Стандартный способ вырваться из рекурсии по схеме

Question

Я пишу свою первую программу в схеме. Я довольно глубоко в рекурсии, потому что я в основном интерпретирую программу для простого робота, который может иметь вложенные вызовы процедур.

Если я нахожу нарушение, мне нужно прекратить интерпретацию программы и вернуть последнее действительное состояние.

Я решил это, объявив глобальную переменную (define illegalMoveFlag 0), а затем установив ее через set!.

Он отлично работает, но я предполагаю, что мой наставник не понравится (потому что это не функциональный подход, я думаю)

Другой подход, который я думал о том, чтобы добавить параметр ошибки для каждой функции я называю рекурсивно в программе. Мне это не очень нравится, потому что это сделает мой код намного менее удобочитаемым, но я думаю, что он более «функциональный».

Возможно, есть третий способ, о котором я не думал? И может ли мой подход быть оправданным в этой парадигме, или это в основном запах кода?

Answer 1

Поскольку это была ваша первая программа Scheme, вам, вероятно, просто нужно ввести условное выражение, cond, чтобы избежать дальнейшей рекурсии, когда вы достигаете конца. Например:

; 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) 

Однако, если вам нужен традиционный return, чтобы вернуться как longjmp в C, вам нужно будет хранить и использовать побег продолжения.Это можно сделать так:

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

(display (example)) 

Если let/ec не определен в вашей реализации схемы, то префикс вашу программу:

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

UPDATE:

Обратите внимание, что cond имеет => вариант :

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

Если ca ll преуспевает, тогда первое предложение кладет , и результат привязан к a. Если вызов завершается с ошибкой, , то используется предложение else.

Answer 2

Обычный способ остановить рекурсию - это прекратить рекурсию. т. е. больше не вызывать рекурсивную функцию. :-)

Если это слишком сложно сделать, другой способ вырваться из чего-то состоит в том, чтобы зафиксировать продолжение на верхнем уровне (прежде чем вы начнете рекурсию), а затем вызвать продолжение, когда вам нужно «убежать», , Однако вашему преподавателю может не понравиться этот подход. ;-)

Answer 3

Вы можете использовать встроенную процедуру error, например, так:

(error "Illegal move") ; gives ** Error: Illegal move 

Это вызовет исключение и прекратить интерпретировать программу (хотя я подозреваю, что это не может быть то, что вы находясь в поиске).

Вы также можете предоставить дополнительные аргументы, например:

(error "Illegal move: " move) ; gives ** Error: Illegal move: <move> 

Answer 4

Вы можете выйти из рекурсии (или любого другого процесса), используя продолжение. Не зная больше деталей, я бы порекомендовал вам взглянуть на documentation вашего переводчика.

Answer 5

Сделать illegalMoveFlag в в параметре Я функция вместо глобального переменной

Я дам вам простой пример с факториалами

т.е. 0! = 1 n! = n * (n - 1)! при п (1 ... бесконечность)

позволяет назвать это рекурсивный Факториал

(define (fact-r n) 
    (if 
     [eq? n 0] 
     1 
     (* n (fact-r (- n 1))) 
    ) 
) 

В качестве альтернативы можно использовать параметр функции для завершения рекурсии Назовём это итеративный факторный

(define (fact-i n total) 
    (if 
     (eq? n 0) 
     total 
     (fact-i (- n 1) (* n total)) 
) 
) 

общие потребности начать в 1, поэтому мы должны сделать еще одну функцию, чтобы использовать его лучше

(define (nice-fact n) 
    (fact-i n 1)) 

Вы можете сделать что-то подобное с нелегальнымMoveFlag, чтобы избежать глобальной переменной Насколько можно избежать использования set! идет, нам, вероятно, потребуется дополнительная информация.

В некоторых случаях его все еще довольно сложно избежать использования. Схема полностью завершена без использования набора! однако, когда дело доходит до доступа к внешнему источнику информации, например, к базе данных или набору роботов! может стать единственным практическим решением ...