Implementazione di funzioni curry in Scheme

Question

Che cosa succede quando faccio la seguente?

(define ((func x) y)
    (if (zero? y)
        ((func x) 1)
        12))

Mi rendo conto che posso fare questo:

(define curried (func 5))

E ora posso usare al curry. Quello che mi incuriosisce è nella definizione della funzione. Fa la riga

((func x) 1)

creare un nuovo lambda con x come argomento, e quindi richiamare su 1? O è più intelligente di quello e appena ri-usa quello esistente. (Per esempio, se faccio (curried 0), la linea ((func x) 1) sarebbe equivalente a (curried 1) -? Fa PLAI Scheme fare questo)

Answer 1

Nello standard Scheme si precisa che

(define (f x) 42) is short for (define f (lambda (x) 42)) .

La naturale (non standard) generalizzazione implica:

(define ((f x) y) (list x y)) is short for (define (f x) (lambda (y) (list x y)))
                which is short for (define f (lambda (x) (lambda (y) (list x y))))

Per provarlo, proviamo l'esempio in DrScheme

Benvenuti a DrScheme, versione 4.1.3.3-svn5dec2008 [3m]. Lingua: Module; limite di memoria:. 384 megabyte

  

(define ((f x) y) (elenco x y))   (F 1)

     

     

((f 1) 2)   (1 2)

Se nominiamo il valore temporaneo, potrebbe essere più facile per vedere cosa succede:

  

(definire h (f 1))   (H 2)   (1 2)   (H 3)   (1 3)

Dal momento che "Schema PLAI" è implementato in DrScheme, credo che eredita questa notazione scorciatoia.

Answer 2

E 'passato troppo tempo da quando ho lavorato con lo schema, ma si potrebbe trovare questo articolo utile. Essa descrive la realizzazione di due macro, c-lambda e C-definire quali permettono definizioni curry implicite di espressioni lambda.

Answer 3

La risposta di Soegaard è corretta - questo è l'espansione tradizionale. Tuttavia, drscheme è intelligente!

Il seguente codice che ho trovato per essere equivalente a tempo di esecuzione:

Fonte originale:

(define ((substitute lv value) e)
  (cond [(LogicVar? e)
     (type-case LogicVar e
       [lv-any (id) (if (symbol=? id (lv-any-id lv))
                value
                e)]
       [lv-cons (f r) 
            (lv-cons ((substitute lv value) f)
                 ((substitute lv value) r))])]
    [(cons? e)
     (cons ((substitute lv value) (car e))
           ((substitute lv value) (cdr e)))]
    [else e]))

Tentativo di ottimizzazione:

(define (substitute lv value)
  (local ([define inner
        (lambda (e)
          (cond [(LogicVar? e)
             (type-case LogicVar e
               [lv-any (id) (if (symbol=? id (lv-any-id lv))
                    value
                    e)]
               [lv-cons (f r) 
                (lv-cons (inner f)
                     (inner r))])]
            [(cons? e)
             (cons (inner (car e))
               (inner (cdr e)))]
            [else e]))])
    inner))

Codice che utilizza pesantemente questa funzione (più volte, non solo una volta) corre a 1800 ms per entrambe le versioni. Più interessante, questa versione (la mia visualizzazione di ciò che stava accadendo):

(define (substitute lv value)
  (local ([define inner
        (lambda (e)
          (cond [(LogicVar? e)
             (type-case LogicVar e
               [lv-any (id) (if (symbol=? id (lv-any-id lv))
                    value
                    e)]
               [lv-cons (f r) 
                (lv-cons ((substitute lv value) f)
                     ((substitute lv value) r))])]
            [(cons? e)
             (cons ((substitute lv value) (car e))
               ((substitute lv value) (cdr e)))]
            [else e]))])
    inner))

Funziona a 2000 ms. Quindi non v'è sicuramente un rallentamento se le chiamate a sostituire entro sostituto sono stati ciascuna creando una lambda, ma sembra non è questo il caso con la notazione di scelta rapida.