Language Reference/Objects and Polymorphism

The programming language Visual Prolog has gone through a huge development in the latest years, and this will also continue in future. Most noticeable is the shift to object-orientation, and the introduction of parametric polymorphism. In this paper we will explain the reason for introducing these features. Examples will be used to illustrate how these facilities can help to tackle the increasing complexity and size of software.

Motivation

While Prolog has many great virtues, one must remember that it is from the IT-bronze-age, and it would be silly to think that it would stay contemporary after three decades or more, especially considering the speed with, which the IT-world has evolved since then. Back then you could write an amazing Prolog program that described how to get a cabbage, a goat, a wolf and a farmer across a river in a little boat without anybody eating anybody. You can still write such programs just as easily (see Farmer, Wolf, Goat and Cabbage), but they are just not that amazing anymore. Show it to your children and they will immediately ask why the solution is not an animation, and explain that there are millions of much more advanced programs one click away on the Internet already.

Programs today must be more advanced than yesterday. They also have to live and interact with a much larger world than yesterday. And this is an ongoing story.

Many attempts has been made to help tackle these challenges; we have chosen to add the elements that we believe are the winners to Visual Prolog. These are especially object-orientation and parametric polymorphism, but there are also other new elements especially taken from the functional programming world.

Goals and Means

The goals of the language update is to provide better means for creating and maintaining more complex programs for more complex surroundings.

Simplicity

Humans are better to dealing with simple things than complex things, so one important way to deal with complexity is to reduce it to something simpler, especially by using "structure" to organize the complexity.

The main "trick" is the divide and conquer principle: Divide the original problem into separate sub-problems that can be solved individually. I.e., the solution to the overall problem consists of a number of sub-solutions and something that combines these into the overall solution.

Maintainability

For software it is often not enough to solve a problem, we must also be able to maintain and extend the solution in an evolving world. So it is important that the used methods not only solve the problem, but also result in a program that can be maintained. Here it is important that the program is understandable and especially that the divides are visible and clear in the program.

Reuse and sharing

When you divide problems into sub-problems, perhaps repeatedly, you will sometimes see similar sub-problems. Then it would of course be nice to short cut by reusing a similar solution. Such a solution can be adopted into the new context, but there are two ways this can happen. We can make a copy and update it to its new purpose, or we can try to share the code between the two problems.

The latter is clearly the hardest and only makes sense if both pieces of software are still maintained. But in that case you will have the advantage that maintenance made in one context is also shared with the other context.

Flexibility

It is also desirable that your software is flexible. You may for example need to deliver several variants of your software to different customers. Or you may need to reconfigure the software to a changed context. Also some of your shared sub-solutions may need to go into contexts that are not completely the same.

Power

Finally, it is of course desirable if language extensions add additional programming power. For example, by simplifying the code necessary to tackle certain standard "issues".

Polymorphism

Visual Prolog has been extended with many language features that support the goals above, but it is still up to the programmer to apply these features such that the goals are achieved. Here we will focus on understanding and using polymorphism.

The object-system in Visual Prolog gives so called subsumption polymorphism and also have parametric polymorphism. Polymorphism is especially well-suited for divide and conquer that supports sharing of code.

Subsumption polymorphism

An object is a closed entity that carries state and code. The object provides an interface through which the surroundings can interact with the object. The object can also interact with other objects through their interfaces.

Each interface has an explicit definition in the source code. The definition effectively consists of a name and a number of predicate declarations.

Let us assume that we want an object through which some administrative system can report salary. In an oversimplified world, such an object might have this interface:

interface salarySystem
predicates
    salary : (string Name,  real Amount).
end interface salarySystem

An object with this interface will allow you to report an Amount for a person (identified by Name).

The salarySystem interface defines a data type that can be used in the program. The main salary reporting predicate in the application might be declared like this:

class predicates
    reportSalary : (salarySystem SalarySystem).

