usefull commit message

17 files changed, 1737 insertions, 0 deletions

diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..a922064
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,3 @@
+bin/
+obj/
+file/*.log
\ No newline at end of file
diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..b474b62
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,62 @@
+CC := gcc
+
+ifdef PROD
+CFLAGS := -std=c99 -Wpedantic -O3 -s # production flags
+else
+CFLAGS := -std=c99 -Wall -Wextra -Wpedantic -Wshadow -Wpointer-arith \
+          -Wstrict-prototypes -Wmissing-prototypes -Wcast-qual -g -DDEBUG
+
+ifdef MEMDEBUG
+CFLAGS += -DENABLE_MEMDEBUG
+endif
+endif
+
+NAME := nlisp
+
+SRC := src
+OBJ := obj
+BIN := bin
+TEST := tests
+
+# rebuild when flags change
+FLAGHASH := $(strip $(shell echo $(CFLAGS) | sha256sum | cut -d " " -f1 ))
+
+SRCS = $(wildcard $(SRC)/*.c)
+OBJS = $(SRCS:$(SRC)/%.c=$(OBJ)/%-$(FLAGHASH).o)
+
+DEPS = $(OBJS:%.o=%.d)
+-include $(DEPS)
+
+.PHONY: all clean $(NAME) analyze valgrind
+.DEFAULT_GOAL := all
+
+all: $(NAME)
+$(NAME): $(BIN)/$(NAME)
+
+clean:
+	rm -rf $(BIN)
+	rm -rf $(OBJ)
+
+$(OBJ) $(BIN):
+	mkdir -p $@
+
+$(OBJ)/%-$(FLAGHASH).o: $(SRC)/%.c | $(OBJ)
+	$(CC) $(CFLAGS) -MMD -MF $(@:%.o=%.d) -c $< -o $@
+
+$(BIN)/%: $(OBJS) | $(BIN)
+	$(CC) $(CFLAGS) $^ -o $@
+
+analyze: clean
+	scan-build \
+		-enable-checker alpha \
+		-enable-checker core \
+		-enable-checker deadcode \
+		-enable-checker security \
+		-enable-checker unix \
+		make
+
+valgrind: $(NAME)
+	valgrind -s --leak-check=full --show-leak-kinds=all $(BIN)/$(NAME)
+
+cppcheck: clean
+	cppcheck --enable=all $(SRCS) 2> cppcheck.log
diff --git a/README.md b/README.md
new file mode 100644
index 0000000..c5b1b48
--- /dev/null
+++ b/README.md
@@ -0,0 +1,3 @@
+* TODOS:
+ - symbol table
+ - lambda
diff --git a/files/test.l b/files/test.l
new file mode 100644
index 0000000..49b4cad
--- /dev/null
+++ b/files/test.l
@@ -0,0 +1,4 @@
+(define a 69)
+'(sn ,(+ a 1))
+(define a 70)
+'(sn ,(+ a 1))
diff --git a/files/test1.l b/files/test1.l
new file mode 100644
index 0000000..b7e4749
--- /dev/null
+++ b/files/test1.l
@@ -0,0 +1,16 @@
+'(sn ,(+ a 1))
+
+'(1 2 (lol . test) 3 4 ,(+ 1 2) test)
+(cons 1 (cons 2 (cons 3 ())))
+(car '(1 2 3))
+'(1 2 3)
+(+ 1 2)
+(car (cdr (cdr (cdr '(1 2 3 (4 5) (6 . 7) ,(+ 1 2))))))
+'(1 . 2)
+(+ 1 2)
+'(1 2 3 4)
+'(1 . (2 . 3))
+'(3 . 2)
+'(1 2 3)
+'(test . (,(+ 1 2) . 5))
+
diff --git a/src/builtin.h b/src/builtin.h
new file mode 100644
index 0000000..144ed4c
--- /dev/null
+++ b/src/builtin.h
@@ -0,0 +1,98 @@
+#include "value.h"
+
+#define PROCEDURES(X)             \
+/*  X(symbol, name, argc) */      \
+    X(plus,   "+",  2)            \
+    X(minus,  "-",  2)            \
+    X(cons,   "cons", 2)          \
+    X(car,    "car", 1)           \
+    X(cdr,    "cdr", 1)           \
+
+// Number of builtin procedures
+#define PLUS_ONE(_symbol, _name, _argc) 1 +
+#define BUILTIN_PROCEDURES PROCEDURES(PLUS_ONE) 0
+
+// Forward decalration of the procedures
+#define DECLARE_PROCEDURE(proc) value_t proc(value_t *args)
+#define FORWARD_DECLARATION(symbol, _name, _argc) \
+    DECLARE_PROCEDURE(symbol);
+
+PROCEDURES(FORWARD_DECLARATION)
+
+// Fill procedure struct for the value_t
+#define PROC_DESCRIPTION(symbol, _name, argc) \
+    {argc, symbol},
+
+struct proc_builtin builtin_proc_descriptions[] = {
+    PROCEDURES(PROC_DESCRIPTION)
+};
+
+// List of ordered names of procedures
+#define PROC_NAME(symbol, name, _argc) \
+    name,
+
+const char *builtin_proc_name_list[] = {
+    PROCEDURES(PROC_NAME)
+};
+
+// ----- Definitions -----
+
+#define ASSERT_TYPE(proc, args, pos, vtype, fail)           \
+    if(args[pos]->type != vtype) {                          \
+        err("Expected arg %d of %s to be %s instead of %s", \
+            pos, #proc, "", "");                            \
+        fail;                                               \
+    }
+
+#define PROC_ASSERT_TYPE(pos, vtype, fail)                  \
+    ASSERT_TYPE(P, args, pos, vtype, fail)
+
+#define P plus
+DECLARE_PROCEDURE(P)
+{
+    PROC_ASSERT_TYPE(0, VALUE_INT, return VALUE_EMPTY);
+    PROC_ASSERT_TYPE(1, VALUE_INT, return VALUE_EMPTY);
+
+    int sum = args[0]->value.num + args[1]->value.num;
+    return value_create(VALUE_INT, &sum);
+}
+#undef P
+
+#define P minus
+DECLARE_PROCEDURE(P)
+{
+    PROC_ASSERT_TYPE(0, VALUE_INT, return VALUE_EMPTY);
+    PROC_ASSERT_TYPE(1, VALUE_INT, return VALUE_EMPTY);
+
+    int difference = args[0]->value.num - args[1]->value.num;
+    return value_create(VALUE_INT, &difference);
+}
+#undef P
+
+#define P cons
+DECLARE_PROCEDURE(P)
+{
+    struct cons cons = {value_copy(args[0]), value_copy(args[1])};
+    return value_create(VALUE_CONS, &cons);
+}
+#undef P
+
+#define P car
+DECLARE_PROCEDURE(P)
+{
+    PROC_ASSERT_TYPE(0, VALUE_CONS, return VALUE_EMPTY);
+
+    value_t left = value_copy(args[0]->value.cons.left);
+    return left;
+}
+#undef P
+
+#define P cdr
+DECLARE_PROCEDURE(P)
+{
+    PROC_ASSERT_TYPE(0, VALUE_CONS, return VALUE_EMPTY);
+
+    value_t right = value_copy(args[0]->value.cons.right);
+    return right;
+}
+#undef P
diff --git a/src/common.h b/src/common.h
new file mode 100644
index 0000000..b91459a
--- /dev/null
+++ b/src/common.h
@@ -0,0 +1,98 @@
+#ifndef COMMON_H
+#define COMMON_H
+
+// LOGGING
+
+#include <stdio.h>
+#include <time.h>
+
+#define _RED    "\033[0;31m"
+#define _GREEN  "\033[0;32m"
+#define _YELLOW "\033[0;33m"
+#define _RST    "\033[0m"
+
+#define _log_print(...) fprintf(stdout, __VA_ARGS__)
+#define _log(color, message) _log_print("[%s] %s%-7s"_RST" ", timenow(), color, message)
+
+#define info(...) do {                              \
+        _log(_GREEN, "[INFO]");                     \
+        _log_print(__VA_ARGS__); _log_print("\n");  \
+    } while(0)
+#define err(...)  do {                              \
+        _log(_RED,   "[ERROR]");                    \
+        _log_print(__FILE__":%d: ", __LINE__);      \
+        _log_print(__VA_ARGS__); _log_print("\n");  \
+    } while(0)
+#define die(...) do {     \
+        err(__VA_ARGS__); \
+        abort();          \
+    } while(0)
+
+static inline char *timenow(void)
+{
+    static char buffer[64];
+    time_t timer = time(NULL);
+    strftime(buffer, 64, "%H:%M:%S", localtime(&timer));
+    return buffer;
+}
+
+// ERROR MANAGEMENT
+
+#include <errno.h>
+
+#define ERR_NZ(e, r, on_fail) do {                \
+        int r;                                    \
+        if((r = e)) { on_fail; }                  \
+    } while(0)
+
+#define ERR_NZ_RET(e)                             \
+    ERR_NZ(e, r, return r)                        \
+
+#define ERR_ERRNO_SET(e, on_fail)                 \
+    ERR_NZ(e, _r, errno = -_r; on_fail)
+
+#define ERR_Z(e, on_fail) do {                    \
+        if(!(e)) { on_fail; }                     \
+    } while(0)
+
+#endif
+
+// MEMORY MANAGEMENT
+
+#ifdef ENABLE_MEMDEBUG
+#include "memdebug.h"
+#define DISABLE_DIE_ALLOC
+#endif
+
+#ifndef DISABLE_DIE_ALLOC
+
+#include <stdlib.h>
+#include <string.h>
+#include <errno.h>
+
+// #ifdef __GNUC__
+// #define __die_alloc(e) ({void *ptr = e; if(!v) die("%s", strerror(errno)); ptr;})
+// #define malloc(...)  __die_alloc(malloc(__VA_ARGS__))
+// #define calloc(...)  __die_alloc(calloc(__VA_ARGS__))
+// #define realloc(...) __die_alloc(realloc(__VA_ARGS__))
+// #else
+
+#define DIE_ALLOC_BUILDER(name, typed_args, args)   \
+    static inline void *__die_##name typed_args     \
+    {                                               \
+        void *r = name args;                        \
+        if(!r) die("%s", strerror(errno));          \
+        return r;                                   \
+    }
+
+DIE_ALLOC_BUILDER(malloc,  (size_t size), (size))
+DIE_ALLOC_BUILDER(calloc,  (size_t nmemb, size_t size), (nmemb, size))
+DIE_ALLOC_BUILDER(realloc, (void *ptr, size_t size), (ptr, size))
+
+#define malloc(size)        __die_malloc (       size)
+#define calloc(nmemb, size) __die_calloc (nmemb, size)
+#define realloc(ptr, size)  __die_realloc(ptr,   size)
+
+// #endif
+#endif
+
diff --git a/src/env.c b/src/env.c
new file mode 100644
index 0000000..1aa452b
--- /dev/null
+++ b/src/env.c
@@ -0,0 +1,78 @@
+#include <stdlib.h>
+#include <string.h>
+
+#include "common.h"
+#include "env.h"
+#include "hashtable.h"
+
+#define ENV_TABLE_CAP (1 << 8)
+
+static unsigned long str_hash(char *str)
+{      
+    unsigned long hash = 5381;
+    int c;
+
+    while ((c = *str++))
+        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
+
+    return hash;
+}
+
+static size_t hash(void *key)
+{
+    return str_hash((char*)key);
+}
+
+static bool equal(void *key1, void *key2)
+{
+    if(strcmp((char *)key1, (char*)key2) == 0) {
+        return true;
+    }
+
+    return false;
+}
+
+static void env_add_ref(env_t env);
+
+env_t env_create(env_t parent, env_destroy_func destroy_func)
+{
+    env_t env = malloc(sizeof(*env));
+    env->destroy_func = destroy_func;
+    env->parent = parent;
+    env->refs = 0;
+    
+    env_add_ref(env);
+
+    ERR_Z(env->table = hashtable_create(ENV_TABLE_CAP, hash, equal),
+          env_destroy(env));
+    
+    return env;
+}
+
+void env_destroy(env_t env)
+{
+    if(!env) return;
+    
+    env->refs--;
+    env_destroy(env->parent);
+    
+    if(env->refs > 0) return;
+
+
+    hashtable_for_each_item(env->table, item, i) {
+        env->destroy_func((char *)item->key, (value_t)item->data);
+    }
+
+    hashtable_destroy(env->table);
+    free(env);
+}
+
+
+static void env_add_ref(env_t env)
+{
+    env->refs++;
+    
+    if(env->parent) {
+        env_add_ref(env->parent);
+    }
+}
diff --git a/src/env.h b/src/env.h
new file mode 100644
index 0000000..577133a
--- /dev/null
+++ b/src/env.h
@@ -0,0 +1,30 @@
+#ifndef ENV_H
+#define ENV_H
+
+// #include "value.h"
+typedef struct value * value_t;
+
+#include "hashtable.h"
+
+typedef struct symbol_table *env_t;
+#define ENV_EMPTY NULL
+
+typedef void (*env_destroy_func)(char *key, value_t value);
+
+struct symbol_table {
+    hashtable_t table;
+
+    struct symbol_table *parent;
+    size_t refs;
+
+    env_destroy_func destroy_func;
+};
+
+env_t env_create(env_t parent, env_destroy_func destroy_func);
+void env_destroy(env_t env);
+
+int env_insert(env_t env, value_t key, value_t data);
+int env_query (env_t env, value_t key, value_t *data);
+int env_delete(env_t env, value_t key);
+
+#endif
diff --git a/src/hashtable.c b/src/hashtable.c
new file mode 100644
index 0000000..5ef1839
--- /dev/null
+++ b/src/hashtable.c
@@ -0,0 +1,164 @@
+#include <stdlib.h>
+#include <errno.h>
+
+#include "common.h"
+#include "hashtable.h"
+
+// TODO:
+// - automatic growing
+// - insertion options
+
+#define HASH(ht, key) (ht->hash_func(key) % ht->cap)
+
+static int hashtable_grow(hashtable_t ht, size_t cap);
+static int hashtable_find_item(hashtable_t ht, size_t idx, void *key, struct hashtable_item **item, struct hashtable_item **prev);
+static void hashtable_table_append_item(struct hashtable_item ** table, size_t idx, struct hashtable_item *item);
+
+hashtable_t hashtable_create(size_t cap, hashtable_hash_func hash_func, hashtable_equal_func equal_func)
+{
+    hashtable_t ht;
+    ERR_Z(ht = malloc(sizeof(*ht)), goto fail);
+
+    ht->hash_func = hash_func;
+    ht->equal_func = equal_func;
+    ht->cap = 0;
+    ht->size = 0;
+
+    ERR_ERRNO_SET(hashtable_grow(ht, cap), goto fail);
+    
+    return ht;
+fail:
+    hashtable_destroy(ht);
+    return NULL;
+}
+
+void hashtable_destroy(hashtable_t ht)
+{
+    if(!ht) return;
+    
+    if(ht->table) {
+        hashtable_for_each_item_safe(ht, item, i) {
+            free(item);
+        }
+        
+        free(ht->table);
+    }
+    
+    free(ht);
+}
+
+void hashtable_reset(hashtable_t ht)
+{
+    if(!ht) return;
+
+    if(ht->table) {
+        hashtable_for_each_item_safe(ht, item, i) {
+            free(item);
+        }
+    }
+
+    ht->size = 0;
+}
+
+int hashtable_insert(hashtable_t ht, void *key, void *data, void **prevkey, void **prevdata)
+{
+    size_t idx = HASH(ht, key);
+
+    struct hashtable_item *item, *prev;
+    hashtable_find_item(ht, idx, key, &item, &prev);
+    
+    if(item) {
+        if(prevkey)  *prevkey  = item->key;
+        if(prevdata) *prevdata = item->data;
+        item->key = key;
+        item->data = data;
+        return 0;
+    }
+    
+    ERR_Z(item = malloc(sizeof(*item)), return -ENOMEM);
+        
+    item->key = key;
+    item->data = data;
+    item->next = NULL;
+
+    hashtable_table_append_item(ht->table, idx, item);
+    ht->size++;
+    
+    if(ht->size > (ht->cap * 3/4)) {
+        return hashtable_grow(ht, 1 << ht->cap);
+    }
+    
+    return 0;
+}
+
+int hashtable_query(hashtable_t ht, void *key, void **data)
+{
+    size_t idx = HASH(ht, key);
+    
+    struct hashtable_item *item;
+    ERR_NZ_RET(hashtable_find_item(ht, idx, key, &item, NULL));
+
+    *data = item->data;
+    
+    return 0;
+}
+
+int hashtable_delete(hashtable_t ht, void *key)
+{
+    size_t idx = HASH(ht, key);
+    
+    struct hashtable_item *item, *prev;
+    ERR_NZ_RET(hashtable_find_item(ht, idx, key, &item, &prev));
+    
+    if(prev)
+        prev->next = item->next;
+    else
+        ht->table[idx] = item->next;
+
+    free(item);
+    
+    return 0;
+}
+
+static int hashtable_grow(hashtable_t ht, size_t cap)
+{
+    struct hashtable_item **new_table;
+    ERR_Z(new_table = calloc(cap, sizeof(*new_table)), return -ENOMEM);
+
+    if(ht->cap > 0) {
+        hashtable_for_each_item_safe(ht, item, i) {
+            // hash but with the new cap
+            size_t idx = ht->hash_func(item->key) % cap;
+            hashtable_table_append_item(new_table, idx, item);
+        }
+
+        free(ht->table);
+    }
+
+    ht->table = new_table;
+    ht->cap = cap;
+    
+    return 0;
+}
+
+static int hashtable_find_item(hashtable_t ht, size_t idx, void *key, struct hashtable_item **item, struct hashtable_item **prev)
+{
+    if(item) *item = NULL;
+    if(prev) *prev = NULL;
+
+    hashtable_for_each_item_on_index(ht, _item, idx) {
+        if(ht->equal_func(_item->key, key)) {
+            if(item) *item = _item;
+            return 0;
+        }
+        if(prev) *prev = _item;
+    }
+    
+    return -ENOENT;
+}
+
+static void hashtable_table_append_item(struct hashtable_item **table, size_t idx, struct hashtable_item *item)
+{
+    item->next = table[idx];
+    table[idx] = item;
+}
diff --git a/src/hashtable.h b/src/hashtable.h
new file mode 100644
index 0000000..b9b1b2a
--- /dev/null
+++ b/src/hashtable.h
@@ -0,0 +1,54 @@
+#ifndef HASHMAP_H
+#define HASHMAP_H
+
+#include <stdbool.h>
+
+typedef struct hashtable *hashtable_t;
+
+typedef size_t (*hashtable_hash_func)(void *key);
+typedef bool (*hashtable_equal_func)(void *key1, void *key2);
+
+struct hashtable {
+    hashtable_hash_func hash_func;
+    hashtable_equal_func equal_func;
+
+    struct hashtable_item {
+        struct hashtable_item *next;
+        void *key;
+        void *data;
+    } **table;
+
+    size_t size;
+    size_t cap;
+};
+
+hashtable_t hashtable_create(size_t cap, hashtable_hash_func hash_func, hashtable_equal_func equal_func);
+void hashtable_destroy(hashtable_t ht);
+void hashtable_reset(hashtable_t ht);
+
+int hashtable_insert(hashtable_t ht, void *key, void *data,
+                     void **prevkey, void **prevdata);
+int hashtable_query(hashtable_t ht, void *key, void **data);
+int hashtable_delete(hashtable_t ht, void *key);
+
+#define hashtable_for_each_item(ht, item, i)            \
+    for(size_t i = 0; i < ht->cap; i++)                 \
+        for(struct hashtable_item *item = ht->table[i]; \
+            item != NULL;                               \
+            item = item->next)
+
+#define hashtable_for_each_item_on_index(ht, item, idx) \
+    for(struct hashtable_item *item =                   \
+            ht->table[idx];                             \
+        item != NULL;                                   \
+        item = item->next)
+
+#define hashtable_for_each_item_safe(ht, item, i)                       \
+    for(size_t i = 0; i < ht->cap; i++)                                 \
+        for(struct hashtable_item                                       \
+                *item = ht->table[i],                                   \
+                *next = NULL;                                           \
+            item != NULL && (next = item->next, 1);                     \
+            item = next)
+
+#endif
diff --git a/src/lexer.c b/src/lexer.c
new file mode 100644
index 0000000..407be25
--- /dev/null
+++ b/src/lexer.c
@@ -0,0 +1,174 @@
+#include <stdlib.h>
+#include <string.h>
+#include <ctype.h>
+
+#include "common.h"
+#include "lexer.h"
+
+#define CH(lexer) (lexer)->str[(lexer)->str_idx]
+#define TOKEN_SEPARATOR_TABLE(X, l)                 \
+    X(('(' == CH(l)), on_separator(l, TOKEN_LP))    \
+    X((')' == CH(l)), on_separator(l, TOKEN_RP))    \
+    X(isspace(CH(l)), on_separator(l, TOKEN_NONE))  \
+    X(TABLE_ELSE,     acc_add_char(l, CH(l)))
+
+#define SET_TYPE(lexer, ttype) (lexer)->token.type = (ttype)
+#define SET_VALUE(lexer, member, tvalue) (lexer)->token.value.member = (tvalue)
+#define TOKEN_VALUE_TABLE(X, l)              \
+    X(is_int(l->acc, &l->token.value.num),   \
+        SET_TYPE(l, TOKEN_INT))              \
+    X(is_special(l->acc, &l->token.type),    \
+        ;)                                   \
+    X(TABLE_ELSE,                            \
+        SET_TYPE(l, TOKEN_ID);               \
+        SET_VALUE(l, id, l->acc))
+
+#define TOKEN_SPECIALS_TABLE(X)      \
+    X(TOKEN_DOT,        ".")         \
+    X(TOKEN_QUOTE,      "'")         \
+    X(TOKEN_UNQUOTE,    ",")         \
+    X(TOKEN_LAMBDA,     "lambda")    \
+    X(TOKEN_DEFINE,     "define")    \
+    X(TOKEN_QUOTE_FORM, "quote")
+
+#define TOKEN_VALUE_STRING_TABLE(X, tvalue)  \
+    X(TOKEN_LP,      "(")                    \
+    X(TOKEN_RP,      ")")                    \
+    X(TOKEN_ID,      "%s", tvalue.id)        \
+    X(TOKEN_STR,     "%s", tvalue.str)       \
+    X(TOKEN_INT,     "%d", tvalue.num)       \
+    TOKEN_SPECIALS_TABLE(X)                  \
+    X(TOKEN_NONE,    "(none)")
+
+#define TABLE_ELSE 1
+#define TABLE_END {}
+
+#define CALLBACK(test, callback)                \
+    if(test) {                                  \
+        ERR_NZ(callback, r, return r);          \
+    } else
+#define CALLBACK_BLIND(test, callback)          \
+    if(test) {                                  \
+        callback;                               \
+    } else
+
+#define LEN(arr) (sizeof(arr)/sizeof(*(arr)))
+
+const char * const token_type_string[] = {
+    TOKEN_TYPES(TO_STRING)
+};
+
+static int on_separator(lexer_t lexer, enum token_type type);
+static int acc_add_char(lexer_t lexer, char ch);
+static int acc_empty(lexer_t lexer);
+
+static int is_int(char *str, int *num);
+static int is_special(char *str, enum token_type *type);
+
+lexer_t lexer_create(FILE *fp)
+{
+    lexer_t lexer = malloc(sizeof(*lexer));
+    lexer->fp = fp;
+    lexer->line = 0;
+    lexer->str_idx = 0;
+    lexer->acc_idx = 0;
+    memset(lexer->acc, 0, sizeof(lexer->acc));
+    memset(lexer->str, 0, sizeof(lexer->str));
+       
+    lexer->token.type = TOKEN_NONE;
+
+    return lexer;
+}
+
+void lexer_destroy(lexer_t lexer)
+{
+    if(!lexer) return;
+    free(lexer);
+}
+
+int lexer_token_next(lexer_t lexer, struct token *token)
+{
+    if(lexer->acc_idx == 0 && lexer->acc[0] != '\0') {
+        memset(lexer->acc, 0, sizeof(lexer->acc));
+    }
+            
+    while(lexer->token.type == TOKEN_NONE)
+    {
+        if(lexer->str[lexer->str_idx] == '\0') {
+            ERR_Z(fgets(lexer->str, LEN(lexer->str), lexer->fp), return -EIO);
+            lexer->str_idx = 0;
+            lexer->line++;
+        }
+        
+        TOKEN_SEPARATOR_TABLE(CALLBACK, lexer) TABLE_END;
+    }
+    
+    *token = lexer->token;
+    lexer->token.type = TOKEN_NONE;
+    return 0;
+}
+
+int token_value_string(struct token *token, size_t buf_sz, char *buf)
+{
+#define AS_STRING(ttype, ...) \
+    case ttype: return snprintf(buf, buf_sz, __VA_ARGS__);
+        
+    switch(token->type) {
+        TOKEN_VALUE_STRING_TABLE(AS_STRING, token->value);
+    }
+
+    return 0;
+}
+
+static int on_separator(lexer_t lexer, enum token_type type)
+{
+    if(lexer->acc_idx > 0) return acc_empty(lexer);
+
+    lexer->token.type = type;
+    lexer->str_idx++;
+    return 0;
+}
+
+static int acc_add_char(lexer_t lexer, char ch)
+{
+    if(lexer->acc_idx >= LEN(lexer->acc) - 1) {
+        return -ENAMETOOLONG;
+    }
+    
+    lexer->acc[lexer->acc_idx++] = ch;
+    lexer->str_idx++;
+
+    return 0;
+}
+
+static int acc_empty(lexer_t lexer)
+{    
+    TOKEN_VALUE_TABLE(CALLBACK_BLIND, lexer) TABLE_END;
+    lexer->acc_idx = 0;
+    
+    return 0;
+}
+
+static int is_int(char *str, int *num)
+{
+    char *endptr = str;
+    long _num = strtol(str, &endptr, 10);
+
+    if(*endptr != '\0') return 0;
+
+    *num = (int)_num;
+    return 1;
+}
+
+static int is_special(char *str, enum token_type *type)
+{
+#define IS_SPECIAL(ttype, sstr)                  \
+    if(strcmp(sstr, str) == 0) {                 \
+        *type = ttype;                           \
+        return 1;                                \
+    } else
+
+    TOKEN_SPECIALS_TABLE(IS_SPECIAL) TABLE_END;
+    
+    return 0;
+}
diff --git a/src/lexer.h b/src/lexer.h
new file mode 100644
index 0000000..7c67028
--- /dev/null
+++ b/src/lexer.h
@@ -0,0 +1,58 @@
+#ifndef LEXER_H
+#define LEXER_H
+
+#include <stdio.h>
+
+#define TOKEN_TYPES(X)        \
+    X(TOKEN_LP)               \
+    X(TOKEN_RP)               \
+    X(TOKEN_ID)               \
+    X(TOKEN_STR)              \
+    X(TOKEN_INT)              \
+    X(TOKEN_DOT)              \
+    X(TOKEN_QUOTE)            \
+    X(TOKEN_UNQUOTE)          \
+    X(TOKEN_LAMBDA)           \
+    X(TOKEN_DEFINE)           \
+    X(TOKEN_QUOTE_FORM)       \
+    X(TOKEN_NONE)
+
+#define TO_ENUM(type) type,
+#define TO_STRING(type) #type,
+
+extern const char * const token_type_string[];
+
+struct token {
+    enum token_type {
+        TOKEN_TYPES(TO_ENUM)
+    } type;
+    
+    union {
+        char *id;
+        char *str;
+        int   num;
+    } value;
+};
+
+typedef struct lexer * lexer_t;
+#define LEXER_EMPTY NULL
+
+struct lexer {
+    FILE *fp;
+    size_t line;
+    
+    char str[256];
+    size_t str_idx;
+
+    struct token token;
+    char acc[256];
+    size_t acc_idx;
+};
+
+lexer_t lexer_create(FILE *fp);
+void lexer_destroy(lexer_t lexer);
+int lexer_token_next(lexer_t lexer, struct token *token);
+
+int token_value_string(struct token *token, size_t buf_sz, char *buf);
+
+#endif
diff --git a/src/main.c b/src/main.c
new file mode 100644
index 0000000..195e213
--- /dev/null
+++ b/src/main.c
@@ -0,0 +1,436 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "lexer.h"
+#include "value.h"
+#include "env.h"
+
+#ifdef ENABLE_MEMDEBUG
+#define MEMDEBUG_OUT_OF_BOUNDS
+#define MEMDEBUG_IMPLEMENTATION
+#define MEMDEBUG_MAIN_VOID
+#define MEMDEBUG_OUTPUT_DIR "files"
+#endif
+
+#include "common.h"
+#include "builtin.h"
+
+#define LEN(arr) (sizeof(arr)/sizeof(*(arr)))
+
+// TODO:
+// - Think about memory leakage and on non fatal errors
+//   like failed list creation and faild s-exp parsing
+// - Check for functions not wrapped in ERR_* macro
+// - Add more error messages
+
+#ifndef DEBUG
+#define TOKEN_NEXT()                            \
+    ERR_NZ(lexer_token_next(lexer, &token), r,  \
+           die("Can't get next token"))
+#else
+#define TOKEN_NEXT() do {                           \
+        ERR_NZ(lexer_token_next(lexer, &token), r,  \
+               die("Can't get next token"));        \
+        print_token(&token);                        \
+    } while(0);
+#endif
+
+#define TOKEN_SKIP(ttype, fail) do {            \
+        if(token.type == ttype) {               \
+            TOKEN_NEXT();                       \
+            break;                              \
+        }                                       \
+        err("Expected token '%s', not '%s'",    \
+            token_type_string[ttype],           \
+            token_type_string[token.type]);     \
+        fail;                                   \
+    } while(0)
+
+#define TOKEN_MATCH(ttype, fail) do {                          \
+        TOKEN_NEXT();                                          \
+        if(token.type == ttype) break;                         \
+                                                               \
+        err("Expected token '%s', not '%s'",                   \
+            token_type_string[ttype],                          \
+            token_type_string[token.type]);                    \
+        fail;                                                  \
+    } while(0)
+
+#define HAS_ENOUGH_ARGS(proc, type, argc, fail)                     \
+    if(argc != proc->value.type.argc) {                             \
+        err("Wrong number of arguemnts, expected %zu, but got %zu", \
+            proc->value.type.argc, argc);                           \
+        fail;                                                       \
+    }
+
+#define NOT_IMPLEMENTED() die("Not Implemented. ABORTING")
+
+static void print_token(struct token *token)
+{
+    char buf[256] = {0};
+    ERR_Z(token_value_string(token, LEN(buf), buf), return);
+    info("%-12s %s", token_type_string[token->type], buf);
+}
+
+static void print_value(value_t value)
+{
+    char buf[256] = {0};
+    value_string(value, LEN(buf), buf);
+    info("%-12s %s", value ?
+         value_type_string[value->type] : "VALUE", buf);
+}
+
+static lexer_t lexer = LEXER_EMPTY;
+static env_t user_env = ENV_EMPTY;
+
+env_t env = ENV_EMPTY;
+struct token token;
+
+value_t apply(value_t proc, size_t argc, value_t *argv);
+value_t evaluate(void);
+value_t evaluate_sexp(void);
+value_t evaluate_id(void);
+value_t evaluate_lambda(void);
+value_t evaluate_define(void);
+value_t evaluate_quote(void);
+value_t quote_sexp(void);
+
+static void destroy_env(char *key, value_t value)
+{
+    (void)key;
+    value_destroy(value);
+}
+
+static void destroy_user_env(char *key, value_t value)
+{
+    free(key);
+    value_destroy(value);
+}
+
+int main(void)
+{
+    user_env = env_create(ENV_EMPTY, destroy_user_env);
+    env = env_create(user_env, destroy_env);
+
+    for(size_t i = 0; i < BUILTIN_PROCEDURES; i++) {
+        value_t proc_value = value_create(
+            VALUE_PROC_BUILTIN,
+            (void *)&builtin_proc_descriptions[i]);
+        hashtable_insert(env->table,
+                         (void *)builtin_proc_name_list[i],
+                         (void *)proc_value, NULL, NULL);
+    }
+    char *filename = "files/test.l";
+        
+    FILE *fp = fopen(filename, "r");
+    if(!fp) {
+        die("fopen: %s", strerror(errno));
+    }
+    
+    lexer = lexer_create(fp);
+
+    while(lexer_token_next(lexer, &token) == 0) {
+        value_t val = evaluate();
+
+        #ifdef FDEBUG
+        print_value();
+        #else
+        char buf[256] = {0};
+        value_string(val, LEN(buf), buf);
+        printf("%s:%zu:   %s\n", filename, lexer->line, buf);
+        #endif    
+        
+        value_destroy(val);
+    }
+
+    lexer_destroy(lexer);
+    fclose(fp);
+  
+    env_destroy(env);
+    env_destroy(user_env);
+    return 0;
+}
+
+value_t apply(value_t proc, size_t argc, value_t *argv)
+{
+    // TODO: make a global nil and copy it
+    if(proc == VALUE_EMPTY) return value_create(VALUE_NIL, NULL);
+    
+    switch(proc->type) {
+    case VALUE_PROC:
+        HAS_ENOUGH_ARGS(proc, proc, argc, return VALUE_EMPTY);
+        NOT_IMPLEMENTED();
+        return VALUE_EMPTY;
+    case VALUE_PROC_BUILTIN:
+        HAS_ENOUGH_ARGS(proc, proc_builtin, argc, return VALUE_EMPTY);
+        return proc->value.proc_builtin.proc(argv);
+    default:
+        err("Value is not a procedure");
+        return VALUE_EMPTY;
+    }
+}
+
+#define IS_NOT_FIRST(arg, fail)                                \
+    if(arg != 0) {                                             \
+        err("special forms can only be the first argument");   \
+        fail;                                                  \
+    }
+#define SPECIAL_FORM(ret, argc, fn, fail) do {  \
+        IS_NOT_FIRST(argc, fail);               \
+        ERR_Z(ret = fn, fail);                  \
+        TOKEN_MATCH(TOKEN_RP,                   \
+                    ret = VALUE_EMPTY;          \
+                    fail);                      \
+    } while(0)
+
+value_t evaluate(void)
+{
+    value_t ret = VALUE_EMPTY;
+        
+    switch(token.type) {
+    case TOKEN_LP:
+        ERR_Z(ret = evaluate_sexp(), goto exit);
+        break;
+    case TOKEN_ID:
+        ERR_Z(ret = evaluate_id(), goto exit);
+        break;
+    case TOKEN_STR:
+    case TOKEN_INT:
+        ERR_Z(ret = value_from_token(&token), goto exit);
+        break;
+    case TOKEN_QUOTE:
+        TOKEN_NEXT();
+        ERR_Z(ret = evaluate_quote(), goto exit);
+        break;
+    default:
+        err("Did not exptect token '%s'", token_type_string[token.type]);
+        break;
+    }
+
+exit:
+    return ret;
+}
+
+value_t evaluate_sexp(void)
+{
+    value_t ret = VALUE_EMPTY;
+    value_t body[256] = {VALUE_EMPTY};
+    size_t argc = 0;
+
+    TOKEN_SKIP(TOKEN_LP, goto exit);
+    
+    for(argc = 0; token.type != TOKEN_RP; argc++)
+    {
+        if(argc >= LEN(body)) {
+            err("Too many arguments");
+            goto exit;
+        }
+        
+        switch(token.type) {
+        case TOKEN_LAMBDA:
+            SPECIAL_FORM(ret, argc, evaluate_lambda(), goto exit);
+            goto exit;
+        case TOKEN_DEFINE:
+            SPECIAL_FORM(ret, argc, evaluate_define(), goto exit);
+            goto exit;
+        case TOKEN_QUOTE_FORM:
+            TOKEN_NEXT();
+            SPECIAL_FORM(ret, argc, evaluate_quote(),  goto exit);
+            goto exit;
+        default:
+            ERR_Z(body[argc] = evaluate(), goto exit);
+            break;
+        }
+
+        TOKEN_NEXT();
+    }
+    
+    ret = apply(body[0], argc-1, &body[1]);
+
+    #ifdef DEBUG
+    info("------------------");
+    info("Applying procedure");
+    print_value(body[0]);
+    info("With Arguemnts");
+    if(argc > 0)
+        for(size_t i = 0; i < argc-1; i++) print_value(body[i+1]);
+    info("Returns");
+    print_value(ret);
+    info("-----------------");
+    #endif
+
+exit:
+    for(size_t i = 0; i < argc; i++)
+        value_destroy(body[i]);
+    return ret;
+}
+
+static value_t evaluate_id_env(env_t env)
+{
+    if(env == ENV_EMPTY) return VALUE_EMPTY;
+    
+    value_t ret = VALUE_EMPTY;
+    ERR_NZ(hashtable_query(env->table, (void *)token.value.id, (void **)&ret), _r, return evaluate_id_env(env->parent));
+    
+    return value_copy(ret);
+}
+
+value_t evaluate_id(void)
+{
+    return evaluate_id_env(env);
+}
+
+value_t evaluate_lambda(void)
+{
+    NOT_IMPLEMENTED();
+}
+
+#define STR_ALLOC_COPY(dest, str) do {    \
+        size_t len = strlen(str) + 1;     \
+        dest = malloc(len);               \
+        memcpy((dest), (str), len);       \
+    } while(0)
+
+value_t evaluate_define(void)
+{
+    // TODO: don't alloc when the key is the same
+    
+    value_t ret = VALUE_EMPTY;    
+    char *key = NULL;
+    
+    TOKEN_SKIP(TOKEN_DEFINE, goto exit);
+
+    // only in the outside environement
+    if(env->parent != user_env) goto exit;
+
+    switch(token.type)
+    {
+    case TOKEN_ID:
+        STR_ALLOC_COPY(key, token.value.id);
+        break;
+    default:
+        err("Did not exptect token '%s'", token_type_string[token.type]);
+        goto exit;
+    }
+
+    TOKEN_NEXT();
+    ERR_Z(ret = evaluate(), goto exit);
+    
+    TOKEN_MATCH(TOKEN_RP, goto exit);
+
+    value_t prevval = VALUE_EMPTY;
+    char *prevkey = NULL;
+
+    ERR_NZ(
+        hashtable_insert(user_env->table, (void *)key, (void *)ret,
+                         (void**)&prevkey, (void **)&prevval),
+        r, {
+            err("Couldn't insert symbol into the hashtable due to %s", strerror(r));
+            value_destroy(ret);
+            free(key);
+            return VALUE_EMPTY;
+        });
+
+    if(prevkey) free(prevkey);
+    value_destroy(prevval);
+exit:
+    return VALUE_EMPTY;
+}
+
+value_t evaluate_quote(void)
+{
+    value_t ret = VALUE_EMPTY;
+
+    switch(token.type) {
+    case TOKEN_ID:
+    case TOKEN_STR:
+    case TOKEN_INT:
+        ERR_Z(ret = value_from_token(&token), goto exit);
+        break;
+    case TOKEN_QUOTE:
+    case TOKEN_LAMBDA:
+    case TOKEN_DEFINE:
+    case TOKEN_QUOTE_FORM: ;
+        char name[64] = {0};
+        ERR_Z(token_value_string(&token, LEN(name), name), goto exit);
+        struct token temp = {0}; temp.type = TOKEN_ID; temp.value.id = name;
+        ERR_Z(ret = value_from_token(&temp), goto exit);
+        break;
+    case TOKEN_LP:
+        ERR_Z(ret = quote_sexp(), goto exit);
+        break;
+    case TOKEN_UNQUOTE:
+        TOKEN_SKIP(TOKEN_UNQUOTE, goto exit);
+        ERR_Z(ret = evaluate(), goto exit);
+        break;
+    default:
+        err("Did not exptect token '%s'", token_type_string[token.type]);
+        break;
+    }
+exit:
+    return ret;
+}
+
+value_t quote_sexp(void)
+{
+    value_t ret   = VALUE_EMPTY;
+    value_t left  = VALUE_EMPTY;
+    value_t right = VALUE_EMPTY;
+    value_t nil = VALUE_EMPTY;
+
+    // TODO: make global nil and copy it
+    ERR_Z(nil = value_create(VALUE_NIL, NULL), goto exit);
+    
+    TOKEN_SKIP(TOKEN_LP, goto exit);
+
+    // Parse NIL
+    if(token.type == TOKEN_RP) {
+        ret = value_copy(nil);
+        goto exit;
+    }
+        
+    ERR_Z(left = evaluate_quote(), goto exit);
+
+    TOKEN_NEXT();
+    if(token.type == TOKEN_DOT)
+    {
+        // Parse cons
+        TOKEN_NEXT();
+        ERR_Z(right = evaluate_quote(), return VALUE_EMPTY);
+        TOKEN_MATCH(TOKEN_RP, return VALUE_EMPTY);
+        
+        struct cons cons = {value_copy(left), value_copy(right)};
+        ret = value_create(VALUE_CONS, &cons);
+        goto exit;
+    }
+    
+    // Parse list
+    right = value_copy(nil);
+    value_t *rightmost = &right; // the final nil
+    while(token.type != TOKEN_RP)
+    {
+        value_t new = VALUE_EMPTY;
+        ERR_Z(new = evaluate_quote(),
+              goto exit);
+        
+        value_t new_cons = VALUE_EMPTY;
+        struct cons cons = {new, *rightmost};
+        ERR_Z(new_cons = value_create(VALUE_CONS, &cons),
+              value_destroy(new);
+              goto exit);
+
+        *rightmost = new_cons;
+        rightmost = &new_cons->value.cons.right;
+        
+        TOKEN_NEXT();
+    }
+
+    struct cons cons = {value_copy(left), value_copy(right)};
+    ret = value_create(VALUE_CONS, &cons);
+exit:
+    value_destroy(left);
+    value_destroy(right);
+    value_destroy(nil);
+    return ret;
+}
diff --git a/src/memdebug.h b/src/memdebug.h
new file mode 100644
index 0000000..d219397
--- /dev/null
+++ b/src/memdebug.h
@@ -0,0 +1,234 @@
+#ifndef MEMDEBUG_H
+#define MEMDEBUG_H
+
+/* OPTIONS:
+ * - MEMDEBUG_IMPLEMENTATION - include the implementation
+ *   (should be inlcuded in only one source file)
+ * - MEMDEBUG_(MALLOC|REALLOC|CALLOC|FREE)_SYMBOL - change
+ *   the function used for the operation
+ * - MEMDEBUG_OUT_OF_BOUNDS - enable the out-of-bounds
+ *   check
+ * - MEMDEBUG_VOID - the main function is main(void)
+ *   instead of main(int argc, char **argv)
+ * - MEMDEBUG_OUTPUT_LOG - output the log in a file
+ *   (format is "memdebug-<timestamp>.log")
+ * - MEMDEBUG_OUTPUT_DIR - set the directory for the log,
+ *   by default it is the current directory (automatically
+ *   enables the MEMDEBUG_OUTPUT_LOG
+ */ 
+
+void *__memdebug_malloc(size_t size, char *file, int line);
+void *__memdebug_calloc(size_t nmemb, size_t size, char *file, int line);
+void *__memdebug_realloc(void *ptr, size_t size, char *file, int line);
+void __memdebug_free(void *ptr, char *file, int line);
+
+#ifdef MEMDEBUG_IMPLEMENTATION
+
+// Default memory allocation functions
+#ifndef MEMDEBUG_MALLOC_SYMBOL
+#define MEMDEBUG_MALLOC_SYMBOL malloc
+#endif
+
+#ifndef MEMDEBUG_REALLOC_SYMBOL
+#define MEMDEBUG_REALLOC_SYMBOL realloc
+#endif
+
+#ifndef MEMDEBUG_CALLOC_SYMBOL
+#define MEMDEBUG_CALLOC_SYMBOL calloc
+#endif
+
+#ifndef MEMDEBUG_FREE_SYMBOL
+#define MEMDEBUG_FREE_SYMBOL free
+#endif
+
+// Log output
+#ifdef MEMDEBUG_OUTPUT_DIR
+#define MEMDEBUG_OUTPUT_LOG
+#else
+#define MEMDEBUG_OUTPUT_DIR "."
+#endif
+
+#ifdef MEMDEBUG_OUTPUT_LOG 
+#define MEMDEBUG_OUTPUT_FMT "memdebug-%lu.log"
+#endif
+
+// Out-of-bounds check
+#define MEMDEBUG_MAGIC_SUFFIX 0xDEADB00BCAFEF00D // 64 bit
+
+typedef long long int memdebug_suffix;
+#define MEMDEBUG_OUT_OF_BOUNDS_EXTRA_SIZE \
+    (sizeof(size_t) + sizeof(memdebug_suffix))
+
+
+// Implementation
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <errno.h>
+#include <time.h>
+
+static FILE *_memdebug_fp = NULL;
+
+#define MEMDEBUG_LOG(...) \
+    fprintf(_memdebug_fp, __VA_ARGS__)
+#define MEMDEBUG_LOG_FUNC(func, ret, file, line)                \
+    do {                                                        \
+        MEMDEBUG_LOG("(%s:%4d) %-8s ", file, line, #func);      \
+        if(ret == NULL)                                         \
+            MEMDEBUG_LOG("FAILED %d (%s) ",                     \
+                         errno, strerror(errno));               \
+    } while(0)
+
+#define MEMDEBUG_OUT_OF_BOUNDS_CHECK(addr, size)            \
+    do {                                                    \
+        if(addr != NULL) {                                  \
+            *(size_t*)addr = size;                          \
+            addr += sizeof(size_t);                         \
+                                                            \
+            memdebug_suffix suffix = MEMDEBUG_MAGIC_SUFFIX; \
+            memcpy(addr + size, &suffix, sizeof(suffix));   \
+        }                                                   \
+    } while(0);
+
+
+void *__memdebug_malloc(size_t size, char *file, int line)
+{
+#ifndef MEMDEBUG_OUT_OF_BOUNDS
+    void *addr = MEMDEBUG_MALLOC_SYMBOL(size);
+#else
+    void *addr = MEMDEBUG_MALLOC_SYMBOL(
+        size + MEMDEBUG_OUT_OF_BOUNDS_EXTRA_SIZE);
+    MEMDEBUG_OUT_OF_BOUNDS_CHECK(addr, size);
+#endif
+
+    MEMDEBUG_LOG_FUNC(malloc, addr, file, line);
+    
+    MEMDEBUG_LOG("size: %zu, ret: %p", size, addr);
+    MEMDEBUG_LOG("\n");
+
+    fflush(_memdebug_fp);
+    return addr;
+}
+
+void *__memdebug_realloc(void *ptr, size_t size, char *file, int line)
+{
+#ifndef MEMDEBUG_OUT_OF_BOUNDS
+    void *addr = MEMDEBUG_REALLOC_SYMBOL(ptr, size);
+#else
+    void *addr = MEMDEBUG_REALLOC_SYMBOL(
+        ptr, size + MEMDEBUG_OUT_OF_BOUNDS_EXTRA_SIZE);
+    MEMDEBUG_OUT_OF_BOUNDS_CHECK(addr, size);
+#endif
+    
+    MEMDEBUG_LOG_FUNC(realloc, addr, file, line);
+    
+    MEMDEBUG_LOG("ptr: %p, size: %zu, ret: %p", ptr, size, addr);
+    MEMDEBUG_LOG("\n");
+
+    fflush(_memdebug_fp);
+    return addr;
+}
+
+void *__memdebug_calloc(size_t nmemb, size_t size, char *file, int line)
+{
+#ifndef MEMDEBUG_OUT_OF_BOUNDS
+    void *addr = MEMDEBUG_CALLOC_SYMBOL(nmemb, size);
+#else
+    void *addr = MEMDEBUG_MALLOC_SYMBOL(
+        nmemb * size + MEMDEBUG_OUT_OF_BOUNDS_EXTRA_SIZE);
+    MEMDEBUG_OUT_OF_BOUNDS_CHECK(addr, nmemb * size);
+    memset(addr, 0, nmemb * size);
+#endif
+    
+    MEMDEBUG_LOG_FUNC(calloc, addr, file, line);
+    
+    MEMDEBUG_LOG("nmemb: %zu, size: %zu, ret: %p", nmemb, size, addr);
+    MEMDEBUG_LOG("\n");
+
+    fflush(_memdebug_fp);
+    return addr;
+}
+
+void __memdebug_free(void *ptr, char *file, int line)
+{    
+    MEMDEBUG_LOG_FUNC(free, (void *)1, file, line);
+    
+    MEMDEBUG_LOG("ptr: %p", ptr);
+
+#ifdef MEMDEBUG_OUT_OF_BOUNDS
+    if(ptr != NULL) {
+        size_t size = *(size_t *)(ptr - sizeof(size_t));
+        memdebug_suffix suffix = 0;
+        memcpy(&suffix, ptr + size, sizeof(suffix));
+
+        MEMDEBUG_LOG(", ");
+        MEMDEBUG_LOG("out-of-bounds-check: ");
+        
+        if(suffix == (memdebug_suffix)MEMDEBUG_MAGIC_SUFFIX)
+            MEMDEBUG_LOG("SUCCESS");
+        else MEMDEBUG_LOG("FAILED");
+                
+        ptr -= sizeof(size_t);
+    }
+#endif
+
+    MEMDEBUG_LOG("\n");
+
+    fflush(_memdebug_fp);
+    MEMDEBUG_FREE_SYMBOL(ptr);
+}
+
+#ifdef MEMDEBUG_MAIN_VOID
+int real_main(void);
+#define CALL_MAIN real_main()
+#else
+int real_main(int argc, char **argv);
+#define CALL_MAIN real_main(argc, argv)
+#endif
+
+int main(int argc, char **argv)
+{
+#ifdef MEMDEBUG_MAIN_VOID
+    (void)argc;
+    (void)argv;
+#endif
+    
+#ifdef MEMDEBUG_OUTPUT_LOG
+    size_t filename_sz = 64 + sizeof(MEMDEBUG_OUTPUT_DIR) + sizeof(MEMDEBUG_OUTPUT_FMT);
+    char *filename = malloc(filename_sz);
+    if(!filename) return -ENOMEM;
+    
+    memset(filename, 0, filename_sz);
+    snprintf(filename, filename_sz, MEMDEBUG_OUTPUT_DIR"/"MEMDEBUG_OUTPUT_FMT, time(NULL));
+    
+    _memdebug_fp = fopen(filename, "w");
+    if(!_memdebug_fp) {
+        perror(filename);
+        free(filename);
+        return errno;
+    }
+
+    int ret = CALL_MAIN;
+    
+    fclose(_memdebug_fp);
+    free(filename);
+    return ret;
+#else
+    _memdebug_fp = stdout;
+    return CALL_MAIN;
+#endif
+}
+
+#define main real_main
+
+#endif
+
+#define __MEMDEBUG_CALL(f, ...) f(__VA_ARGS__, __FILE__, __LINE__)
+
+#define malloc(size)        __MEMDEBUG_CALL(__memdebug_malloc,         size)
+#define calloc(nmemb, size) __MEMDEBUG_CALL(__memdebug_calloc,  nmemb, size)
+#define realloc(ptr, size)  __MEMDEBUG_CALL(__memdebug_realloc, ptr,   size)
+#define free(ptr)           __MEMDEBUG_CALL(__memdebug_free,    ptr)
+
+#endif
diff --git a/src/value.c b/src/value.c
new file mode 100644
index 0000000..233b83c
--- /dev/null
+++ b/src/value.c
@@ -0,0 +1,159 @@
+#include <stdlib.h>
+#include <string.h>
+
+#include "common.h"
+#include "value.h"
+#include "lexer.h"
+
+// TODO:
+// - create VALUE_MANAGE_TABLE which manages
+//   both creation and destruction
+// - check the buffer size in cons creation
+
+// FIX:
+// - remove warning for void pointer cast at line 30
+
+#define NOT_IMPLEMENTED() die("Not Implemented. ABORTING")
+
+const char * const value_type_string[] = {
+    VALUE_TYPES(TO_STRING)
+};
+
+#define VALUE(_value) (_value)->value
+
+#define FN(fn, ...)   fn(buf, buf_sz, __VA_ARGS__)
+#define VALUE_STRING_TABLE(X, v, buf, buf_sz)             \
+    X(VALUE_NIL,  FN(snprintf, "(nil)"))                  \
+    X(VALUE_ATOM, FN(snprintf, "%s", VALUE(v).atom))      \
+    X(VALUE_STR,  FN(snprintf, "%s", VALUE(v).str))       \
+    X(VALUE_INT,  FN(snprintf, "%d", VALUE(v).num))       \
+    X(VALUE_CONS, FN(cons_print, &VALUE(v).cons))         \
+    X(VALUE_PROC, FN(proc_print, &VALUE(v).proc))         \
+    X(VALUE_PROC_BUILTIN,                                 \
+      FN(snprintf, "%p", *(void **)&VALUE(v).proc_builtin.proc))
+
+#define DR(value) (--(value)->refs == 0)
+#define VALUE_DESTROY_TABLE(X, v)                           \
+    X(VALUE_NIL,  (void)DR(v))                              \
+    X(VALUE_ATOM, if(DR(v)) free(VALUE(v).atom))            \
+    X(VALUE_STR,  if(DR(v)) free(VALUE(v).str))             \
+    X(VALUE_INT,  (void)DR(v))                              \
+    X(VALUE_CONS, (void)DR(v);                              \
+        value_destroy(VALUE(v).cons.left);                  \
+        value_destroy(VALUE(v).cons.right))                 \
+    X(VALUE_PROC, if(DR(v)) proc_destroy(&VALUE(v).proc))   \
+    X(VALUE_PROC_BUILTIN, (void)DR(v))
+
+#define CASE_RETURN_APPLY(vtype, apply) \
+    case vtype: return apply;
+#define CASE_APPLY_BREAK(vtype, apply)  \
+    case vtype: apply; break;
+
+static int cons_print(char *buf, size_t buf_sz, struct cons *cons);
+static int proc_print(char *buf, size_t buf_sz, struct proc *proc);
+
+// static value_t proc_create(...);
+static void proc_destroy(struct proc *proc);
+
+value_t value_create(enum value_type type, void *value)
+{
+    value_t _value = malloc(sizeof(*_value));
+    _value->type = type;
+    if(value != NULL)
+        _value->value = *(union value_union *)value;
+    _value->refs = 1;
+
+    return _value;
+}
+
+void value_destroy(value_t value)
+{
+    if(!value) return;
+       
+    switch(value->type) {
+        VALUE_DESTROY_TABLE(CASE_APPLY_BREAK, value);
+    }
+
+    if(value->refs == 0)
+        free(value);
+}
+
+#define STR_ALLOC_COPY(dest, str) do {    \
+        size_t len = strlen(str) + 1;     \
+        dest = malloc(len);               \
+        memcpy((dest), (str), len);       \
+    } while(0)
+
+value_t value_from_token(struct token *token)
+{   
+    switch(token->type)
+    {
+    case TOKEN_ID:  ;
+        char *atom = NULL;
+        STR_ALLOC_COPY(atom, token->value.id);
+        return value_create(VALUE_ATOM, &atom);
+    case TOKEN_STR: ;
+        char *str = NULL;
+        STR_ALLOC_COPY(str, token->value.str);
+        return value_create(VALUE_STR, &str);
+    case TOKEN_INT:
+        return value_create(VALUE_INT, &token->value);
+    default:
+        err("Cannot turn token '%s' to a value",
+            token_type_string[token->type]);
+        return VALUE_EMPTY;
+    }
+}
+
+value_t value_copy(value_t value)
+{
+    if(!value) return value;
+    
+    value->refs++;
+    
+    if(value->type == VALUE_CONS) {
+        value_copy(value->value.cons.left);
+        value_copy(value->value.cons.right);
+    }
+    
+    return value;
+}
+
+int value_string(value_t value, size_t buf_sz, char *buf)
+{
+    if(!value) return snprintf(buf, buf_sz, "(empty)");
+                   
+    switch(value->type) {
+        VALUE_STRING_TABLE(CASE_RETURN_APPLY, value, buf, buf_sz)
+    }
+
+    return 0;
+}
+
+static int cons_print(char *buf, size_t buf_sz, struct cons *cons)
+{
+    // TODO: check for size and off by one errors
+    int offset = 0;
+    buf[offset++] = '(';
+    offset += value_string(cons->left, buf_sz-offset, buf+offset);
+    buf[offset++] = ' ';
+    buf[offset++] = '.';
+    buf[offset++] = ' ';
+    offset += value_string(cons->right, buf_sz-offset, buf+offset);
+    buf[offset++] = ')';
+
+    return offset;
+}
+
+static int proc_print(char *buf, size_t buf_sz, struct proc *proc)
+{
+    (void)buf; (void)buf_sz;
+    (void)proc;    
+    NOT_IMPLEMENTED();
+}
+
+static void proc_destroy(struct proc *proc)
+{
+    (void)proc;
+    NOT_IMPLEMENTED();
+}
diff --git a/src/value.h b/src/value.h
new file mode 100644
index 0000000..c2f43e3
--- /dev/null
+++ b/src/value.h
@@ -0,0 +1,66 @@
+#ifndef VALUE_H
+#define VALUE_H
+
+#include "lexer.h"
+#include "env.h"
+
+typedef struct value * value_t;
+#define VALUE_EMPTY NULL
+
+typedef value_t (*builtin_proc_t)(value_t *args);
+
+#define VALUE_TYPES(X)         \
+    X(VALUE_NIL)               \
+    X(VALUE_ATOM)              \
+    X(VALUE_STR)               \
+    X(VALUE_INT)               \
+    X(VALUE_CONS)              \
+    X(VALUE_PROC)              \
+    X(VALUE_PROC_BUILTIN)      
+
+#define TO_ENUM(type) type,
+#define TO_STRING(type) #type,
+
+extern const char * const value_type_string[];
+        
+struct value {
+    enum value_type {
+        VALUE_TYPES(TO_ENUM)
+    } type;
+
+    union value_union {
+        char *atom;
+        char *str;
+        int   num;
+
+        struct cons {
+            value_t left;
+            value_t right;
+        } cons;
+
+        struct proc {
+            size_t argc;
+            value_t *arg_keys;
+            env_t parent_env;
+            
+            size_t body_len;
+            struct token *body;
+        } proc;
+
+        struct proc_builtin {
+            size_t argc;
+            builtin_proc_t proc;
+        } proc_builtin;
+    } value;
+
+    size_t refs;
+};
+
+value_t value_create(enum value_type type, void * value);
+void value_destroy(value_t value);
+
+value_t value_from_token(struct token *token);
+value_t value_copy(value_t value);
+int value_string(value_t value, size_t buf_sz, char *buf);
+
+#endif