Language Reference/Bounded polymorphism

From wiki.visual-prolog.com

< Language Reference

Revision as of 17:33, 25 February 2019 by Thomas Linder Puls (talk | contribs) (Not released)

Language Reference

The following example can be used as a motivation for bounded polymorphism.

Example Assume that we have a program with two kinds of persons clients and users, and that we have ordered them in a hierarchy like this:
interface person
properties
    name : string.
    ...
end interface person
 
interface client supports person
properties
    clientId : unsigned.
    ...
end interface client
 
interface user supports person
properties
    isAdministrator : boolean.
    ...
end interface user

Using list::sortBy we can create predicate that sorts a list of persons by name like this:

predicates
    sortByName : (person* PersonList) -> person* SortedList.
clauses
    sortByName(List) :- list::sortBy({ (L, R) = compare(L:name, R:name) }, List).

Due to the (structural subtyping) type rules of Visual Prolog we use this predicate to sort a list of users:

SortedList = sortByName(UserList)

However, SortedList is a list of persons rather than a list of users.

So the elements in SortedList does not have the isAdministrator property.

In this example the elements in the SortedList has been "downgraded" from user to person. But if they are users before we sort them then they are also users after they have been sorted. So we would like to create a sortByName predicate that does not perform such an element downgrade.

So we want to create a predicate that returns the same kind of elements that it receives as input. A polymorphic declaration like this:

predicates
    sortByName : (Elem* PersonList) -> Elem* SortedList.

has the desired property. But it will not work, because this predicate can receive any kind of list as input and you cannot get a name from everything.

This is where bounded polymorphism can help. With bounded polymorphism you can state that a a type parameter cannot be anything it has to fulfill some bound.

Bounds have the form where X supports Y.

Example In our example we can use bounded polymorphism like this:
predicates
    sortByName : (Person* PersonList) -> Person* SortedList
        where Person supports person.

Now the type parameter (i.e. Person) can only be a type that supports person.

If we call the predicate with a user list (user*) then the type variable Person will be user in the declaration, corresponding to this declaration:

predicates
    sortByName : (user* PersonList) -> user* SortedList
        where user supports person.

We can see that:

  • The returned list is a user*
  • The bound is fulfilled because user does support person.

On the other hand, if we (attempt to) call the predicate with an integer list (integer*) the type variable Person must have the value integer, corresponding to this declaration:

predicates
    sortByName : (integer* PersonList) -> integer* SortedList
        where integer supports person.

Then the bound is not fulfilled because integer does not support person.

Bounds can be put on polymorphic predicates like above, if you need more than one bound you must write like this:

predicates
    pred : (<type1> P1, <type2> P2, ...) -> <return>.
        where <Sub1> supports <Super1>
        where <Sub2> supports <Super2>
        ....
        where <SubJ> supports <SuperJ>.

When we have put bounds on the parameters we can exploit them in the clauses.

Example L and R has types that supports person, so we can obtain the name property from these variables:
predicates
    sortByName : (Person* PersonList) -> Person* SortedList
        where Person supports person.
clauses
    sortByName(List) :- list::sortBy({ (L, R) = compare(L:name, R:name) }, List).

Bounds can also be put on classes.

Example Given persons from above, we want to create name maps. I.e. we want to map from name to person, but also here we want to be able to use this map for users and customers.

The interface does not reflect that we have persons in mind (we could also implement this interface for other things than persons):

interface nameMap{@Type}
predicates 
   insert : (@Type Element).
   tryGet : (string Name) -> @Type.
interface nameMap

But the personNameMap class will only work persons

class personNameMap{@Person} : nameMap{@Person}
    where @Person supports person
end class personNameMap

Due to the bound we can use the name property in the implementation of the class:

implement personNameMap{@Person}
 
facts
    theMap : mapM{string Name, @Person} := mapM_redBlack::new().
 
clauses
    insert(P) :-
        theMap:set(P:name, P).  % P has a type that supports person, so we can use the name property
 
clauses
    tryGet(Name) = theMap:tryGet(Name).
 
end implement personNameMap

This class can be used to create a user map:

facts
    userMap : nameMap{user} := personNameMap::new().

And in that map we can insert user and we can lookup users (i.e. rather than persons) by name.

In bounds the notion of supports is extended to cover non-object types, in the sense that Sub supports Super if Sub is a subtype of Super. As example integer is a subtype of real.