A decade of developing a programming language

I'm in the same boat as you -- here are the two best resources I found:

https://mukulrathi.com/create-your-own-programming-language/...

https://jaked.org/blog/2021-09-07-Reconstructing-TypeScript-...

I read through the first 10 chapters of TAPL, and skimmed the rest. The first 10 chapters were good to remind myself of the framing. But as far as I can tell, all the stuff I care about is stuffed into one chapter (chapter 11 I think), and the rest isn't that relevant (type inference stuff that is not mainstream AFAIK)

This is also good:

https://github.com/golang/example/blob/master/gotypes/README...

And yeah some of us had the same conversation on Reddit -- somebody needs to make a Crafting Interpreters for type checking :) Preferably with OOP and functional and nominal/structural systems.

---

Also, it dawned on me that what makes TAPL incredibly difficult to read is that it lacks example PROGRAMS.

It has the type checkers for languages, but no programs that pass and fail the type checker. You are left to kind of imagine what the language looks like from the definition of its type checker !! Look at chapter 10 for example.

I mean I get that this is a math book, but there does seem to be a big hole in PL textbooks / literature.

Also I was kinda shocked that the Dragon Book doesn't contain a type checker. For some reason I thought it would -- doesn't everyone say it's the authoritative compiler textbook? And IIRC there are like 10 pages on type checking out of ~500 or more.

The bigger challenge is doing the pattern matching and mainly the exhaustiveness checking of patterns which aren't constructors of a sum type, but for example integer intervals.

Simon Peyton Jones together with others wrote a relatively easy to read book about the writing of Miranda (Haskell), which even includes a simple explanation of lambda calculus, so it includes everything you need to know about the theory, more or less: "The Implementation of Functional Programming Languages" 1987, https://www.microsoft.com/en-us/research/wp-content/uploads/...

I highly recommend https://github.com/sdiehl/write-you-a-haskell as it is very developer friendly. It’s not complete, but it really gets the gears turning and will set you up for writing your own Hendley-Milner style type checker.

