Symbolic Logic:Programming:Change In Time
Logic Programming is extended with features to make it useful in describing a changing world.
The view of mathematics is that the universe is essentially static. We may learn more information about it, but any true fact about it wont change.
This is a wonderfull thing. Mathematics allows for a unique naming of each thing at a particular point in time. This unique naming has immense power.
Value Set Programming is an implementation of a subset of mathematics that lends itself to simple evaluation.
To adapt Logic Programming for practical use we need to consider efficiency in common situations. Also while mathematics may view the world from outside as unchanging, a computer program running on a computer is part of that world, and is moving through time.
Contents |
[edit] Time Change
The mathematical view of time is as another dimension. Simply speaking the world at each instance in time may be regarded as a list of world states. This view allows us to extend the list with new world states to represent the passing of time.
This view is fine in theory as long as we dont ask for the world state at a future point in time. As soon as we ask for information about the world state in the future we are in trouble.
The basics of mathematics is that each expression represents a single value. What answer we give to a question cannot change. This means that I cant answer a question with "I dont know", and later give an actual answer.
This may seem innocent to have a value for a variable that represents "I dont know yet". But consider the equation,
- x = (if y(t) = "I dont know" then 5 else 6)
Here t represents some constant time. If t is in the future then the value of y(t) is not known. But as time passes t moves to the present and then to the past. So y(t) changes from "I dont know" to some other value. Then x changes its is value from 5 to 6.
A change in a variables value is not allowed in mathematics. So we need to be careful about what we ask. When can never ask for a value that is unknown.
[edit] Change
Using a list of world states as the model, modelling a change is difficult. If I want to change the colour of an object from red to green, what I have to do is create a new world, copy all the objects and attributes from the world at the previous time, except for the colour of the object, which is set as green. This is not feasable in practice.
The solution to this problem is to change the model. Instead of a series of world states there is one world. But each attribute of the world is modelled as a list of attributes representing the changing value of the attribute over time. By associating each attribute value with a particular time we allow the state of the world to be reconstructed at any particular time.
In this model to change our objects colour from red to green we again need to leave every other attribute the same and add a list entry for the color attribute of the object. In theory leaving all the other world attributes the same means visiting every object, and every attribute of each object, and adding another time, value pair, that leaves the value unchanged. But in practice we dont need to do this.
Instead when we change an objects attribute, we add a (time, value) pair to the list of values for the attribute.
When we want to query an objects attribute value for a particular reference time, we traverse the list of time, value pairs ends until we find a time on or after the reference time. If we come to the end of the list, and our reference time is not in the future we assume that the value has not changed since the laste time, value pair. This breaks the rules of mathematics because we need to ask the list for an unknown value. This indiscrestion is allowed for the implementation because the effect is the same as if we had extended each attributes list whenever we implemented a change to a value.
Requesting a value in the future is not possible. Such a call can only return when the value is known.
[edit] Clocks
Consider a clock object c. We ask c for the time.
- t1 = c.time()
- t2 = c.time()
But then t1 = t2. So the clock must always give the same time. The solution is to ask the clock for a new clock object.
- c3 = c.next()
then,
- t3 = c3.time()
Time behaves like a list. The times in the past are fixed. The times in the future are not yet known. But as soon as the time is retrieved the value is fixed.
If we wanted to rerun the program we can by giving it the same original clock object. That clock now has the series of times fixed, so we can run the program again and get exactly the same result.
A clock obeys the rule,
- c.time() < c.next().time()
[edit] Branching Clocks
Functional and logic programs do not have to be evaluated in a particular order. There may be many orders of evaluation that give the same result. This contrasts with imperative programs where the order must be pre-determined.
But because we need the time when we update an attribute of an object, clock objects need to be passed around. Every method that changes an attribute needs a clock as a parameter, and needs to pass out a clock as an output parameter. This has the unfortunate side effect of pre-determining the order of execution of the logic programming.
This is a bad thing. Clock branching avoids this. The branch method gives a new clock which gives a list of times independently of the original clock.
- c.time() < c.branch().time()
but not necessarily c.next().time() < c.branch().time().
Branching clocks free us from a particular order of processing.
[edit] Attributes
An attribute is an imperative language is often accessed using a Get and a Set method. The Set method changes the value.
String GetName() { return m_Name; } void SetName(String newVal); { m_Name = newVal; }
In mathematics and logic programming a value can not change. But if we add time as a parameter,
String GetName(Time transactionTime) { return m_NameList.Find(transactionTime); } void SetName(Time transactionTime, String newVal); { m_NameList.Add(transactionTime, newVal); }
Here m_NameList is a list of (time, value) pairs.
In GetName find searches the list for the first pair whose time is greater than or equal to transactionTime. If no pair is found then the last pair is retrieved.
How can Find know if a pair is the last in the list. Strictly it cannot.
However what would be allowed is add a (time, value) pair to every attribute at every tick of the clock. This would be inconvenient and inefficient, but legal.
So instead we need a special kind of class called a service. Services are described below, but first we need to deal with this nuisance of passing a time parameter around everywhere.
[edit] Implicit Parameters and Roles
In using the Get and Set methods defined above we might have code like
// Version A void Initialize(Time transactionTime, String name) { SetName(transactionTime, name); ... }
Passing transactionTime around everywhere is a nuisance. It distracts from the main intent of the programmer. It is cleaner to write,
// Version B void Initialize(String name) { SetName(name); ... }
Implicit parameters allow version B to mean the same thing as version A. But firstly we need to introduce the reserved word "role" and write the Get and Set methods as,
String GetName(role Time transactionTime) { return m_NameList.Find(transactionTime); } void SetName(role Time transactionTime, String newVal); { m_NameList.Add(transactionTime, newVal); }
The "role" keyword says that you dont actually have to provide the parameter (although you can). Instead when the call is made look in the environment of the call look for a "role" variable with the same name.
But in the case of the Initialize function it doesnt have a parameter,
role Time transactionTime
Then because we need this role and it is not defined the compiler adds it as an "Implicit Parameter" to the Initialize function.
And if Initialize was called by another function that did not have a transactionTime role parameter it would be added to that function too.
Version B of the code now looks like legacy imperative code. This means that we can re-interpret imperative code based on Get and Set methods as logic programming.
[edit] Why are "roles" useful
The term "role" is meant here as in "an actor plays a role". But instead of an actor, it is a variable that plays the role. In the call we dont need to be passed the actual value or variable. Instead we can look around for a variable that is playing the role and use it as the parameter.
The "role" functionality is only "syntactic sugar". There is nothing that could not be written without it.
However the "role" functionality allows us to hide "noise". People find extra parameters hard to comprehend. The strength of the human brain is in focusing on the key points. Role functionality allows us to hide the clutter but have the parameters at hand when we need them.
Consider a situation where we are modifying a function and find we need a parameter. If we add a normal parameter we must visit every calling function and add the extra parameter to the call. But then the calling function may need an extra parameter to get the value.
With a "role" parameter we simple add the parameter and it is implicitly added to the other functions where needed. Then at the point where we have the value we provide it as the value to a function call to fill the implicit parameter.
Roles allow us to plumb a value through many levels of function call with no work, or clutter in the code. This allows us to easily use parameters where otherwise we may resort to using global variables. Using global variables makes the code inflexible.
And as we have seen it can be used to re-interpret legacy imperative code as logic programming. Monadic programming achieves the same goal, but unfortunately the concepts in using monads are hard to understand.
[edit] Input and Output Roles
The roles described above are input roles. They take a role parameter value in. Output roles allow us to change the "player" of the role at the point of the call.
This best explained by an example. Suppose I want to write a log file to record the progress of my processing,
void CarWash(Car car) { Wet(car); Soap(car); Rinse(car); Wax(car); }
Then my Wax function,
void Wax(Car car) { Logger.Write("Started waxing car " + car.GetRegistrationNo()); ... Logger.Write("Finished waxing car " + car.GetRegistrationNo()); }
Then in the Logger class,
static void Write(role Logger logFile, role Logger outLogFile to logFile, String text) { outLogFile = logFile.WriteString(text); }
Because the WriteString function cannot have a side effect on the logFile it needs to return a new logFile object (representing the new point in the file).
This new value goes into the outLogFile parameter. If the output parameter is not provided in the call the variable is created to take the output parameter and that variable takes on the role of logFile after the call.
[edit] Output Roles
An output role from a call causes the compiler to look for an output role with the same name in the calling function, and create one if it doesnt find. The variable in the role becomes the output variable. So the above example is the same as,
void Wax(role Logger logFile, role Logger outLogFile to logFile, Car car) { Logger.Write(logFile, l1, "Started waxing car " + car.GetRegistrationNo()); ... Logger.Write(l1, outLogFile, "Finished waxing car " + car.GetRegistrationNo()); }
Output roles should be used sparingly. Output roles model imperative programming in logic and have the same problem. They force the evaluation into a particular order. This means that a parrallel implementation is not possible.
See also,
[edit] Services
Sometimes we need to get around the strict laws of mathematics. The reason for this is that the computer is always changing. Mathematics works in the clean world where the universe is out there to be described. But, for some aspects of the computer, the world is not out there. The world includes the computer, and it is changing.
However there are relatively few cases where it is necessary to allow values to change. These cases are handled by service classes.
A service class is a class may have mutable member variables. The service class may use and modify these mutable variables as long as it does not expose this behaviour to the outside world.
A value returned by a function that comes from a mutable variable is muted. A muted variable cannot be accessed, other than to compare it for equality with another muted variable.
[edit] Id Generator Service
service class IdGenerator { mutable long m_id; IdGenerator() { m_id = 0; } muted Id CreateId() { m_id := m_id + 1; return Id(m_id); } }
Then ids could be generated by code like,
void MyExampleIds(IdGenerator gen) { long v1 = gen.CreateId(); long v2 = gen.CreateId(); }
CreateId returns a different Id every time it is called, but because the value is "muted" it cannot be accessed. But the value may be accessed by service classes. The Id value may then end up in the database or written to a report. The behaviour of the other classes is protected because they cannot access the muted Id value.
[edit] How not to implement an Id generator
We could use a list concept, as used in the Clock class, to implement an Id Generator.
class IdGenerator { long m_id; IdGenerator(long p_id) { m_id = p_id; } Id CreateId() { return Id(m_id); } IdGenerator Next() { return new IdGenerator(m_id + 1); } }
The above class could be used like,
void MyExampleIds(IdGenerator in, IdGnerator out) { long v1 = in.CreateId(); IdGenerator next = in.Next(); long v2 = next.CreateId; out = next.Next(); }
Of course this code could be tidied up using roles. However the problem is that the code written this way has a pre-determined order of evaluation when none is required.
In the future one of the strengths of languages based on mathematics will be that the order of evaluation is not pre-determined and that evaluation can proceed in parallel.
[edit] Time List Class
Previously we needed a list of (time, value) pairs in implementing attributes. This class is the TimeList class. Because the TimeList class must check for the end of the list, which is illegal as more pairs may be added later, the TimeList is implemented as a sevice.
service class TimeList(type) { type m_value; Time m_time; TimeList(type) m_next; type Find(Time t) { if t < m_time then { return unknown; } else if m_time = t or m_next = unknown then { return Unmute(m_value); } else { return m_next.Find(t); } } ... }
Here the service class is being used to hide the behind the scenes bad behaviour that means that we dont have to visit every other attribute every time an attribute is changed.
