Skip to content

Instantly share code, notes, and snippets.

@ilammy

ilammy/lc.cpp Secret

Last active Aug 29, 2015
Embed
What would you like to do?
Интерпретатор бестипового лямбда-исчисления на шаблонах С++
////////////////////////////////////////////////////////////////////////////////
/// Kernel definitions
template <char Var> struct Ref;
template <char Var, class Exp> struct Lam;
template <class Fun, class Arg> struct App;
struct NullEnv;
template <char Var, class Env> struct Lookup;
template <char Var, class Val, class Env> struct Bind;
template <char Var>
struct Lookup<Var, NullEnv>;
template <char Var, class Val, class Env>
struct Lookup<Var, Bind<Var, Val, Env>>
{
typedef Val result;
};
template <char Var, char OtherVar, class Val, class Env>
struct Lookup<Var, Bind<OtherVar, Val, Env>>
{
typedef typename Lookup<Var, Env>::result result;
};
template <class Abs, class Env> struct Closure;
template <class Exp, class Env> struct Eval;
template <class Fun, class Arg> struct Apply;
template <char Var, class Env>
struct Eval<Ref<Var>, Env>
{
typedef typename Lookup<Var, Env>::result value;
};
template <char Var, class Exp, class Env>
struct Eval<Lam<Var, Exp>, Env>
{
typedef Closure<Lam<Var, Exp>, Env> value;
};
template <class Fun, class Arg, class Env>
struct Eval<App<Fun, Arg>, Env>
{
typedef typename Apply<typename Eval<Fun, Env>::value,
typename Eval<Arg, Env>::value>::result value;
};
template <char Var, class Exp, class Env, class Arg>
struct Apply<Closure<Lam<Var, Exp>, Env>, Arg>
{
typedef typename Eval<Exp, Bind<Var, Arg, Env>>::value result;
};
////////////////////////////////////////////////////////////////////////////////
/// Macroexpand : Kernel
template <class Exp> struct Expand;
template <class Exp, class Env>
struct Compute
{
typedef typename Eval<typename Expand<Exp>::result, Env>::value value;
};
template <char Var>
struct Expand<Ref<Var>>
{
typedef Ref<Var> result;
};
template <char Var, class Exp>
struct Expand<Lam<Var, Exp>>
{
typedef Lam<Var, typename Expand<Exp>::result> result;
};
template <class Fun, class Arg>
struct Expand<App<Fun, Arg>>
{
typedef App<typename Expand<Fun>::result,
typename Expand<Arg>::result> result;
};
////////////////////////////////////////////////////////////////////////////////
/// Macroexpand : Variadic abstraction
template <char... Vars> struct Args;
template <class Args, class Exp> struct Lam_;
template <char Var, class Exp>
struct Expand<Lam_<Args<Var>, Exp>>
{
typedef typename Expand<Lam<Var, Exp>>::result result;
};
template <char Var, char... Vars, class Exp>
struct Expand<Lam_<Args<Var, Vars...>, Exp>>
{
typedef Lam<Var, typename Expand<Lam_<Args<Vars...>, Exp>>::result> result;
};
////////////////////////////////////////////////////////////////////////////////
/// Macroexpand : Variadic application : Ref-list
struct Nil;
template <class First, class Rest> struct RefList;
template <char... Vars> struct ToRefList_s;
template <char Var>
struct ToRefList_s<Var>
{
typedef RefList<Ref<Var>, Nil> result;
};
template <char Var, char... Vars>
struct ToRefList_s<Var, Vars...>
{
typedef RefList<Ref<Var>, typename ToRefList_s<Vars...>::result> result;
};
template <class... Exps> struct ToRefList_i;
template <class Exp>
struct ToRefList_i<Exp>
{
typedef RefList<Exp, Nil> result;
};
template <class Exp, class... Exps>
struct ToRefList_i<Exp, Exps...>
{
typedef RefList<Exp, typename ToRefList_i<Exps...>::result> result;
};
////////////////////////////////////////////////////////////////////////////////
/// Macroexpand : Variadic application : Ref-list processing
template <class Apps, class RefList> struct App_wrap;
template <class A, class D, class R>
struct App_wrap<Nil, RefList<A, RefList<D, R>>>
{
typedef typename App_wrap<App<A, D>, R>::result result;
};
template <class Apps, class A>
struct App_wrap<Apps, RefList<A, Nil>>
{
typedef typename App_wrap<App<Apps, A>, Nil>::result result;
};
template <class Apps, class A, class D>
struct App_wrap<Apps, RefList<A, D>>
{
typedef typename App_wrap<App<Apps, A>, D>::result result;
};
template <class Apps>
struct App_wrap<Apps, Nil>
{
typedef Apps result;
};
////////////////////////////////////////////////////////////////////////////////
/// Macroexpand : Variadic application : Actual implementation
template <char... Exps> struct App_s;
template <class... Exps> struct App_i;
template <char... Exps>
struct Expand<App_s<Exps...>>
{
typedef typename Expand<
typename App_wrap<Nil,
typename ToRefList_s<Exps...>::result
>::result
>::result result;
};
template <class... Exps>
struct Expand<App_i<Exps...>>
{
typedef typename Expand<
typename App_wrap<Nil,
typename ToRefList_i<Exps...>::result
>::result
>::result result;
};
////////////////////////////////////////////////////////////////////////////////
/// Foreign term injection
template <class T> struct Inj;
template <class T, class Env>
struct Eval<Inj<T>, Env>
{
typedef T value;
};
template <class T>
struct Expand<Inj<T>>
{
typedef Inj<T> result;
};
////////////////////////////////////////////////////////////////////////////////
/// Unchurchifier
struct Zero
{
static const unsigned int interpretation = 0;
};
struct Succ;
template <class N>
struct Apply<Succ, N>
{
typedef struct _ {
static const unsigned int interpretation = N::interpretation + 1;
} result;
};
/// ///
////////////////////////////////////////////////////////////////////////////////
#include <iostream>
int main()
{
// 1 = λfx.f x
typedef Lam<'f', Lam<'x', App<Ref<'f'>, Ref<'x'>>>> One;
// 2 = λfx.f (f x)
typedef Lam<'f', Lam<'x', App<Ref<'f'>, App<Ref<'f'>, Ref<'x'>>>>> Two;
// + = λab.λfx.a f (b f x)
typedef Lam<'a', Lam<'b', Lam<'f', Lam<'x',
App<App<Ref<'a'>, Ref<'f'>>,
App<App<Ref<'b'>, Ref<'f'>>, Ref<'x'>>>
>>>> Plus;
// Unchurch = λn.(n +1 =0), преобразование чисел Чёрча в int
typedef Lam<'n', App<App<Ref<'n'>, Ref<'I'>>, Ref<'O'>>> Unchurch;
// Result := (Unchurch (+ 1 2))
typedef Eval<App<Ref<'U'>,
App<App<Ref<'+'>, Ref<'1'>>, Ref<'2'>>>,
Bind<'+', typename Eval<Plus, NullEnv>::value,
Bind<'1', typename Eval<One, NullEnv>::value,
Bind<'2', typename Eval<Two, NullEnv>::value,
Bind<'U', typename Eval<Unchurch,
Bind<'I', Succ,
Bind<'O', Zero,
NullEnv>>
>::value,
NullEnv>>>>
>::value Result;
std::cout << Result::interpretation;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment