Comment by herodotus | Hacker News Reader

Comment by herodotus | Hacker News Reader

Parent Full thread

Here is an historical note for those who might be interested. In 1979 I did a Post-doc with Rod Burstall. I helped implement the programming language Hope, which was the first functional programming language to use pattern-matching in function definitions. The implementation was written in an older language called POP-2. Robin Milner and his group were at the the time working on LCF and ML, and they eventually incorporated Burstall's pattern ideas. Eventually, I recall there was a decision within the UK functional programming community to consolidate their efforts into what became Haskell. And of course we see how much Haskell has influenced the newest crop of imperative languages.

It is interesting (to me) to compare factorial in Rust with factorial in Hope:

Rust:

fn factorial(i: u64) -> u64 {

    match I {

        0 => 1,

        n => n * factorial(n-1)
    }

}

Hope:

dec factorial : num -> num;

--- factorial 0 <= 1;

--- factorial n <= n* factorial(n-1);

Note that, in Hope (unlike its own inspiration, Prolog, and, I think unlike Rust), the order of the rules does not matter: the most specific pattern takes precedence. Hope was primitive with respect to types, and did not use Milner's type inferrencing ideas. I don't think Burstall ever intended it to be a "real" programming language. When I left Edinburgh, Don Sanella took over from me, so I was not involved in writing the paper about Hope, but my contribution is acknowledged.

I implemented the pattern matching code, and the idea of pattern compilation occurred to me. I remember showing it to Rod. He freaked out at first, but after about a five minute harangue, the penny dropped, and I remember him saying "clever Michael", "clever Michael" in his charming way.

Very cool, thank you for this history!

> I think unlike Rust

Yes, this is correct: Rust looks at patterns in order, top to bottom.

Incidentally, some folks have asked for a syntax closer to Hope (and Haskell, and others) https://github.com/rust-lang/rfcs/pull/1564

  fn factorial(0: u64) -> u64 { 1 }
  fn factorial(n: u64) -> u64 { n * factorial(n - 1) }

I doubt this will ever happen, though.

I really hope this doesn't happen.

I've never understood the infatuation for this Haskell type syntax where you need to repeat the name of the function for each and every single match case. It's so needlessly verbose.

Most languages which allow for function head clauses also have case or switch statements. So you can use both. I like the pattern when there is a corner case that needs quite a bit of logic but it's not very important for how the code usually works, and you won't want an indent level on it. For example:

    function(SpecialCase ...) ->
       ...
       handle_odd_special_case;

    function(DefaultWhatever ...) ->
       ...
       main_business_logic.

This is more cleaner _sometimes_ than say

    function(...) ->
       case Arg of
           SpecialCase ->
               ...
               handle_odd_special_case;
           Default ->
                ...
                main_business_logic
    end

Now imagine another level of case statements and all of the sudden the main path of the algorithm is squashed to the right with only a 40 columns left.

It seems to me that the things people like about the haskell style syntax are

1. Don't have to name the parameter

2. less nesting.

You can get the best of all worlds with lambdacase style constructs. You don't need to write out the name of the function a bunch of times.

  function = \case
    SpecialCase ->
      ...
      handle_odd_special_case;
    Default ->
      ...
      main_business_logic;

I find it dramatically cleaner.

Each clause is categorically isolated, unlike a case statement (the alternative in Erlang, with which I’m most familiar) where code can precede the case statement and thus introduce bindings that can muck up the logic.

Yes but why repeat the name of the function every time?

It might make more sense if such clauses are scattered through the source, but they are pretty much all the time grouped together, so the name of the function doesn't need to be repeated all the time.

For example, instead of

    factorial 0 => 1;
    factorial n => n* factorial(n-1);

Something like

    factorial {
        0 => 1
        n => n* factorial(n-1);
    }

A lot of this has its origin in Prolog, and there having multiple full definitions is much more natural, given the nature of the language: each predicate can have any number of definitions and then you have back-track to find the right one. A trivial example:

    parent(alice, brad).
    parent(alice, cecilia).
    parent(cecilia, david).
    parent(david, emily).
    parent(brad, felix).
    parent(felix, ginny).
    
    ancestor(A, B) :- parent(A, B).
    ancestor(A, B) :- parent(A, M), ancestor(M, B).

