HN Explorer

Ask HN: What's a starting point for learning how to write programming languages?

213 points by da_murvel ↗ HN
I've been thinking about writing my own programming language for some time. This to gain a deeper understanding of how programming languages, and by extent, computers work. I've bought the Flex and Bison book by John Levine to have a resource on parsing and lexing. I have come to realize however, that writing a complete language like Java, Python, Ruby, from bottom to the top, is of course not a small task. So therefore I started to think of writing maybe a compiler for another language, writing a "simple" language like SQL, Markdown etc. to begin with.

What are your experiences when writing a new programming language, where and how did you start?

104 comments

[ 2.7 ms ] story [ 188 ms ] thread
CyberFonic
I would suggest looking at Niklaus Wirth's Compiler Construction book and even the Oberon compiler. This is one of the best ways to learn about compilers and writing programming languages. See: https://www.inf.ethz.ch/personal/wirth/

Another approach is to look at SICP, it is Scheme oriented and more oriented towards macros. See: https://mitpress.mit.edu/sites/default/files/sicp/index.html

SQL is a deceptively complex language, the optimisations that it performs are very complex. Markdown, on the other hand, is more of a transpiler to HTML and is not Turing Complete.

[deleted]
(comment deleted)
merlincorey
Types and Programming Languages (TAPL) is required reading, in my opinion: https://www.cis.upenn.edu/~bcpierce/tapl/
alexashka
Absolutely not for a markdown parser, which is what the author is asking about to get started
merlincorey
Parsing is but 1/3 of compiling.

Markup languages are not generally thought of as programming languages, but maybe that's an archaic view.

At any rate, 90% of the material in this thread is way overkill if all one wants to do is parse Markdown.

[deleted]
(comment deleted)
citeguised
Check out "Writing An Interpreter In Go" https://interpreterbook.com/ It uses Golang to make an interpreter for a simple C-Style language and it's "only" 200 pages long. I'm about a third in and my head is smoking.
slackpad
This is a great read! The code is very clean and easy to follow and the progression of ideas is well thought out. Even if you don't know Go you could learn that along the way without too much trouble. He also just released a companion volume writing a compiler for the Monkey as well.
dvlsg
That looks pretty awesome. Thanks for the suggestion. Looks like it gets to a good amount of functionality too, with first class functions and closures and the like.
stevekemp
Very much so, and once you've completed the book there are a lot of extensions various people have made.

For example here's a version with classes / OO-behaviour:

https://github.com/haifenghuang/monkey

Or here's my version which "just" adds some more standard-library facilities, allowing you to open/read/write files:

https://github.com/skx/monkey

I found the language fun to play with, and I used a virtually identical lexer and parser-idea in a recent project of my own - rather than "parsing" an input-file with regular-expressions, which is how I would have previously approached the implementation of simple DSLs. I guess that showed I'd learned something useful!

