Я могу использовать язык Common LISP для SICP, или действительно ли Схема является единственной опцией?

Вы уже знакомы с Common Lisp? Я предполагаю, что это то, что вы подразумеваете под «Лиспом». В этом случае вы можете использовать его вместо Scheme. Если вы тоже не знаете, и вы работаете через SICP исключительно для обучения, то, вероятно, вам лучше использовать Scheme. Он имеет гораздо лучшую поддержку для новичков, и вам не придется переводить со Scheme на Common Lisp.

Есть различия; в частности, высокофункциональный стиль SICP более многословен в Common Lisp, потому что вы должны заключать функции в кавычки при их передаче и использовать funcall для вызова функции, привязанной к переменной.

Однако, если вы хотите использовать Common Lisp, вы можете попробовать использовать переводы кода SICP Эли Бендерски на Common Lisp под тегом SICP .

Редактировать: Комментарий Натана Сандерса верен. Ясно, что прошло много времени с тех пор, как я последний раз читал книгу, но я только что проверил, и он не использует напрямую call / cc . Я поддержал ответ Натана.

---

Что бы вы ни использовали, необходимо реализовать продолжения, которые SICP часто использует. Даже не все интерпретаторы Scheme реализуют их, и я не знаю ни одного Common Lisp, который бы их реализовал.

Они похожи, но не одинаковы.

Я считаю, что если вы выберете схему, это будет проще.

Использование SICP с Common Lisp возможно и интересно

Вы можете использовать Common Lisp для обучения с SICP без особых проблем. Подмножество схем, которое используется в книге, не очень сложно. SICP не использует макросы и не использует продолжения. Есть DELAY и FORCE, которые можно написать на Common Lisp в несколько строк.

Также для новичков использование (function foo) и (funcall foo 1 2 3) на самом деле лучше (IMHO!), Потому что код становится понятнее при изучении функционального программирования части. Вы можете видеть, где вызываются / передаются переменные и лямбда-функции.

Оптимизация хвостового вызова в Common Lisp

Есть только одна большая область, в которой использование Common Lisp имеет недостаток: оптимизация хвостового вызова ( ТШО). Common Lisp не поддерживает TCO в своем стандарте (из-за нечеткого взаимодействия с остальным языком, не все компьютерные архитектуры поддерживают его напрямую (подумайте о JVM), не все компиляторы поддерживают его (некоторые Lisp Machine), он делает некоторую отладку / трассировку / шагая сильнее, ...).

Есть три способа смириться с этим:

1. Надежда, что стек не разорвется. ПЛОХО.
2. Используйте реализацию Common Lisp, поддерживающую TCO. Есть некоторые. См. Ниже.
3. Перепишите функциональные циклы (и подобные конструкции) в циклы (и аналогичные конструкции), используя DOTIMES, DO, LOOP, ...

Лично я бы рекомендовал 2 или 3.

Common Lisp отлично и простые в использовании компиляторы с поддержкой TCO (SBCL, LispWorks, Allegro CL, Clozure CL, ...), а в качестве среды разработки используйте либо встроенные, либо GNU Emacs / SLIME.

Для использования с SICP я бы хотел рекомендую SBCL , поскольку он всегда компилируется по умолчанию, по умолчанию имеет поддержку TCO, а компилятор выявляет множество проблем с кодированием (необъявленные переменные, неправильные списки аргументов, множество ошибок типов, ...). Это очень помогает во время обучения. Обычно убедитесь, что код скомпилирован, поскольку интерпретаторы Common Lisp обычно не поддерживают TCO.

Иногда также может быть полезно написать один или два макроса и предоставить некоторые имена функций Scheme, чтобы код выглядел немного более похожим на Scheme. Например, у вас может быть макрос DEFINE в Common Lisp.

Для более продвинутых пользователей существует старая реализация Scheme, написанная на Common Lisp (называемая псевдосхемой), которая должна запускать большую часть кода в SICP.

Моя рекомендация: если вы хотите пройти лишнюю милю и использовать Common Lisp, сделайте это.

Чтобы упростить понимание необходимых изменений, я добавил несколько примеров - помните, что для этого нужен компилятор Common Lisp с поддержкой для оптимизации хвостового вызова :

