6 ms·

Another great-looking book on making dynamic languages. There's been some good ones recently, and this one looks like another good one covering how to make a b

by jnbiche 10y ago

Another great-looking book on making dynamic languages. There's been some good ones recently, and this one looks like another good one covering how to make a basic, interpreted language. 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.

johnbender 10y ago
> Pierce's Types and Programming Languages Pierce's book is as approachable as you're likely to see with respect to type systems. You mostly just have to dig in.
- jnbiche 10y ago
  Yeah, I suspect you're correct at the moment. In fact, TaPL looks pretty approachable for an academic book. 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.
  - bbcbasic 10y ago
    I'm reading TaPL, done 4 chapters. 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.
jasperry 10y ago
> 20-30 year-old textbooks 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
Jweb_Guru 10y ago
You definitely want https://www.cs.princeton.edu/~appel/modern/ml/ https://www.cs.princeton.edu/~appel/modern/ml/.
inconclusive 10y ago
> more advanced, static type systems 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.
- rrradical 10y ago
  The quality of a type system isn't measured solely by what it allows you to do. After all, no type system at all would allow you to do anything and write as many bugs as you want-- not great, right? Instead, a better type system will let you make guarantees about your code, while still allowing correct programs to run. Can you guarantee there are no type errors? Can you guarantee arrays aren't accessed out of bounds? That sort of thing.
- evincarofautumn 10y ago
  Basically, yes. You can do more with a dynamic type system than a static type system because you don’t need to (and actually, aren’t allowed to) prove that your code is consistent. Advancements in static checking and inference mean you can prove more things about your programs, so you don’t have to fall back on dynamic types and data structures so much.
- PeCaN 10y ago
  Well, you could look at a dynamic type system as just a static type system with 1 type—a sum type of everything. Looking at it that way, a dynamic type system is much less powerful.
tekknolagi 10y ago
I'm starting a series of blog posts on making first a dynamic Lisp and then adding a type system to it, then type inferencer, etc. I'd be interested in what resources you found helpful and easy to read.
- msangi 10y ago
  Are you going to share the links once you're done?
  - tekknolagi 10y ago
    I can share now if you like. They're at http://bernsteinbear.com/blog/lisp/ http://bernsteinbear.com/blog/lisp/ -- still a work in progress. I hope to be done with Primitives II tonight.
KellAG 10y ago
There's nothing more "advanced" about statically typed languages. Static typing and type inference are straightforward and can make implementation details simpler than dynamic languages (because you're greatly reducing or removing the unknowns you have to deal with at runtime). This is assuming you're making a batch-style compiler, as most implementors do, and not an interactive system. 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
- jnbiche 10y ago
  I meant "advanced static-typing" (e.g, like System F, which is advanced to someone learning PL). Not that it was more advanced, although I think in fact it is from a learner's point of view. It's incredibly simple to throw together a Scheme, or even a more complex interpreted dynamic language. 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.
  - mafribe 10y ago
    dearth of learning materials for things like Hindley-Milner What's wrong with the original paper [1]? It's really basic and boiled down to the essence (in true Milner style). I give it to all my students interested in typing systems as first paper. (There is a typo on Page 211.) [1] L. Damas, R. Milner, Principal type-schemes for functional programs.
