Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C Programming (http://www.velocityreviews.com/forums/f42-c-programming.html)
-   -   SICP playfulness in C? (http://www.velocityreviews.com/forums/t510562-sicp-playfulness-in-c.html)

 Wilson 05-30-2007 11:06 AM

SICP playfulness in C?

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!

PA Wilson

 Laurent Deniau 05-30-2007 12:41 PM

Re: SICP playfulness in C?

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 <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 06-03-2007 07:56 AM

Re: SICP playfulness in C?

Wilson <PaulAlexWilson@gmail.com> wrote:
>... 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.)
--
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
Reading email is like searching for food in the garbage, thanks to spammers.

 Keith Thompson 06-03-2007 08:12 PM

Re: SICP playfulness in C?

Chris Torek <nospam@torek.net> writes:
[...]
> (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.

--
Keith Thompson (The_Other_Keith) kst-u@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

 Roland Pibinger 06-03-2007 10:10 PM

Re: SICP playfulness in C?

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

 Wilson 06-16-2007 02:24 PM

Re: SICP playfulness in C?

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

have set my mind running :D

Regards,
Paul

 CBFalconer 06-16-2007 04:51 PM

Re: SICP playfulness in C?

Wilson wrote:
>
> ... 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

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

--
<http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>
<http://www.securityfocus.com/columnists/423>
<http://www.aaxnet.com/editor/edit043.html>
cbfalconer at maineline dot net

--
Posted via a free Usenet account from http://www.teranews.com

 Wilson 06-17-2007 11:38 AM

Re: SICP playfulness in C?

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