Skip to content

egorich239/lispm

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

LISPM is an implementation of a minimalistic LISP machine.

ASCII encoding is assumed. Source code can contain symbols in `[0; 126]` range.
ASCII symbol `DEL` is not permitted same as all symbols with the 8th bit set.
The language is case-sensitive: `Abc` and `abc` are different symbols.

There are three kinds of atom:
- empty list: `()`
- literals: a sequence of alphanumeric symbols or symbols `!$%&*+-./@^_`
            where the first symbol is not a number;
- unsigned numerals: decimal, no leading zeros, range `[0; 2^(M-2) - 1]`,
            where `M` is number of bits in `unsigned int`.

There are several traditional forms: `lambda`, `let`, `cond`, `quote`.
In our dialect `cond` evaluates the first branch where predicate evaluates
to anything but the empty list `()`.

There are several builtin functions: `atom?`, `eq?`, `cons`, `car`, `cdr`, `list`.
In our dialect `eq?` returns true only iff both arguments are the same atom;
if at least one of the arguments is not an atom, it will always return `()`.

There is a `panic!` builtin function that immediately terminates the evaluation,
and keeps its parameters as a context for the error, as in:
`(panic! '(the roof is on fire))`.

A lambda is a value: it binds all free variables in the body of the lambda
at the moment of its creation, i.e. when `(lambda ...)` form is evaluated.

Development principles
----------------------

- I aim to be safe: interpreting a LISP program should either end up evaluating
  the provided user function, or fail with an error, but without memory
  corruption or a segfault.
- I aim to keep the `lispm.c` core small, my guideline is less than 500 lines.
- I aim to keep the `lispm.c` core readable, although I am constantly unhappy
  about its state; in fact as of writing I am rather unhappy.
- I aim to keep the binary size of `lispm.c` text section minimal, my guideline
  is 4K in `-Oz -fomit-frame-pointer -mtune=generic` mode for x86-64.
- I aim to keep zero dependencies: it should be possible to enter the machine
  from a boot loader. The few runtime dependencies are abstracted away via
  externally provided functions.
- I aim to keep low development dependencies.

Debugging and tracing
---------------------

After having spent some early days in `gdb` (and I am a very novel user of it),
I also aim for better introspection into the state of the machine.

This is the least developed part of the machine, which I usually improve when
I suspect a simple way to avoid another GDB session with some additional
introspection into program state.

Configuration
-------------

Configuration is done using flags in `lispm.h`:
- `LISPM_CONFIG_ASSERT`: turn on (1) or off (0) assertions. An assertion can
  not be caused by user input (i.e text of the LISP program). There are three
  possible reasons for assertions:
  1) a bug in the interpreter itself;
  2) a misconfigured `lispm` symbol, as defined by `lispm_is_valid_config()`
     function;
  3) an native extension (e.g. `lrt0.c`) violating some of the assumptions.
  
  If all of those are excluded, then assertions are useless, and can be
  turned off.
- `LISPM_CONFIG_VERBOSE`: If the LISPM machine ends up in an error state,
  either because of a bug in the program, or because of resource exhaustion,
  then it returns ends with an error. When `LISPM_CONFIG_VERBOSE` is non-zero,
  the error will have much more information attached to it, including a human
  readable explanation. This verbosity is bloating the binary however, and
  hence it is possible to turn it off - in this case error state will be
  reported with a bare minimum of information.

About

a toy LISP dialect interpreter in C

Resources

License

Stars

Watchers

Forks