¿Puedo usar Common Lisp para SICP o Scheme es la única opción?

common-lisp

Question

Además, incluso si puedo usar Common Lisp, ¿debería? ¿Scheme es mejor?

Answer 1

¿Ya sabes algo de Common Lisp? Supongo que eso es lo que quieres decir con ''Lisp''. En ese caso, es posible que desee usarlo en lugar de Scheme. Si usted no sabe tampoco, y está trabajando a través del SICP únicamente para la experiencia de aprendizaje, entonces probablemente esté mejor con Scheme. Tiene mucho mejor soporte para nuevos estudiantes, y no tendrá que traducir de Scheme a Common Lisp.

Hay diferencias; específicamente, el estilo altamente funcional de SICP es más complejo en Common Lisp porque tienes que citar funciones al pasarlas y usar funcall para llamar a una función vinculada a una variable.

Sin embargo, si desea usar Common Lisp, puede intentar usar las traducciones de Eli Bendersky Common Lisp del código SICP bajo la etiqueta SICP .

Answer 2

Me gustaría ir con un dialecto más práctico como Clojure, Clojure se ejecuta en JVM y puede consumir todas las bibliotecas de Java, lo que es una gran ventaja. También Clojure es un Lisp moderno y abarca conceptos agradables. Tiene una comunidad creciente y agradable. Si quieres probar Clojure, te sugiero Clojurecademy, que es una plataforma interactiva de cursos basada en Clojure que he creado para los recién llegados.

Answer 3

Son similares pero no son lo mismo.

Creo que si vas con Scheme sería más fácil.

Answer 4

Tiene varias respuestas aquí, pero ninguna es realmente exhaustiva (y no estoy hablando de tener suficientes detalles o ser lo suficientemente largos). En primer lugar, la conclusión: no debe usar Common Lisp si desea tener una buena experiencia con SICP.

Si no sabes mucho Common Lisp, entonces tómalo como eso. (Obviamente puedes ignorar este consejo como cualquier otra cosa, algunas personas solo aprenden de la manera difícil).

Si ya conoces Common Lisp, puedes llevarlo a cabo, pero con un esfuerzo considerable y un daño considerable a tu experiencia de aprendizaje en general. Hay algunos problemas fundamentales que separan Common Lisp y Scheme, que hacen que tratar de usar el anterior con SICP sea una idea bastante mala. De hecho, si tiene el nivel de conocimiento para hacerlo funcionar, entonces es probable que esté por encima del nivel de SICP de todos modos. No digo que no sea posible; por supuesto, es posible implementar todo el libro en Common Lisp (por ejemplo, ver las páginas de Bendersky) del mismo modo que lo puedes hacer en C, Perl o lo que sea. Simplemente va a ser más difícil con idiomas que están más allá de Scheme. (Por ejemplo, ML es más fácil de usar que Common Lisp, incluso cuando su sintaxis es muy diferente).

Estos son algunos de estos temas principales, en orden creciente de importancia. (No estoy diciendo que esta lista sea exhaustiva de ninguna manera, estoy seguro de que hay un montón de problemas adicionales que estoy omitiendo aquí).

1. NIL y cuestiones relacionadas, y diferentes nombres.

2. Alcance dinámico.

3. Optimización de llamadas de cola

4. Separar el espacio de nombres para funciones y valores.

Me extenderé ahora sobre cada uno de estos puntos:

El primer punto es el más técnico. En Common Lisp, NIL se usa tanto como la lista vacía como como el valor falso. En sí mismo, este no es un gran problema, y ​​de hecho, la primera edición del SICP tenía una suposición similar, donde la lista vacía y la falsa tenían el mismo valor. Sin embargo, el NIL Common Lisp sigue siendo diferente: también es un símbolo. Entonces, en Scheme tienes una clara separación: algo es una lista, o uno de los tipos primitivos de valores, pero en Common Lisp, NIL no solo es falso y la lista vacía: también es un símbolo. Además de esto, obtienes una serie de comportamientos ligeramente diferentes: por ejemplo, en Common Lisp, la cabeza y la cola (el car y el cdr ) de la lista vacía son en sí mismos la lista vacía, mientras que en Scheme obtendrás un error de tiempo de ejecución si intenta eso. Para colmo, tiene diferentes nombres y convenciones de nombres, por ejemplo: predicados en Common Lisp terminan por convención con P (por ejemplo, listp ) mientras que los predicados en Scheme terminan en un signo de interrogación (por ejemplo, list? ); los mutadores en Common Lisp no tienen una convención específica (algunos tienen un prefijo N ), mientras que en Scheme ¡casi siempre tienen un sufijo ! . Además, la asignación simple en Common Lisp generalmente se setf y puede operar también en combinaciones (por ej., (setf (car foo) 1) ), ¡mientras que en Scheme se set! y limitado a establecer solo variables enlazadas. (Tenga en cuenta que Common Lisp también tiene la versión limitada, se llama setq . Casi nadie lo usa).