The first section defines a small family: alice is the parent of brad and cecilia, cecilia is the parent of david, etc. (identifiers beginning with lower-case letters are atoms, the ones beginning with upper-case are variables). Note that for these first definitions without a body (called "facts" in prolog), it's perfectly natural to have multiple "definitions": you can have as many parent-child relations as you want.

The second predicate ("ancestor") is more interesting: it has two definitions: if A and B are people, then A is the ancestor of B if A is the parent of B, or if A is the parent of M, and M is the ancestor of B.

Notice that there are is no pattern matching happening (Prolog of course has pattern matching, it more or less invented the concept, but I'm not using it here). When you use "ancestor", Prolog has no idea which definiton you want, the patterns are identical. It has to try the first one, and if it fails, it backtracks and tries the second one.

Some examples of using this in the repl. First, "who are alice's children":

    ?- parent(alice, Child).
    Child = brad ;
    Child = cecilia.

The semi-colon means "or", so this means "Child is equal to brad, or Child is equal to cecilia". Second, "who are ginny's ancestors":

    ?- ancestor(Ancestor, ginny).
    Ancestor = felix ;
    Ancestor = alice ;
    Ancestor = brad.

The central idea here is that there is no "one definition" of a predicate or fact, you can have as many as you want, and prolog will search through them. Similarly, any query can have multiple values for the variables that make them true. Repeating the predicate name is the most natural way of expressing this idea. You don't have to, you could rewrite these so that they had only one definition, but that just makes what's going on less clear.

Both are possible in Haskell:

  factorial 0 = 1
  factorial n = n * factorial (n - 1)

  // or:

  factorial n = case n of
    0 -> 1
    n -> n * factorial (n - 1)

Repeating the name allows some optimizations but you'd be unlikely to use or benefit from them unless you were writing functions that returns functions and you could benefit from inlining some patterns and not others.

I think I've seen the pattern in some web framework code, byte libraries, etc.

Although semantically equivalent, the optimizer treats the following differently:

    f a = \b -> ...
    f a b = ...

As much as I like short functions, not all function clauses are just one line. I don’t see your alternative as helpful for longer clauses.

Whatever syntactic means you use to specify long clauses with the current syntax you can reuse with my syntax.

Yes, but function names are a useful way to separate long clauses

It's probably for double dispatch, which Rust doesn't have outside of traits anyway.

No way is it clearer. Moving a pattern match to the top level removes the obvious intent that two (or more) functions overload each other and remove the debug/trace point for figuring out why one body was chosen over another.

I would argue that depends on the language. Neither issue you describe is a problem in Erlang.

Might be wrong here, but if this is to work, will it work across different compilation units? E.g. what if there is a "rogue" version that matches some literal - in way it'll serve as AOP (aspect oriented programming), but it'll be more like monkey patching. It may be useful, but spooky. (Very basic rust/haskell knowledge, just familiar with the core concepts).

The proposal stated:

> Every function clause must be together. It is an error to put another item between two function clauses.

So, it would not. Then again, the proposal wasn't accepted so it's kind of a moot point. But you're totally right that without this it would be very tricky. Given that match arms have an ordering, I'm not sure you could come up with a semantic where it would work across compilation units.

I suspect that Rod Burstall was more interested in conceptual clarity than compactness. I often heard him say "Efficiency is the enemy of clarity". Of course he was probably referring to code, but he might have applied the same thought to language syntax.

I write Elixir (which uses this syntax) and Rust (which doesn't) and I think both are fine. I'm hoping Rust doesn't support this mostly because I don't think the language support this sugar solves any problems Rust has.

Lacking this is probably my biggest gripe when trying to pattern match recursive structures, though mostly closures, this saddens me, you could say my hopes have been dashed.

Hope is pretty close to the Erlang version:

    factorial(0) -> 1;
    factorial(N) -> N * factorial(N-1).

At first I was suspicious of function head clauses but have really come to like them. They make the code much more readable and easier to maintain. You can add another clause and keep your change diff small. It could be a general catch-all clause at the end, or a more specific, restricted case at the front and so on.

Tracing is also much nicer. Fire up dbg or recon and it's easy to pick off a particular clause without much effort.

Erlang adopted function pattern matching https://uniwebsidad.com/libros/concurrent-erlang/chapter-1/p...

Out of curiosity: What did f 0 0 give for f _ 0 = 1; f 0 _ = 2; ?

Reply on news.ycombinator.com