Подтвердить что ты не робот

Могу ли я использовать Common Lisp для SICP или есть только схема?

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

4b9b3361

ОТВЕТЫ

Ответ 1

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

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

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

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

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

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

  • Оптимизация звонков.

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

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

Первый момент - самый технический. В Common Lisp, NIL используется как пустой список, так и как ложное значение. Само по себе это не является большой проблемой, и на самом деле первое издание SICP имело аналогичное предположение: где пустой список и ложные значения были одинаковыми. Однако Common Lisp NIL по-прежнему отличается: это также символ. Итак, на Схеме у вас четкое разделение: что-то есть либо список, либо один из примитивных типов значений, но в Common Lisp, NIL не только false и пустой список: это также символ, В дополнение к этому вы получаете несколько разных действий - например, в Common Lisp голова и хвост (car и cdr) пустого списка сами являются пустым списком, а в Если вы попробуете это, вы получите ошибку времени выполнения. В довершение всего, у вас есть разные имена и соглашения об именах, например - предикаты в Common Lisp завершаются по соглашению с P (например, listp), в то время как предикаты в конце Схемы в вопросительном знаке (например, list?); мутаторы в Common Lisp не имеют специального соглашения (некоторые имеют префикс N), тогда как в Схеме они почти всегда имеют суффикс !. Кроме того, обычное назначение в 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 требуются правильные реализации Схемы, которые гарантируют, что это, по сути, бесконечный цикл, а не запуск на короткое время пока вы не взорвите пространство стека. Это все сущность первого решения Райнера, и причина, по которой он назвал его "ПЛОХОЙ". Его третий вариант - переписывание функциональных циклов (выраженных как рекурсивные функции) в виде общих циклов Lisp (dotimes, dolist и печально известного loop) может работать в нескольких простых случаях, но при очень высокой стоимости: тот факт, что Scheme является языком, который делает надлежащую TCO, не только фундаментален для языка - это также одна из основных тем в книге, поэтому, таким образом, вы полностью потеряете эту точку. Кроме того, есть некоторые случаи, когда вы просто не можете перевести код схемы в общую конструкцию цикла Lisp - например, по мере того, как вы прокладываете себе путь через книгу, вы сможете реализовать мета-циркуляр-интерпретатор, который реализация языка мини-схем. Требуется определенный щелчок, чтобы понять, что этот метааналитик реализует язык, который сам выполняет TCO, если язык, которым вы реализуете этот оценщик, сам выполняет TCO. (Обратите внимание, что я говорю о "простых" интерпретаторах - позже в книге вы реализуете этот оценщик как нечто близкое к машине регистрации, где вы явно делаете это с помощью TCO). Суть всего этого, заключается в том, что этот оценщик - когда он реализован в Common Lisp - приведет к языку, который сам по себе не выполняет TCO. Люди, знакомые со всем этим, не должны удивляться: в конце концов, "круглость" оценщика означает, что вы реализуете язык с семантикой, который очень близок к языку хоста, - поэтому в этом случае вы "наследуете" "Общая семантика Lisp, а не семантика схемы TCO. Однако это означает, что ваш мини-оценщик теперь искалечен: он не имеет TCO, поэтому он не имеет возможности делать петли! Чтобы получить петли, вам нужно будет реализовать новые конструкторы в вашем интерпретаторе, которые обычно будут использовать конструкции итерации в Common Lisp. Но теперь вы уходите от того, что в книге, и вы вкладываете значительные усилия в примерно реализацию идей в SICP на разные языки. Обратите также внимание на то, что все это связано с предыдущей точкой, которую я поднял: если вы следуете за книгой, тогда язык, который вы реализуете, будет лексически охвачен, отвлекая его от основного языка Lisp. Таким образом, вы полностью потеряете" круговую "собственность в том, что книга называет" мета-круговой оценщик". (Опять же, это то, что может вас не беспокоить, но это повредит общему опыту обучения.) В целом, очень немногие языки приближаются к Схеме в возможности реализовать семантику языка внутри языка как не- тривиальный (например, не используя eval) оценщик, который легко. На самом деле, если вы идете с общим Lisp, то, на мой взгляд, второе предложение Райнера - используйте реализацию Common Lisp, которая поддерживает TCO - это лучший способ. Однако в Common Lisp это в основном оптимизация компилятора: поэтому вам, скорее всего, понадобятся (а) знать о ручках в реализации, которые необходимо включить, чтобы сделать TCO, (b) вам нужно будет убедиться, что реализация Common Lisp на самом деле делает правильную TCO, а не просто оптимизацию собственных вызовов (что гораздо проще, чем это не так важно), (c) вы надеетесь, что реализация Common Lisp, которая делает TCO могут сделать это, не повредив параметры отладки (опять же, поскольку это считается оптимизацией в Common Lisp, а затем включив эту ручку, компилятор также может сказать: "Меня не волнует отладка" ).

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

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

Ответ 2

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

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

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

Ответ 3

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

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

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

Оптимизация звонков в Common Lisp

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

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

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

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

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

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

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

Для более продвинутых пользователей существует старая реализация Scheme (называемая 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

Определите имена схем для некоторых функций. Общий 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))

Общий 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

Ответ 4

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

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

Ответ 5

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

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

Ответ 6

Я бы пошел с более практичным диалектом вроде Clojure, Clojure работает на JVM и может потреблять все библиотеки Java, что является огромным преимуществом. Кроме того, Clojure является современным Lisp и охватывает приятные понятия. У него растущее и приятное сообщество. Если вы хотите попробовать Clojure, я предлагаю вам Clojurecademy, который является интерактивной платформой курсов, основанной на Clojure, которую я создал для новички.