DietLISP

DietLISP is an interpreter for an untyped Lisp variant written in Haskell. This is a toy project that I started working on during my winter break in the Doon valley.

The Language

DietLISP is a minimalist, lazy, purely functional lisp. It does not have a static type system. The distinguishing feature of DietLISP is that all executable forms in it are semi-operatives.

Semi-Operatives

The notion of a semi-operative is similar to that of an operative in the Kernel programming language. Semi-operatives combine macros and functions into one unified concept but are more restrictive than fexprs.

I like to describe a semi-operative as a hook into the denotational semantics of the interpreter. You see, in a regular lisp, functions don't directly influence the interpreter and macros are hooks into the parser. Semi-operatives go a little deeper and we get a macro-function hybrid.

A semi-operative, like a macro, gets the bits of AST it has been invoked with, and (unlike a macro) the environment where it was invoked. It has access to functions that evaluate an AST in a specific environment (eval and eval*), and functions to extend the environment (add-binding). The result of the semi-operative invocation is the value (rather, the domain value) the interpreter gets by executing the semi-operative. I think it is useful to think of semi-operatives as hooks that arbitrarily map program phrases into domain values.

As an example of what this makes possible, look at samples/SimpleOperatives.dlisp:

;; The #builtin# directives return an semi-operative defined inside
   the interpreter in Haskell.  global-bind binds them to the global
   lexical scope.
(global-bind let (#builtin# #let#))
(global-bind eval (#builtin# #eval#))

(global-bind wormhole (operative () env (eval env x)))

(let (x 42) (wormhole)) ;; Prints 42, since wormhole evaluates x in
  the environment inside let x (42)

eval (ast, env) evaluates ast in the environment env. eval* (ast, env) evaluates ast in the context of the current environment and then evaluates this result in the context of env (ast not evaluating to an AST is an error). This allows you to write functions this way:

(operative (number) env
  (let (evaluated-number (eval* env number))
    (+ evaluated-number 5)))

In the above case, eval* first evaluates number in the current lexical scope (which gives us the AST passed to the semi-operative during evaluation) and then evaluates that ast in env (which gives us some result to which we then add 5).

Conditional evaluation makes writing macros easy. Here is a when macro:

(global-bind when
  (operative (condition action) env
    (if (eval* env condition)
      (eval* env action)
      0)))

which evaluates to action if condition evaluates to true else evaluates to 0.

Two primitives useful when writing macros are unwrap-ast and wrap-to-ast, which convert an AST to a domain value and vice-versa; respectively. A list can't be directly evaluated but needs to be wrapped into an AST before evaluation. Similarly, an AST is impervious to direct introspection till it has been unwrapped into a regular domain value.

Hopes and fears

So, will this all work out? I don't know. I have a hunch that semi-operatives might lead to a cleaner and more orthogonal language; I'll keep updating this README as I explore and learn more.

Texts

As it is probably evident by now, this is more of a academic project. I found the following texts very helpful:

• Structure and Interpretation of Computer Programs (Hal Abelson, Jerry Sussman, Julie Sussman)
• Essential of Programming Languages (Daniel P. Friedman, Mitchell Wand, Christopher T. Haynes)
• Design Concepts in Programming Languages (Franklyn Turbak, David Gifford, Mark A. Sheldon)

I'd at recommend at least the first two texts to any serious software engineer.