Hacker News new | comments | show | ask | jobs | submit login
Why ML/OCaml are good for writing compilers (1998) (yale.edu)
241 points by monssoen on Apr 15, 2017 | hide | past | web | favorite | 147 comments

For web developers who are looking for an industrial strength functional language instead of JS, OCaml probably has the best story here.

Actually it has two OCaml->JS compilers of very high quality The first one, js_of_ocaml, could bootstrap the whole compiler several years ago(probably the first one there).

The recent one, https://github.com/bloomberg/bucklescript, push the JS compilation into next level, it generates fairly readable code, good FFI story, and its compilation is extremely fast, check out the compiler in JS version(http://bloomberg.github.io/bucklescript/js-demo/), and imagine how fast it would be for the compiler in native version. BuckleScript has a good story for Windows, and generates fairly efficient code, see benchmark here: https://github.com/neonsquare/bucklescript-benchmark BuckleScript is already used in production by big companies: for example Facebook messenger.com 25% is powered by BuckleScript, the new WebAssembly spec interpreter by Google is also partly cross compiled into JS by BuckleScript.

Disclaimer: I am one of the authors of BuckleScript

I'm optimistic about Reason, Facebook's new syntax "skin" on top of OCaml. I find OCaml's syntax to be quite gnarly; of the MLs, F# is probably the cleanest and most modern-feeling. Something like F# without the .NET stuff could have been amazing.

I can confirm that the story of F# on the JS ecosystem is already quite good and is getting better every day. As already mentioned, Fable (http://fable.io) is the way to go today. I did two things that involve "writing compilers" using F# that target the web and did not have any notable issuues.

