454,379 Members | 1,602 Online
Need help? Post your question and get tips & solutions from a community of 454,379 IT Pros & Developers. It's quick & easy.

# SICP playfulness in C?

 P: n/a 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 #include /* 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 May 30 '07 #1
7 Replies

 P: n/a Wilson wrote: 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 #include /* 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. May 30 '07 #2

 P: n/a In article <11**********************@q75g2000hsh.googlegroups .com> Wilson ... or is mirroring the LISP way just not do-able in C?I can't find a way of representing my pairs as functionswithout 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.) -- In-Real-Life: Chris Torek, Wind River Systems Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603 email: forget about it http://web.torek.net/torek/index.html Reading email is like searching for food in the garbage, thanks to spammers. Jun 3 '07 #3

 P: n/a Chris Torek San Diego Supercomputer Center <* "We must do something. This is something. Therefore, we must do this." -- Antony Jay and Jonathan Lynn, "Yes Minister" Jun 3 '07 #4

 P: n/a This might interest you: http://www.ddj.com/dept/cpp/199900573 -- Roland Pibinger "The best software is simple, elegant, and full of drama" - Grady Booch Jun 3 '07 #5

 P: n/a .... 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 :D Regards, Paul Jun 16 '07 #6

 P: n/a Wilson wrote: > ... 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 :D Without quotes this is totally incomprehensible. Usenet articles need to be complete in themselves. -- cbfalconer at maineline dot net -- Posted via a free Usenet account from http://www.teranews.com Jun 16 '07 #7

 P: n/a 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 :D Without quotes this is totally incomprehensible. Usenet articles need to be complete in themselves. Thanks for the advice. Regards, Wilson Jun 17 '07 #8

### This discussion thread is closed

Replies have been disabled for this discussion.