9 ms·

(How to Write a (Lisp) Interpreter (In Python)) (2010)

193 points by selvan 3y ago

Abhitaneja89 3y ago
[dead]
cjfd 3y ago
One main thing that one gets for free this way is garbage collection. I once started writing a lisp iterpreter in C++ but that kind of fell by the wayside once I realized that it is quite easy to create cyclical references in lisp and then using shared_ptr is not good enough.
deleted 3y ago
[deleted]
lisper 3y ago
A lisp-y language with closures in 137 lines of Python: https://flownet.com/ron/lisp/l.py https://flownet.com/ron/lisp/l.py
kingkongjaffa 3y ago
> The beauty of Scheme is that the full language only needs 5 keywords and 8 syntactic forms. 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.
- tmtvl 3y ago
  Various Scheme texts cover writing your own interpreter in more or less detail: Structure and Interpretation of Computer Programs (AKA SICP)*, the Little Schemer, Concrete Abstractions**. Norvig's Paradigms of AI Programming also contains a Scheme interpreter, though the text mainly focuses on Common Lisp. And finally I'd throw Exploring Programming Language Architecture in Perl*** in the mix as a more in-depth look at creating a Scheme interpreter. 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/books_pres_0/6515/sicp.zip/index.html https://mitp-content-server.mit.edu/books/content/sectbyfn/b...> **: <https://gustavus.edu/academics/departments/mathematics-computer-science-and-statistics/max/concrete-abstractions.html https://gustavus.edu/academics/departments/mathematics-compu...> ***: <https://www.billhails.net/Book/front.html https://www.billhails.net/Book/front.html>
- p4bl0 3y ago
  You could start with The Roots of Lisp, by pg: https://www.paulgraham.com/rootsoflisp.html https://www.paulgraham.com/rootsoflisp.html 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.
- arethuza 3y ago
  Many years ago I wrote a simple programming language that would macro expand into lambda calculus statement that could then be compiled down to different sets of combinators - the simplest being just S & K, which are pretty fundamental given how simple they are. The fact that you can express things like recursion in the lambda calculate (see name of our hosts on this site) and therefore in combinators still amazes me. Not the most efficient approach but it does work. https://en.wikipedia.org/wiki/SKI_combinator_calculus https://en.wikipedia.org/wiki/SKI_combinator_calculus
  - tromp 3y ago
    > expand into lambda calculus statement that could then be compiled down to different sets of combinators This approach can be reasonably efficient for implementing Haskell, as shown in [1] and the much more concise [2]. [1] https://github.com/augustss/MicroHs https://github.com/augustss/MicroHs [2] https://crypto.stanford.edu/~blynn/compiler/ https://crypto.stanford.edu/~blynn/compiler/
- pjmlp 3y ago
  You can try to implement your own Scheme like this, "An Incremental Approach to Compiler Construction" http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf 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.
- myth_drannon 3y ago
  I find System Crafters[1] YouTube channel a great learning resource for everything Scheme, Lisp and Emacs 1. https://www.youtube.com/@SystemCrafters https://www.youtube.com/@SystemCrafters
- JonChesterfield 3y ago
  I suppose 5 is better than lots but you can totally write a lisp with zero keywords. 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.
  - tromp 3y ago
    > The optimal basis set for computation is either non-unique 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/86b3184f852f65bfb814e3ab0987d861#universality https://gist.github.com/tromp/86b3184f852f65bfb814e3ab0987d8...
- whiterknight 3y ago
  SICP
- iainctduncan 3y ago
  Second edition of Friedman's Essentials of Programming Languages is very good for this. A tough read, but very good. The second edition is written in Scheme, I think the third changed? (I can't recall the details but I know when I was hunting for reading it was recommended to stick to the second as I was specifically looking for Scheme). https://www.librarything.com/work/347168 https://www.librarything.com/work/347168
- deosjr 3y ago
  My way of learning about Lisp was based on first principles, after reading Norvigs blogpost many times and working through SICP. What helped is that I had just finished the nand2tetris book, which is very much a first principles speedrun of how a computer works. 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/ 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).
