Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Does Perl6 support dependent types?

I was recently looking at the wikipedia page for dependent types, and I was wondering; does Perl 6 actually introduce dependent types? I can't seem to find a reliable source claiming that.

It might be obvious to some, but it sure as heck ain't obvious to me.

like image 522
hao ramirez Avatar asked Aug 14 '16 23:08

hao ramirez


2 Answers

Against Ven, in the comments following the Perl 6 answer to the SO question "Is there a language with constrainable types?", wrote "perl6 doesn't have dependant types" and later wrote "dependent type, probably not, ... well, if we get decidable wheres..." in an exchange on #perl6. (Larry Wall's response was "what's a few halting problems among friends". Btw, by far the best way to get an authoritative answer on all things Perl 6 is to ask TimToady via #perl6.)

For The summary for the 'dependent-type' SO tag is "Dependent types are types that depend on values." Perl 6 supports types that depend on values, so there's that.

For The edit summary for the change by Awwaiid that added Perl 6 to Wikipedia's page on Dependent Types says "Perl 6 ... has undecidable dependent types".

The Wikipedia page starts with:

a dependent type is a type whose definition depends on a value. A "pair of integers" is a type. A "pair of integers where the second is greater than the first" is a dependent type because of the dependence on the value.

Here's one way to create a type along those lines in Perl 6:

subset LessMorePair of Pair where { $_.key < $_.value }
subset MoreLessPair of Pair where { $_.key > $_.value }

multi sub foo (        Pair) { "  P" }
multi sub foo (LessMorePair) { "LMP" }
multi sub foo (MoreLessPair) { "MLP" }

for 1 => 1, 1 => 2, 2 => 1 { say foo $_ }

#   P
# LMP
# MLP

Does this mean the Perl 6 subset feature generates dependent types? Perhaps this is what Awwaiid is thinking of.

like image 158
raiph Avatar answered Oct 05 '22 10:10

raiph


Arguably yes as subsets are types that may depend on arbitrary conditions. However, the type system would be classified as unsound as type invariants are not enforced.

In particular, a variable's type constraint is only checked on assignment, so modifications to an object that make it drop from a subset will lead to a variable holding an object it should not be able to, eg

subset OrderedList of List where [<=] @$_;

my OrderedList $list = [1, 2, 3];
$list[0] = 42;
say $list ~~ OrderedList;

You can use some meta-object wizardry to make the object system automatically check the type after any method call by boxing objects in transparent guard objects.

A naive implementation could look like this:

class GuardHOW {
    has $.obj;
    has $.guard;
    has %!cache =
        gist => sub (Mu \this) {
            this.DEFINITE
                ?? $!obj.gist
                !! "({ self.name(this) })";
        },
        UNBOX => sub (Mu $) { $!obj };

    method find_method(Mu $, $name) {
        %!cache{$name} //= sub (Mu $, |args) {
            POST $!obj ~~ $!guard;
            $!obj."$name"(|args);
        }
    }

    method name(Mu $) { "Guard[{ $!obj.^name }]" }
    method type_check(Mu $, $type) { $!obj ~~ $type }
}

sub guard($obj, $guard) {
    use nqp;
    PRE $obj ~~ $guard;
    nqp::create(nqp::newtype(GuardHOW.new(:$obj, :$guard), 'P6int'));
}

This will make the following fail:

my $guarded-list = guard([1, 2, 3], OrderedList);
$guarded-list[0] = 42;
like image 29
Christoph Avatar answered Oct 05 '22 10:10

Christoph