История изменений
Исправление quasimoto, (текущая версия) :
Это не алгоритм, а концепция. На C++ это скорее всего будут узлы AST как классы наследуемые от интерфейса с методами AST, типа
#include <vector>
#include <iostream>
template <typename Value>
struct Exp {
virtual ~Exp() {}
virtual Value eval() const = 0;
virtual std::string show() const = 0;
};
template <typename Value>
class Lit : public Exp<Value> {
const Value value;
public:
Lit(Value const& value_) : value(value_) {}
Value eval() const { return value; }
std::string show() const { return "lit(" + std::to_string(value) + ")"; }
};
template <typename Value>
class Add : public Exp<Value> {
using E = Exp<Value>;
const E &x, &y;
public:
Add(E const& x_, E const& y_) : x(x_), y(y_) {}
Value eval() const { return x.eval() + y.eval(); }
std::string show() const { return "add(" + x.show() + ", " + y.show() + ")"; }
};
template <typename Value>
struct Mul : public Exp<Value> {
using E = Exp<Value>;
const E &x, &y;
public:
Mul(E const& x_, E const& y_) : x(x_), y(y_) {}
Value eval() const { return x.eval() * y.eval(); }
std::string show() const { return "mul(" + x.show() + ", " + y.show() + ")"; }
};
template <typename Value>
class GarbagePool {
std::vector<Exp<Value>*> garbage_pool;
public:
~GarbagePool() { for (auto e : garbage_pool) delete e; }
Exp<Value>& collect(Exp<Value>* e) { garbage_pool.push_back(e); return *e; }
};
int main() {
GarbagePool<int> gp;
using Exp = Exp<int>;
auto lit = [&gp](int x) -> Exp& { return gp.collect(new Lit<int>(x)); };
auto mul = [&gp](Exp const& x, Exp const& y) -> Exp& {
return gp.collect(new Mul<int>(x, y));
};
auto add = [&gp](Exp const& x, Exp const& y) -> Exp& {
return gp.collect(new Add<int>(x, y));
};
auto &exp = mul(add(lit(1), lit(2)), add(lit(3), lit(4)));
std::cout << exp.show() << " => " << exp.eval() << std::endl;
}
и тут ещё Eq нет. И Read. И пробельных строк :)
Ещё для примера — http://llvm.org/docs/tutorial, там C++ и OCaml.
А в топике функция с вложенным pattern-matching-ом + guards и перетасовыванием дерева, например строчка
transform (Lam x (App e1 e2)) = App (App s (transform (Lam x e1))) (transform (Lam x e2))
это значит, что «функция» transform «принимает» Exp<Value> const& и _если_ это не просто объект класса наследника, а объект в форме Lam(x, App(e1, e2)) где Lam и App — конструкторы классов, а x, e1 и e2 связываются с соответствующими поддеревьями, _то_ возвращается новый (динамическая аллокация та же) объект App(App(s, transform(Lam(x, e1))), transform(Lam(x, e2))). Одна проблема это эта «функция» которая «принимает» — expression problem, нужно какие-то визиторы городить, другая — арену для динамических объектов делать. Ну и с остальными строчками так же. Guards:
transform (Lam x l@(Lam y e)) | free x e = transform (Lam x (transform l))
аналогично, но _только если_ выполняется условие free x e (в AST эта переменная свободна), иначе переходим к анализу следующего case.
Исправление quasimoto, :
Это не алгоритм, а концепция. На C++ это скорее всего будут узлы AST как классы наследуемые от интерфейса с методами AST, типа
#include <vector>
#include <iostream>
template <typename Value>
struct Exp {
virtual ~Exp() {}
virtual Value eval() const = 0;
virtual std::string show() const = 0;
};
template <typename Value>
class Lit : public Exp<Value> {
const Value value;
public:
Lit(Value const& value_) : value(value_) {}
Value eval() const { return value; }
std::string show() const { return "lit(" + std::to_string(value) + ")"; }
};
template <typename Value>
class Add : public Exp<Value> {
using E = Exp<Value>;
const E &x, &y;
public:
Add(E const& x_, E const& y_) : x(x_), y(y_) {}
Value eval() const { return x.eval() + y.eval(); }
std::string show() const { return "add(" + x.show() + ", " + y.show() + ")"; }
};
template <typename Value>
struct Mul : public Exp<Value> {
using E = Exp<Value>;
const E &x, &y;
public:
Mul(E const& x_, E const& y_) : x(x_), y(y_) {}
Value eval() const { return x.eval() * y.eval(); }
std::string show() const { return "mul(" + x.show() + ", " + y.show() + ")"; }
};
template <typename Value>
class GarbagePool {
std::vector<Exp<Value>*> garbage_pool;
public:
~GarbagePool() { for (auto e : garbage_pool) delete e; }
Exp<Value>& collect(Exp<Value>* e) { garbage_pool.push_back(e); return *e; }
};
int main() {
GarbagePool<int> gp;
using Exp = Exp<int>;
auto lit = [&gp](int x) -> Exp& { return gp.collect(new Lit<int>(x)); };
auto mul = [&gp](Exp const& x, Exp const& y) -> Exp& {
return gp.collect(new Mul<int>(x, y));
};
auto add = [&gp](Exp const& x, Exp const& y) -> Exp& {
return gp.collect(new Add<int>(x, y));
};
auto &exp = mul(add(lit(1), lit(2)), add(lit(3), lit(4)));
std::cout << exp.show() << " => " << exp.eval() << std::endl;
}
и тут ещё Eq нет. И Read. И пробельных строк :)
Ещё для примера — http://llvm.org/docs/tutorial, там C++ и OCaml.
А в топике функция с вложенным pattern-matching-ом + guards и перетасовыванием дерева, например строчка
transform (Lam x (App e1 e2)) = App (App s (transform (Lam x e1))) (transform (Lam x e2))
это значит, что «функция» transform «принимает» Exp<Value> const& и _если_ это не просто объект класса наследника, а объект в форме Lam(x, App(e1, e2)) где Lam и App — конструкторы классов, а x, e1 и e2 связываются с соответствующими поддеревьями, _то_ возвращается новый (динамическая аллокация та же) объект App(App(s, transform(Lam(x, e1))), transform(Lam(x, e2))). Одна проблема это эта «функция» которая «принимает» — expression problem, нужно какие-то визиторы городить, другая — арену для динамических объектов делать. Ну и с остальными строчками так же. Guards:
transform (Lam x l@(Lam y e)) | free x e = transform (Lam x (transform l))
аналогично, но _только если_ выполняется условие free x e (в AST эта переменная не свободна), иначе переходим к анализу следующего case.
Исходная версия quasimoto, :
Это не алгоритм, а концепция. На C++ это скорее всего будут узлы AST как классы наследуемые от интерфейса с методами AST, типа
#include <vector>
#include <iostream>
template <typename Value>
struct Exp {
virtual ~Exp() {}
virtual Value eval() const = 0;
virtual std::string show() const = 0;
};
template <typename Value>
class Lit : public Exp<Value> {
const Value value;
public:
Lit(Value const& value_) : value(value_) {}
Value eval() const { return value; }
std::string show() const { return "lit(" + std::to_string(value) + ")"; }
};
template <typename Value>
class Add : public Exp<Value> {
using E = Exp<Value>;
const E &x, &y;
public:
Add(E const& x_, E const& y_) : x(x_), y(y_) {}
Value eval() const { return x.eval() + y.eval(); }
std::string show() const { return "add(" + x.show() + ", " + y.show() + ")"; }
};
template <typename Value>
struct Mul : public Exp<Value> {
using E = Exp<Value>;
const E &x, &y;
public:
Mul(E const& x_, E const& y_) : x(x_), y(y_) {}
Value eval() const { return x.eval() * y.eval(); }
std::string show() const { return "mul(" + x.show() + ", " + y.show() + ")"; }
};
template <typename Value>
class GarbagePool {
std::vector<Exp<Value>*> garbage_pool;
public:
~GarbagePool() { for (auto e : garbage_pool) delete e; }
Exp<Value>& collect(Exp<Value>* e) { garbage_pool.push_back(e); return *e; }
};
int main() {
GarbagePool<int> gp;
using Exp = Exp<int>;
auto lit = [&gp](int x) -> Exp& { return gp.collect(new Lit<int>(x)); };
auto mul = [&gp](Exp const& x, Exp const& y) -> Exp& {
return gp.collect(new Mul<int>(x, y));
};
auto add = [&gp](Exp const& x, Exp const& y) -> Exp& {
return gp.collect(new Add<int>(x, y));
};
auto &exp = mul(add(lit(1), lit(2)), add(lit(3), lit(4)));
std::cout << exp.show() << " => " << exp.eval() << std::endl;
}
и тут ещё Eq нет. И Read. И пробельных строк :)
Ещё для примера — http://llvm.org/docs/tutorial, там C++ и OCaml.
А в топике функция с вложенным pattern-matching-ом + guards и перетасовыванием дерева, например строчка
transform (Lam x (App e1 e2)) = App (App s (transform (Lam x e1))) (transform (Lam x e2))
это значит, что «функция» transform «принимает» Exp<Value> const& и _если_ это не просто объект класса наследника, а объект в форме Lam(x, App(e1, e2)) где Lam и App — конструкторы классов, а x, e1 и e2 связываются с соответсвующими поддеревьями, _то_ возвращается новый (динамическая аллокация та же) объект App(App(s, transform(Lam(x, e1))), transform(Lam(x, e2))). Одна проблема это эта «функция» которая «принимает» — expression problem, нужно какие-то визиторы городить, другая — арену для динамических объектов делать. Ну и с остальными строчками так же.