Hacker News Reader

Comment by the_watcher | Hacker News Reader

How far along as a programmer should one be before attempting building a language. I am a novice (very, very much so) Rubyist, and don't think I am anywhere near being able to attempt it, but I do know that, when I was still in school, the process most likely to make a complicated subject click with me was to understand it all the way to it's origin (the starkest example was actually the quadratic formula - I had tons of trouble understanding it and how to use it until I had a teacher who made us actually derive it, and all of a sudden I was one of the best in the class). Building a programming language seems like it might have the same kind of effect on me, and, being a firm believer of living outside your comfort zone, would like to know if it's possible for someone who is nowhere near being able to call himself a programmer to eventually build one.

View on HN

This may not be a common opinion, but building a language is certainly within the reach of a novice programmer. The base ideas are very, very simple. You do have to be careful not to be overwhelmed by either the terminology ("recursive descent parsing" is a slightly more elaborate version of "reading a file") or some of the more elaborate things that you don't need for the basics but might want for a truly useful tool ("parsing" is a deep subject built mostly around making "reading a file" simpler, for arbitrarily complicated files).

Building languages is also one of the most thoroughly studied topics, which is both a boon and a bane. On one hand, there are lots of good tutorials and excellent tools. On the other hand, there is lots of stuff elaborating on the basics and much of it seems almost deliberately complicated.

Go for it! There are a lot of much worse ways of going into the rabbit hole.

Thanks! Any suggestions for resources to help me get started? I'm not afraid of complicated terminology as long as there is a way for me to easily figure out what it means (whether Wikipedia, a glossary, or simply a great example).

Start with untyped lambda calculus, augmented with numbers, and addition. That's what I did. Such a language is dead simple: you only have four kinds of expressions: numbers, additions, functions, and function calls.

Write a parser and a printer (a pretty printer would be best, but you don't have to). Use one to test the other. Then write an interpreter, who takes an expression as input, evaluates it, and spits out a number.

The whole thing should fit in a couple hundred lines, tops. The only real difficulty is to evaluate function calls. The rest is only a matter of catching runtime errors (like trying to add a number and a function). To properly implement your language, you may have to learn about closures and lexical scoping, though there are tricks to sidestep the issue.

To test your language, check out the Y and Z combinators here https://en.wikipedia.org/wiki/Fixed_point_combinator and use the Z combinator to implement the factorial function.

The next step is to flesh out your language a bit. I suggest you augment it with "let" bindings first: it's just syntax sugar over lambdas: you change your parser, but you don't have to touch the interpreter.

In addition to the article here and "Write Yourself a Scheme in 48 Hours" (the implementation language is Haskell, which may be a barrier)[1], and some others mentioned in the comments here, there's Peter Norvig's "(How to Write a (Lisp) Interpreter (in Python))"[2] and "(An ((Even Better) Lisp) Interpreter (in Python))"[3].

Every last Lisp book out has at least one implementation of a Lisp evaluator, although most don't go into all of the other stuff you have to do like parsing. On the other hand, there are a lot of books and articles that focus on parsing as if it were the most important part.

Someone has already mentioned Structure and Interpretation of Computer Programs[4], additionally, there is the Essentials of Programming Languages[5], Paul Wilson's An Introduction to Scheme and its Implementation[6], and some things I haven't read, like Simon Peyton Jones and David Lester's Implementing functional languages: a tutorial[7].

[1] http://en.wikibooks.org/wiki/Write_Yourself_a_Scheme_in_48_H...

[2] http://norvig.com/lispy.html

[3] http://norvig.com/lispy2.html

[4] http://mitpress.mit.edu/sicp/full-text/book/book.html

[5] http://www.eopl3.com/

[6] ftp://ftp.cs.utexas.edu/pub/garbage/cs345/schintro-v14/schintro_toc.html

[7] http://research.microsoft.com/en-us/um/people/simonpj/Papers...

I don't really have a good answer as to how much experience is needed, but I do know I wish I had attempted it earlier.

My suggestion: Just try and see how it goes. If you find it too overwhelming, don't worry, you can always revisit the concepts later.

I didn't write the tutorial with novice programmers in mind, so I can't promise everything will be explained as you need. But still, if you do try, I'd love to hear your experiences.

Are you the author? If you email me, if I get some free time and get going on this, I'll happily keep you informed. Also, looks like I'll be building a Lisp? That's pretty exciting, since I've wanted to try to learn one for a while now, but was always scared off by the syntax.

Yes, I'm the author. You'll find my contact info at the frontpage of the blog. Please, send my any feedback :)

The language is a simplified variant of Lisp. This is just a toy language, so a lot of things from a real Lisp will be missing, but I think there's enough to give you a sense of the core of the language. Actually, this version isn't too far off from the original Lisp written by John McCarthy over 55 years ago.

Reply on news.ycombinator.com