Re: ADT and GADT (a partial implementation)

[Timo Paulssen]

On 21.03.2013 17:45, Carl Mäsak wrote:
> [...]
> 
> Using hashes and subclasses:  Using
> classes and subclasses: 
> 
> [...]

I came up with a prototype to create those classes like in the second gist
automatically by supplying a haskell-like declaration of the data type.

(skip to the end of the mail for the code)

Here's what it can do:

my %res = create_adt("Tree = Branch Tree left, Tree right | Leaf Str 
storage");
my \Tree = %res;

# create the tree with named parameters
my $t =
Tree.new-branch(
:left(Tree.new-branch(
:left(Tree.new-leaf(:storage(1))),
:right(Tree.new-leaf(:storage(2),
:right(Tree.new-leaf(:storage(3;

# create the tree with positional arguments
my $t2 =
Tree.new-branch(
Tree.new-branch(
Tree.new-leaf(1),
Tree.new-leaf(2)),
Tree.new-leaf(3));
say $t2.gist;
# outputs:  (reformatted for email)
# Tree.new-branch(
#left => Tree.new-branch(
# left => Tree.new-leaf(storage => 1),
# right => Tree.new-leaf(storage => 2)),
#right => Tree.new-leaf(storage => 3))

my \Branch = %res;
my \Leaf = %res;

# haskell-style map for the tree
sub treemap($t, *&code) {
given $t {
when Branch {
return Tree.new-branch(
treemap($t.left, &code),
treemap($t.right, &code))
}
when Leaf {
return Tree.new-leaf(code($t.storage))
}
}
}

say treemap($t2, * * 10).gist;
# outputs:
# Tree.new-branch(
#left => Tree.new-branch(
# left => Tree.new-leaf(storage => 10),
# right => Tree.new-leaf(storage => 20)),
#right => Tree.new-leaf(storage => 30))


There are currently some limitations:

1) there is no compiler support for checking that all cases have been covered,
   but as masak mentioned, I'm confident this can be done with a macro, because
   those run at compile-time basically.
2) you cannot yet use Leaf and Branch for declaring multi subs, because the
   symbols are not there at compile-time, but see below.
3) I have not yet figured out how to properly do pattern matching/decomposing,
   so the names "left", "right" and "storage" need to be supplied in the
   definition unlike in haskell.
4) I'm not sure how to do type parameters (think data Tree A = ...), because
   perl6 has only parametric roles, not parametric classes.

One thing rakudo needs to get for this to be much smoother is support for the
sub EXPORT to return a hash-like of symbols that will be installed in the
caller's package. This would make Tree, Branch and Leaf available as
compile-time symbols, so that multi methods/subs can use them for dispatch.

I mean to turn this into a module for the perl6 modules list some time in the
Future.

Finally, here's the runnable code. Feel free to play around with it and tell me
on this mailing list or the IRC channel what further problems (or even
solutions!) you find.

https://gist.github.com/timo/5226114

Have Fun!
  - Timo

Re: ADT and GADT

[Carl Mäsak]

Philippe (>):
> I like solution 2, but am going to have to delve into the Perl 6 
> Documentation to
> understand its esoteric syntax:

S12 will be a big help here. You may have found it already.

 

I include a few quick pointers below, which also may help.

> - class Tree { ... }

Perl 6 doesn't like types it hasn't seen yet. Because Tree::Branch
uses Tree, I need to declare Tree before I define it. The dots '...'
say "implementation forthcoming, but there's a type called 'Tree'".

> - handles ;,

It's delegation. Instead of writing 'method left { $.branch.left }' in
that class, I just say that $.branch handles calls to 'left'.

> - self.bless(*,, etc.)

Any 'self.bless' you see means "create a new instance of this class,
with these attributes set".

// Carl

Re: ADT and GADT

[phiroc]

Hi Carl,

thanks for your reply.

I like solution 2, but am going to have to delve into the Perl 6 Documentation 
to understand its esoteric syntax: 

- class Tree { ... }
- handles ;,
- self.bless(*,, etc.)

Philippe




- Mail original -
De: "Carl Mäsak" 
À: "Perl6" 
Envoyé: Jeudi 21 Mars 2013 17:45:45
Objet: Re: ADT and GADT

Hi Philippe,

Philippe (>):
> will Abstract Data Types and Generalized Abstract Data Types be available in 
> Perl6 anytime soon?

Algebraic Data Types -- this is a topic that has come up before on
#perl6 on IRC. Often enough I've been the one mentioning it. Let's
just stop briefly to define a few things that we may associate with
ADTs.

As an example, I'll throw up this classic ADT from Haskell:

  data Tree a = Branch (Tree a) (Tree a) | Leaf a

Now, let's list what this gives us:

(a) Nice syntax for (recursively) specifying the type.
(b) Nice syntax for constructing values of the type.

Not shown above, but equally important in my view, are the consumption
end of ADTs:

(c) Nice destructuring syntax when matching against a value.
(d) Ease of binding the matched bits to variables and using those.

Just for fun, I put together two ways to emulate ADTs in Perl 6. These
two gists both run in Rakudo today.

Using hashes and subclasses: <https://gist.github.com/masak/5213423>
Using classes and subclasses: <https://gist.github.com/masak/5213563>

I'd say the first solution does OK at (a), but it's not excellent and
definitely contains boilerplate, especially in those subs. It does (b)
OK, but only because things are very lax. It only begins to do (c) --
it doesn't look into the values -- and it doesn't really do (d) at
all.

In comparison, the second solution is a bit stricter with (b), in
exchange for having a bit more boilerplate in (a). (c) and (d) are
equally bad as in the first solution.

Furthermore, what I'd really like to see is compiler support for all
those four things -- basically type checking on ADTs at compile-time.
People on #perl6 started talking about macros and how they would help
here. I think that's a viable approach, but just how far it gets us
remains to be seen.

As to GADTs, I fear I don't understand them well enough to give a good
answer there. But generally, Perl 6 doesn't do as much typechecking at
compile time as would a strict language, so they may or may not be as
feasible, or even as necessary. People who grok type theory better may
be able to tell you more there, though.

// Carl

Re: ADT and GADT

[Carl Mäsak]

Hi Philippe,

Philippe (>):
> will Abstract Data Types and Generalized Abstract Data Types be available in 
> Perl6 anytime soon?

Algebraic Data Types -- this is a topic that has come up before on
#perl6 on IRC. Often enough I've been the one mentioning it. Let's
just stop briefly to define a few things that we may associate with
ADTs.

As an example, I'll throw up this classic ADT from Haskell:

  data Tree a = Branch (Tree a) (Tree a) | Leaf a

Now, let's list what this gives us:

(a) Nice syntax for (recursively) specifying the type.
(b) Nice syntax for constructing values of the type.

Not shown above, but equally important in my view, are the consumption
end of ADTs:

(c) Nice destructuring syntax when matching against a value.
(d) Ease of binding the matched bits to variables and using those.

Just for fun, I put together two ways to emulate ADTs in Perl 6. These
two gists both run in Rakudo today.

Using hashes and subclasses: 
Using classes and subclasses: 

I'd say the first solution does OK at (a), but it's not excellent and
definitely contains boilerplate, especially in those subs. It does (b)
OK, but only because things are very lax. It only begins to do (c) --
it doesn't look into the values -- and it doesn't really do (d) at
all.

In comparison, the second solution is a bit stricter with (b), in
exchange for having a bit more boilerplate in (a). (c) and (d) are
equally bad as in the first solution.

Furthermore, what I'd really like to see is compiler support for all
those four things -- basically type checking on ADTs at compile-time.
People on #perl6 started talking about macros and how they would help
here. I think that's a viable approach, but just how far it gets us
remains to be seen.

As to GADTs, I fear I don't understand them well enough to give a good
answer there. But generally, Perl 6 doesn't do as much typechecking at
compile time as would a strict language, so they may or may not be as
feasible, or even as necessary. People who grok type theory better may
be able to tell you more there, though.

// Carl