Difference between revisions of "Language Reference/Objects and Polymorphism"

From wiki.visual-prolog.com
(Reference to old version removed)
(version number)
 
Line 53: Line 53:
 
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:
 
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:
  
<vip>interface salarySystem
+
<vip>
 +
interface salarySystem
 
predicates
 
predicates
 
     salary : (string Name,  real Amount).
 
     salary : (string Name,  real Amount).
end interface salarySystem</vip>
+
end interface salarySystem
 +
</vip>
  
An object with this interface will allow you to report an Amount for a person (identified by Name).
+
An object with this interface will allow you to report an <vp>Amount</vp> for a person (identified by <vp>Name</vp>).
  
 
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:
 
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:
  
<vip>class predicates
+
<vip>
     reportSalary : (salarySystem SalarySystem).</vip>
+
class predicates
 +
     reportSalary : (salarySystem SalarySystem).
 +
</vip>
  
 
For the sake of the example, we simply hard code a little salary reporting like this:
 
For the sake of the example, we simply hard code a little salary reporting like this:
  
<vip>clauses
+
<vip>
 +
clauses
 
     reportSalary(SalarySystem) :-
 
     reportSalary(SalarySystem) :-
 
         SalarySystem:salary("John D", 135.12),
 
         SalarySystem:salary("John D", 135.12),
         SalarySystem:salary("Elvis P", 117.00).</vip>
+
         SalarySystem:salary("Elvis P", 117.00).
 +
</vip>
  
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:
+
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 <vp>salarySystem</vp> type '' subsumes'' all the different implementations of the interface. To deal with the ACME salary system we declare this class:
  
<vip>class acme : salarySystem
+
<vip>
end class acme</vip>
+
class acme : salarySystem
 +
end class acme
 +
</vip>
  
The declaration simply says that acme is a class that produces objects of type salarySystem. The class also needs an implementation:
+
The declaration simply says that <vp>acme</vp> is a class that produces objects of type salarySystem. The class also needs an implementation:
  
<vip>implement acme
+
<vip>
 +
implement acme
 
constants
 
constants
 
     fmt = "SAL:%>>>%\n".
 
     fmt = "SAL:%>>>%\n".
Line 85: Line 94:
 
     salary(Name, Amount) :-
 
     salary(Name, Amount) :-
 
         stdio::writef(fmt, Name, Amount).
 
         stdio::writef(fmt, Name, Amount).
end implement  acme</vip>
+
end implement  acme
 +
</vip>
  
 
To illustrate the polymorphism, we will also implement the integration to the O'Salery system. Again we declare and implement a class:
 
To illustrate the polymorphism, we will also implement the integration to the O'Salery system. Again we declare and implement a class:
  
<vip>class oSalary : salarySystem
+
<vip>
 +
class oSalary : salarySystem
 
end class oSalary
 
end class oSalary
  
Line 98: Line 109:
 
     salary(Name, Amount) :-
 
     salary(Name, Amount) :-
 
         stdio::writef(fmt, Name, Amount).
 
         stdio::writef(fmt, Name, Amount).
end implement oSalary</vip>
+
end implement oSalary
 +
</vip>
  
 
Now let us try our two salary system integrations:
 
Now let us try our two salary system integrations:
  
<vip>clauses
+
<vip>
 +
clauses
 
     test():-
 
     test():-
 
         ACME = acme::new(),
 
         ACME = acme::new(),
 
         reportSalary(ACME),
 
         reportSalary(ACME),
 
         Osalery = oSalary::new(),
 
         Osalery = oSalary::new(),
         reportSalary(Osalery).</vip>
+
         reportSalary(Osalery).
 +
</vip>
  
In the test predicate above, we create one of each salary systems and report salary to them. The result looks like this:
+
In the test predicate above, we create one of each salary systems and report salary to them. The result looks like this:
  
<vip>SAL:John D>>>135.12
+
<vip>
 +
SAL:John D>>>135.12
 
SAL:Elvis P>>>117
 
