5 ms·

Show HN: A compiler and VM for a simple language, in 150 lines of code

200 points by p4bl0 4y ago

prezjordan 4y ago
Where can I learn more about mll and mly files? I've hand-rolled parsers and it's always my least favorite part of toy languages.
- deleted 4y ago
  [deleted]
- a-dub 4y ago
  https://v2.ocaml.org/manual/lexyacc.html https://v2.ocaml.org/manual/lexyacc.html
- tekknolagi 4y ago
  Search for ocamllex and ocamlyacc. Also Menhir.
  - mftb 4y ago
    So weird, within the last hour I was wondering why I never see regular, old, lex and yacc around anymore, and then I came across this, which made realize it's probably because they generate C. Funny. I guess these output OCaml?
    - p4bl0 4y ago
      Yes, they do. Lex and yacc equivalent tools are available for many languages. Examples : - Python: https://ply.readthedocs.io/ https://ply.readthedocs.io/ (I already used it in a very small project, again for my students, here is an example of how it works: https://gist.github.com/p4bl0-/f5ed1e60fdc5e76a2d321bc8708a7817 https://gist.github.com/p4bl0-/f5ed1e60fdc5e76a2d321bc8708a7...) - Racket: https://docs.racket-lang.org/parser-tools/ https://docs.racket-lang.org/parser-tools/ (it's really great, I previously used Racket for my compiler course but I've switched to OCaml a few years back, because Racket parser tools don't go well with Typed Racket).
userbinator 4y ago
For those wondering what language this is for before clicking on it: it's not much more than what I think would traditionally be called an expression evaluator, and very simple one at that --- it only recognises binary logic expressions, and the 150 lines doesn't include the parser or lexer either. Not a bad attempt for what is presumably a first try, but I think "complete compiler" is overselling it.
- a-dub 4y ago
  there's no type checking, which i'd say is a fairly integral part of a compiler... but it does use a parser generator to generate a parser that constructs an ast and it then iterates that ast to generate a bytecode. that's basically a compiler, even if the language is basic expressions.
  - userbinator 4y ago
    B has no type checking either. On the other hand, using a parser generator and not counting its output in the line count does seem like cheating.
    - p4bl0 4y ago
      > using a parser generator and not counting its output in the line count does seem like cheating Yeah maybe I should count OCaml's standard library lines of code too. Maybe also count expanded macros and inlined functions at each call site? At which point should I stop? Are assembly language pseudo-instructions cheating too? Common, don't be ridiculous.
    - wtetzner 4y ago
      I don’t see how, I would only count the input lines to the parser generator.
  - compiler-guy 4y ago
    Type checking is a part of semantic analysis, which the author explicitly says isn’t present. Even so, the language it is compiling has only one type, so it isn’t possible for a program to have type errors. Just like in C++ one never need to check if a reference is null—it simply can’t be expressed in the language, thus preventing any errors of that kind, a single type prevents all kinds of type errors. One might argue that this is the most powerful way to do type checking. It simply isn’t possible to have an error.
blacklion 4y ago
Sooo nice :-) It looks like small cute kitten to me, sorry.
- p4bl0 4y ago
  Don't be sorry for this nice comment! I totally understand the cuteness feeling ^_^.
