Implémentation de fonctions cariées dans le schéma

Question

Que se passe-t-il lorsque je fais ce qui suit?

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

Je comprends que je peux le faire:

(define curried (func 5)) 

Et maintenant, je peux utiliser cari. Ce qui m'intéresse, c'est la définition de la fonction. Est-ce que la ligne

((func x) 1) 

crée un nouveau lambda avec x comme argument, puis invoque-le sur 1? Ou est-ce plus intelligent que cela et il réutilise juste celui existant. (Par exemple, si je fais (curried 0), la ligne ((func x) 1) équivaudrait à (curried 1) - ne PLAI Scheme fait cela?)

Answer 1

Dans le standard schéma il est précisé que

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

La généralisation naturelle (non standard) implique:

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

Pour le tester, nous allons essayer l'exemple DrScheme

Bienvenue sur DrScheme, version 4.1.3.3-svn5dec2008 [3m]. Langue: Module; limite de mémoire: 384 mégaoctets

(définie ((fx) y) (liste xy)) (f 1)

((f 1) 2) (1 2)

Si nous nommons la valeur temporaire, il peut être plus facile de voir ce qui se passe:

(define h (f 1)) (h 2) (1 2) (h 3) (1 3)

Depuis "PLAI Scheme" est mis en œuvre DrScheme, je crois qu'il hérite de cette notation de raccourci.

Answer 2

Il y a trop longtemps que je travaille avec le schéma, mais vous pourriez trouver this article utile. Il décrit l'implémentation de deux macros, c-lambda et c-define qui permettent des définitions curriculaires implicites d'expressions lambda.

Answer 3

La réponse de soegaard est correcte - c'est l'expansion traditionnelle. Cependant, drscheme est intelligent!

Le code suivant que j'ai trouvé être équivalent en temps d'exécution:

Source 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])) 

Tentative d'optimisation:

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

code

qui utilise largement cette fonction (plusieurs fois, pas une seule fois) s'exécute à 1800 ms pour les deux versions. Plus intéressant, cette version (ma visualisation de ce qui se passait):

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

Fonctionne à 2000 ms. Il y a donc certainement un ralentissement si les appels à substituer à l'intérieur du substitut créaient chacun un lambda, mais il semble que ce ne soit pas le cas avec la notation de raccourci.