SAL:Elvis P>>>117
 
<salary name="John D" wage="135.12" />
 
<salary name="John D" wage="135.12" />
<salary name="Elvis P" wage="117" /></vip>
+
<salary name="Elvis P" wage="117" />
 +
</vip>
  
 
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.
 
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.
Line 146: Line 162:
 
Therefore we can declare our getMember_nd function like this:
 
Therefore we can declare our getMember_nd function like this:
  
<vip>predicates
+
<vip>
 +
predicates
 
     getMember_nd : (Elem* List) -> Elem Value
 
     getMember_nd : (Elem* List) -> Elem Value
         nondeterm.</vip>
+
         nondeterm.
 +
</vip>
  
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.
+
This declaration says that <vp>getMember_nd</vp> is a function, which takes a list of Elem argument and returns an Elem, where Elem is any domain/type.
  
 
The implementation is straightforward:
 
The implementation is straightforward:
  
<vip>clauses
+
<vip>
 +
clauses
 
     getMember_nd([V|_L]) = V.
 
     getMember_nd([V|_L]) = V.
     getMember_nd([_V|L]) = getMember_nd(L).</vip>
+
     getMember_nd([_V|L]) = getMember_nd(L).
 +
</vip>
  
Without further notice getMember_nd can be used on any list kind:
+
Without further notice <vp>getMember_nd</vp> can be used on any list kind:
  
<vip>clauses
+
<vip>
 +
clauses
 
     run():-
 
     run():-
 
         console::init(),
 
         console::init(),
Line 166: Line 187:
 
         foreach X = list::getMember_nd(L) do
 
         foreach X = list::getMember_nd(L) do
 
             stdio::writef("X = %\n", X)
 
             stdio::writef("X = %\n", X)
         end foreach.</vip>
+
         end foreach.
 +
</vip>
  
Here Elem is integer* (i.e. list of integers). The output looks like this:
+
Here <vp>Elem</vp> is <vp>integer*</vp> (i.e. list of integers). The output looks like this:
  
<vip>X = [1,2,3]
+
<vip>
 +
X = [1,2,3]
 
X = [7,-7]
 
X = [7,-7]
X = [9,4,5]</vip>
+
X = [9,4,5]
 +
</vip>
  
 
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 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.
+
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.
+
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:
 
'''tuple''' is already defined in Visual Prolog its definition looks like this:
  
<vip>domains
+
<vip>
     tuple{T1, T2} = tuple(T1, T2).</vip>
+
domains
 +
     tuple{T1, T2} = tuple(T1, T2).
 +
</vip>
  
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.:
+
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 <vp>T1</vp> and <vp>T2</vp>.  You may think of it as an infinite family of domains corresponding to all instantiations of the type parameters, e.g.:
  
<vip>domains
+
<vip>
 +
domains
 
     tuple_char_char = tuple(char, char).
 
     tuple_char_char = tuple(char, char).
 
     tuple_char_integer = tuple(char, integer).
 
     tuple_char_integer = tuple(char, integer).
 
     tuple_char_string = tuple(char, string).
 
     tuple_char_string = tuple(char, string).
     ...</vip>
+
     ...
 +
</vip>
  
 
The single domain definition above corresponds to all these domains, but actually the domain names/expressions look like this:
 
The single domain definition above corresponds to all these domains, but actually the domain names/expressions look like this:
  
<vip>   tuple{char, char}
+
<vip>
 +
    tuple{char, char}
 
     tuple{char, integer}
 
     tuple{char, integer}
 
     tuple{char, string}
 
     tuple{char, string}
     ...</vip>
+
     ...
 +
</vip>
  
 
The values looks as expected; let us take a relatively complex one right away:
 
The values looks as expected; let us take a relatively complex one right away:
  
<vip>   X = tuple(tuple('a',"a"), [1.2])</vip>
+
<vip>
 +
    X = tuple(tuple('a',"a"), [1.2])
 +
</vip>
  
X 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:
+
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:
  
