Могу ли я использовать Common Lisp для SICP или Scheme - единственный вариант?

Question

Кроме того, даже если я могу использовать Common Lisp, я должен? Схема лучше?

Answer 1

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

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

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

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

1. NIL и связанные с этим вопросы и другие названия.

2. Динамический объем.

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

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

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

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

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

Третий пункт также обсуждался в некоторых предыдущих комментариях. На самом деле, у Райнера было довольно хорошее резюме различных вариантов, которые у вас есть, но он не объяснил, насколько сложно это может сделать. Дело в том, что правильная хвостовая оптимизация (TCO) является одним из фундаментальных понятий в Схеме. Достаточно важно, чтобы это была функция языка , а не просто оптимизация. Типичный цикл в Схеме выражается как функция, вызывающая хвост (например, (define (loop) (loop))), а для правильной реализации Схемы требуется , чтобы реализовать TCO, что гарантирует, что это, на самом деле, бесконечный цикл чем бегать ненадолго, пока вы не взорвете пространство стека. В этом вся суть первого не решения Райнера и причина, по которой он пометил его как «ПЛОХОЙ».Его третий вариант - переписывание функциональных циклов (выраженных в виде рекурсивных функций) в виде циклов Common Lisp (dotimes, dolist и печально известного loop) может работать в нескольких простых случаях, но с очень высокой стоимостью: Тот факт, что Scheme - это язык, который обеспечивает надлежащую TCO, является не только фундаментальным для языка, но и одной из основных тем в книге, поэтому, таким образом, вы полностью потеряете эту точку. Кроме того, в некоторых случаях вы просто не можете преобразовать код Scheme в конструкцию цикла Common Lisp - например, когда вы будете работать с книгой, вы сможете реализовать мета-циркуляр. -интерпретатор, который является реализацией языка мини-схем. Требуется определенный щелчок, чтобы понять, что этот мета-оценщик реализует язык, который сам выполняет TCO , если язык, на котором вы реализуете этот оценщик, сам делает TCO. (Обратите внимание, что я говорю о «простых» интерпретаторах - позже в книге вы реализуете этот оценщик как нечто похожее на машину регистрации, где вы как бы явно заставляете ее выполнять TCO.) Суть в том, является то, что этот оценщик - при реализации в Common Lisp - приведет к языку, который сам не делает TCO. Люди, знакомые со всем этим, не должны удивляться: в конце концов, «цикличность» оценщика означает, что вы реализуете язык с семантикой, очень близкой к языку-хозяину - так что в этом случае вы «наследуете» "Семантика Common Lisp, а не семантика TCO Scheme. Однако это означает, что ваш мини-оценщик теперь поврежден: у него нет TCO, поэтому у него нет способа делать циклы! Чтобы получить циклы, вам потребуется реализовать новые конструкции в вашем интерпретаторе, которые обычно будут использовать конструкции итерации в Common Lisp. Но теперь вы уходите еще дальше от того, что в книге, и вкладываете значительные усилия в приблизительно , воплощая идеи SICP на другом языке. Также обратите внимание, что все это связано с предыдущим пунктом, который я поднял: если вы будете следовать книге, то язык, который вы реализуете, будет лексически ограничен, что уведет его дальше от основного языка Common Lisp. В общем, вы полностью теряете свойство «циклическое» в том, что книга называет «мета-циклический оценщик». (Опять же, это то, что может вас не беспокоить, но это повредит общему опыту обучения.) В целом, очень немногие языки приближаются к Scheme, чтобы иметь возможность реализовать семантику языка внутри язык как нетривиальный (например, не использующий eval) оценщик , что легко. На самом деле, если вы используете Common Lisp, то, на мой взгляд, второе предложение Райнера - использовать реализацию Common Lisp, поддерживающую TCO, - лучший путь. Тем не менее, в Common Lisp это в основном оптимизация компилятора: так что вам, вероятно, нужно (а) знать о ручках в реализации, которые нужно повернуть, чтобы реализовать TCO, (б) вам необходимо убедиться, что Common Реализация Lisp на самом деле делает правильную TCO, а не только оптимизацию self вызовов (что гораздо проще, но не так важно), (c) вы бы надеялись , что Реализация Common Lisp, которая делает TCO, может сделать это без ущерба для параметров отладки (опять же, поскольку это считается оптимизацией в Common Lisp, а затем включение этой ручки, компилятор может также принять выражение «мне не важна отладка» «).

Наконец, мой последний пункт не слишком сложен для преодоления, но концептуально он является наиболее важным. В схеме у вас есть единое правило: идентификаторы имеют значение, которое определяется лексически - и вот и все . Это очень простой язык. В Common Lisp, помимо исторического багажа, в котором иногда используется динамическая область, а иногда - лексическая область, у вас есть символы, которые имеют two различное значение - есть значение функции, которое используется всякий раз, когда переменная появляется в заголовок выражения, и существует другое значение , которое используется в противном случае. Например, в (foo foo) каждый из двух экземпляров foo интерпретируется по-разному - первый - это значение функции foo, а второй - значение ее переменной. Опять же, это не трудно преодолеть - есть ряд конструкций, которые вам нужно знать, чтобы справиться со всем этим. Например, вместо записи (lambda (x) (x x)) вам нужно написать (lambda (x) (funcall x x)), что делает вызываемую функцию отображаемой в переменной позиции, поэтому там будет использоваться то же значение; другой пример - (map car something), который вам нужно будет перевести на (map #'car something) (или, точнее, вам нужно будет использовать mapcar, что является эквивалентом Common Lisp функции car); еще одна вещь, которую вам нужно знать, это то, что let связывает слот значения имени, а labels связывает слот функции (и имеет совершенно другой синтаксис, такой же как defun и defvar.) Но концептуальный результат всего этого заключается в том, что Common Lispers, как правило, используют код более высокого порядка гораздо меньше, чем Schemers, и это идет от идиом, распространенных в каждом языке, до того, что реализации будут делать с ним. (Например, многие компиляторы Common Lisp никогда не оптимизируют этот вызов: (funcall foo bar), в то время как компиляторы Scheme оптимизируют (foo bar), как и любое выражение вызова функции, потому что нет другого способа вызова функций.)

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

Answer 2

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

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

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

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

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

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

1. Надеюсь, что стек не взорвется. BAD.
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 (называемая Pseudo Scheme), которая должна выполнять большую часть кода в 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 очень просто:

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

Давайте определим имена Scheme для некоторых функций. Общий код Лисп:

(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 упоминает delay, the-empty-stream и cons-stream, но не реализует его. Мы предоставляем здесь реализацию в 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 отличается от stream-for-each:

• нам нужно использовать 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

Answer 3

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

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

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

Answer 4

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

---

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

Answer 5

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

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