LISP-ish low level experiments in C

lispish.c

#include <stdbool.h>
#include <memory.h>

#define NIL 0
#define POINTER 1
#define NUMBER 2

typedef struct TaggedCell TaggedCell;

struct TaggedCell {
    unsigned char tag;
    union {
        void* ptr;
        double fnum;
    };
};

static TaggedCell memory[100];
static TaggedCell* free = &memory[0];

TaggedCell allocate_pair() {
    TaggedCell pair;
    pair.tag = POINTER;
    pair.ptr = free;
    free += 2;
    return pair;
}

bool is_null(TaggedCell obj) {
    return obj.tag == NIL;
}

TaggedCell nil() {
    TaggedCell obj;
    obj.tag = NIL;
    return obj;
}

TaggedCell number(double f) {
    TaggedCell obj;
    obj.tag = NUMBER;
    obj.fnum = f;
    return obj;
}

TaggedCell* car(TaggedCell obj) {
    return (TaggedCell*)obj.ptr;
}

TaggedCell* cdr(TaggedCell obj) {
    return (TaggedCell*)(obj.ptr) + 1;
}

TaggedCell cons(TaggedCell car_value, TaggedCell cdr_value) {
    TaggedCell obj = allocate_pair();
    *car(obj) = car_value;
    *cdr(obj) = cdr_value;
    return obj;
}

TaggedCell splice(TaggedCell seq1, TaggedCell seq2) {
    if(is_null(seq1)) return seq2;
    if(is_null(seq2)) return seq1;
    return cons(*car(seq1), cons(*car(seq2), splice(*cdr(seq1), *cdr(seq2))));
}

TaggedCell reverse(TaggedCell input, TaggedCell output) {
    if(is_null(input))
        return output;
    return reverse(*cdr(input), cons(*car(input), output));
}

TaggedCell length(TaggedCell sequence, int accumulator) {
    if(is_null(sequence))
        return number(accumulator);
    return length(*cdr(sequence), accumulator + 1);
}

void length2(TaggedCell* output, TaggedCell sequence, int accumulator) {
    if(is_null(sequence)) {
        *output = number(accumulator);
        return;
    }
    length2(output, *cdr(sequence), accumulator + 1);
}