<vip>   tuple{ tuple{char, string}, real* } </vip>
+
<vip>
 +
    tuple{ tuple{char, string}, real* }  
 +
</vip>
  
 
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.
 
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.
Line 212: Line 246:
 
We are now ready to define our queue domain:
 
We are now ready to define our queue domain:
  
<vip>domains
+
<vip>
     queue_rep{Priority, Data} = tuple{Priority, Data}*.</vip>
+
domains
 +
     queue_rep{Priority, Data} = tuple{Priority, Data}*.
 +
</vip>
  
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 further more it is a list of tuple's of these types.
+
The <vp>_rep</vp> in the domain name has to do with the scheme mentioned above, right now you can simply ignore it. The domain definition says that <vp>queue_rep</vp> is a domain with two type parameters <vp>Priority</vp> and <vp>Data</vp> 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 7.0 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.
+
You may wonder why <vp>Priority</vp> 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:
 
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
 
*transferring as parameter
 
 
*binding and unifying (with values of same type)
 
*binding and unifying (with values of same type)
 
 
*comparing (with values of same type)
 
*comparing (with values of same type)
 
 
*writing on streams
 
*writing on streams
 
 
*reading from streams
 
*reading from streams
  
Line 235: Line 267:
 
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 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:
+
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:
  
<vip>predicates
+
<vip>
     tryGetLeast_rep : (queue_rep{Priority, Data} Queue) -> tuple{Priority, Data} Least determ.</vip>
+
predicates
 +
     tryGetLeast_rep : (queue_rep{Priority, Data} Queue) -> tuple{Priority, Data} Least determ.
 +
</vip>
  
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 predicate is <vp>determ</vp> 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 <vp>Priority</vp> and the <vp>Data</vp>.  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:
 
The list is sorted with the least element first, so the implementation is trivial:
  
<vip>clauses
+
<vip>
     tryGetLeast_rep([Least|_]) = Least.</vip>
+
clauses
 +
     tryGetLeast_rep([Least|_]) = Least.
 +
</vip>
  
 
Similarly we need a predicate for removing the least element:
 
Similarly we need a predicate for removing the least element:
  
<vip>predicates
+
<vip>
 +
predicates
 
     deleteLeast_rep : (queue_rep{Priority, Data} Queue1) -> queue_rep{Priority, Data} Queue.
 
     deleteLeast_rep : (queue_rep{Priority, Data} Queue1) -> queue_rep{Priority, Data} Queue.
 
clauses
 
clauses
 
     deleteLeast_rep([]) = [].
 
     deleteLeast_rep([]) = [].
     deleteLeast_rep([_Least|Rest]) = Rest.</vip>
+
     deleteLeast_rep([_Least|Rest]) = Rest.
 +
</vip>
  
Finally we need an insert predicate:
+
Finally, we need an insert predicate:
  
<vip>predicates
+
<vip>
 +
predicates
 
     insert_rep : (queue_rep{Pri, Data} Q1,  Pri P,  Data D) -> queue_rep{Pri, Data} Q0.
 
     insert_rep : (queue_rep{Pri, Data} Q1,  Pri P,  Data D) -> queue_rep{Pri, Data} Q0.
 
clauses
 
clauses
Line 269: Line 308:
 
             Q0 =
 
             Q0 =
 
                 [tuple(P1,D1) | insert_rep(Rest, Pri, Data)]
 
                 [tuple(P1,D1) | insert_rep(Rest, Pri, Data)]
         end if.</vip>
+
         end if.
 +
</vip>
  
 
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.
 
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.
 
In future versions of Visual Prolog there will also be type variables whose scope is a complete interface/class/implementation.
 
  
 
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:
 
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:
  
<vip>domains
+
<vip>
     queue_rep{Priority, Data} = tuple{Priority, Data}*.</vip>
+
domains
 +
     queue_rep{Priority, Data} = tuple{Priority, Data}*.
 +
</vip>
  
