12 ms·

The First Lisp Compiler

208 points by texdraft 4y ago

pjmlp 4y ago
Note the date (1961), and the target hardware (IBM 7090 series), when considering whatever came after and existing hardware capabilities.
- aidenn0 4y ago
  Funny enough I was talking with someone who wanted to make a lisp run on a very small ARM SoC and we discovered that the 7090 Lisp 1.5 was developed on likely had more core+drum than the SoC had ram.
  - pjmlp 4y ago
    Not even uLisp? That looks like a PIC like CPU to me.
    - deleted 4y ago
      [deleted]
    - aidenn0 4y ago
      This might have been before uLisp (definitely prior to my knowledge of uLisp), and they wanted to write the interpreter for it themselves. IIRC it had 16k of RAM, so it definitely could have run uLisp. [edit] I should also point out that just storing the names of all of the symbols in the common lisp specification exceeds the RAM requirements of uLisp. Obviously builtins can go in ROM, but it gives you an idea of the sizes involved.
      - pjmlp 4y ago
        I see, thanks for the overview.
    - exdsq 4y ago
      uLisp was too large for a small flight computer I made for a hobbyist rocket - I wanted to use it but had such little RAM I had to go down to C. I think I could have ran lisp-to-c to generate from uLisp which I’ll try on my next project.
      - pjmlp 4y ago
        In such contexts it is more like an Assembly with a C like macro processor than proper ANSI C anyway, and if you go the code generation route, then you would be better off using the DSL capabilites from Lisp to generate Assembly directly.
  - deleted 4y ago
    [deleted]
  - bsder 4y ago
    People really underestimate how much RAM a Lisp/Scheme needs. Building lists out of pairs and then using them as your intermediate format creates a lot of garbage.
    - kazinator 4y ago
      The RAM usage is tied to the size of the reachable set, plus some slack filled with garbage that depends on how you tune the garbage collection thresholds. By today's standards, the RAM usage isn't necessarily huge. Here is the TXR Lisp compiler recompiling stdlib/compiler.tl -> stdlib/compiler.tlo, as seen in top: PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND 11488 kaz 20 0 17800 14804 2964 R 98.1 0.7 0:07.07 txr ^^^^^ ^^^^^ On the order of a bash session. It's a lot of RAM by 1982 standards at the institution level, and even 1992 standards at the consumer level, but today it means nothing. You can easily see a Bash process a footprint on that order. It could be reduced by tuning the garbage collector. One way to do that is to build for less memory use (useful for embedded). Here it is with txr rebuilt using #define CONFIG_SMALL_MEM 1 in config.h: PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND 12838 kaz 20 0 11964 9768 3140 R 99.0 0.5 0:10.39 txr Bash footprints for comparison: $ ps aux | head -1 ; ps aux | grep bash USER PID %CPU %MEM VSZ RSS TTY STAT START TIME COMMAND kaz 1093 0.0 0.1 9288 2132 pts/2 Ss+ May15 0:01 -bash kaz 2833 0.0 0.0 8904 1992 pts/0 Ss May15 0:00 -bash kaz 3509 0.0 0.2 10532 4988 pts/1 Ss+ May15 0:28 -bash kaz 7898 0.0 0.1 8968 2212 pts/3 Ss+ May20 0:00 -bash Lists are used for everything: the compiler produces a list-based assembly code which is used from then through assembly. There is an optimizer which divides it into basic blocks, which are objects put into a graph, but the instructions still being lists. The peephole pattern matching is done on lists. The compiler does not bother using destructive append (nconc) for stitching together fragments of code; just straight garbage-generating appends. Same with most of the other rewriting that happens later. In a computer in 1960, your compiler would be capped to the physical memory available. That would be the RAM use. The garbage collector would have to be called whenever the memory is exhausted, or else the show would stop. A successful compilation would demonstrate that the compiler needed no more memory than what the machine has. The closer its actual usage would be to the available memory, the longer it would take, due to the frequent garbage collections required to stay afloat. I'd say that given people's expectations today, shaped by experiences with everyday software, they likely greatly overestimate how much RAM you need for Lisp compiling.
