SICP playfulness in C?

[Wilson]

Hi all,

I recently came across the online video lectures of "The Structure and
Interpretation of Computer Programs". One of the examples, which I
found quite breath taking was their implementation of a pair system
(just two integers stored under one name) out of an anonymous
function.

They define a LISP function to create pairs (called cons), that
naturally takes two integers but returns a function which represents
the pair. They do this by constructing an anonymous function out of
the two parameters (using C style syntax):

cons (int a, int b) {
return lambda (int x) {
if (x==0) return a;
if (x==1) return b;
}
}

Where lambda is just saying "what follows is a function, but there's
no need to name it here". So we could write:

myPair = cons(12,15);

And myPair would then equate to:

myPair(int x) {
if (x==0) return 12;
if (x==1) return 15;
}

They then go on to define two functions to extract the two values,
each taking a function as a parameter and plugging in either 0 or 1:

/* Return the first value of the pair */
car(f){
return f(0);
}

/* Return the second value of the pair */
cdr(f){
return f(1);
}

They build a pair abstraction out of pure code, functional programming
exemplified! I found this very interesting because the system hides
the details of the myPair implementation, placing emphasis on the
interface of the pair object. All that is required of a pair is that
it returns the first value when passed 0, and the second value when
passed 1. The function could simply return the values like above, or
dive into an SQL database or retrieve the values over a network
connection or whatever, and it still behaves ostensibly like any other
pair.

I can imagine it being easily extensible in LISP (I don't know LISP at
all well). If pair represents a coordinate, then we could make 3D
coordinates by defining a function that takes a pair and returns a
function that again takes 1 argument, returning the 3rd coordinate if
the value is 2 or executing and returning the original pair function
with values of 0 or 1:

make3D(pair,int c) {
return lambda (int x) {
if (x==2) return c;
else return pair(x);
}
}

This new 3D point will still play nicely with 2D-aware existing code,
we just need a new function for extracting the 3rd coordinate, easy
enough.

Finally, pairs can have differing implementations but that are all
essentially functions, and thus can be grouped together as if they
were the same type in some sort of collection.

The system just seems to have an elegance about it. I've been thinking
about writing something like this in C, but having trouble getting my
head around it. The problem seems to be with associating the data with
the function: I find myself using structures with function pointers as
my pair implementation, and a malloc'd region to store the parameters
until execution. This is my code so far:

#include <stdio.h>
#include <stdlib.h>

/* Store data together with function pointer */
struct T_Pair {
int *data;
int (*fptr)(struct T_Pair *, int);
};

int simplePair(struct T_Pair *myData, int x){
return myData->data[x];
}

struct T_Pair cons(int a, int b) {
struct T_Pair pair;
pair.data = malloc(2*sizeof(int));
pair.data[0] = a;
pair.data[1] = b;
pair.fptr = simplePair;
return pair;
}

int car(struct T_Pair pair) {
return pair.fptr(&pair,0);
}

int cdr(struct T_Pair pair) {
return pair.fptr(&pair,1);
}

int main(void){
struct T_Pair test;
test = cons(5,4);
printf("First val = %d\n", car(test));
printf("Second val= %d\n", cdr(test));
}

It just doesn't feel right. Can anyone give me any ideas on how to
construct this more neatly, or is mirroring the LISP way just not do-
able in C? I can't find a way of representing my pairs as functions
without having some associated storage for it's values!

Any comments very welcome,
PA Wilson

 

[Laurent Deniau]

Hi all,

I recently came across the online video lectures of "The Structure and
Interpretation of Computer Programs". One of the examples, which I
found quite breath taking was their implementation of a pair system
(just two integers stored under one name) out of an anonymous
function.

They define a LISP function to create pairs (called cons), that
naturally takes two integers but returns a function which represents
the pair. They do this by constructing an anonymous function out of
the two parameters (using C style syntax):

cons (int a, int b) {
return lambda (int x) {
if (x==0) return a;
if (x==1) return b;
}
}

Where lambda is just saying "what follows is a function, but there's
no need to name it here". So we could write:

myPair = cons(12,15);

And myPair would then equate to:

myPair(int x) {
if (x==0) return 12;
if (x==1) return 15;
}

They then go on to define two functions to extract the two values,
each taking a function as a parameter and plugging in either 0 or 1:

/* Return the first value of the pair */
car(f){
return f(0);
}

/* Return the second value of the pair */
cdr(f){
return f(1);
}

They build a pair abstraction out of pure code, functional programming
exemplified! I found this very interesting because the system hides
the details of the myPair implementation, placing emphasis on the
interface of the pair object. All that is required of a pair is that
it returns the first value when passed 0, and the second value when
passed 1. The function could simply return the values like above, or
dive into an SQL database or retrieve the values over a network
connection or whatever, and it still behaves ostensibly like any other
pair.

I can imagine it being easily extensible in LISP (I don't know LISP at
all well). If pair represents a coordinate, then we could make 3D
coordinates by defining a function that takes a pair and returns a
function that again takes 1 argument, returning the 3rd coordinate if
the value is 2 or executing and returning the original pair function
with values of 0 or 1:

