
/* This file contains the Java code corresponding to basic functions defined in
 http://www.cs.rice.edu/~taha/MetaOCaml/examples/lint.ml
 
 It might be also useful to look at:
 http://research.microsoft.com/~akenn/generics/gadtoop.pdf
 */

public class UnstagedLint {
    
    /*
     type exp = Int of int
     | Var of string
     | App of string * exp
     | Add of exp * exp
     | Sub of exp * exp
     | Mul of exp * exp
     | Div of exp * exp
     | Ifz of exp * exp * exp
     type def = Declaration of string * string * exp
     type prog = Program of def list * exp
     */
    
    public static interface Exp {
        public int eval(Env e, FEnv f);
    }
    
    public static class Int implements Exp {
        public int _value;
        public Int(int value) {
            _value = value;
        }
        public int eval(Env e, FEnv f) {
            return _value;
        }
    }
    
    public static class Var implements Exp {
        public String _s;
        public Var(String s) {
            _s = s;
        }
        public int eval(Env e, FEnv f) {
            return e.get(_s);
        }
    }
    
    public static class App implements Exp {
        public String _s;
        public Exp _body;
        public App(String s, Exp body) {
            _s = s;
            _body = body;
        }
        public int eval(Env e, FEnv f) {
            return f.get(_s).apply(_body.eval(e,f));
        }
    }
    
    public static class Add implements Exp {
        public Exp _left, _right;
        public Add(Exp left, Exp right) {
            _left = left;
            _right = right;
        }
        public int eval(Env e, FEnv f) {
            return _left.eval(e,f) + _right.eval(e,f);
        }
    }
    
    public static class Sub implements Exp {
        public Exp _left, _right;
        public Sub(Exp left, Exp right) {
            _left = left;
            _right = right;
        }
        public int eval(Env e, FEnv f) {
            return _left.eval(e,f) - _right.eval(e,f);
        }
    }
    
    public static class Mul implements Exp {
        public Exp _left, _right;
        public Mul(Exp left, Exp right) {
            _left = left;
            _right = right;
        }
        public int eval(Env e, FEnv f) {
            return _left.eval(e,f) * _right.eval(e,f);
        }
    }
    
    public static class Div implements Exp {
        public Exp _left, _right;
        public Div(Exp left, Exp right) {
            _left = left;
            _right = right;
        }
        public int eval(Env e, FEnv f) {
            return _left.eval(e,f) / _right.eval(e,f);
        }
    }
    
    public static class Ifz implements Exp {
        public Exp _test, _conseq, _alt;
        public Ifz(Exp test, Exp conseq, Exp alt) {
            _test = test;
            _conseq = conseq;
            _alt = alt;
        }
        public int eval(Env e, FEnv f) {
            return ((_test.eval(e,f)==0)?_conseq:_alt).eval(e,f);
        }
    }
    
    /*
     exception Yikes
     let env0 = fun x -> raise Yikes
     let fenv0 = env0
     let ext env x v = fun y -> if x=y then v else env y 
     */
    
    public static class Yikes extends RuntimeException { }
    
    // interface to represent int -> int functions
    public static interface Fun {
        public int apply(int param);
    }
    
    // environment; implemented as a function object from String to Exp
    public static interface Env {
        public int get(String y);
    }
    public static final Env env0 = new Env() {
        public int get(String s) { throw new Yikes(); }
    };
    
    public static Env ext(final Env env, final String x, final int v) {
        return new Env() {
            public int get(String y) {
                if (x.equals(y)) return v; else return env.get(y);
            }
        };
    }
    
    // function environment; implemented as a function object from String to Fun
    public static interface FEnv {
        public Fun get(String s);
    }
    public static final FEnv fenv0 = new FEnv() {
        public Fun get(String s) { throw new Yikes(); }
    };
    
    public static FEnv fext(final FEnv fenv, final String x, final Fun v) {
        return new FEnv() {
            public Fun get(String y) {
                if (x.equals(y)) return v; else return fenv.get(y);
            }
        };
    }
    
    public static class Declaration {
        public String _fun, _param;
        public Exp _body;
        public Declaration(String fun, String param, Exp body) {
            _fun = fun;
            _param = param;
            _body = body;
        }
        public String fun() { return _fun; }
        public String param() { return _param; }
        public Exp body() { return _body; }
    }
    
