(How to Write a (Lisp) Interpreter (In Python)) (2010)
norvig.com
norvig.com
https://norvig.com/lispy2.html
The followup expands the original to make it both more complicated and more complete.
Python might have overtaken Lisp's role in AI, but still needs some catching up in tooling.
"The two main drawbacks of Python from my point of view are (1) there is very little compile-time error analysis and type declaration, even less than Lisp, and (2) execution time is much slower than Lisp, often by a factor of 10 (sometimes by 100 and sometimes by 1). Qualitatively, Python feels about the same speed as interpreted Lisp, but very noticably slower than compiled Lisp. For this reason I wouldn't recommend Python for applications that are (or are likely to become over time) compute intensive (unless you are willing to move the speed bottlenecks into C). But my purpose is oriented towards pedagogy, not production, so this is less of an issue. "
There's been a lot of improvement on that front.
And there's also been improvement, see Coalton for a ML on top of CL. (https://github.com/coalton-lang/coalton/) (and SBCL itself evolves)
A good presentation on what we're missing: https://www.youtube.com/watch?v=8Ab3ArE8W3s
I used to use scheme and racket but the joy of debugging in CL is worth putting up with two (or four) name spaces.
Did you try mypyc?
The compute intensive parts of AI already always happen in CUDA/C++/C.
Julia, Mojo, XLA, Triton,... are picking up speed, and the pressure for a JIT on CPython is increasing from Microsoft and Facebook, exactly because not everything is AI, and not everyone wants to write C++, C to speed up Python.
http://www.chiark.greenend.org.uk/~pcorbett/yvfc.html
The author was a labmate, and the person who introduced me to python. Taking over one of his codebases was rather a formative part of my career. (That particular code was considerably more normal than the one linked above).
https://github.com/paddymul/buckaroo/blob/main/buckaroo/jlis...
The focus was really on writing the cleanest idiomatic es6 I could (at the time :)). Check out the tests to see how far I got [1]
Pretty fun exercise =)
[0]: https://github.com/djtriptych/es6-lisp
[1]: https://github.com/djtriptych/es6-lisp/blob/master/test/lisp...
Always loved that and ashamed I can't remember the original author of the quote.
Not Crockford... Maybe Michael Fogus?
(I looked at Wikipedia for reference and it matches my memory of older sources.)
Is there a learning resource that covers exactly this for those wanting to write software in lisp in 2024?
As "first principle thinkers" in some ways all hackers crave for that "fundamental building blocks approach", a bit like wanting to know how we go from transistors to full computers and every step along the way. Most of us have made peace with accepting the many abstractions because we're slinging highly abstracted mostly python, and javascript code at startups.
So learning Lisp seems like a nice digestible point to start from along the continuum if indeed there's some eloquent way to learn: >only needs 5 keywords and 8 syntactic forms.
and then be off to the races, so to speak.
The style of the Little/Seasoned/Reasoned Schemer is a little different from the other books I highlighted here, but various people have said they really like it, including Guy Steele, so they may be worth a look if the others don't really work for you.
*: <https://mitp-content-server.mit.edu/books/content/sectbyfn/b...>
**: <https://gustavus.edu/academics/departments/mathematics-compu...>
In the same vein, it is also fun to have a look at church-encoding in lambda calculus and to play with it in the language you choose.
Not the most efficient approach but it does work.
This approach can be reasonably efficient for implementing Haskell, as shown in [1] and the much more concise [2].
"An Incremental Approach to Compiler Construction"
http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf
You will get you own compile to native code Scheme compiler, and then take it from there.
Don't care about performance, only the learning experience.
I'm not sure what a syntactic form means here - dot as in dotted pair, nil, quote, quasiquote, parens? Having trouble coming up with 8 distinct syntactic things.
The basis set underlying lisp is something like the lambda calculus with optional delayed evaluation, a product type and some file I/O.
The optimal basis set for computation is either non-unique or not yet discovered as far as I can tell - different people arrive at different combinations.
If one adds a requirement of additively optimal program length as in [1], then Binary Lambda Calculus is a good candidate.
[1] https://gist.github.com/tromp/86b3184f852f65bfb814e3ab0987d8...
So I built my own Lisp machine based on the nand2tetris architecture, with lisp instructions supported on the simulated chip level. I'm currently in the progress of doing a writeup of the project, you can see my attempts here if you are interested: https://deosjr.github.io/
I have an almost working version of a REPL running on the machine now, including garbage collection and parsing Lisp with Lisp and passing the output to an eval function written in assembly (the operating system, if you will).
But all Lisps I've seen have garbage collectors. If I could find a Lisp with manual memory management, I could ditch C++ in favor of that Lisp. Is there one?
If it doesn't exist, you could try modifying one of the listed implementations.
Any by a "compiler" I'm talking doing something simply like taking Pascal, converting it to an s-expr grammar, and going to town.
Scheme can be a simple algol style language. Using s-expr syntax just made your lexer/parser much simpler. And (simple) compilation is really not that hard (just compile it to C for your first crack if you want).
I bet you could get quite far quite quickly.
(defvar *heap* (make-array 1024 :element-type '(unsigned-byte 8)))
There are other ways you could do it - for example (I don't know if this would be efficient):
(defvar *heap* (make-array 0 :element-type '(vector (unsigned-byte 8))
:adjustable t :fill-pointer t))
(defun malloc (bytes)
(let ((result (make-array bytes :element-type '(unsigned-byte 8))))
(vector-push-extend result *heap*)
result))
These methods would not really release memory back to the OS. However, C malloc and free typically do not really free memory back to the OS either. You can easily do something in Common Lisp that's on equal footing with C in that regard.
Edi Weitz in "Common Lisp Recipes" points out that when you're doing something like this you're "pooling" memory, and in effect you're replacing automatic memory management with your own hand-rolled memory manager, and chances are it's not going to be as good as an automatic memory manager. But certainly it's doable.
Python gives you a lot of things for free. Writing the lisp in C is quite the adventure in its own way.
sed: https://github.com/shinh/sedlisp
make: https://github.com/shinh/makelisp
befunge: https://github.com/shinh/beflisp
brainfuck: https://github.com/shinh/bflisp
from fakelisp import *
Hy is pretty much Lisp-like syntactic sugar over Python semantics. Calysto is a full scheme implementation.
I am currently written rv64 assembly for some project, and at the same time I am writting a x86_64 interperter for this rv64 assembly code.
rv64 assembly is the new C.
I would assume any assembly language is worse to program than C
Additionnally, if we are honnest with ourselves for a lot of programs, from a life cycle perspective, coding time of the bulk is actually negligictible. It is not the case with all types of programs though, but for a lot of system programs, this is very true.
And rv64 is supposed to become THE ISA standard. One of the main reasons for C existence is ISA abstraction which is kind of gone here. Of course, I wish risc-v to be a success.
But people write lisps in imperative style rather than definitions of desired behaviour declaratively. I don't think we've sufficiently solved how to define desired behaviour to a computer.
Term rewriting behaviours. What are your thoughts?
I started trying to implement term rewriting into my LISP parser, which is the idea that we can match on trees and transform them, subsume branches or move branches around arbitrarily. You kind of want the matching function and transformation function to be imperative or sometimes like a query.
So use ASTs for behaviour and relationships and imperative LISP macros for transformations and rewriting.
The reason I say this is because I dream of a compositional language where I can create a cell in a spreadsheet and say that it should have these behaviours
import load-balancing
import batching
import backoff
import backpressure
import retries
import durable-execution
import memory-contiguity
import memory-alignment
I am asked to define the terms that these behaviours require.
Scheme is close but quotation isn't thought about nearly enough. It is generally a CS problem as logic systems with quotation are very much an open problem. I think that types have gotten too much attention and quotation way too little.
Macros are basically a way to deal with the fact that neither lisp nor scheme have first class quotation which you can evaluate at leisure. I understand why they've done it for efficiency reason, but I think we should have at least one language that gets quotation right.
https://imps.mcmaster.ca/doc/qe-in-church.pdf
The above paper is the state of the art and the author there is pretty much the only person I know who has been working on the problem long term.
Basically reading all his publications will get you to open research problems of which there are many.
[0]: https://okmij.org/ftp/tagless-final/TaglessStaged/beyond-tal...
Can you imagine a language with such a first-class quoting system?
In support of ways of implementing Scheme hygienic macros, there exists an invention known as syntactic closures. In what ways does a syntactic closure fall short of being a "first class quotation"?
E.g. (let ((a 10)) (eval '(+ a 1)))
Hygienic macros are just a band aid over the fact that quotation isn't a first class citizen in scheme.
(progv '(a) '(10) (eval '(+ a 1))) ;; Common Lisp, TXR Lisp
[1]> (defmacro fcquote (expr) `(lambda () ,expr))
FCQUOTE
[2]> (defun fceval (fcq) (funcall fcq))
FCEVAL
[3]> (fceval (let ((a 10)) (fcquote (+ a 10))))
20
Sure, whatever; what I intended to bring up was the specific way of implementing hygienic macros using syntactic closures. Syntactic closures are a way of quoting code, with context. Hygienic macros don't have to be implemented with syntactic closures.
That author you cited seems to be working on something very similar to syntactic closure. The paper has a lot of references, but very few of them are anything Lisp or Scheme related. Looks like the author is working entirely on his own.
In a work like this, I'd expect syntactic closures to be acknowledged, with a discussion of how the work being presented is different.
The work that I cited has types _and_ quotation as first class abstractions.
It's a bit like asking to explain proof theory in terms of Godel numbers. Sure you can technically do it. You're completely missing the point if you do however.
Declarative programming is roughly that control flow is handled by the language runtime instead of the programmer. That's either some dedicated language (makefile, yacc) or a DSL in some non-declarative language. It's not lisp, but the tablegen programs used by llvm's backend are an interesting example of a concise declarative syntax turning into a load of C++.
I'd say both are examples of things lisp doesn't really do for you. They're more reasonable to implement in a lisp than in most other languages.
Lisp is 66 years old, I think its impact on computer science has already happened.
This sounds more like someone getting caught up in the pageantry of a niche that pragmatic people have left behind a long time ago. Lisp was very influential, but those advancement have made their way into practical languages and lisp has been impractical for many decades at this point.
That isn't the point though. You were saying lisp is some mystical thing and it is 66 years old. Its influence happened decades ago. It isn't about every language having every feature. Pretty much all software is made without lots of the features in lisp because not every tradeoff is worth it. Lisp itself is barely used because it isn't about a check list of features, but pragmatism of an ecosystem, syntax, actual compilation etc are all crucial. Lisp is not a modern tool, it is an influential invention from over half a century ago.
When people are stuck on an airplane, they don't try to watch citizen kane, they want to watch literally anything else. Influential isn't the same as being good by modern standards. People don't want to write lisp and people don't want to use software written in lisp. Sorry for the harsh reality check.
And once you notice it once, you start noticing it everywhere.
I agree with this for the most part, though I've yet to see a non-lisp language support macros as nicely as Scheme's syntax-case.
Also, while Lisp's features have made their way into modern languages, there are very few that contain all of them at the same time.
> those advancement have made their way into practical languages
I disagree with this.
And there is at least half a dozen things in Racket that I wish mainstream languages could get their ass in gear and copy, but no such luck.