Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Why ML/OCaml are good for writing compilers (1998)

flint.cs.yale.edu

Post reply on HN
Print view View original

81–90 of 151 posts

Re: Why ML/OCaml are good for writing compilers (1998)

#81

Post by mafribe »

hyperpallium wrote: post #50

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

Re: Why ML/OCaml are good for writing compilers (1998)

#82

Post by cies »

dleslie wrote: post #11
nv-vn wrote: post #6

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 th…

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.

Re: Why ML/OCaml are good for writing compilers (1998)

#83

Post by throwaway7645 »

batmansmk wrote: post #71
throwaway7645 wrote: post #5

Earlier quoted context omitted.

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?

Re: Why ML/OCaml are good for writing compilers (1998)

#84

Post by throwaway7645 »

haskellandchill wrote: post #43
throwaway7645 wrote: post #5

Earlier quoted context omitted.

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.

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?

Re: Why ML/OCaml are good for writing compilers (1998)

#85

Post by mafribe »

hongbo_zhang wrote: post #30

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 genera…

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.)

Re: Why ML/OCaml are good for writing compilers (1998)

#86

Post by data_hope »

throwaway7645 wrote: post #32
nv-vn wrote: post #6

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 th…

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 th…

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.

Re: Why ML/OCaml are good for writing compilers (1998)

#87

Post by LeonidasXIV »

akhilcacharya wrote: post #4
Dangeranger wrote: post #3

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…

>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.

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.

Re: Why ML/OCaml are good for writing compilers (1998)

#88

Post by ms013 »

hyperpallium wrote: post #50

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?

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.

Re: Why ML/OCaml are good for writing compilers (1998)

#89

Post by continuational »

cies wrote: post #82
dleslie wrote: post #11

Earlier quoted context omitted.

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 c…

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.

Re: Why ML/OCaml are good for writing compilers (1998)

#90

Post by ms013 »

data_hope wrote: post #86
throwaway7645 wrote: post #32

Earlier quoted context omitted.

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 th…

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 (whe…

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.

Post reply on HN