kontlang

Language with Clojure-like syntax and semantics based on EoPL + Shift/Reset, implemented in OCaml

Language features

Kontlang is a dynamically typed, purely functional (excluding the use of continuations) language interpreted with a CEK-machine-like evaluator, written in a trampolining defunctionalized continuation passing style.

The language supports the following features:

let, let*, letfn, letrec (each supporting multiple variable bindings in one expression, and mutual recursion in the case of letrec)
lexical scope functions with closures
tail call optimized
simple dynamic scope macros with expression substitution
first class modules that can be imported from file
delimited continuations via the shift & reset operators
standard library modules including implementation of monads via reify and reflect operators
alternative step-wise evaluation interpreter showing expression/value, environment, and continuation at each step

Instructions for use

Recommendation for installing dependencies is OPAM, the defacto standard OCaml package manager.

Once OPAM is installed and configured (opam init & eval $(opam config env) - see OPAM website for further details), run:

opam install dune menhir ounit2

This will install all dependencies for kontlang.

Then in the kontlang repo:

# Running a Read-Eval-Print interpreter
dune exec ./main.exe

# Running a Stepwise Execution interpreter
dune exec ./stepwise.exe

Example programs

Monads

Based on examples and exercises from "Introduction to Programming with Shift and Reset" together with reify and reflect operators as defined in Andrzej Filinski's "Representing Monads" paper.

Non-deterministic search of numbers matching Pythagorus' Theorem

(let [L Stdlib.ListMonad]
  (L.reify
    (let [(x (L.reflect (list 1 2 3 4 5)))
          (y (L.reflect (list 1 2 3 4 5)))
          (z (L.reflect (list 1 2 3 4 5)))]
      (if (= (* z z)
             (+ (* x x)
                (* y y)))
        (list x y z)
        (L.fail)))))

Above returns ((3 4 5) (4 3 5))

State monad:

(let [S Stdlib.StateMonad]
  (S.run_state
    (S.reify
      (let* [(tick
               (fn []
                 (S.reflect
                   (fn [state] (cons nil (+ state 1))))))
             (_ (tick))
             (_ (tick))
             (a (S.get))
             (_ (tick))]
         (- (S.get) a)))
    0))

returns a tuple of the "result" and the final state (1 . 3)

See /modules/list-monad.ktl and /modules/state-monad.ktl for definitions of the ListMonad and StateMonad modules.

For more usage examples, see the /test directory.

yin-yang puzzle

(reset
  (let [(yin ((fn [k] (do [(print "x") k]))
              (shift [k] (k k))))
        (yang ((fn [k] (do [(print "_") k]))
              (shift [k] (k k))))]
    (yin yang)))

The above generates an infinite stream on stdout of the form

x_x__x___x____x_____x....