    public static class Program {
        public Declaration[] _defs;
        public Exp _body;
        public Program(Exp body, Declaration ... defs) {
            _defs = defs;
            _body = body;
        }
        public Declaration[] defs(){ return _defs; }
        public Exp body() { return _body; }
        
        public int peval(Env env, FEnv fenv) {
            return peval(env,fenv,0);
        }
        
        private int peval(final Env env, final FEnv fenv, int defIndex) {
            // match p with
            if (_defs.length<=defIndex) {
                //     Program ([],e) -> eval e env fenv
                return _body.eval(env,fenv);
            }
            else {
                //    |Program (Declaration (s1,s2,e1)::tl,e) ->
                //        let rec f x = eval e1 (ext env s2 x) (ext fenv s1 f)
                //        in peval (Program(tl,e)) env (ext fenv s1 f)
                final Declaration d = _defs[defIndex];
                final String dParam = d._param;
                final String dFun = d._fun;
                final Exp dBody = d._body;
                Fun f = new Fun() {
                    public int apply(int x) {
                        return dBody.eval(ext(env, dParam, x), fext(fenv, dFun, this));
                    }
                };
                return peval(env,fext(fenv, dFun, f),defIndex+1);
            }
        }
    }
    
    /*
     let rec eval e env fenv =
     match e with
     Int i -> i
     | Var s -> env s
     | App (s,e2) -> (fenv s)(eval e2 env fenv)
     | Add (e1,e2) -> (eval e1 env fenv)+(eval e2 env fenv)
     | Sub (e1,e2) -> (eval e1 env fenv)-(eval e2 env fenv)
     | Mul (e1,e2) -> (eval e1 env fenv)*(eval e2 env fenv)
     | Div (e1,e2) -> (eval e1 env fenv)/(eval e2 env fenv)
     | Ifz (e1,e2,e3) -> if (eval e1 env fenv)=0
     then (eval e2 env fenv)
     else (eval e3 env fenv)
     
     let rec peval p env fenv=
     match p with
     Program ([],e) -> eval e env fenv
     |Program (Declaration (s1,s2,e1)::tl,e) ->
     let rec f x = eval e1 (ext env s2 x) (ext fenv s1 f)
     in peval (Program(tl,e)) env (ext fenv s1 f)
     
     */
    
    /*
     let termFact = Program 
     ([Declaration 
     ("f","x",
     Ifz(Var "x", Int 1, Mul(Var"x",(App ("f", Sub(Var "x",Int 1))))))], 
     App ("f", Int 10))
     
     (* let rec f x = if x=0 then 0 else
     if (x-1)=0 then 1 else
     (f (x-1)) + (f (x-2))
     in f 20
     *)
     */
    
    public static Program termFact = new Program
        (new App("f", new Int(10)),
         new Declaration
             ("f", "x", new Ifz
                  (new Var("x"),
                   new Int(1),
                   new Mul(new Var("x"),
                           new App
                               ("f",
                                new Sub
                                    (new Var("x"),
                                     new Int(1)))))));
    
    /*
     let termFib = Program
     ([Declaration 
     ("f","x",
     Ifz(Var "x", Int 0, 
     Ifz(Sub(Var "x",Int 1), Int 1,
     Add(App ("f", Sub(Var "x",Int 1)),
     App ("f", Sub(Var "x",Int 2))))))], 
     App ("f", Int 20))
     
     */
    
    public static Program termFib = new Program
        (new App("f", new Int(10)),
         new Declaration("f", "x", new Ifz
                             (new Var("x"),
                              new Int(0),
                              new Ifz
                                  (new Sub
                                       (new Var("x"),
                                        new Int(1)),
                                   new Int(1),
                                   new Add
                                       (new App
                                            ("f",
                                             new Sub
                                                 (new Var("x"),
                                                  new Int(1))),
                                        new App
                                            ("f",
                                             new Sub
                                                 (new Var("x"),
                                                  new Int(2))))))));
    
    /*
     let rec f x = if x=0 then 1 else x*(f(x-1)) in f 10
     let rec f x = if x=0 then 1 else x*(f(x-1)) in f (10/2)
     */
    
    public static void main(String[] args) {
        int i = termFact.peval(env0, fenv0);
        System.out.println("fact(10) = "+i);
        i = termFib.peval(env0, fenv0);
        System.out.println("fib(10) = "+i);
    }
}