make3D(pair,int c) {
return lambda (int x) {
if (x==2) return c;
else return pair(x);
}
}

This new 3D point will still play nicely with 2D-aware existing code,
we just need a new function for extracting the 3rd coordinate, easy
enough.

Finally, pairs can have differing implementations but that are all
essentially functions, and thus can be grouped together as if they
were the same type in some sort of collection.

The system just seems to have an elegance about it. I've been thinking
about writing something like this in C, but having trouble getting my
head around it. The problem seems to be with associating the data with
the function: I find myself using structures with function pointers as
my pair implementation, and a malloc'd region to store the parameters
until execution. This is my code so far:

#include <stdio.h>
#include <stdlib.h>

/* Store data together with function pointer */
struct T_Pair {
int *data;
int (*fptr)(struct T_Pair *, int);
};

int simplePair(struct T_Pair *myData, int x){
return myData->data[x];
}

struct T_Pair cons(int a, int b) {
struct T_Pair pair;
pair.data = malloc(2*sizeof(int));
pair.data[0] = a;
pair.data[1] = b;
pair.fptr = simplePair;
return pair;
}

int car(struct T_Pair pair) {
return pair.fptr(&pair,0);
}

int cdr(struct T_Pair pair) {
return pair.fptr(&pair,1);
}

int main(void){
struct T_Pair test;
test = cons(5,4);
printf("First val = %d\n", car(test));
printf("Second val= %d\n", cdr(test));
}

It just doesn't feel right. Can anyone give me any ideas on how to
construct this more neatly, or is mirroring the LISP way just not do-
able in C? I can't find a way of representing my pairs as functions
without having some associated storage for it's values!

What you are trying to do is to implement two things in one: a tuple and
a closure. In Common Lisp, it is not that easy to use since calling a
closure requires a specific keyword (funcall). SCIP relies on Scheme
which does not require such specific keyword and process lambda as any
objects.

Since T_Pair is not implemented as a polymorphic object, it is useless
to store the fptr and *data can just be replace by data[2] in the
structure. One way to do it is to use an ADT for the tuple and another
one for the closure and provide the interface to manipulate them. You
will soon see that this approach is highly dynamic and requires a GC to
manage the memory, otherwise it will be a nightmare.

It's a long way to make this kind of features clean, simple, portable,
and efficient. Once you have it, you are half way to the FP side.

a+, ld.

 

[Chris Torek]

... or is mirroring the LISP way just not do-able in C?
I can't find a way of representing my pairs as functions
without having some associated storage for it's values!

That is because it cannot be done.

In Lisp (and Scheme), functions are "first class" objects,
essentially sharing the same properties as data. There is
a runtime cost for this that C refuses to pay, as it were.

In C, ordinary objects can be considered "first class". Arrays
behave a little oddly so they can be considered "second class"
(although some people might just shove them in with other data
types anyway). Both can be created at run time, using malloc()
to allocate space. The space allocated by malloc() has no name
(is "anonymous") but can be referred-to by saving the value
that malloc() returned:

int *p;

p = malloc(N * sizeof *p);
/* creates room for N "int"s */

Functions, however, simply cannot be created at all at runtime
(in C -- in Lisp, "lambda" creates a function at runtime.)

(There are tricks for amortizing out the runtime cost of lambda
binding, currying, and so on; and Lisp and Scheme compilers use
them, and C implementations can use them as well, so that you can
create functions dynamically -- often terribly clumsily -- using
some vendor-specific tricks on *some* C implementations. But the
point here is that C compiler vendors are not *obligated* to provide
such mechanisms. As a result, if you want to simulate Lisp in
Standard C, you *have* to use "some associated storage", so that
you can call a function whose code never changes throughout the
lifetime of the program, and have it interpret the data as needed.)

 

[Keith Thompson]

(There are tricks for amortizing out the runtime cost of lambda
binding, currying, and so on; and Lisp and Scheme compilers use
them, and C implementations can use them as well, so that you can
create functions dynamically -- often terribly clumsily -- using
some vendor-specific tricks on *some* C implementations. But the
point here is that C compiler vendors are not *obligated* to provide
such mechanisms. As a result, if you want to simulate Lisp in
Standard C, you *have* to use "some associated storage", so that
you can call a function whose code never changes throughout the
lifetime of the program, and have it interpret the data as needed.)

In other words, the way to simulate Lisp in standard C is to write a
Lisp interpreter in standard C.

 

[Roland Pibinger]

This might interest you: http://www.ddj.com/dept/cpp/199900573

 

[Wilson]

.... I'm interested to find out more.

I'm sure there's some documentation/books/papers or whatever on the
topic that'll be able to find.

Thanks for all your comments. They made for interesting reading and
have set my mind running

Regards,
Paul

 

[CBFalconer]

... I'm interested to find out more.

About what?

I'm sure there's some documentation/books/papers or whatever on
the topic that'll be able to find. Thanks for all your comments.
They made for interesting reading and have set my mind running

Without quotes this is totally incomprehensible. Usenet articles
need to be complete in themselves.

 

[Wilson]

Without quotes this is totally incomprehensible. Usenet articles
need to be complete in themselves.

Thanks for the advice.

Regards,
Wilson