El segundo punto es mucho más profundo, y posiblemente uno que conducirá a un comportamiento completamente incomprensible de su código. El hecho es que en Common Lisp, los argumentos de función tienen un alcance léxico, pero las variables que se declaran con defvar tienen un alcance dinámico . Existe una amplia gama de soluciones que se basan en enlaces de ámbito léxico, y en Common Lisp simplemente no funcionan. Por supuesto, el hecho de que Common Lisp tenga un alcance léxico significa que puede evitar esto siendo muy cuidadoso con las nuevas vinculaciones, y posiblemente utilizando macros para evitar el alcance dinámico por defecto, pero nuevamente, esto requiere un conocimiento mucho más extenso que un novato típico tiene. Las cosas empeoran aún más: si declaras un nombre específico con un defvar , ese nombre se vinculará dinámicamente incluso si son argumentos para las funciones. Esto puede llevar a algunos errores extremadamente difíciles de rastrear que se manifiestan de una manera extremadamente confusa (básicamente obtienes el valor incorrecto, y no tendrás idea de por qué sucede eso). Los Common Lispers experimentados lo saben (especialmente aquellos que han sido quemados), y siempre seguirán la convención de usar estrellas con nombres de ámbito dinámico (p. Ej., *foo* ). (Y, por cierto, en la jerga de Common Lisp, estas variables de ámbito dinámico se llaman simplemente "variables especiales", que es otra fuente de confusión para los novatos).

El tercer punto también se discutió en algunos de los comentarios anteriores. De hecho, Rainer tuvo un buen resumen de las diferentes opciones que tiene, pero no explicó qué tan difícil puede hacer las cosas. Lo que pasa es que uno de los conceptos fundamentales de Scheme es la adecuada optimización de llamadas de cola (TCO). Es lo suficientemente importante que es una función de idioma en lugar de simplemente una optimización. Un bucle típico en Scheme se expresa como una función de llamada de cola (por ejemplo, (define (loop) (loop)) ) y se requieren implementaciones de Scheme adecuadas para implementar TCO lo que garantizará que esto sea, en realidad, un bucle infinito en lugar de que correr por un tiempo corto hasta que explotes el espacio de la pila. Esta es toda la esencia de la primera solución de Rainer, y la razón por la que lo etiquetó como "MALO". Su tercera opción, la reescritura de bucles funcionales (expresados ​​como funciones recursivas) como bucles Common Lisp ( dotimes , dolist y el infame loop ) puede funcionar para algunos casos simples, pero a un costo muy alto: el hecho de que Scheme es un lenguaje hacer un TCO adecuado no solo es fundamental para el idioma; también es uno de los temas principales del libro, por lo que habrá perdido ese punto por completo. Además, hay algunos casos en los que no se puede traducir el código Scheme en una construcción de bucle Common Lisp; por ejemplo, a medida que avanzas en el libro, podrás implementar un intérprete de metacirculación que es una implementación de un lenguaje de mini-Scheme. Se necesita un cierto clic para darse cuenta de que este metaevaluador implementa un lenguaje que a su vez está haciendo TCO si el lenguaje en el que implementa este evaluador está haciendo TCO. (Tenga en cuenta que estoy hablando de los intérpretes "simples"; más adelante en el libro usted implementa este evaluador como algo cercano a una máquina de registro, donde explícitamente hace que haga TCO). La conclusión de todo esto, es que este evaluador, cuando se implementa en Common Lisp, dará como resultado un lenguaje que no está haciendo TCO. Las personas que están familiarizadas con todo esto no deberían sorprenderse: después de todo, la "circularidad" del evaluador significa que está implementando un lenguaje con semántica que está muy cerca del idioma del sistema principal, por lo que en este caso "hereda". "la semántica Common Lisp en lugar de la semántica Scheme TCO. Sin embargo, esto significa que su mini-evaluador ahora está lisiado: no tiene TCO, ¡así que no tiene manera de hacer bucles! Para obtener bucles, deberá implementar nuevas construcciones en su intérprete, que generalmente usará las construcciones de iteración en Common Lisp. Pero ahora se está alejando de lo que contiene el libro, y está invirtiendo un esfuerzo considerable para implementar aproximadamente las ideas del SICP en los diferentes idiomas. Tenga en cuenta también que todo esto está relacionado con el punto anterior que planteé: si sigue el libro, entonces el lenguaje que implemente tendrá un alcance léxico, alejándolo del lenguaje de host Common Lisp. Entonces, en general, pierde por completo la propiedad "circular" en lo que el libro llama "evaluador meta circular". (De nuevo, esto es algo que puede no molestarle, pero dañará la experiencia de aprendizaje en general.) En general, muy pocos idiomas se acercan a Scheme al poder implementar la semántica del lenguaje dentro del idioma como un no- un evaluador trivial (ej., no usando eval ) tan fácilmente. De hecho, si vas con un Common Lisp, entonces, en mi opinión, la segunda sugerencia de Rainer (utilizar una implementación de Common Lisp que admita TCO) es la mejor manera de hacerlo. Sin embargo, en Common Lisp esto es fundamentalmente una optimización del compilador: por lo que es probable que necesite (a) conocer las perillas en la implementación que necesita activar para que ocurra el TCO, (b) deberá asegurarse de que el Común La implementación de Lisp realmente está haciendo un TCO apropiado, y no solo la optimización de las llamadas (que es el caso mucho más simple que no es tan importante), (c) esperaría que la implementación de Common Lisp que hace TCO pueda hacerlo sin dañar la depuración opciones (de nuevo, dado que esto se considera una optimización en Common Lisp, al encenderlo, el compilador también podría tomar la siguiente instrucción diciendo "No me importa mucho la depuración").

