A Brief Introduction to Common Lisp

The lambda symbol is associated with the Lisp family of programming languages, referring to Alonzo Church’s Lambda Calculus.

Throughout my career, I’ve enjoyed learning new programming languages.  I worked initially as a hardware engineer, so it was more of a hobby than a professional need.  Still, it served me well, as programming and scripting became an important part of hardware development, eventually leading to my transition into electronic design automation (EDA).

Fortran, PL/I, C, icon, dylan, C++, Java, TCL, perl, python, ruby, Haskell, scala, go, rust, julia, R, and many others have had their day, and part of the fun is seeing software development from the perspective of each language and its community.  

The Lisp family of languages is one which I have returned to multiple times.  It is one of the oldest languages, developed by John McCarthy at MIT in the mid to late 1950s.  This paper from 1960 introduces the language: “Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I”. The name Lisp stands for List Processor and it was implemented to support experiments in Artificial Intelligence (AI), initially for a program called “Advice Taker”. Lisp was the dominant language for AI research until the 1990s.   Many variants of the language evolved until a well documented standard, Common Lisp,  emerged in 1984, and was updated as an ANSI standard in 1994.  The Scheme branch of the family tree was defined in 1975 and continues to have a following, especially as a research and teaching vehicle.  The excellent introductory CS text, “Structure and Interpretation of Computer Programs”, is based on Scheme.  Clojure is a modern Lisp which executes on the Java Virtual Machine, featuring functional programming in multi-threaded environments.

I first encountered Lisp as a new grad working as a microcoder and logic designer at minicomputer manufacturer Data General Corporation (DG) in Massachusetts.  I and several of my fellow new grads had read Douglas Hofstadter’s excellent “Gӧdel, Escher, Bach: An Eternal Golden Braid” (GEB), and were excited about artificial intelligence.  It was the era of what is now known as GOFAI (Good Old Fashioned AI).  GOFAI was mostly implemented in Lisp and covered a variety of topics (search, planning, vision, theorem proving…) although much of commercial focus was on expert systems.  These essentially used the knowledge of human experts to build rule-based decision trees.  There was some success in narrow domains (e.g. mycin, macsyma), but it was ultimately too limited and inflexible to deliver on the extravagant claims which had been made about AI, leading to one of the AI Winters.  I’ve barely scratched the surface of Lisp and AI history.   It’s a topic I’d like to return to in future posts.

One of my colleagues implemented a version of MacLISP (the main MIT variant at the time) as a side project and several of us used it to do our homework in a graduate course in AI we had enrolled in at Boston University.  My colleague ultimately landed a job at Symbolics, the most successful company building specialized hardware for Lisp software development.  For me, it was the start of a lifetime of tinkering with or making professional use of Lisp.  Lisp was often used as an embedded scripting language and is still an important embedded language.  In my field of EDA, Scheme was embedded in the Milkyway design database used by the Avanti placement and routing tools, although it was eventually phased out after Avanti was acquired by Synopsys.  The Lisp variant Skill continues to be used as the embedded language in custom silicon layout tools at Cadence Design Systems.  In mechanical CAD, AutoLISP is used in industry leader AutoCAD.

Common Lisp is my language of choice for personal projects, and I plan to use it in this blog as a concise way to illustrate algorithmic ideas.  What’s great about Common Lisp?  It’s a very stable, batteries-included standard with good compilers and tools.  The interactive REPL (Read Eval Print Loop) based development environment is a very comfortable way to implement in a bottoms up manner with trusted components.  On-the-fly, per function, tunable compilation to binary provides good performance.  Memory is managed automatically through garbage collection. There’s a good debugger.  It supports a wide variety of programming paradigms (functional, imperative, object oriented), and is very extensible.  Lisp is homoiconic, which means that programs and data have the same form.  Most hard-core Lisp enthusiasts say that this is the most important feature.  The full power of the language can be used to implement domain specific languages (DSLs) which match the problem domain precisely.  I’ll explore the creation of a DSL in depth in my next post.

While Lisp is a niche language, it has gone through something of a resurgence in recent years, perhaps driven by the popularity of Clojure. It has always had a dedicated following because the ideas behind it are powerful and sound. A wide variety of, dare I say nearly all, programming languages have borrowed ideas from Lisp (garbage collection, anonymous functions (Lambdas), functional programming, REPL…I’m looking at you Python). To that point, I leave you with Greenspun’s Tenth Rule, “Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp.”

There are lots of good books and tutorials on Common Lisp and other variants.

This is a good place to get started:  https://common-lisp.net/

I use the Common Lisp implementation SBCL, the GNU Emacs editor, the SLIME runtime environment, ASDF for project setup, and Quicklisp for libraries and package management.

It was straightforward to set up on both MacOS and Linux.

Practical Common Lisp is one of several good introductory books.

The Common Lisp Cookbook rich collection of examples and is available online.  I bought a paper copy.

I’ve found this to be a helpful tutorial on setting up a project in quicklisp/quickproject.