4 ms·

The difference is that Forth compilers can be bootstrapped from not-very-much assembler on an embedded system. That's not really true for Lisp and Smalltalk. Fo

The difference is that Forth compilers can be bootstrapped from not-very-much assembler on an embedded system. That's not really true for Lisp and Smalltalk. Forth impresses me because of the degree of leverage that bootstrapping process affords for small computers.

Pet_Ant 6y ago
Forth is sort of live image like Smalltalk, and great for designing languages/DSLs in like Lisp which is also homoiconic.
lhorie 6y ago
> Forth compilers can be bootstrapped from not-very-much assembler Do you have any resources handy on how one could do that from scratch?
- naters 6y ago
  Jonesforth [1] is a classic example of this, and a really good example of “literate” code. [1] https://github.com/nornagon/jonesforth/blob/master/jonesforth.S https://github.com/nornagon/jonesforth/blob/master/jonesfort...
- benhoyt 6y ago
  A good learning resource is Jonesforth (something of a classic), on GitHub here: https://github.com/nornagon/jonesforth/blob/master/jonesforth.S https://github.com/nornagon/jonesforth/blob/master/jonesfort... I wrote several Forth compilers when learning to code as a teenager, one using the A86 assembler, and two fully bootstrapped-from-assembler ones for 8086 and 386. The 8086 source code is here (I didn't write the assembler myself): https://github.com/benhoyt/third https://github.com/benhoyt/third (KERNEL.F has the assembler parts)
  - ampdepolymerase 6y ago
    There is also https://github.com/kragen/stoneknifeforth https://github.com/kragen/stoneknifeforth
    - transfire 6y ago
      Nice find. Thanks.
- tailrecursion 6y ago
  You requested from scratch, but also look into "metacompilation", which was typically how it was done.
- dreamcompiler 6y ago
  I did this for the TMS34010 graphics processor many years ago but my notes are long gone. I was inspired by Mach 2 Forth, an amazing compiler for the early Mac. My compiler had local variables and tail call detection to take advantage of a special "one-deep" stack register on the chip. The key point is that Forth can easily incorporate an RPN assembler which you can write in Forth, and with which you can then build a better Forth. I'm not sure if I even started with the official TI assembler for the chip; I probably first wrote a cross assembler in Mach 2 by transcribing the ISA manual and bootstrapped from that.
slaymaker1907 6y ago
I think that very much depends on the Lisp in question. Even if you want a Scheme style Lisp which really needs some form of GC, you can implement a very rudimentary one using bump allocation. Basically just allocate memory by bumping the stack pointer and clear out everything at specific boundaries (i.e. you have some memory that is fixed at startup with the interpreter, basic functions, and constants but after that have well defined points where you clear out everything). If you want something closer to assembly, you can just use a normal Lisp and have the Lisp compile itself to an assembly program, but with the benefit of things like variable names whatever other abstractions you can come up with. This approach is taken by Fairlylog[1] which is implemented in Racket but produces Verilog. You are basically writing a new language which compiles to assembly, but with the benefit of better tooling. Racket gives you the benefit of things like syntax-parse for writing the parser in a way that gives good error messages and more flexibility than a parser generator. [1]: https://pkgs.racket-lang.org/package/Fairylog https://pkgs.racket-lang.org/package/Fairylog
- MaxBarraclough 6y ago
  > just allocate memory by bumping the stack pointer and clear out everything at specific boundaries You've described region-based memory management, also known as arena allocation. [0] This can indeed work nicely in short-lived applications like missile-guidance and even serious compilers. [1] It's not real garbage collection though. [0] https://en.wikipedia.org/wiki/Region-based_memory_management https://en.wikipedia.org/wiki/Region-based_memory_management [1] https://web.archive.org/web/20190126213344/https://www.drdobbs.com/cpp/increasing-compiler-speed-by-over-75/240158941 https://web.archive.org/web/20190126213344/https://www.drdob...
