Scheme interpreter in C

Reserved identifiers:

Code defines string_to_atom(), a function name prefixed with str and followed by a lowercase letter, which was reserved for use by <string.h>. So your code technically invokes undefined behavior.

@David Conrad suggests changing it to atom_from_string() instead.

For Clang, use -Wreserved-identifier to get a warning for such cases. GCC has no equivalent flag.

Each call to malloc() and family should have a corresponding call to the free() function:

In append_char(), we have a call to realloc():

void append_char(char **str, size_t *len, size_t *cap, char ch) {
    if (*len + 1 >= *cap) {
        *cap = (*cap == 0) ? 1 : (*cap * 2);
        *str = realloc(*str, *cap);

But there is no corresponding call to free(). Your interpreter is never freeing the memory it allocates. Consider running the executable with the valgrind program to find such leaks.

About fixing the leak, you need to call free() in read_token() after string_to_atom() returns.

Remove unused variable:

In defvar(), you have:

if (cons_cells[vars].id == vid) {
        int oid = car(vals);
        cons_cells[vals].car = aval;
        return var;

As oid is never used, elide it.

Incorrect format specifier:

Compiling with GCC 14.1 with -Wall -Werror -Wexta, I get:

<source>: In function 'write_obj':
<source>:414:16: error: format '%lld' expects argument of type 'long long int', but argument 2 has type 'int64_t' {aka 'long int'} [-Werror=format=]
  414 |     printf("%lld", cons_cells[s].id);
      |             ~~~^   ~~~~~~~~~~~~~~~~
      |                |                |
      |                long long int    int64_t {aka long int}
      |             %ld

The fix is simple is to use the correct format specifier, PRIu64. Note that the code currently invokes undefined behavior due to a mismatch between the format specifier and the corresponding argument.

A label can only be part of a statement and a declaration is not a statement:

In read_token(), you have:

default:
      char *s = NULL;

Prior to C23, a label (cleanup:) is not allowed to appear immediately before a declaration (such as char *str ...;), only before a statement (printf(...);).

You can put a semicolon immediately after the label's colon for an empty statement.

Signed to unsigned conversions:

GCC reports a lot of these, I'd simply show the warnings:

In function 'string_to_atom':
<source>:207:13: warning: conversion to 'size_t' {aka 'long unsigned int'} from 'long int' may change the sign of the result [-Wsign-conversion]
  207 |         y = endptr - s;
      |             ^~~~~~

and:

<source>:283:43: warning: conversion from 'int' to 'char' may change value [-Wconversion]
  283 |       append_char(&s, &length, &capacity, c);
      |                                           ^
<source>:289:45: warning: conversion from 'int' to 'char' may change value [-Wconversion]
  289 |         append_char(&s, &length, &capacity, tolower(c));
      |                                             ^~~~~~~~~~

and:

<source>: In function 'apply':
<source>:737:32: warning: conversion from 'int64_t' {aka 'long int'} to 'int' may change value [-Wconversion]
  737 |             if (cons_cells[car(a)].id != f)
      |                                ^
<source>:739:21: warning: conversion from 'int64_t' {aka 'long int'} to 'int' may change value [-Wconversion]
  739 |             a = cdr(a);
      |                     ^
<source>:774:33: warning: conversion from 'int64_t' {aka 'long int'} to 'int' may change value [-Wconversion]
  774 |             int current_value = cons_cells[car(a)].id;
      |                                 ^~~~~~~~~~
<source>: In function 'eval_obj':
<source>:816:17: warning: conversion from 'int64_t' {aka 'long int'} to 'int' may change value [-Wconversion]
  816 |         int x = cons_cells[car(id)].id;
      |                 ^~~~~~~~~~
<source>:875:37: warning: conversion from 'int64_t' {aka 'long int'} to 'int' may change value [-Wconversion]
  875 |             cons_cells[p].car = cdr(vid);
      |                                     ^~~
<source>:877:31: warning: conversion from 'int64_t' {aka 'long int'} to 'int' may change value [-Wconversion]
  877 |             return defvar(car(vid), p, env);
      |                               ^~~
<source>:879:23: warning: conversion from 'int64_t' {aka 'long int'} to 'int' may change value [-Wconversion]
  879 |         return defvar(vid, eval_obj(aval, env), env);
      |                       ^~~
<source>:897:33: warning: conversion from 'int64_t' {aka 'long int'} to 'int' may change value [-Wconversion]
  897 |     return lookup(cons_cells[id].id, env);
      |                   ~~~~~~~~~~~~~~^~~

Always compile with warnings enabled. I would suggest:

-std=c23 -g3 -ggdb -no-pie -Wall -Wextra -Warray-bounds -Wconversion -Wformat-signedness -Wmissing-braces -Wno-parentheses -Wpedantic -Wstrict-prototypes -Wwrite-strings -Winline -s -fno-builtin -fno-common -fno-omit-frame-pointer -fsanitize=float-cast-overflow -fsanitize=address -fsanitize=undefined -fsanitize=leak

Though, you no longer have to remember format specifiers like PRIu32 et cetera. C23 has introduced:

wN Specifies that a following b, B, d, i, o, u, x, or X conversion specifier applies to an integer argument with a specific width where N is a positive decimal integer with no leading zeros (the argument will have been promoted according to the integer promotions, but its value shall be converted to the unpromoted type); or that a following n conversion specifier applies to a pointer to an integer type argument with a width of N bits. All minimum-width integer types (7.22.1.2) and exact-width integer types (7.22.1.1) defined in the header <stdint.h> shall be supported. Other supported values of N are implementation-defined.

wfN Specifies that a following b, B, d, i, o, u, x, or X conversion specifier applies to a fastest minimum-width integer argument with a specific width where N is a positive decimal integer with no leading zeros (the argument will have been promoted according to the integer promotions, but its value shall be converted to the unpromoted type); or that a following n conversion specifier applies to a pointer to a fastest minimum-width integer type argument with a width of N bits. All fastest minimum-width integer types (7.22.1.3) defined in the header <stdint.h> shall be supported. Other supported values of N are implementation-defined.

So %w32d for int32_t, %w64d for int64_t, and so on.

Functions from <ctype.h> expect a value in the unsigned char or EOF range:

In string_to_atom(), you have:

// Check if the string represents a number
if ((s[0] == '-' && isdigit(s[1])) || isdigit(s[0])) {

According to the ISO C standard:

7.4

1 The header <ctype.h> declares several functions useful for classifying and mapping characters. In all cases the argument is an int, the value of which shall be representable as an unsigned char or shall equal the value of the macro EOF. If the argument has any other value, the behavior is undefined.

The cast to unsigned char ensures calling isalpha() does not invoke Undefined Behaviour.

Casting a char to an unsigned char works for 2's complement, but not other rare encodings. Accessing the characters via unsigned char * is best. (This is not a problem in C23.)

fflush(stdin) is undefined behavior:

From 7.23.5.2 The fflush function, ISO/IEC 9899:2024:

2 If stream points to an output stream or an update stream in which the most recent operation was not input, the fflush function causes any unwritten data for that stream to be delivered to the host environment to be written to the file; otherwise, the behavior is undefined.

printf("]=> ");
fflush(stdin);

But this was likely meant to flush standard output, so it is an small fix.

Empty argument list vs void in function declarations:

In C:

• void foo() means "a function foo taking an unspecified number of arguments of unspecified type".
• void foo(void) means "a function foo taking no arguments"

C23 adopted C++'s semantics, so an empty argument list now means that the function takes no arguments, and () is once again fine to use. And those who have lived underneath a rock for 25 years need not worry either.

I do not believe this code is using C23, so I'd suggest adding void everywhere.

Only declare as many variables as you require:

/**
 * Creates an empty environment with no variable bindings.
 *
 * @return The identifier of the empty environment.
 */
int empty_environment()
{
    int vars = 0, vals = 0;
    int frame = alloc_cons(vars, vals);
    return alloc_cons(frame, 0);
}

vars, vals, and frame are not referenced again. So it can be simplified to:

return alloc_cons(alloc_cons(0, 0), 0);

Redundant documentation:

/**
 * Returns the 'car' (first element) of the 'cdr' (rest) of the 'cdr' (rest) of
 * the 'cdr' (rest) of a cons cell identified by its ID.
 *
 * @param id The ID of the cons cell.
 * @return The 'car' of the 'cdr' of the 'cdr' of the 'cdr'.
 */

Why are we stating what it returns twice? The function has only 1 line of code, but 7 lines of comments. Same goes for other functions.

Consider linking to some official specification, @J_H suggests Steele, and removing this fluff.

After removing the comments:

int car(int id)
{
    return cons_cells[id].car;
}

int cdr(int id)
{
    return cons_cells[id].cdr;
}

int cadr(int id)
{
    return car(cdr(id));
}

int cddr(int id)
{
    return cdr(cdr(id));
}

int caddr(int id)
{
    return car(cdr(cdr(id)));
}

int cdddr(int id)
{
    return cdr(cdr(cdr(id)));
}

int cadddr(int id)
{
    return car(cdr(cdr(cdr(id))));
}

Or even simpler, and shorter:

int car(int id)    { return cons_cells[id].car;     }
int cdr(int id)    { return cons_cells[id].cdr;     }
int cadr(int id)   { return car(cdr(id));           }
int cddr(int id)   { return cdr(cdr(id));           }
int caddr(int id)  { return car(cdr(cdr(id)));      }
int cdddr(int id)  { return cdr(cdr(cdr(id)));      }
int cadddr(int id) { return car(cdr(cdr(cdr(id)))); }

Note that cdddr() can use cddr(cdr(id)) instead of cdr(cdr(cdr(id))), and cadddr() can use car(cdddr(id)) instead of car(cdr(cdr(cdr(id)))), and so on.

But note: It is common for a scheme to evaluate an init.scm source file before displaying a REPL prompt. It might set up various important language features, perhaps defined in a SRFI; cf "Many ... syntactic forms of the language are now part of the (rnrs base (6)) library" – @J_H.

Having large static arrays can cause running process to be bloated:

/**
 * Allocates a new memory cell and returns its identifier.
 *
 * @return The identifier of the newly allocated memory cell.
 */
int alloc()
{
    return hptr++;
}

What is being "allocated" here? This simply increments a counter and returns.

Looks like you're keeping two file-scope arrays with external linkage:

int hptr = 10;

#define TABLE_SIZE 999983
cons_cell cons_cells[TABLE_SIZE];
const char *atom_table[TABLE_SIZE];

Firstly, these should both have internal linkage, i.e. be prefixed with the static keyword. Secondly, there is never a need to allocate 999983 bytes and 999983 pointers. Do not fear dynamic memory allocation. These arrays might never get fully populated (wasting memory), or they might overflow, because there is no check, and the program would then invoke undefined behavior. See also: How do global variables contribute to the size of the executable?.

Consider what happens when you run out of cells. Where would the new cells go? I would suggest using malloc() and realloc(). Start with a decent size, and then regrow exponentially each time the arrays get full.

Beside that, an int may only have 16 bits, in which it would not be able to hold values up to TABLE_SIZE. I would suggest removing all instances of int with exact-width standard integer types like int32_t, uint32_t, int64_t et cetera.

Also note that if hptr was to overflow, your code would invoke undefined behavior, because signed integer overflow is undefined behavior.

exit(0) indicates success:

#define show_error(...) do { fprintf(stderr, __VA_ARGS__); exit(0); } while(0)

Instead of exiting with magic numbers, use EXIT_SUCCESS and EXIT_FAILURE from <stdlib.h>.

Problems with string_to_atom():

    size_t n = strlen(s);
    size_t y = 0;
    int64_t nval = 0;
    
    // Check if the string represents a number
    if ((s[0] == '-' && isdigit(s[1])) || isdigit(s[0])) {
        char *endptr;
        nval = strtoll(s, &endptr, 0);
        y = endptr - s;
    }

Firstly, strlen() can return 0 if the first character was '\0'. You did not check for that case. Furthermore, s[1] and [0] might be out of bounds, in which case your program would invoke undefined behavior. Moreover, strtoll() can fail:

The strtol() function returns the result of the conversion, unless the value would underflow or overflow. If an underflow occurs, strtol() returns LONG_MIN. If an overflow occurs, strtol() returns LONG_MAX. In both cases, errno is set to ERANGE. Precisely the same holds for strtoll() (with LLONG_MIN and LLONG_MAX instead of LONG_MIN and LONG_MAX).

Potential integer overflow:

In append_char(), we have:

void append_char(char **str, size_t *len, size_t *cap, char ch) {
        if (*len + 1 >= *cap) {
            *cap = (*cap == 0) ? 1 : (*cap * 2);
            *str = realloc(*str, *cap);
            if (*str == NULL) {
                perror("Failed to allocate memory");
                exit(EXIT_FAILURE);
            }
        }
        (*str)[(*len)++] = ch;
        (*str)[*len] = '\0';
}

The unchecked multiplication *cap * 2 poses a significant risk. If an overflow occurs, the result will wrap around, leading to fewer allocated bytes than intended. This could result in the program continuing execution without recognizing the error.

Consider using C23's ckd_mul() function from <stdckint.h>. Both GCC 14.1 and Clang 18.1 implement it.

But then the additions *len + 1 and (*len)++ can also overflow. These could use ckd_add().

And to run cleanly under valgrind, free the allocated memory before calling exit(EXIT_FAILURE). Though ideally, I'd prefer seeing a return EXIT_FAILURE from main().

Lying comments:

We have a copy-paste error here:

/**
 * Returns the 'car' (first element) of the 'cdr' (rest) of a cons cell
 * identified by its ID.
 *
 * @param id The ID of the cons cell.
 * @return The 'car' of the 'cdr'.
 */
int cadr(int id)
{
    return car(cdr(id));
}

/**
 * Returns the 'car' (first element) of the 'cdr' (rest) of a cons cell
 * identified by its ID.
 *
 * @param id The ID of the cons cell.
 * @return The 'car' of the 'cdr'.
 */
int cddr(int id)
{
    return cdr(cdr(id));
}

Both cadr() and cddr() have the same documentation. cddr() lies, it does not return the "'car' (first element) of the 'cdr'...". It returns the 'cdr' of the 'cdr'...

Documentation is appreciated and wonderful. Wrong documentation is frowned upon and frustrating.

Wrong usage of realloc():

In append_char():

*str = realloc(*str, *cap);

If realloc() returned a null pointer, you would lose the only reference to the original allocation and leak memory. Consider doing:

void *const tmp = realloc(*str, *cap);

if (tmp) {
    *str = tmp;
} else {
    free(str);
    // Now exit
}

Check for EOF:

int read_token()
{
    int c;
    for (;;) {
    c = getchar();
    while (isspace(c))
        c = getchar();

c might be EOF, in which case you would keep looping. Consider moving this to a helper function named skip_whitespace() or similar.

Prefer unsigned types over signed types:

You're using an int everywhere for holding sizes and indices. It is not possible for an index or size to be signed. I'd suggest using size_t.

Format your code:

As is, the code is very hard to read and understand (I skipped most of it due to bad formatting), the braces are all over the place, and there is a lot of unnecessary vertical whitespace, which again hinders readability.

Consider using an automatic code formatter like clang-format, GNU Indent, Astyle, et cetera.

Prefer enum to #define:

#define TOK_NIL 0
#define TOK_ERROR 1
#define TOK_OPEN 2
#define TOK_CLOSE 3
#define TOK_QUOTE 4
#define TOK_DOT 5

can be:

enum tokens {
    TOK_NIL,
    TOK_ERROR,
    TOK_OPEN,
    TOK_CLOSE,
    TOK_QUOTE,
    TOK_DOT,
};

This has four benefits:

• Under a debugger, you'd not see magic values like 0, 1, 2, but named constants like TOK_OPEN, TOK_CLOSE, et cetera.

• If you miss some value in a switch statement, the compiler would likely warn about it (assuming there is no default, which often hinders the warning).

• Functions, like read_token(), that return one of the token values can specify the return type to be enum tokens, or just tokens (assuming you create an alias with typedef), instead of int.

• You can give the enum a type in C23 and above. Macros are simple text replacements, and are type-less.

Simplify:

// int64_t sum = (cons_cells[id].id == PPLUS) ? 0 : 1;

int64_t sum = !(cons_cells[id].id == PPLUS);

Global state and missing unit tests:

As is, the code appears very brittle and keeps a global state, which makes it almost untestable. Code that is not tested, and is untestable, is unreliable code.

I'd suggest making a struct containing all the global variables and then passing it around to the functions that require it. And then writing tests for each function. You do not need something complicated, simple assertions (assert() from <assert.h>) often do.

Then write a Makefile with the following targets:

• make debug - this would build the default executable with a strict set of warnings and debugging flags enabled, along with static analyzers and sanitizers (-g3 -ggdb -Werror -Wextra -pedantic-errors et cetera).
• make release - this would build the default executable with optimizations enabled and assertions disabled (-O3 -s -NDEBUG et cetera).
• make test - this would run all the unit tests (that are yet to be written).
• make format - this would automatically format the code with one of the afore-mentioned code formatters.
• make valgrind - this would rebuild the executable without the sanitizers and analyzers (valgrind and AddressSanitizer et cetera do not work together) and then run the executable under the valgrind program.

This translation unit also seems to have an implementation of a hash table. You could move that to a different .c file, and then include the function prototypes with a corresponding .h file. It would decrease the lines of code one has to deal with at a time, make the hash table reusable in other projects, separate the implementation from its use, and allow it to be tested separately from the interpreter.

Also consider giving the user another chance on a syntax error. Python's REPL does not exit when I input some invalid code. It instead offers me a helpful error message and allows me to input again. If some interpreter keeps exiting on syntax errors, I at least would not be very open to using it.

Around line 300 of this source code I gave up fixing the indentation to see what was what.

Code Review:

Not terribly easy for the reader to follow making its logic "over the horizon" for analysis...

Minimal suggested fix: Use whitespace appropriately and consistently... Also, presume w-i-d-e monitors being used. Gone are the days of 24x80 screens doing code development. (Keep width used within reason, of course!) Hiding nested indents by not indenting is deceptive. Write clean, clear, and especially correct code.

One function examined:

Cutting just the code of apply() and pasting it into an empty file, we see 149 lines of quite unreadable code; unreadable owing to flagrant disregard for indentation.

Below is my attempt to make sense of apply(), requiring only 103 lines of code. (I hope I've not made any "Oops!" mistakes while modifying the OP's code here.) Some comments attempt to highlight some of the compressions made.

This snippet is presented merely to indicate how proper indentation and an aversion to unnecessary curly braces can shrink the volume of long, linear code enabling the readers to perform "spot checks" and otherwise assess program flow. If roughly 30% of the compilable code code be removed or compressed, a source of 1000 lines might be more palatable.

I applaud the code's terse variable and function names. Those who enter must commit to making an effort to understand the coder's rationale and its use. Otherwise, any program listing is no more than ASCII art.

To taste, one blank line between each case : body would be nice. Left to the reader to decide...

int apply( int id, int args ) { // consistent brace location
    if ( cons_cells[id].type == BT_FUNCTION ) {
        int params = car(id);
        int body = cadr(id);
        int procenv = cddr(id);
        int env = alloc_cons(alloc_cons(params, args), procenv);
        for( ; cdr(body); body = cdr(body) ) // for(), not while()
            eval_obj(car(body), env);
        return eval_obj(car(body), env);
    }

    if (cons_cells[id].type != BT_BUILTIN) { // early exit. 1 level of indent saved
        show_error("bad application: not a function");
        return TOK_ERROR;
    }

    switch (cons_cells[id].id) {
        case PPLUS:
        case PTIMES: {
            int op = cons_cells[id].id;
            int64_t sum = (op == PPLUS) ? 0 : 1;

            for (int a = args; a; a = cdr(a))
                     if (op == PPLUS) sum += cons_cells[car(a)].id;
                else if (op == PTIMES) sum *= cons_cells[car(a)].id;

            int p = alloc();
            cons_cells[p].type = BT_NUM;
            cons_cells[p].id = sum;
            return p;
        } // clearly end of local variables' existence
        case PNOT:  return car(args) ? 0 : atom_true;
        case PCONS: return alloc_cons(car(args), cadr(args));
        case PCAR:  return car(car(args));
        case PCDR:  return cdr(car(args));
        case PAPPLY:return apply(car(args), cadr(args));
        case PLIST: return args;
        case PREAD: return read_obj();
        case PSYMP: return cons_cells[car(args)].type == BT_ATOM ? atom_true : 0;
        case PNUMP: return cons_cells[car(args)].type == BT_NUM ? atom_true : 0;
        case PPROCP:    return  cons_cells[car(args)].type == BT_FUNCTION
                        ||      cons_cells[car(args)].type == BT_BUILTIN
                            ? atom_true // return condition true
                            : 0;        // return condition false
        case PCONSP:return cons_cells[car(args)].type == BT_CONS ? atom_true : 0;
        case PSETCAR: return cons_cells[ car(args) ].car = cadr(args);
        case PSETCDR: return cons_cells[ car(args) ].cdr = cadr(args);
        case PMINUS: {
            int64_t res = cons_cells[car(args)].id;
            int rargs = cdr(args);
            if (!rargs) res = -res; // simple negation
            else for ( ; rargs; rargs = cdr(rargs) ) // for(), not while()
                    res -= cons_cells[car(rargs)].id;

            int p = alloc(); // common code NOT duplicated
            cons_cells[p].id = res;
            cons_cells[p].type = BT_NUM;
            return p;
        }
        case PEQUAL: {
            if (args) {
                int64_t f = cons_cells[car(args)].id;
                for( int64_t a = cdr(args); a; a = cdr(a) )
                    if (cons_cells[car(a)].id != f)
                        return 0;
            }
            return atom_true;
        }
        case PEQ: {
            int arg1 = car(args);
            int arg2 = cadr(args);
            if (cons_cells[arg1].type != cons_cells[arg2].type) return 0;
            switch (cons_cells[arg1].type) {
                case BT_NUM:
                case BT_FUNCTION:
                case BT_BUILTIN:
                case BT_ATOM:
                    return cons_cells[arg1].id == cons_cells[arg2].id ? atom_true : 0;
                default: // default? Or move outside of switch()?
                    return arg1 == arg2 ? atom_true : 0;
            }
        }
        case PLT:
        case PGT:
        case PLEQ:
        case PGEQ: {
            if (!args) return atom_true;

            int64_t f = cons_cells[car(args)].id;
            for( int a = cdr(args); a; a = cdr(a) ) {
                int current_value = cons_cells[car(a)].id;

                if ((cons_cells[id].id == PLT && f < current_value)
                ||  (cons_cells[id].id == PGT && f > current_value)
                ||  (cons_cells[id].id == PLEQ && f <= current_value)
                ||  (cons_cells[id].id == PGEQ && f >= current_value))
                    f = current_value;
                else return 0;
            }
            return atom_true;
        }
    }
}

Looking at this again, I'd suggest moving those (quite independent) operations involving automatic variables and several lines of code each into its own tiny "helper function". Then apply() would be much more a simple switch() that fits on one screen, and each case : could be evaluated independently. A reader reads code at varying levels of magnification, sometimes up close and sometimes gaining an overview. Make your readers happy!

Below is one such helper function, untested:

int apply_plus_mult( int id, int args ) {
    int op = cons_cells[id].id;
    int64_t sum = (op == PPLUS) ? 0 : 1;

    for (int a = args; a; a = cdr(a))
             if (op == PPLUS) sum += cons_cells[car(a)].id;
        else if (op == PTIMES) sum *= cons_cells[car(a)].id;

    int p = alloc();
    cons_cells[p].type = BT_NUM;
    cons_cells[p].id = sum;
    return p;
}

And it is called from within apply() via switch():

    switch (cons_cells[id].id) {
        case PPLUS:
        case PTIMES: return apply_plus_mult( id, args );
        case PNOT: return car(args) ? 0 : atom_true;
        ...

AND, after another look, it becomes apparent that much of the complexity of my apply_plus_mult() is attributable to "packing two different operations into one function".

Splitting the function into two separate, and even more trivial functions would make reading and checking even simpler. Follow KISS principles.

int store( int64_t val ) {
    int p = alloc();
    cons_cells[p].type = BT_NUM;
    cons_cells[p].id = val;
    return p;
}

int apply_plus( int args ) {
    int64_t v = 0;
    for (int a = args; a; a = cdr(a)) v += cons_cells[car(a)].id;
    return store( v );
}

int apply_mult( int args ) {
    int64_t v = 1;
    for (int a = args; a; a = cdr(a)) v *= cons_cells[car(a)].id;
    return store( v );
}

int apply( int id, int args ) {
    ...

    switch (cons_cells[id].id) {
        case PPLUS:  return apply_plus( args );
        case PTIMES: return apply_mult( args );
        case PNOT:  ...