Finite and Infinite in Lucid2D

Lucid2D is Lucid with both time and space dimensions, as discussed in my last blog post. Program variables denote intensions that can be thought of as streams of arrays. Infinite streams of infinite arrays.

“But wait!” I hear you say. “It’s nice to write elegant equations defining the infinite array of all primes but what about the everyday working world? What about the array of midterm marks of my class? It’s finite! How do you work with that in Lucid2D?”

Not obvious. You can create an infinite array whose first elements are the midterm marks followed by infinitely many -99 values. Then set a variable N equal to the number of valid marks and (say) average the first N values of the array. But in what form to you read it in in the first place? We need a general input protocol that, obviously, doesn’t give -99 a special status.

This becomes more pressing if we’re inputting a finite number of finite arrays. In which case we need a whole stream of N’s.

As I mentioned when  we first tried to “add arrays” to Lucid we tried to find a simple algebra of finite vectors, matrices, etc but never succeeded. The algebra would be specially complex if you want ‘ragged’ arrays in which rows have different lengths (as mentioned above). It turned out that infinite arrays are mathematically simpler than finite ones.

Still, a language that can’t easily average a finite list of midterm grades is not much use. Eventually, we came up with a better solution.

The idea is to introduce a special value that works like -99 above but isn’t an actual number. The new object is eod, which stands for “end of data”. The object eod is not a number, (or a string or a boolean etc). It’s the value of a stream that has terminated. I think of it as the value read in (in UNIX) after you hit control-D.

The input convention is clear. A finite stream gets entered as an infinite one padded with eod’s. The output convention is also simple. When outputting a stream X, you (as usual) demand the values of X in order and output them. When the value returned is eod, you don’t produce anything, rather you terminate normally.

Lucid is based on an algebra: a set of values together with a set of operations on these values. If you extend the set of values, you have to extend the operations and say how they work if any of the operands are the new values.

Fortunately that’s simple for eod. The basic rule is that any data operation (like “+”) that is strict (needs all its arguments) returns eod if any of its arguments are eod. In other words

eod+1 = 4+eod = eod+eod = eod

For an operation like if-then-else that doesn’t need all its arguments, the first argument needed is sensitive on its own to eod:

if eod then 3 else 4 fi = eod

Otherwise it simply chooses between alternatives as usual:

if true then 3 else eod fi = 3

if false then 3 else eod fi = eod

if false then eod else eod fi = eod

Similarly

false and eod = false

true and eod = eod

eod and eod = eod

As for the space and time Lucid operations, they aren’t affected. For example, the value of next X at time t is still the value of X at time t+1 – whether or not this value is eod. So if we’ve written an eductive interpreter, the only part that needs changing is the part that evaluates data operations.

For strict operations, the rule (above) is simple. For if-then-else-fi we first evaluate the test; if it is eod, we return eod. Otherwise we evaluate and return the chosen alternative. Similarly, to evaluate an and expression we evaluate the first operand and return eod if that value is eod. Otherwise, we evaluate the second operand and return this value.

To conclude let’s consider the midterm grades problem. Suppose that we input the stream (a stream, rather than an array) of grades as G, padded with eod’s as above. Let’s say G is

56, 79, 66, 85, eod, eod, eod, …

(it’s a small class).

First we define a running sum

S = first G fby S + next G

so that S is

56, 135, 201, 286, eod, eod, eod, …

Notice that S is also ‘really’ a finite stream of the same length. Yet its definition doesn’t take finiteness into account. When the next value of S is computed by increasing it by the next value of G, and this next value is eod, the resulting value of S is also eod.

Now we define a counter and form the running average A:

N = 1 fby N+1

A = S/N

so that A is

56, 67.5, 67, 71.5, eod, eod, eod, …

(because eod/5 etc is eod).

All we need is the last value of A; the value when the next value is eod. At the moment we can’t  do this because we can’t test for eod. The comparison X eq eod returns eod, because eq is a strict data operation.

We need a primitive that can gaze on eod without being turned to eod. We call it iseod and iseod X returns true if X is eod, false otherwise. Then we can define last as

last(X) = X asa iseod next X

and what we want is last(A). However that’s all we want, so if we ask for

last(A) fby eod

we get one number and a normal termination, as desired. More eloquently, if

just(Y) = first Y fby eod

our output is just(last(A)).

There’s more interesting operators like last that can be defined with eod and iseod. Also, what about intensions that are finite in space as well as time? I’ll talk about these next time.

Finally, you know how this post has to end.

eod

 

Advertisements

About Bill Wadge

I am a Professor in Computer Science at UVic.
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.