Table of Contents:
Library Polya defines a polymorphic (Lisp-like) data type, along with a number of methods and functions which operate on items of this type. The purpose of Polya, for the most part, is to support the functional programming paradigm directly within C++ and to enable rapid prototyping of programs using built-in constructs such as lists and dynamic arrays.
This document assumes the reader is knowledgable about functional programming, object-oriented programming, and C++. It does not attempt to be a tutorial on these topics.
A similar Polya library is available as a Java package. Included in the C++ Polya support are:
Currently automatic storage reclamation is implemented using reference counting and is totally invisible to the user. Likewise, the user does not need to use pointers. Data may be passed as if by value and reference, with all pointer-based structures being implemented behind the scenes.
A central feature of Polya is the ability to construct a list, called a Polylist, of mixed types of elements. A list may consist of integers, floating numeric values, lists, arrays, and functions, in any mixture. Lists can thus be nested within lists to any level of nesting. Therefore it is also easy to construct trees. There is also the analogous concept of Polyarray for arrays. Additionally, the size of a polyarray can be changed dynamically. Although it is not necessary to use this feature, elements of both Polylists and Polyarrays can be replaced by assignment if desired.
The following list and array formatting style is used in this document. In addition, input and output operators (>> and << in C++) are provided which read and write, in this format, an entire item in one step. Of course, the format has little to do with the way the information is actually stored, and it is easy to write one's own custom formatting procedures.
Polylists are printed as S expressions as in Lisp:
(This is an (S expression) with 8 atoms)
Polyarrays are printed using square brackets rather than parentheses. Otherwise, they look the same as lists.
[This is a 6 element array]
Digits and the symbols + and - are interpreted as starting a numeral when read in. If it is desired to treat them as starting a string instead, they should be escaped by putting a \ in front of them. Likewise, on output, strings which begin with digits or + or - will have a \ before those characters so that they may be read back in.
Improper lists, lists which have a rest which is not a list, are shown by a | preceding the rest, rather than using a dot as is customary in Lisp.
A list which ends with a seed will output with ... on the end, indicating that there is more of the list.
The means by which polylists are implemented is as a list of a single type known as a Poly (for polymorphic datum, a datum which can take on many forms). A Poly is a C++ type defined as a class, and can be viewed as a wrapper which can wrap various types of data. Currently the following types can be wrapped.
|
Wrapped-type identifier |
Interpretation |
|
INTEGER |
integer numeric value |
|
FLOATING |
floating point numeric value |
|
CHAR |
single character |
|
STRING |
string of characters |
|
LIST |
list of Polys |
|
ARRAY |
array of Polys |
|
SEED |
used to compute a value on demand |
|
FCLOSURE |
function closure |
|
FUNCTION1 |
function of one Poly, returning a Poly |
|
FUNCTION2 |
function of two Polys, returning a Poly |
|
ISTREAM |
input stream |
|
ERROR |
error value |
|
SCLOSURE |
closure implemented by symbolic evaluation (parameterizable) |
|
OCLOSURE |
closure implemented by an object |
Type integer is defined to be long, but it could be changed to int, for example. Type floating is defined to be double, but it could be changed to float.
The type() method of class Poly can be used to find out what type is wrapped within a given Poly. Example usage is:
switch( p.type() )
{
case INTEGER: .... handle integer ....
case FLOATING: .... handle floating ....
case LIST: .... handle list ....
default: .... handle others ....
}When the wrapped value is integer or floating, we may refer to the Poly as a number or numeric Poly. When the wrapped value is a Polylist or Polyarray, we may refer to the Poly as an aggregate. When the wrapped value is a function (of one argument) or a type which can serve as a function, such as a list, array, or Fclosure, we call the Poly applicable.
Once the type of a wrapped value is determined, the value itself may be extracted by type casting. The following casting operators are available:
operator integer() const; operator floating() const; operator char*() const; operator char() const; operator Polylist() const; operator Polyarray() const; operator Seed() const; operator Fclosure() const; operator Sclosure() const; operator Oclosure() const; operator Function1() const; operator Function2() const; operator istream&() const; operator error() const;
To use them, one would use either of the following forms:
C++ style cast:
integer(p)
C style cast:
(integer)p
Implicit casting is also possible:
integer i = p;
to recover the integer value from p.
Impossible conversions will result in a run-time error. For example, if you code
integer i = p;
and p happens not to contain a number or character, there is no way to proceed. A run-time error message will be generated. Depending on the environment, a segmentation fault may be forced as well. This will permit using the debugger to trace back to the source of the error.
Polys are created by using the constructor Poly on argument values to be wrapped. For example,
Poly p = Poly(5);
will create p as a Poly containing the integer 5. Implicit casting can also be used, as in:
Poly p = 5;
As in C++ in general, the constructor form
Poly p(5);
is equivalent to the above. An assignment such as
p = 3.14;
will change the wrapped value to a floating type.
Polylist is the type of lists supported by the Polya library. As with Poly, Polylist is a C++ class. Most lists are not treated as objects, but rather constructed dynamically and re-built rather than modified in typical functional programming style.
The simplest list constructor (actually a pseudo-constructor, since it does not qualify as a C++ constructor for class Polylist) is called list. This is an overloaded function which is defined for up to twelve arguments. Examples of lists created this way are:
list(1, 2, 3) list of integers
list("alpha", "beta", "gamma") list of strings
list(99.1, 99.2, 99.3, 99.4) list of floating values
list('a', 'e', 'i', 'o', 'u') list of characters
list(1, "beta", 99.3, 'o') mixed list
list(list(1), list(2, 3), list(4, 5, 6)) list of lists
list() empty listThe above expressions just define list values. To declare a Polylist with a specific initial value, one could use the form:
Polylist L = list(1, 2, 3);
The empty or null polylist may be designated by the constant nil. NIL may also be used. In addition, any Polylist not otherwise initialized is implicitly initialized to the empty list.
The following functions are available for dealing with a Polylist L. In some cases, object-oriented, as well as functional, syntax may be used.
cons(P, L)
isEmpty(L) or L.isEmpty()
nonEmpty(L)or L.nonEmpty()
first(L) or L.first()
rest(L) or L.rest()
second(L), third(L), ...., tenth(L)
length(L)or L.length()
L[i]
member(P, L) or L.member(P)
append(L, M) or L.append(M)
reverse(L)or L.reverse()
L.prefix(N)
sort(L) or L.sort()
implode(L) or L.implode()
==, !=, <, >, <=, >= operators
= operator
range(m, n)
range(m, n, i)
from(m)
from(m, i)
map(F, L) or L.map(F)
L.mappend(F)
Polylist::make(F, N)
keep(P, L) or P.keep(L)
drop(P, L) or P.drop(L)
find(P, L) or L.find(P)
L.assoc(P)
L.foldl(F, Unit)
F(....F(F(Unit, x1), x2), ...., xn)
L.foldr(F, Unit)
F(x1 , F(x2, ...., F(xn, Unit)....))
L.scanl(F, Unit)
(F(Unit, x1) F(F(Unit, x1), x2) .... F(x1 , F(x2, ...., F(xn, Unit)....)) )
The list L can be infinite. The result always has the same length as L.
L.scanr(F, Unit)
( F(x1 , F(x2, ...., F(xn, Unit)....)) F(x2, ...., F(xn, Unit)....) .... F(xn, Unit) )
The list L cannot be infinite. The result always has the same length as L.
Polylist::inchars(Istream)
Polylist::random(int low, int high)
Example:
Polylist X = list(1, 2, 3); X.rest().rest().rawRest() = list(4, 5, 6);
The following methods are available for dealing with a Polyarray A.
A.length()
A.resize(long)
A[i]
A.reverse()
A.map(F)
Polyarray::make(F, N)
==, !=, <
= operator
A.deepCopy()
The following deal with polys in general:
ostream << P (where ostream is some ostream such as cout)
istream >> P (where istream is some istream such as cout)
P == Q
P != Q
P < Q, P > Q, P <= Q, P >= Q
+, *, -, and /
cat(P, Q)
P.explode(), explode(P)
makeFloating(P)
makeInteger(P)
makeString(P)
P.deepCopy()
P.deepType()
P.force()
P.type()
These functions recognize common types of polys:
isList(P)
isFloating(P)
isInteger(P)
isNumeric(P)
isString(P)
isChar(P)
Polya defines a type Function1 as follows:
typedef Poly (*Function1)(Poly);
which means that a Function1 is any function of one Poly argument which returns a Poly. Such a function can itself be wrapped as a Poly. For example, one could then make a Polylist or Polyarray having such functions as elements.
Certain of the methods in Polya, for example map, expect functions as arguments. Here is an example of defining such a function, then using it, to produce a list of squares.
Poly square(Poly x)
{
return x*x;
}
....
cout << range(1, 10).map(square) << endl;
Here method map actually takes a Poly as its argument type, and the Function square is cast to a Poly implicitly.
A related type which may also be wraped is Function2 defined as:
typedef Poly (*Function)(Poly, Poly);
i.e. a function of two Poly arguments returning a Poly.
Rather than extracting a Function (of one argument) from a Poly argument and then applying it, consider coding to apply the Poly directly. The advantage of this style is that there are several different wrapped types which work as functions:
Function1 Fclosure Array List
These are discussed next.
Every array and every list may be viewed as a partial function from valid indices to values. If an array or list is wrapped in a Poly, then the Poly can be applied as a function. So there are at least three wrapped types which can be so applied: functions as defined above, Polyarrays, and Polylists. For example, the following statement
cout << list(5, 3, 1).map(list(2, 3, 5, 7, 11, 13)) << endl;
produces the list
(13 7 3)
That is, the list (2 3 5 7 11 13) is treated as a function and applied against 5, 3, and 1 in turn. Applying to 5 selects the sixth element of the list (indexing starts at 0) which is 13, applying to 3 selects the fourth element which is 7, and applying to 1 selects the second element which is 3.
A similar result, the array
[13 7 3]
is produced if an array rather than a list is applied.
Note: It is not advisable to use repeated indexing L[i] in a for loop to get list elements, as in:
for( int i = 0; i < L.length(); i++ )
.... use L[i] ....
since i elements need to be traversed on each access to get to the ith element. (Also, the evaluation of length() is done on each step.) It is better to use "list peeling" style:
for( Polylist M = L; M.nonEmpty(); M = M.rest() )
.... use M.first() ....
An Fclosure (function closure) is another type of datum which can be wrapped in a Poly. An Fclosure can be applied as a function. However, the Fclosure also carries some data along with it. A Poly Fclosure is constructed as:
Fclosure(Function2, Poly)
where type Function2 is a function of two arguments, both Polys. The first argument to the Function2 is the data in the Fclosure, sometimes called the environment part of the Fclosure. The second argument to the Function2 is the actual argument to which the Fclosure is applied.
As an example, consider using map to scale a list of numbers. We wish to have the scaling factor as an argument to the function argument of map thus:
L.map(scale(2)) L.map(scale(3))
These expressions mean return a new list obtained by scaling the elements of L by factors of 2 or 3 respectively. In order to accomplish this, we have scale return an Fclosure. The environment part of the Fclosure carries the scale factor.
Poly scaler(Poly k, Poly x) // a Function2
{
return k*x;
}
Poly scale(Poly k) // scaling function
{
return Fclosure(scaler, k);
}When the Fclosure is applied, the scale factor becomes the first argument to the Function2, in this case named scaler.
An Sclosure (symbolic closure) is a closure which is intended to be evaluated symbolically by an interpreter. When the closure is constructed, the interpreter is given as an argument. An example of an interpreter may be found in the files eva.H and eva.C.
An Oclosure (object closure) is a closure which is defined by a C++ object rather than a C++ function. Such an object must be a member of the class Applicable which is defined in polya.H. This is done by extending the class Applicable to a class of interest. The operator() applied to a Poly and returning a Poly defines the application of an Oclosure. The constructor for the class may take arguments which have values which are used when the Oclosure is applied. (In the Java version of Polya, Fclosures are not available so Oclosures must be used to achieve higher-order functions.)
Although it takes a little more syntactic effort than in a functional language, "infinite" lists can be created in Polya. A simple way of summarizing an infinite list L is to say that L[i] exists for any non-negative integer i.
Several pre-defined methods create infinite lists. The simplest of them is Polylist::from.
from(N) creates the infinite list (N N+1 N+2 ...)
Consider the following steps:
Polylist L = from(0); // L is an infinite list
This doesn't generate all the elements of L immediately; instead they will be generated as they are demanded. For example,
cout << L[100] << endl;
would cause elements [0, ...., 100] to be generated and 100 would be produced as a result. Because the list is evaluated lazily however, subsequent access of L[100] would not regenerate these elements; they would stay in place. Access of L[200] would generate the next 100 elements, and so on. The list would stay intact until L is possibly reassigned, at which time the original space would be reclaimed.
When it makes sense, most of the list methods work on infinite lists. Consider the method map, for example. If we define square as
Poly square(Poly x)
{
return x*x;
}then
L.map(square) would give the infinite list of squares,
(0 1 4 9 16 25 ...)
and, as with L itself, these elements would be produced on demand.
Constructing your own methods for infinite lists requires a little care. The key construct for creating an infinite list is the Seed Poly. A Seed is an abstraction for creating a Poly (called the resultant) through computation specified by a function and an argument to that function. Once the resultant is created (called growing the seed), it effectively replaces the seed itself, so that the creating computation is only done once. Other terms for seed or similar abstractions which have appeared in the literature include future, recipe, and suspension.
To create a seed, use the constructor which has the form
seed(Generator, Argument)
Here Generator has the type
Poly (*Generator)(Poly)
(i.e. a generator is a function taking a Poly argument and returning a Poly) and Argument has type Poly. When the value of a seed is demanded, the computation prescribed by the function application
Generator(Argument)
is used to compute the resultant. To make this clearer, we illustrate with the implementation of method from. The generator in this case is called fromGen.
Poly fromGen(Poly m)
{
return cons(m, seed(fromGen, m+1));
}
Polylist Polylist::from(Poly m)
{
return fromGen(m);
}We see that the value returned by from is that of fromGen applied to the argument m. This is immediately evaluated and returns a list beginning with m as its first and seed(fromGen, m+1) as its rest. The latter creates a seed which remains unevaluated until its value is demanded. At that point, the resultant is computed as
fromGen(m+1)
which yields the list beginning with the value of m+1 and followed by
seed(fromGen, m+2).
Thus we never evaluate more of the list than is needed.
In some cases, more than one value is necessary to generate the next element of the list. Since a Generator is defined to take just one argument, these values must be packaged up as an aggregate Poly which is used as the argument to Generator. A Polyarray is recommended for this purpose. In many cases, the Polyarray can be reused at each generation cycle, by assigning to one or more elements of the array. The user is encouraged to examine the source files for examples of this reuse technique.
The following files are copyrighted, but free use is permitted as long as such use is not for profit. There is absolutely no warranty of any form.
Please report any bugs to keller at cs dot hmc dot edu.