Klister

Klister [TyDe 2020, video] is a programming language, a research prototype which combines features from Racket, ML, and a strict Haskell into a single language. It is named after its most distinguishing feature, "stuck macros" [Compose NYC 2019], as "Klister" is Danish for "adhesive".

#lang "prelude.kl"

-- do notation is not builtin syntax, it's implemented as a library!
(import "monad.kl")

-- An effectful action whose inferred type is (-> String (IO Unit))
(defun putStrLn (str)
  (write stdout (string-append str "\n")))

-- "run" is like main, except you can have more than one.
(run
  -- Klister doesn't have type classes yet, so "do" needs an explicit
  -- dictionary argument.
  (do io-monad
    (putStrLn "hello")
    (putStrLn "world")))

You can run the above program using either stack or cabal:

$ cabal run klister -- run examples/hello.kl
hello
world

Features

Features we borrow from Racket:

• Custom syntax, via hygienic macros with easy-to-override hygiene.
• Custom languages (#lang), via macros which reinterpret terms into those of an existing #lang.
• Syntax objects, that is, s-expressions annotated with source locations and lexical information.
• A module system which respects the phase system. Thus, if Klister one day supports generating binaries, those binaries will not be unnecessarily clogged with dependencies which were only needed at compile-time.

Features we borrow from ML:

• A type system with parametric polymorphism, algebraic datatypes, and Hindley-Milner type inference.

Features we borrow from Haskell:

• Monadic macros; our macros have type (-> Syntax (Macro Syntax)), where Macro Syntax is similar to Q Exp in TemplateHaskell. Note that this type implies that a macro is allowed to generate ill-typed code; this error is caught where the macro is called, not where the macro is defined. We thus aim for the expressivity of Template Haskell, not the extra guarantees of Typed Template Haskell.
• Purely functional; primitives with compile-time side-effects (e.g. comparing identifiers while taking into account the current set of bindings) run in the Macro monad, while primitives with runtime side-effects (e.g. printing to stdout) run in the IO monad.
• Higher-kinded types; for example monads are defined as a library.

Features which make Klister special (but not necessarily unique; see the bibliography for languages with similar features):

• Type-providing macros; a macro can provide type information about the code it plans to generate.
• Type-aware macros; a macro can obtain type requirements about the code it needs to generate.
• Stuck macros; the above two features make it possible for macros to communicate, and thus to affect what each other generates. The language primitives are designed so that the order in which the macros are expanded cannot affect their results, and indeed the same is true for the order in which the macro expansion and type-inference steps are interleaved. This means that the order in which the type checker traverses a program and generates constraints is not visible to the authors of macros, providing a predictable programming model. This makes Klister code more robust to refactorings which affect that order.
• Problem-aware macros; in addition to the type, a macro can learn which "problem" it needs to solve, namely whether it must generate an expression, a type, a pattern, etc. Each problem would correspond to a form of judgment if the language was formalized, e.g. a typing judgment for the expression problem, a well-formed type judgment for the type problem, etc.

Cool things which can be built using the above features:

• Macros communicating via types
• Custom type-driven code generation, via macros which generate code from a type.
• Languages with custom type systems, via macros which reinterpret types into those of an existing #lang, and which contribute to type inference by providing type information about the code they generate. The variety of type-systems which can be implemented this way is unforunately limited by the core type system to which everything must be rewritten.
• Languages with custom implicit terms, via macros which generate terms of an existing #lang based on a type in the new #lang.

While we think Klister demonstrates some neat ideas, there are some limitations which make Klister an impractical choice for most real-life projects. If you want to help make Klister a more practical language, please reach out!

Here are the most prominent Racket features which are missing from Klister:

• Klister does not yet support custom readers, and thus every #lang looks like a Lisp. This also limits languages to Integer literals and String literals.
• local-expand is planned, but not yet implemented.
• Syntax parameters are planned, but not yet implemented.

Here are the most prominent Haskell features which are missing from Klister:

• Type classes are planned as a library, but are not yet implemented.
• Type annotations containing foralls are planned, but not yet implemented. Currently, Klister only supports type ascriptions, e.g. (+ (the Integer (* 2 3)) 1), for giving the type of a sub-expression.
• Klister does not support GADTs nor type families.

Here are the most prominent features which Racket and Haskell both have but which are missing from Klister:

• Klister is missing commonly-expected datatypes like Map, Set, and Double.
• Klister requires functions and datatypes to be defined before they are used.
• Klister does not support concurrency. It might be possible to implement a #lang with a green thread scheduler.
• Klister does not support exception-handling. error and syntax-error both terminate the program immediately, like panic! in Rust. It is definitely possible to implement Either-based error handling, and it should be possible to implement a #lang in which exceptions are an ambient effect.
• Klister does not have a rich ecosystem of libraries. It does not have a package repository where individual contributors can release their own packages. Please upload your Klister code to the examples folder, it currently contains all the Klister code which was ever written.
• Klister does not have a rich set of IO primitives out of which you could build all the libraries you need yourself. Currently, you can only print to stdout.
• A Foreign-Function-Interface (FFI), to reuse Haskell's rich ecosystem of libraries (and its own FFI to C), is planned but not yet implemented.
• Expanding modules separately, to speed up expansion times, is planned but not yet implemented.
• Klister does not produce binary executables.

Guide and Reference

The Klister Guide consists of the various commented examples linked from the above feature list, plus the extra information in the sub-sections below.

The Klister Reference covers every identifier in the "prelude.kl" language, but doesn't currently say much about each. It consists of a list of examples showing how to use the macros, and a list of type signatures documenting how to use the values and functions.

Imports

The import form will search for modules in the same directory as the importing module, and in directories listed in the KLISTERPATH environment variable, a :-separated list of directories.

Setting KLISTERPATH is needed for all tests to pass, as some rely on modules from the examples directory;

$ cabal test

Test suite klister-tests: RUNNING...
All tests
  Golden tests
    keyword-used-incorrectly:                          FAIL
      ...
      +Module not found: keyword-test.kl
      +Searched in directory at /.../examples/failing-examples
      +And on $KLISTERPATH:
      ...
    wrong-keyword:                                     FAIL
      ...
      +Module not found: keyword-test.kl
      +Searched in directory at /.../examples/failing-examples
      +And on $KLISTERPATH:
      ...
    bound-vs-free:                                     FAIL
      ...
      +Module not found: do.kl
      +Searched in directory at /.../examples/failing-examples
      +And on $KLISTERPATH:
      ...

3 out of 132 tests failed
Test suite klister-tests: FAIL

$ KLISTERPATH=examples cabal test
...
Test suite klister-tests: PASS