SHARE
TWEET

Compile-time LISP interpreter

a guest Nov 14th, 2011 415 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /**
  2.  * This thing SHOULD be Turing complete.
  3.  */
  4.  
  5. /**
  6.  * Symbol
  7.  */
  8. template <char val>
  9. struct sym;
  10.  
  11. /**
  12.  * Numeric value
  13.  */
  14. template <int val_>
  15. struct val {
  16.     static constexpr int value = val_;
  17.     struct get { };
  18. };
  19.  
  20. /**
  21.  * Variable binding
  22.  */
  23. template <typename Name, typename Value>
  24. struct var {
  25.     typedef Value value;
  26. };
  27.  
  28. /**
  29.  * List
  30.  */
  31. template <typename... T>
  32. struct list;
  33.  
  34. /**
  35.  * Empty list
  36.  */
  37. typedef list<> nil;
  38.  
  39. /**
  40.  * Quoted expr
  41.  */
  42. template <typename Expr>
  43. struct quote;
  44.  
  45. /**
  46.  * Lambda
  47.  */
  48. template <typename Closure, typename Params, typename Body>
  49. struct lambda;
  50.  
  51. /**
  52.  * C++ metafunction binding
  53.  */
  54. template <template <typename...> class Fun>
  55. struct builtin;
  56.  
  57. /**
  58.  * Variable environment
  59.  */
  60. template <typename Outer = void, typename... Vars>
  61. class env {
  62.     template <typename Name, typename... Vars2>
  63.     struct do_get;
  64.  
  65.     template <typename Name, typename Var, typename... Rest>
  66.     struct do_get<Name, Var, Rest...> {
  67.         typedef typename do_get<Name, Rest...>::result result;
  68.     };
  69.  
  70.     template <typename Name, typename Value, typename... Rest>
  71.     struct do_get<Name, var<Name, Value>, Rest...> {
  72.         typedef var<Name, Value> result;
  73.     };
  74.  
  75.     template <typename Name>
  76.     struct do_get<Name> {
  77.         typedef typename Outer::template get<Name>::result result;
  78.     };
  79.    
  80.   public:
  81.     template <typename Name>
  82.     struct get {
  83.         typedef typename do_get<Name, Vars...>::result result;
  84.     };
  85. };
  86.  
  87. typedef sym<'i'> s_if;
  88. typedef sym<'q'> s_quote;
  89. typedef sym<'l'> s_lambda;
  90. typedef sym<'d'> s_define;
  91. typedef sym<'b'> s_begin;
  92.  
  93. template <typename Env, typename List>
  94. struct eval;
  95.  
  96. /**
  97.  * Evaluate (quote expr)
  98.  */
  99. template <typename Env, typename Expr>
  100. struct eval<Env, list<s_quote, Expr>> {
  101.     typedef Expr result;
  102. };
  103.  
  104. /**
  105.  * Evaluate (if cond then else)
  106.  */
  107. template <typename Env, typename Cond, typename Then, typename Else>
  108. struct eval_if {
  109.     typedef typename eval<Env, Then>::result result;
  110. };
  111.  
  112. template <typename Env, typename Then, typename Else>
  113. struct eval_if<Env, nil, Then, Else> {
  114.     typedef typename eval<Env, Else>::result result;
  115. };
  116.  
  117. template <typename Env, typename Cond, typename Then, typename Else>
  118. struct eval<Env, list<s_if, Cond, Then, Else>> {
  119.     typedef typename eval_if<Env, typename eval<Env, Cond>::result, Then, Else>::result result;
  120. };
  121.  
  122. /**
  123.  * Evaluate (lambda params body)
  124.  */
  125. template <typename Env, typename Params, typename Body>
  126. struct eval<Env, list<s_lambda, Params, Body>> {
  127.     typedef lambda<Env, Params, Body> result;
  128. };
  129.  
  130. /**
  131.  * Evaluate (define name value)
  132.  */
  133. template <typename Env, typename Name, typename Value>
  134. struct eval<Env, list<s_define, Name, Value>> {
  135.     typedef var<Name, typename eval<Env, Value>::result> result;
  136. };
  137.  
  138. /**
  139.  * Evaluate a value
  140.  */
  141. template <typename Env, int value>
  142. struct eval<Env, val<value>> {
  143.     typedef val<value> result;
  144. };
  145.  
  146. /**
  147.  * Look up symbol in environment
  148.  */
  149. template <typename Env, char name>
  150. struct eval<Env, sym<name>> {
  151.     typedef typename Env::template get<sym<name> >::result::value result;
  152. };
  153.  
  154. /**
  155.  * Evaluate definitions
  156.  */
  157. template <typename Env, typename Name, typename Value, typename... Rest>
  158. struct eval<Env, list<list<s_define, Name, Value>, Rest...>> {
  159.     typedef typename eval<
  160.         env<Env, typename eval<Env, list<s_define, Name, Value> >::result>,
  161.         list<Rest...>
  162.         >::result result;
  163. };
  164.    
  165. template <typename Env, typename Name, typename Value, typename Expr>
  166. struct eval<Env, list<list<s_define, Name, Value>, Expr>> {
  167.     typedef typename eval<
  168.         env<Env, typename eval<Env, list<s_define, Name, Value> >::result>,
  169.         Expr
  170.         >::result result;
  171. };
  172.  
  173. /**
  174.  * Evaluate (function args*)
  175.  */
  176. template <typename Env, typename...>
  177. struct eval_call;
  178.  
  179. template <typename Env, typename Closure, typename Body, typename... Params, typename... Args>
  180. struct eval_call<Env, lambda<Closure, list<Params...>, Body>, Args...> {
  181.     typedef typename eval<env<Closure, var<Params, Args>...>, Body>::result result;
  182. };
  183.  
  184. template <typename Env, template<typename...> class Fun, typename... Args>
  185. struct eval_call<Env, builtin<Fun>, Args...> {
  186.     typedef typename Fun<typename eval<Env, Args>::result...>::result result;
  187. };
  188.  
  189. template <typename Env, typename Fun, typename... Args>
  190. struct eval<Env, list<Fun, Args...> > {
  191.     typedef typename eval_call<
  192.         Env,
  193.         typename eval<Env, Fun>::result,
  194.         typename eval<Env, Args>::result...>::result result;
  195. };
  196.  
  197.  
  198. /**
  199.  * Return Then if cond, else Else
  200.  */
  201. template <bool cond, typename Then, typename Else>
  202. struct if_ {
  203.     typedef Then result;
  204. };
  205.  
  206. template <typename Then, typename Else>
  207. struct if_<false, Then, Else> {
  208.     typedef Else result;
  209. };
  210.  
  211. /**
  212.  * Represent a compile-time string
  213.  */
  214. template <char... chars>
  215. struct code;
  216.  
  217. template <typename code>
  218. struct parse;
  219.  
  220. /**
  221.  * Parse number or symbol
  222.  */
  223. template <char c, char... r>
  224. struct parse<code<c, r...>> {
  225.     typedef typename if_<'0' <= c && c <= '9', val<c-'0'>, sym<c> >::result result;
  226.     typedef code<r...> rest;
  227.     static std::string str() { return {c}; }
  228. };
  229.  
  230. /**
  231.  * Parse special forms
  232.  */
  233. template <char... r>
  234. struct parse<code<'i', r...>> {
  235.     typedef s_if result;
  236.     typedef code<r...> rest;
  237. };
  238. template <char... r>
  239. struct parse<code<'q', r...>> {
  240.     typedef s_quote result;
  241.     typedef code<r...> rest;
  242. };
  243. template <char... r>
  244. struct parse<code<'l', r...>> {
  245.     typedef s_lambda result;
  246.     typedef code<r...> rest;
  247. };
  248. template <char... r>
  249. struct parse<code<'d', r...>> {
  250.     typedef s_define result;
  251.     typedef code<r...> rest;
  252. };
  253.  
  254. /**
  255.  * Parse a list
  256.  */
  257. template <typename list, typename code>
  258. struct parse_list;
  259.  
  260. template <typename... Elems, char... r>
  261. struct parse_list<list<Elems...>, code<r...>> {
  262.     typedef parse<code<r...> > elem;
  263.     typedef parse_list<list<Elems..., typename elem::result>, typename elem::rest> list_;
  264.     typedef typename list_::result result;
  265.     typedef typename list_::rest rest;
  266. };
  267.  
  268. template <typename... Elems, char... r>
  269. struct parse_list<list<Elems...>, code<')', r...> > {
  270.     typedef list<Elems...> result;
  271.     typedef code<r...> rest;
  272. };
  273.  
  274. template <char... r>
  275. struct parse<code<'(', r...> > {
  276.     typedef parse_list<list<>, code<r...> > list_;
  277.     typedef typename list_::result result;
  278.     typedef typename list_::rest rest;
  279. };
  280.  
  281.  
  282. /**
  283.  * Builtin functions
  284.  */
  285.  
  286. template <typename Lhs, typename Rhs>
  287. struct add {
  288.     typedef val<Lhs::value + Rhs::value> result;
  289. };
  290.  
  291. template <typename Lhs, typename Rhs>
  292. struct sub {
  293.     typedef val<Lhs::value - Rhs::value> result;
  294. };
  295.  
  296. template <typename Lhs, typename Rhs>
  297. struct mul {
  298.     typedef val<Lhs::value * Rhs::value> result;
  299. };
  300.  
  301. template <typename Lhs, typename Rhs>
  302. struct div_ {
  303.     typedef val<Lhs::value / Rhs::value> result;
  304. };
  305.  
  306. template <typename L, typename R>
  307. struct eq {
  308.     typedef nil result;
  309. };
  310.  
  311. template <typename L>
  312. struct eq<L, L> {
  313.     typedef val<true> result;
  314. };
  315.  
  316. template <typename List>
  317. struct car;
  318.  
  319. template <typename H, typename... T>
  320. struct car<list<H, T...>> {
  321.     typedef H result;
  322. };
  323.  
  324. template <typename List>
  325. struct cdr;
  326.  
  327. template <typename H, typename... T>
  328. struct cdr<list<H, T...>> {
  329.     typedef list<T...> result;
  330. };
  331.  
  332. typedef env<
  333.     void,
  334.     var<sym<'+'>, builtin<add> >,
  335.     var<sym<'-'>, builtin<sub> >,
  336.     var<sym<'*'>, builtin<mul> >,
  337.     var<sym<'/'>, builtin<div_> >,
  338.     var<sym<'='>, builtin<eq> >,
  339.     var<sym<'h'>, builtin<car> >,
  340.     var<sym<'t'>, builtin<cdr> >
  341.     > globals;
  342.  
  343. /**
  344.    ((define y 4)
  345.     (define f (lambda (x) (* x x)))
  346.     (f (* y 2)))
  347. */
  348. typedef parse<code<
  349.     '(','(','d','y','4',')',
  350.         '(','d','f','(','l','(','x',')','(','*','x','x',')',')',')',
  351.         '(','f','(','*','y','2',')',')',')'>> p;
  352.  
  353. constexpr int _ = eval<globals, p::result>::result::get::value;
  354.  
  355. /*
  356.    g++ -std=c++0x eval2.cpp -c -Wall -pedantic && ./eval
  357.    eval2.cpp:322:19: error: ‘value’ is not a member of ‘val<64>::get’
  358. */
  359.  
  360.  
RAW Paste Data
Top