動機

這已經雪藏很久了，久在github page還沒用到之前就在我的google docs中 整理一下貼出來

Ch1 datatype in Java

abstract class N {}
class Zero extends N {}
class AddOne extends N {}

=>

datatype N = Zero | AddOne of N

就是datatype

The First Bit of Advice

When specifying a collection data, use abstract classes for datatypes and extended classes for variants.

Ch2 list recur ( [type] -> bool & [type(‘a)] -> ‘a)

onlyA

abstract class Ab {
    abstract boolean onlyA();
}

class Base extends Ab {
     boolean onlyA() { return true; }
}

class B extends Ab {
     Ab ab;

     B(Ab _ab) { ab = _ab; }
     boolean onlyA() { return false; }
}

class A extends Ab {
     Ab ab;

     A(Ab _ab) { ab = _ab; }
     boolean onlyA() { return ab.onlyA(); }
}

ab.{{func}}，在ML中的ab是{{func}}的參數！！

datatype Ab = Base | A of Ab | B of Ab

fun onlyA(Base) = true
    | onlyA(A(ab)) = onlyA(ab)
    | onlyA(B(ab)) = false
(onlyA : Ab -> bool)

hold_what

abstract class Ab {
    abstract boolean onlyA();
    abstract Object hold_what();
}

class Base extends Ab {
     Object hold;
     Base(Object _hold) { hold = _hold; }

     Object hold_what() { return hold; }
     boolean onlyA() { return true; }
}

class B extends Ab {
     Ab ab;
     B(Ab _ab) { ab = _ab; }

     boolean onlyA() { return false; }
     Object hold_what() { return ab.hold_what; }
}

class A extends Ab {
     Ab ab;

     A(Ab _ab) { ab = _ab; }
     boolean onlyA() { return ab.onlyA(); }
     Object hold_what() { return ab.hold_what; }
}

datatype ‘a Ab = Base of ‘a | A of Ab | B of Ab

fun hold_what(Base(x)) = x
    | hold_what(A(ab)) = hold_what(ab)
    | hold_what(B(ab)) = hold_what(ab)
(hold_what : ‘a Ab -> ‘a)

The Second Bit of Advice

When writing a function over a datatype, place a method in each of the variants that make up the datatype. If a field of a variant belongs to the same datatype, the method may call the corresponding method of the field in computing the function.

template method pattern

abstract class Point {
     abstract boolean closerTo(Point p);
     abstract int dist();
} 

class C extends Point {
     int x,y;

     C(int x,int y) { x = x; y= y;}
     boolean colserTo(Point p) { return dist() <= p.dist(); }
     int dist() { return abs(sqrt(x*x+y*y)); }
}

class M extends Point {
     int x,y;

     C(int x,int y) { x = x; y= y;}
     boolean colserTo(Point p) { return dist() <= p.dist(); }
     int dist() { return x+y; }
}

可以把相同的抽到abstract放著

abstract class Point {
     boolean closerTo(Point p) { return dist() <= p.dist(); }
     abstract int dist(); // template，template method pattern
}

my tip

在所有variant都一樣的function，可以放到abstract class

Ch3 list recur ([type] -> [type])

remA

abstract class Ab {
    abstract Ab remA();
}

class Base extends Ab {
     Ab remA() { return new Base(); }
}

class B extends Ab {
     Ab ab;

     B(Ab _ab) { ab = _ab; }
     Ab remA() { return new B(ab.remA()); }
}

class A extends Ab {
     Ab ab;

     A(Ab _ab) { ab = _ab; }
     Ab remA() { return ab.remA(); }
}

datatype Ab = Base | A of Ab | B of Ab

fun remA(Base) = Base
    | remA(A(ab)) = remA(ab)
    | remA(B(ab)) = B(remA(ab))
(remA : Ab -> Ab)

appB

abstract class Ab {
    abstract Ab remA();
    abstract Ab appB();
}

class Base extends Ab {
     Ab remA() { return new Base(); }
     Ab appB() { return new Base(); }
}

class B extends Ab {
     Ab ab;
     B(Ab _ab) { ab = _ab; }

     Ab remA() { return new B(ab.remA()); }
     Ab appB() { return new B(ab.appB()); }
}

class A extends Ab {
     Ab ab;

     A(Ab _ab) { ab = _ab; }
     Ab remA() { return ab.remA(); }
     Ab appB() { return new B(new A(ab.appB())); }
}

