This documentation is under construction.

The Polya C++ Library

Version 2.0

Robert M. Keller

keller@cs.hmc.edu

Harvey Mudd College

27 July 1997

Keywords: functional programming, C++, polymorphism, lazy evaluation, object-oriented programming, pointer-free programming, higher-order functions, infinite lists, closures, rapid protytyping

Table of Contents:

 

Introduction

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.

 

Formatting

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.

 

Wrappers

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.

 

Extraction of Values

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.

 

Creating Polys

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.

 

Polylists

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 list

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

 

Polylist Functions and Methods

The following functions are available for dealing with a Polylist L. In some cases, object-oriented, as well as functional, syntax may be used.

list(P1, P2, ...., Pn)
For n = 0, 1, ...., 12, these functions create lists given the elements of the list.
 

cons(P, L)

creates a list beginning with the Poly P and followed by the items in Polylist L. These are open lists, in the sense that the contents of the new and old list are shared; The contents of L are not copied.
 

isEmpty(L) or L.isEmpty()

returns 1 if argument is the empty list, otherwise returns 0.
 

nonEmpty(L)or L.nonEmpty()

returns 1 if argument is not the empty list, otherwise returns 0.
 

first(L) or L.first()

returns the first Poly in a non-empty Polylist L. (Make sure L.nonEmpty() before calling first.)
 

rest(L) or L.rest()

returns the Polylist of remaining Polys skipping the first Poly. (Make sure L.nonEmpty() before calling rest.)
 

second(L), third(L), ...., tenth(L)

returns respective elements of a Polylist
 

length(L)or L.length()

returns the length of Polylist L
 

L[i]

returns reference to i-th component of L (i = 0, 1, 2, 3, ...). Since this is a reference, L[i] can be used as an lvalue, i.e. L[i] = ....;
 

member(P, L) or L.member(P)

returns 1 if Poly P is a member of Polylist L, and 0 otherwise
 

append(L, M) or L.append(M)

returns the result of appending M to L non-destructively.
 

reverse(L)or L.reverse()

returns the result of reversing list L non-destructively.
 

L.prefix(N)

returns the length N prefix of L (or all of L if N exceeds the length of L)
 

sort(L) or L.sort()

returns the result of sorting list L non-destructively according to poly ordering
 

implode(L) or L.implode()

if L is a list of characters, returns the corresponding string (as a Poly)
 

==, !=, <, >, <=, >= operators

These operators all work on lists, as well as on other data types. Two lists are == if they have the same number of elements and the elements are pairwise equal. Two lists are != if they are not ==. L < M means that L has no more elements than M, and the elements of L are pairwise less than the corresponding elements of M. The meaning of the other comparison operators is similar.
 

= operator

This designates assignment to a list. In assignment, the original and the copy share elements. Use deepCopy() to get a copy without sharing.
 

range(m, n)

m and n are numeric Polys. Creates the list (m m+1 .... n).
 

range(m, n, i)

m, n, and i are numeric Polys. Creates the list (m m+i m+2i .... n). i can be negative, in which case the list is descending.
 

from(m)

m is a numeric Poly. Creates the infinite list (m m+1 ...).
 

from(m, i)

m and i are numeric Polys. Creates the infinite list (m m+i m+2i ....)
 

map(F, L) or L.map(F)

if F is a function taking a Poly into a Poly, and L is a Polylist, map(F, L) is the list resulting from applying F to each element of L. L can be an infinite list.
 

L.mappend(F)

if F is a function taking a Poly into a Polylist, and L is a Polylist, map(F, L) is the list resulting from applying F to each element of L and appending thos results together. L can be an infinite list.
 

Polylist::make(F, N)

A list of length N is created, (F(0) F(1) .... F(N-1)).
 

keep(P, L) or P.keep(L)

P is a predicate in the form of a function Poly. A new list is constructed which is like L except that only elements satisfying P are kept.
 

drop(P, L) or P.drop(L)

P is a predicate in the form of a function Poly. A new list is constructed which is like L except that elements satisfying P are dropped.
 

find(P, L) or L.find(P)

P is a predicate in the form of a function Poly. The suffix of L beginning with the first element satisfying P is returned. If there is no such element, then the empty list is returned.
 

L.assoc(P)

L is assumed to be a list of lists. L is searched to find a list, the first element of which is equal to Poly P. If such an element is found, the entire element is returned. If not, the empty list is returned.
 

L.foldl(F, Unit)

(fold-left) F is a two-argument function and Unit is a unit for that function. If L has the form of a list [x1, x2, ...., xn], then the result has the form

F(....F(F(Unit, x1), x2), ...., xn)

 

L.foldr(F, Unit)

(fold-right) F is a two-argument function and Unit is a unit for that function. If L has the form [x1, x2, ...., xn], then the result has the form

F(x1 , F(x2, ...., F(xn, Unit)....))

 

L.scanl(F, Unit)

(scan-left) F is a two-argument function and Unit is a unit for that function. If L has the form [x1, x2, ...., xn], then the result is a list of the form

(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)

(scan-right) F is a two-argument function and Unit is a unit for that function. If L has the form (x1 x2 .... xn), then the result is a list of the form

( 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)

reads the characters from an istream returning them in the form of a list. If the stream is non-terminating, the list will be infinite.
 

Polylist::random(int low, int high)

