8 ms·

Step 1: Make a language high-level enough to build a parser without being a masochist. Step 2: Make a lisp. Step 3: Do it all in lisp. Step 4: Profit. Even

by ORioN63 11y ago

Step 1: Make a language high-level enough to build a parser without being a masochist. Step 2: Make a lisp. Step 3: Do it all in lisp. Step 4: Profit. Even Amber(https://github.com/nineties/amber https://github.com/nineties/amber) and its syntax looks a lot like lisp concept of grammar. But instead of (s expressions) you've got what is very similar to M[expressions] (https://en.wikipedia.org/wiki/M-expression https://en.wikipedia.org/wiki/M-expression). It's amazing what you can with Lisp.

pjmlp 11y ago
Yeah, even operating systems it seems. :)
WildUtah 11y ago
Parsing LISP in assembly isn't even so hard. Without a lot of syntactic symbols, you're just finding whitespace and parens. Even syntactic sugar like ' for quote and , or @ in macros are pretty simple to parse compared to C or -- code gods forbid -- C++. What I'd dread is writing the garbage collector in assembly. Maybe you could rely on reference counting, but that could still be a mess.
- Arelius 11y ago
  > What I'd dread is writing the garbage collector in assembly. Then don't. If you're just building a lisp just so you can bootstrap your lisp compiler in lisp, the free-everything-and-quit should be a good enough GC strategy, and quite quick too.
  - geon 11y ago
    Especially with 16 GiB of ram...
- JoshTriplett 11y ago
  > What I'd dread is writing the garbage collector in assembly. Maybe you could rely on reference counting, but that could still be a mess. You don't have to write the final Lisp in assembly; you write the first Lisp in assembly, and the final Lisp in Lisp.
  - Turing_Machine 11y ago
    Sure. At a naive (but workable) level, you could just use assembly to link all the free space up into one humongoid list at startup, then operate on that using Lisp (either directly, or by having a later stage in the startup transform this rudimentary free list into something more sophisticated).
- fao_ 11y ago
  That only works if you don't have self referential structures though. (Disclaimer: I've never actually used one /or/ seen an example of one being used... (See, those AI Koans do have useful tidbits of knowledge in them!)).
- tom_mellior 11y ago
  > What I'd dread is writing the garbage collector in assembly. There are very simple garbage collectors out there, GC doesn't necessarily mean generational mark-sweep-compact or whatever. Semispace collectors are pretty simple and don't even need a stack: https://en.wikipedia.org/wiki/Cheney%27s_algorithm https://en.wikipedia.org/wiki/Cheney%27s_algorithm
nickpsecurity 11y ago
Yeah, it's kind of a cheat. A real language built in assembler would be headaches and I bet a HLL prototype would be hidden somewhere. HLA might be doable, though, especially if macro's are used diligently for pre-optimization work. Competition has gone down from the 70's and 80's, though. I remember reading a Scheme paper that builds a software interpreter then implements the thing in hardware too. There were also people doing HLL-to-microcode compilers to cheat extra performance out of their chips. These days most projects stop at assembler. I'd love to see people whip out their FPGA's and start trying to outdo 70's-80's era innovation in hardware/software designs maybe for modern languages. One of my concepts collecting dust is the Secure Python Target that merges a capability machine, LISP-like hardware at core for native bytecodes, and compiler from Python to that language. Result could be quite productive, reliable, and secure. Another was a Secure Haskell (or ML/Ocaml) Target. I don't know that kind of stuff as well, though. Python has enough documentation, community, and simplicity (to a degree) that academics could port some of its core to hardware.
- Turing_Machine 11y ago
  "A real language built in assembler would be headaches" Depending on what you consider a "real language", it's not that bad. I did a Forth in 80x86 assembler years ago, and it was reasonably easy and fun. (I did use the BIOS routines for keyboard/screen I/O...they were one character at a time, IIRC).
  - nickpsecurity 11y ago
    It does depend on the definition. I'd disqualify Forth as a real language, too. I've always considered it a cross-platform, macro assembler for an abstract, machine design. Like P-code was but more flexible. It's definitely interesting and useful but doesn't feel like a 3GL or even a full LISP. I'd see it as a bootstrap (firmware) or compilation target (eg BootSafe) of a high-level language. Cool that you assembled one, though. (pun intended)
    - claystu 11y ago
      Forth has an ANSI standard as a programming language. What more do you need? What features does a language require to make it a 3GL?