(這還需要翻成ML嗎)

如果 appB().remA()，其實與replace A成B是一樣的所以

repA

abstract class Ab {
    abstract Ab repA();
}

class Base extends Ab {
     Ab repA() { return new Base(); }
}

class B extends Ab {
     Ab ab;

     B(Ab _ab) { ab = _ab; }
     Ab repA() { return new B(ab.repA()); }
}

class A extends Ab {
     Ab ab;

     A(Ab _ab) { ab = _ab; }
     Ab repA() { return new B(ab.repA()); }
}

The Third Bit of Advice

When writing a function that returns values of a datatype, use new to create these values.

composite & interpreter pattern

abstract class PizzaD {
    abstract PizzaD remA();
    abstract PizzaD topAwC();
    abstract PizzaD subAbC();
}

class Crust extends PizzaD {
    PizzaD subAbC(){
        return new Crust();
    }
    PizzaD topAwC(){
        return new Crust();
    }
    PizzaD subAbC(){
        return new Crust();
    }
}

class Cheese extends PizzaD {
    PizzaD p;
    Cheese (PizzaD _p) {
        p = _p;
    }
    PizzaD remA(){
        return new Cheese(p.remA());
    }
    PizzaD topAwC(){
        return new Cheese(p.topAwC());
    }
    PizzaD subAbC(){
        return new Cheese(p.subAbC());
    }
}

class Olive extends PizzaD {
    PizzaD p;
    Olive (PizzaD _p) {
        p = _p;
    }
    PizzaD remA(){
        return new Olive(p.remA());
    }
    PizzaD topAwC(){
        return new Olive(p.topAwC());
    }
    PizzaD subAbC(){
        return new Olive(p.subAbC());
    }
}

class Anchovy extends PizzaD {
    PizzaD p;
    Anchovy (PizzaD _p) {
        p = _p;
    }
    PizzaD remA(){
        return p.remA();
    }
    PizzaD topAwC(){
        return new Cheese(new Anchovy(p.topAwC()));
    }
    PizzaD subAbC(){
        return new Cheese(p.subAbC());
    }
}

class Sausage extends PizzaD {
    PizzaD p;
    Sausage (PizzaD _p) {
        p = _p;
    }
    PizzaD remA(){
        return new Sausage(p.remA());
    }
    PizzaD topAwC(){
        return new Sausage(p.topAwC());
    }
    PizzaD subAbC(){
        return new Sausage(p.subAbC());
    }
}

這兩個pattern的本質是都是自己嵌套自己的datatype，所以可以達成如同list效果，可以無限嵌套來組合

Ch4 pattern match ver1(pass all args by myself & func in abstract class)

從Java到SML?

先複習onlyA

abstract class Ab {
    abstract boolean onlyA();
}

class Base extends Ab {
     boolean onlyA() { return true; }
}

class B extends Ab {
     Ab ab;
     B(Ab _ab) { ab = _ab; }
     boolean onlyA() { return false; }
}

class A extends Ab {
     Ab ab;
     A(Ab _ab) { ab = _ab; }
     boolean onlyA() { return ab.onlyA(); }
}

接著改寫成像ML的樣子，把所有動作都放到同一個地方

class OnlyA { // closure!! OR visitor
     boolean forBase() { return true; }
     boolean forA(Ab ab) { return ab.onlyA(); }
     boolean forB(Ab ab) { return false; }
}

datatype Ab = Base | A of Ab | B of Ab

fun onlyA(Base) = true
    | onlyA(A(ab)) = onlyA(ab)
    | onlyA(B(ab)) = false
(onlyA : Ab -> bool)

這下把執行動作從variant分離出來了．

但這要怎麼用？？ 如果這closure固定在一個所有variant可以碰到的地方的話

visitor (first try)

abstract class Ab {
    OnlyA func = new OnlyA();
    abstract boolean onlyA();
}

class Base extends Ab {
     boolean onlyA() { return func.forBase(); }
}

class B extends Ab {
     Ab ab;

     B(Ab _ab) { ab = _ab; }
     boolean onlyA() { return func.forB(ab); }
}

class A extends Ab {
     Ab ab;

     A(Ab _ab) { ab = _ab; }
     boolean onlyA() { return func.forA(ab); }
}

The Fourth Bit of Advice

When writing several functions for the same self-referential datatype, use visitor protocols so that all methods for a function can be found in a single class.

