Standard way for breaking out of recursion in scheme

Question

I am writing my first program in scheme. I get pretty deep into recursion because I basically interpret a program for a simple robot which can have nested procedure calls.

If I find a violation I need to stop interpreting the program and return the last valid state.

I've solved it by declaring a global variable (define illegalMoveFlag 0) and then setting it via set!.

It works fine, but I guess my tutor won't like it (because it's not functional approach I guess)

Other approach I've thought about is to add an error parameter to every function I call recursively in the program. I don't quite like it because it would make my code far less readable, but I guess it's more 'functional'.

Is there maybe a third way I didn't think about? And can my approach be justified in this paradigm, or is it basically a code smell?

Answer 1

Since this was your first Scheme program, you probably just need to introduce a conditional expression, cond, in order to avoid further recursion when you reach the end. For example:

; sum : natural -> natural
;  compute the sum 0+1+...+max
(define (sum max)
  (define (sum-helper i sum-so-far)
    (if (> i max)
        sum-so-far
        (sum-helper (+ i 1) (+ sum-so-far i))))
  (sum-helper 0 0))

(display (sum 10))
(newline)

However, if you need a traditional return to return like longjmp in C, you will need to store and use an escape continuation. This can be done like this:

(define (example)
  (let/ec return
    (define (loop n)
      (if (= n 100000)
          (return (list "final count: " n))
          (loop (+ n 1))))
    (loop 0)))

(display (example))

If let/ec is not defined in your Scheme implementation, then prefix your program with:

(define-syntax let/ec 
  (syntax-rules ()
    [(_ return body ...)
     (call-with-current-continuation
      (lambda (return)
        body ...))]))

UPDATE:

Note that cond has an => variant:

(cond
  [(call-that-can-fail)
    => (lambda (a) <use-a-here>))]
  [else <do-something-else>])

If the call succeeds then the first, clause is taken and the result is bound to a. If the call fails, then the else clause is used.

Answer 2

The usual way to stop recursing is, well, to stop recursing. i.e., don't call the recursive function any longer. :-)

If that is too hard to do, the other way to break out of something is to capture a continuation at the top level (before you start recursing), then invoke the continuation when you need to "escape". Your instructor may not like this approach, though. ;-)