NoExcess

NoExcess is a scheme-like programming language that is written in C. The goal of this project is to create a stripped down version of scheme that with a minimal set of built-in functions that work with the built-in datatypes. Users can make their own versions of NoExcess by writing macros that alter the way the language is written. I wrote the bulk of this thing in a caffeine binge of three days. It's a pretty cool program!

The language is currently not ready for release, although you can play around with it and most things will work.

You can get the program here:

If you still have problems getting the copies of the software, you can browse my git frontend for the software names.

Explanation

This language was made by separating the interpretation into three phases: the tokenization, the parsing, and the visiting. The tokenizer takes the input file and groups characters into structures called tokens. This groups characters together in order to treat things as single objects. For example, the number 1582.3 should be read as a single number rather than a string of characters.

The parser was done via recursive descent. Basically, the parser takes the tokens and converts them into abstract syntax tree nodes. The abstract syntax tree is a hierarchy of data which determines the order of the later execution of the program. It recursively goes through the tokens, trying to find certain patterns in the tokens and identifying them to be certain program objects.

During the parsing phase, variables are stored in a hash table and they are set equal to an abstract syntax tree. Later, this table of global variables will be sent to the visitor to be evaluated.

After the parsing phase is finished, the visitor phase evaluates the abstract syntax tree. It traverses the tree until it gets to the bottom of it, in which case it returns another abstract syntax tree that corrolates to the value that each node evaluates to. There are several self evaluating types in this language which return themselves when evaluated, and there are others that have different rules for what they evaluate to. This is defined in the visitor.

When a function is evaluated, each function argument is evaluated as well which is then put on a stack of hash tables. In this way, I have programmed a simulated stack frame like ones found in C, and recursion is then possible. Symbols in this language get evaluated to what they are bound to (you can bind symbols to expressions via the `bind` keyword, and local variables also get evaluated in the same way via the stack frame).