Ch5 equal!?(match self-defined type) & object as type var

原本應該要用equals去幹一個，但我懶所以用Integer

class Rem1 {
     IntList forNull() { return new Null(); }

     IntList forCons(IntList l, Object i) {
      if(1.equals(i))
        return l.rem1();
      else
        return new Cons(i,l.rem1());
    }
}

abstract class IntList {
      Rem1 func = new Rem1();
      abstract IntList rem1();
}

class Null extends IntList {
      IntList rem1() { return func.forNull(); }
}

class Cons extends IntList {
      Integer i;
      IntList next;

      // …..

      IntList rem1() { return func.forCons(next, i); }
}

這裡省略了一個地方，因為我這裡是用integer所以不用override euqals，但是書上是自訂的class(variant)，所以要用equals要自己實作，而相等的條件就是同類的class的實體，所以用instanceof．

SubstV

class SubstV {
    PieD forBot(Object n, Object o) {
        return new Bot();
    }
    PieD forTop (Object t, PieD r, Object n, Object o) {
        if (o.equals(t))
            return new Top(n, r.subst(n, o));
        else
            return new Top(t, r.subst(n, 0));
    }
}

abstract class PieD {
    RemV remFn = new RemV();
    SubsbV substFn = new SubstV();
    abstract PieD rem(Object o);
    abstract PieD subst(Object n, Object o);
}

class Bot extends PieD {
    PieD rem(Object o){
        return remFn.forBot(o);
    }
    PieD subst(Object n, Object o){
        return substFn.forBot(n, o)
    }
}

class Top extends PieD {
    Object t; // type var
    PieD r;
    Top(Object _t, PieD _r){
        t = _t;
        r = _r;
    }
    PieD rem(Object o){
        return remFn.forTop(t, r, o);
    }
    PieD subst(Object n, Object o){
        return substFn.forTop(t, r, n, o)
    }
}

這是不是與list很像，不過注意到subst的Object n, Object o在遞迴的時候其實不會變，所以應該要把它抽出來，scheme是letrec或curry，ML是curry，那這邊要怎麼做？

Ch6 pattern match ver2 (pass closure to invoker & curry func)

class SubstV {
    Object n,o;

    // ….
    PieD forBot() {
        return new Bot();
    }
    PieD forTop (Object t, PieD r) {
        if (o.equals(t))
            return new Top(n, r.subst(this));
        else
            return new Top(t, r.subst(this));
    }
}

如果照原本的把closure固定在一個所有variant可以碰到的地方的方式，我們沒機會使用我們自己new出來的clousre!!

從upper class傳closure變成從參數傳

那要做出一個空間出來！！

abstract class PieD {
    abstract PieD subst(SubstV func);
}

class Bot extends PieD {
    PieD subst(SubstV func){
        return func.forBot();
    }
}

class Top extends PieD {
    Object t;
    PieD r;

    Top(Object _t, PieD _r){
        t = _t;
        r = _r;
    }

    PieD subst(SubstV func){
        return func.forTop(t,r);
    }
}

每個closure都是有for…,for…的話可以拉上去變成abstract嗎？ 可以！！ 直接看像是function template，但是當成function type就是PieD -> PieD!!

所以這其實代表的是function type，與ml越來越像了

interface PieI {
     PieD forBot();
     PieD forTop(Object t,PieD p);
}

(subst : ‘a Pie -> ‘a Pie)

都抽成interface了，invoke的地方要不要統一一下

假設我們有許多closure，那每個都要給一個function name在variant的class，等著丟PieI的實體嗎？ 可以設一個invoke(在書上是accept)接收closure，再把需要的參數灌進去．

abstract class PieD {
    abstract PieD invoke(PieI func);
}

class Bot extends PieD {
    PieD invoke(PieI func){
        return func.forBot();
    }
}

class Top extends PieD {
    Object t;
    PieD r;

    Top(Object _t, PieD _r){
        t = _t;
        r = _r;
    }

    PieD invoke(PieI func){
        return func.forTop(t,r);
    }
}

class SubstV {
    Object n,o;

    // ….
    PieD forBot() {
        return new Bot();
    }

    PieD forTop (Object t, PieD r) {
        if (o.equals(t))
            return new Top(n, r.invoke(this));
        else
            return new Top(t, r.invoke(this));
    }
}

如果clousre有狀態?

如果是有acc（有狀態的）的函數

class LtdSubstV implements PieVisitorI {
    int c;
    Object n;
    Object o;

