Re: emulate "sum type" pattern matching?

[Chris Vine]

On Thu, 12 Mar 2020 15:56:47 +0100
Ricardo Wurmus <address@hidden> wrote:
> Chris Vine <address@hidden> writes:
> > On Wed, 11 Mar 2020 19:58:04 +0000
> > Sam Halliday <address@hidden> wrote:
> >> Hi all,
> >> 
> >> I have read the Guile manual as my introduction to Guile. I am very
> >> impressed at how mature this project is and was overwhelmed by the
> >> feature set, which seems to be on-par with heavily invested technologies
> >> like Java and the JVM.
> >> 
> >> I am considering using Guile for a project because I love Emacs lisp and
> >> know it very well. Emacs lisp has some limitations that I feel Guile
> >> overcomes, e.g. multithreading, a superior regexp engine, a module
> >> system, and parsers.
> >> 
> >> However, there is one feature that is critical to the development of the
> >> project and I was hoping to be able to implement it through a macro: sum
> >> type pattern matching.
> >> 
> >> By that, I mean in the sense of Haskell sum types, which I understand
> >> are similar to C++ union types. Roughly translated into GOOP, and using
> >> Scala's encoding of sum types, this would look like record types that
> >> are all children of a superclass. I noticed that Guile has support for
> >> discovering all direct subclasses at runtime, but is this facility
> >> available at compiletime?
> >> 
> >> An example of how I would want to use this feature can be described in
> >> terms of the XML calculator in the Guile Manual.
> >> https://www.gnu.org/software/guile/manual/html_node/sxml_002dmatch.html#Catamorphisms
> >> which looks like
> >> 
> >> (define simple-eval
> >>   (lambda (x)
> >>     (sxml-match x
> >>       [,i (guard (integer? i)) i]
> >>       [(plus ,x ,y) (+ (simple-eval x) (simple-eval y))]
> >>       [(times ,x ,y) (* (simple-eval x) (simple-eval y))]
> >>       [(minus ,x ,y) (- (simple-eval x) (simple-eval y))]
> >>       [(div ,x ,y) (/ (simple-eval x) (simple-eval y))]
> >>       [,otherwise (error "simple-eval: invalid expression" x)])))
> >> 
> >> If the sxml-match was aware that it was matching over a superclass of
> >> plus, minus, times, div then the "otherwise" line would be redundant and
> >> (most importantly) if I were to forget to match over one of the
> >> subclasses I would get a compiler error.
> >> 
> >> And that's basically my usecase in a nutshell: exhaustive pattern
> >> matching over a tree-like structure (an AST, in fact). But I'll have
> >> lots of different trees so I don't want to have to manually write a
> >> pattern match macro every time I define a "sum type"... although that
> >> said I do have some ideas on how to abstract that. But I don't really
> >> want to go down a lisp macro rabbit hole at the very beginning...
> >
> > guile's built-in pattern matcher (ice-9 match) enables you to match on
> > symbols, literals, pairs, lists, vectors and records, but I don't think
> > it enables you to match on GOOPS objects - someone may contradict me on
> > that, but at least I have never tried doing so (I don't like GOOPS nad
> > I rarely use it).
> 
> You can match on anything as long as there is a predicate for it.  For a
> GOOPS object that has a procedure “thing?” that returns #t when the
> argument is of the expected type you can match with
> 
>     (? thing? thing)
> 
> You cannot, as far as I know, use match to know at compile time that the
> clauses are exhaustive.

Ah OK.  But if that is the use issue in hand, then you might as well
use 'cond' (or 'if') rather than 'match'.

Traditional pattern matching is mainly structural, because in a
statically typed language the argument given to the matcher must
normally be of the correct type to begin with.  You can still do
structural matching with the guile matcher.  For example you can peel
off a list with:

  (match lst
    (() ... )
    ((head . tail) ...))

and extract values from a record or vector in a similar way.

But scheme doesn't have variants (sum types) in the ordinary sense so
you cannot extract values by matching on the case/constructor of a
variant in the same way as with statically typed languages.  As you
say, you would have to use a predicate for something equivalent.