> I would love to see a book as gentle and fun as _Crafting Interpreters_ but about making a static ML like language without starting with hardcore theory. (Bob, if you're listening, please make a sequel!)

I don't think an ML-like language is the best option. I would start with type-checking something simple like C or Pascal: no overloading, generics, type inference, anonymous functions. Just plain old subroutines and declared types on everything, arrays and structs as the only composite data structures.

Then you could add implicit conversions, type inference for locals (not that hard), subtyping, target type inference for anonymous functions, generics and maybe overloads if you're brave enough.

I had a similar experience this year as I’m working on an ML-cousin to Golang. I actually found that ChatGPT (gpt4) was really good and breaking down the step of implementing a Hindley-Milner type system in a language I could understand. It could also provide follow up clarifications to my questions too. I then implemented it a small bit at a time and as the complexity grew I started to better understand the algorithm.

EDIT: ChatGPT could actually demonstrate the whole process for type checking small chunks of code, including: assigning them type variables, collecting constraints and then unification. It would even then point out if there was a type error in the code snippet!

I've mentioned this in a different comment, but I've written several articles on type inference, trying to make the topic more approachable:

https://gilmi.me/blog/tags/type%20inference

If you find that helpful, I've made more content on compilers (including live coding a compiler, without narration) which should be easily reachable from my website.

I would love to know more about what the author found difficult regarding type checking. As long as you don't screw up your semantics to the point of needing a full blown constraint solver there should be no issues.

Edit: by "screwing up semantics" I mostly mean the combination of overloading and implicit conversions, which is known to cause issues in Java, C++, etc.

I’ve written about this at some length, but long story short: type modeling and semantic checking is intimately connected to the language semantics, so aside from very simple “look at the properties of the underlying nodes, derive properties of the current node”, it is hard to present any generic approach. In fact, there are many possible way to approach modeling types even with the exact same semantics, leading to different trade offs (just compare different C compilers and you’ll see!).

So this is actually harder to do that it might seem. The best advice I have is to contribute to a compiler or two and understand their semantic checking model.

> about making a static ML like language without starting with hardcore theory.

The book Applicative Order Programming: The Standard ML Perspective has you implement an ML-like language at the end (the book is mostly about programming in Standard ML itself). Chapter 10 covers type checking and type inference. Chapter 11 covers interpretation via graph reduction. Chapter 12 covers compilation of the ML-like language to an abstract stack machine. The code is all in Standard ML. It's very direct and practical without getting bogged down in theory, although it does talk about theory, and it's not as gentle and fun as Crafting Interpreters.

It was published in 1991. It's on libgen; I'd recommend downloading a PDF and reading those chapters in order to judge for yourself.

I've written a type checker or two. My experience: https://lambdaland.org/posts/2022-07-27_how_to_write_a_type_...

I left some links/references to books that helped me out.

Might this help? I wrote it: https://azdavis.net/posts/define-pl-01/

“Modern Compiler Implementation” by Appel is definitely worth a look. I read the ML version, and the code is really clean/readable (not sure about the C and Java versions).

> sometimes a PL has to go down an unconventional path to make something new.

Absolutely, just look at Haskell as an example.

> most important part is figuring out who is going to use the PL and what problems they are solving.

Completely agree. Rust and Go have received a lot of criticism over the years, but I think that is often down to them not being as general purpose as many people try to claim. The creators had particular users and use cases in mind.

I disagree, as somebody who has also worked with tons of type-hinted Python code. Gradual typing is obviously worse than real static typing, but it's a step up from full dynamic typing. It has caught many bugs for me before hitting them in runtime, and provides good documentation about what I can expect a function to accept and return without forcing me to read prose.

Type hints don't provide any safety, though. That was never the goal, given that they're strictly optional and don't really exist at runtime anyway (though I have written some experimental monstrosities that used annotations for code generation at runtime). They're documentation in a standard form that static analysis tools can leverage.

I really can't imagine a situation where having type hints in Python is worse than simply not having them. They're not the worst of both worlds, they're a compromise with some of the benefits and drawbacks of each.

Any? I regularly find bugs. I don’t find every bug, but finding some bugs is better than none. Especially for the minimal cost of writing annotations.

How is it worse than no typing? If you're not testing adequately because you think type safety is enough, you done f'd up.

Gradual typing is great. The parts you want precision on are statically typed, the parts that don't matter dynamic, and they fit together sanely at the language level.

Writing type annotations in comments for an optional preprocessor to pass judgement on before the actual implementation ignores them is a bad thing. But that's on python, not on gradual typing.

(An any type + static is also fine if you have a way to retrieve type information at runtime, and there's a sense in which template instantiations of a generic function and a function taking arguments of type any are the same thing as each other)

Python's type hints are just that, hints. They aren't static type annotations. Cython uses gradual typing, but the mainstream Python implementation does not actually offer gradual typing. It's still dynamically typed, but with an annotation mechanism that lets other tools do some analysis for you.

It's not the gradual typing. It's that static typing gives you the illusion of some safety where there isn't any.

I know someone that was on the Dart team and they say the same thing.

> only 3 years, because they were targeting an existing platform. Clojure took only 2 years and was d̶e̶v̶e̶l̶o̶p̶e̶d̶ ̶b̶y̶ targeting a single person.

Clojure is a lisp, it basically got to skip the parsing and lexing stages

> The only "good" programming language is the language I make! Everybody thinks different

Yeah. There's always one little thing or another that bothers me in every language I've learned. Guess I've just come full circle now that I've finally made my own. No doubt it will bother someone else too. If anyone ever uses it.

Kernel[1] has the ability to make scoping more abstract, but in a clean way which doesn't introduce the "spooky action at distance" of full dynamic scoping. It's an improvement on the older fexprs.

Essentially, you have a lambda-like combiner called an operative which does not reduce its operands, and implicitly receives a reference to the caller's dynamic environment as an additional argument. The operative body can then optionally evaluate anything as if it were the caller, with even the ability to mutate the caller's local scope. The parent scopes of the caller are accessible for evaluation, but not mutation. You can only mutate an environment for which you have a direct reference - and the environments themselves are first-class values which you can pass around and store in other environments. It is only possible to mutate the parent environment of a caller if the caller's caller has passed a reference to its own environment, and the caller forwards that reference explicitly.

You can create empty environments or environments from an initial set of bindings, and build on them from there, and you can also isolate the static environment from a callee, ensuring that only a limited set of bindings are accessible to the callee. In effect, this enables a kind of "sandboxing" approach - where you can easily do things like load an external plugin which can be written using a limited subset of Kernel features, and only access the specific functions of your host program which you allow. It provides a lot of abstractive power, with the ability to have things like types and classes defined as libraries. The operatives can introduce "sub-languages", which can simulate the behavior of other language semantics.

As you suspect, this runs pretty slow because it's almost impossible to optimize ahead-of-time. A given piece of code is just a tree of symbols and self-evaluating atoms, and the symbols in some code are only given any functional meaning by the environment it is evaluated in. Kernel busts the myth that "compilation vs interpretation is just an implementation choice," and explores what can happen when we go all-in on interpretation. The author has written about the nature of interpreted programming languages and how this differs from compiled languages.[2]

There are opportunities to have compilation and performance without much loss of abstractive power, but this is not a focus of Kernel - whose design goals are described at detail in the report. I've done a lot of R&D on making performance acceptable for a Kernel-like language. The main insight is that you should be able to make some assumptions about the environment passed to an operative without knowing anything else about the environment. I do this by modelling environments as row polymorphic types, where the operative specifies a set of bindings it expects the caller's dynamic environment to contain, complete with type signatures, and assumes these bindings behave in some specific way. (Eg, that the binding `+` means addition, which is in no way guaranteed by Kernel, and that the type signature of `+` is `Number, Number -> Number`).

---

A mostly complete implementation of Kernel: https://github.com/dbohdan/klisp (Cloned from Andres Navarro's bitbucket repo which is no longer available).

Some performance improvements of klisp, with a lot of hand-written 32-bit x86 assembly: https://github.com/ghosthamlet/bronze-age-lisp (Cloned from Oto Havle's bitbucket repo, also no longer available).

Another implementation of Kernel, with some examples of defining records, classes, objects, generators etc as libraries: https://github.com/vito/hummus/tree/master

---

[1]:http://web.cs.wpi.edu/%7Ejshutt/kernel.html

[2]:https://fexpr.blogspot.com/2016/08/interpreted-programming-l...

> Lisp is the easiest language to parse that I've ever seen, managed to write a parser by hand.

I've written a dozen or so parsers for different languages by hand: the parser is easy regardless of the syntax you choose. The complicated bit is always compilation/interpretation.

The biggest value I see to using S-expressions isn't the time saved in writing a parser, it's reducing the amount of bikeshedding you'll be tempted to do fiddling with syntax.

I found that a naive frontend for a language is not that big of a deal with something like ANTLR. The benefit is that you have a formal grammar syntax description, and you can iterate on that endlessly without too many code changes down the line.

I see lisp as sort of "no syntax". It's basically the AST. Which is a good thing, you can concentrate on the compiler and add syntax later. If you are working on a compiler for a non lisp PL, it makes sense to log the AST after parsing, as a lisp, as a readable AST.

Sigh. Please don’t refer to the rather exceptional nature of Zig’s self hosting. There has been an insane amount of work put into the Zig compiler by various contributors. Probably easily eclipsing the effort to write two separate compilers. The whole WASM deal comes AFTER they essentially built the compiler both in C++ and Zig to reduce bootstrapping steps. That just addresses the bootstrapping cost and not the fact that you have to build the compiler at least twice - and if you do it before 1.0 - more than twice. Cargoculting Zig’s development isn’t going to give you Zig’s success. Zig is successful because of Andrew presenting a vision of a language that lots of people was attracted to, and then cultivating the community well. It’s a well known fact in the community that the first C++ compiler had to go because it wasn’t well written, not because self hosting is great.

Oh that's a great point! Didn't someone give a talk about that too?

Pursuing gradual typing makes sense when you've got an established dynamic language and want to incorporate typing into it (forget Elixir, let's just look at the massive success of TypeScript). But as OP's recommendation says - "for new languages", gradual typing has lots of costs and fewer benefits.

To put it in other terms: my informal impression is that the dynamic "features" of TypeScript are used grudgingly; the community strongly pushes towards strictness, eliminating anys, preferring well-typed libraries, and so on. There's little appetite to - in a single project, unless absolutely required - mix-and-match dynamism with staticness, which is the thing that gradual typing gets you. Rather, it feels like we're migrating from dynamic to static and gradual typing is just how we're doing the migration. But in the case of a new language, why not just start at the destination?

I think the author's recommendation has some needed context:

> Recommendation: either make your language statically typed or dynamically typed (preferably statically typed, but that's a different topic), as gradual typing just doesn't make sense for new languages.

The "for new languages" part is really important. Gradual typing makes a lot of sense when you are trying to retrofit some amount of static checking onto an existing enormous corpus of dynamically typed code. That's the case for TypeScript with JavaScript and Elixir with Elixir and Erlang.

Well, there's no memo (real or as a manner of speaking). It's just this person's preference.

I think gradual typing is a nice concept, and his arguments against it amount to "gradual typing is not stating typing", which is like the whole point. E.g. he goes on how the compiler can't do some optimizations on functions using gradual typing, but, well, it isn't supposed to anyway.

The benefit of gradual typing is that you can make your program fully dynamic (e.g. for quick exploration), and if you want more assurances and optimizations make it fully static, or if you just want that for specific parts, do them static. And you have the option to go for any of those 3 things from the start.

What you can do is the opposite, integrate a “dynamic” type into a statically-types language, like C# does: https://learn.microsoft.com/en-us/dotnet/csharp/advanced-top...

This lets you use dynamic typing when you want, and enables more seamless interoperability with dynamically-typed languages.

A sibling addresses the nuance expressed in “for new languages”. But even if the original author’s opinion was that gradual typing is always bad, why does that mean we should dismiss the Elixir team’s efforts?

I have opinions about Elixir, mostly around aesthetics (for context, I started programming in Python, not Ruby), but that doesn’t mean my opinions are objectively more valid than those of a genius like José Valim.

I’ve actually found Elixir to be very well-designed and internally consistent, and after two years using it, it’s obvious to me that José and team are very thoughtful and deliberative. I don’t think they want to introduce gradual typing because it’s trendy.

It should be added that we also use Rust to fully build the front-end of the language and compile it into native code using LLVM.

Your question doesn't make a lot of sense. The entirety of gradual typing works by type inference, as does the static typing on any new language.

What part of the statement "is" because of type inference?

It's a vanity project until it isn't. I don't know what makes a language succeed but it's clearly possible. I've seen quite a few languages rise from small to widely used. Zig is a prominent example but there are others.

Good god, all is well but can we please all stop posting this xkcd :p