Scarlett -- a Kernel/Scheme interpreter

About

Scarlett is an interpreter for a language that is inspired on Kernel/Scheme. I aim to stay close to John Shutt's Kernel as presented in the R^-1RK combined with the newest Scheme standard R⁶RS. However, I don't consider these documents to be holy, even though the design principles followed in the R^-1RK are very good. The interpreter is developed in portable C++ (2011 standard). The aim is to provide an easy extension language to C++, with transparent support for numerical arrays in the tradition of Python with NumPy.

Performance in terms of speed is not a primary target. The idea is to have all underlying structures and operators defined in C++; Scarlett providing the means of putting different elements together.

News

2013/05/06: Implemented interface between C++ classes and Scarlett operative closures.
2013/05/01: New website!.

current State

Scarlett is not yet in top shape. In particular the following work needs to be done

implementing numerical tower
universal lists
continuation guards
...

the Language

Scarlett fits into a long history of Lisp variants like Scheme and Kernel. If you are not familiar with either Lisp or Scheme, I recommend to learn Scheme from the lectures by

Abelson and Sussman -- "Structure and Interpretation of Computer Programs"

as well as

Friedman and Felleisen -- "the Little Schemer" and "the Seasoned Schemer".

There are several (planned) features that deviate from the Schemes that you may know.

F-exprs

Like Kernel, we make the distinction between operative and applicative functions. Applicatives have their argument-tree mapped through eval, before being passed to the underlying operative, which applies its arguments unevaluated. Operatives should have name starting with $ and are created using $vau. To create an applicative from an operative and back, the applicatives wrap and unwrap are defined. For example, the $lambda-operative can be defined as

($define! $lambda ($vau (par-tree . body) dyn-env
    (wrap (eval (list* $vau par-tree #ignore body) dyn-env))))

Pattern matching

Scarlett supports Kernel-style formal parameter trees. This means a set of parameters can have more complicated topology than just a proper or improper list. For example, we can decompose a list into its car and cdr, by pattern matching:

($define! (lcar . lcdr) [1 2 3 4])

Resulting in lcar having value 1, and lcdr having value (2 3 4). We added some syntax candy of [items ...], which is equivalent to (list items ...), and transparent support for pair syntax, (func . lst) being the same as (apply func lst). This means we don't need the functions cons, car, cdr, list or list*; eventhough they are still defined as such. A function returning the first 12 numbers from the Fibonacci sequence from (fib [1 1] 10), can be defined as follows

($define! fib
  ($lambda ((a b . c) n)
    ($if (zero? n)
      [a b . c]
      (fib [(+ a b) a b . c] (- n 1)))))

[N(Y|E)I] There are some ideas that go even further. Using function overloading in combination with pattern matching with predicates, allows you to write programs in a formal way, without using $if-statements. This is similar, though more powerfull, to the $case-lambda construct in scheme. There are several complications, mainly in syntax. Do we allow the parameter-tree to be mixed with predicates? They would have to be predicates before evaluation. How do we mix in type-checking into this? All in all, it seems that a simple conditional is just as simple, and clear as a more complicated pattern-matching. Also an $if statement is more efficient than matching an entire pattern.

Cyclic lists

Scarlett has build-in support for cyclic lists. A bit of extra syntax:

[1 2 3 4 ...]

is equivalent to

($let ((a (list 1 2 3 4))) (encycle! a 3 1) a)

This is extremely usefull when we try to match list patterns for some function. For example an implementation of $let, may check its arguments for congruence against

(((:par-tree: :expr:) ...) :body:)

Objects

Objects are very naturally implemented in Scarlett in the form of closures.

($define! look-up
  (wrap ($vau (s) e (eval s e))))

($define! make-object 
  ($lambda ()
    ($let ((env (current-environment)))
      ($vau (method . args) #ignore
        ($cond 
	  ((combiner? (look-up method))
	   (eval [method . args] env))

	  (#t (look-up method)))))))

($let ((A (make-object)))
  (A $define! x 7)
  (A $define! f ($lambda (y) (* x y)))
  (A f (+ 4 2)))

Returning the value 42. This example can be expanded to support class definitions and inheritance. An interface to C++ objects can be implemented to mimic this style objects. Also this allows to implement multi-type operators like +, -, *, etc. transparently.

Universal lists (NYI)

Scheme has several linear structures: lists, vectors and streams. Each has its set of accessor functions. Combining different structures in a single applicative like map is not so easy. If we use the Scarlett object interface with C++ iterators in mind, it becomes feasible to define a universal lazy map. Also all these structures allow for a head/tail functionality, so a vector can be matched to a paramater-tree as easily as a stream, or user defined sequence. This feature is Not Yet Implemented.

the Source

The source code of Scarlett is available on github, under the GPL3 licence. To download Scarlett say

git clone https://github.com/jhidding/scarlett.git

Compile the code using ./make all in the directory that contains the make-script. I use C++11 extensively, so a version of GCC ≥ 4.7 is required.