pjmlp 6y ago
Lisp surely can and has been. Basically start with a s-exp based Assembler, add a macro support subset and go from there.
- guerrilla 6y ago
  I'd like to see that or maybe try it myself but that's not quite the same as Forth fitting in a 512 byte boot sector[1] or on a tinyAVR. I bet it can be done but I suspect it'd require more cleverness than doing the same with Forth. 1. https://news.ycombinator.com/item?id=24604457 https://news.ycombinator.com/item?id=24604457
  - pjmlp 6y ago
    People tend to forget that Lisp was originally developed on an IBM 704, written in Assembly, with the traditional size a 1950 machine filling a server room was capable of, which was just a few KB. While not the same thing, you can have a look at http://www.ulisp.com/ http://www.ulisp.com/ for AVR.
    - dreamcompiler 6y ago
      All the original compilers like Lisp and Fortran were written in assembler. But that doesn't mean it was easy, or that the resulting language was very capable by modern standards. The thing about Forth is that it is easy, and you get a full-featured Forth when you're done. That's not to say it can't be done in Lisp but Lisp needs a lot more runtime support than Forth. If I was going to bootstrap a Lisp, I'd bootstrap a Forth first and then write the garbage collector for Lisp in Forth.
      - kazinator 6y ago
        Writing primitives like cons, car and cdr in assembler, a garbage collector in assembler, and eval in assembler would make a great amount of sense, from a performance and bootstrapping POV. A Lisp compiler in assembler is just about rationally unjustifiable, though.
moonchild 6y ago
> Forth compilers can be bootstrapped from not-very-much assembler on an embedded system. That's not really true for Lisp and Smalltalk Sectorlisp[0] is an attempt to make a lisp that can fit in a bootsector (512 bytes). It's currently ~1.5 bootsectors; larger than the smallest forths, but certainly in the same ballpark. Stage0[1] is an attempt to make a boostrappable seed from a minimum of binary dependencies. I recommend taking a look at what it says[2] on the matter, though it's too long to quote here. 0. https://github.com/jart/sectorlisp https://github.com/jart/sectorlisp 1. https://savannah.nongnu.org/projects/stage0/ https://savannah.nongnu.org/projects/stage0/ 2. https://git.savannah.nongnu.org/cgit/stage0.git/tree/README.org https://git.savannah.nongnu.org/cgit/stage0.git/tree/README.... skip to ‘stage2’

Pet_Ant 6y ago

Forth is sort of live image like Smalltalk, and great for designing languages/DSLs in like Lisp which is also homoiconic.

lhorie 6y ago

> Forth compilers can be bootstrapped from not-very-much assembler Do you have any resources handy on how one could do that from scratch?

naters 6y ago
Jonesforth [1] is a classic example of this, and a really good example of “literate” code. [1] https://github.com/nornagon/jonesforth/blob/master/jonesforth.S https://github.com/nornagon/jonesforth/blob/master/jonesfort...
benhoyt 6y ago
A good learning resource is Jonesforth (something of a classic), on GitHub here: https://github.com/nornagon/jonesforth/blob/master/jonesforth.S https://github.com/nornagon/jonesforth/blob/master/jonesfort... I wrote several Forth compilers when learning to code as a teenager, one using the A86 assembler, and two fully bootstrapped-from-assembler ones for 8086 and 386. The 8086 source code is here (I didn't write the assembler myself): https://github.com/benhoyt/third https://github.com/benhoyt/third (KERNEL.F has the assembler parts)
- ampdepolymerase 6y ago
  There is also https://github.com/kragen/stoneknifeforth https://github.com/kragen/stoneknifeforth
  - transfire 6y ago
    Nice find. Thanks.
tailrecursion 6y ago
You requested from scratch, but also look into "metacompilation", which was typically how it was done.
dreamcompiler 6y ago
I did this for the TMS34010 graphics processor many years ago but my notes are long gone. I was inspired by Mach 2 Forth, an amazing compiler for the early Mac. My compiler had local variables and tail call detection to take advantage of a special "one-deep" stack register on the chip. The key point is that Forth can easily incorporate an RPN assembler which you can write in Forth, and with which you can then build a better Forth. I'm not sure if I even started with the official TI assembler for the chip; I probably first wrote a cross assembler in Mach 2 by transcribing the ISA manual and bootstrapped from that.