    LtdSubstV(int _c, Object _n, Object _o) {
        c = _c;
        n = _n;
        o = _o;
    }

    public PieD forBot() {
        return new Bot();
    }

    public PieD forTop(Object t, PieD r) {
        if (c == 0)
            return new Top(t, r);
        else
            if (o.equals(t))
                return new Top(n, r.accept(this); //這裡的狀態應該改變
            else
                return new Top(t, r.accept(this));
    }

}

那就new一下，畢竟這裡是functional programming

class LtdSubstV implements PieVisitorI {
    int c;
    Object n;
    Object o;

    LtdSubstV(int _c, Object _n, Object _o) {
        c = _c;
        n = _n;
        o = _o;
    }

    public PieD forBot() {
        return new Bot();
    }

    public PieD forTop(Object t, PieD r) {
        if (c == 0)
            return new Top(t, r);
        else
            if (o.equals(t))
                return new Top(n, r.accept(LtdSubstV(c-1, n, o)));
            else
                return new Top(t, r.accept(this));
    }
}

The sixth Bit of Advice

When the additional consumed values change for a self-referenced use of a visitor, don’t forget to create a new visitor.

Ch7 tree recur & object as type var

tree走訪

abstract class TreeD {
    abstract boolean accept(bTreeVisitorI ask);
    abstract int accept(iTreeVisitorI ask);
    abstract TreeD accept(tTreeVisitorI ask);
}

class Bud extends TreeD {
    boolean accept(bTreeVisitorI ask) {
        return ask.forBud();
    }
    int accept(iTreeVisitorI ask) {
        return ask.forBud();
    }
    TreeD accept(tTreeVisitorI ask) {
        return ask.forBud();
    }
}

class Flat extends TreeD {
    FruitD f;
    TreeD t;
    Flat(FruitD _f, TreeD _t) {
        f = _f;
        t = _t;
    }
    boolean accept(bTreeVisitorI ask) {
        return ask.forFlat(f, t);
    }
    int accept(iTreeVisitorI ask) {
        return ask.forFlat(f, t);
    }
    TreeD accept(tTreeVisitorI ask) {
        return ask.forFlat(f, t);
    }
}

class Split extends TreeD {
    TreeD l;
    TreeD r;
    Split(Treed _l, TreeD _r) {
        l = _l;
        r = _r;
    }
    boolean accept(bTreeVisitorI ask) {
        return ask.forSplit(l, r);
    }
    int accept(iTreeVisitorI ask) {
        return ask.forSplit(l, r);
    }
    TreeD accept(tTreeVisitorI ask) { 
        return ask.forFlat(l, r);
    }
}

不想每個return type都寫一個interface (那個時候應該還沒有泛型)

把不同回傳type的值合併起來

interface TreeVisitorI {
    Object forBud();
    Object forFlat(FruitD f, TreeD t);
    Object forSplit(TreeD l, TreeD r);
}

abstract class TreeD {
    abstract Object accept(TreeVisitorI ask);
}

class IsFlatV implements TreeVisitorI {
    public Object forBud() {
        return new Boolean(true);
    }

    public Object forFlat(FruitD f, TreeD t) {
        return t.accept(this);
    }

    public Object forSplit(TreeD l, TreeD r) {
        return new Boolean(false);
    }
}

class IsSplitV implements bTreeVisitorI {
    public boolean forBud() {
        return new Boolean(true);
    }

    public boolean forFlat(FruitD f, TreeD t) {
        return new Boolean(false);
    }

    public boolean forSplit(TreeD l, TreeD r) {
        if (((Boolean)(l.accept(this))).booleanValue())
            return r.accept(this);
        else
            return new Boolean(false);
    }
}

因為我們目前沒有範型，用範型才比較正常

The seventh bit of advice

When designing visitor protocols for many different types, create a unifying protocol using Object.

Ch8 arith(abstract actions) & 2 types of inherence

到處都是cast

interface ExprVisitorI {
    Object forPlus(ExprD l, ExprD r); // 相加
    Object forDiff(ExprD l, ExprD r); // 相减
    Object forProd(ExprD l, ExprD r); // 相乘
    Object forConst(Object c); // 常量
}

class IntEvalV implements ExprVisitorI {
    public Object forPlus(ExprD l, ExprD r){
        return plus(l.accept(this), r.accept(this));
    }