harpocrates 10y ago
Writing a type-checker is fun and pretty interesting. For that, I recommend you get acquainted with formal semantics and judgements (that's just the language for describing type-systems). You'll probably be interested in then looking up * simply typed lambda calculus * Hindley-Milner type inference * bidirectional typing After that, there are all sorts of cool things like linear/affine types, system F, dependent types, etc. which can be picked up. All of this (except maybe the first part) is easily learnable either from Wikipedia, the original papers, or recent tutorials.
- AlphaSite 10y ago
  Notes only tell half the story, but these are good notes on the first two topics. https://www.cs.cornell.edu/courses/cs4110/2016fa/schedule.html https://www.cs.cornell.edu/courses/cs4110/2016fa/schedule.ht...
  - jnbiche 10y ago
    Those are very good notes that have come up frequently in my Google searches.
- krat0sprakhar 10y ago
  Shameless plug: If you know OCaml, then I wrote this tiny implementation of Hindley-Milner[0] for a tiny functional language. It's (hopefully) very well commented, so it should clarify a bunch of concepts for newcomers. [0] - https://github.com/prakhar1989/type-inference https://github.com/prakhar1989/type-inference
munificent 10y ago
I did think about trying to sneak a type checker in here too, but it's just too much for a first book on languages and interpreters. If you're looking for a book on statically typed functional languages, I think Appel's book[1] 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. [1]: http://www.cs.princeton.edu/~appel/modern/ http://www.cs.princeton.edu/~appel/modern/
mamcx 10y ago
I want this too, but is weird to me that is a huge chasm in this area, where a lot of material stop at the most basic, and then it cover a niche that is complicated (like for example, type inference). 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.
- jnbiche 10y ago
  > 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. 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.
mafribe 10y ago
Anyone up for writing such a high-quality book as this one on statically-typed languages, Not a book, but maybe "The Essence of ML Type Inference" by Pottier and Remy [1] is of interest. It's a bit more in-depth than TAPL. [1] gallium.inria.fr/~fpottier/publis/emlti-final.pdf

by jnbiche 10y ago

johnbender 10y ago

> Pierce's Types and Programming Languages Pierce's book is as approachable as you're likely to see with respect to type systems. You mostly just have to dig in.

jnbiche 10y ago
Yeah, I suspect you're correct at the moment. In fact, TaPL looks pretty approachable for an academic book. 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.
- bbcbasic 10y ago
  I'm reading TaPL, done 4 chapters. 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.

jasperry 10y ago

> 20-30 year-old textbooks 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

Jweb_Guru 10y ago

You definitely want https://www.cs.princeton.edu/~appel/modern/ml/ https://www.cs.princeton.edu/~appel/modern/ml/.

inconclusive 10y ago

> more advanced, static type systems 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.

rrradical 10y ago
The quality of a type system isn't measured solely by what it allows you to do. After all, no type system at all would allow you to do anything and write as many bugs as you want-- not great, right? Instead, a better type system will let you make guarantees about your code, while still allowing correct programs to run. Can you guarantee there are no type errors? Can you guarantee arrays aren't accessed out of bounds? That sort of thing.
evincarofautumn 10y ago
Basically, yes. You can do more with a dynamic type system than a static type system because you don’t need to (and actually, aren’t allowed to) prove that your code is consistent. Advancements in static checking and inference mean you can prove more things about your programs, so you don’t have to fall back on dynamic types and data structures so much.
PeCaN 10y ago
Well, you could look at a dynamic type system as just a static type system with 1 type—a sum type of everything. Looking at it that way, a dynamic type system is much less powerful.

tekknolagi 10y ago

I'm starting a series of blog posts on making first a dynamic Lisp and then adding a type system to it, then type inferencer, etc. I'd be interested in what resources you found helpful and easy to read.

msangi 10y ago
Are you going to share the links once you're done?
- tekknolagi 10y ago
  I can share now if you like. They're at http://bernsteinbear.com/blog/lisp/ http://bernsteinbear.com/blog/lisp/ -- still a work in progress. I hope to be done with Primitives II tonight.

KellAG 10y ago

There's nothing more "advanced" about statically typed languages. Static typing and type inference are straightforward and can make implementation details simpler than dynamic languages (because you're greatly reducing or removing the unknowns you have to deal with at runtime). This is assuming you're making a batch-style compiler, as most implementors do, and not an interactive system. 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

jnbiche 10y ago
I meant "advanced static-typing" (e.g, like System F, which is advanced to someone learning PL). Not that it was more advanced, although I think in fact it is from a learner's point of view. It's incredibly simple to throw together a Scheme, or even a more complex interpreted dynamic language. 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.
- mafribe 10y ago
  dearth of learning materials for things like Hindley-Milner What's wrong with the original paper [1]? It's really basic and boiled down to the essence (in true Milner style). I give it to all my students interested in typing systems as first paper. (There is a typo on Page 211.) [1] L. Damas, R. Milner, Principal type-schemes for functional programs.

harpocrates 10y ago

Writing a type-checker is fun and pretty interesting. For that, I recommend you get acquainted with formal semantics and judgements (that's just the language for describing type-systems). You'll probably be interested in then looking up * simply typed lambda calculus * Hindley-Milner type inference * bidirectional typing After that, there are all sorts of cool things like linear/affine types, system F, dependent types, etc. which can be picked up. All of this (except maybe the first part) is easily learnable either from Wikipedia, the original papers, or recent tutorials.

AlphaSite 10y ago
Notes only tell half the story, but these are good notes on the first two topics. https://www.cs.cornell.edu/courses/cs4110/2016fa/schedule.html https://www.cs.cornell.edu/courses/cs4110/2016fa/schedule.ht...
- jnbiche 10y ago
  Those are very good notes that have come up frequently in my Google searches.
krat0sprakhar 10y ago
Shameless plug: If you know OCaml, then I wrote this tiny implementation of Hindley-Milner[0] for a tiny functional language. It's (hopefully) very well commented, so it should clarify a bunch of concepts for newcomers. [0] - https://github.com/prakhar1989/type-inference https://github.com/prakhar1989/type-inference

munificent 10y ago

I did think about trying to sneak a type checker in here too, but it's just too much for a first book on languages and interpreters. If you're looking for a book on statically typed functional languages, I think Appel's book[1] 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. [1]: http://www.cs.princeton.edu/~appel/modern/ http://www.cs.princeton.edu/~appel/modern/

mamcx 10y ago

I want this too, but is weird to me that is a huge chasm in this area, where a lot of material stop at the most basic, and then it cover a niche that is complicated (like for example, type inference). 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.

jnbiche 10y ago
> 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. 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.

mafribe 10y ago

Anyone up for writing such a high-quality book as this one on statically-typed languages, Not a book, but maybe "The Essence of ML Type Inference" by Pottier and Remy [1] is of interest. It's a bit more in-depth than TAPL. [1] gallium.inria.fr/~fpottier/publis/emlti-final.pdf