Finalmente, mi último punto no es demasiado difícil de superar, pero conceptualmente es el más importante. En Scheme, usted tiene una regla uniforme: los identificadores tienen un valor, que se determina léxicamente, y eso es todo . Es un lenguaje muy simple. En Common Lisp, además del bagaje histórico de usar el alcance dinámico algunas veces con el alcance léxico, tiene símbolos que tienen dos valores diferentes: el valor de la función que se utiliza cada vez que aparece una variable en el encabezado de una expresión, y hay un valor diferente que se usa de otra manera. Por ejemplo, en (foo foo) , cada una de las dos instancias de foo se interpreta de forma diferente: la primera es el valor de función de foo y la segunda es su valor de variable. Nuevamente, esto no es difícil de superar: hay una serie de construcciones que debe conocer para manejar todo esto. Por ejemplo, en lugar de escribir (lambda (x) (xx)) necesita escribir (lambda (x) (funcall xx)) , lo que hace que la función que se está llamando aparezca en una posición variable, por lo tanto, el mismo valor será utilizado allí; otro ejemplo es (map car something) que tendrá que traducir (map #''car something) (o más exactamente, tendrá que utilizar mapcar que es el equivalente de Common Lisp de la función del car ); otra cosa que necesitarás saber es que let vincular la ranura de valor del nombre, y las labels enlazan la ranura de función (y tiene una sintaxis muy diferente, como defun y defvar ). Pero el resultado conceptual de todo esto es que Common Lispers tiende a usar código de orden superior mucho menos que Schemers, y eso va desde los modismos que son comunes en cada idioma hasta lo que las implementaciones harán con él. (Por ejemplo, muchos compiladores de Common Lisp nunca optimizarán esta llamada: (funcall foo bar) , mientras que los compiladores de Scheme optimizarán (foo bar) como cualquier expresión de llamada de función, porque no hay otra manera de llamar funciones.

Finalmente, notaré que gran parte de lo anterior es un material muy bueno para flamear: arroje cualquiera de estos problemas en un foro público de Lisp o Scheme (en particular, comp.lang.lisp y comp.lang.scheme ), y lo hará Es probable que veamos un largo hilo donde las personas explican por qué su elección es mucho mejor que la otra, o por qué alguna "característica llamada" es en realidad una decisión idiota hecha por diseñadores de idiomas que estaban claramente muy borrachos en ese momento, etc., etc. la cuestión es que estas son solo diferencias entre los dos idiomas, y eventualmente la gente puede hacer su trabajo en cualquiera de los dos. Simplemente sucede que si el trabajo es "hacer SICP" entonces Scheme será mucho más fácil considerando cómo aborda cada uno de estos problemas desde la perspectiva del Esquema. Si quieres aprender Common Lisp, ir con un libro de texto de Common Lisp te dejará mucho menos frustrado.

Answer 5

Editar: El comentario de Nathan Sanders es correcto. Claramente ha pasado un tiempo desde la última vez que leí el libro, pero acabo de verificarlo y no usa call/cc directamente. He votado a favor la respuesta de Nathan.

Lo que sea que use necesita implementar implementaciones, que SICP usa mucho. Ni siquiera todos los intérpretes de Scheme los implementan, y no conozco ningún Common Lisp que lo haga.

Answer 6

Usar SICP con Common Lisp es posible y divertido

Puede usar Common Lisp para aprender con SICP sin muchos problemas. El subconjunto de Scheme que se usa en el libro no es muy sofisticado. SICP no usa macros y no usa continuaciones. Hay DELAY y FORCE, que se pueden escribir en Common Lisp en unas pocas líneas.

También para un principiante que utiliza (function foo) y (funcall foo 1 2 3) es realmente mejor (¡En mi humilde opinión!), Porque el código se vuelve más claro al aprender las partes de programación funcional. Puede ver dónde se llaman / pasan las variables y las funciones lambda.

Optimización de llamadas de cola en Common Lisp

Solo hay una gran área donde el uso de Common Lisp tiene un inconveniente: la optimización de llamadas de cola (TCO). Common Lisp no admite TCO en su estándar (debido a una interacción poco clara con el resto del lenguaje, no todas las arquitecturas informáticas lo soportan directamente (piense en JVM), no todos los compiladores lo soportan (algunas máquinas Lisp), realiza alguna depuración / rastreo / pisando más fuerte, ...).

Hay tres formas de vivir con eso:

1. Espero que la pila no se apague. MALO.
2. Use una implementación de Common Lisp que admita TCO. Hay algunos. Vea abajo.
3. Reescriba los bucles funcionales (y construcciones similares) en bucles (y construcciones similares) utilizando DOTIMES, DO, LOOP, ...

Personalmente, recomendaría 2 o 3.

Common Lisp tiene compiladores excelentes y fáciles de usar con soporte TCO (SBCL, LispWorks, Allegro CL, Clozure CL, ...) y como entorno de desarrollo utiliza los integrados o GNU Emacs / SLIME.

Para usar con SICP, recomendaría SBCL , ya que compila siempre de manera predeterminada, tiene soporte de TCO por defecto y el compilador detecta muchos problemas de codificación (variables no declaradas, listas de argumentos incorrectos, un montón de errores de tipo, ...). Esto ayuda mucho durante el aprendizaje. Por lo general, asegúrese de que el código esté compilado, ya que los intérpretes de Common Lisp generalmente no admiten el TCO.

A veces también puede ser útil escribir una o dos macros y proporcionar algunos nombres de funciones de Scheme para que el código se parezca un poco más a Scheme. Por ejemplo, podría tener una macro DEFINE en Common Lisp.

Para los usuarios más avanzados, existe una antigua implementación de Scheme (llamada Pseudo Scheme), que debería ejecutar la mayor parte del código en SICP.

Mi recomendación: si quieres hacer un esfuerzo adicional y usar Common Lisp, hazlo.

Para facilitar la comprensión de los cambios necesarios, agregué algunos ejemplos: recuerde que necesita un compilador de Common Lisp compatible con la optimización de la cola de llamadas :

Ejemplo

Veamos este código simple de 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)))