For the sake of the example, we simply hard code a little salary reporting like this:

clauses
    reportSalary(SalarySystem) :-
        SalarySystem:salary("John D", 135.12),
        SalarySystem:salary("Elvis P", 117.00).

We will of course also need to implement our salary system objects, and that is where the subsumption polymorphism comes in play. The thing is that our customers of course use a lot of different salary systems, which must receive input in many different formats and using many different media. Objects are implemented by classes, and the fortunate thing is that many different classes can implement the same interface. Objects produced by any such class can be used by the reportSalary predicate. Thus, the reportSalary predicate is polymorphic because the salarySystem type subsumes all the different implementations of the interface. To deal with the ACME salary system we declare this class:

class acme : salarySystem
end class acme

The declaration simply says that acme is a class that produces objects of type salarySystem. The class also needs an implementation:

implement acme
constants
    fmt = "SAL:%>>>%\n".
clauses
    salary(Name, Amount) :-
        stdio::writef(fmt, Name, Amount).
end implement  acme

To illustrate the polymorphism, we will also implement the integration to the O'Salery system. Again we declare and implement a class:

class oSalary : salarySystem
end class oSalary
 
implement oSalary
constants
    fmt = "<salary name=\"%\" wage=\"%\" />\n".
clauses
    salary(Name, Amount) :-
        stdio::writef(fmt, Name, Amount).
end implement oSalary

Now let us try our two salary system integrations:

clauses
    test():-
        ACME = acme::new(),
        reportSalary(ACME),
        Osalery = oSalary::new(),
        reportSalary(Osalery).

In the test predicate above, we create one of each salary systems and report salary to them. The result looks like this:

SAL:John D>>>135.12
SAL:Elvis P>>>117
<salary name="John D" wage="135.12" />
<salary name="Elvis P" wage="117" />

In this example, the difference was not that big, but we might also have placed the result in a database, used a foreign API, called a WEB service or whatever.

The solution above uses the divide and conquer principle to separate the reporting in a vendor independent part and a vendor specific part. In this case the vendor independent part also deals with the company level in the reporting, were as the vendor dependent part only deals with the person level.

We have used subsumption polymorphism to provide the flexibility to deal with many different salary systems in a seamless way. In real world, this may not be as simple as here though. The key to success is that the salarySystem interface is a sufficiently powerful abstraction/generalization of all the relevant salary systems. It may for example be necessary to provide several different ways to identify persons in the salary predicate. Different salary systems can then use the identification method, which is appropriate for them and ignore the rest.

The reportSalary predicate is shared across different salary systems. The sharing is a high-level domain specific sharing, within the same application or variants of it.

Visual Prolog also has another kind of subsumption polymorphism: Predicate values. A predicate value is a predicate that is bound to variables, transferred as parameter and/or stored in facts. Again, the polymorphism comes from a type that subsumes many different implementations.

As an example, PFC uses predicate values in its heavily used event notification scheme. A scheme that can of course also be used outside PFC.

The event notification scheme has two kinds of actors: the event source and the event listener. There is one event source, but there can be any number of listeners. The event source offers predicates for registering and deregistering event listeners. When the event occurs all registered listeners are notified.

The interesting thing is that the event listener is a predicate, meaning that the notification will immediately execute code. In addition, due to the subsumption polymorphism each listener can have its own implementation and thus perform quite different actions.

A very important property of predicate values is that they can be object predicates, and that these have access to the object state to which they belong.

We shall not describe the event notification scheme in details here, though it is good to understand. The reader is encouraged to study the concept in PFC (look for addXxxxListener). However, the use of predicate values will be exercised in the job-scheduling example in the end of this paper.

Parametric Polymorphism

Like for subsumption polymorphism the purpose of parametric polymorphism is to use the same code for many things. However, where subsumption polymorphism is mainly about supplying different implementations to the same context, parametric polymorphism is mainly about using the same implementation in different contexts.

