[Nickle]"purely" functional nickle (was: Recursive datatypes)

[Carl Worth]

On Jul 24, Keith Packard wrote:
 > The way around this type problem is to use a type which can be represented
 > with more than one kind of value.
 > 
 > To avoid pure polymorphism, you can use a union type instead:
 > 
 > 	if (l.ref == listend) printf ("yes\n");

I suppose that was intended to be:

	if (l.ref == (listref.end) <>) printf ("yes\n");

which is indeed a rather awkward syntax.

Other than the syntax, I do like the other characteristics of using a
union for this purpose.

I ended up just using poly. I made a global struct value named nil as
a placeholder for list termination. When the new poly zero is in
place, I can get rid of my nil.

Using poly is actually the right thing for what I'm doing, (which
involves implementing a purely polymorphic language in nickle). I've
been trying is a little experiment in "pure functional" programming in
nickle. I've been going through a 1984 paper by John Hughes, "Why
Functional Programming Matters"[1], implementing each example.

With a small module defining cons, nil, and functional versions of all
the operators it was a simple matter to directly implement the first
set of examples:

	/* fp.5c */
	namespace FP {
	
	    public typedef struct {
	        poly car;
	        poly cdr;
	    } cons_cell;
	
	    public global cons_cell nil = { car = 0, cdr = 0 };
	
	    public cons_cell cons(car, cdr) {
	        return (cons_cell){car = car, cdr = cdr};
	    }
	
	    public poly add(a, b) {
	        return a + b;
	    }
	
	    public poly mult(a, b) {
	        return a * b;
	    }
	
	    /* etc. for all other nickle operators */
	}
	
	/* fptest.5c */
	/* load "fp.5c";  *** Commented out for your cut-and-paste pleasure */
	import FP;

	poly reduce(poly(poly,poly) binop, poly basis, cons_cell list)
	{
	    if (list == nil) {
	        return basis;
	    } else {
	        return binop(list.car, reduce(binop, basis, list.cdr));
	    }
	}

	poly sum(cons_cell list) {
	    return reduce(add, 0, list);
	}

	poly product(cons_cell list) {
	    return reduce(mult, 1, list);
	}

	cons_cell append(cons_cell a, cons_cell b) {
	    return reduce(cons, b, a);
	}

	l1 = cons(1, cons(2, nil));
	l2 = cons(3, cons(4, nil));
	list = append(l1, l2);
	
	printf("sum is %d\n", sum(list));
	printf("product is %d\n", product(list));

That's all very straightforward.

The next example revealed something interesting. He starts with a
single function to double each element in a list, then progressively
decomposes it in order to arrive at a definition for map. I was able
to implement the version with map like so:

	poly(poly,poly) compose(poly(poly,poly) f, poly(poly) g) {
	    poly composite(car, cdr) {
		return f(g(car), cdr);
	    }
	    return composite;
	}

	poly map(poly(poly) f, cons_cell list) {
	    return reduce(compose(cons, f), nil, list);
	}

	poly double(arg) {
	    return mult(2, arg);
	}

	cons_cell doubleall(list) {
	    return map(double, list);
	}

	list2 = doubleall(list);

This works, but the definition of compose isn't very satisfying. This
compose is restricted to accepting one function with two arguments and
a second with one argument. A more powerful compose would be able to
accept functions with any number of arguments and just do the Right
Thing. That is, if f accepts M arguments and g accepts N arguments,
then compose would return a function accepting N + (M-1) arguments
that would return f(g(arg1, ..., argN), argN+1, ..., argN+M-1).

I don't suppose there would be any way to write such a beast in
nickle?

Oh, and in a similar vein, is there any way to call one function with
a variable length argument list from another that also has a variable
length argument list. Something like:

int foo(int args ...)
{
    /* ... */
    return 0;
}

int bar(int args ...)
{
    return foo(args); /* How to make something like this work? */
}

Would we want some new bit of syntax that turns an array into a list
of arguments for a function call?

By the way, thanks for nickle. I'm having a lot of fun poking and
prodding at it like this.

-Carl

[1] http://www.math.chalmers.se/~rjmh/Papers/whyfp.html

-- 
Carl Worth                                        
USC Information Sciences Institute                 cworth@east.isi.edu
3811 N. Fairfax Dr. #200, Arlington VA 22203		  703-812-3725