Podemos usarlo directamente en Common Lisp con una macro DEFINE :

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

Ahora debería usar SBCL, CCL, Allegro CL o LispWorks. Estos compiladores admiten TCO de forma predeterminada.

Usemos 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....

Otro ejemplo: diferenciación simbólica

El SICP tiene un ejemplo de esquema para la diferenciación:

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

Hacer que este código se ejecute en Common Lisp es fácil:

• algunas funciones tienen diferentes nombres, number? es numberp en CL
• CL:COND usa T lugar de else
• CL:ERROR usa cadenas de formato CL

Definamos los nombres de Esquema para algunas funciones. Código de Lisp común:

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

Nuestra macro define desde arriba:

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

El código 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))))

Probémoslo en LispWorks:

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

Ejemplo de secuencias del SICP en Common Lisp

Vea el código del libro en el capítulo 3.5 en SICP. Usamos las adiciones a CL desde arriba.

El SICP menciona el delay , the-empty-stream y cons-stream , pero no lo implementa. Proporcionamos aquí una implementación en 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"))

Ahora viene el código portátil del libro:

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

Ahora Common Lisp difiere en stream-for-each :

• necesitamos usar cl:progn lugar de begin
• los parámetros de función deben llamarse con cl:funcall

Aquí hay una versión:

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

También necesitamos pasar funciones usando cl:function :

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

Pero luego el ejemplo funciona:

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