sylware 3y ago
I would prefer a python interpreter written directly in rv64 assembly with a near 0-SDK. Would run on x86_64 and arm64 with a rv64 interpreter (ofc with some code paths adaptation).
- matheusmoreira 3y ago
  I made a lisp that's somewhat close to what you described. It's a freestanding lisp that targets the Linux kernel directly. No libraries, not even libc. https://github.com/lone-lang/lone https://github.com/lone-lang/lone
  - sylware 3y ago
    The idea would be to write a port in rv64 assembly, and to run it in a x86_64/arm64 interpreter (for legacy support). 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.
    - whitten 3y ago
      Really? I would assume any assembly language is worse to program than C
      - sylware 3y ago
        It is more upfront work for sure. But you get immunity from the planned obsolescence of syntax feature creeps from ISO or gcc extensions (a 5-10 years cycle)... and from compiler implementations. 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.
- marcpaq 3y ago
stevekemp 3y ago
If you enjoyed this, as members of hacker news tend to do, then you might enjoy the followup piece: https://norvig.com/lispy2.html https://norvig.com/lispy2.html The followup expands the original to make it both more complicated and more complete.
okaleniuk 3y ago
Or you can just from fakelisp import * And turn your Python into a Lisp. https://github.com/akalenuk/fakelisp https://github.com/akalenuk/fakelisp
- Zambyte 3y ago
  Not exactly the same (doesn't embed into the source like this did), but I believe Hylang[0] is the best Lisp package available for modern Python. [0] https://github.com/hylang/hy https://github.com/hylang/hy
  - okaleniuk 3y ago
    Ah, yes! Fakelisp page references Hylang too, although with a broken link.
  - bitwize 3y ago
    Calysto Scheme would like a word: https://github.com/Calysto/calysto_scheme https://github.com/Calysto/calysto_scheme Hy is pretty much Lisp-like syntactic sugar over Python semantics. Calysto is a full scheme implementation.
- zerojames 3y ago
  This is fun!
- selimthegrim 3y ago
  If only importing fakedang turned my site into HN
exchemist 3y ago
I think this "lisp as a python one-liner" has come up before: http://www.chiark.greenend.org.uk/~pcorbett/yvfc.html 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).
- randrus 3y ago
  That is truly impressive.
samsquire 3y ago
What I find promising about LISP is the ability to do term rewriting and macros. 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 Truly futuristic programming where we we program behaviours. I am asked to define the terms that these behaviours require.
- llm_trw 3y ago
  Lisp is not the language for that unfortunately, it is very much an imperative language with better syntax and _some_ macros. 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 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.
  - deleted 3y ago
    [deleted]
  - remexre 3y ago
pjmlp 3y ago
Given Peter Norvig's work on Lisp and Python, pity that after 24 years, his "Python for Lisp Programmers" essay from 2000 is still mostly true. 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. " -- https://norvig.com/python-lisp.html https://norvig.com/python-lisp.html
- housecarpenter 3y ago
  > (1) there is very little compile-time error analysis and type declaration There's been a lot of improvement on that front.
  - vindarel 3y ago
    It's still… not the same. In CL (and specially with SBCL), we get compile time (type) errors and warnings at the blink of an eye, when we compile a single function with a keystroke (typically C-c C-c in Slime). And there's also been improvement, see Coalton for a ML on top of CL. (https://github.com/coalton-lang/coalton/ https://github.com/coalton-lang/coalton/) (and SBCL itself evolves)
    - housecarpenter 3y ago
      I haven't used CL myself, but it wouldn't surprise me if CL does a better job. Just pointing out that Python is significantly better in this respect than it used to be. In particular, using VS Code with Pylance, I can see type errors highlighted as soon as I write the code---I don't even need to use a keystroke. 24 years ago, I don't think anything like that was possible; the language didn't even support type annotations.
djtriptych 3y ago
At some point I translated this demo into es6 if anyone's interested [0]. 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 https://github.com/djtriptych/es6-lisp [1]: https://github.com/djtriptych/es6-lisp/blob/master/test/lisp.test.js https://github.com/djtriptych/es6-lisp/blob/master/test/lisp...
- actionfromafar 3y ago
  It's a fun thing to try, since Javascript almost was to be a Lisp at inception!
  - djtriptych 3y ago
    Someone once said Javascript is a "Scheme-like language with C-like syntax". Always loved that and ashamed I can't remember the original author of the quote. Not Crockford... Maybe Michael Fogus?
    - actionfromafar 3y ago
      Not sure, but Brendan Eich originally wanted to just put Scheme in the Netscape browser but his bosses wanted something with a Java like syntax. (I looked at Wikipedia for reference and it matches my memory of older sources.)
      - patrickmay 3y ago
        Every time I'm reminded of that I get annoyed thinking of how much better the web could have been.
    - throwaway87651 3y ago
      Crockford: "Lisp in C's Clothing" https://www.crockford.com/javascript/javascript.html https://www.crockford.com/javascript/javascript.html
  - 3y ago
matheusmoreira 3y ago
This code is really beautiful and makes a lot of hard things easy to understand. I read this article many times before I developed the confidence to do it myself. Python gives you a lot of things for free. Writing the lisp in C is quite the adventure in its own way.
omoikane 3y ago
If you are interested in less conventional implementations of Lisp, Shinichiro Hamaji has done a few: sed: https://github.com/shinh/sedlisp https://github.com/shinh/sedlisp make: https://github.com/shinh/makelisp https://github.com/shinh/makelisp befunge: https://github.com/shinh/beflisp https://github.com/shinh/beflisp brainfuck: https://github.com/shinh/bflisp https://github.com/shinh/bflisp
mapreduce 3y ago
This might sound crazy or stupid but I really want to know if there is some Lisp with manual memory management? I love Lisp syntax. People complain about the parentheses but for me they are a blessing. I like how extremely uniform and regular they look. 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?
- paines 3y ago
  Maybe carp or bone-lisp?
- Zambyte 3y ago
  There is PreScheme[0] [0] https://groups.scheme.org/prescheme/1.3/ https://groups.scheme.org/prescheme/1.3/
- deleted 3y ago
  [deleted]
- ignoreusernames 3y ago
  You can use a regular common lisp distribution like SBCL and just stick to foreign types https://www.sbcl.org/manual/#Foreign-Types https://www.sbcl.org/manual/#Foreign-Types this way you still have a GC for lighter tasks but with the option of manual memory management
  - massysett 3y ago
    You can also use the DYNAMIC-EXTENT declaration to (in general) tell your implementation to stack-allocate a value. http://clhs.lisp.se/Body/d_dynami.htm#dynamic-extent http://clhs.lisp.se/Body/d_dynami.htm#dynamic-extent
- sema4hacker 3y ago
  If it exists, it's probably among the ones listed at https://www.softwarepreservation.org/projects/LISP/ https://www.softwarepreservation.org/projects/LISP/ If it doesn't exist, you could try modifying one of the listed implementations.
paddy_m 3y ago
I used Norvig’s lisp2.py to build a low code UI. I modified the interpreter to accept JSON flavored lisp, basically replace parens with brackets. The upside is that it was very very easy to make a react front end that manipulates JSON (JLisp). My thinking was, I need a serialization format for operations from the front end, and a way to interpret them. I could write my own language that no one has heard of, or use lisp, which few have used. https://github.com/paddymul/buckaroo/blob/main/buckaroo/jlisp/lispy.py https://github.com/paddymul/buckaroo/blob/main/buckaroo/jlis...
Jun8 3y ago
This is one of the very few cases where adding the date in parentheses in the HN submission screws up the title of the post.
- deleted 3y ago
  [deleted]
- westmeal 3y ago
  I was also extremely upset that the whole expression wasn't wrapped in parens
qubit0ne 3y ago
Inspired by Norvig's article. A Lisp Interpreter in Rust. https://github.com/vishpat/lisp-rs https://github.com/vishpat/lisp-rs
jmcdonald007 3y ago
[dead]
cacozen 3y ago
The title alone is already worth an upvote

193 points by selvan 3y ago

[dead]

cjfd 3y ago

One main thing that one gets for free this way is garbage collection. I once started writing a lisp iterpreter in C++ but that kind of fell by the wayside once I realized that it is quite easy to create cyclical references in lisp and then using shared_ptr is not good enough.

deleted 3y ago

[deleted]

lisper 3y ago

A lisp-y language with closures in 137 lines of Python: https://flownet.com/ron/lisp/l.py https://flownet.com/ron/lisp/l.py

kingkongjaffa 3y ago

> The beauty of Scheme is that the full language only needs 5 keywords and 8 syntactic forms. 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.

tmtvl 3y ago
Various Scheme texts cover writing your own interpreter in more or less detail: Structure and Interpretation of Computer Programs (AKA SICP)*, the Little Schemer, Concrete Abstractions**. Norvig's Paradigms of AI Programming also contains a Scheme interpreter, though the text mainly focuses on Common Lisp. And finally I'd throw Exploring Programming Language Architecture in Perl*** in the mix as a more in-depth look at creating a Scheme interpreter. 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/books_pres_0/6515/sicp.zip/index.html https://mitp-content-server.mit.edu/books/content/sectbyfn/b...> **: <https://gustavus.edu/academics/departments/mathematics-computer-science-and-statistics/max/concrete-abstractions.html https://gustavus.edu/academics/departments/mathematics-compu...> ***: <https://www.billhails.net/Book/front.html https://www.billhails.net/Book/front.html>
p4bl0 3y ago
You could start with The Roots of Lisp, by pg: https://www.paulgraham.com/rootsoflisp.html https://www.paulgraham.com/rootsoflisp.html 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.
arethuza 3y ago
Many years ago I wrote a simple programming language that would macro expand into lambda calculus statement that could then be compiled down to different sets of combinators - the simplest being just S & K, which are pretty fundamental given how simple they are. The fact that you can express things like recursion in the lambda calculate (see name of our hosts on this site) and therefore in combinators still amazes me. Not the most efficient approach but it does work. https://en.wikipedia.org/wiki/SKI_combinator_calculus https://en.wikipedia.org/wiki/SKI_combinator_calculus
- tromp 3y ago
  > expand into lambda calculus statement that could then be compiled down to different sets of combinators This approach can be reasonably efficient for implementing Haskell, as shown in [1] and the much more concise [2]. [1] https://github.com/augustss/MicroHs https://github.com/augustss/MicroHs [2] https://crypto.stanford.edu/~blynn/compiler/ https://crypto.stanford.edu/~blynn/compiler/
pjmlp 3y ago
You can try to implement your own Scheme like this, "An Incremental Approach to Compiler Construction" http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf 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.
myth_drannon 3y ago
I find System Crafters[1] YouTube channel a great learning resource for everything Scheme, Lisp and Emacs 1. https://www.youtube.com/@SystemCrafters https://www.youtube.com/@SystemCrafters
JonChesterfield 3y ago
I suppose 5 is better than lots but you can totally write a lisp with zero keywords. 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.
- tromp 3y ago
  > The optimal basis set for computation is either non-unique 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/86b3184f852f65bfb814e3ab0987d861#universality https://gist.github.com/tromp/86b3184f852f65bfb814e3ab0987d8...
whiterknight 3y ago
SICP
iainctduncan 3y ago
Second edition of Friedman's Essentials of Programming Languages is very good for this. A tough read, but very good. The second edition is written in Scheme, I think the third changed? (I can't recall the details but I know when I was hunting for reading it was recommended to stick to the second as I was specifically looking for Scheme). https://www.librarything.com/work/347168 https://www.librarything.com/work/347168
deosjr 3y ago
My way of learning about Lisp was based on first principles, after reading Norvigs blogpost many times and working through SICP. What helped is that I had just finished the nand2tetris book, which is very much a first principles speedrun of how a computer works. 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/ 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).

