Can I use Common Lisp for SICP or is there just a schema?

Also, even if I can use Common Lisp, should I? Is the circuit better?

+47
lisp scheme common-lisp sicp
Jul 21 '09 at 13:34
source share
6 answers

You have a few answers here, but none of them are exhaustive (and I'm not saying that you have enough details or long enough). First of all, the bottom line: you should not use Common Lisp if you want to have good experience with SICP.

If you do not know much in common with Lisp, then just take it like this. (Obviously, you can neglect this advice, like everything else, some people only learn the hard way.)

If you already know Common Lisp, you can remove it, but with considerable effort and with significant damage to your overall learning experience. There are some fundamental problems that Common Lisp and Scheme share, which try to use the first with SICP rather bad idea. In fact, if you have a level of knowledge to make it work, then you are likely to exceed the SICP level. I'm not saying that this is impossible - of course, you can implement the entire book in Common Lisp (for example, see Bendersky Pages) just as you can do it in C or Perl or something else. This will be much more complicated with languages ​​that are even more different from Schema. (For example, ML will probably be easier to use than Common Lisp, even if its syntax is very different.)

Here are some of these key issues, in increasing order of importance. (I'm not saying this list is exhaustive anyway, I'm sure there are a whole bunch of additional issues that I omit here.)

  • NIL and its related problems, as well as different names.

  • Dynamic area.

  • Call optimization.

  • Separate the namespace for functions and values.

Now I will deal with each of these points:

The first point is the most technical. In Common Lisp, NIL used both as an empty list and as a false value. This in itself is not a big problem, and in fact the first edition of SICP had a similar assumption: where the empty list and false values ​​were the same. However, the Common Lisp NIL is still different: it is also a symbol. So, in the Scheme you have a clear separation: something is either a list or one of the primitive value types, but in Common Lisp, NIL not only false and an empty list: it is also a symbol.In addition to this, you get several different actions - for example, in Common Lisp the head and tail ( car and cdr ) of an empty list are themselves an empty list, and if you try this, you will get a runtime error. To top it off, you have different names and naming conventions, for example - predicates in Common Lisp terminate by agreement with P (for example, listp ), while the predicates at the end of the Schema in a question mark (for example, list? ); mutators in Common Lisp do not have a special convention (some have the N prefix), while in Schema they almost always have a suffix ! . In addition, the usual assignment in Common Lisp is usually setf , and it can work on combinations (for example, (setf (car foo) 1) ), but on the diagram it can be set! and limited only by setting related variables. (Note that Common Lisp also has a limited version, it is called setq . Almost no one uses it, though.)

The second point is much deeper, and possibly one that will lead to completely incomprehensible behavior of your code. The point is that in Common Lisp function arguments are lexically limited, but variables declared with defvar are dynamically limited. There are a number of solutions that rely on lexical bindings - and they just won't work in Common Lisp. Of course, the fact that Common Lisp has a lexical scope means that you can get around this by being very careful about new bindings and possibly using macros to get around the default dynamic scope - but again, this requires much more vast than an ordinary beginner. Things get even worse: if you declare a specific name with defvar , then that name will be bound dynamically, even if they are arguments to functions. This can lead to extremely difficult tracking of errors that appear in an extremely confusing way (you basically get the wrong value and you don’t understand why this is happening). Experienced general lispers know this (especially those that were burned by him), and will always follow the agreement to use stars around names with a dynamic region (for example, *foo* ). (And by the way, in Common Lisp jargon, these dynamically copied variables are simply called “special variables,” which is another source of confusion for beginners.)

The third paragraph has also been discussed in some previous comments. In fact, Rainer had a pretty good summary of the various options you have, but he did not explain how difficult it is. The fact is that proper tail call optimization (TCO) is one of the basic concepts of the Scheme. It is important enough that this be a language function, not just optimization. A typical loop in a Scheme is expressed as a function of calling the tail (for example, (define (loop) (loop)) ), and the implementation of TCO requires the correct implementation of the Scheme, which ensures that it is, in fact, an infinite loop, and not a short run until you explode the stack space. This is the essence of Rainer's first decision, and the reason he called it “BAD.” Its third option is to rewrite functional loops (expressed as recursive functions) as generic Lisp loops ( dotimes , dolist and the infamous loop ) can work in a few simple cases, but at a very high cost: the fact that Scheme is a language that makes proper TCO is not only fundamental to the language - it is also one of the main topics in the book, therefore, in this way you will completely lose this point. In addition, there are some cases where you simply cannot translate the code of the circuit into the general construction of the Lisp loop - for example, as you work your way through the book, you can implement the meta-circular interpreter, which is the implementation of the mini-circuit language . It takes a certain click to understand that this meta-analyst implements a language that runs TCO itself, if the language that you implement this evaluator runs TCO itself. (Please note that I'm talking about “simple” interpreters - later in the book you will implement this evaluator as something close to the registration machine, where you explicitly do this using TCO). The essence of all this is that this evaluator - when implemented in Common Lisp - will lead to a language that itself does not execute TCO. People familiar with all this should not be surprised: after all, the "roundness" of the evaluator means that you implement a language with semantics that is very close to the host language - therefore, in this case, you "inherit" the General semantics of Lisp, and not the semantics of the TCO scheme. However, this means that your mini-evaluator is now crippled: it does not have TCO, so it is not able to make loops! To get loops, you will need to implement new constructors in your interpreter that will usually use iteration constructs in Common Lisp. But now you care those from what is in the book, and you put considerable effort into roughly implementing ideas in SICP in different languages. Please also note that all this is connected with the previous point that I raised: if you follow the book, then the language, which you implement will be lexically encompassed, diverting it from the main Lisp language, thus completely losing your “circular” ownership in what the book calls a “meta-circular appraiser.” (Again, this is something that may not bother you, but it will hurt the overall learning experience.) In general, very few languages ​​approach Scheme in the ability to implement the semantics of the language within the language as a non-trivial (for example, without using eval ) evaluator, which is easy. In fact, if you go with shared Lisp, then, in my opinion, Rainer's second suggestion - using the implementation of Common Lisp that supports TCO is the best way. However, in Common Lisp, this is mainly a compiler optimization: therefore, you most likely need to (a) be aware of the handles in the implementation that you need to enable to make TCO, (b) you will need to make sure that the Common Lisp implementation actually does proper TCO, not just optimizing your own calls (which is much easier than not so important), (c) you hope that the Common Lisp implementation that does TCO can do this without damaging the debugging options (again, since this is considered optimization in Common Lisp, and then turning on this knob, the compiler like this e can say, "I do not care Debugging").