- mdp2021 4y ago
  If you like The Arts, and remarkable results, the website of Pablo ( https://pablo.rauzy.name/ https://pablo.rauzy.name/ ) is a thing to behold.
denotational 4y ago
As another comment also alludes, there's probably quite a lot more work required before this could be called a complete compiler (without heavy qualification as to what it actually compiles, since the language of boolean expressions probably isn't something that most people would consider to be a programming language per se); that said, toy languages like this are a great way to explore some fundamental principles of programming language theory. Boolean expressions have very trivial denotational semantics (since there's no recursion or state), so you could try formalising these in Coq (FRAP [1] and Software Foundations Vol. 2 [2] are both good places to learn more about this). Next, you could write formal operational semantics for your VM, and then finally prove that your compiler is correct in a formal sense (i.e. the image of any well-formed input under the compiler operation has a terminating execution in the operational semantics that yields the same value as would be obtained by the execution of the input expression under the denotational semantics). The last part would require implementing the compiler in Coq, but since you've written it in OCaml it probably wouldn't be very hard to port. [1] : https://frap.csail.mit.edu/main https://frap.csail.mit.edu/main [2] : https://softwarefoundations.cis.upenn.edu/plf-current/toc.html https://softwarefoundations.cis.upenn.edu/plf-current/toc.ht... Edit: Having looked at your profile I now realise that you probably know all of this already, but it might be informative for anyone else reading :)
- stepchowfun 4y ago
  Coq is so much fun. It makes writing proofs feel like playing a video game. I've just finished writing a Coq tutorial [1] that is aimed at programmers (rather than, say, computer scientists). It covers topics like programming with dependent types, writing proofs as data, universes & other type theory stuff, and extracting verified code—with exercises. [1] https://github.com/stepchowfun/proofs/tree/main/proofs/Tutorial https://github.com/stepchowfun/proofs/tree/main/proofs/Tutor...
skybrian 4y ago
I think people are getting hung up on the word "complete." This is a complete compiler in the sense that "hello world" is a complete (but minimal) program.
- p4bl0 4y ago
  Yes exactly :), I meant that it does everything from lexing the source code to emitting bytecode instructions (and provides the VM to run this bytecode). It is not a part of a compiler, it is a tiny, simple, stupid, but complete, compiler.
  - kragen 4y ago
    I want to preface this comment with the fact that I'm terrible at teaching and know nothing about it, so it's entirely possible that your example compiler is much better for pedagogical purposes than the ones I'm going to suggest here. But I think they all have a significantly higher "power density", which at least from my point of view makes them more interesting and inspiring. I think mostly people are complaining that the language it compiles isn't a programming language, so it omits a lot of things that compilers for programming languages have to handle. And so it feels a bit like much ado about nothing: because there are no variables, loops, or values beyond single-bit values, the program it compiles can only ever produce a constant, predetermined output, and that output can only ever be 1 or 0. So the compiler is just sort of a particularly awkward and inefficient way to output that 1 or 0. A compiler for Brainf*** or SK-combinators or the untyped λ-calculus would be "more real" in that sense. More practical, and maybe also fitting into 150 lines, might be a language for something like a programmable calculator (untested sketch): program ::= stmt | stmt ";" program. stmt ::= "print" numexpr | variable ":=" numexpr | "while" numexpr comparator numexpr "{" program "}". comparator ::= "<" | ">" | "==" | "!=" | "<=" | ">=". numexpr ::= term | numexpr "+" term | numexpr "-" term. term ::= factor | term "*" factor | term "/" factor | term "%" factor. factor ::= atom | "-" atom | "+" atom | atom "^" factor. atom ::= "(" numexpr ")" | numeric_constant | variable. That's powerful enough to conveniently write, for example, a numerical root finding program for an arbitrary arithmetic expression. Maybe for pedagogical purposes (which, as I said, I am totally ignorant of) it would be useful to leave out one of the levels of precedence and some of the operators and have the students add them as an exercise. But I think that within a complexity budget of 150 lines of code you can maybe be even more ambitious than that. Darius Bacon's example compiler in https://github.com/darius/parson/blob/master/eg_calc_compile.py https://github.com/darius/parson/blob/master/eg_calc_compile... is a bit more stripped down than that, but in its 32 lines of code it compiles arithmetic assignment statements to a three-address RISC-like code (though using an unbounded number of registers). https://github.com/darius/parson/blob/master/eg_calc_to_rpn.py https://github.com/darius/parson/blob/master/eg_calc_to_rpn.... is a 16-line version that compiles the same language to a stack machine like your tutorial example: from parson import Grammar, alter g = Grammar(r""" stmt* :end. stmt : ident '=' exp0 ';' :assign. exp0 : exp1 ('+' exp1 :'add')*. exp1 : exp2 ('*' exp2 :'mul')*. exp2 : '(' exp0 ')' | /(\d+)/ | ident :'fetch'. ident : /([A-Za-z]+)/. FNORD ~: /\s*/. """)(assign=alter(lambda name, *rpn: rpn + (name, 'store'))) ## print ' '.join(g('v = 42 * (5+3) + 2*2; v = v + 1;')) #. 42 5 3 add mul 2 2 mul add v store v fetch 1 add v store Of course that still contains no control flow, so it's still not a very convincing example of why you'd take the extra trouble to write a compiler rather than an interpreter. In 66 lines of code in https://github.com/kragen/peg-bootstrap/blob/master/peg.md https://github.com/kragen/peg-bootstrap/blob/master/peg.md I wrote an example compiler which compiles a PEG grammar into a JavaScript parser for that grammar. Admittedly those 66 lines do not include an implementation of JavaScript to run the code on. It compiles the language it's written in. In 132 lines of code in https://github.com/kragen/stoneknifeforth/blob/master/tinyboot1.tbf1 https://github.com/kragen/stoneknifeforth/blob/master/tinybo... I wrote an example compiler which compiles a crippled Forth dialect into i386 machine code, including an ELF header so you can run the result. It also compiles the language it's written in. It also doesn't include an i386 emulator to run it on. In 83 lines of code in http://canonical.org/~kragen/sw/dev3/neelcompiler.ml http://canonical.org/~kragen/sw/dev3/neelcompiler.ml Neel Krishnaswami wrote a compiler from the untyped λ-calculus to a simple assembly language for a register machine. It also doesn't include an implementation of the assembly language. In 18 lines of code in http://canonical.org/~kragen/sw/dev3/meta5ix.m5 http://canonical.org/~kragen/sw/dev3/meta5ix.m5, a simplification of Val Schorre's META-II, I wrote a compiler from grammar descriptions to an assembly code for a parsing-oriented virtual machine. It compiles the language it's written in. A Python interpreter for the machine is in http://canonical.org/~kragen/sw/dev3/meta5ixrun.py http://canonical.org/~kragen/sw/dev3/meta5ixrun.py (109 lines of code) and a precompiled version of the compiler-compiler for bootstrapping is in http://canonical.org/~kragen/sw/dev3/meta5ix.generated.m5asm http://canonical.org/~kragen/sw/dev3/meta5ix.generated.m5asm. It does recursive descent with only a single token of backtracking; a minimal summary of the most eccentric aspects of its syntax is that "" encloses text to expect on input, {} encloses text to output, <<>> encloses a token to parse from the input that might be copied to the output with $it (or unindented with @it), commas separate alternatives, and [x] is zero or more repetitions of x. - program: ["-" name @it ":" terms {return}, "#" [:notin ""]] - terms: term ["," {continue $choice} term] @choice - term: (factor {else $seq}, output) [factor {assert}, output] @seq - factor: string {literal $it} , "(" terms ")" , "[" @many terms {continue $many} "]" , name {call $it} , "<<" {begin} terms ">>" {end} , ":fnord" {fnord} factor , ":notin" string {notin $it} , ":between" string {between $it} - output: (quasiquote, "@" {dedent} (var, quasiquote)) {writeline} - quasiquote: "{" [(<<ch [ch]>>, "\" <<:notin "">>) {say "$it"}, "$" var] "}" - ch: :notin "$}\" - var: "it" {copyinput}, name {gen $it} - string: :fnord <<'"' [:notin '"'] '"', "'" [:notin "'"] "'">> - name: :fnord <<letter [letter, :between "09"]>> - letter: :between "az", :between "AZ", :between "__" A slightly incompatible variant of Meta5ix which instead compiles itself to C is in http://canonical.org/~kragen/sw/dev3/meta5ix2c.m5 http://canonical.org/~kragen/sw/dev3/meta5ix2c.m5 (133 lines of code, depending on how you count). (No C compiler is included.) The precompiled C output for bootstrapping is in http://canonical.org/~kragen/sw/dev3/meta5ix2c.c http://canonical.org/~kragen/sw/dev3/meta5ix2c.c. Meta5ix is extremely weak and limited, really only enough for a compiler front-end. Dave Long described META-II as "a field-improvised lever", which I think is still apt for Meta5ix. Now, again, I am totally ignorant about pedagogy, so I could be wrong about this, but I think that probably self-compiling compiler-compilers like most of my examples here are not the best tutorial examples, because they refer to themselves in complex and confusing ways. But I feel like they represent pretty good evidence that you can do something a lot more interesting in a 150-line-of-code compiler than evaluating a Boolean circuit.
