Parametric Programming – an equational approach to OO and beyond

A very long time ago I had an interesting if flawed idea. The idea was to (optionally) replace instances of expression constructs with equations defining or referring to components of conventional compound structures. The special variables defined or used I called “pronouns” but now I prefer “parameters”.

I fixed the flaw … and in so doing discovered a promising new equational programming paradigm.

The new paradigm allows a purely equational approach to something like OO and in particular allows an OO extension of Lucid that is simple and natural. But parametric programming (PP) seems to go beyond OO. It can be used in conjunction with other declarative languages like Haskell.

Valof clauses

First we need to avoid where clauses, which complicate the issues. When I was at Warwick in the old days there was a band of enthusiastic devotees of the pioneering system language BCPL. BCPL was a descendant of the monster (and unimplemented) language CPL, and an ancestor (via B) of C itself.

Anyway BCPL had many nice features including the VALOF construct. A VALOF was like a begin-end block except that you use a command RESULTIS to return a value. For example

VALOF $( DISC := B*B - 4*A*C IF DISC < 0 RESULTIS ERR RESULTIS (-B + SQRT(DISC))/(2*A) $)

BCPL’s VALOF is easily adapted to an equational approach. We simply replace the commands with an (unordered) set of equations including exactly one for the special variable result:

valof disc = b*b - 4*a*c; root = (-b + sqrt(disc))/(2*a); result = if disc<0 then ERR else root fi; end

(Note that the Lucid version, in which variables are evaluated on demand, will not attempt to take a negative square root. The equations are not assignment statements.)

Output parameters

At one point an interesting thought occurred to me, why not have output parameters? That return results? For example, this would allow an equivalent of if-then-else-fi without the nested structure:

valof test = n<1; choicet = 1; choicef = n*(n-1); result = choice; end

The variable result is special in that it cannot be renamed – unlike disc and root. I call it a “parameter”, like the parameters columns, rows and numformat pyLucid uses to format output.

Here it’s understood that

choice = if test then choicet else choicef fi

but you don’t write this equation, it’s automatically included.

So that was my idea. I showed that with parameters you can formalize other “constructs” like multiple exit loops.

And that was it. Not an earth-shaking idea. And one with a few problems. For example, it ties up identifiers like “choice” or “test” that the programmer might want to use. So I dropped it, for many decades.

A simple modification

The other day I decided to write a blog post about parameters and as I reflected on the problem of tied-up identifiers a simple solution occurred to me: preface the parameter names with the names of the construct in question. Thus for example

valof if.test = n < 1; if.true = 1; if.false = n*(n-1); result = if.result end

Well will you look at that. Familiar? Yes, it looks like the invocation of an OO object called “if”. The equations defining the ‘input’ parameters like “if.test” are setting properties (in this case test) and the expression if.result is calling a method result.

And yet there’s nothing going on other than invoking an implicit equation, namely

if.result = if if.test then if.true else if.false fi;

No storage allocation and no parameter initialization, none of the overhead associated with creating an object in traditional imperative OO. At most copying a string at compile time, namely the implicit equation.

Schemes

Clearly the if object is built-in. What about other objects we might want? Suppose we wanted to solve a quadratic equation. We can imagine invoking an object quad

valof 
  import quad;
  quad.a = 3;
  quad.b = 9;
  quad.c = -8;
  result = [%quad.root1,quad.root2%];
end

to calculate the two roots of the quadratic/;

3x2 + 9x - 8

Notice the line

import quad;

I put that there because I imagined quad would not be built-in and we’d have to invoke something to bring in the required implicit equations. And what would these equations be? Something like

disc = b*b - 4*a*c;
droot = sqrt(disc);
root1 = (-b + droot)/2/a
root2 = (-b - droot)/2/a

The obvious solution is

class quad droot = sqrt(disc); root1 = (-b + droot)/2/a root2 = (-b - droot)/2/a end

except there’s not enough information here. We need to specify that a, b, and c are input parameters (basically properties) and that root1 and root2 (but not disc and droot) are output parameters (basically methods). Also, as we will find, these packages can’t always be thought of as OO objects. So I’ve decided to call these sets of equations “schemes” as in

scheme quad disc = $b*$b - 4*$a*$c; droot = sqrt(disc); $root1 = (-$b + droot)/2/$a $root2 = (-$b - droot)/2/$a end

The fact that $root1 and $root2 have definitions means root1 and root2 are output parameters.

Function Parameters

So far so good. Then something hit me: both input and output parameters could be functions:

scheme integrate
m = ($a+$b)/2
$area = ($b-$a)($f($a)+4$f(m)+$f($b)

and could be used as follows:

valof
 import integrate
 integrate.a = 1;
 integrate.b = 2;
 integrate.f(x) = 1/x;
 log2 = integrate.area;
end

This was a big surprise! pyLucid (for example) is strictly first order, you can’t define a function that takes another function as an argument. We figured out how to do it in principal but there are syntactical and implementation complications.

And now we have it almost for free, all done with little more than compile time string copying. We can also have functions returned as output parameters, as in this scheme which computes a derivative numerically:

scheme deriv
 $df(x) = ($f(x+eps)-$f(x))/eps;
end
valof
 import deriv;
 deriv.f(x) = x*x;
 result = deriv.df(4);
end

Enter PYFL

At this point it occurred to me that this idea has nothing inherently to do with Lucid, it works with any equational language. Furthermore as an equational language Lucid has irrelevant baggage such as being first order and requiring dimensional analysis to make eduction work.

So I decided  to specify and implement a super simple equational language as a platform for demonstrating parameters. Thus was born PYFL, the PYthon based Functional Language.

What followed was ironic on two grounds. First, PYFL was not super simple for long. I discovered that it was  relatively easy to extend PYFL with interesting features like VBOs or (paradoxical) functional while loops. At the same time, I got distracted from parameters and didn’t implement them till quite late.

And when I did implement them, I discovered that they aren’t quite as simple as they seem. You can’t just have the (say)  equation for if.result at the topmost level. It  has to be included in every valof clause that imports the if scheme.

User defined schemes are complex and haven’t been done yet.

So parameters aren’t quite vaporware but they haven’t really been tried out. The vapor hasn’t condensed yet.

 

 

About Bill Wadge

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

1 Response to Parametric Programming – an equational approach to OO and beyond

  1. Pingback: Tech roundup 105: a journal published by a bot - Javi López G.

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.