dmux 4y ago
> In LISP 1.5, function definitions were stored on the property list of the function's name... The fact that this was once the norm but has since been done away with saddens me. I've always been fascinated with "live environments" but felt they only went half way if they didn't include the source code itself. If I'm going to be updating something in a running system, I want to know what source code was used to get the system to the state its currently in, and preferably be able to query that source code as data. Of course, that code could be kept within source control, but then it's a shadow of the running system -- a map of the territory and not the territory. As far as I know, the only languages/environments where this functionality is still available are Tcl, Smalltalk, and to some extent stored procedures within an RDBMS.
- rscho 4y ago
  Doesn't SBCL have this functionality?
  - uticus 4y ago
    The DOCUMENTATION function shows documentation from a function's definition.
- mananaysiempre 4y ago
  This is not the norm in Forth due to the very spartan environments it originated in, but most mature implementations include a pretty comprehensive decompiler as SEE. (Ironically, this is where the Forth claim of having a modular compiler comes apart, because SEE is always monolithic and nonextensible, or at least I haven’t seen it done any other way.)
- lispm 4y ago
  many Lisp systems record the source location and/or the source itself (especially a source level interpreter needs that)
  - dmux 4y ago
    Do you mind enumerating what those systems are? I've only played around with Allegro CL and SBCL myself.
fulafel 4y ago
What does the prog form with parameters do? I only know about progn in CL.
- texdraft 4y ago
  The "classic" prog still exists in Common Lisp. You probably haven't heard of it because it's almost never used. Here is the description in the HyperSpec: http://clhs.lisp.se/Body/m_prog_.htm#prog http://clhs.lisp.se/Body/m_prog_.htm#prog In Common Lisp terms, it's a combination of LET, BLOCK, and TAGBODY.
  - aidenn0 4y ago
    There's also progv which, off the top of my head, is the only thing in the CL standard that lets you establish bindings (dynamic only for obvious reasons) on a non-constant list of symbols.
larsbrinkhoff 4y ago
"Bernard S. Greenburg" It's Greenberg.
- texdraft 4y ago
  Fixed, thanks.
nemoniac 4y ago
Tail call elimination!!! I had no idea that this was in LISP 1.5. If you had asked me, I would have sworn it was Steele, 1977. Wikipedia supports that[1], albeit one might not consider it the most reliable source. So apparently (partial) TCE has been around since at least 1961. In that light, it's baffling that it's not supported more universally. [1] https://en.wikipedia.org/wiki/Tail_call https://en.wikipedia.org/wiki/Tail_call
- pflanze 4y ago
  The OP describes the support in HLC for TCO as limited (only for self-recursion, if I get it right, possibly more limited than that). Steele may still have been first to describe general TCO.
- texdraft 4y ago
  You could edit Wikipedia, citing Hart and Levin's memo introducing the compiler.
- aap_ 4y ago
  Tail call optimization in scheme are automatic. This LISP 1.5 compiler simply recognizes certain patterns and rewrites them. Not quite the same thing but I was surprised as well when I first looked into the code.
armitron 4y ago
It's amazing that the translation to Common Lisp is as minimal as it gets, with the code being pretty much identical. For the folks that insist Clojure is a Lisp, try doing that as an exercise.
- deleted 4y ago
  [deleted]
- pjmlp 4y ago
  It is a Lisp, as much as, Raket is a Scheme.
Existenceblinks 4y ago
Hmm bookmarked. I'm making an structure editor, yeah it never get old! This is quite details and helpful. Lisp and Standard ML are two languages worth learning the basic. Currently I use Webassembly spec as reference for design decision.
mc4ndr3 4y ago
For the love of.... the compiler doesn't need a stupid initialism. Just say "the compiler". There is nothing memorable or disambiguating or intuitive or efficient about initialisms.
- deleted 4y ago
  [deleted]