secondcoming 4y ago
scrame 4y ago
k. so this is an OCaml parser for a toy language? I mean, cool, but... I don't know OCaml and this doesn't do a lot to sell the language over AntLR or whatever lex/yacc is called these days. I just feel like I need to learn another language to learn the language to be efficient. That's not really a criticism of the language, but it feels a little code-golfy. Is there a use for these tools other than writing yet-another-language? edit:I think ocaml actually can run perl5 modules, if I remember correctly.
- p4bl0 4y ago
  > k. so this is an OCaml parser for a toy language? The parser consists only of the first two files (and it is not even for a "toy language", it is really just for boolean expressions, a toy language could have been a lot more complex!). > I mean, cool, but... I don't know OCaml and this doesn't do a lot to sell the language over AntLR or whatever lex/yacc is called these days. > I just feel like I need to learn another language to learn the language to be efficient. So you don't know OCaml or it's parsing tools and don't want to learn about either, that is your choice but has nothing to do with this project :). > Is there a use for these tools other than writing yet-another-language? These tools are made for lexing and parsing. They work as a DSL because it's easier this way. They could have other usages but that's not their point. If you never want to parse anything you may never need them. And that's fine, you can just move along.

200 points by p4bl0 4y ago

Where can I learn more about mll and mly files? I've hand-rolled parsers and it's always my least favorite part of toy languages.

