Guest User

Compile-time LISP interpreter

a guest
Nov 14th, 2011
545
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

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×