loffa
The jovial writing style makes the content easily consumable
[deleted]
(comment deleted)
iafisher
Build Your Own Lisp (http://buildyourownlisp.com/) is as good a starting point as any. You learn to implement a high-level dynamic programming language in C, which is a common choice of implementation language for interpreters (e.g., CPython, Ruby). I really can't recommend the book enough.
axlprose
Beautiful Racket[0] is a good starting point that covers a lot of nice small examples that incrementally build up your understanding of the different components involved in making languages. And it uses Racket[1], which incorporates the idea of crafting many small "domain-specific" languages to solve different problems into its entire philosophy[2].

[0] https://beautifulracket.com/

[1] https://racket-lang.org/

[2] http://felleisen.org/matthias/manifesto/

mi_lk
Second Beautiful Racket. Good writing and approachable content.
mikeurbach
I'm just finishing up the last tutorial, and I highly recommend this as well. I made one traditional C compiler back in college with flex and bison, which I consider an invaluable experience, but I've always wanted to tap in to the power of Scheme for developing new languages. I had some false starts on my own and with mediocre tutorials, but in the end Beautiful Racket was exactly the kind of pedagogy I needed.
nybblesio
I'm writing a programming language from scratch called Basecode. It's very early days yet. The bootstrap compiler (written in C++) is about three months away from being complete. Then I'll rewrite the compiler in Basecode itself to make it self-hosted. After the language is self-hosted, there's a second level of features I'll be adding that I think are quite exciting.

I've captured the entire process on video: https://www.youtube.com/watch?v=0_PX2Ue6F_A&list=PLWMUVtnFsZ...

The YouTube playlist is an archive of my daily streams on Twitch.

Impossible
Although its still in development, http://craftinginterpreters.com/ (previously on HN https://news.ycombinator.com/item?id=13406081) seems promising, and the existing content is good.
zfdrdg
Crafting interpreters is a great place to start! Takes you from basically nothing to implementing a whole language surprisingly quickly.
cgag
I'm not super far in but I'm very happy with it so far. I recommend it very highly and am very skeptical of anyone recommending reading the dragon book without doing something more hands on like this first.

Maybe that book is more practical than I realize though.

koonsolo
I also recommend Crafting Interpreters.

It helped me write the scripting language that I use in one of my projects.

nostrademons
Learn the mechanics of compiler construction first - that'll inform everything about your language, and is a prerequisite to actually building something other people can use. I'd recommend The Dragon Book [1], SICP [2], and Modern Compiler Implementation in ML [3] for this.

After that, it's a question of where you want to go with your language, and what distinguishing features you'd like it to have relative to other languages. Languages which just change some syntax and keywords but otherwise look like C are common, but they tend not to get usage beyond their creators. Much of the academic research lately is about type systems (TAPL has already been mentioned) - there's research into dependent types, effect typing, total functional programming, linear types already made it into Rust's borrow checker, etc.

However, many of the worst problems in industry - dependencies, versioning, smoothly migrating from a prototype to robust production code, code navigation, security, parallelization & distribution, the memory hierarchy - have gotten relatively little attention in academic research, and are desperately awaiting solutions. If you have some industry experience, it may be worth trying to imagine how you might fix these problems if you were allowed to change the programming language at will.

[1] https://en.wikipedia.org/wiki/Compilers:_Principles,_Techniq...

[2] http://web.mit.edu/alexmv/6.037/sicp.pdf

[3] https://www.amazon.com/Modern-Compiler-Implementation-Andrew...

earenndil
> Languages which just change some syntax and keywords but otherwise look like C are common, but they tend not to get usage beyond their creators

Considering c++ is one of the most widely-used languages out there, I would question this.

nostrademons
C++ has a bunch of new semantics on top of C - classes, access modifiers, virtual functions, constructors/destructors, operator overloading, different casting rules, exceptions, namespaces, templates, etc. People who know both of them well consider them very distinct languages, because the programming style you use in a C++ program is very different from a C program.
ecesena
I've been working for a while on a sort of language for writing highly optimized cryptographic code, mostly elliptic curve cryptography where there's a very elegant mathematical description, but when you try to optimize every single detail manually it's easy to get very dirty code.

The idea was then to have a language that maintains the elegance and clarity, and a compiler that generates in my case C code. This let me focus on the "core" of a compiler, without too much emphasis on parsing, tons of optimizations, corner cases.

So this would be my advice. Pick a domain, maybe focus on getting highly optimized code, design a small language and build your first compiler.

alexashka
If you like books, this one is great:

https://www.elsevier.com/books/programming-language-pragmati...

If you like excellent free university lectures online, this is great:

https://www.youtube.com/watch?v=3N__tvmZrzc

In reality - programming languages are most likely what you think they are, if you simply start with the basics like what's a variable, what's a function. How do I call functions inside other functions. Do I want variables to have types. What kind of types?

If you start with the very very basics - global variables, global functions, you can't call functions within other functions - and implement that, you'll get the feel for it, which is most likely as far as you'll want to go, because it gets very tedious, very quickly, as soon as you want something as 'simple' as proper unicode support, garbage collection, generics, inheritance, foreign-function-interface and the list goes on and on.

To get your feet wet regarding what it's all about - those video lectures above are top notch.

tluyben2
A Forth or a Lisp are simple tasks for an experienced programmer, and even basic ones are really satisfying imho. Seeing simple constructs work in an hour of coding really feels great. I implemented more complex languages (with types) for work which were more like DSLs but in languages less suited for the type of DSL we required, but I find most pleasure doing little Forth (like [1]) or Lisp likes when I am waiting for hours (in a plane for instance). It is like playing games for me. I write them on my phone or iPad.

I would recommend a lot of books here as well for a solid base and giving you the background needed to write more complex languages including static types, compilers, JITs and VMs. But for me, because I really do not have that much time, that would stretch over too long time and I lose interest, so I stick to things I know I can finish (or rather, get working and achieve something a previous incantation did not achieve; smallest, simplest, fastest etc).

[1] https://gist.github.com/tluyben/16ee2645c4c8aed813005d51488d...

white-flame
I'll agree and expand on their benefits to more complex things:

The vast majority of languages are parsed into ASTs of some form, and Lisp is basically directly programming in AST data structures that are executable. Seeing that source code is basically just another data structure to be manipulated and converted was the major "Ah hah!" moment in demystifying compilers for me.

Forth is a great lower-level representation of nested expression evaluation, and sheds a lot of light on how to organize that evaluation in your code generation, converting foo(bar(baz(val),blort(val2))) into a linear stream of operations. Even for register machines, Forth's stack represents the intermediate values that must be retained between expressions in either registers or memory.

Once this basis of how programming languages work is established, then the ideas of new programming language design from the source code perspective can be explored in practical terms.

kovrik
What worked for me: read Norvig's tutorials (How to write lisp). It gives basic understanding.

Then continue enhancing that tiny language, add more features.

Start with an interpreter, they are easier to grasp. You can always add a compiler later.

I grabbed Scheme R5RS standard and started implementing it in Kotlin: https://github.com/kovrik/scheme-in-kotlin

Then added more Clojure-like and Racket-like features, plus some Kotlin features.

mballantyne
I suggest "Programming Languages: Application and Interpretation", available free here: http://cs.brown.edu/courses/cs173/2012/book/ It's an undergraduate-level programming languages class textbook.

Other books burn a lot of time on things like lexing and parsing; this one does not. In the lisp tradition, it assumes s-expressions and gets to the juicy bits of programming language semantics immediately: lexical scope, first class functions, objects, etc.

bendmorris
Second this. I'm writing a compiler now (https://github.com/kitlang/kit) and this book has been invaluable.

A few other tips:

* Use a parser generator. Parsing is more or less a solved problem; get it out of the way as fast as possible.

* Writing a language that compiles to another language is very helpful as you can often borrow the underlying language's implementation of a feature. Doubly helpful if you can leverage the underlying language's libraries for things like syscalls.

* Make a todo list (I like Trello for this) full of self-contained tasks. Pick one at a time, think through how you would implement that feature, and go to work. Compilers look like a lot of work in the beginning, but if you take one step at a time, one day you'll look back and have accomplished more than you realize. The list can also be helpful to avoid scope creep; add any new ideas to your backlog and deal with them later.

* Write unit tests, as you'll very likely want to refactor something down the line. Once your compiler becomes complex enough, add functional tests that verify entire programs can compile and run and produce the expected output.

nakkaya
I maintain a programming language called Ferret [1]. You can read through the manual, it is a literate program, covers everything you need to implement your own lisp. Compiler, optimizations, runtime, garbage collection etc. [2] overlaps with [1] covers how to compile a restricted subset of Clojure to C++. If you are interested in interpreters [3] has an implementation of the "A Micro-Manual for Lisp - not the whole Truth" in C.

[1] https://ferret-lang.org/ [2] https://nakkaya.com/2011/06/29/ferret-an-experimental-clojur... [3] https://nakkaya.com/2010/08/24/a-micro-manual-for-lisp-imple...

derekp7
I'd like to offer a bit different approach. First, start off by making a simple calculator program, that uses RPN syntax. This is dirt simple to implement -- read a line of input, if it is a number then add it to a stack. If it is a math operator, then call a function handling that operator (addition, multiplication, etc) on the last two items in the stack and push the results back on the stack.

Now add error handling (i.e., unrecognized operators, or stack underflow condition) -- figure out what you want to do, such as crash the interpreter with an error message, or return an error and let the user continue.

Now, read up on the Shunting Yard algorithm. This lets you take a regular (infix) math expression, and convert it to RPN (postfix) notation, which you can then feed directly into the RPN interpreter ("stack machine") that you just wrote.

Now look at handling parentheses, which should be covered in the same explanation of the Shunting Yard algorithm.

Next, add in variables in the original stack language, and figure out what minimal changes to the second piece (the algebraic expression parser) you need to do to get it to handle variables.

Finally, add in functions, and you have a simple language. I followed this exact formula when putting together a toy language many years ago, after which I learned how much I didn't know that I didn't know about language design. But I know enough now for a second shot.

Oh, and some other resources to study that may help -- Look for the reference books for the Postscript language. The "Blue" book teaches you Postscript, and I believe it is the "Red" book that tells you enough of the internals for you to write your own Postscript interpreter (or to at least get inspiration on creating you own version of a Stack machine interpreter).

marianoguerra
Write lexers and parsers for data formats, JSON and EDN are two good starting points.

write a forth or lisp lexer, parser and interpreter.

then write a small language that compiles to a target, like js, make sure your language is close in semantics to the target language to avoid headaches.

chaoticmass
Probably the greatest amount of growth I've had in my lifelong programming journey was during the years when I was working on making my own scripting language. I think the skills I learned have shaped how I approach other programming project. Think debugging is hard? Try debugging why your script interpreter isn't running a given script correctly.
unilynx
Decide first whether your language will be case-sensitive or case-insensitive. Then regret your choice forever.
arh68
There's more than a few ways to do it.

Ohm [0] is a good place to start. It's a parser generator. If you can understand the math example [1], you can probably realize how things get built upwards. Then you can focus on what you want your language to do, how you'll interpret it, what problems it would express, &c.

[0] https://ohmlang.github.io/

[1] https://github.com/harc/ohm/blob/master/examples/math/index....

Also consider reading about OMeta, if Ohm isn't your thing.

guidoism
Ohm’s web playground is an awesome way to learn how to build up a language from scratch. I’m in the process of porting Postscript to it and it’s amazingly easy.
carapace
FWIW Prolog DCGs (Definite Clause Grammar) are very similar to Ohm/OMeta.