CODEWITHSUNDEEP
cpointersschemeinterpreter
CSCSCS
CSCSCS

Reputation: 79

Writing a print method in C

I am new to C and working on making an interpreter for Scheme. I am trying to get a suitable printList method to traverse through the structure.

The program takes in an input like:

(a (b c))

and internally represent it as:

[""][ ][ ]-->  [""][ ][/]
     |              |              
   ["A"][/][/]     [""][ ][ ]-->  [""][ ][/]     
                        |              |                 
                      ["B"][/][/]    ["C"][/][/]

Right now, I just want the program to take in the input, make the appropriate cell structure internally and print out the cell structure, thereby getting

(a (b c))

at the end.

Here is my struct:

typedef struct conscell *List;

struct conscell {
char symbol;
struct conscell *first;
struct conscell *rest;

};


void printList(char token[20]){
    List current = S_Expression(token, 0);

     printf("(");

printf("First Value? %c \n", current->first->symbol);
printf("Second value? %c \n", current->rest->first->first->symbol);
printf("Third value? %c \n", current->rest->first->rest->first->symbol);


printf(")");

}

In the main method, I get the first token and call:

printList(token);

I tested the values again for the sublists and I think it is working. However, I will need a method to traverse through the whole structure. Please look at my printList code again. The print calls are what I have to type, to manually get the (a (b c)) list values. So I get this output:

First value? a

First value? b

First value? c

It is what I want, but I want a method to do it using a loop, no matter how complex the structure is, also adding brackets where appropriate, so in the end, I should get:

(a (b c))

which is the same as the input.

Can anyone please help me with this?

Upvotes: 2

Views: 275

Answers (2)

dyoo
dyoo

Reputation: 12013

The original program's datatype is slightly weird; you want to be able to describe a disjoint set of data, in which case a union is probably what you want. At the moment, you've only got a single datatype for cons cells, which makes it difficult to distinguish between:

(a b c)

and

(a (b c))

The trick you're using right now is to treat symbolic data as one where both the left and right pointers of your cell are NULL, but that makes it impossible to represent:

(())

which is exactly what happens when you have a cons cell whose contents are both NULL.

One way you might represent a disjoint set of data is to use a tagged disjoint union, like this:

enum SexpType {SYMBOL, CONS, NIL};

struct Sexp {
  enum SexpType type;
  union {
    char symbol;
    struct Cons *cons;
  };
};

struct Cons {
  struct Sexp *first;
  struct Sexp *rest;
};

An Sexp can either be a SYMBOL, a CONS, or NIL. Depending on its type, we'll treat the union part of the structure differently.

We might include a few helpers to make it easier to construct these kind of structures:

struct Sexp* newCons(struct Sexp* first, struct Sexp* rest) {
  struct Sexp* pair = malloc(sizeof(struct Sexp));
  pair->type = CONS;
  pair->cons = malloc(sizeof(struct Cons));
  pair->cons->first = first;
  pair->cons->rest = rest;
  return pair;
}

struct Sexp* newSymbol(char c) {
  struct Sexp* ch = malloc(sizeof(struct Sexp));
  ch->type = SYMBOL;
  ch->symbol = c;
  return ch;
}

Once we have the proper data representation, then printList will be a recursive function that dispatches based on the the type tag:

void printSexp(struct Sexp* sexp) {
  switch (sexp->type) {
  case SYMBOL: 
    /* FIXME */
    break;
  case CONS:
    /* FIXME */
    break;
  case NIL:
    /* FIXME */
    break;
  }
}

where each of the cases are fairly simple. To get the CONS case to do something, we might try something like this:

printf("(");
printSexp(sexp->cons->first);
printf(" . ");
printSexp(sexp->cons->rest);
printf(")");

where we recursively call the printer on the components of the pair. However, this might not be exactly what we want, since it treats everything as an improper structure, and you may want to do something nicer for regular lists.

Upvotes: 2

Naytzyrhc
Naytzyrhc

Reputation: 2317

the type of List is a pointer of struct conscell, therefore should the malloc() in your createList function be of sizeof(struct conscell):

List node = malloc(sizeof(struct conscell));

the pointer to the structure is only 8 byte, whereas the size of the structure itself is 17 (with default padding actually 24byte):

http://en.wikipedia.org/wiki/Data_structure_alignment

Upvotes: 1

Related Questions