208 points by texdraft 4y ago

Note the date (1961), and the target hardware (IBM 7090 series), when considering whatever came after and existing hardware capabilities.

aidenn0 4y ago
Funny enough I was talking with someone who wanted to make a lisp run on a very small ARM SoC and we discovered that the 7090 Lisp 1.5 was developed on likely had more core+drum than the SoC had ram.
- pjmlp 4y ago
  Not even uLisp? That looks like a PIC like CPU to me.
  - deleted 4y ago
    [deleted]
  - aidenn0 4y ago
    This might have been before uLisp (definitely prior to my knowledge of uLisp), and they wanted to write the interpreter for it themselves. IIRC it had 16k of RAM, so it definitely could have run uLisp. [edit] I should also point out that just storing the names of all of the symbols in the common lisp specification exceeds the RAM requirements of uLisp. Obviously builtins can go in ROM, but it gives you an idea of the sizes involved.
    - pjmlp 4y ago
      I see, thanks for the overview.
  - exdsq 4y ago
    uLisp was too large for a small flight computer I made for a hobbyist rocket - I wanted to use it but had such little RAM I had to go down to C. I think I could have ran lisp-to-c to generate from uLisp which I’ll try on my next project.
    - pjmlp 4y ago
      In such contexts it is more like an Assembly with a C like macro processor than proper ANSI C anyway, and if you go the code generation route, then you would be better off using the DSL capabilites from Lisp to generate Assembly directly.
- deleted 4y ago
  [deleted]
- bsder 4y ago
  People really underestimate how much RAM a Lisp/Scheme needs. Building lists out of pairs and then using them as your intermediate format creates a lot of garbage.
  - kazinator 4y ago
    The RAM usage is tied to the size of the reachable set, plus some slack filled with garbage that depends on how you tune the garbage collection thresholds. By today's standards, the RAM usage isn't necessarily huge. Here is the TXR Lisp compiler recompiling stdlib/compiler.tl -> stdlib/compiler.tlo, as seen in top: PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND 11488 kaz 20 0 17800 14804 2964 R 98.1 0.7 0:07.07 txr ^^^^^ ^^^^^ On the order of a bash session. It's a lot of RAM by 1982 standards at the institution level, and even 1992 standards at the consumer level, but today it means nothing. You can easily see a Bash process a footprint on that order. It could be reduced by tuning the garbage collector. One way to do that is to build for less memory use (useful for embedded). Here it is with txr rebuilt using #define CONFIG_SMALL_MEM 1 in config.h: PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND 12838 kaz 20 0 11964 9768 3140 R 99.0 0.5 0:10.39 txr Bash footprints for comparison: $ ps aux | head -1 ; ps aux | grep bash USER PID %CPU %MEM VSZ RSS TTY STAT START TIME COMMAND kaz 1093 0.0 0.1 9288 2132 pts/2 Ss+ May15 0:01 -bash kaz 2833 0.0 0.0 8904 1992 pts/0 Ss May15 0:00 -bash kaz 3509 0.0 0.2 10532 4988 pts/1 Ss+ May15 0:28 -bash kaz 7898 0.0 0.1 8968 2212 pts/3 Ss+ May20 0:00 -bash Lists are used for everything: the compiler produces a list-based assembly code which is used from then through assembly. There is an optimizer which divides it into basic blocks, which are objects put into a graph, but the instructions still being lists. The peephole pattern matching is done on lists. The compiler does not bother using destructive append (nconc) for stitching together fragments of code; just straight garbage-generating appends. Same with most of the other rewriting that happens later. In a computer in 1960, your compiler would be capped to the physical memory available. That would be the RAM use. The garbage collector would have to be called whenever the memory is exhausted, or else the show would stop. A successful compilation would demonstrate that the compiler needed no more memory than what the machine has. The closer its actual usage would be to the available memory, the longer it would take, due to the frequent garbage collections required to stay afloat. I'd say that given people's expectations today, shaped by experiences with everyday software, they likely greatly overestimate how much RAM you need for Lisp compiling.

