Схема: процедуры, которые возвращают другую внутреннюю процедуру

Это из книги SICP, которая, как я уверен, многие из вас знакомы. Это ранний пример в книге, но я чувствую чрезвычайно важную концепцию, которую я пока еще не могу получить. Вот он:

(define (cons x y)
 (define (dispatch m)
   (cond ((= m 0) x)
         ((= m 1) y)
         (else (error "Argument not 0 or 1 - CONS" m))))
 dispatch)
(define (car z) (z 0))
(define (cdr z) (z 1))

Итак, я понимаю, что car и cdr определяются в пределах области cons, и я получаю, что они сопоставляют некоторый аргумент z с 1 и 0 соответственно (аргумент z является некоторым cons). Но скажите, что я называю (cons 3 4)... как оцениваются аргументы 3 и 4, когда мы сразу переходим к этой внутренней процедуре dispatch, которая принимает некоторый аргумент m, который мы еще не указали? И, может быть, что более важно, в чем смысл возвращения "dispatch? Я вообще не понимаю эту часть. Любая помощь приветствуется, спасибо!

Ответ 1

Это один из более странных (и, возможно, один из самых замечательных) примеров использования первоклассных функций в Схеме. Что-то похожее также в Little Schemer, где я впервые увидел его, и я помню, как царапаю голову на несколько дней. Позвольте мне посмотреть, могу ли я объяснить это таким образом, который имеет смысл, но я приношу свои извинения, если это не ясно.

Я предполагаю, что вы понимаете примитивы cons, car и cdr, поскольку они уже реализованы в Схеме, но напомните вам: cons создает пару, car выбирает первый компонент пара и возвращает его, а cdr выбирает второй компонент и возвращает его. Вот простой пример использования этих функций:

> (cons 1 2)
(1 . 2)
> (car (cons 1 2))
1
> (cdr (cons 1 2))
2

Версия cons, car и cdr, которую вы вставили, должна вести себя точно так же. Я попытаюсь показать вам, как.

Прежде всего, car и cdr не определены в рамках cons. В вашем фрагменте кода все три (cons, car и cdr) определены на верхнем уровне. Функция dispatch является единственной, которая определена внутри cons.

Функция cons принимает два аргумента и возвращает функцию одного аргумента. Важно то, что эти два аргумента видны внутренней функции dispatch, которая является тем, что возвращается. Я доберусь до этого момента.

Как я уже сказал в своем напоминании, cons создает пару. Эта версия cons должна делать то же самое, но вместо этого возвращает функцию! Это нормально, нам все равно, как пара реализована или выложена в памяти, пока мы можем получить первый и второй компоненты.

Итак, с этой новой функциональной парой мы должны иметь возможность вызвать car и передать пару в качестве аргумента и получить первый компонент. В определении car этот аргумент называется z. Если бы вы выполняли тот же сеанс REPL, который у меня был выше с помощью этих новых функций cons, car и cdr, аргумент z в car будет привязан к паре функций, которая что cons возвращает, то есть dispatch. Это сбивает с толку, но просто подумайте об этом осторожно, и вы увидите.

Основываясь на реализации car, кажется, что он принимает функцию одного аргумента и применяет его к числу 0. Поэтому, применяя dispatch к 0, и, как вы можете видеть из определения dispatch, это то, что мы хотим. Внутри cond сравнивается m с 0 и 1 и возвращает либо x, либо y. В этом случае он возвращает x, который является первым аргументом cons, другими словами, первым компонентом пары! Таким образом, car выбирает первый компонент, как и обычный примитив в схеме.

Если вы выполните эту же логику для cdr, вы увидите, что она ведет себя почти так же, но возвращает второй аргумент cons, y, который является вторым компонентом пары.

Есть несколько вещей, которые могут помочь вам лучше понять это. Один из них - вернуться к описанию модели замещения оценки в главе 1. Если вы тщательно и тщательно следуете этой модели замещения для некоторого очень простого примера использования этих функций, вы увидите, что они работают.

Другим способом, который является менее утомительным, является попытка воспроизвести функцию dispatch непосредственно в REPL. Ниже переменная p определяется как относящаяся к функции dispatch, возвращаемой cons.

> (define p (cons 1 2))
#<function> ;; what the REPL prints here will be implementation specific
> (p 0)
1
> (p 1)
2

Ответ 2

Код в вопросе показывает, как переопределить примитивную процедуру cons, которая создает cons-cell (пара двух элементов: автомобиль и cdr), используя только закрытие и диспетчеризацию сообщений.

Процедура dispatch действует как селектор аргументов, переданных в cons: x и y. Если получено сообщение 0, возвращается первый аргумент cons (car ячейки). Аналогично, если принимается 1, возвращается второй аргумент cons (cdr ячейки). Оба аргумента хранятся в закрытии, неявно определяемом для процедуры dispatch, замыкание, которое фиксирует x и y и возвращается как продукт вызова этой процедурной реализации cons.

Следующие переопределения car и cdr основываются на этом: car реализуется как процедура, которая передает 0 в закрытие, возвращенную в вышеприведенном определении, и cdr реализуется как процедура который передает 1 в замыкание, в каждом случае в конечном счете возвращает исходное значение, которое было передано как x и y соответственно.

Действительно хорошая часть этого примера состоит в том, что он показывает, что cons-cell, самая основная единица данных в системе Lisp может быть определена как процедура, поэтому размывание различия между данными и процедурой.

Ответ 3

Это, в основном, "изоморфизм замыкания/объекта".

Внешняя функция (cons) - это конструктор класса. Он возвращает объект, который является функцией одного аргумента, где аргумент эквивалентен имени метода. В этом случае методы являются геттерами, поэтому они оценивают значения. Вы могли бы так же легко сохранить больше процедур в объекте, возвращаемом конструктором.

В этом случае числа, выбранные как имена методов и сахаристые процедуры, определенные вне самого объекта. Вы могли бы использовать символы:

(define (cons x y)
  (lambda (method)
    (cond ((eq? method 'car) x)
          ((eq? method 'cdr) y)
          (else (error "unknown method")))))

В этом случае то, что вы более близко напоминаете OO:

# (define p (cons 1 2))
# (p 'car)
1
# (p 'cdr)
2