white-flame 11y ago
Absolutely. Two languages that anybody who wants to truly understand computing, programming languages, and compilers are Lisp and Forth. - Lisp is a fundamental, extensible, simple, unbounded AST system (and brings in interesting lambda calculus). - Forth is a fundamental, extensible, simple, unbounded expression evaluator. From there, the world is yours. (Note I use "simple" in Rich Hickey's sense of simple vs easy)

by ORioN63 11y ago

pjmlp 11y ago

Yeah, even operating systems it seems. :)

WildUtah 11y ago

Parsing LISP in assembly isn't even so hard. Without a lot of syntactic symbols, you're just finding whitespace and parens. Even syntactic sugar like ' for quote and , or @ in macros are pretty simple to parse compared to C or -- code gods forbid -- C++. What I'd dread is writing the garbage collector in assembly. Maybe you could rely on reference counting, but that could still be a mess.

Arelius 11y ago
> What I'd dread is writing the garbage collector in assembly. Then don't. If you're just building a lisp just so you can bootstrap your lisp compiler in lisp, the free-everything-and-quit should be a good enough GC strategy, and quite quick too.
- geon 11y ago
  Especially with 16 GiB of ram...
JoshTriplett 11y ago
> What I'd dread is writing the garbage collector in assembly. Maybe you could rely on reference counting, but that could still be a mess. You don't have to write the final Lisp in assembly; you write the first Lisp in assembly, and the final Lisp in Lisp.
- Turing_Machine 11y ago
  Sure. At a naive (but workable) level, you could just use assembly to link all the free space up into one humongoid list at startup, then operate on that using Lisp (either directly, or by having a later stage in the startup transform this rudimentary free list into something more sophisticated).
fao_ 11y ago
That only works if you don't have self referential structures though. (Disclaimer: I've never actually used one /or/ seen an example of one being used... (See, those AI Koans do have useful tidbits of knowledge in them!)).
tom_mellior 11y ago
> What I'd dread is writing the garbage collector in assembly. There are very simple garbage collectors out there, GC doesn't necessarily mean generational mark-sweep-compact or whatever. Semispace collectors are pretty simple and don't even need a stack: https://en.wikipedia.org/wiki/Cheney%27s_algorithm https://en.wikipedia.org/wiki/Cheney%27s_algorithm

nickpsecurity 11y ago

Yeah, it's kind of a cheat. A real language built in assembler would be headaches and I bet a HLL prototype would be hidden somewhere. HLA might be doable, though, especially if macro's are used diligently for pre-optimization work. Competition has gone down from the 70's and 80's, though. I remember reading a Scheme paper that builds a software interpreter then implements the thing in hardware too. There were also people doing HLL-to-microcode compilers to cheat extra performance out of their chips. These days most projects stop at assembler. I'd love to see people whip out their FPGA's and start trying to outdo 70's-80's era innovation in hardware/software designs maybe for modern languages. One of my concepts collecting dust is the Secure Python Target that merges a capability machine, LISP-like hardware at core for native bytecodes, and compiler from Python to that language. Result could be quite productive, reliable, and secure. Another was a Secure Haskell (or ML/Ocaml) Target. I don't know that kind of stuff as well, though. Python has enough documentation, community, and simplicity (to a degree) that academics could port some of its core to hardware.

Turing_Machine 11y ago
"A real language built in assembler would be headaches" Depending on what you consider a "real language", it's not that bad. I did a Forth in 80x86 assembler years ago, and it was reasonably easy and fun. (I did use the BIOS routines for keyboard/screen I/O...they were one character at a time, IIRC).
- nickpsecurity 11y ago
  It does depend on the definition. I'd disqualify Forth as a real language, too. I've always considered it a cross-platform, macro assembler for an abstract, machine design. Like P-code was but more flexible. It's definitely interesting and useful but doesn't feel like a 3GL or even a full LISP. I'd see it as a bootstrap (firmware) or compilation target (eg BootSafe) of a high-level language. Cool that you assembled one, though. (pun intended)
  - claystu 11y ago
    Forth has an ANSI standard as a programming language. What more do you need? What features does a language require to make it a 3GL?

white-flame 11y ago

Absolutely. Two languages that anybody who wants to truly understand computing, programming languages, and compilers are Lisp and Forth. - Lisp is a fundamental, extensible, simple, unbounded AST system (and brings in interesting lambda calculus). - Forth is a fundamental, extensible, simple, unbounded expression evaluator. From there, the world is yours. (Note I use "simple" in Rich Hickey's sense of simple vs easy)