Finally, my last moment is not too difficult to overcome, but it is conceptually the most important. In the Scheme you have a single rule: identifiers have a value that is defined lexically - and that it is. This is a very simple language. In Common Lisp, in addition to historical baggage, sometimes using a dynamic scope and sometimes using a lexical scope, you have characters that have two different meanings - there is a function value that is used whenever the variable appears at the head of the expression and exists another value that is used differently. For example, in (foo foo) each of the two instances of foo interpreted differently - the first is the value of the function foo , and the second is its variable value. Again, this is not difficult to overcome - there are a number of designs that you need to know in order to deal with all this. For example, instead of writing (lambda (x) (xx)) you need to write (lambda (x) (funcall xx)) , which makes the function that is called appear in a variable position, so the same value will be used there; another example is (map car something) , which you need to translate into (map #'car something) (or, more precisely, you will need to use mapcar , which is the general Lisp equivalent of the car function); another thing you need to know is that let binds the name value slot, and labels binds the function slot (and has a completely different syntax, like defun and defvar ). But the conceptual result of all this is that Common Lispers, as a rule, use a higher-order code much less than Schemers, and this completely depends on the idioms that are common to each language, on what implementations will do with it . (For example, many Common Lisp compilers will never optimize this call: (funcall foo bar) , while Scheme compilers will optimize (foo bar) like any function call expression, because there is no other way to call functions.)

Finally, I would like to point out that most of the material above is very good flamewar material: drop any of these issues into the public Lisp or Scheme forum (specifically comp.lang.lisp and comp.lang.scheme ) and you you will most likely see a long thread where people explain why their choice is much better than the other, or why some kind of “so-called feature” is actually an idiotic decision made by language designers, who at that time were clearly drunk, etc. But the fact is that these are only the differences between the two languages, and ultimately people can do their job in one. It just happens that if the task "does SICP", then the scheme will be much easier to consider how it affects each of these problems from the point of view of the scheme. If you want to learn Common Lisp, then go on to the general Lisp tutorial, you will be left much less upset.

+106
Jul 23 '09 at 1:47
source share

Do you already know some common Lisp? I guess this means "Lisp". In this case, you can use it instead of Scheme. If you also don’t know this, and you work through SICP exclusively for training, then you will probably be better off using Scheme. It has much better support for new students, and you don’t have to translate from Schema to general Lisp.

There are differences; in particular, SICP's highly functional style is simpler in Common Lisp because you must quote functions when passing them and use funcall to call the function associated with the variable.

However, if you want to use Common Lisp, you can try using Eli Bendersky Common Lisp translations of SICP code under the SICP tag.

+11
Jul 21 '09 at 13:49
source share

Using SICP with shared Lisp is fun and fun.

You can use Common Lisp to learn with SICP without much trouble. The subset of Scheme used in the book is not very complex. SICP does not use macros and does not use any continuations. There are DELAY and FORCE, which can be written in Common Lisp in several lines.

Also for a beginner, using (function foo) and (funcall foo 1 2 3) is actually better (IMHO!), Because the code becomes clearer when learning the parts of functional programming. You can see where variables and lambda functions are called / passed.

Call Optimization in Common Lisp

There is only one big area where using Common Lisp has a drawback: Tail Call Optimization (TCO). Generic Lisp does not support TCO in its standard (due to fuzzy interaction with the rest of the language, not all computer architectures support it directly (I think the JVM), not all compilers support it (some Lisp Machine), it does some debugging / tracing / stepping , ...).

There are three ways to live with this:

  • Hope the stack does not deflate. Bad.
  • Use a generic Lisp implementation that supports TCO. There are some. See below.
  • Rewrite function loops (and similar constructs) into loops (and similar constructs) using DOTIMES, DO, LOOP, ...

Personally, I would recommend 2 or 3.

Common Lisp has excellent and easy-to-use compilers with TCO support (SBCL, LispWorks, Allegro CL, Clozure CL, ...), and either the built-in or GNU Emacs / SLIME are used as the development environment.

For use with SICP, I would recommend SBCL , since it always compiles by default, has TCO support by default, and the compiler catches a lot of coding problems (undeclared variables, invalid argument lists, a bunch of type errors, ...). This helps a lot during training. As a rule, make sure that the code is compiled, since Common Lisp interpreters usually do not support TCO.

Sometimes it’s also useful to write one or two macros and provide some Scheme function names so that the code looks more like a circuit. For example, you might have a DEFINE macro in Common Lisp.

For more advanced users, there is an old Scheme implementation (called Pseudo Scheme) that should run most of the code in SICP.

My recommendation: if you want to go the extra mile and use Common Lisp, do it.

To make it easier to understand the necessary changes, I added some examples - remember that he needs a Common Lisp compiler with support for tail call optimization:

Example

Take a look at this simple code from 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))) 

