Реализация каррированных функций в схеме

Что происходит, когда я делаю следующее?

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

Я понимаю, что я могу сделать это:

(define curried (func 5))

И теперь я могу использовать карри. Что мне интересно, так это определение функции. Ли линия

((func x) 1)

создать новую лямбду с x в качестве аргумента, а затем вызвать его на 1? Или это умнее, и он просто повторно использует существующий. (Например, если я это сделаю (curried 0), ((func x) 1)строка будет эквивалентна (curried 1)- это делает схема PLAI?)

10.12.2008 19:48:44
3 ОТВЕТА
РЕШЕНИЕ

В стандарте Схемы указано, что

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

Естественное (нестандартное) обобщение предполагает:

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

Чтобы проверить это, давайте попробуем пример в DrScheme

Добро пожаловать в DrScheme, версия 4.1.3.3-svn5dec2008 [3m]. Язык: модуль; ограничение памяти: 384 мегабайта.

(определить ((fx) y) (список xy)) (f 1)

((f 1) 2) (1 2)

Если мы назовем временное значение, может быть легче увидеть, что происходит:

(определить h (f 1)) (h 2) (1 2) (h 3) (1 3)

Поскольку «Схема PLAI» реализована в DrScheme, я считаю, что она наследует эту сокращенную запись.

8
5.06.2012 08:10:46
Попался. чтобы ответить на мой вопрос сейчас - это расширение произойдет даже в функции 'f', верно?
Claudiu 11.12.2008 17:21:02
О какой е сейчас идет речь?
soegaard 12.12.2008 08:35:48

Прошло слишком много времени с тех пор, как я работал со схемой, но эта статья может оказаться полезной. В нем описывается реализация двух макросов c-lambda и c-define, которые позволяют неявно определять кардинальные выражения лямбда-выражений.

2
10.12.2008 20:03:51
хм, интересная статья, но это поведение, о котором я спрашиваю, встроено в схему plai, и я хочу знать, как она реализована - статья реализует другую версию каррирования.
Claudiu 10.12.2008 20:35:26

Ответ Soegaard является правильным - это традиционное расширение. Тем не менее, drscheme умный!

Следующий код, который я нашел эквивалентным во время выполнения:

Первоначальный источник:

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

Попытка при оптимизации:

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

Код, который интенсивно использует эту функцию (несколько раз, а не один раз), выполняется в 1800 мс для обеих версий. Еще интереснее эта версия (моя визуализация происходящего):

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

Работает на 2000 мс. Таким образом, определенно наблюдается замедление, если бы каждый вызов замещения внутри замены создавал лямбду, но, похоже, это не относится к сокращенной записи.

0
11.12.2008 17:46:42
Если вы выполняете тестирование в DrScheme, не забудьте включить отладку (в языковом меню выберите «Детали») - или попробуйте время в MzScheme.
soegaard 12.12.2008 08:34:47