Sclisp

Sclisp is a toy project for learning C programming language. It's mostly based on the book Build Your Own Lisp and using mpc parser to parse the characters.

There's a few tweak that didn't exist in the book, like malloc() failure handler and using the archive library, see Highlights for more tweaks info. There's also the playground directory which contains my experiment about call stack overflow, array in function parameter, gcc builtin arithmetic overflow function, and so on.

The source code mostly using the linux kernel coding style as guidance, like no curly bracket if there's only one statement in if-else statement or using tab instead of space for indentation.

Running the REPL

You can compile the source code by running the run script like:

./run main

Or if you need some debugging information, you can use this:

./run main-debug

If you make any changes to the mpc parser, you can recompile the archive library with this:

./run mpc

After you compile the source code, you can start the REPL like this:

./sclisp

Caveats

There's a few caveats with sclisp and some them are:

1. Sclisp only tested in arch linux. So if you use another linux distro or even another operating system, you might need to tweak the source code or the run script, like the linking to readline library.

2. Sclisp using double type for the result. This is to make parsing easier by only using 1 type for the number, which can cause a problem.

3. Sclisp only tested using gcc compiler, so the code might not compile when using other compiler.

4. Sclisp depends on operating system to clean up the allocated memory when there's allocation failure or integer overflow, because we exit the program directly without doing the clean up of previous memory allocation. This is bad but i'm still not sure what is the right mechanism to do that with the interpreter.

There might be other caveats that i didn't realize yet, so be careful.

Highlights

This is the highlight of what i did differently from the book:

1. Separate the source code to sclisp.c, utils.c, utils.h. Trying to emulate the library structure with utils.c and utils.h.

2. Rather than compiling the mpc parser over and over again, we compile it once into an object file and then put that as archive library. This can safe some time during compilation process, especially if we did not change the parser frequently.

3. Handle case when allocation with malloc() or realloc() failed, which is returning NULL value, by exit the program with code 69.

4. Handle integer overflow case with gcc builtin arithmetic overflow function such as __builtin_uadd_overflow() and __builtin_addc() and exit the program with code 42.

5. Trying to implement reallocarray() from the BSD system, which basically realloc() with multiplication overflow checker (still not sure if this is the right implementation).

6. Changing the mpca_lang() and mpc_cleanup() from the mpc parser to take array and array size instead of variadic function. The problem with using variadic function with mpca_lang() is that when we forgot to put NULL at the end of the arguments and there's unknown parser name, we will get segmentation fault error. That's because there's no limit when we try to find the parser with mpca_grammar_find_parser() which will attempt to access some inaccessible memory. And by using array and array size in mpc_cleanup(), we don't need to update the arguments every time we add new parser as long as we use the same array as mpca_lang().

This is the things that i remember doing differently. There might be other things that i forgot to mention, so if you want to find out more, you can check the source code.

Side Notes

This project was mostly built on live stream at youtube. For the playlist, you can check here.

References

• Build your own lisp book.
• MPC parser.
• Linux kernel coding style.
• C reference.
• C99 rationale pdf.
• GNU history library.
• Where C string literal stored.
• Examine contents of data section in ELF file.
• Memory segments in C/C++ (youtube video).
• Understand the .bss segment in C.
• History about virtual memory (youtube video).
• Linux kernel programming language documentation.
• x86 assembly guide.
• Inline assembly in C.
• Basic integer overflow.
• GCC string literal (pdf).
• C programming static keyword.
• Build C static/archive library.
• Function call stack demo.
• GNU virtual memory documentation.
• Computer science from the bottom up.
• right-left rule to read C declaration.
• Explanation about pointer.
• Explanation about function pointer (youtube video).
• GDB Online Documentation.
• Big endian vs little endian format.