A definition like this one is just an abbreviation or synonym, so queue_rep{integer, sting} is exactly the same as tuple{integer, string}*.
+
A definition like this one is just an abbreviation or synonym, so <vp>queue_rep{integer, sting}</vp> is exactly the same as <vp>tuple{integer, string}*</vp>.
  
#The debugger will always show the unfolded type (i.e. tuple{integer, string}*) and this can be rather confusing.
+
#The debugger will always show the unfolded type (i.e. <vp>tuple{integer, string}*</vp>) and this can be rather confusing.
  
 
#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).
 
#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).
Line 292: Line 332:
 
Therefore, to the real queue domain will look like this:
 
Therefore, to the real queue domain will look like this:
  
<vip>domains
+
<vip>
     queue{Priority, Data} = queue(queue_rep{Priority, Data}).</vip>
+
domains
 +
     queue{Priority, Data} = queue(queue_rep{Priority, Data}).
 +
</vip>
  
 
Such a domain is neither an abbreviation nor a synonym.
 
Such a domain is neither an abbreviation nor a synonym.
Line 299: Line 341:
 
The exported/public predicates will of course work on queue 's, so the complete class declaration looks like this:
 
The exported/public predicates will of course work on queue 's, so the complete class declaration looks like this:
  
<vip>class priorityQueue
+
<vip>
 +
class priorityQueue
 
     open core
 
     open core
  
Line 319: Line 362:
 
predicates
 
predicates
 
     deleteLeast : (queue{Priority, Data} Queue1) -> queue{Priority, Data} Queue.
 
     deleteLeast : (queue{Priority, Data} Queue1) -> queue{Priority, Data} Queue.
end class priorityQueue</vip>
+
end class priorityQueue
 +
</vip>
  
 
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.
 
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.
Line 325: Line 369:
 
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:
 
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:
  
<vip>clauses
+
<vip>
 +
clauses
 
     insert(queue(Queue), Priority, Data) = queue(insert_rep(Queue, Priority, Data)).
 
     insert(queue(Queue), Priority, Data) = queue(insert_rep(Queue, Priority, Data)).
  
Line 332: Line 377:
  
 
clauses
 
clauses
     deleteLeast(queue(Queue)) = queue(deleteLeast_rep(Queue)).</vip>
+
     deleteLeast(queue(Queue)) = queue(deleteLeast_rep(Queue)).
 +
</vip>
  
 
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.
 
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.
Line 338: Line 384:
 
Priority queues can be used like this:
 
Priority queues can be used like this:
  
<vip>clauses
+
<vip>
 +
clauses
 
     test():-
 
     test():-
 
         Pq1 = priorityQueue::empty,
 
         Pq1 = priorityQueue::empty,
Line 344: Line 391:
 
         Pq3 = priorityQueue::insert(Pq2, 12, "Hello"),
 
         Pq3 = priorityQueue::insert(Pq2, 12, "Hello"),
 
         Pq4 = priorityQueue::insert(Pq3, 23, "!"),
 
         Pq4 = priorityQueue::insert(Pq3, 23, "!"),
         stdio::writef("%\n", Pq4).</vip>
+
         stdio::writef("%\n", Pq4).
 +
</vip>
  
 
The output looks like this (except for additional white space):
 
The output looks like this (except for additional white space):
  
<vip>queue( [tuple(12,"Hello"), tuple(17,"World"), tuple(23,"!") ] )</vip>
+
<vip>
 +
queue( [tuple(12,"Hello"), tuple(17,"World"), tuple(23,"!") ] )
 +
</vip>
  
 
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:
 
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:
  
<vip>clauses
+
<vip>
 +
clauses
 
     test():-
 
     test():-
 
         Pq1 = priorityQueue::empty,
 
         Pq1 = priorityQueue::empty,
 
         Pq2 = priorityQueue::insert(Pq1, 17, "World"),
 
         Pq2 = priorityQueue::insert(Pq1, 17, "World"),
         Pq3 = priorityQueue::insert(Pq2, 12, 13).</vip>
