Item — HN Reader

I'm a little more familiar with SNOBOL, but ICON is imperative and procedural and a bit complicated, and it looks tempting as a target for this little thought experiment that we have, writing a compiler to understand how it works.

Now it would not be a fair test to go after scheme or lisp, as there are many examples out there of people who have implemented toy schemes and toy lisps. Toy here in the sense of tutorial or exploratory.

So being a simple country boy, I seem to be having trouble coming up with examples in line with your point. I wonder if you could give me some examples of non-procedural languages for which this exercise would not work--the exercise of writing a compiler for a language not being successful for learning the language without doing extensive rigorous mathematical semantic modeling?

1 comments

I would say nearly all functional programming languages are beyond the scope of the dedicated hacker with nothing to go with but the Dragon book and Lex and Yacc manuals. The strict ones are more approachable, but even an FP in its most primitive form, the untyped lambda calculus, is hard to reason about without some form of mathematical tools, at least enough to understand efficient implementation of recursion. (Anyone can implement recursion, even in assembly, but its consequences are far more reaching than just "set base pointer to stack pointer, add sizeof(locals) to stack pointer, and jump to routine entry point"; that's why you have people like GvR struggling with it, 20+ years after the lambda papers.)

Type theory would send anyone insane; static typing is trivial when you have a set of "primitive" types and another "derived" types; neither C nor Pascal nor another Algol dialect actually implement proper types. C gives you a bag of bytes in the form of a struct, and pointer to that back; you create your data structures with that. ML dialects take type theory to fantastic extremes. Throw pattern matching into the mix and your regular compiler hacker is off to reading the semantics literature.

Reasoning about lazy evaluation is also not trivial. It doesn't even show up in the mainstream compiler literature, which, by the way, has always been about creating the fastest Fortran dialect. Compiler research IS Fortran research, while the PL research is mostly FP research (even if it masquarades as OOP sometimes, usually for grant and resume purposes.)

Logical languages also are beyond the reach of someone coming from a classic compiler hacking background. LPLs are so far out that not even mainstream PL enthusiasts grok them.

All is not lost, however. At least one language, Forth, is trivial to implement, and best learned by implementing it first, as much as it's difficult to reason about. The problem with Forth is that there is nothing magical going on; it's a simple and beautiful little perversion, something that could only come out of a mind untainted by theory. Ditto with Perl, though by no means pretty. Perl has the finger prints of a hobbyist all over it.

So if i were nuts enough to try this experiment, which language would you recommend? Ok to reply via email off list as well.

Call me selfish, but I treasure programming languages, specially the weird and unconventional ones, and specially if they have some sort of academic/theoretical brownie points.

You have already done BLISS, I have been meaning to clone it ever since I read an old rant by Dennis Ritchie on usenet. I am weirdly attracted to CMU languages, so I am gonna say Dylan :-) Marlais is open source and you can use it as a starting point. I am half way through cloning DUIM for Common Lisp and, frankly, all their "syntax" innovation would be lost to me. I am forever ruined for non-Lisp syntaxes, I think. ISO Lisp would be cool too.

If you weren't a compiler hacker I would have recommended Oberon.

For some reason, I could never see compiler hacking outside the traditional code generation for a real machine. If I wanna do source translation I would probably stick to macrology.

Miranda would be cool too, specially since there are no FLOSS compilers for it.

Mozart/Oz has a tiny kernel which you can clone, but I don't want you to learn this in that matter. Instead, get the book by van Roy and Haridi and enjoy at a leisurely pace.

Someday I would love to implement an APL and a Prolog dialect. Someday.