Let us start with a very simple example, to introduce the concepts. We will implement a function, which takes the list as argument and returns the elements one by one (non-deterministically).

In Visual Prolog the list domain is a polymorphic domain: If Elem is a type/domain then Elem* the list domain of Elem. The new thing is that parameters like Elem and type expressions like Elem* can be used in declarations, and that the resulting declaration will cover any instantiation of such parameters.

Therefore we can declare our getMember_nd function like this:

predicates
    getMember_nd : (Elem* List) -> Elem Value
        nondeterm.

This declaration says that getMember_nd is a function, which takes a list of Elem argument and returns an Elem, where Elem is any domain/type.

The implementation is straightforward:

clauses
    getMember_nd([V|_L]) = V.
    getMember_nd([_V|L]) = getMember_nd(L).

Without further notice getMember_nd can be used on any list kind:

clauses
    run():-
        console::init(),
        L = [[1,2,3], [7,-7], [9,4,5]],
        foreach X = list::getMember_nd(L) do
            stdio::writef("X = %\n", X)
        end foreach.

Here Elem is integer* (i.e. list of integers). The output looks like this:

X = [1,2,3]
X = [7,-7]
X = [9,4,5]

The list domain is a predefined polymorphic domain. But you can also define polymorphic domains yourself. As an example we can create a priority queue; sometimes called a heap. Let me warn you, the implementation I will use here is not particularly efficient; it is just simple.

The idea of the priority queue is that we can insert some data with a priority, later we can then retrieve the data with lowest priority. It sounds a bit strange, that it is the one with the lowest Priority that is retrieved; but that is how it normally works. I assume that it comes from the idea of first priority, second priority, etc. where smaller number means higher priority.

Anyway, in this case we want to implement the queue as a list of tuple's, each tuple has two elements the first is the priority and the second is the Data. Furthermore, we will keep the list sorted after priority (i.e. an invariant), such that the smallest element is always first in the list.

tuple is already defined in Visual Prolog its definition looks like this:

domains
    tuple{T1, T2} = tuple(T1, T2).

There are also tuple's with other arities, but we only need the pair. This is an example of a programmer defined polymorphic domain. What the definition says is that tuple is a domain with two type parameters T1 and T2. You may think of it as an infinite family of domains corresponding to all instantiations of the type parameters, e.g.:

domains
    tuple_char_char = tuple(char, char).
    tuple_char_integer = tuple(char, integer).
    tuple_char_string = tuple(char, string).
    ...

The single domain definition above corresponds to all these domains, but actually the domain names/expressions look like this:

    tuple{char, char}
    tuple{char, integer}
    tuple{char, string}
    ...

The values looks as expected; let us take a relatively complex one right away:

    X = tuple(tuple('a',"a"), [1.2])

T2 is a tuple, its first element is itself a tuple (containing a char and a string), its second element is a list of real's. Subsequently, X has this type:

    tuple{ tuple{char, string}, real* }

As you can see type expressions can become rather complex. You will probably soon get use to this, but below I will show a little scheme that can be used to keep type expressions simpler and more understandable, and which will at the same time make your program more type safe.

We are now ready to define our queue domain:

domains
    queue_rep{Priority, Data} = tuple{Priority, Data}*.

The _rep in the domain name has to do with the scheme mentioned above, right now you can simply ignore it. The domain definition says that queue_rep is a domain with two type parameters Priority and Data furthermore it is a list of tuple's of these types.

You may wonder why Priority is a type parameter, you may think that it should have been a number type like integer. However, in Visual Prolog all data types are ordered, and therefore any data type can be used as a priority. Using a type parameter here makes the resulting queue more flexible. And at least I do not have to choose whether the priority should be integer, unsigned or real.

To know whether you can use a type parameter or have to use a regular type you will have to consider what you need from the type. Like here where we need ordering (comparison). The following is possible on type parameters:

• transferring as parameter
• binding and unifying (with values of same type)
• comparing (with values of same type)
• writing on streams
• reading from streams

The last thing is partially wrong, the compiler allows this, but in practice you cannot read all kind of data, it is for example not possible to read predicate values and objects from streams.

Let us return to our priority queue. Now that we have defined the domain that represents the queues, we will also have to declare and implement the suitable operations.

Let us start with the simple ones. First we need an operation to obtain the least element in the queue (i.e. the one with least priority). This can be declared like this:

predicates
    tryGetLeast_rep : (queue_rep{Priority, Data} Queue) -> tuple{Priority, Data} Least determ.

The predicate is determ because the queue might be empty. The predicate is a function whose argument is a priority queue and which returns a tuple containing both the Priority and the Data. It does not remove the element from the queue, because I want to be able to peek at the element without removing it.

The list is sorted with the least element first, so the implementation is trivial:

clauses
    tryGetLeast_rep([Least|_]) = Least.

Similarly we need a predicate for removing the least element:

predicates
    deleteLeast_rep : (queue_rep{Priority, Data} Queue1) -> queue_rep{Priority, Data} Queue.
clauses
    deleteLeast_rep([]) = [].
    deleteLeast_rep([_Least|Rest]) = Rest.

Finally, we need an insert predicate:

predicates
    insert_rep : (queue_rep{Pri, Data} Q1,  Pri P,  Data D) -> queue_rep{Pri, Data} Q0.
clauses
    insert_rep([], Pri, Data) = [tuple(Pri, Data)].
 
    insert_rep(Q1, Pri, Data) = Q0 :-
        [tuple(P1,D1)|Rest] = Q1,
        if Pri <= P1 then
            Q0 = [tuple(Pri, Data)| Q1]
        else
            Q0 =
                [tuple(P1,D1) | insert_rep(Rest, Pri, Data)]
        end if.

I have chosen shorter variable names to make the code fit the narrow column, but at the same time it gives me the opportunity to explain that type variables like Pri above only have scope in the declaration/definition where they occur. Therefore, there is nothing wrong with using Priority in one declaration and Pri in another. Nevertheless, you should of course choose variable names with care, because good names make the code clearer. The compiler would not mind if you exchange Priority and Data, but I am sure that it could confuse many programmers.

The priority queue above can be used for various purposes, but it has two disadvantages, which both relate to the way we have defined the queue domain itself:

domains
    queue_rep{Priority, Data} = tuple{Priority, Data}*.

A definition like this one is just an abbreviation or synonym, so queue_rep{integer, sting} is exactly the same as tuple{integer, string}*.

1. The debugger will always show the unfolded type (i.e. tuple{integer, string}*) and this can be rather confusing.

1. Any piece of data that have this type can accidentally be given as argument to the priority queue predicates. However, the priority queue operations not only require that the data has this type, it also expect that it is sorted in a specific way (i.e. that the data satisfies the invariant).

The latter problem could just as easy exist without polymorphism. It comes from using a general data structure for something specific. If you do this, you can mix anything that is of the general kind even though it is of different specific kinds.

So instead we just consider the queue_rep domain as being the internal representation of the queues, hence the extension _rep. To the external world we will wrap each queue_rep queue inside a functor.

Therefore, to the real queue domain will look like this:

domains
    queue{Priority, Data} = queue(queue_rep{Priority, Data}).

Such a domain is neither an abbreviation nor a synonym.

The exported/public predicates will of course work on queue 's, so the complete class declaration looks like this:

class priorityQueue
    open core
 
domains
    queue_rep{Priority, Data} = tuple{Priority, Data}*.
 
domains
    queue{Priority, Data} = queue(queue_rep{Priority, Data}).
 
constants
    empty : queue{Priority, Data} = queue([]).
 
predicates
    insert : (queue{Pri, Data} Q1, Pri Pri, Data Data) -> queue{Pri, Data} Q0.
 
