They Called It LISP for a Reason: List Processing (2005)
I&#x27;m seeing a lot of people sort of dismissing the usefulness of lists without really understanding why Lisp is important: aren&#x27;t vectors and hash maps better?  Isn&#x27;t CONS just malloc()?  Doesn&#x27;t Forth solve the problem that low-level languages like C are inflexible?<p>— ⁂ —<p>The first thing to understand is that <i>Lisp invented functional programming</i>.  (Seibel&#x27;s chapter mentions this, of course.)<p>The functional-programming approach is to define your procedures recursively rather than iteratively; this began in Lisp but is now central to a number of other languages, like Haskell, OCaml, and F#.  For certain fields, like symbolic algebra and compilers, this approach makes many difficult problems trivial.  Even outside those fields, pervasive immutability often has many benefits, eliminating large classes of bugs, greatly simplifying problems like undo and thread-safety, and dramatically reducing the runtime cost of garbage collection.  However, recursively defined linked data structures tend to use more space, and they&#x27;re not very cache-friendly, and sometimes those are more important considerations.<p>To define your procedures recursively, it&#x27;s very helpful to define your data types recursively.  Recursively-defined lists (for example, &quot;a list of Ts is either the empty list of Ts or a T followed by a list of Ts&quot;) support this recursive, immutable approach to programming.<p>Other kinds of recursive structures do, too; Haskell and ML dialects tend to use application-specific sum types at least as much as general-purpose lists, and I like that style better.  It has most of the same advantages and disadvantages.<p>STL-style vectors do not support a recursive style of programming.  They support an iterative, imperative approach to programming.  If you use that other approach to programming exclusively, you will not understand why anyone would want to primarily use linked lists.  And occasionally you will be confronted with problems that are very difficult for you to solve, problems which would have been trivial with a recursive approach, and you will not realize that you are doing a hundred times more work to solve them than you need to.  SICP is full of examples.<p>— ⁂ —<p>The second thing about Lisp is that it has <i>orthogonal serialization and deserialization</i>: PRINT and READ.  This mechanism is sometimes, though not always, adequate for debug logging, saving and loading application state, configuration files, and networking.  Modern Lisps like Clojure generally extend those to arbitrary data structures, not just lists and atoms, but it&#x27;s especially easy to implement if you only have lists and atoms; it&#x27;s about 30 lines of Forth, for example¹.  This is of course not unique to Lisp anymore; Java, Python, Tcl, Golang, and many other languages have ways to do it.<p>Orthogonal deserialization of lists is not really an optional extra, since you use it to parse Lisp programs, too.  And you need the serialization to print lists in the REPL, anyway.<p>— ⁂ —<p>The third thing about Lisp is that <i>it supports metaprogramming very well</i>.  This takes lots of forms; compile-time macros are a common one, and they give you enormous flexibility to extend Lisps into domain-specific languages, though they&#x27;re probably used even more often to hack around inadequately optimized compilers.  EVAL answers many requirements for runtime flexibility, though there are times when it is too powerful.<p>As with serialization and deserialization, these metaprogramming facilities mostly just fall out of the Lisp design; they require minimal or no extra code in a Lisp interpreter.<p>— ⁂ —<p>Historically speaking Lisp had a lot of other advantages: for a long time it was the only garbage-collected language, the only dynamically-typed language, the only language with EVAL, the only language with higher-order functions, and so on, and so for many years it was by far the best language for the things that you would do in JS, Python, Ruby, Lua, or OCaml today.  JS, Python, Ruby, Lua, and OCaml are better for some of those things, and for many purposes they adequately support the functional, recursive, immutable approach to programming that Lisp pioneered.<p>Still, it might be easier to learn it in Lisp.<p>— ⁂ —<p>Lisp is sort of a minimal core of functional programming.  In a decent low-level language like C or Forth, you can build a Lisp with an interactive functional programming environment with dynamic typing, orthogonal serialization and deserialization, an interactive interpreter, garbage collection, and extensive metaprogramming capabilities, in under 1000 lines of code, and the only data structure you need to do it is cons.<p>(It&#x27;s not quite as simple as you might think from reading the &quot;Maxwell&#x27;s Equations of Software&quot; in the Lisp 1.5 manual; those gloss over READ, PRINT, decimal conversion, arithmetic, symbol interning, the garbage collector, and user interaction, so you end up with significantly more code in a low-level language² where you have to implement those.  But it&#x27;s still days of work, not weeks.)<p>That doesn&#x27;t mean Lisp is the <i>only</i> way to do functional programming, or even the <i>best</i> one.  Quite apart from implementation questions, you might reasonably prefer the ML approach, with its strong static type checking; or the Haskell approach, which also features laziness; or the Clojure approach, which includes first-class persistent finite maps and integer-indexed &quot;vectors&quot;; or again the Clojure approach, where every operation supports ad-hoc polymorphism; or the Tcl approach, where everything is a string; or the Q approach, where your code defines term-rewriting rules rather than functions; or the Prolog approach, where you have not only list processing but lists that can contain uninstantiated logic variables; or the KANREN approach, which generalizes functional programming to full-on relational programming; or the Bicicleta approach, where you program directly in a side-effect-free ς-calculus, overriding methods instead of passing parameters; and many other approaches that haven&#x27;t been thought of yet.<p>But if you&#x27;re thinking of Forth as an alternative to Lisp, or STL vectors as an alternative to Lisp lists, and in general rather than in a particular case, you just haven&#x27;t understood the Lisp approach to problem solving at all.<p>And when you do, it&#x27;s going to be <i>awesome</i>.<p>______<p>¹ <a href="http:&#x2F;&#x2F;canonical.org&#x2F;~kragen&#x2F;sw&#x2F;dev3&#x2F;readprint.fs" rel="nofollow">http:&#x2F;&#x2F;canonical.org&#x2F;~kragen&#x2F;sw&#x2F;dev3&#x2F;readprint.fs</a><p>² <a href="https:&#x2F;&#x2F;www.mail-archive.com&#x2F;kragen-hacks@canonical.org&#x2F;msg00164.html" rel="nofollow">https:&#x2F;&#x2F;www.mail-archive.com&#x2F;kragen-hacks@canonical.org&#x2F;msg0...</a>