7 ms·

Simple steps to implementing a programming language

112 points by kvalle 12y ago

thomassvensen 12y ago
Fun and useful tutorial, great work, Kjetil!
- kvalle 12y ago
  Thanks!
NaNaN 12y ago
Yet another LISP-like language parser tutorial. Just like Learning ??? Programming in ?? days. This is just the beginning, guys. LISP-like languages are not always great. (I'm not to look down this tutorial! Really!) I prefer imperative programming language parser tutorial. Every time I see such title, I will think of LISP.
- vidarh 12y ago
  If you want an imperative tutorial then the Crenshaw tutorial [1] or Nicklaus Wirth's book Compiler Construction[2] are great starting points. [1] http://compilers.iecc.com/crenshaw/ http://compilers.iecc.com/crenshaw/ [2] http://www.ethoberon.ethz.ch/WirthPubl/CBEAll.pdf http://www.ethoberon.ethz.ch/WirthPubl/CBEAll.pdf
  - NaNaN 12y ago
    Thank you. I have read Crenshaw's tutorial before, and I think I should get some time to translate it with modern language with unicode support to make more fun. :)
- Elrac 12y ago
  I'm admittedly nitpicking here, but I think "(non-)imperative" is not a useful label for characterizing Lisp-ish languages. Some Lisps, like Clojure, are rather functional; others, like Common Lisp, are considered imperative. For the distinction you're looking for, I'd like to suggest "C-like" or "Algol-family" instead for those languages which work with sequences, conditionals, loops and probably braces and semicolons.
mqsiuser 12y ago
During my project I was once at the point where I actually implemented my own (interpreted) scripting language. I have never thought that I'd be one of the guys who creates something like this, but once you are so fed up with something over the years (and I was with ESQL just for being "closed source") you'd just may be starting to go for it and just try out an dig into it. And it works. I am now saying things like "If I'd need a JIT compiler for it, I'd write one. I'll look at everything and evaluate if possible and how to be done." Inventing wheels is great for learning and I am now back to Java (good enough ;)
throwaway13qf85 12y ago
Nice work. There's a similar article which uses Haskell as the base language instead of Python, which is also worth reading (this is actually how I learned both Haskell and Scheme..!) https://en.wikibooks.org/wiki/Write_Yourself_a_Scheme_in_48_Hours https://en.wikibooks.org/wiki/Write_Yourself_a_Scheme_in_48_...
- kvalle 12y ago
  Nice! I've actually just started learning me some Haskell (for great good). Will definitely have a look at that wikibook.
- dmunoz 12y ago
  There is also SICP Chapter 4: Metalinguistic Abstraction. More precisely, 4.1 The Metacircular Evaluator [0]. Chapter 5 is about compiling to a toy register machine, as well. I'm a big fan of the approach taking in Programming Languages: Application and Interpretation (PLAI). The Brown course from 2012 has video lectures available [2]. This one uses what is very close to Racket as the implementation language. It's typed, and called plai-typed. The course these days uses the later chapters of Programming and Programming Languages (PAPL). This uses a new language, Pyret [3]. It's a bit more clear, due to the implementation language and source language having obviously different syntax, compared to plai-typed vs. the s-expression based language implemented. [0] https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-26.html#%_sec_4.1 https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-26.htm... [1] http://cs.brown.edu/courses/cs173/2012/book/ http://cs.brown.edu/courses/cs173/2012/book/ [2] http://cs.brown.edu/courses/cs173/2012/Videos/ http://cs.brown.edu/courses/cs173/2012/Videos/ [3] http://www.pyret.org/ http://www.pyret.org/
Udo 12y ago
Inventing your own programming language is something I can highly recommend. If you've never done it before it will dramatically broaden your programming horizon. It's a journey. About a year ago I decided to make a language mainly because I wanted to experiment with some programming paradigms. I had made little domain-specific "languages" many times before, but this was going to be different. I'd suggest that you try to figure out most things on your own, however. It's way more rewarding to think about the problems you're trying to solve, go ahead and implement them. That way you're also forced to have eye-opening meta thoughts about programming in general. Only after you've gained some appreciation for the issues involved, look them up and see how other people solved them. This worked very well for me. Lisps and Schemes are certainly easier to implement than most syntaxes, but consider doing something else so you can get a better understanding of the complexities of parsing a non-Lisp. In my case, I did my prototype in Java, that's the lexer, parser, runtime and standard library. While I wouldn't necessarily want to do it that way again, it was a great learning experience and I was pleased with the result. About two months ago I decided to give it another try, but this time in C, using the Lua codebase. So far this has been a very good choice for a second stab at the idea. And I was pleased that I could recognize a lot of the patterns in the Lua codebase where I had implemented equivalent parts in my earlier project. If I hadn't taken the hard route back then, I probably would have a harder time now.
- kvalle 12y ago
  It's definitely a journey! And I agree that trying to figure out how the concepts for yourself is by far the most rewarding. I hope this tutorial can help people realize that it's not difficult to get started, and inspire them to get started exploring on their own.
- vidarh 12y ago
  While I agree with you that it's worth learning to parse something "non-Lisp", I think that starting with an s-expression type syntax is worthwhile for a first-time even if you want to eventually implement a non-Lisp, for the simple reason that parsing is "easy" and very well documented compared to code-generation. Unless your language has a particularly hairy grammar (Ruby, I'm looking at you...), figuring out how to parse it into your desired structure afterwards is fairly straight-forward in comparison. That's why I took the approach of bypassing the parser entirely with my compiler series ( http://www.hokstad.com/compiler http://www.hokstad.com/compiler ), where the first several parts involved going straight to code-generation from code simply abusing the Ruby Array notation. Then later adding a simple s-expression parser. I didn't even decide to turn it into a Ruby compiler for quite some time (in retrospect, had I planned to do Ruby from the very beginning, there are a few things I'd likely do differently, but not that much; the biggest issues with writing the series have been learning a lot of new things about how writing about code influences the entire process)
kabdib 12y ago
My rule of thumb when doing a new language: Write the debugger first, you're going to need it anyway....
- mcguire 12y ago
  Bah! If you need a debugger, you're not thinking hard enough.
  - WalterBright 12y ago
    Debuggers are crutches for losers. I use an oscilloscope to debug.
DougWebb 12y ago
This is nice, but I was hoping to find guidelines about designing the syntax for a new programming language. As others are saying, s-expression syntax is simple to parse because it's basically already structured like the AST. But s-expression syntax isn't so easy to develop in, especially for non-developers. Why non-developers? I'm interested in DSLs that are used to add plugin-type scripting capabilities, so that advanced non-developer users can extend behavior on their own. Think Lua, but more specific to the domain. As far as syntax, I'm thinking about something more like BASIC for its simplicity.
- derekp7 12y ago
  Take a look at the Shunting Yard algorithm -- this will go from standard (infix) to Postfix notation. And Postfix (RPN) is actually easier to interpret than Prefix (the main loop is about a half dozen lines or so).
- dragonwriter 12y ago
  > This is nice, but I was hoping to find guidelines about designing the syntax for a new programming language. As others are saying, s-expression syntax is simple to parse because it's basically already structured like the AST. But s-expression syntax isn't so easy to develop in, especially for non-developers. IME, the "especially for non-developers" part doesn't seem to be true. People who are exposed to s-expression syntax first don't seem to be any more likely to have problems with that syntax style than those introduced to programming with other syntaxes are with whatever syntax the are introduced to first; the people that are most put-off by s-expressions as a syntax of expressing programs are people who are attached to some other syntax first, and particularly people whose experience is with multiple languages all from the same syntax family, usually the ALGOL-style family.
platz 12y ago
Handy reference for those embarking on creating a new PL: http://colinm.org/language_checklist.html http://colinm.org/language_checklist.html
- Marcus316 12y ago
  While this is still amusing, and poignant, I don't believe the goal of the original link is to encourage people to try and compete with modern languages. For those of us (like me) who learn best by trying things out, a PL project is a great way to wrap your head around some of the more abstract concepts of modern programming languages (like closures, as mentioned in the post). Still, +1 for amusement.
mamcx 12y ago
This is great, but I want the other things that are important but forgotten: " We will not have: A proper type system Error handling Good performance And much, much more " Good performance is something that have a lot of literature, so can be avoided in this tutorials. I have been in this talk at lambda: http://lambda-the-ultimate.org/node/4929#comment-79628 http://lambda-the-ultimate.org/node/4929#comment-79628 Where is discussed where to talk about implement compilers. I ask about the other things that bother me: - Debugger/ Debugging experience - REPL - Tracing (ie: Dtrace or similar) and other things that I wish to understand before just make another parser. How build a "hacker news" for it? Exist some project I could use?
inetsee 12y ago
I would recommend the Racket tutorial, especially, the section on using Racket's macro system to implement a slight variation of Algol 60. Working through this tutorial would give you a foundation on building your own DSLs, as well as giving you a solid foundation on using Racket and its macro system itself.
- dmunoz 12y ago
  Could you please link to this? I didn't find anything when searching for the relevant keywords, or see anything of the sort at http://docs.racket-lang.org/ http://docs.racket-lang.org/.
  - inetsee 12y ago
    I found the starting point here "http://docs.racket-lang.org/algol60/index.html" http://docs.racket-lang.org/algol60/index.html".
    - dmunoz 12y ago
      I found that as well, but it is not what inetsee described in his post. I was interested specifically in "using Racket's macro system to implement a slight variation of Algol 60", which is not what that section or the Racket guide section on macros [0] does. It's not clear what was meant by "the Racket tutorial". [0] http://docs.racket-lang.org/guide/macros.html http://docs.racket-lang.org/guide/macros.html
_random_ 12y ago
... 8. Find someone to do the most boring part - IDE - for you (most OSS languages).

112 points by kvalle 12y ago

thomassvensen 12y ago

Fun and useful tutorial, great work, Kjetil!

kvalle 12y ago
Thanks!

NaNaN 12y ago

Yet another LISP-like language parser tutorial. Just like Learning ??? Programming in ?? days. This is just the beginning, guys. LISP-like languages are not always great. (I'm not to look down this tutorial! Really!) I prefer imperative programming language parser tutorial. Every time I see such title, I will think of LISP.

vidarh 12y ago
If you want an imperative tutorial then the Crenshaw tutorial [1] or Nicklaus Wirth's book Compiler Construction[2] are great starting points. [1] http://compilers.iecc.com/crenshaw/ http://compilers.iecc.com/crenshaw/ [2] http://www.ethoberon.ethz.ch/WirthPubl/CBEAll.pdf http://www.ethoberon.ethz.ch/WirthPubl/CBEAll.pdf
- NaNaN 12y ago
  Thank you. I have read Crenshaw's tutorial before, and I think I should get some time to translate it with modern language with unicode support to make more fun. :)
Elrac 12y ago
I'm admittedly nitpicking here, but I think "(non-)imperative" is not a useful label for characterizing Lisp-ish languages. Some Lisps, like Clojure, are rather functional; others, like Common Lisp, are considered imperative. For the distinction you're looking for, I'd like to suggest "C-like" or "Algol-family" instead for those languages which work with sequences, conditionals, loops and probably braces and semicolons.

mqsiuser 12y ago

During my project I was once at the point where I actually implemented my own (interpreted) scripting language. I have never thought that I'd be one of the guys who creates something like this, but once you are so fed up with something over the years (and I was with ESQL just for being "closed source") you'd just may be starting to go for it and just try out an dig into it. And it works. I am now saying things like "If I'd need a JIT compiler for it, I'd write one. I'll look at everything and evaluate if possible and how to be done." Inventing wheels is great for learning and I am now back to Java (good enough ;)

throwaway13qf85 12y ago

Nice work. There's a similar article which uses Haskell as the base language instead of Python, which is also worth reading (this is actually how I learned both Haskell and Scheme..!) https://en.wikibooks.org/wiki/Write_Yourself_a_Scheme_in_48_Hours https://en.wikibooks.org/wiki/Write_Yourself_a_Scheme_in_48_...

kvalle 12y ago
Nice! I've actually just started learning me some Haskell (for great good). Will definitely have a look at that wikibook.
dmunoz 12y ago
There is also SICP Chapter 4: Metalinguistic Abstraction. More precisely, 4.1 The Metacircular Evaluator [0]. Chapter 5 is about compiling to a toy register machine, as well. I'm a big fan of the approach taking in Programming Languages: Application and Interpretation (PLAI). The Brown course from 2012 has video lectures available [2]. This one uses what is very close to Racket as the implementation language. It's typed, and called plai-typed. The course these days uses the later chapters of Programming and Programming Languages (PAPL). This uses a new language, Pyret [3]. It's a bit more clear, due to the implementation language and source language having obviously different syntax, compared to plai-typed vs. the s-expression based language implemented. [0] https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-26.html#%_sec_4.1 https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-26.htm... [1] http://cs.brown.edu/courses/cs173/2012/book/ http://cs.brown.edu/courses/cs173/2012/book/ [2] http://cs.brown.edu/courses/cs173/2012/Videos/ http://cs.brown.edu/courses/cs173/2012/Videos/ [3] http://www.pyret.org/ http://www.pyret.org/

Udo 12y ago

Inventing your own programming language is something I can highly recommend. If you've never done it before it will dramatically broaden your programming horizon. It's a journey. About a year ago I decided to make a language mainly because I wanted to experiment with some programming paradigms. I had made little domain-specific "languages" many times before, but this was going to be different. I'd suggest that you try to figure out most things on your own, however. It's way more rewarding to think about the problems you're trying to solve, go ahead and implement them. That way you're also forced to have eye-opening meta thoughts about programming in general. Only after you've gained some appreciation for the issues involved, look them up and see how other people solved them. This worked very well for me. Lisps and Schemes are certainly easier to implement than most syntaxes, but consider doing something else so you can get a better understanding of the complexities of parsing a non-Lisp. In my case, I did my prototype in Java, that's the lexer, parser, runtime and standard library. While I wouldn't necessarily want to do it that way again, it was a great learning experience and I was pleased with the result. About two months ago I decided to give it another try, but this time in C, using the Lua codebase. So far this has been a very good choice for a second stab at the idea. And I was pleased that I could recognize a lot of the patterns in the Lua codebase where I had implemented equivalent parts in my earlier project. If I hadn't taken the hard route back then, I probably would have a harder time now.

kvalle 12y ago
It's definitely a journey! And I agree that trying to figure out how the concepts for yourself is by far the most rewarding. I hope this tutorial can help people realize that it's not difficult to get started, and inspire them to get started exploring on their own.
vidarh 12y ago
While I agree with you that it's worth learning to parse something "non-Lisp", I think that starting with an s-expression type syntax is worthwhile for a first-time even if you want to eventually implement a non-Lisp, for the simple reason that parsing is "easy" and very well documented compared to code-generation. Unless your language has a particularly hairy grammar (Ruby, I'm looking at you...), figuring out how to parse it into your desired structure afterwards is fairly straight-forward in comparison. That's why I took the approach of bypassing the parser entirely with my compiler series ( http://www.hokstad.com/compiler http://www.hokstad.com/compiler ), where the first several parts involved going straight to code-generation from code simply abusing the Ruby Array notation. Then later adding a simple s-expression parser. I didn't even decide to turn it into a Ruby compiler for quite some time (in retrospect, had I planned to do Ruby from the very beginning, there are a few things I'd likely do differently, but not that much; the biggest issues with writing the series have been learning a lot of new things about how writing about code influences the entire process)

kabdib 12y ago

My rule of thumb when doing a new language: Write the debugger first, you're going to need it anyway....

mcguire 12y ago
Bah! If you need a debugger, you're not thinking hard enough.
- WalterBright 12y ago
  Debuggers are crutches for losers. I use an oscilloscope to debug.

DougWebb 12y ago

This is nice, but I was hoping to find guidelines about designing the syntax for a new programming language. As others are saying, s-expression syntax is simple to parse because it's basically already structured like the AST. But s-expression syntax isn't so easy to develop in, especially for non-developers. Why non-developers? I'm interested in DSLs that are used to add plugin-type scripting capabilities, so that advanced non-developer users can extend behavior on their own. Think Lua, but more specific to the domain. As far as syntax, I'm thinking about something more like BASIC for its simplicity.

derekp7 12y ago
Take a look at the Shunting Yard algorithm -- this will go from standard (infix) to Postfix notation. And Postfix (RPN) is actually easier to interpret than Prefix (the main loop is about a half dozen lines or so).
dragonwriter 12y ago
> This is nice, but I was hoping to find guidelines about designing the syntax for a new programming language. As others are saying, s-expression syntax is simple to parse because it's basically already structured like the AST. But s-expression syntax isn't so easy to develop in, especially for non-developers. IME, the "especially for non-developers" part doesn't seem to be true. People who are exposed to s-expression syntax first don't seem to be any more likely to have problems with that syntax style than those introduced to programming with other syntaxes are with whatever syntax the are introduced to first; the people that are most put-off by s-expressions as a syntax of expressing programs are people who are attached to some other syntax first, and particularly people whose experience is with multiple languages all from the same syntax family, usually the ALGOL-style family.

platz 12y ago

Handy reference for those embarking on creating a new PL: http://colinm.org/language_checklist.html http://colinm.org/language_checklist.html

Marcus316 12y ago
While this is still amusing, and poignant, I don't believe the goal of the original link is to encourage people to try and compete with modern languages. For those of us (like me) who learn best by trying things out, a PL project is a great way to wrap your head around some of the more abstract concepts of modern programming languages (like closures, as mentioned in the post). Still, +1 for amusement.

mamcx 12y ago

This is great, but I want the other things that are important but forgotten: " We will not have: A proper type system Error handling Good performance And much, much more " Good performance is something that have a lot of literature, so can be avoided in this tutorials. I have been in this talk at lambda: http://lambda-the-ultimate.org/node/4929#comment-79628 http://lambda-the-ultimate.org/node/4929#comment-79628 Where is discussed where to talk about implement compilers. I ask about the other things that bother me: - Debugger/ Debugging experience - REPL - Tracing (ie: Dtrace or similar) and other things that I wish to understand before just make another parser. How build a "hacker news" for it? Exist some project I could use?

inetsee 12y ago

I would recommend the Racket tutorial, especially, the section on using Racket's macro system to implement a slight variation of Algol 60. Working through this tutorial would give you a foundation on building your own DSLs, as well as giving you a solid foundation on using Racket and its macro system itself.

dmunoz 12y ago
Could you please link to this? I didn't find anything when searching for the relevant keywords, or see anything of the sort at http://docs.racket-lang.org/ http://docs.racket-lang.org/.
- inetsee 12y ago
  I found the starting point here "http://docs.racket-lang.org/algol60/index.html" http://docs.racket-lang.org/algol60/index.html".
  - dmunoz 12y ago
    I found that as well, but it is not what inetsee described in his post. I was interested specifically in "using Racket's macro system to implement a slight variation of Algol 60", which is not what that section or the Racket guide section on macros [0] does. It's not clear what was meant by "the Racket tutorial". [0] http://docs.racket-lang.org/guide/macros.html http://docs.racket-lang.org/guide/macros.html

_random_ 12y ago

... 8. Find someone to do the most boring part - IDE - for you (most OSS languages).