deleted 4y ago
[deleted]
a-dub 4y ago
https://v2.ocaml.org/manual/lexyacc.html https://v2.ocaml.org/manual/lexyacc.html
tekknolagi 4y ago
Search for ocamllex and ocamlyacc. Also Menhir.
- mftb 4y ago
  So weird, within the last hour I was wondering why I never see regular, old, lex and yacc around anymore, and then I came across this, which made realize it's probably because they generate C. Funny. I guess these output OCaml?
  - p4bl0 4y ago
    Yes, they do. Lex and yacc equivalent tools are available for many languages. Examples : - Python: https://ply.readthedocs.io/ https://ply.readthedocs.io/ (I already used it in a very small project, again for my students, here is an example of how it works: https://gist.github.com/p4bl0-/f5ed1e60fdc5e76a2d321bc8708a7817 https://gist.github.com/p4bl0-/f5ed1e60fdc5e76a2d321bc8708a7...) - Racket: https://docs.racket-lang.org/parser-tools/ https://docs.racket-lang.org/parser-tools/ (it's really great, I previously used Racket for my compiler course but I've switched to OCaml a few years back, because Racket parser tools don't go well with Typed Racket).

userbinator 4y ago

For those wondering what language this is for before clicking on it: it's not much more than what I think would traditionally be called an expression evaluator, and very simple one at that --- it only recognises binary logic expressions, and the 150 lines doesn't include the parser or lexer either. Not a bad attempt for what is presumably a first try, but I think "complete compiler" is overselling it.