+
         Pq3 = priorityQueue::insert(Pq2, 12, 13).
 +
</vip>
  
 
Then I will get the error message:
 
Then I will get the error message:
Line 366: Line 418:
 
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:
 
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:
  
<vip>clauses
+
<vip>
 +
clauses
 
     test():-
 
     test():-
 
         Pq1 = priorityQueue::empty,
 
         Pq1 = priorityQueue::empty,
 
         Pq2 = priorityQueue::insert(Pq1, 17, "World"),
 
         Pq2 = priorityQueue::insert(Pq1, 17, "World"),
         Pq3 = priorityQueue::insert(Pq1, 12, 13).</vip>
+
         Pq3 = priorityQueue::insert(Pq1, 12, 13).
 +
</vip>
  
 
On the other hand this is legal:
 
On the other hand this is legal:
  
<vip>clauses
+
<vip>
 +
clauses
 
     test():-
 
     test():-
 
         Pq1a = priorityQueue::empty,
 
         Pq1a = priorityQueue::empty,
 
         Pq2 = priorityQueue::insert(Pq1a, 17, "World"),
 
         Pq2 = priorityQueue::insert(Pq1a, 17, "World"),
 
         Pq1b = priorityQueue::empty,
 
         Pq1b = priorityQueue::empty,
         Pq3 = priorityQueue::insert(Pq1b, 12, 13).</vip>
+
         Pq3 = priorityQueue::insert(Pq1b, 12, 13).
 +
</vip>
  
 
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 "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".
Line 401: Line 457:
 
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:
 
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:
  
<vip>interface scheduler
+
<vip>
 +
interface scheduler
 
domains
 
domains
 
     job = (integer Time) procedure (i).
 
     job = (integer Time) procedure (i).
Line 410: Line 467:
 
predicates
 
predicates
 
     timerTick : (integer Time).
 
     timerTick : (integer Time).
end interface scheduler</vip>
+
end interface scheduler
 +
</vip>
  
 
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.
 
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.
Line 420: Line 478:
 
The implementation looks like this:
 
The implementation looks like this:
  
<vip>implement scheduler
+
<vip>
 +
implement scheduler
 
     open core, priorityQueue
 
     open core, priorityQueue
 
facts
 
facts
Line 443: Line 502:
 
             timerTick(Time)
 
             timerTick(Time)
 
         end if.
 
         end if.
end implement scheduler</vip>
+
end implement scheduler
 +
</vip>
  
 
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.
 
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.
Line 467: Line 527:
 
Let us use the timer in a console program, where the clock is provided by a simple for loop:
 
Let us use the timer in a console program, where the clock is provided by a simple for loop:
  
<vip>class predicates
+
<vip>
 +
class predicates
 
     traceJob : (integer Time).
 
     traceJob : (integer Time).
 
clauses
 
clauses
Line 479: Line 540:
 
         foreach Time = std::fromTo(1,1000) do
 
         foreach Time = std::fromTo(1,1000) do
 
             Scheduler:timerTick(Time)
 
             Scheduler:timerTick(Time)
         end foreach.</vip>
+
         end foreach.
 +
</vip>
  
 
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.
 
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.
Line 485: Line 547:
 
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:
 
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:
  
<vip>class predicates
+
<vip>
 +
class predicates
 
     cyclicJob : (integer Time).
 
     cyclicJob : (integer Time).
 
clauses
 
clauses
Line 500: Line 563:
 
         foreach Time = std::fromTo(1,200) do
 
         foreach Time = std::fromTo(1,200) do
 
             scheduler:timerTick(Time)
 
             scheduler:timerTick(Time)
         end foreach.</vip>
+
         end foreach.
 +
</vip>
  
 
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.
 
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.
 
  
 
[[ru:Объекты и полиморфизм. Ч.1]]
 
[[ru:Объекты и полиморфизм. Ч.1]]

Latest revision as of 22:45, 15 July 2017

Language Reference

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 example 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.