4 ms·

Implement a programming language from scratch

136 points by sea6ear 12y ago

samatman 12y ago
C'mon, why stop there? Implement Scheme in your toy lambda. Then implement another toy lambda in your Scheme, and a Scheme in that. Continue until it takes several minutes to do (fib 5). Then, write JIT compiler for that Scheme. See what it takes to get down to pre-Inception levels of performance. Now, you've actually learned something: Abstractions are costly.
- minopret 12y ago
  Or you can go on to implement all the toy lambdas in all the toy lambdas, simultaneously. * [The Mystery of the Tower Revealed: A Non-Reflective Description of the Reflective Tower](http://www.cs.indiana.edu/cgi-bin/techreports/TRNNN.cgi?trnum=TR196 http://www.cs.indiana.edu/cgi-bin/techreports/TRNNN.cgi?trnu...) [abstract](http://www.ccs.neu.edu/home/wand/Bibliography.html#WandFriedman88 http://www.ccs.neu.edu/home/wand/Bibliography.html#WandFried...) * [Reflection](http://library.readscheme.org/page11.html http://library.readscheme.org/page11.html) Maybe abstraction is only a means to [expressiveness](http://programmers.stackexchange.com/a/254867/100375 http://programmers.stackexchange.com/a/254867/100375).
- gus_massa 12y ago
  Too late, someone already did that and measured the overhead of up to five interpretations layers: "Scheme benchmarking with a meta-circular" interpreter http://yinwang0.wordpress.com/2013/11/04/scheme-benchmarking/ http://yinwang0.wordpress.com/2013/11/04/scheme-benchmarking... Archive: http://web.archive.org/web/20140105145428/https://yinwang0.wordpress.com/2013/11/04/scheme-benchmarking/ http://web.archive.org/web/20140105145428/https://yinwang0.w... HN discussion: https://news.ycombinator.com/item?id=7045734 https://news.ycombinator.com/item?id=7045734 (25 points, 443 days ago, 9 comments) (The main critic is that it should compare more scheme implementations.) Many modern schemes (and similar languages like Racket and Clojure) have many optimization, use bytecode and jit compiling, so the abstraction overhead is not as big as in the naive versions. And you get nice code and powerful macros in exchange. IIRC Stalin is faster than C in some benchmarks, but the compiling time is very big. "Stalin: a global optimizing compiler for Scheme" https://github.com/barak/stalin https://github.com/barak/stalin HN discussion: https://news.ycombinator.com/item?id=8214343 https://news.ycombinator.com/item?id=8214343 (85 points, 220 days ago, 70 comments)
- Peaker 12y ago
  Unless your compiler strips them out!
blt 12y ago
Just add garbage collection!
bishc 12y ago
In my experience, many people will miss the significance of this, or will simply fail to grasp how this is implementing a programming language at all. After all, you're taking advantage of the host language for every single aspect of the new language, even tokenizing/parsing. More interesting for beginners (in my opinion) are examples implementing a simple tokenizer, parser, and compiler to another source language. This seems to be what closes the gap between programming languages as mystical constructs and programming languages as programs themselves. This point of view does tend to displease the traditional SICP crowd though :-).
- minopret 12y ago
  I agree. A counterargument is that you're inherently taking advantage of the processor(s) and the operating system, not to mention, ha ha, every single component and factor that you did not personally create, whether or not it is computational in nature... Another route, my present hobby and something that I know many have done before: Take the Lisp program on page 10 of the Lisp 1.5 User Manual and translate it into C. Write a simple tokenizer/parser (read function) in C and translate that into Lisp. Once the C program can run the equivalent Lisp program, we're on our way. At the outset I have no garbage collection. I just expect the memory space to fill up pretty soon. I could have `cons` compute a hash for each cell to eliminate common subexpressions, but for a while I suppose I won't bother at all. The C program has a loop to handle evcon (did I write cons? oops), eval, and apply as a trio of mutually tail-recursive operations. That's an obvious place to put a stop-the-world mark-and-sweep operation or some such thing. To get the C tools out of the loop eventually, hand-disassemble the binary program (C compiler output) just to see what's there. Then write a Lisp program (compiler) that translates the Lisp 1.5 User Manual program into something pretty similar.
  - kazinator 12y ago
    A counter-counter argument is that implementing a language that is semantically distant from assembly language, over top of assembly language, counts as "from scratch", whereas skinning a language over with an interpreter (which doesn't even scan tokens, collect garbage or perform any I/O) doesn't count as "from scratch".
wesleyy 12y ago
Scared me for a second, thought he as going to make a programming language in the MIT gui language "Scratch"
amatic 12y ago
Here is something from my todo list, build lisp in C: http://www.buildyourownlisp.com/ http://www.buildyourownlisp.com/

136 points by sea6ear 12y ago

C'mon, why stop there? Implement Scheme in your toy lambda. Then implement another toy lambda in your Scheme, and a Scheme in that. Continue until it takes several minutes to do (fib 5). Then, write JIT compiler for that Scheme. See what it takes to get down to pre-Inception levels of performance. Now, you've actually learned something: Abstractions are costly.

minopret 12y ago
Or you can go on to implement all the toy lambdas in all the toy lambdas, simultaneously. * [The Mystery of the Tower Revealed: A Non-Reflective Description of the Reflective Tower](http://www.cs.indiana.edu/cgi-bin/techreports/TRNNN.cgi?trnum=TR196 http://www.cs.indiana.edu/cgi-bin/techreports/TRNNN.cgi?trnu...) [abstract](http://www.ccs.neu.edu/home/wand/Bibliography.html#WandFriedman88 http://www.ccs.neu.edu/home/wand/Bibliography.html#WandFried...) * [Reflection](http://library.readscheme.org/page11.html http://library.readscheme.org/page11.html) Maybe abstraction is only a means to [expressiveness](http://programmers.stackexchange.com/a/254867/100375 http://programmers.stackexchange.com/a/254867/100375).
gus_massa 12y ago
Too late, someone already did that and measured the overhead of up to five interpretations layers: "Scheme benchmarking with a meta-circular" interpreter http://yinwang0.wordpress.com/2013/11/04/scheme-benchmarking/ http://yinwang0.wordpress.com/2013/11/04/scheme-benchmarking... Archive: http://web.archive.org/web/20140105145428/https://yinwang0.wordpress.com/2013/11/04/scheme-benchmarking/ http://web.archive.org/web/20140105145428/https://yinwang0.w... HN discussion: https://news.ycombinator.com/item?id=7045734 https://news.ycombinator.com/item?id=7045734 (25 points, 443 days ago, 9 comments) (The main critic is that it should compare more scheme implementations.) Many modern schemes (and similar languages like Racket and Clojure) have many optimization, use bytecode and jit compiling, so the abstraction overhead is not as big as in the naive versions. And you get nice code and powerful macros in exchange. IIRC Stalin is faster than C in some benchmarks, but the compiling time is very big. "Stalin: a global optimizing compiler for Scheme" https://github.com/barak/stalin https://github.com/barak/stalin HN discussion: https://news.ycombinator.com/item?id=8214343 https://news.ycombinator.com/item?id=8214343 (85 points, 220 days ago, 70 comments)
Peaker 12y ago
Unless your compiler strips them out!

blt 12y ago

Just add garbage collection!

bishc 12y ago

In my experience, many people will miss the significance of this, or will simply fail to grasp how this is implementing a programming language at all. After all, you're taking advantage of the host language for every single aspect of the new language, even tokenizing/parsing. More interesting for beginners (in my opinion) are examples implementing a simple tokenizer, parser, and compiler to another source language. This seems to be what closes the gap between programming languages as mystical constructs and programming languages as programs themselves. This point of view does tend to displease the traditional SICP crowd though :-).

minopret 12y ago
I agree. A counterargument is that you're inherently taking advantage of the processor(s) and the operating system, not to mention, ha ha, every single component and factor that you did not personally create, whether or not it is computational in nature... Another route, my present hobby and something that I know many have done before: Take the Lisp program on page 10 of the Lisp 1.5 User Manual and translate it into C. Write a simple tokenizer/parser (read function) in C and translate that into Lisp. Once the C program can run the equivalent Lisp program, we're on our way. At the outset I have no garbage collection. I just expect the memory space to fill up pretty soon. I could have `cons` compute a hash for each cell to eliminate common subexpressions, but for a while I suppose I won't bother at all. The C program has a loop to handle evcon (did I write cons? oops), eval, and apply as a trio of mutually tail-recursive operations. That's an obvious place to put a stop-the-world mark-and-sweep operation or some such thing. To get the C tools out of the loop eventually, hand-disassemble the binary program (C compiler output) just to see what's there. Then write a Lisp program (compiler) that translates the Lisp 1.5 User Manual program into something pretty similar.
- kazinator 12y ago
  A counter-counter argument is that implementing a language that is semantically distant from assembly language, over top of assembly language, counts as "from scratch", whereas skinning a language over with an interpreter (which doesn't even scan tokens, collect garbage or perform any I/O) doesn't count as "from scratch".

wesleyy 12y ago

Scared me for a second, thought he as going to make a programming language in the MIT gui language "Scratch"

amatic 12y ago

Here is something from my todo list, build lisp in C: http://www.buildyourownlisp.com/ http://www.buildyourownlisp.com/