a-dub 4y ago
there's no type checking, which i'd say is a fairly integral part of a compiler... but it does use a parser generator to generate a parser that constructs an ast and it then iterates that ast to generate a bytecode. that's basically a compiler, even if the language is basic expressions.
- userbinator 4y ago
  B has no type checking either. On the other hand, using a parser generator and not counting its output in the line count does seem like cheating.
  - p4bl0 4y ago
    > using a parser generator and not counting its output in the line count does seem like cheating Yeah maybe I should count OCaml's standard library lines of code too. Maybe also count expanded macros and inlined functions at each call site? At which point should I stop? Are assembly language pseudo-instructions cheating too? Common, don't be ridiculous.
  - wtetzner 4y ago
    I don’t see how, I would only count the input lines to the parser generator.
- compiler-guy 4y ago
  Type checking is a part of semantic analysis, which the author explicitly says isn’t present. Even so, the language it is compiling has only one type, so it isn’t possible for a program to have type errors. Just like in C++ one never need to check if a reference is null—it simply can’t be expressed in the language, thus preventing any errors of that kind, a single type prevents all kinds of type errors. One might argue that this is the most powerful way to do type checking. It simply isn’t possible to have an error.

blacklion 4y ago

Sooo nice :-) It looks like small cute kitten to me, sorry.