sylware 3y ago

I would prefer a python interpreter written directly in rv64 assembly with a near 0-SDK. Would run on x86_64 and arm64 with a rv64 interpreter (ofc with some code paths adaptation).

matheusmoreira 3y ago
I made a lisp that's somewhat close to what you described. It's a freestanding lisp that targets the Linux kernel directly. No libraries, not even libc. https://github.com/lone-lang/lone https://github.com/lone-lang/lone
- sylware 3y ago
  The idea would be to write a port in rv64 assembly, and to run it in a x86_64/arm64 interpreter (for legacy support). 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.
  - whitten 3y ago
    Really? I would assume any assembly language is worse to program than C
    - sylware 3y ago
      It is more upfront work for sure. But you get immunity from the planned obsolescence of syntax feature creeps from ISO or gcc extensions (a 5-10 years cycle)... and from compiler implementations. 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.
marcpaq 3y ago

stevekemp 3y ago

If you enjoyed this, as members of hacker news tend to do, then you might enjoy the followup piece: https://norvig.com/lispy2.html https://norvig.com/lispy2.html The followup expands the original to make it both more complicated and more complete.

okaleniuk 3y ago

Or you can just from fakelisp import * And turn your Python into a Lisp. https://github.com/akalenuk/fakelisp https://github.com/akalenuk/fakelisp

