1

I am trying to implement basic cons, car and cdr of SCHEME in C. I have made a simple program that allows me to cons two integers as shown in the main program. However, I want my program to be able to cons a 'consed object' with a digit as well as cons a 'consed object' with another 'consed object' as shows below:

  • (cons 2 3)
  • (cons 2 (cons 2 3))
  • (cons (cons 2 3) (cons 2 3))

Since the limitation arises because the data in the struct is of type int, is it possible to have a variable accept multiple data types in C? If yes, how? If not, is there another way to deal with this issue? Here is my code:

#include <stdio.h> #include <string.h> typedef struct cons_object { int data; struct node* next; } cons_object; cons_object* cons(int x, int y ) { cons_object* car = NULL; cons_object* cdr = NULL; car = malloc(sizeof(struct cons_object)); cdr = malloc(sizeof(struct cons_object)); car->data = x; car->next = cdr; cdr->data = y; cdr->next = NULL; return car; /*returns the pointer car*/ } int car(cons_object* list) /*takes in a consed object*/ { cons_object* car = list; int y; y = car->data; return y; } int cdr(cons_object* list) { cons_object* cdr = list; cdr = cdr->next; int z; z= cdr->data; return z; } int main () { int y = car (cons(33,42)); printf("%d\n",y); int z = cdr (cons(3,4)); printf("%d\n",z); return 0; }
Improve this question
1
  • 4
    look up union Commented Jul 17, 2013 at 15:09

2 Answers 2

Reset to default
9

Further to ratchet freak's comment, look up discriminated union, or tagged union.

You can make your data type a void *, but you also need to track what it really points to. That is, at some point you need to figure out if it's an integer or a double or another list.

The tagged union itself might look something like this:

#include <stdlib.h> #include <assert.h> enum TypeTag { NoType, CharType, IntType, DoubleType, ConsType }; union Value { char c; int i; double d; void *p; }; struct TaggedType { enum TypeTag type; union Value value; };

and the cons code can use it - without worrying about what type is really inside the TaggedType structure - like this:

struct ConsNode { struct TaggedType value; struct ConsNode *next; }; struct ConsNode *cons(struct TaggedType value, struct ConsNode *next) { struct ConsNode *head = malloc(sizeof *head); head->value = value; head->next = next; return head; } struct TaggedType *car(struct ConsNode *head) { return &head->value; } struct ConsNode *cdr(struct ConsNode *head) { return head->next; }

Then all you need is the boxing/unboxing code to work with actual concrete types:

struct TaggedType mkint(int i) { struct TaggedType value = { IntType, {.i=i} }; return value; } struct TaggedType mkdbl(double d) { struct TaggedType value = { DoubleType, {.d=d} }; return value; } int toint(struct TaggedType *data) { assert(data->type == IntType); return data->value.i; } double todbl(struct TaggedType *data) { assert(data->type == DoubleType); return data->value.d; } int main () { struct ConsNode *list = cons(mkint(33), cons(mkint(42), NULL)); int y = toint(car(list)); assert(y == 33); assert(toint(car(cdr(list))) == 42); return y; }

Note that most list operations don't know or care about the type stored in each node - this only becomes important where you do something with it.

Improve this answer
2

Make it a void *. Then it can point to anything. Memory management is up to you.

This will result in not having any type checking. If you go down this path, see http://libcello.org/ for what is possible. (But if you want to go down this path, why are you writing in C?)

Improve this answer
8
  • 1
    void* to accommodate generic types is a very normal use of C - I disagree with "why are you writing in C". Commented Jul 17, 2013 at 15:19
  • @JustinMeiners I think he just means, if you're trying to write in a LISP style, why don't you use a LISP, which is a totally reasonable question... Commented Jul 17, 2013 at 15:27
  • 1
    But if you're trying to write LISP, starting with LISP isn't necessarily a helpful suggestion Commented Jul 17, 2013 at 15:29
  • @Useless I disagree. There is a long history of implementing Lisps in Lisp. For example SCIP is mostly about how to write Scheme in Scheme. This history goes back to the beginning - the very first implementation of Lisp was written in Lisp! (And then unexpectedly hand compiled to assembly. Quite a surprise to the team which hadn't finished designing the language.) Commented Jul 17, 2013 at 15:53
  • 1
    @btilly - that's fair, I think what I meant to say was if OP asked about implementing LISP in C, suggesting OP implements it in LISP instead isn't necessarily helpful. Commented Jul 17, 2013 at 16:38

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.