p4bl0 4y ago
Don't be sorry for this nice comment! I totally understand the cuteness feeling ^_^.
mdp2021 4y ago
If you like The Arts, and remarkable results, the website of Pablo ( https://pablo.rauzy.name/ https://pablo.rauzy.name/ ) is a thing to behold.

denotational 4y ago

As another comment also alludes, there's probably quite a lot more work required before this could be called a complete compiler (without heavy qualification as to what it actually compiles, since the language of boolean expressions probably isn't something that most people would consider to be a programming language per se); that said, toy languages like this are a great way to explore some fundamental principles of programming language theory. Boolean expressions have very trivial denotational semantics (since there's no recursion or state), so you could try formalising these in Coq (FRAP [1] and Software Foundations Vol. 2 [2] are both good places to learn more about this). Next, you could write formal operational semantics for your VM, and then finally prove that your compiler is correct in a formal sense (i.e. the image of any well-formed input under the compiler operation has a terminating execution in the operational semantics that yields the same value as would be obtained by the execution of the input expression under the denotational semantics). The last part would require implementing the compiler in Coq, but since you've written it in OCaml it probably wouldn't be very hard to port. [1] : https://frap.csail.mit.edu/main https://frap.csail.mit.edu/main [2] : https://softwarefoundations.cis.upenn.edu/plf-current/toc.html https://softwarefoundations.cis.upenn.edu/plf-current/toc.ht... Edit: Having looked at your profile I now realise that you probably know all of this already, but it might be informative for anyone else reading :)

stepchowfun 4y ago
Coq is so much fun. It makes writing proofs feel like playing a video game. I've just finished writing a Coq tutorial [1] that is aimed at programmers (rather than, say, computer scientists). It covers topics like programming with dependent types, writing proofs as data, universes & other type theory stuff, and extracting verified code—with exercises. [1] https://github.com/stepchowfun/proofs/tree/main/proofs/Tutorial https://github.com/stepchowfun/proofs/tree/main/proofs/Tutor...

skybrian 4y ago

I think people are getting hung up on the word "complete." This is a complete compiler in the sense that "hello world" is a complete (but minimal) program.

p4bl0 4y ago
Yes exactly :), I meant that it does everything from lexing the source code to emitting bytecode instructions (and provides the VM to run this bytecode). It is not a part of a compiler, it is a tiny, simple, stupid, but complete, compiler.
- kragen 4y ago
  I want to preface this comment with the fact that I'm terrible at teaching and know nothing about it, so it's entirely possible that your example compiler is much better for pedagogical purposes than the ones I'm going to suggest here. But I think they all have a significantly higher "power density", which at least from my point of view makes them more interesting and inspiring. I think mostly people are complaining that the language it compiles isn't a programming language, so it omits a lot of things that compilers for programming languages have to handle. And so it feels a bit like much ado about nothing: because there are no variables, loops, or values beyond single-bit values, the program it compiles can only ever produce a constant, predetermined output, and that output can only ever be 1 or 0. So the compiler is just sort of a particularly awkward and inefficient way to output that 1 or 0. A compiler for Brainf*** or SK-combinators or the untyped λ-calculus would be "more real" in that sense. More practical, and maybe also fitting into 150 lines, might be a language for something like a programmable calculator (untested sketch): program ::= stmt | stmt ";" program. stmt ::= "print" numexpr | variable ":=" numexpr | "while" numexpr comparator numexpr "{" program "}". comparator ::= "<" | ">" | "==" | "!=" | "<=" | ">=". numexpr ::= term | numexpr "+" term | numexpr "-" term. term ::= factor | term "*" factor | term "/" factor | term "%" factor. factor ::= atom | "-" atom | "+" atom | atom "^" factor. atom ::= "(" numexpr ")" | numeric_constant | variable. That's powerful enough to conveniently write, for example, a numerical root finding program for an arbitrary arithmetic expression. Maybe for pedagogical purposes (which, as I said, I am totally ignorant of) it would be useful to leave out one of the levels of precedence and some of the operators and have the students add them as an exercise. But I think that within a complexity budget of 150 lines of code you can maybe be even more ambitious than that. Darius Bacon's example compiler in https://github.com/darius/parson/blob/master/eg_calc_compile.py https://github.com/darius/parson/blob/master/eg_calc_compile... is a bit more stripped down than that, but in its 32 lines of code it compiles arithmetic assignment statements to a three-address RISC-like code (though using an unbounded number of registers). https://github.com/darius/parson/blob/master/eg_calc_to_rpn.py https://github.com/darius/parson/blob/master/eg_calc_to_rpn.... is a 16-line version that compiles the same language to a stack machine like your tutorial example: from parson import Grammar, alter g = Grammar(r""" stmt* :end. stmt : ident '=' exp0 ';' :assign. exp0 : exp1 ('+' exp1 :'add')*. exp1 : exp2 ('*' exp2 :'mul')*. exp2 : '(' exp0 ')' | /(\d+)/ | ident :'fetch'. ident : /([A-Za-z]+)/. FNORD ~: /\s*/. """)(assign=alter(lambda name, *rpn: rpn + (name, 'store'))) ## print ' '.join(g('v = 42 * (5+3) + 2*2; v = v + 1;')) #. 42 5 3 add mul 2 2 mul add v store v fetch 1 add v store Of course that still contains no control flow, so it's still not a very convincing example of why you'd take the extra trouble to write a compiler rather than an interpreter. In 66 lines of code in https://github.com/kragen/peg-bootstrap/blob/master/peg.md https://github.com/kragen/peg-bootstrap/blob/master/peg.md I wrote an example compiler which compiles a PEG grammar into a JavaScript parser for that grammar. Admittedly those 66 lines do not include an implementation of JavaScript to run the code on. It compiles the language it's written in. In 132 lines of code in https://github.com/kragen/stoneknifeforth/blob/master/tinyboot1.tbf1 https://github.com/kragen/stoneknifeforth/blob/master/tinybo... I wrote an example compiler which compiles a crippled Forth dialect into i386 machine code, including an ELF header so you can run the result. It also compiles the language it's written in. It also doesn't include an i386 emulator to run it on. In 83 lines of code in http://canonical.org/~kragen/sw/dev3/neelcompiler.ml http://canonical.org/~kragen/sw/dev3/neelcompiler.ml Neel Krishnaswami wrote a compiler from the untyped λ-calculus to a simple assembly language for a register machine. It also doesn't include an implementation of the assembly language. In 18 lines of code in http://canonical.org/~kragen/sw/dev3/meta5ix.m5 http://canonical.org/~kragen/sw/dev3/meta5ix.m5, a simplification of Val Schorre's META-II, I wrote a compiler from grammar descriptions to an assembly code for a parsing-oriented virtual machine. It compiles the language it's written in. A Python interpreter for the machine is in http://canonical.org/~kragen/sw/dev3/meta5ixrun.py http://canonical.org/~kragen/sw/dev3/meta5ixrun.py (109 lines of code) and a precompiled version of the compiler-compiler for bootstrapping is in http://canonical.org/~kragen/sw/dev3/meta5ix.generated.m5asm http://canonical.org/~kragen/sw/dev3/meta5ix.generated.m5asm. It does recursive descent with only a single token of backtracking; a minimal summary of the most eccentric aspects of its syntax is that "" encloses text to expect on input, {} encloses text to output, <<>> encloses a token to parse from the input that might be copied to the output with $it (or unindented with @it), commas separate alternatives, and [x] is zero or more repetitions of x. - program: ["-" name @it ":" terms {return}, "#" [:notin ""]] - terms: term ["," {continue $choice} term] @choice - term: (factor {else $seq}, output) [factor {assert}, output] @seq - factor: string {literal $it} , "(" terms ")" , "[" @many terms {continue $many} "]" , name {call $it} , "<<" {begin} terms ">>" {end} , ":fnord" {fnord} factor , ":notin" string {notin $it} , ":between" string {between $it} - output: (quasiquote, "@" {dedent} (var, quasiquote)) {writeline} - quasiquote: "{" [(<<ch [ch]>>, "\" <<:notin "">>) {say "$it"}, "$" var] "}" - ch: :notin "$}\" - var: "it" {copyinput}, name {gen $it} - string: :fnord <<'"' [:notin '"'] '"', "'" [:notin "'"] "'">> - name: :fnord <<letter [letter, :between "09"]>> - letter: :between "az", :between "AZ", :between "__" A slightly incompatible variant of Meta5ix which instead compiles itself to C is in http://canonical.org/~kragen/sw/dev3/meta5ix2c.m5 http://canonical.org/~kragen/sw/dev3/meta5ix2c.m5 (133 lines of code, depending on how you count). (No C compiler is included.) The precompiled C output for bootstrapping is in http://canonical.org/~kragen/sw/dev3/meta5ix2c.c http://canonical.org/~kragen/sw/dev3/meta5ix2c.c. Meta5ix is extremely weak and limited, really only enough for a compiler front-end. Dave Long described META-II as "a field-improvised lever", which I think is still apt for Meta5ix. Now, again, I am totally ignorant about pedagogy, so I could be wrong about this, but I think that probably self-compiling compiler-compilers like most of my examples here are not the best tutorial examples, because they refer to themselves in complex and confusing ways. But I feel like they represent pretty good evidence that you can do something a lot more interesting in a 150-line-of-code compiler than evaluating a Boolean circuit.

secondcoming 4y ago

scrame 4y ago

k. so this is an OCaml parser for a toy language? I mean, cool, but... I don't know OCaml and this doesn't do a lot to sell the language over AntLR or whatever lex/yacc is called these days. I just feel like I need to learn another language to learn the language to be efficient. That's not really a criticism of the language, but it feels a little code-golfy. Is there a use for these tools other than writing yet-another-language? edit:I think ocaml actually can run perl5 modules, if I remember correctly.

p4bl0 4y ago
> k. so this is an OCaml parser for a toy language? The parser consists only of the first two files (and it is not even for a "toy language", it is really just for boolean expressions, a toy language could have been a lot more complex!). > I mean, cool, but... I don't know OCaml and this doesn't do a lot to sell the language over AntLR or whatever lex/yacc is called these days. > I just feel like I need to learn another language to learn the language to be efficient. So you don't know OCaml or it's parsing tools and don't want to learn about either, that is your choice but has nothing to do with this project :). > Is there a use for these tools other than writing yet-another-language? These tools are made for lexing and parsing. They work as a DSL because it's easier this way. They could have other usages but that's not their point. If you never want to parse anything you may never need them. And that's fine, you can just move along.