5 ms·

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

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.

willtim 10y ago
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.
- rbehrends 10y ago
  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_mapper.htm https://caml.inria.fr/pub/docs/manual-ocaml/libref/Ast_mappe... [2] https://people.eecs.berkeley.edu/~necula/cil/api/Cil.cilVisitor.html https://people.eecs.berkeley.edu/~necula/cil/api/Cil.cilVisi...
  - willtim 10y ago
    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.
    - rbehrends 10y ago
      > 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.
coolsunglasses 10y ago
>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 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.
- willtim 10y ago
  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.
- tom_mellior 10y ago
  > 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?
naasking 10y ago
> 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.
- rbehrends 10y ago
  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.
  - gsg 10y ago
    Use Int64.t?
    - rbehrends 10y ago
      1. This wasn't what the original article was talking about. 2. int64's are normally boxed.
  - naasking 10y ago
    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?
    - rbehrends 10y ago
      Umm, compilers? That's what the post was about. Compilers need to be able to represent integer literals up to machine precision.
      - naasking 10y ago
        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.
tom_mellior 10y 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.
- rbehrends 10y ago
  > 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.
  - tom_mellior 10y ago
    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.

willtim 10y ago

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.

rbehrends 10y ago
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_mapper.htm https://caml.inria.fr/pub/docs/manual-ocaml/libref/Ast_mappe... [2] https://people.eecs.berkeley.edu/~necula/cil/api/Cil.cilVisitor.html https://people.eecs.berkeley.edu/~necula/cil/api/Cil.cilVisi...
- willtim 10y ago
  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.
  - rbehrends 10y ago
    > 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.

coolsunglasses 10y ago

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

willtim 10y ago
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.
tom_mellior 10y ago
> 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?

naasking 10y ago

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

rbehrends 10y ago
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.
- gsg 10y ago
  Use Int64.t?
  - rbehrends 10y ago
    1. This wasn't what the original article was talking about. 2. int64's are normally boxed.
- naasking 10y ago
  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?
  - rbehrends 10y ago
    Umm, compilers? That's what the post was about. Compilers need to be able to represent integer literals up to machine precision.
    - naasking 10y ago
      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.

tom_mellior 10y 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.

rbehrends 10y ago
> 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.
- tom_mellior 10y ago
  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.