predicates
    tryGetLeast : (queue{Priority, Data} Queue) -> tuple{Priority, Data} Least determ.
 
predicates
    deleteLeast : (queue{Priority, Data} Queue1) -> queue{Priority, Data} Queue.
end class priorityQueue

I have also added an empty queue constant to the class. As a user of the class you then do not need to be concerned with the representation of the queues at all, there are predicates and constants for everything.

The predicates in this class are very simple to implement given the predicates we implemented before, the only thing they should do is to remove and add the queue functor in the relevant places:

clauses
    insert(queue(Queue), Priority, Data) = queue(insert_rep(Queue, Priority, Data)).
 
clauses
    tryGetLeast(queue(Queue)) = tryGetLeast_rep(Queue).
 
clauses
    deleteLeast(queue(Queue)) = queue(deleteLeast_rep(Queue)).

Using this _rep scheme is a bit less efficient, because of the extra functor, and it is entirely up to your temperament whether to use it or not. In any case it makes your type unique, rather than being a synonym type.

Priority queues can be used like this:

clauses
    test():-
        Pq1 = priorityQueue::empty,
        Pq2 = priorityQueue::insert(Pq1, 17, "World"),
        Pq3 = priorityQueue::insert(Pq2, 12, "Hello"),
        Pq4 = priorityQueue::insert(Pq3, 23, "!"),
        stdio::writef("%\n", Pq4).

The output looks like this (except for additional white space):

queue( [tuple(12,"Hello"), tuple(17,"World"), tuple(23,"!") ] )

It may seem that polymorphism disables type check, but in fact it gives a very strong but flexible type check. If, for example, I write:

clauses
    test():-
        Pq1 = priorityQueue::empty,
        Pq2 = priorityQueue::insert(Pq1, 17, "World"),
        Pq3 = priorityQueue::insert(Pq2, 12, 13).

Then I will get the error message:

error c504: The expression has type '::integer', which is incompatible with the type '::string'

The first insert forces the Data type of Pq2 to be string, therefore you cannot use an integer in the next line.

What may be more surprising is that it also forces the Data type of Pq1 to be string. Therefore this code gives exactly the same error:

clauses
    test():-
        Pq1 = priorityQueue::empty,
        Pq2 = priorityQueue::insert(Pq1, 17, "World"),
        Pq3 = priorityQueue::insert(Pq1, 12, 13).

On the other hand this is legal:

clauses
    test():-
        Pq1a = priorityQueue::empty,
        Pq2 = priorityQueue::insert(Pq1a, 17, "World"),
        Pq1b = priorityQueue::empty,
        Pq3 = priorityQueue::insert(Pq1b, 12, 13).

The "moral" is that the constant empty is polymorphic, but variables can only have a monomorphic type, so when empty is bound to a variable a concrete type is chosen and "frozen".

The priority queue above can be use for numerous purposes. And the code can be shared between all such uses, both within a single program and across programs. If I choose to make a more efficient solution to the priority queue, then I will benefit from this in all places where it is used.

Parametric polymorphism is used to solve different problems in the same way (e.g. a using priority queue), and as such it is often used to make basic library software.

Subsumption polymorphism is in many respects the complement to parametric polymorphism: it is used solve the same problem in different ways (e.g. reporting salaries to different salary systems), and as such it is often used at high levels in applications to deal with variance.

However, the world is not black and white in this respect, there are many graduations and clear exceptions to this.

Example: Job Scheduler

Now let us try to combine some of the things from above to produce a simple, but yet powerful job scheduler.

A job is just some computation that should be performed. You register a job in the scheduler; the scheduler will then start the job at the requested time. Given such an "alarm clock" scheduler it is relatively easy to deal with reoccurring jobs and jobs that start in X minutes rather than at a certain time, and so forth. Here we will only consider the "alarm clock" functionality.

The scheduler will rely on a timer event: every time the timer even triggers it will see if any jobs are due, and execute these.

