How much lisp to implement in C before writing the extension in itself?

I am implementing a lisp interpreter in C, I have implemented along with several primitives like cons, car, cdr, eq, basic arithmetic stuff.

Just before I started implementing define and lambda, it occurred to me that I needed to implement an environment. I'm not sure if I can implement it directly in lisp.

I intend to implement a minimal amount of lisp so that I can write an extension to the language by itself. I'm not sure how minimal this is, will FFI Qualify be minimal?


source to share

3 answers

The answer to your question depends on the meaning you give to the word "minimum".

Given your question, and assuming you don't want an implementation to compete with the current exact implementations of Common Lisp and Schema, my hypothesis is that with the minimum value you intend: Turing complete , capable of expressing any computation expressed in a programming language general purpose.

Under this assumption, you need to implement three other things:

  • conditional forms ( cond

  • lambda expressions ( lambda

  • a way to define a recursive lambda expression ( labels

    or defun


Then your interpreter should be able to evaluate the forms. This should be sufficient for the language to be equivalent to the original LISP , which allows any computable function to be expressed in the language.



First, you are talking about the first writing of the LISP interpreter. You have many options to take when it comes to scoping, LISP1 versus LISP2, as these questions change the core of the implementation. An interpreter is a general purpose program that reads and evaluates code. It can support abstractions, but it won't expand to create more native materials.

If you are interested in stuff like this, you can probably make a compiler. For example. there are many Sceme subsets that compile to C or Java code, but you can create your own virtual machine. So it can actually compile itself on its own target machine (self-hosting) if all the forms and procedures you use were implemented using primitives supported by the compiler.

Creating a dumb compiler is not much different from creating an interpreter. This is very clear if you watched the SICP video (10A is the compilation, 7A-B is the translators)

The environment can be a chain of pairs, as in the LISP interpreter. It would be difficult to implement an environment in LISP without making it a very difficult LISP language to use (unless it's compiled) However, you can use LISP data structures and primitives from C code.

Creating an FFI is a quick way to provide your language with many features. It solves the chicken and egg problem by using other people working in your language. In swimming trunks, the top (primitives and syntax) and bottom (runtime) of your system. It is a final primitive, and you can think of it as a system call or message bus at runtime.



I highly recommend reading The Queinnec: Lisp Book In Small Parts . This is a book entirely devoted to answering your question and explains in detail the many tradeoffs and internals of Lisp implementations and definitions, giving many examples of Lisp interpreters and compilers explained.

You can also use libffi . You may be interested in the insides of M. Serrano Bigloo and Hop . You can even take a look at my MELT lisp-like language to customize the GCC  compiler.

You also need to learn more about garbage collection (you can read the GC Guide ). You can use Boehm's conservative garbage collector (or something else like Qish or MPS ) or write your own GC.

You can read more about Chicken , Scheme 48 , Guile and read their docs and look into their code.

See also J.Pitrat's Blog : This isn't about Lisp (but about self-tuning strong AI) and has some fascinating entries related to self-tuning.



All Articles