We can use it directly in Common Lisp with the DEFINE macro:

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

You should now use SBCL, CCL, Allegro CL, or LispWorks. These compilers support TCO by default.

Let me use 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.... 

Another example: symbolic differentiation

SICP has an example circuit for differentiating:

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

Running this code in Common Lisp is easy:

  • some functions have different names, number? - numberp in CL
  • CL:COND uses T instead of else
  • CL:ERROR uses CL format strings

Define schema names for some functions. Generic Lisp code:

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

Our DEFINE macro above:

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

Generic Lisp code:

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

Try it at LispWorks:

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

Example flows from SICP to Common Lisp

See book code in chapter 3.5 in SICP. We use additions to the CL from above.

SICP mentions delay , the-empty-stream and cons-stream , but does not implement it. Here we give an implementation in Common Lisp:

 (defmacro delay (expression) `(lambda () ,expression)) (defmacro cons-stream (ab) `(cons ,a (delay ,b))) (define (force delayed-object) (funcall delayed-object)) (defparameter the-empty-stream (make-symbol "THE-EMPTY-STREAM")) 

Now comes the portable code from the book:

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

Now Common Lisp is different from stream-for-each :

  • we need to use cl:progn instead of begin
  • Function parameters must be called using cl:funcall

Here is the version:

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

We also need to pass functions using cl:function :

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

But then an example works:

 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 
+10
Jul 21 '09 at 14:37
source share

Edit: Nathan Sanders comment is correct. Obviously, some time has passed since the last time I read the book, but I just checked and did not use call/cc directly. I supported Nathan's answer.




No matter what you use, you must implement a sequel that SICP uses a lot. Not even all Schema interpreters implement them, and I don't know of a single Common Lisp that does.

+2
Jul 21 '09 at 13:41
source share

They are similar, but not the same.

I believe that if you go with the Scheme, it will be easier.

+1
Jul 21 '09 at 13:37
source share

I would go with a more practical dialect like Clojure, Clojure runs on the JVM and can consume all Java libraries, which is a huge advantage. In addition, Clojure is a modern Lisp and embraces nice concepts. He has a growing and enjoyable community. If you want to try Clojure, I offer you Clojurecademy , which is an interactive course platform based on Clojure that I created for beginners.

0
09 Oct '17 at 19:01
source share



All Articles