Пример

Давайте посмотрим на этот простой код из SICP:

(define (factorial n)
  (fact-iter 1 1 n))

(define (fact-iter product counter max-count)
  (if (> counter max-count)
      product
      (fact-iter (* counter product)
                 (+ counter 1)
                 max-count)))

Мы можем использовать его непосредственно в Common Lisp с макросом DEFINE :

(defmacro define ((name &rest args) &body body)
  `(defun ,name ,args ,@body))

Теперь вам следует использовать SBCL, CCL, Allegro CL или LispWorks. Эти компиляторы поддерживают TCO по умолчанию.

Давайте использовать SBCL:

* (define (factorial n)
    (fact-iter 1 1 n))
; in: DEFINE (FACTORIAL N)
;     (FACT-ITER 1 1 N)
; 
; caught STYLE-WARNING:
;   undefined function: FACT-ITER
; 
; compilation unit finished
;   Undefined function:
;     FACT-ITER
;   caught 1 STYLE-WARNING condition

FACTORIAL
* (define (fact-iter product counter max-count)
    (if (> counter max-count)
        product
        (fact-iter (* counter product)
                   (+ counter 1)
                   max-count)))

FACT-ITER
* (factorial 1000)

40238726007709....

Другой пример: символическое дифференцирование

SICP имеет пример схемы для дифференцирования:

(define (deriv exp var)
  (cond ((number? exp) 0)
        ((variable? exp)
         (if (same-variable? exp var) 1 0))
        ((sum? exp)
         (make-sum (deriv (addend exp) var)
                   (deriv (augend exp) var)))
        ((product? exp)
         (make-sum
           (make-product (multiplier exp)
                         (deriv (multiplicand exp) var))
           (make-product (deriv (multiplier exp) var)
                         (multiplicand exp))))
        (else
         (error "unknown expression type -- DERIV" exp))))

Выполнить этот код в Common Lisp очень просто:

• некоторые функции имеют разные имена, число? равно числоp в CL
• CL: COND использует T вместо else
• CL : ERROR использует строки формата CL

Давайте определим имена схем для некоторых функций. Код Common Lisp:

(loop for (scheme-symbol fn) in
      '((number?      numberp)
        (symbol?      symbolp)
        (pair?        consp)
        (eq?          eq)
        (display-line print))
      do (setf (symbol-function scheme-symbol)
               (symbol-function fn)))

Наш макрос define сверху:

(defmacro define ((name &rest args) &body body)
  `(defun ,name ,args ,@body))

Код Common Lisp:

(define (variable? x) (symbol? x))

(define (same-variable? v1 v2)
  (and (variable? v1) (variable? v2) (eq? v1 v2)))

