Statically typed functional programming language implementation with Go and LLVM | Hacker News Reader

Statically typed functional programming language implementation with Go and LLVM

github.com

120 pointskristianp19 comments

From the description in the README file:

"GoCaml is subset of OCaml in Go based on MinCaml using LLVM. GoCaml adds many features to original MinCaml. MinCaml is a minimal subset of OCaml for educational purpose. It is statically-typed and compiled into a binary."

What do they mean with "GoCaml is subset of OCaml in Go"? Do they mean the compiler is written in Go?

Yes, the compiler is written in Go, and implements a subset of OCaml, the language.

MinCaml is a project for students to easily learn what they need to know to build a useful subset of Ocaml in about 2000 lines of code. Here's the academic paper that describes the work with a 14 week plan for implementation:

https://esumii.github.io/min-caml/paper.pdf

I added it to our site for bootstrapping as it's a nice way to transition from a small, imperative 3GL into a ML. Well, without using a LISP or other metaprogramming tool that is. The bootstrapping site is here if you're interested in other small languages and builds:

http://bootstrapping.miraheze.org/

This is well timed! I've been starting work on my own strongly-typed functional programming language using Go + LLVM, and this looks like a great reference for implementing some of the parts I hadn't yet thought out. Though I'm not going the OCaml/MinCaml route, it's still extremely useful to see some of the key compiler stages implemented, since it helps give me a guideline for what has worked for others. Thanks for posting!

What is your motivation behind that activity?

Mostly for my own edification/enjoyment. It's something I've wanted to do for a long time, and once you have that itch, it's just a matter of time. I've built some toy compilers before, but this project I'm aiming a lot higher to see if I can combine some recent research in type theory (algebraic subtyping as an extension of ML-style type inference, effects) and the bits of languages that I would really love to see meshed together (rich pattern matching, including pattern matching on binary data, macros, zero/low-cost abstractions, Erlang-style concurrency with actors/supervision/transparent distribution) and see if I can still find a sweet spot where the language is still approachable, has good tooling, etc. I've accumulated a lot of research and notes, but only recently started working on an actual implementation. At this point nothing is set in stone, since I'm not certain all of those things are actually compatible in a single language, but those are the goals I have in mind for now, so we'll see where it takes me.

As for why I chose Go, I wanted something which was pretty portable, with decent performance, easy to build command line tooling in, but at a slightly higher level of abstraction than C; that way I could conceivably port it to C or C++ relatively easily if I felt like that was a better way to go down the road, but could mostly focus on getting things done in the short term. I'm not a huge fan of the OCaml toolchain, even though I like the language, and it's not very approachable for other people if they wanted to pitch in. Go isn't an ideal language to build a compiler in, but it's not bad either. I'm comfortable with it though, and that's all that really matters for a project like this.

Are you the same bitwalker, responsible for all those great Elixir libraries and Docker images? Wanted to say thank you :)

I am! Thanks for the kind words! I don't hear from people using my stuff too often, so it's always good to get some positive feedback :)

You're most welcome :) Thank you again for doing a great job, offering your time and brain to improve the Elixir community! I certainly benefit a lot from Distillery and the Docker images that you always keep up-to-date.

You may find this helpful for writing a compiler in Go: https://godoc.org/github.com/BurntSushi/go-sumtype

This is great! Thanks :)

Does anybody have a good reference on how to implement inlining and beta reductions efficiently (efficient at both compile time and run-time)?

I've found SPJ's paper but I find it a bit of a grab-bag of ideas (difficult to see how to implement it step by step instead of all at once).

I don't have a reference, what in particular are you unsure about? In my code, for inlining, I do something like

* Replace function application (function call) expression with body of inlined function

* Now replace all variables in the target function body with the argument values from the func expr

* Re-bind all variables.

(Some details elided :) )

The trickiest aspect of inlining is deciding what to inline.

Well, I have a deeply nested tree of let blocks intermixed with lambda abstractions (my front-end, which uses a continuation passing style, generates very inefficient code). If I alternate between beta-reductions and inlining, then I need to do many passes to end up with something small and sensible (and this takes a lot of time). So, I guess I have to do both types of steps in a single depth-first pass. I'm about to rewrite my optimizer this way, so I thought perhaps I'd better read up on it first to prevent unnecessary work :)

Yes, checking what to inline is tricky, but I'm not there yet; my code is still very simple and everything can be inlined in principle (unless of course intermediate results would cause problems, which I'm not sure about).

Ok, I think I see the problem. What about traversing down to as deep as possible, then walking up the AST inlining as you go? This should allow processing in a linear time in the number of nodes, with a single pass.

Hey, thanks for the reply. I'm already doing something like that. The problem is that I also have to do the beta-reductions (i.e. reduction of function applications), and I'm not sure what order is best.

not to be confused with JoCaml https://en.wikipedia.org/wiki/JoCaml ;)

which is not to be confused with https://en.wikipedia.org/wiki/Joe_Camel

This is nice.

Reply on news.ycombinator.com