Commits

Paweł Wieczorek  committed 6d35a3b Draft

added first encoding

  • Participants

Comments (0)

Files changed (1)

+#include <string>
+#include <iostream>
+#include <sstream>
+#include <boost/mpl/map.hpp>
+#include <boost/mpl/vector.hpp>
+#include <boost/mpl/at.hpp>
+#include <boost/mpl/insert.hpp>
+#include <boost/mpl/has_key.hpp>
+#include <boost/mpl/fold.hpp>
+#include <boost/mpl/if.hpp>
+#include <boost/mpl/placeholders.hpp>
+
+namespace lang
+{
+    template <char name>
+    struct var
+    {};
+
+    template <typename F, typename A>
+    struct apply
+    {};
+
+    template <char name, typename B>
+    struct fun
+    {};
+
+
+    template <int val>
+    struct const_int
+    {};
+
+    template <typename C, typename T, typename F>
+    struct branch
+    {};
+
+    struct plus
+    {};
+
+    struct minus
+    {};
+
+    struct times
+    {};
+
+    namespace representation
+    {
+
+        template <typename Tm>
+        struct represent
+        { };
+
+        template <int val>
+        struct represent< const_int<val> >
+        {
+            represent()
+            {
+                std::stringstream ss;
+                ss << val;
+                value = ss.str();
+            }
+
+            std::string value;
+        };
+
+        template <char name>
+        struct represent< var<name> >
+        {
+            represent()
+            {
+                value += name;
+            }
+
+            std::string value;
+        };
+
+        template <>
+        struct represent< plus >
+        {
+            represent()
+            {
+                value += '+';
+            }
+
+            std::string value;
+        };
+
+        template <>
+        struct represent< minus >
+        {
+            represent()
+            {
+                value += '-';
+            }
+
+            std::string value;
+        };
+
+        template <>
+        struct represent< times >
+        {
+            represent()
+            {
+                value += '*';
+            }
+
+            std::string value;
+        };
+
+        template <typename C, typename T, typename F>
+        struct represent< branch<C, T, F> >
+        {
+            represent()
+            {
+                represent<C> repr_C;
+                represent<T> repr_T;
+                represent<F> repr_F;
+
+                value.append("(if ");
+                value.append(repr_C.value);
+                value.append(" then ");
+                value.append(repr_T.value);
+                value.append(" else ");
+                value.append(repr_F.value);
+                value.append(")");
+            }
+
+            std::string value;
+        };
+
+
+        template <typename F, typename A>
+        struct represent< apply<F, A> >
+        {
+            represent()
+            {
+                represent<F> repr_F;
+                represent<A> repr_A;
+
+                value.append("(");
+                value.append(repr_F.value);
+                value.append(" ");
+                value.append(repr_A.value);
+                value.append(")");
+            }
+
+            std::string value;
+        };
+
+        template <char var, typename B>
+        struct represent< fun<var, B> >
+        {
+            represent()
+            {
+                represent<B> repr_B;
+
+                value.append("(fun ");
+                value += var;
+                value.append(". ");
+                value.append(repr_B.value);
+                value.append(")");
+            }
+
+            std::string value;
+
+        };
+    }
+
+}
+
+namespace domain
+{
+    template <typename Tm>
+    struct embed
+    { };
+
+    template <typename DF, typename DA>
+    struct apply
+    { };
+
+    template <char name, typename B, typename Env>
+    struct fun_closure
+    { };
+
+    template <int val>
+    struct const_int
+    { };
+
+    template <typename DC, typename T, typename F, typename Env>
+    struct branch_closure
+    { };
+
+
+    template <typename Builtin, int val>
+    struct builtin_closure
+    { };
+
+    struct plus_tag
+    { };
+
+    struct minus_tag
+    { };
+
+    struct times_tag
+    { };
+
+    namespace representation
+    {
+
+        template <typename Tm>
+        struct represent
+        {
+            represent()
+            {
+                value.append("<unknown>");
+            }
+
+            std::string value;
+        };
+
+        template <typename Env>
+        struct represent_env;
+
+        template <typename Tm>
+        struct represent< embed<Tm> >
+        {
+            represent()
+            {
+                lang::representation::represent<Tm> p;
+                value.append("(embed ");
+                value.append(p.value);
+                value.append(")");
+            };
+
+            std::string value;
+        };
+
+        template <int val>
+        struct represent< const_int<val> >
+        {
+            represent()
+            {
+                std::stringstream ss;
+                ss << val;
+                value = ss.str();
+            }
+
+            std::string value;
+        };
+
+        template <typename DB, int val>
+        struct represent< builtin_closure<DB, val> >
+        {
+            represent()
+            {
+                represent<DB> repr_DB;
+                value.append(repr_DB.value);
+                value.append("<");
+                std::stringstream ss;
+                ss << val;
+                value.append(ss.str());
+                value.append(">");
+            }
+
+            std::string value;
+        };
+
+        template <>
+        struct represent< plus_tag >
+        {
+            represent()
+            {
+                value += '+';
+            }
+
+            std::string value;
+        };
+
+        template <>
+        struct represent< minus_tag >
+        {
+            represent()
+            {
+                value += '-';
+            }
+
+            std::string value;
+        };
+
+        template <>
+        struct represent< times_tag >
+        {
+            represent()
+            {
+                value += '*';
+            }
+
+            std::string value;
+        };
+
+        template <typename DC, typename T, typename F, typename Env>
+        struct represent< branch_closure<DC, T, F, Env> >
+        {
+            represent()
+            {
+                represent<DC> repr_DC;
+                lang::representation::represent<T> repr_T;
+                lang::representation::represent<F> repr_F;
+                typename represent_env<Env>::type repr_Env;
+
+                value.append("(if ");
+                value.append(repr_DC.value);
+                value.append(" then ");
+                value.append(repr_T.value);
+                value.append(" else ");
+                value.append(repr_F.value);
+                value.append(" @ ");
+                value.append(repr_Env.value);
+                value.append(")");
+            }
+
+            std::string value;
+        };
+
+        template <typename F, typename A>
+        struct represent< apply<F, A> >
+        {
+            represent()
+            {
+                represent<F> repr_F;
+                represent<A> repr_A;
+
+                value.append("(");
+                value.append(repr_F.value);
+                value.append(" ");
+                value.append(repr_A.value);
+                value.append(")");
+            }
+
+            std::string value;
+        };
+
+        template <char var, typename B, typename Env>
+        struct represent< fun_closure<var, B, Env> >
+        {
+            represent()
+            {
+                lang::representation::represent<B> repr_B;
+                typename represent_env<Env>::type repr_Env;
+
+                value.append("(closure ");
+                value += var;
+                value.append(". ");
+                value.append(repr_B.value);
+                value.append(" @ ");
+                value.append(repr_Env.value);
+                value.append(")");
+            }
+
+            std::string value;
+
+        };
+
+        template <typename Env>
+        struct represent_env
+        {
+
+            struct empty_state
+            {
+                empty_state()
+                {
+                    value = "";
+                }
+
+                std::string value;
+            };
+
+            template <typename prev_state, typename current>
+            struct oper 
+            {
+            };
+
+            template <typename prev_state, char _key, typename _value>
+            struct oper<prev_state, boost::mpl::pair<lang::var<_key>, _value> >
+            {
+                oper()
+                {
+                    prev_state prev;
+                    represent<_value> repr_value;
+                    value.append(prev.value);
+                    value.append("[ ");
+                    value += _key;
+                    value.append(" -> ");
+                    value.append(repr_value.value);
+                    value.append(" ]");
+                }
+
+                std::string value;
+            };
+
+
+            typedef typename boost::mpl::fold
+                < Env
+                , empty_state
+                , oper
+                    < boost::mpl::placeholders::_1
+                    , boost::mpl::placeholders::_2
+                    >
+                >::type type;
+
+        };
+
+    }
+}
+
+namespace domain_evaluator 
+{
+    using namespace domain;
+
+    template <typename builtin_tag, int value1, int value2>
+    struct builtin_compute
+    {};
+
+    template <int value1, int value2>
+    struct builtin_compute<plus_tag, value1, value2>
+    {
+        typedef const_int<value1+value2> type;
+    };
+
+    template <int value1, int value2>
+    struct builtin_compute<minus_tag, value1, value2>
+    {
+        typedef const_int<value1-value2> type;
+    };
+
+    template <int value1, int value2>
+    struct builtin_compute<times_tag, value1, value2>
+    {
+        typedef const_int<value1*value2> type;
+    };
+
+    template <typename D, template <typename Tm, typename Env> class Eval>
+    struct compute
+    {
+        typedef D type;
+    };
+
+
+    template <char name, typename B, typename Env, typename DA, template <typename Tm, typename Env> class Eval>
+    struct compute< apply< fun_closure<name, B, Env> , DA >, Eval>
+    {
+        typedef typename boost::mpl::insert<Env, boost::mpl::pair<lang::var<name>, DA> >::type newEnv;
+
+        typedef typename Eval<B, newEnv>::type type;
+    };
+
+    template <typename T, typename F, typename Env, template <typename Tm, typename Env> class Eval>
+    struct compute< branch_closure<const_int<0>, T, F, Env>, Eval >
+    {
+        typedef typename Eval<F, Env>::type type;
+    };
+
+    template <int v, typename T, typename F, typename Env, template <typename Tm, typename Env> class Eval>
+    struct compute< branch_closure<const_int<v>, T, F, Env>, Eval >
+    {
+        typedef typename Eval<T, Env>::type type;
+    };
+
+    template <int value, template <typename Tm, typename Env> class Eval>
+    struct compute< apply< plus_tag, const_int<value> >, Eval>
+    {
+        typedef builtin_closure<plus_tag, value> type;
+    };
+
+
+    template <int value, template <typename Tm, typename Env> class Eval>
+    struct compute< apply< minus_tag, const_int<value> >, Eval>
+    {
+        typedef builtin_closure<minus_tag, value> type;
+    };
+
+
+    template <int value, template <typename Tm, typename Env> class Eval>
+    struct compute< apply< times_tag, const_int<value> >, Eval>
+    {
+        typedef builtin_closure<times_tag, value> type;
+    };
+
+    template <typename tag, int value1, int value2, template <typename Tm, typename Env> class Eval>
+    struct compute< apply< builtin_closure<tag, value1>, const_int<value2> >, Eval>
+    {
+
+        typedef typename builtin_compute<tag, value1, value2>::type type;
+    };
+
+}
+
+namespace evaluator
+{
+
+    template <typename Tm, typename Env>
+    struct eval
+    {
+        typedef domain::embed<Tm> type;
+    };
+
+    template <char name, typename Env>
+    struct eval< lang::var<name>, Env>
+    {
+        typedef typename
+            boost::mpl::if_c
+                < boost::mpl::has_key<Env, lang::var<name> >::type::value
+                , typename boost::mpl::at<Env, lang::var<name> >::type 
+                , domain::embed< lang::var<name> >
+                >::type type;
+
+    };
+
+    template <int val, typename Env>
+    struct eval< lang::const_int<val>, Env>
+    {
+        typedef domain::const_int<val> type;
+    };
+
+    template <typename F, typename A, typename Env>
+    struct eval< lang::apply<F, A>, Env >
+    {
+        typedef typename eval<F, Env>::type DF;
+
+        typedef typename eval<A, Env>::type DA;
+
+        typedef typename domain_evaluator::compute<domain::apply<DF, DA>, eval>::type type;
+    };
+
+
+    template <char name, typename B, typename Env>
+    struct eval< lang::fun<name, B>, Env >
+    {
+        typedef domain::fun_closure<name, B, Env> type;
+    };
+
+    template <typename C, typename T, typename F, typename Env>
+    struct eval< lang::branch<C, T, F>, Env>
+    {
+        typedef typename eval<C, Env>::type DC;
+
+        typedef typename domain_evaluator::compute<domain::branch_closure<DC, T, F, Env>, eval>::type type;
+    };
+
+    template <typename Env>
+    struct eval< lang::plus, Env >
+    {
+        typedef domain::plus_tag type;
+    };
+
+    template <typename Env>
+    struct eval< lang::minus, Env >
+    {
+        typedef domain::minus_tag type;
+    };
+
+    template <typename Env>
+    struct eval< lang::times, Env >
+    {
+        typedef domain::times_tag type;
+    };
+}
+
+
+namespace lib
+{
+    using namespace lang;
+
+    typedef boost::mpl::map<> empty_env;
+   
+    // pure id
+    typedef fun< 'x', var<'x'> > id;
+
+
+    // easy application
+    // multi_apply<F, vector<A,B,C>> = apply<apply<apply<F, A>, B>, C>
+
+    template <typename F, typename Vector>
+    struct multi_apply
+    {
+        typedef typename
+            boost::mpl::fold
+                < Vector
+                , F
+                , apply
+                    < boost::mpl::placeholders::_1
+                    , boost::mpl::placeholders::_2
+                    >
+                >::type type;
+    };
+
+    // SKI combinatory logic
+    typedef fun< 'x', fun<'y', var<'x'> > > K;
+
+    typedef fun< 'f', fun<'g', fun<'x', apply< apply< var<'f'>, var<'x'> >, apply<var<'g'>, var<'x'> > > > > > S;
+
+    typedef apply< apply< S, K >, K > I;
+
+    // Y combinator (encoded recurrence in lambda)
+    
+    namespace Ydef
+    {
+        typedef apply< var<'x'>, var<'x'> >     apply_xx;
+        typedef apply< apply_xx, var<'v'> >     apply_xx_v;
+        typedef fun<'v', apply_xx_v>            fun_v_apply_xx_v;
+
+        typedef apply< var<'f'>, fun_v_apply_xx_v> apply_f_fun_v_xx_v;
+
+        typedef fun<'x', apply_f_fun_v_xx_v>    omega;
+
+        typedef fun<'f', apply<omega, omega> >  Y;
+    }
+
+    typedef Ydef::Y Y;
+}
+
+namespace test1
+{
+    using namespace lang;
+    using namespace lib;
+
+    typedef const_int<1> term;
+
+    typedef evaluator::eval<term, empty_env>::type value;
+}
+
+
+namespace test2
+{
+    using namespace lang;
+    using namespace lib;
+
+    typedef apply<plus, const_int<1> > term;
+
+    typedef evaluator::eval<term, empty_env>::type value;
+}
+
+
+namespace test3
+{
+    using namespace lang;
+    using namespace lib;
+
+    typedef apply<apply<plus, const_int<1> >, const_int<2> > term;
+
+    typedef evaluator::eval<term, empty_env>::type value;
+}
+
+
+namespace test4
+{
+    using namespace lang;
+    using namespace lib;
+
+    typedef apply<id, const_int<1> > term;
+
+    typedef evaluator::eval<term, empty_env>::type value;
+}
+
+namespace test5
+{
+    using namespace lang;
+    using namespace lib;
+
+    typedef lib::id term;
+
+    typedef evaluator::eval<term, empty_env>::type value;
+}
+
+namespace test6
+{
+    using namespace lang;
+    using namespace lib;
+
+    typedef fun<'a', fun<'b',
+                multi_apply
+                    < plus
+                    , boost::mpl::vector< var<'a'>, var<'b'> >
+                    >::type
+            > > add;
+
+    typedef apply<add, const_int<5> > term;
+
+    typedef evaluator::eval<term, empty_env>::type value;
+}
+
+namespace test7
+{
+    using namespace lang;
+    using namespace lib;
+
+    /*
+     * pred n = n - 1
+     *
+     * silnia' rec n = 
+     *  if n != 0
+     *      then n * rec(pred(n))
+     *      else 1
+     *
+     *
+     * silnia = Y silnia' = silnia' (Y silnia')
+     */
+
+    typedef fun<'z', multi_apply<minus, boost::mpl::vector< var<'z'>, const_int<1> > >::type > pred;
+
+    typedef multi_apply<times, boost::mpl::vector< var<'n'>, apply<var<'r'>, apply<pred, var<'n'> > >  > >::type then_branch;
+
+    typedef const_int<1> else_branch;
+
+    typedef branch< var<'n'>, then_branch, else_branch > silnia_body;
+
+    typedef fun<'r', fun<'n', silnia_body> > silnia_norec;
+
+    typedef apply<Y, silnia_norec> silnia;
+
+    typedef apply<silnia, const_int<5> > term;
+
+    typedef evaluator::eval<term, empty_env>::type value;
+}
+
+
+
+int
+main()
+{
+    std::cout << "TERM  1: " << lang::representation::represent<test1::term>().value << std::endl;
+    std::cout << "VALUE 1: " << domain::representation::represent<test1::value>().value << std::endl;
+    std::cout << "TERM  2: " << lang::representation::represent<test2::term>().value << std::endl;
+    std::cout << "VALUE 2: " << domain::representation::represent<test2::value>().value << std::endl;
+    std::cout << "TERM  3: " << lang::representation::represent<test3::term>().value << std::endl;
+    std::cout << "VALUE 3: " << domain::representation::represent<test3::value>().value << std::endl;
+    std::cout << "TERM  4: " << lang::representation::represent<test4::term>().value << std::endl;
+    std::cout << "VALUE 4: " << domain::representation::represent<test4::value>().value << std::endl;
+    std::cout << "TERM  5: " << lang::representation::represent<test5::term>().value << std::endl;
+    std::cout << "VALUE 5: " << domain::representation::represent<test5::value>().value << std::endl;
+    std::cout << "TERM  6: " << lang::representation::represent<test6::term>().value << std::endl;
+    std::cout << "VALUE 6: " << domain::representation::represent<test6::value>().value << std::endl;
+    std::cout << "TERM  7: " << lang::representation::represent<test7::term>().value << std::endl;
+    std::cout << "VALUE 7: " << domain::representation::represent<test7::value>().value << std::endl;
+    return 0;
+}