SICP playfulness in C?

Discussion in 'C Programming' started by Wilson, May 30, 2007.

  1. Wilson

    Wilson Guest

    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
     
    Wilson, May 30, 2007
    #1
    1. Advertising

  2. 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.
     
    Laurent Deniau, May 30, 2007
    #2
    1. Advertising

  3. Wilson

    Chris Torek Guest

    In article <>
    Wilson <> 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
    email: forget about it http://web.torek.net/torek/index.html
    Reading email is like searching for food in the garbage, thanks to spammers.
     
    Chris Torek, Jun 3, 2007
    #3
  4. Chris Torek <> 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) <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"
     
    Keith Thompson, Jun 3, 2007
    #4
  5. Roland Pibinger, Jun 3, 2007
    #5
  6. Wilson

    Wilson Guest

    .... 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
     
    Wilson, Jun 16, 2007
    #6
  7. Wilson

    CBFalconer Guest

    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.

    --
    <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
     
    CBFalconer, Jun 16, 2007
    #7
  8. Wilson

    Wilson Guest


    > > 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
     
    Wilson, Jun 17, 2007
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. legere

    SICP in Python, redux

    legere, Jun 29, 2003, in forum: Python
    Replies:
    0
    Views:
    1,790
    legere
    Jun 29, 2003
Loading...

Share This Page