[francogt]

I see many comments saying that the book implements the C compiler in ocaml. In the introduction the author states that the book actually uses pseudo code so you are actually free to implement it in any language. The only recommendation is that you use a language with pattern matching because the pseudo code makes heavy use of it. The reference implementation is in ocaml.

[markus_zhang]

Thanks, can you please lemme know which part uses pattern matching? I'd assume mostly in the lexer, but the parser should just be something that consume the tokens and spit out AST. Unless of course it combines the two.

[shawn_w]

Presumably anything that walks the syntax tree.

[markus_zhang]

Thanks. At first I thought it is something like regex, but then I found it's something in functional programming. I need to read a few chapters of the book before buying it because I'm not interested in learning FP at the moment.

[CrimsonCape]

Question for HN, pattern matching is defined as “runtime type/value checking”, is that correct?

Is duck typing the pseudo-unsafe alternative? (Not unsafe as in accessing unsafe memory, but as in throwing exceptions if the duck-typed function doesn’t exist on the current type)

Can C handle both?

Coming from a static type system like rust and c#, i’m doing alot of “if this is a duck, duck.quack()” and i’m looking for faster alternatives and less verbosity if possible

[trealira]

One thing is that pattern matching can make writing tree manipulation code succinct and easier to read. For example, take this article[0] that describes the difference list algorithm (in Haskell). Basically, it's kind of like a rope, but for lists. It's a tree with lists at the leaves, and when you want to convert it into a list, you rewrite the tree to be right-leaning, and then concatenate all the lists at once. This turns repeated concatenation at the end of lists from taking quadratic time into one that takes linear time (strcpy can be an example of this in C [1]). The code can be written like this:

  data Tree a = Leaf a | Branch (Tree a) (Tree a)

  fromList :: [a] -> Tree [a]
  fromList = Leaf

  toList :: Tree [a] -> [a]
  toList (Leaf x) = x
  toList (Branch (Leaf x) r) = x ++ toList r
  toList (Branch (Branch l1 l2) r)
               = toList (Branch l1 (Branch l2 r))

  append :: Tree [a] -> Tree [a] -> Tree [a]
  append = Branch

In a language that doesn't have tree pattern matching, the code wouldn't be this short and easy to understand, and I don't think it could be replicated just by having duck typing. Rust has pattern matching, but because it's primarily focused on lower-level concerns like pointers and memory ownership, pattern matching isn't this nice, because you have to pattern match on the pointer first.

Since a compiler is all about tree manipulation, support for tree pattern matching should be a boon.

[0]: http://h2.jaguarpaw.co.uk/posts/demystifying-dlist/

[1]: https://en.wikipedia.org/wiki/Joel_Spolsky#Schlemiel_the_Pai...

[ashconnor]

Useful list considering that feature: https://en.wikipedia.org/wiki/Category:Pattern_matching_prog...

[songbird23]

I can implement it in rust?