5 ms·
This looks like a very well-written, easy introduction to making simple, dynamic programming languages (not surprising given the author's writing background).
by jnbiche 11y ago
This looks like a very well-written, easy introduction to making simple, dynamic programming languages (not surprising given the author's writing background).
But everyone writes about how to build these kinds of basic Forths, or Lisps, or reverse polish notation calculators. To be honest, once you've learned the basic technique, writing a toy dynamic language interpreter is pretty easy. Even adding a toy JIT isn't very hard, and there are multiple guides online on how to do this using Luajit, or Libjit, PyPy, or LLVM, etc.
What I want more than anything is a guide written on the same level on how to build a toy statically-typed language, with algebraic data types. And even better, some basic discussion on how to learn about implementing advanced techniques like refinement, or linear, or dependent types (I realize these are extremely complex topics).
Every discussion I find on these topics is in dense academic papers. I'm slowly making headway, but it's a slog.
The only good resource I've found so far (and it's an excellent one) is Andrej Bauer's Programming Languages Zoo. But as far as I know, it's all (very helpful and instructive) source code, with no accompanying tutorials.
Is there no very simple introduction on writing a simple ML, with type checking? Any recommended resources?
It's possible that Butterick intends to cover these topics in later chapters, in which case I can't wait to read the book.
- samth 11y agoAre you looking for general references on implementing type checkers and ML-like languages? Or how to implement those as languages in Racket specifically?
- jnbiche 11y agoEither or any would be great, particularly if they're online and not books (although I'd buy a good book that covered those topics in depth). Particularly an approachable intro to Hindley-Milner and building a toy/mini-ML, and type checking in general. All the better if it's in Racket, or some ML. Actually, do you know of any examples of ML-type languages, or any statically-typed languages, that are written in Racket, aside from Typed Racket itself? Is looking at the Typed Racket code instructive? (I should just take a look)
- heimp 11y agoIt looks like Pyret was first written in Racket. I think it's optionally typed, though. https://github.com/brownplt/pyret-lang-resugarer https://github.com/brownplt/pyret-lang-resugarer
- deleted 11y ago[deleted]
- mkolosick 11y agoAs the sibling comment mentions, Pyret was originally written in Racket. It's now self-hosted, and I'm working on rewriting the typechecker so if you want I can answer questions about that. The current development is all done on https://github.com/brownplt/pyret-lang https://github.com/brownplt/pyret-lang
- sklogic 11y agoNot in Racket, but still a Lisp: https://github.com/combinatorylogic/mbase/tree/master/src/l/lib/ml https://github.com/combinatorylogic/mbase/tree/master/src/l/...
- jnbiche 11y agoThat is quite a broad and instructive project, very interested to see the Prolog type checking you describe below in action. Thanks!
- samth 11y agoThere is a simple ML-like language implemented in Racket, called plai-typed, which is used by some people for teaching the PLAI programming language book. You can see the implementation here: https://github.com/mflatt/plai-typed https://github.com/mflatt/plai-typed
- ics 11y agoNot the tutorial form you probably want but I've had this bookmarked, it may be interesting: http://www.cse.chalmers.se/edu/year/2015/course/DAT150/ http://www.cse.chalmers.se/edu/year/2015/course/DAT150/ http://www.cse.chalmers.se/edu/year/2015/course/DAT150/lectures/ http://www.cse.chalmers.se/edu/year/2015/course/DAT150/lectu...
- jjtheblunt 11y agoThere was a great textbook by Sam Kamin around 1990 (http://loome.cs.uiuc.edu/kamin/pubs.html http://loome.cs.uiuc.edu/kamin/pubs.html). I think that might help.
- orlandohill 11y agoThese should get you started. The last two are by Simon Peyton Jones, one of the creators of Haskell. One Hour ML https://vimeo.com/64593770 https://vimeo.com/64593770 Algorithm W Step by Step http://catamorph.de/documents/AlgorithmW.pdf http://catamorph.de/documents/AlgorithmW.pdf Implementing functional languages http://research.microsoft.com/en-us/um/people/simonpj/Papers/pj-lester-book/ http://research.microsoft.com/en-us/um/people/simonpj/Papers... The Implementation of Functional Programming Languages http://research.microsoft.com/en-us/um/people/simonpj/Papers/slpj-book-1987/index.htm http://research.microsoft.com/en-us/um/people/simonpj/Papers...
- jnbiche 11y agoOh, those are great, thanks. Not big on videos, but the Algo W pdf is great, and the last book is exactly what I need, and looks to answer some of the questions I'm running into doing this on my own (3rd one looks a little advanced for me at this point, maybe after I get through the Peyton Jones textbook).
- nteon 11y agoPierce's Types and Programming Languages ( https://www.cis.upenn.edu/~bcpierce/tapl/ https://www.cis.upenn.edu/~bcpierce/tapl/ ) is great - I'm working throught it now. Its goes through both untyped and statically typed languages. It also goes into how to implement these things in OCaml.
- jnbiche 11y agoYeah, I think I'm going to have a break down and shell out the dough for Types and Programming Languages. It's exactly what I need now.
- cgag 11y agoI belive this is trying to fill that niche: http://dev.stephendiehl.com/fun/ http://dev.stephendiehl.com/fun/
- eru 11y agoDo you find "Types and Programming Languages" to be a slog?
- jnbiche 11y agoI've not yet wanted to shell out for Types and Programming Languages in the hopes of finding something online, but given that it covers exactly what I need at this moment, I'll probably go ahead and buy it. And no, excerpts from Pierce I've looked at in the past looked perfect for my level. That said, the old Peyton Jones textbook that was referenced above looks pretty interesting. Might work through that one before I buy Types and Programming Languages.
- sklogic 11y ago> What I want more than anything is a guide written on the same level on how to build a toy statically-typed language, with algebraic data types. The answers here might be useful: http://stackoverflow.com/questions/12532552/what-part-of-milner-hindley-do-you-not-understand http://stackoverflow.com/questions/12532552/what-part-of-mil... > Is there no very simple introduction on writing a simple ML, with type checking? Any recommended resources? I'd recommend reading A. Field, P. Harrison, "Functional Programming". Despite the title, the book is about implementation techniques. P.S. I keep suggesting to everyone interested in implementing type systems to use a very simple technique: find an embeddable Prolog compiler for your language of choice (e.g., MiniKanren for Racket), and then simply emit a flat list of Prolog equations out of your source language AST (do the lexical scoping pass first). Easy. And easily extendable to dependent typing and all that fancy stuff.
- nickpsecurity 11y ago"find an embeddable Prolog compiler for your language of choice (e.g., MiniKanren for Racket), and then simply emit a flat list of Prolog equations out of your source language AST (do the lexical scoping pass first). Easy. And easily extendable to dependent typing and all that fancy stuff." So, you represent the AST associations and type-checks as Prolog logic rules that operate on predicates describing the AST? And the inference engine runs through it to dump out true or false for various predicates and rules? Am I understanding it right? Also, didn't realize Prolog could handle dependent types and such. That's neat to know.
- sklogic 11y agoFor example, you have an AST node for 'x + 2', encoded as 'apply(apply(var("+"), var("x")), const("2"))' (we're talking about ML, so it is curried here). Firstly, all the expression nodes must be annotated with type tags: 'A1:apply(A2:apply(A3:var("plus"),A4:var("x")), A5:const("2"))'. Then your typing pass walking over this segment of AST would generate the following (mostly trivial) equations A5=integer // from constant type A4=Vx A3=Vplus A3=fun(integer, fun(integer, integer)) // from environment lookup A3=fun(V1, A2) // application rule A2=fun(V2, A1) // application rule Then this long Prolog query (all equations are comma separated) is executed and you'll get all An type values to attach to your AST, as well as variable x type. > Prolog could handle dependent types It's Turing-complete. You can encode anything you want in it.
- gsg 11y agoPerhaps MinCaml: http://esumii.github.io/min-caml/index-e.html http://esumii.github.io/min-caml/index-e.html
- soegaard 11y agoI have a compile-to-Racket implementation of a Pascal subset here: https://github.com/soegaard/minipascal https://github.com/soegaard/minipascal There are two versions. The first one https://github.com/soegaard/minipascal/blob/master/minipascal/compiler-simple.rkt is without typechecking. The second one adds a type checker: https://github.com/soegaard/minipascal/blob/master/minipascal/compiler.rkt https://github.com/soegaard/minipascal/blob/master/minipasca...