Functional Programming with the simple object system

[M Joshua Ryan]

In the previous post, "Designing a simple object system ..." I presented
a simple definition of a tag union data structure and associated
functions for manipulating simple dynamically typed objects in C.

But we need one more layer of support before the Parser Combinators can
be realized. This /secret sauce/ includes environments (enabling us to
recognizably simulate closures), map and join (constituents of the
'bind' function), and some other stuff.


For environments, I went with the simplest possible data structure given
the fact that I already have lists: association lists. These are lists
of (key value) pairs and can be created with the function 'env'.


list env( list tail, int n, ... );


'env' is used when creating a function object. By adding new pairs onto
an existing *tail* list, functions may inherit values from parent
scopes. So we have dynamic scoping, but quite a bit of manual control.

Within the function of a function object, these values can be queried
with the 'assoc' function.

object assoc( object key, list alist );

The key can be any type that the 'eq' function can deal with.

boolean eq( object a, object b );

It can compare objects of any type for equality. But some special care
has been afforded to make the SYMBOL object a good choice for a key,
although it does mean an allocation for every use.

Another function occasionally used with environments is 'copy'. In one
or two places, an enviroment needs to be merged with another. So we
make a copy of one before chaining the new thing on to it.

list copy( list a );


Map and Join are importanct components of the 'bind' function which is
very important for the Parser Combinators.

Map takes a function object and a list and calls the function on each
element of the list, returning a new list of the results. The extra
complication here in the current case is that 'map' must be careful
about suspensions, the lazy values which need a function call to yield
actual values.

list map( oper f, list o );

Join does another important job for 'bind' but it's a little more
tedious to explain. The Parser Combinators return zero or more
pairs of (result, remaining-input). So when we call 'bind' to
attach a function to the results, the function gets called with
the 'map' obviously. But since this function may itself return
multiple results, 'bind' must also merge all the little lists
together which the separate function calls may have produced.

Does that make sense? So 'join' does this merging together of
the lists returned by all the mapped functions.

list join( list o );

Join also has to be careful with suspensions.


And two more miscellaneous functions. These both do a 'fold' operation
over a list. Except one of them works on an array. And the one the
does take a list may expect a *wonky* list with extra indirections
in it that must be explored.

object collapse( fBinOper *f, list o );
object reduce( fBinOper *f, int n, object *po );

'collapse' is used by the regex builder to create parsers for
sequences and alternations. Whereas 'reduce' is used by macros
to extend binary combinators like 'seq' and 'plus' to take more
than 2 arguments.


And that finally is all the support code needed before we can
build the Parser Combinators. This is also the code that needed
the most attention during debugging. It's still in a pretty
sorry state, but can be seen in the usual places:

https://github.com/luser-dr00g/pcomb/blob/d02f76a18a7a37fed847310af07d19e8d4b64c21/pc9fp.c
https://github.com/luser-dr00g/pcomb/archive/d02f76a18a7a37fed847310af07d19e8d4b64c21.zip


I still feel very haphazard in my use of suspensions. Perhaps
more old papers will help....

Any questions?