TempLisp

Lisp implementation in C++ templates.

How to use

% ./compile.sh -e "(car '(a b c))" > car.cc
% g++ -std=c++14 -o car car.cc
% ./car
A
% ./compile.sh -e "
(defun fact (n) (if (eq n 0) 1 (* n (fact (- n 1)))))
(fact 10)" > fact10.cc
% g++ -std=c++14 -o fact10 fact10.cc
% ./fact10
FACT
3628800
% cat << EOF > gen.lisp
(defun gen (n) (lambda (m) (setq n (+ n m))))
(setq x (gen 100))
(x 10)
(x 90)
(x 300)
EOF
% ./compile.sh < gen.lisp > gen.cc
% g++ -std=c++14 -o gen gen.cc
% ./gen
GEN
<expr>
110
200
500
% cat gen.cc
#include "templisp.h"
int main() {
  using env = InitMemory::env;
  DEFINE_SYMBOL(GEN);
  DEFINE_SYMBOL(N);
  DEFINE_SYMBOL(M);
  DEFINE_SYMBOL(X);
  using ret0 = Eval<List<DEFUN, GEN, List<N>, List<LAMBDA, List<M>, List<SETQ, N, List<ADD, N, M>>>>, env, InitMemory::memory>;
  constexpr auto str0 = PrettyPrinter::Print<ret0>::toString();
  std::cout << str0 << std::endl;
  using ret1 = Eval<List<SETQ, X, List<GEN, Int<100>>>, env, ret0::memory>;
  constexpr auto str1 = PrettyPrinter::Print<ret1>::toString();
  std::cout << str1 << std::endl;
  using ret2 = Eval<List<X, Int<10>>, env, ret1::memory>;
  constexpr auto str2 = PrettyPrinter::Print<ret2>::toString();
  std::cout << str2 << std::endl;
  using ret3 = Eval<List<X, Int<90>>, env, ret2::memory>;
  constexpr auto str3 = PrettyPrinter::Print<ret3>::toString();
  std::cout << str3 << std::endl;
  using ret4 = Eval<List<X, Int<300>>, env, ret3::memory>;
  constexpr auto str4 = PrettyPrinter::Print<ret4>::toString();
  std::cout << str4 << std::endl;
  return 0;
}
% g++ -std=c++14 -S gen.cc
% tail -n 20 gen.s
        .section        __TEXT,__literal4,4byte_literals
L___const.main.str0:                    ## @__const.main.str0
        .asciz  "GEN"

        .section        __TEXT,__const
l___const.main.str1:                    ## @__const.main.str1
        .asciz  "<expr>"

        .section        __TEXT,__literal4,4byte_literals
L___const.main.str2:                    ## @__const.main.str2
        .asciz  "110"

L___const.main.str3:                    ## @__const.main.str3
        .asciz  "200"

L___const.main.str4:                    ## @__const.main.str4
        .asciz  "500"

How does it work

All LISP objects are represented as C++ types. Symbols are represented as empty structs. Conses are repsented as structs which take 2 template parameters.

struct NIL {};
struct T {};
struct LAMBDA {};

template<typename T1, typename T2>
struct Cons {
  using car = T1;
  using cdr = T2;
};

LISP evaluator is also represented as C++ types. Conditional expressions are represented by template specializations. Eval can be represented as a struct which take 2 template parameters if mutations are not necessary.

template<typename Exp, typename Env>
struct Eval {
  using value = typename Assoc<Exp, Env>::value::cdr;
};
template<int i, typename Env>
struct Eval<Int<i>, Env> {
  using value = Int<i>;
};
template<typename T1, typename T2, typename Env>
struct Eval<Cons<T1, T2>, Env> {
  using value = typename EvCom<T1, T2, Env>::value;
};

Actually TempLisp supports mutations. To support mutations, memory is necessary. The memory is something like a set of key/value pairs. It's represented as an alist whose key is an Int and value is a immutable cons.

template<typename NextId, typename Alist>
struct Memory {
  using nextId = NextId;
  using alist = Alist;
};

Mutable conses are achieved by accessing conses via Memory.

template<typename Id>
struct ConsRef {
  using id = Id;
};
template<typename Car, typename Cdr, typename Mem>
struct MCons {
private:
  using currId = typename Mem::nextId;
  using nextId = Int<currId::value + 1>;
public:
  using value = ConsRef<currId>;
  using memory = Memory<
    nextId,
    Cons<Cons<currId, Cons<Car, Cdr>>,
         typename Mem::alist>>;
};
template<typename Ref, typename Mem>
struct MCarImpl {
  using value = typename Assoc<
    typename Ref::id,
    typename Mem::alist>>::value::cdr::car;
};

Now that Eval takes another parameter and returns another type for Memory.

template<typename Exp, typename Env, typename Mem>
struct Eval {
  using value = MCdr<typename FindVar<Exp, Env, Mem>::value, Mem>;
  using memory = Mem;
};

See templisp.h for details.

C++ types (representing LISP objects and evaluator) are resolved at compile time. So LISP expressions are evaluated at C++ compile time.