Make a Lisp (github)

Depending on what you know and how you want to learn, you might like this:

It is a brilliant project: Lisp is implemented in many other programming languages but all of them following the same structured steps. So if you know any of those languages, you can follow along.

5 Likes

Count me out for LISP. I could never remeber CAR CDR or things like that. Head, Tail I can remember. What are the many other programing langugages?

(Moved this discussion out of the Introduce Yourself thread… just to keep things tidy)

2 Likes

Note that CAR and CDR are ancient artifacts that are no longer necessary for “modern” (since the 1980s) Lisps; Common Lisp, in for example, defines FIRST, SECOND, THIRD, etc., as well as REST; instead of CAR and CDR, a Common Lisp program can use FIRST and REST. The value of CAR and CDR remains in its compound words like CADDR and CADADR and the like, although I rapidly get lost in those and prefer to create named accessors.

And, of course, the meaning of CAR and CDR are obvious once you remember Contents of Address Register and Contents of Decrement Register. :wink:

2 Likes

The full list is in the github page.

The current count is 87 different programming languages! Pretty much all the big ones, and plenty of smaller ones, some esoterics, some because-I-can like GNU make…

1 Like

There is also https://buildyourownlisp.com which is in course format, and the implementation language is C.

1 Like

I don’t see WISP here. I was exposed to WISP in about 1965-66 at University of Colorado, Boulder. It was supposed to be something like an assembly language for LISP.

WISP sounds interesting… Wilkes seems to be involved, perhaps the W…

I found “A Base for a Mobile Programming System” by Orgass and Waite:

The compiler for the list processing language WISP is written in a subset of itself which can be compiled by SIMCMP. SIMCMP has been used to implement the WISP language for several computing machines. The programming effort required to implement WISP in this manner is about one man-week.

WISP may be described approximately by saying that it is a simple version of the “program feature” of LISP

This paper leads us to Sydney… “WISP – A self-compiling list processing language” 122 pages, Orgass, 1965, not found online, but also to “An Experiment with a Self -Compiling Compiler for a Simple List -Processing Language” by Wilkes in 1963, at the Mathematical Laboratory in Cambridge (England!) and just 20 pages.

1 Like

mal look really interesting and I will give it a try. Meanwhile I was looking into slackbuilds what is available there (yes, I am a Slackware person) and there is Roswell https://roswell.github.io/ which is kind of similar to mal (if I understand it correctly). I will compare those two.

It looks like Roswell is more of a lisp-in-a-box installation system. MAL is a project where you learn to implement your own Lisp in any implementation language you chose, and the goal is to implement a Lisp that is complete enough to run a Lisp written in the Lisp you wrote.

1 Like

Lisp, like Forth is something I’ve not really ever gotten to grips with (although I have written a lot of Forth and been paid for it!)

I have looked through the MAL thing and maybe this might be the thing to give me some appreciation of it? Although my personally preferred implementation language might just be BCPL… One day!

-Gordon

1 Like

Implementing a practical Lisp and its signature code-as-data in other programming languages is a lot more viable now that languages with garbage collection have gone mainstream. Java comes to mind. And indeed there is Clojure, which, although it doesn’t follow the Common Lisp standard, is tightly integrated into the Java universe and its libraries. It’s worth noting that Clojure is non-accidentally incompatible with Common Lisp, which makes code portability difficult. But for new code, no one seems deterred, as it is way over 10x more popular than Common Lisp and Scheme. (Differences between Clojure and other Lisps)

Implementing a Lisp in a language without an underlying garbage collector (GC) can be a fun exercise, but it’s not one I’d use for projects. For a GC to be 100% reliable, it is critical to maintain the integrity of the heap (dynamically allocated memory) at all times, and if multi-threading is allowed, care needs to taken as to when the GC is allowed to reclaim storage space (e.g. between any two instructions?)

It is not impossible to implement Lisp in C, and indeed it’s been done, but you often find that C’s calling conventions and relaxed approach to memory management get in the way of building the Lisp you were dreaming of. And if you want tail recursion (one of Scheme’s must-haves) you’re going to have to be super-clever. Lastly do you want compiled code, or will you be satisfied with a slow interpreter?

Where does this leave us? Building a Lisp in assembly language? There are probably more assembly language programmers per capita in this forum than than most others. OR The approach that I highly recommend: to implement a virtual machine (e.g. byte code interpreter) and target your compiled Lisp code to that. This solves many many problems including heap integrity, garbage collection, and tail recursion. And, for small embedded systems and the retro world, a VM approach can do a wonderful job of code compression. The very first Intel 4004 application code was a byte code interpreter (768 bytes including I/O drivers). The entire calculator app itself fit in 256 bytes.

2 Likes

Why not in FORTH? Only a few primitves then need be wiritten in assembly.
I remember reading about LISP cpu’s with LISP in Hardware.Perhaps you can
build your virtual machine, that can translate well to a hardware design. Later
you can build the hardware.
Ben.

See also
Design of LISP-based Processors, or SCHEME: A Dielectric LISP, or Finite Memories Considered Harmful, or LAMBDA: The Ultimate Opcode (Steele and Sussman, 1979, 75 pages)

1 Like

I have a copy of WISP A Self Compiling List Processing Language, by Orgass, Schorr, Waite, and Wilkes, February, 1967. Contains listing of WISP written in WISP. It’s about 110 page document. I’ll take it by UPS Store and see how much they want to scan it and I’ll post it on my Github page. I have an implementation of simcomp written in C at crandylb (Charles Randyl Britten) · GitHub.
In 1965-66 I got to sit in one class with Prof Waite at U Colorado where he talked about WISP. I was completely fascinated but had to drop the class because it conflicted with graduation requirements. Much later I got to meet Wilkes when he gave a talk at U Washington.
The whole adventure with self compiling code has had the most profound effect on my life and career in computer science.
Randyl

4 Likes

That’s excellent @crandylb!

Thanks Ben for the link to this, AI Memo 514. There’s an HN discussion on it which has some good content and links. (“I believe this is about the Lisp Microprocessor that Guy Steele created in Lynn Conway’s groundbreaking 1978 MIT VLSI System Design Course”) Particularly, info on this chip, the SIMPLE processor, which takes up a substantial proportion of the multi-project chip. Images from Lynn Conway’s pages:



1 Like

Forth would make a great target language for Lisp runtime code. You could implement custom “words” (primitives) that handle type-tagged data, memory allocation, etc., so the heap always contains valid objects.when a word has finished executing. (You don’t GC in the middle of the assembly language routines, only at safe preemption points.) Because stack discipline is a free-for-all in Forth, you could even implement tail recursion. Using Forth would be a lot like a byte code interpreter but without the interpreter. You’d trade-off the compactness of byte codes for the speed of threaded code.

1 Like

Internet Archive might appreciate a copy, too.

1 Like

For Forth, the classic book on it, “Starting Forth”, is available for free as PDF: https://www.forth.com/starting-forth/ as is “Thinking Forth” Forth Books by the Experts - FORTH, Inc

LISP in BCPL would be glorious.

1 Like

Nice idea. The scan turned out pretty good, about 130 pages from originals in various condition. However I had made many pencil anotations back when, some of those are readable, some not. That may spoil the copy for some. It may be a few days before I get it posted.
Randyl

1 Like