(define (make-sum a1 a2) (list '+ a1 a2))

(define (make-product m1 m2) (list '* m1 m2))

(define (sum? x)
  (and (pair? x) (eq? (car x) '+)))

(define (addend s) (cadr s))

(define (augend s) (caddr s))

(define (product? x)
  (and (pair? x) (eq? (car x) '*)))

(define (multiplier p) (cadr p))

(define (multiplicand p) (caddr p))

(define (deriv exp var)
  (cond ((number? exp) 0)
        ((variable? exp)
         (if (same-variable? exp var) 1 0))
        ((sum? exp)
         (make-sum (deriv (addend exp) var)
                   (deriv (augend exp) var)))
        ((product? exp)
         (make-sum
           (make-product (multiplier exp)
                         (deriv (multiplicand exp) var))
           (make-product (deriv (multiplier exp) var)
                         (multiplicand exp))))
        (t
         (error "unknown expression type -- DERIV: ~a" exp))))

Давайте попробуем его в LispWorks:

CL-USER 19 > (deriv '(* (* x y) (+ x 3)) 'x)
(+ (* (* X Y) (+ 1 0)) (* (+ (* X 0) (* 1 Y)) (+ X 3)))

Пример потоков из SICP в Common Lisp

См. код книги в главе 3.5 в SICP. Мы используем дополнения к CL сверху.

SICP упоминает задержку , пустой поток и cons-поток , но не реализует его. Мы предоставляем здесь реализацию на Common Lisp:

(defmacro delay (expression)
  `(lambda () ,expression))

(defmacro cons-stream (a b)
  `(cons ,a (delay ,b)))

(define (force delayed-object)
  (funcall delayed-object))

(defparameter the-empty-stream (make-symbol "THE-EMPTY-STREAM"))

Теперь идет переносимый код из книги:

(define (stream-null? stream)
  (eq? stream the-empty-stream))

(define (stream-car stream) (car stream))

(define (stream-cdr stream) (force (cdr stream)))

(define (stream-enumerate-interval low high)
  (if (> low high)
      the-empty-stream
    (cons-stream
     low
     (stream-enumerate-interval (+ low 1) high))))

Теперь Common Lisp отличается потоком для каждого :

• нам нужно использовать cl: progn вместо begin
• параметры функции необходимо вызывать с помощью cl: funcall

Вот версия:

(defmacro begin (&body body) `(progn ,@body))

(define (stream-for-each proc s)
  (if (stream-null? s)
      'done
      (begin (funcall proc (stream-car s))
             (stream-for-each proc (stream-cdr s)))))

Нам также необходимо передавать функции, используя cl : function :

(define (display-stream s)
  (stream-for-each (function display-line) s))

Но тогда пример работает:

CL-USER 20 > (stream-enumerate-interval 10 20)
(10 . #<Closure 1 subfunction of STREAM-ENUMERATE-INTERVAL 40600010FC>)

CL-USER 21 > (display-stream (stream-enumerate-interval 10 1000))

10 
11 
12 
...
997 
998 
999 
1000 
DONE

У вас есть несколько ответов, но ни один из них не является исчерпывающим (и я не говорю о том, чтобы иметь достаточно деталей или быть достаточно длинным). Прежде всего, подведем итоги: вам следует не использовать Common Lisp, если вы хотите получить хороший опыт работы с SICP.

Если вы не очень хорошо разбираетесь в Common Lisp, то просто примите это как . (Очевидно, вы можете не принимать во внимание этот совет, как и все остальное, некоторые люди усваивают только трудный путь.)

Если вы уже знаете Common Lisp, вы можете справиться с этим, но со значительными усилиями и со значительным ущербом для вашего общего учебный опыт. Есть несколько фундаментальных проблем, разделяющих Common Lisp и Scheme, из-за которых использование первого с SICP является довольно плохой идеей. Фактически, если у вас есть уровень знаний, чтобы заставить его работать, то вы ' в любом случае, скорее всего, выше уровня SICP. Я не говорю, что это невозможно - конечно, можно реализовать всю книгу на Common Lisp (например, см. Страницы Бендерского) так же, как вы можете сделать это на C, Perl или чем-то еще. С языками, которые находятся дальше от Scheme, будет все сложнее. (Например, ML, вероятно, будет проще использовать, чем Common Lisp, даже если его синтаксис сильно отличается.)

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

1. NIL и связанные с ними проблемы, а также разные имена .

2. Динамическая область видимости.

3. Оптимизация хвостового вызова.

4. Отдельное пространство имен для функций и значений.

I ' Сейчас я подробнее остановлюсь на каждом из этих пунктов:

Первый пункт является наиболее техническим. В Common Lisp NIL используется и как пустой список, и как ложное значение. Само по себе это не большая проблема, и на самом деле первая редакция SICP имела аналогичное предположение - где пустой список и ложь имели одно и то же значение. Однако NIL Common Lisp все же отличается: это также символ. Итак, в Scheme у вас есть четкое разделение: что-то является либо списком, либо одним из примитивных типов значений - но в Common Lisp NIL не только false и пустой список: это также символ. В дополнение к этому вы получаете множество немного различающихся поведений - например, в Common Lisp голова и хвост ( car и cdr ) пустого списка сами по себе являются пустым списком, а в Scheme вы получите ошибку времени выполнения, если попробуете это . В довершение всего у вас есть разные имена и соглашения об именах, например - предикаты в Common Lisp по соглашению заканчиваются на P (например, listp ), а предикаты в Scheme заканчиваются на вопросительный знак (например, список? ); мутаторы в Common Lisp не имеют специального соглашения (некоторые имеют префикс N ), тогда как в Scheme они почти всегда имеют суффикс ! . Кроме того, простое присваивание в Common Lisp - это , обычно setf , и оно также может работать с комбинациями (например, (setf (car foo) 1) ), а в Scheme - набор! и ограничивается установкой только связанных переменных. (Обратите внимание, что Common Lisp также имеет ограниченную версию, она называется setq . Однако ее почти никто не использует.)

Второй момент гораздо более глубокий и, возможно, приведет к совершенно непонятному поведению. вашего кода. Дело в том, что в Common Lisp аргументы функции имеют лексическую область видимости, но переменные, объявленные с помощью defvar , имеют динамическую область видимости. Существует целый ряд решений, которые полагаются на привязки с лексической областью видимости - и в Common Lisp они просто не будут работать. Конечно, тот факт, что Common Lisp имеет лексическую область видимости , означает, что вы можете обойти это, если будете очень осторожны с новыми привязками и, возможно, использовать макросы для обхода динамической области по умолчанию - но опять же, для этого требуются гораздо более обширные знания, чем у обычного новичка. Ситуация становится еще хуже: если вы объявляете конкретное имя с помощью defvar , то это имя будет динамически привязано , даже если являются аргументами функций. Это может привести к очень сложным для отслеживания ошибкам, которые проявляются крайне запутанным образом (вы в основном получаете неправильное значение, и вы не будете знать, почему это происходит). Опытные Common Lispers знают об этом (особенно те, которые были сожжены им), и будут всегда следовать соглашению об использовании звездочек вокруг имен с динамической областью видимости (например, * foo * ). (И, кстати, на жаргоне Common Lisp эти переменные с динамической областью видимости называются просто "специальными переменными" - что является еще одним источником путаницы для новичков.)

Третий момент также обсуждался в некоторых из предыдущих комментариев. Фактически, у Райнера было довольно хорошее резюме различных вариантов, которые у вас есть, но он не объяснил, насколько сложно это может сделать. Дело в том, что правильная оптимизация хвостовой части (TCO) - одна из фундаментальных концепций в Scheme. Достаточно важно, чтобы это была функция языка , а не просто оптимизация. Типичный цикл в Схеме выражается как функция вызова хвоста (например, (define (loop) (loop)) ), и требуются соответствующие реализации схемы для реализации TCO, которая будет Гарантировать, что это, по сути, бесконечный цикл, а не работать в течение короткого времени, пока вы не взорвете пространство стека. В этом вся суть Райнера » Его третий вариант - переписывание функциональных циклов (выраженных как рекурсивные функции) как циклов Common Lisp ( dotimes , dolist и печально известный цикл ) может работать для несколько простых случаев, но за очень высокую цену: тот факт, что Scheme - это язык, обеспечивающий надлежащую совокупную стоимость владения, не только фундаментален для языка, но и является одной из основных тем в книге, поэтому, сделав это, вы сможете полностью потеряли эту точку. Кроме того, есть некоторые случаи, когда вы просто не можете преобразовать код схемы в конструкцию цикла Common Lisp - например, по мере прохождения книги вы можете реализовать мета-циркуляр -интерпретатор, который является реализацией языка мини-схем. Требуется определенный щелчок, чтобы понять, что этот мета-оценщик реализует язык, который сам выполняет TCO , если язык, на котором вы реализуете этот оценщик, сам выполняет TCO. (Обратите внимание, что я говорю о «простых» интерпретаторах - позже в книге вы реализуете этот оценщик как нечто близкое к регистровой машине, где вы явно заставляете его выполнять совокупную стоимость владения.) Суть всего этого, заключается в том, что этот анализатор - когда он реализован в Common Lisp - приведет к языку, который сам не выполняет TCO. Людям, знакомым со всем этим, не следует удивляться: в конце концов, «замкнутость» оценщика означает, что вы реализуете язык с семантикой, очень близкой к основному языку, поэтому в этом случае вы «наследуете» " семантика Common Lisp, а не семантика TCO схемы. Однако это означает, что ваш мини-оценщик теперь поврежден: у него нет TCO, поэтому он не может выполнять циклы! Чтобы получить циклы, вам нужно будет реализовать новые конструкции в вашем интерпретаторе, который обычно будет использовать итерационные конструкции в Common Lisp. Но теперь вы уходите еще дальше от того, что написано в книге, и вкладываете значительные усилия в примерно реализацию идей SICP на другом языке. Также обратите внимание, что все это связано с предыдущим вопросом, который я поднял: если вы следите за книгой, тогда язык, который вы реализуете, будет иметь лексическую область видимости, уводя его дальше от основного языка Common Lisp. Таким образом, вы полностью теряете свойство «круговорота» в том, что книга называет « На самом деле, если вы действительно используете Common Lisp, то, на мой взгляд, второе предложение Райнера - используйте реализацию Common Lisp, поддерживающую TCO - лучший способ. Однако в Common Lisp это, по сути, оптимизация компилятора: поэтому вам, вероятно, потребуется (а) знать о регуляторах в реализации, которые вам нужно повернуть, чтобы добиться TCO, (б) вам нужно будет убедиться, что Common Lisp Реализация Lisp на самом деле выполняет правильную совокупную стоимость владения, а не просто оптимизацию вызовов self (что является гораздо более простым случаем, который не так важен), (c) вы надеетесь , что Реализация Common Lisp, которая выполняет TCO, может сделать это, не повреждая параметры отладки (опять же, поскольку это считается оптимизацией в Common Lisp, то включение этой ручки также может быть воспринято компилятором как выражение " каждый из двух экземпляров foo интерпретируется по-разному: первый - это значение функции foo , а второй - значение его переменной. Опять же, это несложно преодолеть - есть ряд конструкций, о которых вам нужно знать, чтобы справиться со всем этим. Например, вместо записи (lambda (x) (xx)) вам нужно написать (lambda (x) (funcall xx)) , что делает вызываемую функцию появляются в переменной позиции, поэтому там будет использоваться то же значение; другой пример - (map car something) , который вам нужно будет перевести в (map # 'car something) (или, точнее, вам нужно будет использовать mapcar ], который является эквивалентом функции car в Common Lisp); Но концептуальный результат всего этого состоит в том, что Common Lispers склонны использовать код более высокого порядка намного реже, чем Schemers, и это идет от идиом, общих для каждого языка, до того, что реализации будут с ним делать. (Например, многие компиляторы Common Lisp никогда не оптимизируют этот вызов: (funcall foo bar) , тогда как компиляторы Scheme оптимизируют (foo bar) , как любое выражение вызова функции, потому что существует нет другого способа вызова функций.)

Наконец, я отмечу, что большая часть вышеперечисленного является очень хорошим материалом для борьбы с пламенем: передавайте любую из этих проблем на общедоступный форум Lisp или Scheme (в частности, comp.lang.lisp и comp.lang.scheme ), и вы, скорее всего, увидите длинную цепочку, в которой люди объясняют, почему их выбор намного лучше, чем другой, или почему некоторая «так называемая особенность» на самом деле является идиотским решением, которое было принято языковыми разработчиками, которые в то время были явно очень пьяными, и т. д. Но дело в том, что это просто различия между двумя языками, и в конечном итоге люди могут получить их работа сделана в любом из них. Просто так случается, что если работа «выполняет SICP», то Scheme будет намного проще, учитывая, как она решает каждую из этих проблем с точки зрения Scheme. Если вы хотите изучить Common Lisp, то использование учебника Common Lisp оставит вас гораздо менее разочарованным.

и в конечном итоге люди могут выполнять свою работу в любом из них. Просто так случается, что если работа «выполняет SICP», то Scheme будет намного проще, учитывая, как она решает каждую из этих проблем с точки зрения Scheme. Если вы хотите изучить Common Lisp, то использование учебника Common Lisp оставит вас гораздо менее разочарованным.

и в конечном итоге люди могут выполнять свою работу в любом из них. Просто так случается, что если работа «выполняет SICP», то Scheme будет намного проще, учитывая, как она решает каждую из этих проблем с точки зрения Scheme. Если вы хотите изучить Common Lisp, то использование учебника Common Lisp оставит вас гораздо менее разочарованным.