- My coeffects page (http://tomasp.net/coeffects) is an implementation of a simple ML-like language with coeffect type system. It was written using FunScript, which is a precursor of Fable - Fable improved many things, but this was over a year ago when it was not around yet.

- The Gamma (https://thegamma.net) is a web-based language for doing simple data science work and the compiler for that is written all in Fable. It works perfectly and integrates neatly with things like virtual-dom (source code is on GitHub https://github.com/the-gamma/thegamma-script)

Indeed, fable is a very neat project, but to be honest, it is not as mature as BuckleScript at this time.

For example, it takes around 20~80ms to compile a single file for BuckleScript, while Fable would talk 10x more to compile.

Its generated code is pretty but its performance is not very good, see this issue (https://github.com/fable-compiler/Fable/issues/646) "this can make a difference in speed of up to about six or seven times for tight loop code using tuples, records, lists, unions, etc.(compared with BuckleScript)"

But Fable is a nice project, JavaScript platform is large enough to have both :-)

I absolutely agree that the JS platform is large enough to have both!

That said, I think doing a fair comparison is going to be difficult. Although OCaml and F# share the same background, I think the OCaml and F# communities care about quite different things - and this can be seen in the difference between BuckleScript and Fable. OCaml compiler is very fast and produces efficient code and so it feels reasonable to expect the same for BuckleScript. F# is often slower, but people tend to care a lot about making interop nice. You can see this with the React bindings and Elmish tooling.

Those different goals are exactly the reason why there is room for both. I think Fable vs. BuckleScript mirror the philosophy of F# vs. OCaml with respect to .NET and native.

The good news is that you can have your cake and eat it too! Reason is a front-end to the OCaml compiler and BuckleScript is a back-end. Your Reason programs can be compiled to JS via BuckleScript. Yay!


Fable: http://fable.io/

It's able to self-host as well. Check it out at http://fable.io/repl

F# also runs on .NET Core, which is cross-platform and comes with a good CLI. Documented, too: https://docs.microsoft.com/en-us/dotnet/articles/fsharp/tuto...

Fable looks great, and I might try it out, but I was thinking more along the lines of native, static compilation.

I find OCaml's syntax simple and clear. I don't get the reason for Reason, but hope it leads to more OCaml adoption.

OCaml might be simple and clear, but starting from Standard ML - there's a number of differences that feel like warts and needless complications for no discernable gain for the programmer.

I do think Reason fix up a few of these ancient and partially crumbled stone walls making the ocaml landscape easier to criss-cross for a new generation of programmers.

> there's a number of differences that feel like warts and needless complications for no discernable gain

Such as?

It's been a while - but pretty much what Reason address - although I'd prefer filling in SML for js-ish syntax.

I get the reason* for Reason even though it may ostensibly be a superficial one. There was a post by someone on HN saying they started using Reason and ended up using straight Ocaml.

* My earliest memories of attempting to use Ocaml was pasting something directly from a beginner's tutorial into ocamli and getting a baffling error message. I think it had to do with use of double semicolons vs single semicolons. Yet that wasn't mentioned in the entire tutorial.

Reason is more then a "slightly improved syntax to help attract programmers from mainstream languages".

It also improves error messages and tooling. It has something akin to JSX built into the lang.

>I find OCaml's syntax to be quite gnarly

What's wrong with the OCaml syntax? It's much more clean than say scala's one, it's indentation insensitive, and a' list feels more relevant than the list<'T>

It's a lot of little random things. For example, the ~keyword: syntax, the need to paranthesize where other languages don't (e.g.: "foo -1" doesn't work, you have to do "foo (-1)"). The way argumentless functions must be declared with "function". The expression termination issue (";;") is a lot less elegant than, say, Haskell's whitespace awareness. Operators not being overloaded is annoying, although there's a valid argument for explicitness.

Overall, it's not a terrible syntax, but it feels a lot like someone just invented things along the way as they needed them, without a cohesive plan. Lots of pragmatic but visually ugly choices.

I also take issue with the tooling; things like error messages, or just the antiquated feel of the CLI tools. For example, having a REPL without built-in readline support (rlwrap to the rescue) in this day and age is not acceptable.

>The way argumentless functions must be declared with "function".

Could you show an example, I don't get it?

>The expression termination issue (";;")

Strange, I've never used ";;" in my code, only in repl.

>Operators not being overloaded is annoying, although there's a valid argument for explicitness.

Overloading is harmful. It's definitely the wrong way to do ad-hoc polymorphism, and OCaml have a polymorphic comparison operators, which brought so much headache. Type classes or modular implicits are the right way to do ad-hoc. Looking forward to see modular implicits in OCaml [1].

>For example, having a REPL without built-in readline support (rlwrap to the rescue)

What do you mean by "readline" support?

[1] http://ocamllabs.io/doc/implicits.html

Sorry, I should have been clearer. As I'm aware you have the choice between several ways:

  let foo : unit -> unit = <code>

  let foo = function
    | <pattern match stuff>

  let foo = (function () -> <code>)

  let foo = (fun () -> <code>)
I'm not an expert, but I guess this awkwardness comes from OCaml not having a dedicated function-declaration syntax; so if you do:

  let foo = do_stuff + 42;
...then you're obviously just defining a variable, which is evaluated right away. Which means that the only way to define a "procedure"-type function that takes zero arguments is the above.

> What do you mean by "readline" support?

Readline is a library that adds a line editor to a REPL. It adds keyboard shortcuts (arrow keys etc.), history, autocompletion, and so on. Unlike almost every single REPL out there (Python, Ruby, Haskell, etc.), OCaml doesn't come with built-in support, as far as I've been able to determine. You have to run "rlwrap ocaml" to get Readline into your REPL.

>Readline is a library that adds a line editor to a REPL.

There is a great advanced REPL for OCaml if you need something beyond simple stuff:


You can also do this:

    let foo () = <code>

That's news to me. Thanks!

() is just an empty tuple, so yes, you can write let f () =...

OCaml doesn't have argumentless functions.. But they do have functions that take a 'unit' argument.

I know, I've asked about this:

>The way argumentless functions must be declared with "function".

function is just a sugar for fun+match, what does it have to do with argumentlessness?

I think by "argumentless function" OP just means "a function taking a single, unnamed argument", which is what function does as opposed to fun in OCaml (As you say, function is just sugar for (fun arg -> match arg with .... ) - it's a common enough idiom to have some sugar in the syntax).

One problem is that it is full of shift-reduce conflicts, due to a lack of an "end" token in most expressions.

The one that bugs me the most is nested match expressions, which often need to be wrapped in parenthesis.

In OCaml's expression syntax, "begin" is a synonym for left parenthesis, and "end" is a synonym for right parenthesis. So I've taken to just using "begin match e with ... end" in every situation to avoid this problem.

F# has lots of .net warts. Haskell is probably the cleanest ML syntax-wise in somewhat widespread use.

And the OCaml-as-JS community is small and very welcoming. How often can you get first-class support from the compiler makers as a newbie? Hongbo Zhang and Jordan Walke and Cheng Lou are all on the Discord channel and are extremely helpful.

Jump in fellas, the language is powerful, and the community is nice!

I can testify that the the Discord channels are a very welcoming place.

I can also verify this. The documentation is not perfect, and the fine people who hang out on Discord were able to lead me on how to fix the docs, and get me up and running.

Also, having full Intellisense for a JavaScript like language is amazing! I found it better for Reason than Typesript, oddly enough even in VS Code.

I'd be interested to learn how web-dev in OCaml->JS compares to web-dev with Scala.js. The latter has the amazing JVM eco-system to hand.

(I'm not interested in a Scala vs Ocaml language comparison. I know both languages very well. I'd be interested in the quality of JS support.)

> The latter has the amazing JVM eco-system to hand.

What do you mean? Scala.js allows you to use things from the Java ecosystem in JavaScript?

Only if it's been ported to Scala.js; in fact, same goes for Scala to Scala.js, all libs need to be cross compiled.

The only thing you get for "free" in Scala.js is Scala, which is of course no small accomplishment, but the JVM ecosystem as a whole does not come with it.

That's what I thought, and why I was confused by the original comment. Scala.js doesn't seem to have any benefits over js_of_ocaml, unless you prefer the language itself.

I was expressing myself sloppily, sorry. You still can use many things in the JVM ecosystem because you can compile (most of) scala.js not only to Javascript but also to the JVM, and then analyse the code with JVM specific tools like fuzzers, debuggers, profilers etc. This is powerful. Making sure your code runs on two platform will expose additional problems that one platform alone doesn't do.

I see. Well, I suppose that's true of OCaml as well. Its ecosystem is smaller, but it does have some pretty powerful tools, including a time-traveling debugger.

better than clojure and f#?

After learning Elm I wanted to understand ML/OCaml a bit more, so I worked through some documentation from the OCaml site and walked away pleasantly surprised.

After using it for a couple of weeks I am confused why ML/OCaml aren't more popular. They are safe, functional, stable, fast, and have great tooling. They seem poised to take over the functional domain.

While the syntax took a little getting used to ( emphasis on little) once you are used to it, it's very natural. Union types are wonderful, and the implicit type safety within programs was nice.

Crappy windows support for OCaml. F# is similar to OCaml, but is very difficult for beginners and those not familiar with .NET. I also don't see a lot of beginner material for OCaml.

In France, my two first years of CS were taught in OCaml. 20k+ students are learning that way every year over there. We learn about recursions, complexity, types, compilers, language theory, graph theory ... without leaving the confort of one expressive language. I terribly missed OCaml when I had to realign with the technologies promoted in job offers and expected within the industry.

I imagine Inria has some influence there as well as FP is good to teach in college. It's always a tough balance choosing between what is more relevant as computer science (Lisp, Prolog, OCaml...etc) versus what will get students paid money (Java, JavaScript, C++, or Python). I'm glad you had a positive experience and as i asked below, do you have the course material? And outside of the basic things you learn in school/mention above, could you use it in your daily job? Is there enough library support?

At computer science at the University of Copenhagen F# has been used for the introduction courses the past couple of years, which as far as I know has been a big success, so I'm doubtful of it not being beginner friendly

Mileage is probably not representative when you're in a university setting being taught by professors in an intro course versus a professional trying to use a multitude of the data science libraries and having trouble tying it together. Python has a zillion books published and a large percentage of them are beginner oriented. F# has only a few books and they are almost all for experts.

The community surrounding F# today is very supportive and helpful with people of all experience levels. Compared to when I learned F# in 2010 it is orders of magnitude easier and more social. So many resources: the F# Foundation website http://fsharp.org/ is a good place to start. http://fsharpforfunandprofit.com/ and the book form of the site's articles on github https://swlaschin.gitbooks.io/fsharpforfunandprofit/content/... has great information for people at all levels. And finally just get on twitter #fsharp to start meeting people in the community.

I've gone through all of those and although it's nice, it is not what I'd call beginner friendly at all. Python has books teaching you to program in Python which is a really good way to learn a programming language. Scott's tutorial using Frankenstein to explain Monads is interesting, but I need to see how to build simple programs and modules first. How does one organize a program using pure FP, or what's the best way to mix in OOP and it is really confusing to learn all the pragmas and compiler directives. I'm not sure if I'm using the right terminology, but a lot of example code uses FSI which has to call the modules differently than if you make an executable. I really would love nothing more than F# to be my go to language, but I need a little more help getting there. I realize not all users have this problem though.

i am an expert and Scott's website is usually bananas to me. For some people his approach doesn't seem to click.

A good beginner book for F# is a good idea.

Glad to hear I'm not the only one lol. I'd spend top dollar for a beginner's book focusing on creating short 1/2 page programs like guess my number, hangman, plotting graphs...etc and only mix in things like currying and monads later in the book along with C# interop.

I have been teaching OCaml in CS1 at Boston College for 4 years now. Of hundreds of students who went on to learn Java in our CS2 course (joining Python-trained students from other sections of CS1), nearly unanimous happy campers. When OCaml is their first programming language, they're good to go.

Is the course material online?

I've moved to doing ocaml development on my windows 10 machine under the windows subsystem for Linux. The Linux ocaml tool chain works pretty seamlessly there. Works very smoothly relative to past experiences with native ocaml compilers on windows.

True, but at least for compilers Windows support shouldn't be a big deal. This is because the Windows support is mostly only an issue when using certain libraries, and since compilers rarely have many dependencies it's often a non-issue.

The beginner material is kind of true as well, although I do believe that the little beginner material that exists for OCaml (pretty much just the official documentation/Learn OCaml and Real World OCaml) are much easier to get started with than the tutorials of many other languages. OCaml's learning material is pretty short and to-the-point, and I found it to be a good set of boot-strap knowledge: I pretty much learned the core language in 3-4 days or so and then went on to explore the various libraries, tools, and language features not covered by the basic tutorials at my own pace.

OCaml from the Very Beginning is amazing beginner material.

Thanks, I'll take a look again. He has some sample chapters posted that look really short(3 pages), but I'm guessing that is just a chapter snippet as the book itself is 200 pages?

The book is short, but there are plenty of exercises and worked solutions in the back. Do the exercises and you will get your money's worth. I suggest buying it with the bundle because More OCaml is good also.

I think MLs are kind of in limbo in regards to functional vs. imperative and OO vs. procedural programming. While they offer good OO, it's utilized very little. The functional features are used a ton, but don't dare approach the complexity of Scala, Haskell, etc., which is disappointing to a lot of more advanced functional programmers. They have reasonably good facilities for imperative programming, but these are mostly frowned upon. The whole language is, to an extent, a compromise over various paradigms that are very nearly mutually exclusive outside of ML.

I would actually argue the opposite: ML languages propose the sweet spot of having functional features but still being flexible.

Mutability, OO and various other feature are all there just when you need them. You don't need, like in Haskell, to do incredible contortions to be able to express things naturally.

Regardless which algorithm and API you want, there is a pretty good chance you can express it in OCaml naturally, and it'll almost always be reasonably efficient by default.

Also, everyone underestimate modules a lot. They're the best software development tool in any language by a long shot.

So, what's your answer to the question being asked, "why ML/OCaml aren't more popular" ?

Sounds like you're in the same boat as the asker.

In practice languages don't need to be popular for you to use them. They might be hard sells to bosses and the like, but there is room for impopular technology in the market as well. All you need is a main advocate with enough sway with bosses and the like.

There are positions at companies using niche languages. Even though most companies prefer not to make broad technical decisions (even though they have CTOs, etc.), plenty of them do and so you're not going to find them making massively concurrent backends in Java.

Even in the situation where there are no jobs for a language, why would you really not use it if it's the best tool you have? The onus is not on the language/technology to make people realize it's great. The reverse is true too: It's not Java's, JavaScript's, C++, Ruby's or any other language's fault that people are stupid enough to make backends in them. Even if the majority of those languages/platforms were good it'd be stupid to use them for things they're designed not to do.

I simply made my peace with the fact that popularity has little to do with merit. :)

> The whole language is, to an extent, a compromise over various paradigms that are very nearly mutually exclusive outside of ML.

I'd say the MLs are functional-first (with imperative/OO on top). Like Ruby OO-first (with some functional on top).

For me this type of multi-paradigm is ok. It starts to hurt when all the paradigms are "first", which I see in Scala.

>After using it for a couple of weeks I am confused why ML/OCaml aren't more popular

For me, the issue is the GIL, although that is being worked on as we speak.

Sadly, I'm starting to lose my hope over multicore. It's been in the works for as long as I've used the language with much speculation of it being "almost done" or "in the next release" that have failed to materialize. That said, I don't have the time to really follow along with the compiler's development so take that with a grain of salt.

Precisely this is the reason I've lost hope with regards to OCaml as a main language. Multicore, specifically, is one of those things that has been "close" for so long that it's looking like a Duke Nuke'em Forever feature. I keep track of OCaml regularly because I love the language and I find that it's probably the best combination of features in one place, both in terms of my enjoyment as a programmer and in terms of the performance of the language.

I've come to realize later, though, that there's one glaring problem: Runtime inspection really is much more valuable to me than clean syntax and programmer comfortability when I'm building a system. With that in mind, maybe it'll never be very interesting to build a bigger system in a language like OCaml, even though it offers you a lot in terms of programmer efficiency as well as high performance.

Maybe it's better to glue together OCaml programs on the BEAM (The Erlang VM) so that you're able to orchestrate them and introspect them and get proper handling and oversight of the different components of your system. Maybe all that makes multicore in OCaml mostly pointless for you in practise.

Of course, not everyone will use the BEAM and OCaml together, so for them it matters a lot. I've come to see it as a worrying sign of a community that doesn't care to evolve enough, more than anything, and that's why OCaml is not as interesting as it could be.

It should be said that languages that supposedly are made for building systems also lack this runtime introspection and oversight. They have no way to locate and refer to their threads and no way to automatically handle their successes and failures. These languages are wildly popular, and so none of the above apparently matters to the vast majority of people. I think it's an interesting argument around (or against?) multicore in OCaml.

Good news, there is indeed Alpaca: ML for the BEAM.


I always found that strange since Python has the same GIL and it hasn't stopped the massive adoption, same with MRI Ruby (though one could argue JRuby is more popular, but don't see any massively multicore applications in Ruby either), so that reason does not convince me.

What does the lack of multi core keep you from doing?

In web-apps architectures, you have a choice: multithread or multiprocess. Multithreading is far more memory friendly, and occasionally a bit faster, but many interpreted language runtimes aren't prepared for multithreading. Python / OCaml have a big global lock on certain things (interpreter, garbage collection) that are needed frequently enough that even requests aren't really interfering at the DB transactional level will block one another under multithreading. So instead you have to take the hit of multiprocessing, where each web worker has its own memory space and set of locks.

So if you're going to justify writing a webapp in OCaml, it would be helpful if the language was more efficient than whatever your alternative is.

> In web-apps architectures, you have a choice: multithread or multiprocess.

No, the choice is definitely not that limited. Saying something like this is like saying there's no Nginx, only Apache available as an HTTP server. For the concurrent, IO-bound code you can leverage all kinds of concurrency approaches (coroutines, green threads, callbacks). In these use cases, multiple threads are actually a bad idea from the memory efficiency perspective.

On the other hand, multiple threads would be viable for CPU-bound and/or long-running code were it not for the GIL, that's true. With the GIL you don't have that option and have to resort to multiprocessing.

Multiprocessing is not so bad, actually, although it does make the code more complicated. Unless your problem is massively parallel (but then you'd use GPU instead), spawning n x 2 processes for n cores is definitely possible with how much RAM is available nowadays on the servers. You get optimal parallelism at the cost of serialization overhead (or other complexities if you want to directly share memory).

There are some languages which do support most existing concurrency mechanisms and they may be a better fit for a particular project. However, not supporting parallelism via multi-threading hardly disqualifies any language, provided the other tools are in place, solid and widely used.

Now that JaneStreet and Facebook are investing so much in the language, I think this feature is more likely to be implemented then ever.

CML/MLton or Manticore will deal with most of those issues.

Ocaml is a great language. But the sad fact is I'm not going to be as productive in it as I would be in worse languages that have more libraries and tools.

Because of package manager and library issues. Things aren't popular because of their inherent qualities or flaws. Popularity is driven by itself and external factors.

As a rule, functional programming languages tend to have trouble with gaining adoption. It's simply a programming paradigm that a great many programmers don't seem to be comfortable with.

Now, the ML family of languages (SML, OCaml, F#) is technically a family of multi-paradigm, functional-first languages, but that doesn't help with clearing the "functional" hurdle in popular perception.

I've heard the concurrency situation with OCaml isn't very good, though I know nothing about that. Weirdly, this kind of bias and the idea that it doesn't have as many libraries for my particular domain (web programming) has put me off it, as much as I'd like to use it.

Using functional languages without Lisp-like macros will always be sort of weird to me, like I'm missing out on something.

Just to clarify, it's not concurrency that's the issue but parallelism. You can write nice concurrent code pretty easily, but writing code that runs on multiple cores is still a problem. Also, if you're interested in using OCaml for web programming, there is some pretty cool stuff you might wanna check out [1] [2] [3]. That said, there's no great solution to the lack of macros :/

[1] https://github.com/dannywillems/ocaml-for-web-programming

[2] https://github.com/rizo/awesome-ocaml#web-development

[3] https://facebook.github.io/reason/ [2]

Strictly speaking, it's not parallelism, but multi-threaded code that operates on shared memory and which is not limited to arrays over scalars.

You're talking about data parallelism, the OP is talking about task parallelism. Since in both cases things are occurring in parallel it makes sense to use 'parallelism' as an umbrella term for both and it was clear from context here that it was task parallelism under discussion.

I am talking about both. You can have task parallelism in a distributed system with no shared memory, after all.

Thanks for the links and info, I'll be looking into Ocaml more.

Like C++ and Perl, there's a bit of caution required to avoid writing unreadable OCaml code. A disadvantage of pattern matching is that it's relatively easy to write a function where you define a variable and then first access it 500 lines later. IDE support for obscure languages is also often weak or requires extensions or idiosyncratic IDEs which are unfamiliar to many people (and often you want some kind of tool to collapse a 500-line function). OCaml has good vim plugins but not everyone uses vim.

That's my experience with it anyway.

> A disadvantage of pattern matching is that it's relatively easy to write a function where you define a variable and then first access it 500 lines later.

I've written plenty of OCaml, and I can't see how this would ever be a problem. Are you writing 500 line functions in OCaml? It seems like it would be difficult to write such a long function in OCaml. An why would pattern matching cause it?

Maybe I'm misunderstanding something.

> Are you writing 500 line functions in OCaml? It seems like it would be difficult to write such a long function in OCaml.

Me, no; my colleagues, yes. I am averse to writing long functions even more than most people. I agree with 'jldugger that this is a sign that some cleanup is needed but the point is that bad code exists in cool languages too (there are also Mondays in Australia).

I've done it when writing translators / compilers for school. If you're pattern matching against an AST, its easy to to have a pretty big list of possible types the AST can contain.

Probably this is a code smell that should be rearchitected.

Haven't used OCaml but the recommended practice in Erlang/Elixir is to break down complex pattern matches into separate function clauses, as function calls are also driven by pattern matching.

the toolchain was pretty damn bad for years. it's only very recently gotten better with the rise of opam, oasis and some decent build systems.

I'll note that some of the aspects don't necessarily work out like that in practice:

1. The GC part is true, but one has to remember that this was written at a time when GC was still a bit of an unusual feature in mainstream languages.

2. Tail recursion doesn't really make much of a difference for walking trees, which is recursive, but (mostly) not tail recursive.

3. OCaml in particular uses 63/31-bit ints due to implementation details, which isn't a good fit for 64/32-bit integers. The strings and bignum part is mostly right, though.

4. ADTs can be good or bad for describing ASTs. Once you enrich ASTs with semantics shared by all variants (such as source coordinates), inheritance can become a better fit than ADTs.

8. Type inference doesn't really extend to module signatures, which you have to write out explicitly (though tooling such as `ocamlc -i` allows you to let the compiler help you write them). I also generally find it better to explicitly annotate functions with types. Not only does it make the code more readable later in its life, but you get fewer truly impenetrable type error messages because you forgot parentheses or a semicolon somewhere.

That said, there are several good points still.

> 2. Tail recursion doesn't really make much of a difference for walking trees, which is recursive, but (mostly) not tail recursive.

Unless you, as the article notes, "know how to take advantage of it". Here's a fully tail-recursive binary tree traversal in OCaml:

    type 'a tree = Leaf of 'a | Branch of 'a tree * 'a tree

    let iter f tree =
      let rec iter_rec f worklist tree =
        match tree with
        | Leaf a ->
          (* Perform the action on this element. *)
          f a;
          (* Consult the worklist for more things to do. *)
          begin match worklist with
          | [] -> ()
          | next_tree::worklist' -> iter_rec f worklist' next_tree
        | Branch (left, right) ->
          (* Visit the left subtree, save the right for visiting later. *)
          iter_rec f (right::worklist) left
      iter_rec f [] tree
Usage example:

    let mytree =
      Branch (Branch (Leaf 1, Leaf 2),
              Branch (Leaf 3, Branch (Leaf 4, Leaf 5)))

    let () = iter (Printf.printf "%d\n") mytree
Yes, people do write traversals like this in OCaml, though with less verbosity than this example I whipped up.

> 3. OCaml in particular uses 63/31-bit ints due to implementation details, which isn't a good fit for 64/32-bit integers.

I think the article means here that you just use int for all the kinds of numerical identifiers that compilers give to things like instructions, basic blocks, pseudo-registers, etc., without doing the kind of micro-optimization that C++ programmers would do, guessing whether the number of blocks is safe to store in an unsigned short etc.

For representing constants from the program, which is what you seem to be referring to, the article does suggest using bignums, not OCaml's native ints.

> Unless you, as the article notes, "know how to take advantage of it". Here's a fully tail-recursive binary tree traversal in OCaml:

This is a depth-first search with an explicit stack (the stack is tree :: worklist). You can do the same in an imperative language. Tail recursion here is only an extra-complicated way of writing a simple loop, and you're adding extra complexity by having two variables to represent the stack. The same code can be written just as (if not more) compactly in an imperative language.

You are correct on all counts. Tail recursion allows you to reap the benefits of imperative programming in a purely functional setting, but only thanks to tail call optimization.

>2. Tail recursion doesn't really make much of a difference for walking trees, which is recursive, but (mostly) not tail recursive.

Non-strictness helps here more than TCO in a strict language.

>4. ADTs can be good or bad for describing ASTs. Once you enrich ASTs with semantics shared by all variants (such as source coordinates), inheritance can become a better fit than ADTs.

Since this article was written we have better ways of augmenting/annotating ASTs. There's a lot of this out there, but here's one example: https://brianmckenna.org/blog/type_annotation_cofree

There are other alternatives that are like inheritance but with better reasoning properties as well. Finally tagless comes to mind.

>I also generally find it better to explicitly annotate functions with types.

This Haskeller whole-heartedly agrees for all the reasons stated.

> Non-strictness helps here more than TCO in a strict language.

Can you explain? Assume I want to fold a function over a large tree and fully inspect the final result. (For example, to compile a large expression to a piece of code.) If I use non-tail recursion, my stack will be exhausted. How does non-strictness help with stack usage?

More generally, functor sum and products allow composition of recursive data types. The cofree comonad, which Brian describes, is a special case of a functor sum.

ADTs and pattern matching are much more convenient and higher-level in practice than using OOP with inheritance. The visitor pattern, essentially just a fold, is the best one can do in an OOP language. With type-class abstractions and data type generic programming, the gap widens further.

In Haskell, my current FP language of choice, I can implement a complex transform such as Lambda lifting in a few 10's of lines of readable idiomatic code.

First, inheritance provides a strict superset of standard ADT functionality. Proof: Scala does ADTs through inheritance. ADTs are basically isomorphic to a closed two-tiered inheritance hierarchy with an abstract superclass at the top tier.

Second, you're confusing inheritance with the ability to map subtypes to operations (and in statically typed languages, in a type-safe fashion). This is a function of OCaml's (or SML's, or Haskell's, or F#'s) pattern matching facilities, not of inheritance vs. ADTs. It can also be done with typecase statements, multi-methods (or actually, just external methods), or tree parsers. The tree parser approach in particular is more general and powerful than the typical pattern matchers in functional languages.

Third, if you look at actual compilers, such traversal will commonly be done in an ad-hoc fashion and can be done equally well with bog-standard methods. Where you have generalized traversal mechanisms, the visitor pattern will crop up in OCaml, too (in some guise or another). Examples are the Ast_mapper module for PPX in OCaml itself [1] and the visitor interface in CIL [2]. The reason is that if you want to perform a generalized fold, map, etc. operation over a heterogeneous data structure such as an AST (visitor is usually fold + map due to destructive updates), you need to also provide a set of operations for the various types that you can encounter during traversal.

[1] https://caml.inria.fr/pub/docs/manual-ocaml/libref/Ast_mappe...

[2] https://people.eecs.berkeley.edu/~necula/cil/api/Cil.cilVisi...

Inheritance may be a theoretical superset of ADTs, but it is not as convenient due to the complexity of subtyping and problems with its inference. Scala is the proof of this.

Both extensible records and open recursion can be achieved with ADTs, so why do we need inheritance with all its problems? You still haven't explained this.

I lumped inheritance and OOP together as this is what is typically packaged and available for us to use.

It is true that more principled traversals (e.g. catamorphisms) only match one level deep, but pattern matching is still a convenient and high-level syntax in such cases. Pattern matching would also complement e.g. attribute grammars.

> Inheritance may be a theoretical superset of ADTs, but it is not as convenient due to the complexity of subtyping and problems with its inference. Scala is the proof of this.

Scala isn't proof of this, because so much of the complexity of Scala's type system is due to a desire to provide smooth interoperability with Java's, which requires the replication of and dealing with some of the more misguided aspects of Java's approach. (The biggest one is probably that Java's constrained parametric polymorphism is intimately tied to a form of nominal subtyping that is simultaneously too constraining and not expressive enough for a number of use cases, leading to things such as implicit arguments and CanBuildFrom in Scala.)

> Both extensible records and open recursion can be achieved with ADTs, so why do we need inheritance with all its problems? You still haven't explained this.

My general argument would be that any single approach to polymorphism will be insufficient to cover all use cases, many of which have mutually incompatible requirements:

1. You may want to be able to exhaustively enumerate operations on a type or subtype for purposes of code verification or optimization.

2. You may want to be able to add additional operations to a type or subtype for purposes of modularity or extensibility.

3. You may want to be able to exhaustively enumerate subtypes of a type for purposes of code verification or optimization.

4. You may want to be able to add additional subtypes to a type for purposes of modularity or extensibility.

5. You may want to resolve polymorphism at runtime.

6. You may want to resolve polymorphism at compile-time.

ADTs present you with a closed universe of subtypes and an open universe of operations as well as runtime polymorphism. In other words, they meet half of the above criteria.

Haskell's approaches to extensible records and open recursion cannot square the circle, either. They require their own mechanisms and/or hacks on top of ADTs and have their pros and cons that are distinct from the pros and cons of using inheritance. There is no single mechanism for polymorphism that can do it all. (OCaml, incidentally, has at least six distinct polymorphism mechanisms that support runtime polymorphism: ADTs, polymorphic variants, open types, records of closures, first-class modules, objects.)

A simple example of something that basic ADTs just don't do: add more variants (subtypes in the OO case) to the type. You can go with something like OCaml's polymorphic variants, but that doesn't make it easy to extend existing operations in a modular fashion as you add more variants. If you want to simulate OO-style extensible late binding in Haskell, you'll generally need {-# LANGUAGE ExistentialQuantification #-} and type classes.

Inheritance, incidentally, does not inherently present more or less problems than other approaches. That it does not fit neatly in the Haskell universe is the result of various constraints and preferences within Haskell's design, just as some of Haskell's mechanisms fit poorly into other languages. These are not universal problems; this is about language design constraints.

I'm happy that you posted this. It's something that I discovered on my own, and have been tentatively arguing for years[1][2][3][4].

In fact, I never really understood the visitor pattern until after I started using ML's pattern matching. The "eureka" moment came when I realized that not only do abstract classes map to sum types (logical disjunction), but interfaces correspond to product types (logical conjunction).

[1] https://www.reddit.com/r/programming/comments/2e572a/rebutta...

[2] https://www.reddit.com/r/programming/comments/14t3ay/either_...

[3] https://news.ycombinator.com/item?id=822479

[4] http://stackoverflow.com/questions/19696342/limiting-class-a...

> First, inheritance provides a strict superset of standard ADT functionality.

That's not true. Much of the value of ADTs in OCaml is full type inference. Scala has type inference, but it only sorta-kinda sometimes works.

In other words, a lot of the value of OCaml's types are that they are quite flexible, while still having enough restrictions for the compiler to usefully reason about them.

> That's not true. Much of the value of ADTs in OCaml is full type inference.

I consider using type inference for your interfaces to be a software engineering anti-pattern. (Scala also doesn't really support that, except for return types, but you see related issues if you try type inference with objects in OCaml.) Without explicitly typing your interface, users have to look at the implementation to know what the type of a function is. Type inference for local entities is usually pretty easy.

Most of the remaining problems with type inference in Scala are the result of prioritizing Java interoperability in the type system, leading to a number of contortions and workarounds.

I don't necessarily disagree with what you've said, my main point was that much of the value of ADTs in OCaml is in their restrictions.

> 3. OCaml in particular uses 63/31-bit ints due to implementation details, which isn't a good fit for 64/32-bit integers

I'm not sure what "isn't a good fit" is supposed to mean.

Try storing an integer literal that requires 64 bits in a variable that can hold only 63 bits.

It's not going to make it impossible (you may just need something like a ShortIntLiteral and a LongIntLiteral variant), but it's going to require additional effort.

Sure, but not many real programs actually need the full 64-bits. Many of the ones that may seem to require the full bit width are doing bit ops on larger bit streams, for which there's ocaml-bitstream. What sort of programs are you thinking of?

Umm, compilers? That's what the post was about. Compilers need to be able to represent integer literals up to machine precision.

Compilers for languages with full-width integers need to represent full-width integer literals while compiling, sure. I'm not sure that it's:

a) all that common to need full width integers while compiling even these languages, and

b) all that problematic to use boxed numbers in this context, or big_int.

What you are saying here is that it isn't a huge problem in practice, and I agree with that. However, that's not what the original post was saying. It said that OCaml was especially suited for writing compilers because of its ints, which is the exact opposite claim.

Use Int64.t?

1. This wasn't what the original article was talking about.

2. int64's are normally boxed.

The problem with this article is that it's missing an answer to why one would choose ML/OCaml over Haskell. Haskell has many more features, a more advanced type system, arguably superior syntax, and much better library support. However, I believe that OCaml/SML are often a better choice for a number of reasons.

First of all, OCaml/SML are the best choice in terms of example code for compilers. They're historically the choice of many compiler/interpreter/type theory texts (Types and Programming Languages, Modern Compiler Implementation in ML, and an ML is even used as a language to interpret in Essentials of Programming Languages). Andrej Bauer's PLZOO is also written in OCaml. Equally important is the fact that there are a variety of ML implementations, all of which are much more approachable than GHC. The OCaml compiler's codebase is a reasonable size that an individual could get a good idea of how it works in a few weeks or so. SMLNJ, MLKit, MLton, CakeML are all open source and on Github, and all seem to be fairly approachable in comparison to the monolith that is GHC. And that's not even mentioning other compiler in ML (Haxe, Rust's bootstrap compiler, Facebook's Hack compiler, etc.). The fact that there are real-world compilers with perfectly approachable code bases (even without great familiarity with the language; compilers in Haskell might require an in-depth understanding of many of the core type classes and language extensions available) that are open source is highly attractive to novice compiler writers.

Additionally, the feature set in MLs is a good choice for compilers. While they lack some of the cooler features of Haskell, MLs make up for it in simplicity; lots of the features in GHC's type system (especially with language extensions) mean very little for 90% of compiler writers, and getting rid of them from the get-go helps keep the code small and easy to reason about (even if you won't have as much type safety in the compiler itself). This also means that there are a lot less ways to do a single thing, which can be nice when you're not sure exactly how you're going to implement a certain feature. However, one thing I really find incredibly useful is OCaml's polymorphic variants. These are pretty much perfect for statically enforcing a nanopass-like system in your compiler and are a great way of designing your AST/data types in your compiler. I feel like this gets passed up a ton (as far as I know I'm the first person who's used them to create nanopasses), but it's quite convenient and makes OCaml a good competitor for Scheme in this regard.

Also, Haskell is something of a soup of DSL-operators that require one spend significant time researching what they mean and what behaviour they induce. Even with such knowledge, it suffers from the Perl-ish woe of write-once and read-never.

Wholly disagree. Yes in Haskell you can define operators yourself (they are just functions but made out of special characters and placed after the first argument, e.g.: "Hi " ++ username); and this is often done by Haskellists. So you sometimes need to learn a few new operators that come with a library to WRITE code using that lib; but in order to READ code I rarely need to ref the docs, it is just evident from the context.

> it suffers from the Perl-ish woe of write-once and read-never.

My experience with Haskell is opposite, I think Haskell yields very maintainable code that is largely self documenting and allows me to confidently hack around old code bases.

My experience with Perl is the same. Very hard to read back, maintain or get productive on old code bases.

I'll just leave [Control.Lens.Operators](http://hackage.haskell.org/package/lens-4.15.1/docs/Control-...) here...

In defense of Haskell, the situation is similar in Scala. I think some people just prefer inventing their own operators instead of using descriptive names.

To be fair, a number of those operators are

> This is an infix alias for cons. > This is an infix alias for snoc. > A convenient infix (flipped) version of toListOf. > An infix version of itoListOf.

And a lot of them are (<+~) and friends.

shrug When I look at Haskell code I see overly terse expressions and nothing resembling the concept of self-documentation.

Are you fluent in Haskell?

I was some years ago, before I gave up on the language; but one shouldn't have to be fluent in a language for it to satisfy the concepts of self-documentation and readability.

Requiring domain-specific knowledge of symbolic notation is not a trait of self-documenting languages. Recommending that the API search engine be open alongside or within your editor is likewise not a trait of self-documenting languages.

Self-documenting languages are coherent at-a-glance to average programmers with little to no knowledge of the language. Haskell is not this.

This article is from 1998, the landscape was much different. Haskell had a handful of the language features it has today, and was lacking many of the innovations in its runtime and libraries.

Very true. I didn't mean this so much as a criticism of the article, but more of an addition to what the article was already saying. I think all the arguments addressed in it are pretty good, but it's not 100% up to date with the current FP world.

Haskell may indeed be one of the most advanced languages out there in terms of raw power, but it is very complex (how many monad tutorials does it seriously take to teach one of the most core pieces of the language) and how much category theory do you need to know to be moderately effective? Also, the ecosystem could use some work. An example is the main string library isn't used in favor of a different one. Using the first and obvious one leads to performance worse than python and perl even after you compile. I'm being nitpicky, but anytime someone writes a blog post comparing a programming language to playing darksouls (game where you die thousands of times) I'd say you have an issue.

Honestly, none. I'm not a category theorist, and have no more understanding of monads than anyone who's used a javascript promise library, and I've been employeed professionally as a Haskell programmer for the past year, contributed libraries back to the community, and given talks in my local area.

Haskell is a language like any other. Many people would like to complicate it, but if you spend the time learning its syntax and semantics, there is very little need to learn the theory.

I started to write a toy compiler in OCaml. I had some previous experience with Haskell, but in no way an expert. I.e. no category theory background, only shallow exposure to monads.

My "problems" with OCaml started, when I wanted to "map" over a data structure I defined. I ended up having to define custom mapping functions for all container-like data structures I wrote and call them in a non-polymorphic fashion (where I would have just used fmap in Haskell).

Sure, in OCAML I needed to use a parser generator where I would have used megaparsec in haskell, but it was also a tolerable inconvenience.

Trouble started when I needed to track state in the compilation process. I.e. I was generating variable names for temporary results and values, and I needed to track a number that increased. In the end I used a mutable state for it, and it turned out nightmarish in my unit tests.

After a while, I just ported the code base to Haskell and never looked back. The State monad was an easy fix for my mutable state issues. Parser combinators made the parser much more elegant. And many code paths improved, became much more concise. It is hard to describe, but in direct comparison, OCaml felt much more procedural and Haskell much more declarative (and actually easier to read).

The only advantage of OCaml to me is the strict evaluation. I don't think lazy evaluation by default ins Haskell is a great idea.

I assume you were just not interested in passing the state around to the functions that needed it, and preferred the fact that the state monad hides that plumbing for you via bind and return. It's worth noting that there exist Ocaml libraries that provide the same operators and even similar do notation syntax that desugars to bind/return operators (via PPX).

Ocaml does tend to be more verbose than Haskell - it's just the nature of the language syntax. E.g., in Ocaml, one says (fun x -> x+1) vs (\x -> x+1). Similarly, ocaml is cursed by the excessive "in"'s that accompany let bindings. "Let .. in let .. in let ...". That can get annoying.

Interestingly, I had the opposite experience with a commercial compiler project. Haskell's syntactic cleverness (monadic syntax, combinator libraries, etc..) eventually got in the way - it became very difficult to understand what a single line of code actually meant since one had to mentally unpack layers of type abstractions. Migrating to ocaml, the verbosity eventually was more tolerable than the opacity of the equivalent Haskell code once the compiler got sufficiently complex.

My experience may vary from yours. I've been doing Haskell/Ocaml in production for many years, so the pain points I've adapted to are likely different than one working on toy compilers or weekend projects. And no, category theory exposure is not and never has been necessary for understanding Haskell or FP unless one is a PL researcher (and even then, only a subset of PL researchers are concerned with those areas). And one can be quite productive and prolific in Haskell without a deep understanding of monads and monad transformers - the blogosphere has given you the wrong impression if you believe otherwise.

I've done a lot of production Haskell and I've had a similar experience.

In our case, we dealt with it by keeping relatively bare, boring code. We avoided point-free style, crazy combinators like lenses, and complex monad transformer stacks except in the 'plumbing' part of the application that didn't need to change very much.

This paid off in spades as we had a lot of engineers who only ever had to work in the 'porcelain' parts of the application. They got a lot of great work done using abstractions that matched their intuition exactly.

Thanks for the thorough reply and it sounds like you're quite experienced here. Any chance going into more detail with what you do for a living? Do you maintain a compiler for something more mainstream?

I cofounded a company recently that is using code transformation and optimization methods to accelerate data analytics code on special purpose hardware. Our compilation toolchain is all ocaml, and the language that is compiled/transformed/optimized is Python. Prior to this venture, I did similar work - code analysis and transformation, but in that case largely around high performance computing for scientific applications. That tooling was mostly ocaml/Haskell, but not production focused - it was mostly research code.

Just want to note that, while not frequently seen, you can use more powerful abstractions (monad transformers, parser combinators, etc) in OCaml.

As an example consider looking at the Angstrom[1] parser combinator library and my Pure[2] functional base library.

[1] https://github.com/inhabitedtype/angstrom

[2] https://github.com/rizo/pure

> (how many monad tutorials does it seriously take to teach one of the most core pieces of the language) and how much category theory do you need to know to be moderately effective?

I believe the answer to both questions is zero. Unfortunately there is pedagogical cruft in the community that makes it appear this way. main :: IO () is comparable to public static void main(args[]) or whatever nonsense in Java.

> These are pretty much perfect for statically enforcing a nanopass-like system in your compiler and are a great way of designing your AST/data types in your compiler.

Nice, I was just asking about this on the nanopass list the other day, do you happen to have a publicly available example of this anywhere?

For anyone interested and isn't aware yet Facebook is developing Reason, a layer over OCaml. I've been fiddling with it for the past couple of weeks and coming from JavaScript I personally found the experience generally enjoyable.


Hah! Thanks for the link- I discovered this gem just now in their list of comparisons to JS syntax:

  Javascript    | Reason
  const x = y;  | let x = y;
  let x = y;    | reference cells
  var x = y;    | No equivalent (thankfully)

:) Yeah, unfortunately JavaScript can only be improved by educating people not to use the horrible parts (rather than fixing/deprecating them which is not possible). const and let were extremely necessary.

That was an extremely pleasant and convincing introduction, thank you for that. I'm definitely going to give this a try in future projects.

I agree that Ocaml is just extremely well suited for making new programig languages. If you are interested in Ocaml+programming languages check out the plzoo: http://plzoo.andrej.com/

I personally think that Ocaml is really good at this, because I started converting the Scheme examples from the PLAI book to Ocaml and it's just felt right(maybe because I'm not fan of the scheme syntax).

OCaml has the potential to be great for almost everything with some work and a bigger ecosystems. F# as well (very similar). i can only imagine how great the world would be if a standard ml had accidentally become the web browser language and all that mind share had gone into evolving it and optimizing it and its tools.

Currently taking a compilers course that uses SML/NJ and it has been an absolute delight. The functional paradigm is a little strange to get used to at first, but after a while its strong suits make themselves known. The trivial type inferences and pattern matching capabilities make it easy to efficiently describe complicated and precise program situations.

I'm a relatively young developer (three years older than Java) and don't fully get the thing about exceptions (point 7). It sounds very familiar to the solution I know from Java, and it does not make safety - or even feeling about it - any better. If you can still write code that can throw exception and an explicit assurance about it is the only way to prevent the crash, it doesn't change anything, actually.

P.S. I'm not really familiar to ML/OCaml, but have decent experience with large code bases in languages that are not very keen to protect you from yourself.

Exceptions in ML languages are very similar to those in Java. The reason for that is simple: they are simply a good way of dealing with computations that might fail. Having said that, exceptions are best used (in any language) where you want to deal with the failure way up in the call stack. If you catch the exception right where it occurs, you should just use a safe method that reports a failure in the return value.

Speaking as a Haskell programmer, never use exceptions. You can get away with this advice because the Either monad allows you to have the behavior of exceptions (namely, at any point you can "fail" a computation and have the error automatically propagate up to the handler). However, this approach relies heavily on having a type system more advanced than OCaml's in order to be reasonable.

The Either pattern for errors works great in OCaml; most of the code I write uses it. I'm not sure what problem you're referring to.

FP is based on recursion, and recursive types, inductive algorithms are essential for linguistic processing and transformation.

How are simple parsers written in ML (or ocaml)?

You can't use the coding style used for recursive descent in the Dragon compiler book, without using mutable variables.

Do you have to use parser combinators, which have their own limitations?

Parser combinators tend to work by recursive descent, so cannot handle left recursive grammars [1], and tend to be really slow. The latter is not a problem for many applications, but removing left recursion can be irritating even for small grammars. It is possible to build combinator parsers that can handle all context-free grammars [2], but I'm not sure any of Ocaml's are built that way.

In any case, Ocaml has parser generators that are fast, do bottom-up parsing (hence handle left-recursion without issue) and not based on parser combinators, e.g. ocamlyacc [3].

I'd use parser combinators for quick prototypes, and, if measurement shows a performance problem, replace them with a generated (e.g. by ocamlyacc) parser. As far as I remember the parser in Ocaml's (superfast) compiler is generated by ocamlyacc.

[1] https://en.wikipedia.org/wiki/Left_recursion

[2] T. Ridge, Simple, functional, sound and complete parsing for all context-free grammars. http://www.tom-ridge.com/resources/ridge11parsing-cpp.pdf

[3] https://caml.inria.fr/pub/docs/manual-ocaml/lexyacc.html

In production code we tend to use ocamlyacc or menhir. There is nothing about ocaml/ML that prohibits the use of the kind of parser generators one would expect in any other language.

You can do mutation in both Standard ML and OCaml. If I recall, Robert Harper's book on Standard ML starts off with a recursive descent parser.

The most common way is using a parser generator (ocamlyacc or menhir, both are basically interchangeable 99% of the time). Parser combinators are a choice, but honestly I think recursive descent parsers are more common than combinators in OCaml.

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact