6 ms·

I think compiler implementation is a particular sweetspot for functional languages. Here's a similar tiny example in Haskell: http://www.timphilipwilliams.com/

I think compiler implementation is a particular sweetspot for functional languages. Here's a similar tiny example in Haskell: http://www.timphilipwilliams.com/posts/2014-05-22-the-essence-of-compilation.html http://www.timphilipwilliams.com/posts/2014-05-22-the-essenc...

pjmlp 9y ago
When I did my degree, the older students were forbidden to use any language from the Lisp, ML or Prolog families for the compiler design assignment as that would be too easy. As Java was just released by the time my class got to do the same assignment, we ended up using Java with JavaCC and JJTree. While not as easy as Lisp, ML or Prolog, it was still much easier than the Jurassic yacc/lex that still prevails in some circles.
- smadge 9y ago
  Something about that rule seems extremely backwards to me. Might as well implement a Prolog or Scheme in a lower level language then do your compiler assignments in that. Reminds me of this quote "Any sufficiently complicated C or Fortran program contains an ad-hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp." Source: https://en.m.wikipedia.org/wiki/Greenspun%27s_tenth_rule https://en.m.wikipedia.org/wiki/Greenspun%27s_tenth_rule
- 1298312321 9y ago
  What is this nonsense? ML uses yacc and lex. Again, could you point us to a repository that contains your work?
- willtim 9y ago
  I think I'd have been confused as to why using a parser generator was also not similarly regarded as being too easy :) Interestingly, most mature industrial languages (e.g. Java, GCC, clang) use hand-coded recursive descent parsers. And of course such parsers can be implemented very easily from first principles using parser combinators in FP. I've used both JavaCC and Antlr in the past for small DSLs, both are very good tools, when working with Java.
  - pjmlp 9y ago
    Yeah, I guess it comes down to the later compiler layers, when doing data structure manipulation for the actual code generation. Pattern matching and FP/LP based algorithms are quite convenient, versus doing it in an imperative approach. Hand coded parsers win on the error reporting front.
- seanmcdirmid 9y ago
  You’d be surprised how much hand written recursive descent is dominant in industry, and to be honest, I think it is often easier than using generator magic. Everyone who is into compilers and parsing should try recursive descent at least once.
  - pjmlp 9y ago
    True, but it should only be done after getting a working compiler, to get good error handling and messages. From my experience most people don't use parser generator tools due to lack of knowledge that they even exist.
    - seanmcdirmid 9y ago
      People don't use parser generator tools because you wind up doing more work than needed to integrate it with the rest of your compiler. The reason to use a parser generator is not for ease of use or rapid development (because they are harder to use and slower to develop with) but for performance and reliability. The first one isn't such a big deal for most programming languages, the second one is. Throw in better error handling and tricks like sub-file incremental and/or heuristical compilation (for IDEs), and the generators don't make much sense anymore.
      - willtim 9y ago
        > People don't use parser generator tools because you wind up doing more work than needed to integrate it with the rest of your compiler. I don't think you can make such a sweeping generalisation. Both JavaCC and Antlr have saved me a lot of time when doing DSLs in the past and both are well documented and easy to use. It would have been much more work for me to write the parsers by hand in Java. Both could also generate my own hand-rolled AST easily and so I do not see why integration would be a problem for most projects. I agree that generators do not scale to large compilers or projects with special needs, but that is not most projects.
      - pjmlp 9y ago
        That makes sense after having a language reaching 1.0 in production use. Not so much when prototyping, when it isn't even clear if the language is going to get any users beyond the design team.
- deleted 9y ago
  [deleted]
amelius 9y ago
> I think compiler implementation is a particular sweetspot for functional languages. Compilers often use graphs as intermediate representation, and functional languages often are not a good fit for dealing with them.
- willtim 9y ago
  Modern compilers seem to work with trees more often than graphs. Trees would certainly be easier to work with in any language. That said, functional languages can and do work with graphs when needed, but yes it is much more awkward than trees.
  - thangngoc89 9y ago
    Tree is also a form of graph
  - seanmcdirmid 9y ago
    Not down in the lower levels of IR and IL, the trees have mostly disappeared by then. If you are just interpreting or doing unoptimized compiling, you can get by with just trees.
    - willtim 9y ago
      GHC Haskell does nearly all its optimisation using trees and a high-level functional IR, so I think you are understating trees.
      - seanmcdirmid 9y ago
        Yes, but I don't think they require a low-level IR in that case (purity, no re-assignment, no loops). LLVM does not use trees at that level, for example, because they really need to use stuff like SSA, basic blocks, and so on.
  - deleted 9y ago
    [deleted]