In this example I will just assume that time is an integer. I might want to use several schedulers in my program, so I choose to represent each scheduler by an object. Therefore the scheduler is mainly described as an interface, i.e. the type of the scheduler objects. The declaration of the scheduler looks like this:

interface scheduler
domains
    job = (integer Time) procedure (i).
 
predicates
    registerJob : (integer Time, job Job).
 
predicates
    timerTick : (integer Time).
end interface scheduler

A job is a predicate value acting as a callback. I have chosen that the job receive the invocation Time as a parameter. This is mainly for illustrative purposes and simplicity. In real life, I would probably rather give it the scheduler, which I would enrich with predicates for obtaining the current time and probably other things as well. That way the job can itself decide which information it wants to obtain.

registerJob has the obvious functionality.

timerTick should be invoked regularly, since this is the heart of the scheduler.

The implementation looks like this:

implement scheduler
    open core, priorityQueue
facts
    jobQueue : queue{integer, job}.
 
clauses
    new() :-
        jobQueue := empty.
 
clauses
    registerJob(Time, Job) :-
        jobQueue := insert(jobQueue, Time, Job).
 
clauses
    timerTick(Time) :-
        if
            tuple(T, Job) = tryGetLeast(jobQueue),
            T <= Time
        then
            Job(Time),
            jobQueue := deleteLeast(jobQueue),
            timerTick(Time)
        end if.
end implement scheduler

Most of the implementation is completely trivial. The main thing is that I use a priority internally for storing the jobs, with the time as priority. This have the advantage that the "most due" job is always easily accessible.

There is a jobQueue fact that is initialized in the constructor, and registerJob simply insert the job in the priority queue.

The important things take place in timerTick. It peek at the "least" job in the queue. If this hob should be started now or earlier then it is stated and removed from the queue, and then the rest of the queue is considered.

If the "least" job is not due then we do nothing, i.e. then we wait for another timer tick.

Before we use the scheduler I want to point out that several good reasons why the scheduler does not contain the actual timer:

• It may be important to be in synchronization with some external clock

• In some contexts the increment in the Time parameter need not be the same al the time

• In some contexts the Time does not relate to real time. (E.g. game steps, workflow steps., etc).

• In a GUI application it may be important that the timerTick's are invoked from a window event. I.e. to keep the application single threaded.

Using external timer ticks makes all this possible.

Let us use the timer in a console program, where the clock is provided by a simple for loop:

class predicates
    traceJob : (integer Time).
clauses
    traceJob(Time) :-
        stdio::write("Now: ", Time, "\n").
 
clauses
    test() :-
        Scheduler = scheduler::new(),
        Scheduler:registerJob(500, traceJob),
        foreach Time = std::fromTo(1,1000) do
            Scheduler:timerTick(Time)
        end foreach.

The traceJob simply writes the clock. We create a scheduler and register the traceJob for running at Time = 500, and then we start the clock.

We can also make a job that reschedules itself and thus runs repeatedly. To do this the job must have access to the scheduler and therefore we save it in a fact:

class predicates
    cyclicJob : (integer Time).
clauses
    cyclicJob(Time) :-
        stdio::write("Hello World!\n"),
        scheduler:registerJob(Time+50, cyclicJob).
 
class facts
    scheduler : scheduler := erroneous.
clauses
    test() :-
        scheduler := scheduler::new(),
        scheduler:registerJob(5, cyclicJob),
        foreach Time = std::fromTo(1,200) do
            scheduler:timerTick(Time)
        end foreach.

In the scheduler we have clearly used the (parametric) polymorphic priority queue. We have also used the (subsumption) polymorphism that comes from predicate values, such that we can register jobs with different implementation in the scheduler. The parametric polymorphism has exploited the homogeneous treatment of prioritizing things, no matter which kind of things we are dealing with. The subsumption polymorphism has been used to deal with the heterogeneous nature of jobs themselves.