[HN Gopher] (How to Write a (Lisp) Interpreter (In Python)) (2010)
___________________________________________________________________
(How to Write a (Lisp) Interpreter (In Python)) (2010)
Author : selvan
Score : 167 points
Date : 2024-03-11 08:47 UTC (14 hours ago)
(HTM) web link (www.norvig.com)
(TXT) w3m dump (www.norvig.com)
| cjfd wrote:
| 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.
| lisper wrote:
| A lisp-y language with closures in 137 lines of Python:
|
| https://flownet.com/ron/lisp/l.py
| kingkongjaffa wrote:
| > 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 wrote:
| 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/b...>
|
| **: <https://gustavus.edu/academics/departments/mathematics-
| compu...>
|
| ***: <https://www.billhails.net/Book/front.html>
| p4bl0 wrote:
| You could start with The Roots of Lisp, by pg:
| 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 wrote:
| 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
| tromp wrote:
| > 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
|
| [2] https://crypto.stanford.edu/~blynn/compiler/
| pjmlp wrote:
| You can try to implement your own Scheme like this,
|
| "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.
| myth_drannon wrote:
| I find System Crafters[1] YouTube channel a great learning
| resource for everything Scheme, Lisp and Emacs
|
| 1. https://www.youtube.com/@SystemCrafters
| JonChesterfield wrote:
| 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 wrote:
| > 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/86b3184f852f65bfb814e3ab098
| 7d8...
| whiterknight wrote:
| SICP
| iainctduncan wrote:
| 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
| sylware wrote:
| 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 wrote:
| 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
| sylware wrote:
| 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.
| marcpaq wrote:
| If you mean "Lisp" interpreter, then I also did something
| that's kinda what you're describing:
|
| https://github.com/marcpaq/arpilisp
| stevekemp wrote:
| If you enjoyed this, as members of hacker news tend to do, then
| you might enjoy the followup piece:
|
| https://norvig.com/lispy2.html
|
| The followup expands the original to make it both more
| complicated and more complete.
| okaleniuk wrote:
| Or you can just from fakelisp import *
|
| And turn your Python into a Lisp.
|
| https://github.com/akalenuk/fakelisp
| Zambyte wrote:
| 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
| okaleniuk wrote:
| Ah, yes! Fakelisp page references Hylang too, although with a
| broken link.
| bitwize wrote:
| Calysto Scheme would like a word:
| https://github.com/Calysto/calysto_scheme
|
| Hy is pretty much Lisp-like syntactic sugar over Python
| semantics. Calysto is a full scheme implementation.
| zerojames wrote:
| This is fun!
| selimthegrim wrote:
| If only importing fakedang turned my site into HN
| exchemist wrote:
| I think this "lisp as a python one-liner" has come up before:
|
| 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).
| samsquire wrote:
| 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 wrote:
| 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
|
| 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.
| remexre wrote:
| Have you seen/considered the work on staged programming?
| Something like [0], while thorny, seems like a reasonable
| stab at it.
|
| [0]: https://okmij.org/ftp/tagless-
| final/TaglessStaged/beyond-tal...
| Y_Y wrote:
| I think a lot of confusion come from the fact that a lot of
| people (including, presumably, the parent) use "Lisp" to mean
| Common Lisp, whereas many others take it to mean what Common
| Lisp people might call "lisp" or lisp-family. You can easily
| have a substanceless argument this way, and many often do!
| llm_trw wrote:
| There is no member of the lisp family that treats quotation
| as a first class citizen of the language. Granted, lisp is
| one of the few language families where it's even a part of
| the language but it's at best an afterthought, which is why
| you need macros to manipulate unquoted expressions.
| kazinator wrote:
| What is the requirement defining "first class quotation"?
|
| 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"?
| JonChesterfield wrote:
| Lots of term rewriting found in compilers. Usually based on
| pattern matching on trees followed by some guard function to
| deal with DAGs / graphs. Lisp/scheme don't have pattern
| matching in the core - possibly because it's much cleaner with
| a static type system doing some of the dispatch - but you can
| implement one or use one of the libraries.
|
| 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.
| abecedarius wrote:
| A kind of aspect-oriented programming?
| CyberDildonics wrote:
| _Truly futuristic programming where we we program behaviours._
|
| Lisp is 66 years old, I think its impact on computer science
| has already happened.
| bitwize wrote:
| Lisp is _eldritch_ by programming language standards; we are
| still wrestling with the ramifications of McCarthy 's half-
| page of code.
| CyberDildonics wrote:
| You think lisp is "weird and sinister or ghostly" and that
| 'we' are still wrestling with something 66 years later?
|
| 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.
| tmtvl wrote:
| Ah yes, all of the modern practical languages allow you
| to connect to a running system, redefine a class, and
| automatically update every existing instance of that
| class.
| floren wrote:
| > This sounds more like someone getting caught up in the
| pageantry of a niche that pragmatic people have left
| behind a long time ago.
|
| And once you notice it once, you start noticing it
| everywhere.
| wtetzner wrote:
| > those advancement have made their way into practical
| languages
|
| 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.
| kryptiskt wrote:
| Scheme has pioneered a lot of stuff over the last 30-40
| years that is still fresh for most of the PL world,
| hygienic macros (like Rust is trying to implement),
| delimited continuations (which underlies Java's new
| virtual threads, see
| https://www.youtube.com/watch?v=9vupFNsND6o), efficient
| closure representations (used all over the place since
| everybody got lambda fever). Into formal verification?
| Scheme was there in 1995
| https://www.semanticscholar.org/paper/VLISP%3A-A-
| verified-im...
|
| 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.
| kazinator wrote:
| StackOverflow answer [January 2024], using term rewriting:
|
| https://stackoverflow.com/a/77857873/1250772
| pjmlp wrote:
| 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
| housecarpenter wrote:
| > (1) there is very little compile-time error analysis and type
| declaration
|
| There's been a lot of improvement on that front.
| vindarel wrote:
| 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/) (and
| SBCL itself evolves)
| housecarpenter wrote:
| 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.
| llm_trw wrote:
| It's pretty much impossible to explain to people what it's
| like to work in a CL environment.
|
| A good presentation on what we're missing:
| https://www.youtube.com/watch?v=8Ab3ArE8W3s
| zarathustreal wrote:
| If you're part of the group missing something, how would
| you know?
| llm_trw wrote:
| I use python/C for my day job and common lisp for my
| wacky off the clock hacking.
|
| I used to use scheme and racket but the joy of debugging
| in CL is worth putting up with two (or four) name spaces.
| Kototama wrote:
| Curiosity beyond your own tools
| djtriptych wrote:
| 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
|
| [1]:
| https://github.com/djtriptych/es6-lisp/blob/master/test/lisp...
| actionfromafar wrote:
| It's a fun thing to try, since Javascript almost was to be a
| Lisp at inception!
| djtriptych wrote:
| 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 wrote:
| 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 wrote:
| Every time I'm reminded of that I get annoyed thinking of
| how much better the web could have been.
| matheusmoreira wrote:
| 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 wrote:
| If you are interested in less conventional implementations of
| Lisp, Shinichiro Hamaji has done a few:
|
| sed: https://github.com/shinh/sedlisp
|
| make: https://github.com/shinh/makelisp
|
| befunge: https://github.com/shinh/beflisp
|
| brainfuck: https://github.com/shinh/bflisp
| mapreduce wrote:
| 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 wrote:
| Maybe carp or bone-lisp?
| Zambyte wrote:
| There is PreScheme[0]
|
| [0] https://groups.scheme.org/prescheme/1.3/
| ignoreusernames wrote:
| You can use a regular common lisp distribution like SBCL and
| just stick to 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 wrote:
| 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
| sema4hacker wrote:
| If it exists, it's probably among the ones listed at
| https://www.softwarepreservation.org/projects/LISP/
|
| If it doesn't exist, you could try modifying one of the listed
| implementations.
| whartung wrote:
| I bet you could go quite far writing a straightforward compiler
| using an S-expr syntax.
|
| 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.
| paddy_m wrote:
| 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/jlis...
| Jun8 wrote:
| 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.
| westmeal wrote:
| I was also extremely upset that the whole expression wasn't
| wrapped in parens
| qubit0ne wrote:
| Inspired by Norvig's article. A Lisp Interpreter in Rust.
|
| https://github.com/vishpat/lisp-rs
___________________________________________________________________
(page generated 2024-03-11 23:00 UTC)