Re: Recursive Unions

[Yves Cloutier <yves.cloutier@xxxxxxxxx>]

Well Ori, that certainly did the job!

I'm following examples from the book "Programming Language Concepts" by
Peter Sestoft.

The book uses F# for the implementation of the examples. I thought I would
try to follow along using Myrrdin.

As a followup question, the F# version of Prim is:

Prim (string, Expression Expression)

I used byte[:] here after looking at some examples. looking at the string
package and seeing byte[:] I just assumed is was similar to a C char* or
char[].

Is this correct? there is no "string" type?



On Thu, Aug 16, 2018 at 6:33 PM Ori Bernstein <ori@xxxxxxxxxxxxxx> wrote:

> On Thu, 16 Aug 2018 17:17:38 -0400
> Yves Cloutier <yves.cloutier@xxxxxxxxx> wrote:
>
> > Is it possible to have recursive "ADT" a-la-ML using unions?
>
> Yes, with one caveat: It can't contain itself
> directly, or it would be an infinitely sized
> type.
>
> > I'm leaning towards no, as I get the following error:
> >
> > syntax error, unexpected Ttick
> >
> > making reference to
> >
> > `Prim (byte[:], `Expression, `Expression)
> >
> > from the code below:
> >
> > use std
> >
> > type Expression = union
> >     `Int int
> >     `Prim (byte[:], `Expression, `Expression)
> > ;;
>
> Here, there are two issues:
> 1. `Expression is a tag; the type name is just
>     Expression.
>
> 2. A type can't contain itself directly, so you
>    would need to store it as a pointer.
>
> With those two fixed:
>
>         type expression = union
>                 `Int int
>                 `Prim (byte[:], expression#, expression#)
>         ;;
>
> > const eval = { e
> >     match e
> >     | `Int x: -> x
> >     | `Prim ("+", x, y): -> eval(x) + eval(y)
> >     | `Prim ("-", x, y): -> eval(x) - eval(y)
> >     | `Prim ("*", x, y): -> eval(x) * eval(y)
> >     ;;
> > }
>
> Here, you'd need to use a pointer-chasing match:
>
>     const eval = { e
>         match e
>         | `Int x: -> x
>         | `Prim ("+", &x, &y): -> eval(x) + eval(y)
>         | `Prim ("-", &x, &y): -> eval(x) - eval(y)
>         | `Prim ("*", &x, &y): -> eval(x) * eval(y)
>         ;;
>     }
>
> And since inexhaustive matches are errors, you'll need
> to add a catch-all clause;
>
>         | `Prim (wut, _, _):    std.fatal("wut: {}\n", wut)
>
> > const main = {
> >   var x = eval(`Int 2)
> >   std.put("2 = {}", x)
> >   var y = eval(`Prim("+", `Int 2, `Int 5))
> >   std.put("2 + 5 = {}", y)
> > }
>
> And this code needs to take the address of the
> literals:
>
>
>     var y = eval(`Prim("+", &`Int 2, &`Int 5))
>
>
> Currently at work, so I haven't had a chance to test
> this -- I may have screwed things up horribly.
>
> --
> Ori Bernstein <ori@xxxxxxxxxxxxxx>
>
>