Re: Recursive Unions

[Ori Bernstein <ori@xxxxxxxxxxxxxx>]

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>