- 9y ago

pjmlp 9y ago

When I did my degree, the older students were forbidden to use any language from the Lisp, ML or Prolog families for the compiler design assignment as that would be too easy. As Java was just released by the time my class got to do the same assignment, we ended up using Java with JavaCC and JJTree. While not as easy as Lisp, ML or Prolog, it was still much easier than the Jurassic yacc/lex that still prevails in some circles.

smadge 9y ago
Something about that rule seems extremely backwards to me. Might as well implement a Prolog or Scheme in a lower level language then do your compiler assignments in that. Reminds me of this quote "Any sufficiently complicated C or Fortran program contains an ad-hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp." Source: https://en.m.wikipedia.org/wiki/Greenspun%27s_tenth_rule https://en.m.wikipedia.org/wiki/Greenspun%27s_tenth_rule
1298312321 9y ago
What is this nonsense? ML uses yacc and lex. Again, could you point us to a repository that contains your work?
willtim 9y ago
I think I'd have been confused as to why using a parser generator was also not similarly regarded as being too easy :) Interestingly, most mature industrial languages (e.g. Java, GCC, clang) use hand-coded recursive descent parsers. And of course such parsers can be implemented very easily from first principles using parser combinators in FP. I've used both JavaCC and Antlr in the past for small DSLs, both are very good tools, when working with Java.
- pjmlp 9y ago
  Yeah, I guess it comes down to the later compiler layers, when doing data structure manipulation for the actual code generation. Pattern matching and FP/LP based algorithms are quite convenient, versus doing it in an imperative approach. Hand coded parsers win on the error reporting front.
seanmcdirmid 9y ago
You’d be surprised how much hand written recursive descent is dominant in industry, and to be honest, I think it is often easier than using generator magic. Everyone who is into compilers and parsing should try recursive descent at least once.
- pjmlp 9y ago
  True, but it should only be done after getting a working compiler, to get good error handling and messages. From my experience most people don't use parser generator tools due to lack of knowledge that they even exist.
  - seanmcdirmid 9y ago
    People don't use parser generator tools because you wind up doing more work than needed to integrate it with the rest of your compiler. The reason to use a parser generator is not for ease of use or rapid development (because they are harder to use and slower to develop with) but for performance and reliability. The first one isn't such a big deal for most programming languages, the second one is. Throw in better error handling and tricks like sub-file incremental and/or heuristical compilation (for IDEs), and the generators don't make much sense anymore.
    - willtim 9y ago
      > People don't use parser generator tools because you wind up doing more work than needed to integrate it with the rest of your compiler. I don't think you can make such a sweeping generalisation. Both JavaCC and Antlr have saved me a lot of time when doing DSLs in the past and both are well documented and easy to use. It would have been much more work for me to write the parsers by hand in Java. Both could also generate my own hand-rolled AST easily and so I do not see why integration would be a problem for most projects. I agree that generators do not scale to large compilers or projects with special needs, but that is not most projects.
    - pjmlp 9y ago
      That makes sense after having a language reaching 1.0 in production use. Not so much when prototyping, when it isn't even clear if the language is going to get any users beyond the design team.
deleted 9y ago
[deleted]

amelius 9y ago

> I think compiler implementation is a particular sweetspot for functional languages. Compilers often use graphs as intermediate representation, and functional languages often are not a good fit for dealing with them.

willtim 9y ago
Modern compilers seem to work with trees more often than graphs. Trees would certainly be easier to work with in any language. That said, functional languages can and do work with graphs when needed, but yes it is much more awkward than trees.
- thangngoc89 9y ago
  Tree is also a form of graph
- seanmcdirmid 9y ago
  Not down in the lower levels of IR and IL, the trees have mostly disappeared by then. If you are just interpreting or doing unoptimized compiling, you can get by with just trees.
  - willtim 9y ago
    GHC Haskell does nearly all its optimisation using trees and a high-level functional IR, so I think you are understating trees.
    - seanmcdirmid 9y ago
      Yes, but I don't think they require a low-level IR in that case (purity, no re-assignment, no loops). LLVM does not use trees at that level, for example, because they really need to use stuff like SSA, basic blocks, and so on.
- deleted 9y ago
  [deleted]
9y ago