Modo standard per interrompere la ricorsione nello schema

Question

Sto scrivendo il mio primo programma nello schema. Vado abbastanza in profondità nella ricorsione perché fondamentalmente interpreto un programma per un semplice robot che può avere chiamate di procedure annidate.

Se trovo una violazione, devo interrompere l'interpretazione del programma e restituire l'ultimo stato valido.

L'ho risolto dichiarando una variabile globale (define illegalMoveFlag 0) e quindi impostandola tramite set!.

Funziona bene, ma credo che il mio tutor non piacerà (perché non è approccio funzionale immagino)

altro approccio che ho pensato è quello di aggiungere un parametro di errore per ogni funzione che io chiamo ricorsivamente nel programma. Non mi piace molto perché renderebbe il mio codice molto meno leggibile, ma immagino sia più "funzionale".

C'è forse una terza via a cui non ho pensato? E il mio approccio può essere giustificato in questo paradigma o fondamentalmente è un odore di codice?

Answer 1

Poiché questo è stato il primo programma Scheme, probabilmente è necessario introdurre un'espressione condizionale, cond, per evitare ulteriori ricorsioni quando si raggiunge la fine. Per esempio:

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

Tuttavia, se avete bisogno di un tradizionale return per tornare come longjmp in C, avrete bisogno di memorizzare e utilizzare una continuazione di fuga.Questo può essere fatto in questo modo:

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

(display (example)) 

Se let/ec non è definito nell'implementazione Scheme, fare precedere il programma con:

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

UPDATE:

noti che cond ha un => variante :

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

Se il ca ll succede allora la prima clausola è presa e il risultato è legato a a. Se la chiamata fallisce, viene utilizzata la clausola else.

Answer 2

Il modo usuale per interrompere la ricorrenza è, beh, smettere di ricorrere. vale a dire, non chiamare più la funzione ricorsiva. :-)

Se questo è troppo difficile da fare, l'altro modo per uscire da qualcosa è catturare una continuazione al livello più alto (prima di ricominciare da capo), quindi invocare la continuazione quando è necessario "scappare" . Il tuo istruttore potrebbe non gradire questo approccio, però. ;-)

Answer 3

si potrebbe desiderare di utilizzare la procedura di built-in error, in questo modo:

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

Ciò solleva un'eccezione e smettere di interpretare il programma (anche se ho il sospetto che questo potrebbe non essere ciò che sei cercando).

È possibile anche fornire argomenti aggiuntivi, in questo modo:

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

Answer 4

È possibile uscita di una ricorsione (o da qualsiasi altro processo) utilizzando una continuazione. Senza conoscere ulteriori dettagli, ti consiglio di dare un'occhiata allo documentation del tuo interprete.

Answer 5

Fare illegalMoveFlag un paramter nella funzione invece di una variabile globale

Vi darò un semplice esempio con fattoriali

cioè: 0! = 1 n! = n * (n - 1)! quando n (1 ... infinito)

consente di chiamare questo un fattoriale ricorsiva

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

Un'alternativa sarebbe quella di utilizzare un parametro per la funzione di porre fine alla ricorsione consente di chiamare iterativo fattoriale

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

fabbisogno totale a partire dal numero 1 in modo dovremmo fare un'altra funzione per rendere più bello usarlo

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

Si potrebbe fare qualcosa di simile con illegalMoveFlag per evitare di avere una variabile globale Per quanto si eviti di usare set! va, probabilmente avremo bisogno di più informazioni.

In alcuni casi è ancora piuttosto difficile evitare di usarlo. Lo schema è completamente completo senza l'uso del set! tuttavia quando si tratta di accedere a una fonte esterna di informazioni come un database o un set di robot! può diventare l'unica soluzione pratica ...