One of the best programming books (for any language) ever written IMO. Seibel has a knack for clear, readable but still technical prose that's all too rare unfortunately.
It’s a fine first book. I’d certainly recommend it.
I don’t recall if it has instructions on getting a dev env up and running, but if it does I imagine they’re out of date. Emacs with Sly or SLIME is what I’ve used, but I believe there are viable options for proper interactive development in vim and vs code among others.
If you just use a basic editor and paste code into a repl in a terminal you won’t be getting the experience most Lispers do.
I recommend the gentle introduction to Lisp book for the complete beginner.
The chapter on files in the Practical Common Lisp book wasn't complete enough for me to read a one line file of 800MB which is part of the Harvard Library Open Metadata archived set.
Practical Common Lisp is a fantastic read, but Common Lisp: A Gentle Introduction to Symbolic Computation gets my vote as the best book for Common Lisp beginners. Working through it was a joy.
Shared structure is overrated. The cases where you need a tree-like mutable structure are vanishingly small in modern times. Mostly it boils down to "just use hash tables."
This isn't just a dismissive observation. It's the heart of why Lisp is so hard to implement. When I ignored mutable cons cells, I realized I could just implement bel in Python by using actual Python lists.
Presto, now you have car, cdr, and join (cons) in Python.
This works (and works very well). You can build lists with Lisp and then pass them off to other Python libraries -- after all, they're just lists. And in the rare case where you care about mutating cons cells, you can just use a dict instead.
You're right, I was imprecise. I meant specifically shared list structure in Lisp contexts, not shared structures in general.
There's a fascination in the Lisp world for cons cells. Specifically the cell aspect. If you represent lists as:
l = [x, [y, [z]]]
Then you can implement car as l[0] and cdr as l[1].
If you require mutable cons cells, that's pretty much the only way to do it. Because if you want to set the car of cdr(l), how do you do it? You can just do
cdr(l)[0] = t
Because that's the same as
l[1][0] = t
Which of course makes the list become
l = [x, [t, [z]]]
But this sucks. It's always sucked, and Lispers go out of their way to ignore the fact that it sucks. I wince at having such a dismissive attitude here, but it's been the source of years of frustrations.
It's a frustration because if Lisp had been implemented using vectors and hash tables instead, it'd be in a far stronger position today. Everyone uses vectors. Vectors are [1, 2, 3, 4] ... Plain old arrays! In fact, I used vectors in the above examples, and didn't even have to explain what they were. Everyone knows and understands arrays.
Lisp can work fine with vectors, if you drop the requirement of mutable cons cells. Because l becomes:
l = [x, y, z]
And cdr(l) becomes l[1:], so cdr(l) returns [y, z] -- an entirely new vector containing y and z.
This might seem like nonsense, but in practice it's not. In practice, you're rarely building lists containing hundreds of thousands of elements. Usually it's much smaller lists contained in other structures, like hash tables.
And when the lists are small, you really don't care about creating new lists. The fact that cdr(l) returns a copy of l minus the first element is inconsequential. You'll ~never experience a slowdown.
And the gains are massive. You get to interface with all your native libraries using lisp algorithms. You don't have to convert from "lisp lists" to "python lists" or "javascript lists" or anything else. They're just arrays.
Lisp has had vectors and hash tables considerably longer than Python has existed.
It's a general purpose language, and any competent Lisper uses the right data structure for the job. As it happens, the cons tree (not a list, a tree!) is the right data structure for representing Lisp code. It's not necessarily the right data structure for representing other non-code data that Lisp code is working with.
> Yes, but cdr(vector(1, 2, 3)) throws an error in almost all lisp implementations. Which means you can’t use the classic algorithms on them, like map.
What? MAP[1] works just fine with vectors and other sequence types. Are you somehow surprised that MAPCAR doesn't? The name makes it pretty obvious I'd think. I'm starting to think you just lack familiarity with the language that you're criticizing.
Suppose Lisp were forced to abandon cons cells and could only use vectors to represent code. What's the disadvantage?
My retort to you would be "I'm starting to think you like complexity for the sake of it," but debates are much more fun when we're both genuinely interested in the other's perspective.
Variable length vectors are observably more complex than 2-tuples. And forgive me, but you are giving me the impression that you are trolling rather than debating.
Suppose Lisp were forced to abandon cons cells and could only use SQL tables to represent code. What's the disadvantage?
Anyhow, by all means write your Python vector based Lisp dialect. It's no skin off my teeth. Maybe it really is superior and you'll be the next Rich Hickey.
cons is a recursive data structure. it’s not discussed much here in the comments, but a lot of its useability comes from that fact - you can write elegant recursive algorithms with cons as your data structure
with vectors that doesn’t work UNLESS you add a bit of overhead (which most optimising programs may do since for many cases vectors can be more performant)
And some Lisp implementations optimize some cons lists into vectors. The technique is called CDR encoding[1]. It's my understanding that at least the latest generation of modern CPUs actually have optimized instructions for tagged 64 bit pointers too, so this can be implemented efficiently on current hardware just as it was on Lisp machines! Of note though is that mutability complicates things, as usual.
It's just that since decades Lisp implementations don't do this, since most implementors don't see it providing much advantage (in speed or size) and it complicates the implementation.
> In the presence of mutable objects, CDR coding becomes more complex. If a reference is updated to point to another object, but currently has an object stored in that field, the object must be relocated, along with any other pointers to it. Not only are such moves typically expensive or impossible, but over time they cause fragmentation of the store. This problem is typically avoided by using CDR coding only on immutable data structures.
This is exactly what I've been saying. Thank you for providing a formal reference to the idea.
(I'm a bit confused how we wound up talking past each other, since my original proposal was identical to CDR coding on immutable cons cells.)
Without having any idea of this, right now I'm facing the problem of making a PDDL compiler (which is basically Lisp) in C++ , and this was the way I took. Lists are just std::vectors<std::variant>> and the variant can be a function, number (literal) or a variable.
I'd love to see your code and compare notes! Mine is pretty crummy; I'm not sure there are any worthwhile ideas in it. Did you have much trouble with the std::variant route?
It seems you're suggesting making CDR into an O(N) operation. So for example ordinary list processing algorithms that take O(N) will now be O(N^2).
Anyway, these kind of weird arguments from people who don't get it have been proposed and shot down a million times before, and I'm not sure there's any value reiterating. I suggest anyone interested in Lisp (or any programming language, really) ignore weird HN critiques and just read a book, like the one linked here.
This isn't a case of Lisp being hard to implement, this is a case of trying to make your Lisp work with Python language idiosyncrasies. These two issues have close to nothing to do with one another.
Shared mutable state is an odd focus here. The point isn't that a cons cell is some magical thing. The point is that LISP gives you a ton of things that it already knows how to do.
Other languages have started catching up with massive standard libraries. But... LISP has been there for a long time.
> Shared structure is overrated. The cases where you need a tree-like mutable structure are vanishingly small in modern times. Mostly it boils down to "just use hash tables."
So confused by this. Shared, tree-like, and mutable seem pretty orthogonal to me.
Sure, I'll forgo mutable structure. And since I don't mutate, I can safely share structure. But I don't want O(n) update operations, so I'd better make my hash tables use a tree-shaped data structure:
I think the point to take home here is that LISP has a rich set of functions and building blocks around lists. Indeed, if you have something you want to do to a list, that function probably already exists.
Contrasted with many other languages that are catching up, but sometimes have surprising amount of boilerplate to process data.
I wonder what the minimal set of data structures is that you can build all others out of. For example binary trees can be built with lists, SEXPs are proof of that. You can of course also make a (boxed) linked list out of an array of 2 pointers, with one element pointing to the value and the other to the next element. You can make arrays with just pointer arithmetic, sooooo... just pointers is enough? (I guess this can also be shown from the "other" direction, by pointing out that assembly has nothing but arithmetic and pointers)
You would also need various arithmetic operations, possibly up to hashing algorithms for hash tables/sets/bloom filters/etc. I would love to know if anyone can point me to an article or something describing the minimal set of operations needed to construct any data structure.
For those who haven't checked either nandgame or nand2tetris out, I would recommend them as fun little diversions in boolean logic and computer architecture.
Maybe I am starting to spam the thread a bit here but I think the answer is canonical S-expressions, but proving that to be the case is more tricky than it looks although it is also kinda obvious from the surface level; vectors in s-expressions.
But yeah the real answer is lambda calculus, see lambda lisp and justine.lol
Any sufficiently rich data structure is probably enough on its own. Lists certainly are. For example, you don't need arithmetic separately, since you can simulate it with lists in any number of ways; e.g., the von Neumann-esque `0 = ()` and `succ n = n : n`, according to which a number is represented by a canonical list of that length. Once you can define `succ`, you can define all other arithmetic. If you're willing to give up canonical representatives, and represent a number by any list of that length, then you get an easy definition of addition by concatenation.
Can anyone link a screencast of doing Common Lisp with all its cool interactive features? (REPL-driven, SLY/SLIME, restarts, etc) and I mean doing real small projects not just simply touting how cool lisp is or talking about (+ 2 3) and C-c C-c
I tried searching on YouTube but didn't find anything particularly unique.
This is a real project, this guy wrote a compiler, to convert common lisp to GLSL (I'm not talking about a simple DSL with code generation, but also type checking and so on).
In his Livestreams, he usually try to implement a specific 3D feature (like triplanar mapping, the Phong of lighting, ...).
Everything is done in a single window, with the program being recompiled while running, pure lisp style.
He is on a hiatus right now though with livestreams, but there is plenty of material already to watch ...
The real elegance of Lisp is that malloc() has been renamed to (cons) and everyone feels smarter about it.
I jest a little bit, but that's really the fundamental thing about list-processing. For most code, you don't really care about runtime, and you really just need "a data structure that probably can solve the problem", and the (cons) based list of car and cdr solves it.
List processing itself is an elegant technique: a garbage collector tuned for exactly (cons) (2-element "items" that have a car-and-cdr, and the cdr is usually a pointer to another cons), is small, simple, elegant to implement, and works for almost any problem imaginable.
Maybe not as fast as a properly designed specific data-structure, but it will work. On top of that, Lisp has all kinds of shortcuts to make list processing easier to type.
---------
Getting a basic implementation of whatever project you're doing in cars-and-cdrs in (cons) is more important anyway for learning about your problem. Choosing a data-structure too early can hamper your understanding and bias you towards a possibly inefficient solution.
Knuth tries to explain the topic in his "binary trees representation of trees" subject, and notes that pointers to (two pointers) elegantly solves a wide variety of problems. Whether you wanna see them as binary trees, Lisp-lists, or graphs or even collections of malloc'd() nodes, it doesn't really matter. Its the flexibility of this data-structure that is incredible.
EX: the "left" child is "down a level", and the "right" child is "next sibling". Therefore, binary trees can represent any tree, and if allowed to loop, I'm sure the cons / binary tree node can be forced into working with graphs.
Nah, I don't agree with this. Lisp is inherently dynamic, there is much more going on than just automatic garbage collection.
To achieve the same-level of expressiveness in C you need to craft an interpreter, dynamic memory allocation doesn't cut it.
I once wrote a simple linked list library in C to achieve lisp like functions, things got complex very quickly. I still dream of writing a garbage collector for it and evolve it to a lisp like state.
Like Greenspun said, I believe any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp.
There are many lisps that are not interpreted, but are instead compiled.
The beauty of the lisp language is that it doesn't care about interpreted vs compiled vs whatever. Its just the true elegance of "everything is a (lisp) list" (which is probably the wrong word. The truth of the matter is that "everything is a graph" and lisp-lists are really just a universal building block that can represent arbitrary graphs).
The important gadgets are:
1. Universal garbage collection (allowing you to ignore free() issues and simplify code)
2. Pointer to (two pointers). That is, car-and-cdr.
That's it. Everything else flows from these two things.
That is true, but some sort of a runtime bordering on being an interpreter needs to exist doesn't it. Because my brain cannot comprehend how you can do metaprogramming with macros etc. with static code.
My opinion was that the compiled lisps precompile as much as possible (calculations etc.) into assembly and leave bits they can't compile intact, that's what make them fast.
Macros just is code that transform a (list) data structure into (another different list), and then feeds (another different list) into the compiler (rather than the original (list) going into the compiler: how things happen without macros).
You can see how these things happen in like, Chicken Scheme (R5RS Scheme to C compiler).
I want to look at it to understand. But my guess is that this happens at runtime, doesn't it. If this happens at runtime, this means runtime evaluates the macro, lisp function is generated, generated lisp function is compiled and used.
How can you evaluate a complex macro at compile-time if you are doing AoT compilation? Lisp macros are not like C macros where simple substitution would suffice, they need to be evaluated.
The answers on SO are still not clear to me, some people say the macros can be evaluated at compile time, some say that the runtime needs to include some kind of interpreted to run macros. Some say incremental compilation is key to understand how macros get evaluated at compile time.
A compiled Lisp program might not be able to eval a list or load a source file, for the same reason a packaged jar generally won’t contain a copy of the Java compiler. I think eval-when controls which macro definitions (if any) need to be available at runtime, rather than being expanded away while compiling functions.
From my conversation with lispm above, I discovered that each binary SBCL produces includes the compiler as well. This is what is meant by incremental compilation I get it.
When I first heard the term incremental compilation, I thought of a process like going through the ast couple of times and evaluating expressions. This wasn't what it meant. Now it makes sense. You include the lisp compiler in each binary. For parts you cannot evaluate at compile time, you compile at runtime, just like a JIT.
> If this happens at runtime, this means runtime evaluates the macro
Generally speaking this isn’t the case. There are probably exceptions besides a repl, but they’ll almost all be repl-like because macros are effectively functions of pre-compiled code, represented as lists as written in the code.
In other words, generally speaking, a lisp program’s life cycle goes something like this:
1. Developer writes lists.
2. Some of these lists are macros, compile them and execute them with their arguments. Many of these are themselves lists and symbols, which will be preserved according to various rules depending on which lisp you’re using and how they isolate code lists from program lists. It’s complicated.
3. Recurse step two until there are no more macro calls.
4. Now you have the actual program, and now you compile that.
Macros were invented such that macro expansion does NOT happen at runtime.
Lisp designers were implementing languages in the 70s which were used to develop whole operating systems for computers with less than one million instructions per second. With window systems, networking, etc.
A big part of the history of Lisp is how to design the language such that it is efficient AND/OR dynamic. Lots of people invented clever memory management, clever implementation techniques and adjusted the language for efficiency.
The first self-hosted Lisp compiler appeared already in 1962.
Because of the way pointers are used, Forth is both compiled and not compiled.
> After the fetch and store operations are redefined for the code space, the compiler, assembler, etc. are recompiled using the new definitions of fetch and store. This effectively reuses all the code of the compiler and interpreter. Then, the Forth system's code is compiled, but this version is stored in the buffer. The buffer in memory is written to disk, and ways are provided to load it temporarily into memory for testing. When the new version appears to work, it is written over the previous version.
What is the difference between a runtime and an interpreter? I still believe forth is interpreted. Forth uses a small set of functions in assembly as its runtime/interpeter.
Your quote looks like its about bootstrapping the Forth ecosystem. After writing fetch and store operations in native assembly, you can bootstrap the forth system that is logical. This is the way Chuck Moore first used Forth anyways. He had no interpreter/compiler back than, he wrote some functions to aid him circumvent assembly and make his code portable. It is genius, but I think it's still interpreted.
You can compile python to bytecode and run it in python's vm, does this mean your python code is compiled. IMHO no, it is compiled for the python vm and python vm interprets it. Same thing applies to Forth.
Forth is interpreted, even if you compile and package it in a standalone executable binary.
An interpreter interprets, typically either a byte code or textual representation version of a program or some other intermediate form (for instance, parsing to an AST and then evaluating/interpreting that versus line-by-line or token-by-token). A runtime could include an interpreter, but doesn't have to. Go includes its own runtime which handles things like scheduling goroutines and garbage collection, but it is not interpreted nor does it include an interpreter.
This is exactly what I'm talking about. Go is a statically typed C-like compiled language. It can convert the code much or less in its entirety to machine code. Lisp and forth on the other hand cannot, I think. They need some kind of interpretation at runtime to function so dynamically. If this is not the case, please prove me wrong. The distinction between compile time vs run time bugs me a lot.
I think it is easier to say forth is closer to compiled. I can kind of imagine each user defined word being translated into assembly. With lisp I am speechles.
Lisp can be ahead of time compiled, being dynamically typed doesn't impact that. It does impact what gets generated by the compiler. Compiled CL code is usually "generic", it has logic inside that helps it dispatch based on the dynamic types during the runtime but this is not interpretation (in the sense meant by TCL, Python, and others). You can also specify the types and a compiler can, optionally, make (or use) more specific code which should error on a type mismatch but can run faster if you give it the correct, restricted types.
As to your speechlessness regarding compiled Lisp, here's a quick example:
I know that lisp compilers compile compute heavy trivial functions directly to machine code. But how is the output of a program containing a lisp macro for example. Let's say define a lisp macro don't call it and generate its assembly. What is the machine code output? This is the part I'm speechless about.
"The logic inside that helps dispatch based on the dynamic types at runtime" is the interpreter part IMHO. Plus you need logic to add the metaprogramming elements that require you to change the code after it has been written.
We need to generate an example of something we can't do in C, something which requires evaluation at runtime.
> But how is the output of a program containing a lisp macro for example.
I think you have a fundamental confusion about when and where macros are applied. In a compiled CL implementation, macros are expanded prior to compilation. The code will be exactly the same as if there was no macro involved. If you want to see what that might look like take the function body of this simple function:
Now take that output and put it in a new function, call it `baz`. Then disassemble both `bar` and `baz` (I've done this and included the output of just one because they have the same instructions):
EDIT: Snipped the excessively long code, here's a link:
It doesn't really make sense to talk about disassembling a macro as a macro is not, itself, what gets compiled when it's applied, but rather its output gets compiled (in a compiled Lisp).
> "The logic inside that helps dispatch based on the dynamic types at runtime" is the interpreter part IMHO.
Then every compiled program that uses a tagged union is really an interpreted program (which is a statement you could make a strong argument for, perhaps). The code above is still machine code, though, it's not being interpreted. This is part of the distinction between an interpreter and a runtime. Dyna...
From my conversation with lispm, I discovered that each binary sbcl produces includes the lisp compiler. That means for evaluating expressions that cannot be determined at runtime, SBCL does some kind of JIT compilation.
Now it makes sense, SBCL requires a complete compiler embedded in the runtime. Runtime is small enough that you don't care for it.
Okay I agree that lisp can be compiled. You just need a clever runtime being able to dynamically compile parts at runtime. If there are lisp implementations that do not require embedding either a compiler or an interpreter in the runtime, I'd doubt their expressiveness.
> Plus you need logic to add the metaprogramming elements that require you to change the code after it has been written.
Not sure what you mean by this but perhaps you're referring to how Lisp allows redefining functions on the fly without relinking? That's done by indirect function calls. Every function call in Lisp jumps indirectly through the function's symbol name (if it has one). This incurs a runtime penalty of one extra memory access per function call, but it enables functions to be redefined on the fly without changing any of their callers. Optimization switches exist to get rid of this extra overhead if you need maximum speed in deployed code.
You are dissasembling inside the interpreter. Interpreter already reads, evaluates before generating the assembly code. How does EVAL work if the entire program is compiled AoT?
REPL is a Read Eval Print Loop, which is a way to interact with a Lisp runtime. This is independent on how EVAL is implemented. A bunch of Lisp systems implement EVAL with an incremental compiler.
An interpreter is a Lisp feature where code gets interpreted from source at runtime. Some implementations have one, some don't, some only have an interpreter, some only have a compiler, some have several compilers, some have both.
> running sbcl without the REPL and produce an executable binary file
The executable binary file in SBCL always includes the compiler.
REPL: a user interface to execute Lisp code. Reads s-expressions, evaluates them and prints the results as s-expressions.
EVAL: the interface to execute code. A function.
Interpreter: an implementation of Lisp which interprets source code.
Byte Code Interpreter: an implementation of Lisp which interprets byte code instructions.
Compiler: an implementation of Lisp which can compile code to a) byte code, b) C code, c) machine code
In-memory compiler: an implementation of Lisp where the compiler does not create files, but writes the executable code directly to RAM
Whole-Program compiler: an implementation of Lisp, which only compiles whole programs and creates executables -> rare, but various examples exists
Thank you for taking the time to explain. I now get it. SBCL includes the compiler in each binary and this is called incremental compiling. That explains the expressiveness. It is kind of like a JIT when needed. Compile everything you can AoT, leave dynamic parts to runtime compilation. It makes perfect sense. Thanks .
I guess the difference is that in an interpreter you don't go down to assembly, you parse and run stuff. The moment you cross the line to generate bytecode/machine code or transpile into a different language you get a compiler.
Basically all SBCL code is pre-compiled. There is mostly no runtime compilation happening. Only if the user/developer actually wants it. For example one can connect to a running SBCL and have one or more networked REPLs into it.
The REPL (traditionally "listener") is a kind of interpreter, because it reads textual input, and hands it off for processing. There is some definition of "interpreter" which this meets.
lispm's point is that it's not a/the Lisp interpreter. An Lisp interpreter and Lisp listener are different things. The listener is more like a "command interpreter".
You can write a very poorly featured listener yourself, by literally following the REPL acronym: (loop (print (eval (read)))). You have not written a Lisp interpreter in four operators; the read and eval functions are doing that. The following is a copy and paste from an actual session:
Some other languages are the same way. When Bash runs a script, it's not going through the interactive command line processor that is used for interactive input, which has completion, recall and editing. That command line processor isn't what parses and understands Bash syntax.
We can write a REPL at the Bash prompt also. We can write a loop which reads a line of input, evaluates it as shell syntax, and then repeats that ad infinitum until we hit Ctrl-C:
$ while true ; do read -r command ; eval "$command" ; done
echo foo
foo
for x in 1 2 3; do printf "[%s]\n" $x; done
[1]
[2]
[3]
uname -a
Linux sun-go 4.15.0-167-generic #175-Ubuntu SMP Wed Jan 5 01:55:52 UTC 2022 i686 i686 i686 GNU/Linux
^C
The shell language interpreter is in the eval command; we have not written a shell! The "for x in 1 2 3" syntax isn't coming from our "interpreter" loop.
Lisp's eval isn't necessarily an interpreter. A Lisp implementation which has only a compiler will implement eval by compiling, like this:
;; insert expression into lambda expression.
;; compile lambda expression, resulting in a compiled function object
;; call function object, with no arguments.
(defun eval (expr)
(funcall (compile `(lambda () ,expr))))
You can write this function in any Common Lisp (just don't call it cl:eval).
Thereby you obtain a compiling eval, even if the standard cl:eval is interpretive.
Forth can be interpreted but it can also be compiled in at least two or three different ways. Forth is unique in that its interpreter can look (and perform) a lot like compiled code.
Let's say you have a list of assembly language function names FOO, BAR, BAZ, etc. Each name stands for the starting memory address of that function. Each function ends with a standard RET instruction. At address PROGRAM, you store the list of 64-bit function addresses. Now a "Forth Interpreter" is just
JSR-INDIRECT RP++
REPEAT
where beforehand you've stashed PROGRAM in register RP. Most assemblers don't provide an indirect JSR instruction but it's easy to write a macro that serves that purpose.
Is this an interpreter? The only way it differs from true compiled code is that the function calls are indirect, so it's almost as fast as regular function calls.
What if you unroll the thing so the code looks like
JSR FOO
JSR BAR
JSR BAZ
...
Now all the function calls are direct. And as a bonus, all the individual functions themselves don't have to do anything more special than directly call functions. It's turtles all the way down.
I've glossed over some issues like how to pass values and how many stacks you need and proactive tail-calling, but that's the gist of it. The whole "interpreter" just vanishes in a puff of smoke.
Thank you, I didn't know about the jsr instruction. I always imagined forth does this somehow with jmps.
Another main difference from true compiled code is that your entire program consists of subroutine calls. There are no inline instructions and a main function.
I've got a lot of reading to do on this. "Indirect jsr", I'll experiment with this.
Okay I'm convinced, forth is not interpreted when it's compiled to threaded code :). There is no main loop that reads instructions and dispatches them dynamically, the program flow is linear with subroutine calls stacked under each other.
Exactly. And there are many other inline instructions (e.g. for doing arithmetic etc) but I didn't show them here. Any instruction the CPU supports can be present in a Forth program. In a compiled Forth, words can be specified as a list of calls to other Forth words or as raw assembly instructions, or both.
Yeah. It seems to get overlooked a lot. Forth clicked for me easier than Lisp. It still requires you to build out a lot unless you build it on top of higher level languages.
I think building everything out of conses held Lisp back. It was possible, and it was deemed to be elegant, so people went too far with it. YMMV since my adventures with Lisp were around twenty years ago, but reading code, you'd see somebody constructing a list with a bunch of nested lists inside it, or some other complicated structure with conses, and you'd have no idea what it was or how they intended to use it, and you'd just have to read the code until you figured it out. It's much easier to read code that uses named data structures.
Of course in Lisp your code can and should have clearly named functions that encapsulate your use of conses to build data structures, but casually violating that encapsulation, or better yet doing without encapsulation at all, just playing with conses, was the cool way to do it, the way you programmed if you had even a little bit of swagger. That was fun as long as feeling smart about the fact that I could do it outweighed feeling annoyed at everyone else doing it, but in the end, the feeling of smartness faded and the feeling of annoyance remained.
I haven't used Lisp in years, but isn't it very easy to just name the list members by defining a structure ... thus making your use/purpose of the list elements quite transparent?
In a lot of Lisp code, people don't bother to use that feature, and instead do a lot of (undocumented (sets of ((lists) that ) have some unknown) undefined structure)
I never wrote Lisp code professionally, mostly just as a hobby for myself. It was all just dirty cons/cdr/car code.
Given how generic lisp-lists are, they're really free form and could be anything. They are probably "too generic" for a lot of applications, much like XML or JSON is overkill.
There's something to be said about writing configuration as .ini files by Python's ConfigParser, for example. Or other simpler files (even .csv files) and working off of that.
But Lisp gives you that "power" to have a true hierarchy / language built into your lists. With that power, comes great confusion 3 months later when you forget the structure.
-------
A good, professional programmer probably should:
1. Start with the Lisp-lists as a prototype
2. Simplify down to a simpler structure, like vector, or dictionary/HashMap, if possible.
My gut feeling is that this hasn't been true for a long time, unless you're really implementing a small test. Even then, using CLOS is quicker than deciding that "CDDR" refers to attribute "X".
Modern CL is referred to as a multi-paradigm language, and I almost always start a project by starting with "defclass" and "defmethod" like in any OO language.
I think this was one of the big differences from Scheme vs CL.
Scheme, especially R5RS which is what I played around with the most, was about purity and simplicity. It wasn't really a practical/pragmatic language (though practical Schemes existed, like Racket), it was almost a "group study" in functional programming and greater programming concepts.
Common Lisp of course, was a practical/pragmatic language from the start. So of course you use vectors / hash maps / object-oriented programming.
-------
That being said, I fondly remember a lot of my scheme code, even if it was a bit quick-and-dirty. Its a paradigm that clearly works for a ton of problems.
In a modern Common Lisp program, using conses for everything is serious code smell. It reeks of a very obsolete Lisp style and it makes code incredibly difficult to maintain. Doesn't matter if you give good names to deeply-nested list accessors; it's still a bad practice.
That doesn't mean conses and lists should be prohibited, but any use of conses/lists instead of arrays, CLOS objects, hash tables, or structs needs to be justified. And a programmer's ignorance of those other data structures is not a good enough justification.
Unless you have reason to worry about the internals and how they’re implemented (which last I used Clojure is unavoidable for non-trivial code, but I don’t think that’s intended), the data structures should all conceptually desugar to s-expressions. And they certainly do at the reader level. All of the non-list literal types are semantically equivalent to some kind of list representing how their values are defined or generated as a [specialization of] `(seq . …)`.
I don't think you're alone in this sentiment. I found myself on the wikipedia article for cons and found this witty quip in the Usage in Conversation section[0]:
> I sped up the code a bit by putting in side effects instead of having it cons ridiculously.
In my experience, this is far less common in Clojure and far from idiomatic. The language’s core data structures and abstractions around them are all[1] based around `seq`, which is conceptually list-like in some respects. But among other distinctions (eg seq is presumed lazy by most APIs), it’s used to back various higher-level data structures, with various map structures in common use. There is an actual list type/structure which more or less works like cons, but it’s generally only used for code structure. I’m sure there’s a lot more that’s not “lisp” about Clojure, but I think this divergence is one of its big strengths.
From what I’ve seen, this also seems uncommon in Racket, but I haven’t actually written code in Racket or spent time in the ecosystem, so I can’t say nearly so much about what’s typical with much confidence.
1: Excepting reference types, which are all based around either transactional logic, “transients” which are scope-local mutables, or host VM interop.
> It's much easier to read code that uses named data structures.
That's why a bunch of large Lisp software was written with named data structures in the 70s/80s. They were called class, flavor, structure, frame, ... One can find a lot about that in the literature. Common Lisp was literally the first officially standardized object-oriented language, providing named classes and generic functions as building blocks.
Yes, this is the lovely elegance that comes out of building out of a nice re-composable underlying concept. I still find it hard all these years later to fully wrap my head around building programs in this style, but I adore the fact that it exists.
FWIW I feel like RelationalAI, in their "Rel" language, has done for n-ary (database) relations what Lisp&Scheme did for lists. Something I had pondered myself for years and kind of grasped at but never really got, and I think they've done it. It's really quite elegant, worth checking out:
"The constants true and false are also relations, of arity 0. There are only two of these: false is {} (the empty relation with arity 0), and true is {()}, that is, the relation with one empty tuple (arity 0 and cardinality 1)."
and
"In Rel, a single elements is identified with a relation of arity 1 and cardinality 1. For example, the number 7 is the same as the relation {(7)}"
This lets them do clever things like use relational cross-product ("," operator) kind of like Lisp's `cons` to build tuples, so:
(1, 2, 3)
builds the relation
{(1,2,3)} from {(1)}, {(2)}, {(3)}.
And also the same operator can be used for filtering because "false" and "true" likewise evaluate to relations, so crossproducting them acts like a "where" clause, so:
^ "filters" myelements to return the values in the relation that are greater than 3 and less than 7.
And it also works as a pure cross-product operator, of course, for when you need that.
It's the same kind of elegant composability you get from Lisp, but with a maybe semantically richer datatype and a richer set of (relational algebraic) operations.
Very interesting! thanks for this. The n-ary relations are bipartite graphs, one partition in the graph is the relations (hyperedges). This is /the/ universal (turing machine) theorem of computing.
By the way, check out datalisp.is, I think we should re-encode the web :)
>lists are an excellent data structure for representing any kind of heterogeneous and/or hierarchical data
I found this a really curious statement. Linked lists made sense given the limitations in compute when LISP was invented (~1958) but how are vectors not a superior solution in every way, when available?
Vectors give you fast random access and fast append plus the same first/next semantics and performance as lists and the same ability to form trees. Pretty much the only thing lists are better at is prepend (which in my experience is much less useful than append).
Then for truly heterogeneous data you probably want hash maps as well, which, if you want something associative rather than sequential, are in a class all their own.
In homoiconic languages like lisp I think you'd need more flexibility than vectors.
What if you need to remove an item for example, do you need to shift all remaining items to keep order or mark the removed section with Xs so that the cursor jumps to the next data item.
You need to be able to randomly access bits and pieces to form a network.
You could see forth as just netstrings recursively. You evaluate the outermost netstring by unquoting and then doing a forth over the netstrings it contains.
Lisp lists aren't linked lists. Pointers to TWO pointers (first pointer is named car, and the 2nd pointer is named cdr).
The realization that (cons) / Lisp-lists / car-and-cdr give is that you can represent arbitrary graphs (!!!) with car / cdr / cons, leading to a truly universal data-structure.
Not necessarily an _efficient_ datastructure mind you, but a universal one.
------
So really, Lisp-lists are just the "try to represent your problem as a graph" and it really works 99% of the time, because graphs are just so flexible of a concept.
For example, take the HTML of this webpage. <DOCTYPE> <blah blah blah> and all that. Its pretty obvious how to convert it into an equivalent (DOCTYPE (blah blah blah) (p) ...) kind of structure.
Now try to do the same with vectors and hashmaps. You can't. You need to create a concept of vectors-of-vectors and hashmaps-of-hashmaps with arbitrary amount of depth.
-----------
Example HTML to think about
<div>
<p> Start of a paragraph </p>
<p> Second paragraph <b> but some of it is bold</b> </p>
</div>
(div (p "Start of a paragraph") (p "Second paragraph" (b " but some of it is bold")))
Lisp itself is written in the form of Lisp-lists. The entirety of your programming code _IS_ a list, proving how truly universal this data-structure is.
You can't convert your C code into a vector or a hash-map. It just doesn't make sense. Meanwhile, all of lisp is a list, including the code.
Universal in the sense of structure, but vectors are pretty faithful to the machine memory.. which also makes them universal but more in terms of content. Therefore we should use canonical S-expressions as a universal data interchange format. When you build metaprogramming on top of it then you can do some cool things I think (check out datalisp.is).
> Pointers to TWO pointers (first pointer is named car, and the 2nd pointer is named cdr).
This is not true; only cdr is a pointer to a pointer. car is a pointer to a value. For example, if x is (1 2), then (car x) is a pointer to the value 1, while (cdr x) is a pointer to the list (2), so only the latter is "to a pointer".
> convert your C code into a vector or a hash-map.
nit: C has neither vectors nor hash-maps, neither builtin nor part of any standard library.
This isn't really true either. Either half of a cons could contain a pointer or a direct value. Lisp makes the decision about pointers based on whether the value you're trying to store is small enough to fit there directly or not. And crucially, Lisp can tell the difference between a pointer and a value at runtime which means it will always do the right thing with whatever it finds.
This is why it gets dicey talking about pointers in Lisp: Pointers exist all over the place in Lisp but you have no direct control over them. That's the garbage collector's job.
Nothing in Lisp requires pointers in either half of a cons cell. There is a convention followed by the Lisp reader and printer that lists are represented with their head in the car and their remainder in the cdr of a cons cell, but the cons cells themselves don't care. Cons cells themselves know nothing about lists. They're just dumb 2-tuples with a car half and a cdr half. You're free to stick anything you want in either side. Each side holds 64 bits, and if you want to stick a string containing the Gettysburg address in the car [or cdr], Lisp will let you. (More specifically if you create this string Lisp will allocate a pointer for it, and it will then stick that pointer in the car.)
> Nothing in Lisp requires pointers in either half of a cons cell.
You are definitely right about that, but the initial claim was made about "Lisp list", for which cdr is certainly a pointer. I would expect that when we refer to "Lisp lists", we certainly don't include things like (cons 1 2)
If you're mutating it, yes. And CL/Scheme do offer that datatype.
Linked lists support a functional style building shared structures without having to worry about plan interference from the mutations. Clojure can do this with immutable arrays instead of lists, but the implementation is hairier than either linked lists or mutable arrays.
That lambda expression shares the args object with the caller, of course (and an array would do the same), but it also shares the body object, which an array won't do unless it's a very specialized array.
The backquote expression can compile down to:
(list* 'lambda args body)
which allocates exactly two cons cells: one cell to hold lambda in its car; another one to hold args in its car and the body goes into the cdr of that same one.
It's also incredibly common to work with the suffix of a list.
In the reverse direction, we can break the lambda:
This requires no memory allocation We can pull the args out of an array-based lambda expression for free; but not the body (suffix of the array).
Vectors have the advantage of compact storage; a large vector's storage should be roughly the value word size times number of elements, plus small fixed overhead. Each element of a list costs us a cons cell (unless we have cdr coding, which is just little vectors in disguise). Cons cells can be compactly allocated, but not like the elements of a vector. They can be individually reclaimed though. If we cdr three steps down a list, and nothing has retained the pointer to that list, those three conses can be identified as garbage and reclaimed.
One example is queues: Lists are superior to vectors for queues that need to grow and shrink. It's easy to build an augmented list with an extra cons cell at the beginning that contains a pointer to both the first and last cons cells of the queue. This provides O[1] prepend, append, and push and pop operations. [Popping from the far end remains slow, which is why you typically push onto the far end and pop from the near end.]
Doing this with vectors is internally much messier and requires a lot of copying, which makes it slower, unless your queue is a circular buffer of fixed size.
I'm seeing a lot of people sort of dismissing the usefulness of lists without really understanding why Lisp is important: aren't vectors and hash maps better? Isn't CONS just malloc()? Doesn't Forth solve the problem that low-level languages like C are inflexible?
— ⁂ —
The first thing to understand is that Lisp invented functional programming. (Seibel's chapter mentions this, of course.)
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're not very cache-friendly, and sometimes those are more important considerations.
To define your procedures recursively, it's very helpful to define your data types recursively. Recursively-defined lists (for example, "a list of Ts is either the empty list of Ts or a T followed by a list of Ts") support this recursive, immutable approach to programming.
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.
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.
— ⁂ —
The second thing about Lisp is that it has orthogonal serialization and deserialization: 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's especially easy to implement if you only have lists and atoms; it'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.
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.
— ⁂ —
The third thing about Lisp is that it supports metaprogramming very well. 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'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.
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.
— ⁂ —
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. ...
124 comments
[ 4.3 ms ] story [ 182 ms ] threadI don’t recall if it has instructions on getting a dev env up and running, but if it does I imagine they’re out of date. Emacs with Sly or SLIME is what I’ve used, but I believe there are viable options for proper interactive development in vim and vs code among others.
If you just use a basic editor and paste code into a repl in a terminal you won’t be getting the experience most Lispers do.
The chapter on files in the Practical Common Lisp book wasn't complete enough for me to read a one line file of 800MB which is part of the Harvard Library Open Metadata archived set.
http://www.cs.cmu.edu/~dst/LispBook/index.html
— which, yes, is a wonderful book for a complete beginner.
This isn't just a dismissive observation. It's the heart of why Lisp is so hard to implement. When I ignored mutable cons cells, I realized I could just implement bel in Python by using actual Python lists.
Presto, now you have car, cdr, and join (cons) in Python.This works (and works very well). You can build lists with Lisp and then pass them off to other Python libraries -- after all, they're just lists. And in the rare case where you care about mutating cons cells, you can just use a dict instead.
EDIT: See https://news.ycombinator.com/item?id=33194570 for a more thorough explanation of why mutable cons cells are problematic.
Every MMU running a Unix with mmap probably disagrees!
There's a fascination in the Lisp world for cons cells. Specifically the cell aspect. If you represent lists as:
Then you can implement car as l[0] and cdr as l[1].If you require mutable cons cells, that's pretty much the only way to do it. Because if you want to set the car of cdr(l), how do you do it? You can just do
Because that's the same as Which of course makes the list become But this sucks. It's always sucked, and Lispers go out of their way to ignore the fact that it sucks. I wince at having such a dismissive attitude here, but it's been the source of years of frustrations.It's a frustration because if Lisp had been implemented using vectors and hash tables instead, it'd be in a far stronger position today. Everyone uses vectors. Vectors are [1, 2, 3, 4] ... Plain old arrays! In fact, I used vectors in the above examples, and didn't even have to explain what they were. Everyone knows and understands arrays.
Lisp can work fine with vectors, if you drop the requirement of mutable cons cells. Because l becomes:
And cdr(l) becomes l[1:], so cdr(l) returns [y, z] -- an entirely new vector containing y and z.This might seem like nonsense, but in practice it's not. In practice, you're rarely building lists containing hundreds of thousands of elements. Usually it's much smaller lists contained in other structures, like hash tables.
And when the lists are small, you really don't care about creating new lists. The fact that cdr(l) returns a copy of l minus the first element is inconsequential. You'll ~never experience a slowdown.
And the gains are massive. You get to interface with all your native libraries using lisp algorithms. You don't have to convert from "lisp lists" to "python lists" or "javascript lists" or anything else. They're just arrays.
If you want to try it out for yourself, give Lumen a spin: https://github.com/sctb/lumen
His Postgres FFI is the prettiest lisp FFI you’ll ever see. https://github.com/sctb/motor/blob/master/pq.l
Sounds a lot like Clojure
It's a general purpose language, and any competent Lisper uses the right data structure for the job. As it happens, the cons tree (not a list, a tree!) is the right data structure for representing Lisp code. It's not necessarily the right data structure for representing other non-code data that Lisp code is working with.
It’s worth considering carefully why you feel cons cells are so important for lisp code. Nested vectors are trees. Why not represent
asWhat? MAP[1] works just fine with vectors and other sequence types. Are you somehow surprised that MAPCAR doesn't? The name makes it pretty obvious I'd think. I'm starting to think you just lack familiarity with the language that you're criticizing.
[1] http://clhs.lisp.se/Body/f_map.htm
My retort to you would be "I'm starting to think you like complexity for the sake of it," but debates are much more fun when we're both genuinely interested in the other's perspective.
Suppose Lisp were forced to abandon cons cells and could only use SQL tables to represent code. What's the disadvantage?
Anyhow, by all means write your Python vector based Lisp dialect. It's no skin off my teeth. Maybe it really is superior and you'll be the next Rich Hickey.
with vectors that doesn’t work UNLESS you add a bit of overhead (which most optimising programs may do since for many cases vectors can be more performant)
[1] https://en.wikipedia.org/wiki/CDR_coding
> In the presence of mutable objects, CDR coding becomes more complex. If a reference is updated to point to another object, but currently has an object stored in that field, the object must be relocated, along with any other pointers to it. Not only are such moves typically expensive or impossible, but over time they cause fragmentation of the store. This problem is typically avoided by using CDR coding only on immutable data structures.
This is exactly what I've been saying. Thank you for providing a formal reference to the idea.
(I'm a bit confused how we wound up talking past each other, since my original proposal was identical to CDR coding on immutable cons cells.)
std::variant is really tricky, mostly because of C++'s type system. I went with std::any. My attempt is here: https://gist.github.com/shawwn/63e0f010479efd95ebffdf2108645...
I'd love to see your code and compare notes! Mine is pretty crummy; I'm not sure there are any worthwhile ideas in it. Did you have much trouble with the std::variant route?
What I'm doing is an extremely simple evaluator, which can do what is required for PDDL: basic arithmetic, logic operators and IF.
Anyway, these kind of weird arguments from people who don't get it have been proposed and shot down a million times before, and I'm not sure there's any value reiterating. I suggest anyone interested in Lisp (or any programming language, really) ignore weird HN critiques and just read a book, like the one linked here.
I tried. It sucks. The conversion becomes a problem all over the place.
isinstance(Cons(nil, nil), list) will fail, for example.
I posted a more thorough answer here: https://news.ycombinator.com/item?id=33194570
I think I see where your problem actually is.
Other languages have started catching up with massive standard libraries. But... LISP has been there for a long time.
Lisp is hard to implement? The list processing core is very small and relatively easy to implement.
So confused by this. Shared, tree-like, and mutable seem pretty orthogonal to me.
Sure, I'll forgo mutable structure. And since I don't mutate, I can safely share structure. But I don't want O(n) update operations, so I'd better make my hash tables use a tree-shaped data structure:
https://en.wikipedia.org/wiki/Hash_array_mapped_trie
Contrasted with many other languages that are catching up, but sometimes have surprising amount of boilerplate to process data.
You would also need various arithmetic operations, possibly up to hashing algorithms for hash tables/sets/bloom filters/etc. I would love to know if anyone can point me to an article or something describing the minimal set of operations needed to construct any data structure.
For those who haven't checked either nandgame or nand2tetris out, I would recommend them as fun little diversions in boolean logic and computer architecture.
But yeah the real answer is lambda calculus, see lambda lisp and justine.lol
If you'll forgive my giving an answer that clearly wasn't what you intended, rather famously, lambdas are sufficient: https://en.wikipedia.org/wiki/Lambda_calculus. See also https://en.wikipedia.org/wiki/Combinatory_logic.
I tried searching on YouTube but didn't find anything particularly unique.
For larger projects I remember youtube videos for Diablo and Minecraft clones.
This is a real project, this guy wrote a compiler, to convert common lisp to GLSL (I'm not talking about a simple DSL with code generation, but also type checking and so on).
In his Livestreams, he usually try to implement a specific 3D feature (like triplanar mapping, the Phong of lighting, ...).
Everything is done in a single window, with the program being recompiled while running, pure lisp style.
He is on a hiatus right now though with livestreams, but there is plenty of material already to watch ...
I jest a little bit, but that's really the fundamental thing about list-processing. For most code, you don't really care about runtime, and you really just need "a data structure that probably can solve the problem", and the (cons) based list of car and cdr solves it.
List processing itself is an elegant technique: a garbage collector tuned for exactly (cons) (2-element "items" that have a car-and-cdr, and the cdr is usually a pointer to another cons), is small, simple, elegant to implement, and works for almost any problem imaginable.
Maybe not as fast as a properly designed specific data-structure, but it will work. On top of that, Lisp has all kinds of shortcuts to make list processing easier to type.
---------
Getting a basic implementation of whatever project you're doing in cars-and-cdrs in (cons) is more important anyway for learning about your problem. Choosing a data-structure too early can hamper your understanding and bias you towards a possibly inefficient solution.
Knuth tries to explain the topic in his "binary trees representation of trees" subject, and notes that pointers to (two pointers) elegantly solves a wide variety of problems. Whether you wanna see them as binary trees, Lisp-lists, or graphs or even collections of malloc'd() nodes, it doesn't really matter. Its the flexibility of this data-structure that is incredible.
EX: the "left" child is "down a level", and the "right" child is "next sibling". Therefore, binary trees can represent any tree, and if allowed to loop, I'm sure the cons / binary tree node can be forced into working with graphs.
To achieve the same-level of expressiveness in C you need to craft an interpreter, dynamic memory allocation doesn't cut it.
I once wrote a simple linked list library in C to achieve lisp like functions, things got complex very quickly. I still dream of writing a garbage collector for it and evolve it to a lisp like state.
Like Greenspun said, I believe any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp.
The beauty of the lisp language is that it doesn't care about interpreted vs compiled vs whatever. Its just the true elegance of "everything is a (lisp) list" (which is probably the wrong word. The truth of the matter is that "everything is a graph" and lisp-lists are really just a universal building block that can represent arbitrary graphs).
The important gadgets are:
1. Universal garbage collection (allowing you to ignore free() issues and simplify code)
2. Pointer to (two pointers). That is, car-and-cdr.
That's it. Everything else flows from these two things.
My opinion was that the compiled lisps precompile as much as possible (calculations etc.) into assembly and leave bits they can't compile intact, that's what make them fast.
You can see how these things happen in like, Chicken Scheme (R5RS Scheme to C compiler).
Macros would be evaluated at compile-time (or arguably _right before_ compile time).
I found my exact question on stackoverflow: https://stackoverflow.com/questions/7072980/how-do-you-compi...
The answers on SO are still not clear to me, some people say the macros can be evaluated at compile time, some say that the runtime needs to include some kind of interpreted to run macros. Some say incremental compilation is key to understand how macros get evaluated at compile time.
I will run experiments on this.
When I first heard the term incremental compilation, I thought of a process like going through the ast couple of times and evaluating expressions. This wasn't what it meant. Now it makes sense. You include the lisp compiler in each binary. For parts you cannot evaluate at compile time, you compile at runtime, just like a JIT.
Generally speaking this isn’t the case. There are probably exceptions besides a repl, but they’ll almost all be repl-like because macros are effectively functions of pre-compiled code, represented as lists as written in the code.
In other words, generally speaking, a lisp program’s life cycle goes something like this:
1. Developer writes lists.
2. Some of these lists are macros, compile them and execute them with their arguments. Many of these are themselves lists and symbols, which will be preserved according to various rules depending on which lisp you’re using and how they isolate code lists from program lists. It’s complicated.
3. Recurse step two until there are no more macro calls.
4. Now you have the actual program, and now you compile that.
5. Now you can execute the actual program.
Lisp designers were implementing languages in the 70s which were used to develop whole operating systems for computers with less than one million instructions per second. With window systems, networking, etc.
A big part of the history of Lisp is how to design the language such that it is efficient AND/OR dynamic. Lots of people invented clever memory management, clever implementation techniques and adjusted the language for efficiency.
The first self-hosted Lisp compiler appeared already in 1962.
Because of the way pointers are used, Forth is both compiled and not compiled.
> After the fetch and store operations are redefined for the code space, the compiler, assembler, etc. are recompiled using the new definitions of fetch and store. This effectively reuses all the code of the compiler and interpreter. Then, the Forth system's code is compiled, but this version is stored in the buffer. The buffer in memory is written to disk, and ways are provided to load it temporarily into memory for testing. When the new version appears to work, it is written over the previous version.
Your quote looks like its about bootstrapping the Forth ecosystem. After writing fetch and store operations in native assembly, you can bootstrap the forth system that is logical. This is the way Chuck Moore first used Forth anyways. He had no interpreter/compiler back than, he wrote some functions to aid him circumvent assembly and make his code portable. It is genius, but I think it's still interpreted.
You can compile python to bytecode and run it in python's vm, does this mean your python code is compiled. IMHO no, it is compiled for the python vm and python vm interprets it. Same thing applies to Forth.
Forth is interpreted, even if you compile and package it in a standalone executable binary.
I think it is easier to say forth is closer to compiled. I can kind of imagine each user defined word being translated into assembly. With lisp I am speechles.
As to your speechlessness regarding compiled Lisp, here's a quick example:
(SBCL was used for the above)"The logic inside that helps dispatch based on the dynamic types at runtime" is the interpreter part IMHO. Plus you need logic to add the metaprogramming elements that require you to change the code after it has been written.
We need to generate an example of something we can't do in C, something which requires evaluation at runtime.
I think you have a fundamental confusion about when and where macros are applied. In a compiled CL implementation, macros are expanded prior to compilation. The code will be exactly the same as if there was no macro involved. If you want to see what that might look like take the function body of this simple function:
And run it through `macroexpand` (`with-open-file` is the macro I'm particularly interested in here): Now take that output and put it in a new function, call it `baz`. Then disassemble both `bar` and `baz` (I've done this and included the output of just one because they have the same instructions):EDIT: Snipped the excessively long code, here's a link:
https://topaz.github.io/paste/#XQAAAQCODwAAAAAAAAAQYOhAaDnr7... (still long, but at least HN will truncate it)
It doesn't really make sense to talk about disassembling a macro as a macro is not, itself, what gets compiled when it's applied, but rather its output gets compiled (in a compiled Lisp).
> "The logic inside that helps dispatch based on the dynamic types at runtime" is the interpreter part IMHO.
Then every compiled program that uses a tagged union is really an interpreted program (which is a statement you could make a strong argument for, perhaps). The code above is still machine code, though, it's not being interpreted. This is part of the distinction between an interpreter and a runtime. Dyna...
I think this is called incremental compilation: https://en.wikipedia.org/wiki/Incremental_compiler
Now it makes sense, SBCL requires a complete compiler embedded in the runtime. Runtime is small enough that you don't care for it.
Okay I agree that lisp can be compiled. You just need a clever runtime being able to dynamically compile parts at runtime. If there are lisp implementations that do not require embedding either a compiler or an interpreter in the runtime, I'd doubt their expressiveness.
Not sure what you mean by this but perhaps you're referring to how Lisp allows redefining functions on the fly without relinking? That's done by indirect function calls. Every function call in Lisp jumps indirectly through the function's symbol name (if it has one). This incurs a runtime penalty of one extra memory access per function call, but it enables functions to be redefined on the fly without changing any of their callers. Optimization switches exist to get rid of this extra overhead if you need maximum speed in deployed code.
The use of the macro gets expanded at compile time and the expanded code then gets compiled.
Lisp macros are designed in such a way that they are be expanded before runtime.
> evaluation at runtime
Evaluation at runtime does not mean the code gets not compiled.
The SBCL implementation of Common Lisp:
You'll see that EVAL at runtime compiles the code on-the-fly and in-memory to ARM64 machine code.What you see is no interpreter. It's an interactive interface, reading code, compiling it, executing it, printing the result.
There is by default no interpreter. Everything is compiled in SBCL.
A Lisp system typically includes an on-board compiler and/or interpreter.
Try running sbcl without the REPL and produce an executable binary file. Maybe the binary representation changes into something with dynamic dispatch?
An interpreter is a Lisp feature where code gets interpreted from source at runtime. Some implementations have one, some don't, some only have an interpreter, some only have a compiler, some have several compilers, some have both.
> running sbcl without the REPL and produce an executable binary file
The executable binary file in SBCL always includes the compiler.
REPL: a user interface to execute Lisp code. Reads s-expressions, evaluates them and prints the results as s-expressions.
EVAL: the interface to execute code. A function.
Interpreter: an implementation of Lisp which interprets source code.
Byte Code Interpreter: an implementation of Lisp which interprets byte code instructions.
Compiler: an implementation of Lisp which can compile code to a) byte code, b) C code, c) machine code
In-memory compiler: an implementation of Lisp where the compiler does not create files, but writes the executable code directly to RAM
Whole-Program compiler: an implementation of Lisp, which only compiles whole programs and creates executables -> rare, but various examples exists
I guess the difference is that in an interpreter you don't go down to assembly, you parse and run stuff. The moment you cross the line to generate bytecode/machine code or transpile into a different language you get a compiler.
lispm's point is that it's not a/the Lisp interpreter. An Lisp interpreter and Lisp listener are different things. The listener is more like a "command interpreter".
You can write a very poorly featured listener yourself, by literally following the REPL acronym: (loop (print (eval (read)))). You have not written a Lisp interpreter in four operators; the read and eval functions are doing that. The following is a copy and paste from an actual session:
Some other languages are the same way. When Bash runs a script, it's not going through the interactive command line processor that is used for interactive input, which has completion, recall and editing. That command line processor isn't what parses and understands Bash syntax.We can write a REPL at the Bash prompt also. We can write a loop which reads a line of input, evaluates it as shell syntax, and then repeats that ad infinitum until we hit Ctrl-C:
The shell language interpreter is in the eval command; we have not written a shell! The "for x in 1 2 3" syntax isn't coming from our "interpreter" loop.Lisp's eval isn't necessarily an interpreter. A Lisp implementation which has only a compiler will implement eval by compiling, like this:
You can write this function in any Common Lisp (just don't call it cl:eval). Thereby you obtain a compiling eval, even if the standard cl:eval is interpretive.Let's say you have a list of assembly language function names FOO, BAR, BAZ, etc. Each name stands for the starting memory address of that function. Each function ends with a standard RET instruction. At address PROGRAM, you store the list of 64-bit function addresses. Now a "Forth Interpreter" is just
where beforehand you've stashed PROGRAM in register RP. Most assemblers don't provide an indirect JSR instruction but it's easy to write a macro that serves that purpose.Is this an interpreter? The only way it differs from true compiled code is that the function calls are indirect, so it's almost as fast as regular function calls.
What if you unroll the thing so the code looks like
Now all the function calls are direct. And as a bonus, all the individual functions themselves don't have to do anything more special than directly call functions. It's turtles all the way down.I've glossed over some issues like how to pass values and how many stacks you need and proactive tail-calling, but that's the gist of it. The whole "interpreter" just vanishes in a puff of smoke.
Another main difference from true compiled code is that your entire program consists of subroutine calls. There are no inline instructions and a main function.
I've got a lot of reading to do on this. "Indirect jsr", I'll experiment with this.
Okay I'm convinced, forth is not interpreted when it's compiled to threaded code :). There is no main loop that reads instructions and dispatches them dynamically, the program flow is linear with subroutine calls stacked under each other.
Great username btw.
Of course in Lisp your code can and should have clearly named functions that encapsulate your use of conses to build data structures, but casually violating that encapsulation, or better yet doing without encapsulation at all, just playing with conses, was the cool way to do it, the way you programmed if you had even a little bit of swagger. That was fun as long as feeling smart about the fact that I could do it outweighed feeling annoyed at everyone else doing it, but in the end, the feeling of smartness faded and the feeling of annoyance remained.
I never wrote Lisp code professionally, mostly just as a hobby for myself. It was all just dirty cons/cdr/car code.
Given how generic lisp-lists are, they're really free form and could be anything. They are probably "too generic" for a lot of applications, much like XML or JSON is overkill.
There's something to be said about writing configuration as .ini files by Python's ConfigParser, for example. Or other simpler files (even .csv files) and working off of that.
But Lisp gives you that "power" to have a true hierarchy / language built into your lists. With that power, comes great confusion 3 months later when you forget the structure.
-------
A good, professional programmer probably should:
1. Start with the Lisp-lists as a prototype
2. Simplify down to a simpler structure, like vector, or dictionary/HashMap, if possible.
Modern CL is referred to as a multi-paradigm language, and I almost always start a project by starting with "defclass" and "defmethod" like in any OO language.
Scheme, especially R5RS which is what I played around with the most, was about purity and simplicity. It wasn't really a practical/pragmatic language (though practical Schemes existed, like Racket), it was almost a "group study" in functional programming and greater programming concepts.
Common Lisp of course, was a practical/pragmatic language from the start. So of course you use vectors / hash maps / object-oriented programming.
-------
That being said, I fondly remember a lot of my scheme code, even if it was a bit quick-and-dirty. Its a paradigm that clearly works for a ton of problems.
Don't. Lisp since decades has a lot of different data types which are easy to use: vector/arrays, structures (-> records), classes, etc.
That doesn't mean conses and lists should be prohibited, but any use of conses/lists instead of arrays, CLOS objects, hash tables, or structs needs to be justified. And a programmer's ignorance of those other data structures is not a good enough justification.
> I sped up the code a bit by putting in side effects instead of having it cons ridiculously.
[0]: https://en.wikipedia.org/wiki/Cons#Use_in_conversation
From what I’ve seen, this also seems uncommon in Racket, but I haven’t actually written code in Racket or spent time in the ecosystem, so I can’t say nearly so much about what’s typical with much confidence.
1: Excepting reference types, which are all based around either transactional logic, “transients” which are scope-local mutables, or host VM interop.
That's why a bunch of large Lisp software was written with named data structures in the 70s/80s. They were called class, flavor, structure, frame, ... One can find a lot about that in the literature. Common Lisp was literally the first officially standardized object-oriented language, providing named classes and generic functions as building blocks.
FWIW I feel like RelationalAI, in their "Rel" language, has done for n-ary (database) relations what Lisp&Scheme did for lists. Something I had pondered myself for years and kind of grasped at but never really got, and I think they've done it. It's really quite elegant, worth checking out:
https://docs.relational.ai/rel/intro/overview
E.g.
"The constants true and false are also relations, of arity 0. There are only two of these: false is {} (the empty relation with arity 0), and true is {()}, that is, the relation with one empty tuple (arity 0 and cardinality 1)."
and
"In Rel, a single elements is identified with a relation of arity 1 and cardinality 1. For example, the number 7 is the same as the relation {(7)}"
This lets them do clever things like use relational cross-product ("," operator) kind of like Lisp's `cons` to build tuples, so:
builds the relation And also the same operator can be used for filtering because "false" and "true" likewise evaluate to relations, so crossproducting them acts like a "where" clause, so: ^ "filters" myelements to return the values in the relation that are greater than 3 and less than 7.And it also works as a pure cross-product operator, of course, for when you need that.
It's the same kind of elegant composability you get from Lisp, but with a maybe semantically richer datatype and a richer set of (relational algebraic) operations.
By the way, check out datalisp.is, I think we should re-encode the web :)
I found this a really curious statement. Linked lists made sense given the limitations in compute when LISP was invented (~1958) but how are vectors not a superior solution in every way, when available?
Vectors give you fast random access and fast append plus the same first/next semantics and performance as lists and the same ability to form trees. Pretty much the only thing lists are better at is prepend (which in my experience is much less useful than append).
Then for truly heterogeneous data you probably want hash maps as well, which, if you want something associative rather than sequential, are in a class all their own.
What am I missing?
What if you need to remove an item for example, do you need to shift all remaining items to keep order or mark the removed section with Xs so that the cursor jumps to the next data item.
You need to be able to randomly access bits and pieces to form a network.
The realization that (cons) / Lisp-lists / car-and-cdr give is that you can represent arbitrary graphs (!!!) with car / cdr / cons, leading to a truly universal data-structure.
Not necessarily an _efficient_ datastructure mind you, but a universal one.
------
So really, Lisp-lists are just the "try to represent your problem as a graph" and it really works 99% of the time, because graphs are just so flexible of a concept.
For example, take the HTML of this webpage. <DOCTYPE> <blah blah blah> and all that. Its pretty obvious how to convert it into an equivalent (DOCTYPE (blah blah blah) (p) ...) kind of structure.
Now try to do the same with vectors and hashmaps. You can't. You need to create a concept of vectors-of-vectors and hashmaps-of-hashmaps with arbitrary amount of depth.
-----------
Lisp itself is written in the form of Lisp-lists. The entirety of your programming code _IS_ a list, proving how truly universal this data-structure is.You can't convert your C code into a vector or a hash-map. It just doesn't make sense. Meanwhile, all of lisp is a list, including the code.
This is not true; only cdr is a pointer to a pointer. car is a pointer to a value. For example, if x is (1 2), then (car x) is a pointer to the value 1, while (cdr x) is a pointer to the list (2), so only the latter is "to a pointer".
> convert your C code into a vector or a hash-map.
nit: C has neither vectors nor hash-maps, neither builtin nor part of any standard library.
This isn't really true either. Either half of a cons could contain a pointer or a direct value. Lisp makes the decision about pointers based on whether the value you're trying to store is small enough to fit there directly or not. And crucially, Lisp can tell the difference between a pointer and a value at runtime which means it will always do the right thing with whatever it finds.
This is why it gets dicey talking about pointers in Lisp: Pointers exist all over the place in Lisp but you have no direct control over them. That's the garbage collector's job.
Nothing in Lisp requires pointers in either half of a cons cell. There is a convention followed by the Lisp reader and printer that lists are represented with their head in the car and their remainder in the cdr of a cons cell, but the cons cells themselves don't care. Cons cells themselves know nothing about lists. They're just dumb 2-tuples with a car half and a cdr half. You're free to stick anything you want in either side. Each side holds 64 bits, and if you want to stick a string containing the Gettysburg address in the car [or cdr], Lisp will let you. (More specifically if you create this string Lisp will allocate a pointer for it, and it will then stick that pointer in the car.)
You are definitely right about that, but the initial claim was made about "Lisp list", for which cdr is certainly a pointer. I would expect that when we refer to "Lisp lists", we certainly don't include things like (cons 1 2)
BTW
so (cons 1 2) is indeed a list; it's just not a proper list.If you're mutating it, yes. And CL/Scheme do offer that datatype.
Linked lists support a functional style building shared structures without having to worry about plan interference from the mutations. Clojure can do this with immutable arrays instead of lists, but the implementation is hairier than either linked lists or mutable arrays.
Making different lists that share the same tail, by building at the front, is incredibly common in code that manipulates code.
For instance, in many situations you have a body of forms that are to be put into some statement:
That lambda expression shares the args object with the caller, of course (and an array would do the same), but it also shares the body object, which an array won't do unless it's a very specialized array.The backquote expression can compile down to:
which allocates exactly two cons cells: one cell to hold lambda in its car; another one to hold args in its car and the body goes into the cdr of that same one.It's also incredibly common to work with the suffix of a list.
In the reverse direction, we can break the lambda:
This requires no memory allocation We can pull the args out of an array-based lambda expression for free; but not the body (suffix of the array).Vectors have the advantage of compact storage; a large vector's storage should be roughly the value word size times number of elements, plus small fixed overhead. Each element of a list costs us a cons cell (unless we have cdr coding, which is just little vectors in disguise). Cons cells can be compactly allocated, but not like the elements of a vector. They can be individually reclaimed though. If we cdr three steps down a list, and nothing has retained the pointer to that list, those three conses can be identified as garbage and reclaimed.
Doing this with vectors is internally much messier and requires a lot of copying, which makes it slower, unless your queue is a circular buffer of fixed size.
How so?
Say we have a vector #(1 2 3 4) .
How do I get a vector with the first element removed? How do I get a vector with a element added?
(rest #(1 2 3 4)) -> #(2 3 4) (prepend 0 #(1 2 3 4)) -> #(0 1 2 3 4)
There are basically a few options to implement this:
a) allocate new vectors
b) implement growing/shrinking vectors
c) do something very clever internally, sharing vector memory
With cons cells this is simple. The possible drawbacks:
a) memory is fragmented into cons cells linking each other
b) lists may share memory
— ⁂ —
The first thing to understand is that Lisp invented functional programming. (Seibel's chapter mentions this, of course.)
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're not very cache-friendly, and sometimes those are more important considerations.
To define your procedures recursively, it's very helpful to define your data types recursively. Recursively-defined lists (for example, "a list of Ts is either the empty list of Ts or a T followed by a list of Ts") support this recursive, immutable approach to programming.
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.
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.
— ⁂ —
The second thing about Lisp is that it has orthogonal serialization and deserialization: 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's especially easy to implement if you only have lists and atoms; it'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.
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.
— ⁂ —
The third thing about Lisp is that it supports metaprogramming very well. 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'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.
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.
— ⁂ —
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. ...