slaymaker1907 6y ago

I think that very much depends on the Lisp in question. Even if you want a Scheme style Lisp which really needs some form of GC, you can implement a very rudimentary one using bump allocation. Basically just allocate memory by bumping the stack pointer and clear out everything at specific boundaries (i.e. you have some memory that is fixed at startup with the interpreter, basic functions, and constants but after that have well defined points where you clear out everything). If you want something closer to assembly, you can just use a normal Lisp and have the Lisp compile itself to an assembly program, but with the benefit of things like variable names whatever other abstractions you can come up with. This approach is taken by Fairlylog[1] which is implemented in Racket but produces Verilog. You are basically writing a new language which compiles to assembly, but with the benefit of better tooling. Racket gives you the benefit of things like syntax-parse for writing the parser in a way that gives good error messages and more flexibility than a parser generator. [1]: https://pkgs.racket-lang.org/package/Fairylog https://pkgs.racket-lang.org/package/Fairylog

MaxBarraclough 6y ago
> just allocate memory by bumping the stack pointer and clear out everything at specific boundaries You've described region-based memory management, also known as arena allocation. [0] This can indeed work nicely in short-lived applications like missile-guidance and even serious compilers. [1] It's not real garbage collection though. [0] https://en.wikipedia.org/wiki/Region-based_memory_management https://en.wikipedia.org/wiki/Region-based_memory_management [1] https://web.archive.org/web/20190126213344/https://www.drdobbs.com/cpp/increasing-compiler-speed-by-over-75/240158941 https://web.archive.org/web/20190126213344/https://www.drdob...

pjmlp 6y ago

Lisp surely can and has been. Basically start with a s-exp based Assembler, add a macro support subset and go from there.

guerrilla 6y ago
I'd like to see that or maybe try it myself but that's not quite the same as Forth fitting in a 512 byte boot sector[1] or on a tinyAVR. I bet it can be done but I suspect it'd require more cleverness than doing the same with Forth. 1. https://news.ycombinator.com/item?id=24604457 https://news.ycombinator.com/item?id=24604457
- pjmlp 6y ago
  People tend to forget that Lisp was originally developed on an IBM 704, written in Assembly, with the traditional size a 1950 machine filling a server room was capable of, which was just a few KB. While not the same thing, you can have a look at http://www.ulisp.com/ http://www.ulisp.com/ for AVR.
  - dreamcompiler 6y ago
    All the original compilers like Lisp and Fortran were written in assembler. But that doesn't mean it was easy, or that the resulting language was very capable by modern standards. The thing about Forth is that it is easy, and you get a full-featured Forth when you're done. That's not to say it can't be done in Lisp but Lisp needs a lot more runtime support than Forth. If I was going to bootstrap a Lisp, I'd bootstrap a Forth first and then write the garbage collector for Lisp in Forth.
    - kazinator 6y ago
      Writing primitives like cons, car and cdr in assembler, a garbage collector in assembler, and eval in assembler would make a great amount of sense, from a performance and bootstrapping POV. A Lisp compiler in assembler is just about rationally unjustifiable, though.

moonchild 6y ago

> Forth compilers can be bootstrapped from not-very-much assembler on an embedded system. That's not really true for Lisp and Smalltalk Sectorlisp[0] is an attempt to make a lisp that can fit in a bootsector (512 bytes). It's currently ~1.5 bootsectors; larger than the smallest forths, but certainly in the same ballpark. Stage0[1] is an attempt to make a boostrappable seed from a minimum of binary dependencies. I recommend taking a look at what it says[2] on the matter, though it's too long to quote here. 0. https://github.com/jart/sectorlisp https://github.com/jart/sectorlisp 1. https://savannah.nongnu.org/projects/stage0/ https://savannah.nongnu.org/projects/stage0/ 2. https://git.savannah.nongnu.org/cgit/stage0.git/tree/README.org https://git.savannah.nongnu.org/cgit/stage0.git/tree/README.... skip to ‘stage2’