emulate "sum type" pattern matching?

emulate "sum type" pattern matching?

[Sam Halliday]

[-- Attachment #1: Type: text/plain, Size: 2306 bytes --]

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

-- 
Best regards,
Sam

[-- Attachment #2.1: Type: text/plain, Size: 0 bytes --]



[-- Attachment #2.2: signature.asc --]
[-- Type: application/pgp-signature, Size: 194 bytes --]

Re: emulate "sum type" pattern matching?

[Chris Vine]

On Wed, 11 Mar 2020 19:58:04 +0000
Sam Halliday <sam.halliday@gmail.com> 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).  The other problem is that discriminated unions are a
better fit with statically typed languages such as Haskell and the MLs;
in dynamically typed languages there is a sense in which every variable
name represents a union of unlimited extent but which enables its
current type to be interrogated.

Re: emulate "sum type" pattern matching?

[Ricardo Wurmus]

Chris Vine <vine35792468@gmail.com> writes:

> On Wed, 11 Mar 2020 19:58:04 +0000
> Sam Halliday <sam.halliday@gmail.com> 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.

-- 
Ricardo

Re: emulate "sum type" pattern matching?

[Chris Vine]

On Thu, 12 Mar 2020 15:56:47 +0100
Ricardo Wurmus <rekado@elephly.net> wrote:
> Chris Vine <vine35792468@gmail.com> writes:
> > On Wed, 11 Mar 2020 19:58:04 +0000
> > Sam Halliday <sam.halliday@gmail.com> 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.