Live data from Hacker News

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

news.ycombinator.com

41–50 of 105 posts

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

#41
To understand how computers work is the reason that compilers is the capstone class in many CS programs. It unites automata with algorithms and machine code, bringing everything together in one program. I'm pretty sure I wouldn't have gotten through this exercise myself outside college.

A lot of the resources out there are going to assume you have one or two sides of this triangle already and are ready to bring it all together. If you don't then you'll probably feel like you're in over your head.

I would recommend checking out "Let's Build a Compiler". It's a bit old-fashioned but at least things are pretty simple. https://compilers.iecc.com/crenshaw/

Different flavors of Markdown are not a bad place to start. Try and find something with a real syntax. As I recall, the original/official version is defined by a Perl program and has no true grammar. But other variants probably do.

SQL is not simple. Just the parser for PostgreSQL's dialect was around 1500 lines of code, last I checked. Although, if you did a small subset, maybe it wouldn't be so bad.

I really like the book Semantics with Applications which discusses the meaning of different programming languages. When I was starting out, it seemed to me like there was a lot riding on the syntactic differences between languages like C and Pascal. Now having seen the fringe, a lot of those differences are not as significant to me as they were before. This book helps you drill into what makes some languages different below the surface, and how to model those differences formally.

I think it's eminently possible to make a small language, like "While", in a few pages of code. I would start with a very simple unambiguous grammar, and a little interpreter for it, but if you really want the full experience, generate assembler. This paper sort of presents the language I'm talking about, but there is a lot here about type theory and semantics that may not be interesting to you, so just ignore that. https://arxiv.org/pdf/1603.08949.pdf When I took compilers ~15 years ago, we generated code for nasm because gas syntax was too weird for us. Anyway.

Another approach that looks interesting to me is "many small steps": http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf The idea here is to start with a program that only knows about integers, but handle everything end-to-end. Then you slowly add features one-by-one, but in an end-to-end fashion. I think this would be a lot easier to iterate and it hearkens back to Crenshaw's approach.

A lot of compiler construction material focuses on Lisp and Scheme. This is because it sort of hides or ignores the parsing problem. You will probably have to learn some other languages to build a compiler; it wouldn't hurt to know some Lisp or Scheme to be able to access these resources. A lot of people build a Lisp-like language as their first for this reason too. Just something I'm pointing out.

Anyway, it's a noble goal and best of luck!

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

#42
post #37

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 c…

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.

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

#43

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 f…

I totally agree here, if you want low level I think j1 forth (http://www.excamera.com/sphinx/fpga-j1.html) and for lisp I really liked http://www.buildyourownlisp.com which uses modern C libraries so it polishes your C knowledge too.

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

#46
There's a ton of great responses in this thread. Allow me to go a bit meta: this is a big topic, and as you enter it, you'll eventually find out which parts of it appeal to you. Do you care about parsers? Type theory? Garbage collection? Code generation/optimization? Notation as a tool for thought?

Ever since I started programming, the idea of writing my own language was a sort of "white whale". I have one idea for a language that I think could be usable in a very particular domain. For that, I wrote a very primitive tree-walking interpreter (terrible performance, very technically uninteresting). The idea for the language was what I wanted to explore. I recently started writing a regex->jvm bytecode compiler. That's much lower level, and if I stick with it, performance will be what I optimize for. In neither case did I do anything interesting with parsers, though I used to love learning about new parsing techniques.

In that vein, see dfox's suggestion to "just use hand built recursive descent parser and some set of ad-hoc lexical analysis subroutines". That's the fastest way to get started, whether or not it'll be the best in the long term.

So, my advice is to explore and figure out which things you're interested in, and what you want to accomplish. That will tell you where you want to invest your time.

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

#47
post #36

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 f…

Someone wrote an amazing write-your-own lisp using Python tutorial, I found it amazingly consumable and it only took a weekend: https://github.com/kvalle/diy-lang

There's also Make a Lisp: https://github.com/kanaka/mal/blob/master/process/guide.md

It's available in a variety of languages and has a nice guide (linked) to various steps.

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

#48
For many people, and I include myself in that group, the class in compiler and language design is where all of the concepts being taught in CS came together into a bigger and more rich picture. A common observation that it was like learning "how" music was written rather than just "playing" music.

That said, everyone who learns to program usually learns more than one language. For me, it was after about the fifth language that the syntax of a particular language fell away and what remained was the algorithm that was being expressed. It was this ability to see the algorithm distinct from the syntactic construction of the language that lets me see where the language is "helping" and where it is "hurting" in expressing the algorithm.

The advice then for starting points for developing new languages would be to take some algorithms you know well and implement it in as many languages as you can find. Ideally you'll have at least one imperative language (BASIC, C, Fortran, COBOL all qualify), one functional language (haskell/APL), one lambda language (lispish), and one semantic language (Ada, Mesa, Modula) Typically sorting, string handling, and asynchronous execution (or schedulers) all make for good algorithms to try. See what is "easy" and what is "hard" to implement based on the features the language brings to the table.

Then optimize for 'easy'.

That will gives you verbs and structure that support your need, once you have those then giving them names and a syntactic structure is fairly straight forward.

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

#49
There is much good advice given by others here regarding the implementation of languages. However, if you really want to get into language design, there is one area that you should/need to understand (as far as I am concerned) and that is how to specify the meaning of your language and its constructs. If this is not done, you end up with too many gotchas and special cases in how you will do things.

I have found too many language designers have not thought about this clearly enough. When you go to actually use the language, you will suddenly find all sorts of oddities in how you construct the program you are trying to write. Undefined behaviour is a curse, implementation defined behaviour is a curse.

If your language allows you to write something and it passes the compiler, then make sure that it is completely defined so that no matter what there are no subtle surprises.

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

#50
If at any point you find yourself looking for parser generators, Nearley JS is a fun tool for experimenting with lightweight grammars. (Emphasis on lightweight - it's a javascript library.) It has good docs as well. If you're interested in the Earley algorithm, you can run it in a nodejs shell and look under the hood at the data structure, step-by-step as it scans the string.

https://nearley.js.org/

Post reply on HN