Simple steps to implementing a programming language
kjetilvalle.com
kjetilvalle.com
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.
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 ), 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)
Once I've got a semantics I like, I'll probably do a second pass to come up with a new syntax if I haven't decided I'm done with the project. By then I'll have written plenty of test cases using the first syntax, so I should have a much better idea of what I'd like to get out of a more complex one.
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.
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.
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
[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...
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.
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.
https://en.wikibooks.org/wiki/Write_Yourself_a_Scheme_in_48_...
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.htm...
[1] http://cs.brown.edu/courses/cs173/2012/book/
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 ;)
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.
" 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
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?
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.
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.
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".
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.