dmux 4y ago

> In LISP 1.5, function definitions were stored on the property list of the function's name... The fact that this was once the norm but has since been done away with saddens me. I've always been fascinated with "live environments" but felt they only went half way if they didn't include the source code itself. If I'm going to be updating something in a running system, I want to know what source code was used to get the system to the state its currently in, and preferably be able to query that source code as data. Of course, that code could be kept within source control, but then it's a shadow of the running system -- a map of the territory and not the territory. As far as I know, the only languages/environments where this functionality is still available are Tcl, Smalltalk, and to some extent stored procedures within an RDBMS.

rscho 4y ago
Doesn't SBCL have this functionality?
- uticus 4y ago
  The DOCUMENTATION function shows documentation from a function's definition.
mananaysiempre 4y ago
This is not the norm in Forth due to the very spartan environments it originated in, but most mature implementations include a pretty comprehensive decompiler as SEE. (Ironically, this is where the Forth claim of having a modular compiler comes apart, because SEE is always monolithic and nonextensible, or at least I haven’t seen it done any other way.)
lispm 4y ago
many Lisp systems record the source location and/or the source itself (especially a source level interpreter needs that)
- dmux 4y ago
  Do you mind enumerating what those systems are? I've only played around with Allegro CL and SBCL myself.

fulafel 4y ago

What does the prog form with parameters do? I only know about progn in CL.

texdraft 4y ago
The "classic" prog still exists in Common Lisp. You probably haven't heard of it because it's almost never used. Here is the description in the HyperSpec: http://clhs.lisp.se/Body/m_prog_.htm#prog http://clhs.lisp.se/Body/m_prog_.htm#prog In Common Lisp terms, it's a combination of LET, BLOCK, and TAGBODY.
- aidenn0 4y ago
  There's also progv which, off the top of my head, is the only thing in the CL standard that lets you establish bindings (dynamic only for obvious reasons) on a non-constant list of symbols.

larsbrinkhoff 4y ago

"Bernard S. Greenburg" It's Greenberg.

texdraft 4y ago
Fixed, thanks.

nemoniac 4y ago

Tail call elimination!!! I had no idea that this was in LISP 1.5. If you had asked me, I would have sworn it was Steele, 1977. Wikipedia supports that[1], albeit one might not consider it the most reliable source. So apparently (partial) TCE has been around since at least 1961. In that light, it's baffling that it's not supported more universally. [1] https://en.wikipedia.org/wiki/Tail_call https://en.wikipedia.org/wiki/Tail_call

pflanze 4y ago
The OP describes the support in HLC for TCO as limited (only for self-recursion, if I get it right, possibly more limited than that). Steele may still have been first to describe general TCO.
texdraft 4y ago
You could edit Wikipedia, citing Hart and Levin's memo introducing the compiler.
aap_ 4y ago
Tail call optimization in scheme are automatic. This LISP 1.5 compiler simply recognizes certain patterns and rewrites them. Not quite the same thing but I was surprised as well when I first looked into the code.

armitron 4y ago

It's amazing that the translation to Common Lisp is as minimal as it gets, with the code being pretty much identical. For the folks that insist Clojure is a Lisp, try doing that as an exercise.

deleted 4y ago
[deleted]
pjmlp 4y ago
It is a Lisp, as much as, Raket is a Scheme.

Existenceblinks 4y ago

Hmm bookmarked. I'm making an structure editor, yeah it never get old! This is quite details and helpful. Lisp and Standard ML are two languages worth learning the basic. Currently I use Webassembly spec as reference for design decision.

mc4ndr3 4y ago

For the love of.... the compiler doesn't need a stupid initialism. Just say "the compiler". There is nothing memorable or disambiguating or intuitive or efficient about initialisms.

deleted 4y ago
[deleted]