CODEWITHSUNDEEP
rascal
redjamjar
redjamjar

Reputation: 771

Inheritance for Algebraic Data Types in Rascal?

Right, I have this data type in Rascal:

data Type = Any() | Void() | Int() | Not(Type l) | And(set[Type] es) | Or(set[Type] es);

What I want to do is define another type like this:

data Primitive = Any() | Void() | Int();

And then be able to do things like this:

Primitive p = Any();
Type d = p;

Or, for example, match against Primitive when simplifying Type. Something like this:

public Type reduce(Not(Primitive p)) = p;

Currently, the only solution I can see is to expand the above rule for each case like so:

public Type reduce(Not(Any)) = Any();
public Type reduce(Not(Void)) = Void();
public Type reduce(Not(Int)) = Int();

I'm guessing there is a way to do this, but I didn't figure it out yet ... thoughts?

Upvotes: 1

Views: 158

Answers (2)

Paul Klint
Paul Klint

Reputation: 1406

The short answer: although Abstract Data Types can be extended (i.e., their definition can be extended across modules) there is no direct inheritance.

Work arounds:

Solution A

data Type = Any() | Void() | Int() | Not(Type l) | And(set[Type] es) | Or(set[Type] es);

bool isPrim(Any()) = true;
bool isPrim(Void()) = true;
bool isPrim(Int()) = true;
default bool isPrim(Type t) = false;

Type reduce(Not(Type t)) = t when isPrim(t);
default Type reduce(Type t ) = t;

Here all constructors for Type are in a single ADT and the predicate isPrim selects the primitives. For example, reduce(Not(Void())) will reduce to Void().

Solution B

data Primitive = Any() | Void() | Int();

data Type = prim(Primitive p) | Not(Type l) | And(set[Type] es) | Or(set[Type] es);

Type reduce(Not(prim(Primitive p))) = prim(p);
default Type reduce(Type t ) = t;

Here the primitives are collected in a separate ADT Primitive and they are included in Type via the constructor prim. Now reduce(Not(prim(Void()))) will reduce to prim(Void()).

Final Notes

  • We would also prefer to have inheritance (without the extra constructor prim as in Solution B) but for various technical reasons we did not include it. Although desirable, I am not sure that we will ever do.
  • Note the functions preceded by default, they are the catch all case when the other declarations of a function do not match.
  • All functions are public, unless preceded by the key word private.

Upvotes: 1

Jurgen Vinju
Jurgen Vinju

Reputation: 6696

Nice question. Rascal does not feature user-defined sub-typing and typing for data types is nominal. That answers your question in theory, so how does that work in practise?

  • The answer for data types is slightly different for syntax types, so here follows both stories;
  • There many are different idioms to model a hierarchy of data-structures, we'll show only three here for the sake of simplicity;

Here's a way to extend a data-type with new features which does not involve adding new types, this produces an over-approximate model of what you intended:

// first the primitive types are defined (I've added Not here to make a point later):
data Type = Any() | Void() | Int() | Not(Type l); 

// then the extension is added (perhaps in a different module)
data Type = And(set[Type] es) | Or(set[Type] es);

// the second definition adds its alternatives also to the child of `Not`.

The second way is more close to an actual extension, because the original Type is not extended, and no "junk" is added accidentally:

// we give the original type a unique name:
data Primitive = Any() | Void() | Int();

// For the extension the Primitive type is not polluted with the new constructors, but
// it was wrapped inside a singleton constructor `prim`
data Type = prim(Primitive super) | And(set[Type] es) | Or(set[Type] es);

Of course, this second solution will make you add prim constructors in possible pattern matches you might do, but the / deep match operator will allow you to ignore it where possible. For example:

bool evalt(prim(p)) = evalp(p);
bool evalp(Any()) = true;
bool evalp(Not(p)) = !evalp(p);

bool containsVoid(Type t) = /Void() := t;

Now for syntax types the story is similar but since chain rules in syntax types are invisible, it gives some additional flavor:

syntax Primitive = "any" | "void" | "int";

// notice the first chain rule or "injection" of Primitive into Type:
syntax Type = Primitive | left Type "∧" Type > left Type "∨" Type;

bool evalt((Type) `any`) = true; // the chain rule is parsed but invisible

People have been discussing to add implicit chaining to the abstract data-types as well, for its attractive to simulate sub-typing like so. I guess that would be like Scala's implicits. The jury is still out on that one.

Upvotes: 1

Related Questions