case_test_01.cpp

///
/// \file lambda.cpp
///
/// An example of implementing Lambda Calculus interpreter in Mach7.
///
/// \author Yuriy Solodkyy <yuriy.solodkyy@gmail.com>
///
/// This file is a part of Mach7 library (http://parasol.tamu.edu/mach7/).
/// Copyright (C) 2011-2012 Texas A&M University.
/// All rights reserved.
///

//------------------------------------------------------------------------------

#include <mach7/type_switchN-patterns.hpp> // Support for N-ary Match statement on patterns
#include <mach7/patterns/address.hpp>      // Address and dereference combinators
#include <mach7/patterns/bindings.hpp>     // Mach7 support for bindings on arbitrary UDT
#include <mach7/patterns/constructor.hpp>  // Support for constructor patterns
#include <mach7/patterns/equivalence.hpp>  // Equivalence combinator +
#include "testutils.hpp"

//------------------------------------------------------------------------------

struct Term {
    virtual ~Term() {}
};

struct Var : Term {
    std::string name;
    Var(const char* n) {
        name = std::string(n);
    }
};

struct Abs : Term {
    Var*  var;
    Term* body;
    Abs(Var*  v, Term* t)
        : var(v)
        , body(t) {}
};

struct App : Term {
    Term* func;
    Term* arg;
    App(Term* f, Term* a)
        : func(f)
        , arg(a) {}
};

//configures the members that can be extracted while pattern matching
//occurs
namespace mch {
    template <> struct bindings<Var> {
        Members(Var::name);
    };

    template <> struct bindings<Abs> {
        Members(Abs::var, Abs::body);
    };

    template <> struct bindings<App> {
        Members(App::func,App::arg);
    };
} // of namespace mch

using namespace mch;

void change_vars(Term& t) {
    var<Var&>  v;
    var<Term&> t1, t2;
    var<std::string> s;

    Match(t)
    {
        Case(C<Var>(s)) { return; }
        Case(C<Abs>(&v,&t1)) {
            ((Var &) v).name = std::string("foobar");

            // "Match(t1) {" instead of the line blow
            // produces a SIGSEGV. Why is that?
            Match((Term &) t1){
                Case(C<Var>(v)) {
                    ((Var &) v).name = std::string("foobar");
                    return;
                }
                Otherwise() { return; }
            } EndMatch

            change_vars(t1);
            return ;
        }
        Case(C<App>(&t1,&t2)) {
            change_vars(t1);
            change_vars(t2);
            return ;
        }
    }
    EndMatch

    return;
}

std::ostream& operator<<(std::ostream& os, const Term& t) {
    std::string      s;
    var<const Var&>  v;
    var<const Term&> t1,t2;

    Match(t)
    {
        Case(C<Var>(s))       return os << s;
        Case(C<Abs>(&v,&t1))  return os << '\\' << v << '.' << t1;
        Case(C<App>(&t1,&t2)) return os << '(' << t1 << ')' << '(' << t2 << ')';
    }
    EndMatch

        return os; // To prevent all control path warning
}

//------------------------------------------------------------------------------

/// Substitutes every occurence of variable #v in #s with #t.
Term* substitute(const Term& s, const Var& v, const Term& t) { return nullptr; }

//------------------------------------------------------------------------------

Term* evaluate(Term* t)
{
    var<const Var&>  v;
    var<const Term&> t1,t2;

    Match(t)
    {
        Case(C<Var>()) return &match0;
        Case(C<Abs>()) return &match0;
        Case(C<App>(C<Abs>(&v,&t1),&t2))
            return evaluate(substitute(t1,v,t2));
        Otherwise() std::cerr << "Error: Invalid term";
    }
    EndMatch

        return nullptr;
}

//------------------------------------------------------------------------------

bool operator==(const Term&, const Term&);
inline bool operator!=(const Term& left, const Term& right) { return !(left == right); }

//------------------------------------------------------------------------------

bool operator==(const Term& left, const Term& right)
{
    //std::clog << "(" << left << ',' << right << ')' << std::endl;
    var<std::string> s;
    //var<const Var&>  v;
    var<const Term&> v,t,f;

    Match(left,right)
    {
        Case(C<Var>(s),     C<Var>(+s)     ) return true;
        Case(C<Abs>(&v,&t), C<Abs>(&+v,&+t)) return true;
        Case(C<App>(&f,&t), C<App>(&+f,&+t)) return true;
        Otherwise()                          return false;
    }
    EndMatch

        return false; // To prevent all control path warning
}

bool equal_terms(const Term& left, const Term& right)
{
    if (typeid(left) != typeid(right))
        return false;

    if (typeid(left) == typeid(Var))
    {
        return static_cast<const Var&>(left).name == static_cast<const Var&>(right).name;
    }
    else
        if (typeid(left) == typeid(Abs))
        {
            const Abs& l = static_cast<const Abs&>(left);
            const Abs& r = static_cast<const Abs&>(right);

            return equal_terms(*l.var, *r.var)
                && equal_terms(*l.body,*r.body);
        }
        else
            if (typeid(left) == typeid(App))
            {
                const App& l = static_cast<const App&>(left);
                const App& r = static_cast<const App&>(right);

                return equal_terms(*l.func,*r.func)
                    && equal_terms(*l.arg, *r.arg);
            }
}

//------------------------------------------------------------------------------

Term* random_term(int n)
{
    static Var* variables[] = {new Var("a"), new Var("b"), new Var("c"), new Var("d"), new Var("e"), new Var("f")};
    const int N = XTL_ARR_SIZE(variables);
    Var* v = variables[rand()%N];

    if (n < 3)
    {
        switch (n)
        {
        case 0: return v;
        case 1: return new Abs(v,v);
        case 2: return new App(new Abs(v,v),variables[rand()%N]);
        }
    }
    else
    {
        switch (n % 3)
        {
        case 0: return v;
        case 1: return new Abs(v,random_term(n/3));
        case 2: return new App(random_term(n/3),random_term(n/3));
        }
    }
}

//------------------------------------------------------------------------------

inline size_t compare_terms1(Term* left, Term* right) { return equal_terms(*left, *right); }
inline size_t compare_terms2(Term* left, Term* right) { return *left == *right; }

//------------------------------------------------------------------------------

int main()
{
    std::vector<Term*> arguments(N);

    for (size_t i = 0; i < N; ++i)
        arguments[i] = random_term(rand()%1000);

    Term *test = new Abs(new Var("f"), new Var("g + f"));
    // Should output "\fnord.g+fnord"
    std::cout << *test << std::endl;
    change_vars(*test);
    std::cout << *test << std::endl;

    for (size_t j = 0; j < N; ++j){
        change_vars(*arguments[j]);
        std::cout << "\t" << *arguments[j] << std::endl;
    }

    return 0;
}