    public Object forDiff(ExprD l, ExprD r){
        return diff(l.accept(this), r.accept(this));
    }

    public Object forProd(ExprD l, ExprD r){
        return prod(l.accept(this), r.accept(this));
    }

    public Object forConst(Object c){
        return c;
    }

    Object plus(Object l, Object r){
        return new Integer(((Integer)l).intValue()+((Integer)r).intValue());
    }

    Object diff(Object l, Object r){
        return new Integer(((Integer)l).intValue()-((Integer)r).intValue());
    }

    Object prod(Object l, Object r){
        return new Integer(((Integer)l).intValue()*((Integer)r).intValue());
    }
}

為了避免大量的轉換（其實就是隱藏plus, diff, prod的實作），所以把general action拉出來．

再抽象一次

假設這裡要一個對set操作的eval，那可以

  1. 直接cast用method，簡單暴力
class SetEvalV extends IntEvalV {
    Object plus(Object l, Object r){
        return ((SetD)l).plus((SetD)r);
    }

    Object diff(Object l, Object r){
        return ((SetD)l).diff((SetD)r);
    }

    Object prod(Object l, Object r){
        return ((SetD)l).prod((SetD)r);
    }
}
  1. 重新拉一個class出來
abstract class EvalD implements ExprVisitorI {
    public Object forPlus(ExprD l, ExprD r){
        return plus(l.accept(this), r.accept(this));
    }

    public Object forDiff(ExprD l, ExprD r){
        return diff(l.accept(this), r.accept(this));
    }

    public Object forProd(ExprD l, ExprD r){
        return prod(l.accept(this), r.accept(this));
    }

    public Object forConst(Object c){
        return c;
    }

    abstract Object plus(Object l, Object r);
    abstract Object diff(Object l, Object r);
    abstract Object prod(Object l, Object r);
}

class IntEvalV extends EvalD {
    Object plus(Object l, Object r){
        return new Integer(((Integer)l).intValue()+((Integer)r).intValue());
    }

    Object diff(Object l, Object r){
        return new Integer(((Integer)l).intValue()-((Integer)r).intValue());
    }

    Object prod(Object l, Object r){
        return new Integer(((Integer)l).intValue()*((Integer)r).intValue());
    }
}

class SetEvalV extends EvalD {
    Object plus(Object l, Object r){
        return ((SetD)l).plus((SetD)r);
    }

    Object diff(Object l, Object r){
        return ((SetD)l).diff((SetD)r);
    }

    Object prod(Object l, Object r){
        return ((SetD)l).prod((SetD)r);
    }
}

The eighth bits of advice

When extending a class, use overriding to enrich its functionality.

繼承有兩種，一個是繼承自通用class來做出自己想要的功能，這是理想case；而第二種是複寫原有功能的繼承，雖然說這不合理，然而現實中常常看不到別人的class，只能這樣來使用．

Ch9 extend visitor

用繼承增加支援的type

當要為datatype用那種比較討厭的繼承時來加variant時，visitor要怎麼調整

datatype shape = Union of Shape * Shape | …

func f = …

func newF(Union(a,b)) = ….
      | newF(x) = f(x)

class Union extends ShapeD {
    ShapeD s;
    ShapeD t;

    Union(ShapeD _s, ShapeD _t) {
        s = _s;
        t = _t;
    }

    boolean accept(ShapeVisitorI ask) { // 這裡是implement原本的abstract
        ((UnionVisitorI)ask).forUnion(s, t); //要自己轉，不然看不到多加的part
    }
}

interface UnionVisitorI extends ShapeVisitorI { // interface 可以 extends !!!
    boolean forUnion(ShapeD s, ShapeD t);
}

class UnionHasPtV extends HasPtV implements ShapeVisitorI {
    UnionHasPtV(PointD _p) {
        super(_p);
    }

    public boolean forUnion(ShapeD s, ShapeD t) {
        return s.accept(this) || t.accept(this);
    }
}

抽象constructor

這行Trans(CartP(3,7),Union(Square(10),Circle(10))).invoke(UnionV) 陪下面的code，會出事

class HasPtV implements ShapeVisitorI {
    PointD p;

    HasPtV(PointD _p) {
        p = _p;
    }

    public boolean forCircle(int r) {
        return p.distanceTo0() <= r;
    }

    public boolean forSquare(int s) {
        return p.x <= s && p.y <= s;
    }

