Jonathan Lam

EE/CS @ The Cooper Union


Blog

SICP notes: Haskell and CL are too powerful for SICP

On 7/7/2021, 7:23:29 PM

Return to blog


This is somewhat of a brain dump because I don't know that much about Haskell or Common Lisp (CL). But I've spent some time this summer learning about them (reading Practical Common Lisp and A Gentle Introduction to Haskell) in my free time, which have prompted me to write this post.

I've already written that Scheme is great for SICP because it is very minimal and has great metaprogramming abilities (e.g., homoiconicity). These, combined, allow us to experiment with different language constructs without feeling hemmed in or otherwise influenced by existing structures in the language. We also get stuck in a mostly-functional language, which, as discussed in the previous post, is instructive and has a number of nice mathematical and practical properties associated with it.

Compare this with Java, a common language of choice for beginners. Java typing, even with its minimal ability for metaprogramming with reflection, feels extremely rigid. There is an enormous library, both the standard library and third-party packages, which can not noly make you feel overwhelmed but can make you dependent on existing libraries and unable to write good code on your own. Functional programming is terrible (the pre-lambda syntax was awful, and lambdas still don't really feel like first-class types). Multiple inheritance of interfaces is allowed but multiple subclassing is not. There are both abstract classes and interfaces with default methods. And the verbosity.

A nightmare for beginners.

Compare this with Python, which has overtaken Java in popularity as a learner's language for some time now. We have a partially functional language, but as far as I've seen, most beginners (especially engineers and data scientists) use it in a mostly- or all-imperative manner. There are too many "magic" methods and the syntax is not homoiconic, but it's much better than Java. There is a class system, but typing is dynamic and loose, and the multiple inheritance situation is simpler.

The situation is a lot better than Java, but still not as good as Lisp. Metaprogramming exists but limited to the existing class system (whereas in Lisp macros can transform any source code), the syntax is more complex (e.g., spacing). The worst part is still about functional programming -- the students I see using Python are often very inclined to write sequential code with mutations (a pitfall of imperative programming, because then it forces you to be careful about ordering statements) and spaghetti code galore like run-on sentences. (FP, on the other hand, tends to build up functions via compositions of lesser functions, and thus tends to be more modular.)

I think, in order to learn SICP in the way Abelson and Sussman intended, in order to learn how to "structure" and "interpret" computer programs in a meaningful way, we need some degree of enforcing functional programming. Even though SICP is not a book on FP, FP lends itself to good programming principles.

Which brings us to the two languages mentioned in the title. Common Lisp, which is considered more practical than the academic Scheme; and Haskell, a purely-functional-yet-practical language. I've seen a number of questions on forums like Stack Exchange asking whether or not these two languages would be good substitutions for Scheme when reading SICP. Feel free to read them. This is my take after having just a little taste of CL and Haskell, and overlaps with those many posts.

tl;dr: Haskell and CL are both too "practical" for SICP, and have the same pitfalls as other popular languages like Python or Java. Scheme and SICP were basically made for one another; but that doesn't mean that the ideas don't carry over into other languages.


Haskell

Being purely functional has its benefits and drawbacks. On the one hand, we have the predictability and referential transparency offered by FP. On the other hand, we need to introduce new constructs (and thus additional complexity) to deal with possibly non-pure expressions. Expressions with possible side-effects are constructed as a special type called a monad, and expressions that use monads are themselves marked as monads1. This means that any impure functions are deliberately marked as such, and in a very generic way that encompasses I/O, exceptions, and more. While some may find it beautiful, others with a weaker mathematical background may find it confusing.

Besides monads, which are specific to functional programming, Haskell generally has more features in the language than Lisp. There is a strict type system and inheritance. There are infix operators as well as prefix ones. With sometimes-optional parentheses, you can avoid the complexity of Lisp but now have to pay attention to operator precedence and indentation. Each new feature comes with its own syntax, and Haskell syntax is far from what a C programmer might find intuitive.

Thus, the grammar is not at all similar to Lisp, which is extremely detrimental in SICP when writing an interpreter, or when talking about metaprogramming capabilities. Regular Haskell doesn't even support macros -- you need an extension (Template Haskell) to support them.

Moreover, in Haskell there are many "hidden behaviors" that may confuse the casual beginner. Laziness is already built-in by default, while strictness is optional; the opposite is true of Lisp, and Lisp's method is probably more intuitive. We also have pattern-matching for types, whose implementation is probably not apparent.

Haskell is no doubt a very powerful functional language, but it throws away the minimalism that is required for SICP.


CL

Common Lisp is much more similar to Scheme, and it's probably a much better candidate for following along with SICP than Haskell. However, it is still less desirable for some minor reasons. That being said, I've seen some posts online that say CL is just fine for SICP, so I wouldn't say this is a definitive no.

One of the commonly cited reasons is that CL is a Lisp-2, while Scheme is a Lisp-1. One of the biggest arguments that SICP makes in the first two chapters is the equivalence of procedures and data. I've already talked about this many times in previous posts: it is useful to be able to treat procedures and variables in a uniform way. This is reflected in the code: we define variables and procedures uniformly with define or let. This is not the case in Common Lisp (and other Lisp-2's), in which functions and variables are in separate namespaces for efficiency reasons. Common Lisp code is instead littered with defun and defvar, and invoking a function stored in a variable uses different syntax than invoking something declared to be a function. While this is mostly a cosmetic concern, it takes away from the message that SICP tries to present and requires you to think of variables and functions separately. Moreover, it probably2 makes writing an interpreter more difficult.

Secondly, Common Lisp already has implemented some of the features that we build up from scratch in SICP, such as a type system (like the CLOS), multiple inheritance (which exists in the CLOS, and is configurable), or laziness (the CLazy extension). Common Lisp has a good variety of packages and has wider support in industry.

I'm sure there are other reasons why CL might be more confusing than Scheme, but I'm not advanced enough with CL to know.


In summary, what we have are two godly languages: highly functional (with builtin laziness), performant, homoiconic (CL) or at least allowing metaprogramming (Template Haskell), languages with robust but extensible type systems and great library support. They embody a lot of the language constructs that SICP introduces, but the book is about the process of getting to this point. As before with Python and Java, having builtin support for the features may be counterproductive to the learning process because we can't build these up from scratch.


Footnotes

1. This may not be very precise wording, as I've just been introduced to the idea of monads. But I believe this to be the general idea.

2. "Probably" because I haven't read Chapter 4 yet, and because I'm honestly not sure if it makes writing an interpreter simpler or more difficult with separrate namespaces.


© Copyright 2021 Jonathan Lam