generates an infinite stream of random integers between low and high inclusive.

 

L.rawRest()
is intended for expert use. It returns a reference to the rest of the list in "raw" form. This is a reference to a Poly which can be overwritten. Doing so modifies the structure of the list. rawRest() can also be used in optimizing lazy evaluation methods by checking whether the rest of a list is a Seed or not, and doing something special if it is.

Example:

Polylist X = list(1, 2, 3);
X.rest().rest().rawRest() = list(4, 5, 6);
Here X.rest().rest() is the list [3]. Setting rawRest() of this list to (4 5 6) is equivalent to tacking list (4 5 6) onto the end of X.
 

Polyarray Functions and Methods

The following methods are available for dealing with a Polyarray A.

array(x1, x2, ...., xn)
For n = 0, 1, ...., 12, these functions create Polyarrays [x1 x2 .... xn] given the elements of the array.
 

A.length()

returns the length of the array.
 

A.resize(long)

sets the length of the array. If the new length is shorter than the old, trailing elements are discarded; if newer than the old, the array is padded by nil elements.
 

A[i]

returns reference to i-th component of A (i = 0, 1, 2, 3, ...). Since this is a reference, A[i] can be used as an lvalue, i.e. A[i] = ....;
 
A.accomodate(long)
makes sure that the array can accomodate the given argument as an index. If not, the size is increased using resize().
 
A.sort()
sorts the array in place according to poly ordering.
 

A.reverse()

reverses the array in place.
 

A.map(F)

analogous to L.map(F) except for arrays instead of lists. A new array is created.
 

Polyarray::make(F, N)

An array of length N is created [F(0) F(1) .... F(N-1)]. This technique is sometimes called array comprehension.
 

==, !=, <

tests two arrays for equality or inequality analogous to the tests of lists.
 

= operator

Assigning an array to an array variable does not copy the array. The target and the source simply share the same elements. Use method deepCopy() to make a new array without sharing.
 

A.deepCopy()

means that A is copied by making a deep copy of each elements in A.

 

Poly Functions and Methods

The following deal with polys in general:

P.type()
returns the type of P. If P is a Seed, the seed is grown first.
 

ostream << P (where ostream is some ostream such as cout)

Outputs a poly as an "S expression"
 

istream >> P (where istream is some istream such as cout)

Inputs a poly from an "S expression"
 

P == Q

Polys can be compared for equality.
 

P != Q

Polys can be compared for inequality.
 

P < Q, P > Q, P <= Q, P >= Q

Polys can be compared for an ordering , where reasonable. The "lexicographic" ordering is used for aggregates (lists and arrays). Atoms are defined to be < aggregates. For example,
  • Two numbers are < in the usual sense.
  • Two strings are < in alphabetic ordering.
  • Every number is < every string.
  • Every string is < every list.
  • Two Polylists or Polyarrays are < as defined in the section on Polylist Methods.
add(P, Q), multiply(P, Q), subtract(P, Q), divide(P, Q)
P and Q should wrap numbers. These functions return the result of the corresponding operation. In the case of add, if one of the arguments is a string, cat is used. In the case of both arguments being arithmetic, the result will be integer if, and only if, both arguments are integer. Otherwise the result will be floating. In particular, the result of integer division will always truncate the fraction.
 

+, *, -, and /

are the infix forms of add, multiply, subtract, and divide. When + is used on Strings, it means concatenation.
 

cat(P, Q)

Concatenates the string representation of P with that of Q.
 

P.explode(), explode(P)

If P contains a character string, explode(P) is a list of those characters. If P is something else, it will be first converted to a character string, then the string will be exploded.
 

makeFloating(P)

returns a Poly having a floating value which is equivalent to the argument. This is similar to casting the argument as a floating, except the result is re-wrapped as a Poly.
 

makeInteger(P)

analogous to makeFloating, except an integer value is wrapped.
 

makeString(P)

analogous to makeFloating, except a char* value is wrapped.
 

P.deepCopy()

means that P is copied by making a deep copy of each elements in the case P is an aggregate. In deep copies, no values are shared between the original and the copy.
 

P.deepType()

returns a list with the same structure as P, in which the elements have been replaced with strings indicating the type of each.
 

P.force()

fully expands P, in the event that there are any Seed components anywhere inside P.
 

P.type()

returns the type of P. If P is a Seed, the seed is not grown first, but rather SEED is returned. This is primarily for internal use.

 

Recognizers

These functions recognize common types of polys:

atomic(P)
returns 1 if argument is not an aggregate (Polylist or Polyarray).
 

isList(P)

returns 1 if its argument Poly contains a Polylist, otherwise 0.
 

isFloating(P)

returns 1 if P contains a floating value, otherwise returns 0.
 

isInteger(P)

returns 1 if P contains an integer value, otherwise returns 0.
 

isNumeric(P)

returns 1 if P contains a numeric value (integer or floating).
 

isString(P)

returns 1 if P contains a string.
 

isChar(P)

returns 1 if P contains a char.

 

Function Wrappers

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.

 

Arrays and Lists as Functions

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() ....

Fclosures

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.

Sclosures

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.

 

Oclosures

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

 

Infinite Lists and Lazy Evaluation

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.

 

Seeds and Generators

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.

 

Source Files for Polya

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.

 

Other Relevant Links