Church and State (part 2)

While State is a low level language that compiles directly to machine code, Church has features common to many high level languages (and some uncommon ones):


  • A block-indented syntax (similar to Python or Haskell)
  • Macros
    syntax new [(&rest args) (let ((class-name (second (first args)))
                                   (key-args (loop for (_key k v) in (cdr args) collect `(:symbol ,k) collect v)))
                                `(:let (((:var "o") (:inline state::state-make-object (:symbol ,class-name) ,@key-args)))
                                    (:apply "init" (:var "o"))
                                    (:var "o"))))]
  • A class system
  • Dynamic dispatch (dispatch depends on all the arguments of a function, also known as multiple-dispatch)
  • Pattern matching syntax like Erlang or Prolog (yet to be implemented)
  • A high level ‘loop’ control structure
    bar list1 list2
                    for x in list1
                    for y in list2
                    when x
                    do (print x)
                    when y
                    do (print y)
                    collect y

At the moment I have a fairly primitive implementation for dynamic dispatch, I use a cons list to store lists of patterns and bodies, sorted first by symbol and then by argument types.

Symbols are also interned into a cons list, later I will have to find a way to include them directly in compiled code.

Loops are expanded into State’s tagbody forms.

The parser is implemented in my Common Lisp version of OMeta, which I plan to port to Church later.

My future work is focussed on writing the Church and State compilers in Church itself, thus bootstrapping the language.

Church and State (part 1)

After porting jolt-burg I started developing a higher level language on top of it. My codenames for this high-level and low-level combination are Church and State.


My implementation of State has been progressing steadily to the point where I have the following features:

  • lisp-like sexp syntax (I use the lisp reader from the host environment to read the State source files)
  • functions and global variables
  • Macros
    (syntax end? (x) `(if (null? ,x)
                          (if (pair? ,x)
                              (abort "bad list encountered in end?"))))
  • partial lexical closures (also known as ‘downward funargs’)
    (define |main| (lambda ()
                     (let ((a 1)
                           (b 2))
                       ((lambda (arg)
                          (+ arg a)) b))))
  • basic machine operations such as + – * bitwise and, bitwise or and bitshifts
  • if forms
    (if a
  • ‘cond’, ‘and’ and ‘or’ forms
  • the tagbody control structure
       (if (end)
           (go finished)
           (go next))
  • primitive structures
  • non-local-return
    (define foo (lambda ()
                     (block a
                       (block b
                         (return-from foo 1)))

All of the above has been implemented with a 32-bit x86 backend. The compiler generates relocatable code which is written to ELF objects and linked with the unix linker.