Implement a programming language from scratch
matt.might.net
matt.might.net
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 :-).
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.
http://www.cl.cam.ac.uk/~am21/research/funnel/prolog.c
A list of tiny, powerful interpreters would be good.
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
enum {I,O,V,A,L};
int n=44,i,c,T[M]={L,A,8,A,2, V,0,L,L,V,
A,30,L,A,2,V,0,L,A,5,A,7,L,V,0,O,
A,14,L,A,2,V,0,L,A,5,A,2, V,0,O,O,A},b,s;
typedef struct _{int t,r; struct _*e,*n;} C;C*e,*f,*l,*S[M];
void x(int l,int u){for(;l<=u;T[n++]=T[l++]);}
int g(){i--||(i=b,c=getchar());return c>>i&1;}
void d(C*l){!l||--l->r||(d(l->e),d(l->n),l->n=f,f=l);}
int p(int m){if(g()){for(T[n++]=V;g();T[n]++);n++;}else
T[m]=n++&&g()?(T[m+1]=p(++n),A):L,p(n);return n-m;}
int main(int t){char o;
b=t>1?0:7;T[43]=p(n);i=0;
for(t=b?10:26;;)switch(T[t]){
case I: g();i++;assert(n<M-99);if(~c&&b){x(0,6);for(T[n-5]=96;i;T[n++]=!g())
x(0,9);}x(c<0?7:b,9);T[n++]=!b&&!g();break;
case O: t=b+t>42?(o=2*o|t&1,28):(putchar
(b?o:t+8),fflush(stdout),b?12:28);break;
case V: l=e;for(t=T[t+1];t--;e=e->n);
t=e->t;(e=e->e)&&e->r++;d(l);break;
case A: t+=2;f||(f=calloc(1,sizeof(C)));assert(f&& s<M);S[s++]=l=f;f=l->n;
l->r=1;l->t=t+T[t-1];(l->e=e)&&e->r++;break;
case L: if(!s--)return 0;S[s]->n=e;e=S[s];t++;break;
}
return T[t+2];
} eval(someCode);
It uses a hand-rolled state machine for tokenizing. Recursive descent for parsing. And the interpreter uses the visitor pattern to walk the AST.
Mine also, strangely unlike many of these so-called "teaching" toy languages, has documentation. I don't understand the point of a tiny language for people to learn from if you made it tiny by removing all of the comments. :(
And, to try to avoid leading the reader astray, it calls out any shortcuts it makes. Those are hints where you'd want to do something more robust if you weren't trying to be minimal.
It's here:
https://github.com/munificent/jasic
If you work your way through that, you'll be a long way towards being able to find your way around a real-world interpreter.
The main things it doesn't do is:
1. GC. It leans on Java for that.
2. Compile to bytecode or some other representation. It's a simple tree walker, like Ruby 1.8.
If you want to learn more about those, take a look at:
Everything except for actually carrying out function application (which is pretty much the only computation in a language this tiny).
It's kind of like saying in order to learn how to exercise we should play some video games first.
99% of languages out there, including in the Lisp family.
>It's kind of like saying in order to learn how to exercise we should play some video games first.
No, it's more like saying that in order to learn how to exercise we should move our bodies...
> This point of view does tend to displease the traditional SICP crowd though :-).
I disagree. SICP does a fairly good job in explaining what's behind compilers and other languages. See chapter 5 "Computing with Register Machines" that follows immediately the chapter that contains the eval/apply loop.
Although the tokenizer and parser are sadly missing in SICP, these are also the most boring topics. Yes, you can write them by hand, but in the end you'll learn how to use regexes and parser generators. Which is important, but only a tiny fraction of what happens inside a compiler or interpreter.
In my experience, most production compilers and interpreters use handwritten parsers, not regexes and parser generators. The latter is usually confined to small DSLs and toy compilers because things like error reporting and recovery is usually a nightmare with parser generators.
I don't agree the tonenizer and parser bit is "boring", but they are extremely well covered compared to subjects like code generation, though.
Now, you've actually learned something: Abstractions are costly.
* [The Mystery of the Tower Revealed: A Non-Reflective Description of the Reflective Tower](http://www.cs.indiana.edu/cgi-bin/techreports/TRNNN.cgi?trnu...) [abstract](http://www.ccs.neu.edu/home/wand/Bibliography.html#WandFried...)
* [Reflection](http://library.readscheme.org/page11.html)
Maybe abstraction is only a means to [expressiveness](http://programmers.stackexchange.com/a/254867/100375).
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 HN discussion: https://news.ycombinator.com/item?id=8214343 (85 points, 220 days ago, 70 comments)