current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free.
up vote 1 down vote favorite

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;

}
share|improve this question
4  
look up union –  ratchet freak Jul 17 '13 at 15:09

2 Answers 2

up vote 7 down vote accepted

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.

share|improve this answer
up vote 2 down vote

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?)

share|improve this answer
1  
void* to accommodate generic types is a very normal use of C - I disagree with "why are you writing in C". –  Justin Meiners Jul 17 '13 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... –  Jimmy Hoffa Jul 17 '13 at 15:27
1  
But if you're trying to write LISP, starting with LISP isn't necessarily a helpful suggestion –  Useless Jul 17 '13 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.) –  btilly Jul 17 '13 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. –  Useless Jul 17 '13 at 16:38

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.