Zambyte 3y ago
Not exactly the same (doesn't embed into the source like this did), but I believe Hylang[0] is the best Lisp package available for modern Python. [0] https://github.com/hylang/hy https://github.com/hylang/hy
- okaleniuk 3y ago
  Ah, yes! Fakelisp page references Hylang too, although with a broken link.
- bitwize 3y ago
  Calysto Scheme would like a word: https://github.com/Calysto/calysto_scheme https://github.com/Calysto/calysto_scheme Hy is pretty much Lisp-like syntactic sugar over Python semantics. Calysto is a full scheme implementation.
zerojames 3y ago
This is fun!
selimthegrim 3y ago
If only importing fakedang turned my site into HN

exchemist 3y ago

I think this "lisp as a python one-liner" has come up before: http://www.chiark.greenend.org.uk/~pcorbett/yvfc.html 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).

randrus 3y ago
That is truly impressive.

samsquire 3y ago

What I find promising about LISP is the ability to do term rewriting and macros. 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 Truly futuristic programming where we we program behaviours. I am asked to define the terms that these behaviours require.

llm_trw 3y ago
Lisp is not the language for that unfortunately, it is very much an imperative language with better syntax and _some_ macros. 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 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.
- deleted 3y ago
  [deleted]
- remexre 3y ago

pjmlp 3y ago

Given Peter Norvig's work on Lisp and Python, pity that after 24 years, his "Python for Lisp Programmers" essay from 2000 is still mostly true. 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. " -- https://norvig.com/python-lisp.html https://norvig.com/python-lisp.html

housecarpenter 3y ago
> (1) there is very little compile-time error analysis and type declaration There's been a lot of improvement on that front.
- vindarel 3y ago
  It's still… not the same. In CL (and specially with SBCL), we get compile time (type) errors and warnings at the blink of an eye, when we compile a single function with a keystroke (typically C-c C-c in Slime). And there's also been improvement, see Coalton for a ML on top of CL. (https://github.com/coalton-lang/coalton/ https://github.com/coalton-lang/coalton/) (and SBCL itself evolves)
  - housecarpenter 3y ago
    I haven't used CL myself, but it wouldn't surprise me if CL does a better job. Just pointing out that Python is significantly better in this respect than it used to be. In particular, using VS Code with Pylance, I can see type errors highlighted as soon as I write the code---I don't even need to use a keystroke. 24 years ago, I don't think anything like that was possible; the language didn't even support type annotations.

djtriptych 3y ago

At some point I translated this demo into es6 if anyone's interested [0]. 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 https://github.com/djtriptych/es6-lisp [1]: https://github.com/djtriptych/es6-lisp/blob/master/test/lisp.test.js https://github.com/djtriptych/es6-lisp/blob/master/test/lisp...

actionfromafar 3y ago
It's a fun thing to try, since Javascript almost was to be a Lisp at inception!
- djtriptych 3y ago
  Someone once said Javascript is a "Scheme-like language with C-like syntax". Always loved that and ashamed I can't remember the original author of the quote. Not Crockford... Maybe Michael Fogus?
  - actionfromafar 3y ago
    Not sure, but Brendan Eich originally wanted to just put Scheme in the Netscape browser but his bosses wanted something with a Java like syntax. (I looked at Wikipedia for reference and it matches my memory of older sources.)
    - patrickmay 3y ago
      Every time I'm reminded of that I get annoyed thinking of how much better the web could have been.
  - throwaway87651 3y ago
    Crockford: "Lisp in C's Clothing" https://www.crockford.com/javascript/javascript.html https://www.crockford.com/javascript/javascript.html
- 3y ago

matheusmoreira 3y ago

This code is really beautiful and makes a lot of hard things easy to understand. I read this article many times before I developed the confidence to do it myself. Python gives you a lot of things for free. Writing the lisp in C is quite the adventure in its own way.

omoikane 3y ago

If you are interested in less conventional implementations of Lisp, Shinichiro Hamaji has done a few: sed: https://github.com/shinh/sedlisp https://github.com/shinh/sedlisp make: https://github.com/shinh/makelisp https://github.com/shinh/makelisp befunge: https://github.com/shinh/beflisp https://github.com/shinh/beflisp brainfuck: https://github.com/shinh/bflisp https://github.com/shinh/bflisp

mapreduce 3y ago

This might sound crazy or stupid but I really want to know if there is some Lisp with manual memory management? I love Lisp syntax. People complain about the parentheses but for me they are a blessing. I like how extremely uniform and regular they look. 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?

paines 3y ago
Maybe carp or bone-lisp?
Zambyte 3y ago
There is PreScheme[0] [0] https://groups.scheme.org/prescheme/1.3/ https://groups.scheme.org/prescheme/1.3/
deleted 3y ago
[deleted]
ignoreusernames 3y ago
You can use a regular common lisp distribution like SBCL and just stick to foreign types https://www.sbcl.org/manual/#Foreign-Types https://www.sbcl.org/manual/#Foreign-Types this way you still have a GC for lighter tasks but with the option of manual memory management
- massysett 3y ago
  You can also use the DYNAMIC-EXTENT declaration to (in general) tell your implementation to stack-allocate a value. http://clhs.lisp.se/Body/d_dynami.htm#dynamic-extent http://clhs.lisp.se/Body/d_dynami.htm#dynamic-extent
sema4hacker 3y ago
If it exists, it's probably among the ones listed at https://www.softwarepreservation.org/projects/LISP/ https://www.softwarepreservation.org/projects/LISP/ If it doesn't exist, you could try modifying one of the listed implementations.

paddy_m 3y ago

I used Norvig’s lisp2.py to build a low code UI. I modified the interpreter to accept JSON flavored lisp, basically replace parens with brackets. The upside is that it was very very easy to make a react front end that manipulates JSON (JLisp). My thinking was, I need a serialization format for operations from the front end, and a way to interpret them. I could write my own language that no one has heard of, or use lisp, which few have used. https://github.com/paddymul/buckaroo/blob/main/buckaroo/jlisp/lispy.py https://github.com/paddymul/buckaroo/blob/main/buckaroo/jlis...

Jun8 3y ago

This is one of the very few cases where adding the date in parentheses in the HN submission screws up the title of the post.

deleted 3y ago
[deleted]
westmeal 3y ago
I was also extremely upset that the whole expression wasn't wrapped in parens

qubit0ne 3y ago

Inspired by Norvig's article. A Lisp Interpreter in Rust. https://github.com/vishpat/lisp-rs https://github.com/vishpat/lisp-rs

jmcdonald007 3y ago

[dead]

cacozen 3y ago

The title alone is already worth an upvote