| HN Mirror

Y	Hacker News new \| ask \| show \| jobs

by rbehrends 3356 days ago

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.

4 comments

tom_mellior 3355 days ago

> 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
          end
        | Branch (left, right) ->
          (* Visit the left subtree, save the right for visiting later. *)
          iter_rec f (right::worklist) left
      in
      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.