It's slightly less in depth than the roadmap of "Crafting Interpreters", but again, it exists right now.
I am in the process writing a semi-natural query language (boolean logic) targeted at domain experts (in this case biomedical researchers) that compiles to either database queries (e.g. SQL) or a function call for arbitrary logic. The goal of the compiler bit is to abstract away where the data ultimately lives (similar to GraphQL) or how it is structured.
So the code is all done, and now "all" that's left to do is write and edit all of the prose. Which, of course, is really the hardest part by far.
Strongly complemented by Sedgewick's Algorithms in C.
//> SomeName not-yet
in the code mean? Are they meant for some kind of automatic processing? Its a bit hard to read with all of them there...
I know it makes the code hard to read. I should probably slap together a little script to strip them out.
I am currently working on Scheme R5RS implementation in Java. It is a hobby project, but I'm really enjoying it. It is somewhat enlightening.
Look forward to reading the Optimization chapter: I couldn't find much useful and practical info on that. I think it is quite easy to implement your interpreter, but it is really difficult (at least for me) to make it fast.
Can anyone recommend any articles or books with common optimization tricks and techniques?
> Look forward to reading the Optimization chapter: I couldn't find much useful and practical info on that.
There's not too much depth in that particular chapter. The whole second part is really about implementing an interpreter (fairly) efficiently in C. As you probably know, you have to think about performance at every level—your object model, bytecode format, hash table implementation, etc.
If you'd like a sneak peek, the code for the entire book is actually done already (!). You can see which snippets go into each chapter cloning the repo then running:
There are a ton of optimization tricks that are specific to Scheme and Lisps and a lot of literature behind them. Macros and eval make it a lot harder. It's pretty dense, but I liked "Lisp in Small Pieces" a lot.
(See also Lua's upvalues for a way to optimize closure variable access that's a bit simpler than his display closures).
Yes! In fact, that's how the C version of the interpreter in my book implements closures. It's pretty brilliant. <3 those Lua folks.
Or perhaps do you have a link about how it works?
Now I remember it uses LGPL as the license. I understand the reasoning, but I've always viewed the freedoms as giving the user freedom over the implementer...kind of just trading power.
Scheme/lisp based languages and Haskell are a great choice for this kind of project.
If you are interested in the subject you could take a look to my blog (https://tomassetti.me) I write 1-2 posts per week on building languages. Most of the time I talk about DSL.
On a side note, to anyone interested in an overview of high-level language features and what their implementation requires, I can wholeheartedly recommend Michael Scott's Programming Language Pragmatics. It doesn't go into implementation details, but tells you a lot about the historical choices and implementation possibilities of (mostly) mainstream languages.
I really like your blog, I have read all of it, some posts even 2-3 times, and not only because of the content, but your writing style. I will probably read this book too ;)
Also, I think Magpie is awesome.
Thank you very much!
A much less involved language-building tutorial that's available now is Beautiful Racket. Racket is a Scheme, but it's also specially outfitted to be a language workbench.
However my one tiny complaint is that the sign-up box is on every page, and even after I've signed up, it still has to be closed every page I go to.
I'll try to resurrect that for this one.
Some of us have written 1 or 2 dynamic, interpreted languages, feel pretty comfortable with those concepts, and are interested in transiting to more advanced, static type systems and writing a good type checker.
Anyone up for writing such a high-quality book as this one on statically-typed languages, ideally functional languages? The only decent books I've found on the subject are 20-30 year-old textbooks. I'm watching "Write You a Haskell" with interest (and have partially read it), even though I'm more into ML and Scala than Haskell, but it's still pretty unfinished.
There's also the plzoo, which is a great resource but not a book.
Oh, and I definitely need to read Pierce's Types and Programming Languages textbook, I've ordered it and need to sit down with it. I suspect it will be very enlightening.
But a more approachable book on statically-typed languages in the same genre as this one is (popular, less academic) would also be welcome.
If you're looking for a book on statically typed functional languages, I think Appel's book is canon. From what I've heard, the C and Java ones aren't very great. It's worth learning enough ML to get through that version because ML is clearly the language Appel thinks in.
I assume you're talking about something like "Modern Compiler Implementation in ML"? That book is still a good starting point, and once you get a basic implementation going you'll be in a good position to start learning about and implementing more advanced features. You'll end up teaching yourself as you figure out how to add features to your own codebase.
edit: fix title
If you're focused on benchmark numbers, dynamically typed languages are much more challenging to squeeze performance out of better code generation.
You can also add static type inference and consistency checking to a dynamic language, and indeed some systems do in the name of better
Add in a static typing, type inferencing, and type checking, and that all becomes much more complicated, at least from this learner's point of view. From how highly upvoted my comment is, I suspect I'm far from being alone here. Learning, understanding, and implementing Hindley-Milner by itself was harder for me than learning how to put together a basic interpreter for a simple scheme. And I think a big part of that is the dearth of learning materials for things like Hindley-Milner and related concepts, whereas there are 100 books and tutorials on how to implement a Scheme interpreter in language X.
Finally, if you're talking about language performance, then yes clearly it's much harder to squeeze performance out of dynamic languages. But I'm talking about learning exercises here, not production programming languages.
dearth of learning materials for things
 L. Damas, R. Milner, Principal type-schemes for functional programs.
map : ∀α ∀β ((α → β) → (α list → β list))
 - Former C# language designer, Roslyn compiler team, etc.
 - https://ericlippert.com/?s=excessive&submit=Search
The thought that somebody would not be able to understand the type of map had not occurred to me, because I'm surrounded by people with a strong maths/FP background. Shows just how narrow-minded I am.
- How to ensure that the inference algorithm is correct.
- How to design typing systems that are expressive, yet lightweight, and have enough type inference to be usable in practise.
- How to deal with concurrency and parallelism.
None of these problems is really solved. In practise even making type inference fast is a challenge, e.g. in older versions of the Scala compiler, type inference was really slow due to implicits.
Pierce's book is as approachable as you're likely to see with respect to type systems. You mostly just have to dig in.
But it seems to be there's a place for a more popular book on type systems and making a statically-typed language, in the vein of this Crafting Interpreters book (and others like it).
Perhaps I'll read TaPL, write a nice statically-typed language, and then write the book I'm looking for.
I think you can replace the math with intuitive diagrams and be a little less rigorous and that would be a book for the masses.
TaPL requires you to learn a lot between coding sessions too which may put off more practically minded folk.
If I wanna to implement a dialect of ML, I haven't' find a simple explanation in how implement product/sum types, modules & pattern matching.
Yet, tons of type inference and other less common things.
ie: The basics stop fast and suddenly jump into something else.
Exactly. I mean, how in the world to implement pattern matching in ML-like languages? And ADTs? These are exactly the kind of subjects I'd like to see covered in a more advanced book on building interpreters or compilers for statically-typed languages.
* simply typed lambda calculus
* Hindley-Milner type inference
* bidirectional typing
All of this (except maybe the first part) is easily learnable either from Wikipedia, the original papers, or recent tutorials.
It's (hopefully) very well commented, so it should clarify a bunch of concepts for newcomers.
 - https://github.com/prakhar1989/type-inference
Are static type systems more advanced than dynamic type systems? This sounds surprising, given how much more one can do with a dynamic type system.
Anyone up for writing such a high-quality
book as this one on statically-typed languages,