    public boolean forTrans(PointD q, ShapeD s) {
        return s.accept(new HasPtV(p.minus(q))); // 兇手
    }
}

因為Trans會call到上一層的visitor，之後就回不來UnionHasPtV了！！

所以要有辦法讓它能夠產生新的，抽象constrctor

class HasPtV implements ShapeVisitorI {
    PointD p;

    HasPtV(PointD _p) {
        p = _p;
    }

    ShapeVisitorI newHasPt(PointD p) { // factory method
        return new HasPtV(p);
    }

    public boolean forCircle(int r) {
        return p.distanceTo0() <= r;
    }

    public boolean forSquare(int s) {
        return p.x <= s && p.y <= s;
    }

    public boolean forTrans(PointD q, ShapeD s) {
        return s.accept(newHasPtV(p.minus(q)));
    }
}

The nineth bit of advice

If a datatype may have to be extended, be forward looking and use a constructor-like(override) method so that visitors can be extended too.

factory method pattern

class UnionHasPtV extends HasPtV implements UnionVisitorI {
    UnionHasPtV(PointD _p) {
        super(_p);
    }

    ShapeVisitorI newHasPt(PointD p) { // factory method
        return new UnionHasPtV(p);
    }

    public boolean forUnion(ShapeD s, ShapeD t) {
        return s.accept(this) || t.accept(this);
    }
}

Ch10 Visitor pattern(obj作為打包好的參數&state[直接修改obj])

觀察在class的invoke，都只是把field的東西傳到closure中而已，那object其實可以直接access自己的field，那可以直接傳obj?

interface PieVisitorI {
    Object forBot(Bot that);
    Object forTop(Top that);
}

abstract class PieD {
    abstract Object accept(PieVisitorI ask);
}

class Bot extends PieD {
    Object accept(PieVisitorI ask) {
        return ask.forBot(this);
    }

}

class Top extends PieD {
    Object t;
    PieD r;

    Top(Object _t, Object _r) {
        t = _t;
        r = _r;

    }

    Object accept(PieVisitorI ask) {
        return ask.forTop(this);

    }
}

class OccursV implements PieVisitorI {
    Object a;

    OccursV(Object _a) {
        a = _a;
    }

    public Object forBot(Bot that) {
        return new Integer(0);
    }

    public Object forTop(Top that) {
        if (that.t.equals(a))
            return new Integer(((Integer)(that.r.accept(this))).intValue()+1);
        else
            return that.r.accept(this);
    }
}

現在是直接傳物件，那能不能直接改，這樣就不用new了

class SubstV implements PieVisitorI {
    Object n;
    Object o;

    SubstV(Object _n, Object _o) {
        n = _n;
        o = _o;
    }

    public Object forBot(Bot that) {
        return new Bot();
    }

    public Object forTop(Top that) {
        if (o.equals(that.t))
            return new Top(n, (PieD)(that.r).accept(this));
        else
            return new Top(that.t, (PieD)(that.r).accept(this));
    }
}

class SubstV implements PieVisitorI {
    Object n;
    Object o;

    SubstV(Object _n, Object _o) {
        n = _n;
        o = _o;
    }

    public Object forBot(Bot that) {
        return that;
    }

    public Object forTop(Top that) {
        if (o.equals(that.t))
            that.t = n;  //直接被改完了，同時r也沒變，不用設回去
        that.r.accept(this);
        return that;
    }
}

the tenth bit of advice

When modifications to objects are needed, use a class to insulate the operations that modify objects. Otherwise, beware the consequences of your actions.

Y in Java

datatype 'a T = Into of 'a T -> 'a

fun Y(f)= H(f)(Into(H(f)))
and H(f)(a) = f(G(a))
and G(Into(a))(x) = a(Into(a))(x);

class Mk {
  Func apply(Func f) {
      return new Fact(f);
  }
}

class Fact {
  Func f;

  Fact(Func _f) {
      f = _f;
  }

  Integer apply(Integer x) {
      if (x == 0) return 1;
      else return x * f.apply(x - 1);
  }

}

class Y {
  Func apply(Mk f) {
      H h = new H(f);
      return h.apply(h);
  }
}

class H {
  Mk f;

  H(Mk _f) {
      f = _f;
  }

  H apply(H a) {
      return f.apply(new G(a));
  }
}

class G {
  H h;
  G(H _h) {
      h = _h;
  }
  Integer apply(Integer x) {
      return h.apply(h).apply(x);
  }
}