Lambda.sol

import "./RLP.sol";
import "./RLPW.sol";

library Lambda {
    using RLP for bytes;
    using RLP for RLP.RLPItem;
    using RLP for RLP.Iterator;
    /*  Takes an annotated ast as input, and returns a fully reduced ast
        Each node in the ast one of the three following formats:
        [1, function, argument] - Application
        [2, parameter, body] - Abstraction
        [3, name] - Identifier
    */
    //Context is an array of ast:s. Therefore, every name should be an index
    function first(RLP.RLPItem item) internal returns (RLP.RLPItem) {
        return item.iterator().next();
    }
    
    function second(RLP.RLPItem item) internal returns (RLP.RLPItem) {
        var iter = item.iterator();
        iter.next();
        return iter.next();
    }
    
    function third(RLP.RLPItem item) internal returns (RLP.RLPItem) {
        var list = item.toList();
        return list[2];
    }
    
    function testSecond(bytes encItem) returns (bytes) {
        return second(encItem.toRLPItem()).toBytes();
    }
    function testThird(bytes input) returns (bytes) {
        return third(input.toRLPItem()).toBytes();
    }
    
    function equal(bytes memory one, bytes memory two) returns (bool) {
        if (!(one.length == two.length)) {
            return false;
        }
        for (var i = 0; i<one.length; i++) {
            if (!(one[i] == two[i])) {
                return false;
            }
        }
        return true;
    }
    
    function equal(RLP.RLPItem one, RLP.RLPItem two) internal returns (bool) {
        return equal(one.toBytes(), two.toBytes());
    }
    
    function rlptester(bytes encodedContext) returns (bytes) {
        RLP.RLPItem memory context = encodedContext.toRLPItem(true);
        RLP.RLPItem[] memory contextList = context.toList();
        bytes memory newElement = new bytes(1);
        newElement[0] = 0x08;
        contextList[0] = newElement.toRLPItem(true);
        return contextList[0].toBytes();
    }
    
    /*
    //list = [[key, value], [key, value], [key, value]]
    //Observe that list needs to be a list of lists (TODO: is this good?)
    function lookup(RLP.RLPItem key, RLP.RLPItem list) internal returns (RLP.RLPItem) {
        var iter = list.iterator();
        for (var i = 0; i<list.items(); i++) {
            var potential = iter.next();
            if (equal(first(potential), key)) {
                return second(potential);
            }
        }
        bytes memory output = new bytes(0);
        return output.toRLPItem();
    }
    
    function testLookup(bytes encodedKey, bytes encodedList) returns (bytes) {
        var key = encodedKey.toRLPItem();
        var list = encodedList.toRLPItem();
        return lookup(key, list).toBytes();
    }
    */
    function strToBytes(string input) returns (bytes) {
        return bytes(input);
    }
    
    struct Term {
        RLP.RLPItem kindOfTerm;
        RLP.RLPItem content;
    }
    
    struct App {
        RLP.RLPItem fun; //Function (left hand side)
        RLP.RLPItem arg; //Argument (right hand side)
    }
    
    struct Abs {
        RLP.RLPItem param; // (left hand side)
        RLP.RLPItem body; //(right hand side)
    }
    
    struct Identifier {
        RLP.RLPItem name;
    }
    
    //bytes constant APP = hex"83617070";
    //bytes(4);
    //App[0] = byte(0x83);
    //APP[1] = 0x61;
    //APP[2] = 0x70;
    //APP[3] = 0x70;
    
    //Applications have two components, the function and its argument
    function isApp(RLP.RLPItem ast) internal returns (bool) {
        return ast.items()==2;
    }
    
    //Abstractions have three components, lambda, the parameter and the body
    function isAbs(RLP.RLPItem ast) internal returns (bool) {
        return ast.items()==3;
    }
    
    function isId(RLP.RLPItem ast) internal returns (bool) {
        return ast.items()==1;
    }
    
    function getParam(RLP.RLPItem abs) internal returns (RLP.RLPItem) {
        return second(abs);
    }
    
    function getBody(RLP.RLPItem abs) internal returns (RLP.RLPItem) {
        return third(abs);
    }
    /*
    //substitute all instances in the body that appear in the context
    function subst(RLP.RLPItem body, RLP.RLPItem context) internal returns (RLP.RLPItem) {
        var iter = body.iterator();
        RLP.RLPItem memory output;
        for (var i = 0; i<body.items(); i++) {
            var current = iter.next();
            if (!lookup(current,context).isNull()) {
                current = lookup(current, context);
            }
            output = RLPW.push(output, current);
        }
        return output;
    }
    */
    //mapping (string => RLP.RLPItem) context;
    
    struct keyValue {
        bytes key;
        RLP.RLPItem value;
    }
    
    
    //If key is found in context, change it for the value, otherwise, return the key
    function substi(bytes key, keyValue[] context) internal returns (RLP.RLPItem) {
        for (var i = 0; i<context.length; i++) {
            if (equal(key, context[i].key)) {
                return context[i].value;
            }
        }
        return key.toRLPItem();
    }
    /*
    function subst(RLP.RLPItem item, keyValue[] context) internal returns (RLP.RLPItem) {
        var iter = item.iterator();
        bytes memory output;
        for (var i = 0; i<item.items(); i++) {
            var current = iter.next();
            bytes memory key = current.toBytes();
            output = RLPW.concat(output, key);
        }
    }
    */

    /*
    function testsubst(bytes encBody, bytes encContext) returns (bytes) {
        var body = encBody.toRLPItem();
        var context = encContext.toRLPItem();
        return subst(body, context).toBytes();
    }
    */
    //For every application where both sides are abstractions, the rhs is added
    //to the context (which is a list of RLPItems). The de Bruijn indices then
    //give the position of the RLPItem numbered from the end
    /*
    function eval(RLP.RLPItem ast, RLP.RLPItem[] context) internal returns (RLP.RLPItem) {
        if (isApp(ast)) {
            //Application is the interesting case
            var iter = ast.iterator();
            var lhs = iter.next();
            var rhs = iter.next();
            if (isAbs(lhs) && isAbs(rhs)) {
                //var param = getParam(lhs);
                //var extraContext = RLPW.push(RLPW.toList(param), rhs);
                context.push(rhs);
                return eval(getBody(lhs), context);
            }
            else if (isAbs(lhs)) {
                rhs = eval(rhs, context);
            }
            else {
                lhs = eval(lhs, context);
            }
            return eval(lhs, rhs);
        }
        else if (isId(ast)) { //term is just an identifier
            return eval(context[context.length-1])
            return eval(lookup(ast, context), context);
        }
        //Abstraction is a value already
        else if (isAbs(ast)) {
            return ast;
        }
        //return [ast, RLPW.push(context, extraContext)];
    }
    
    function testEval(bytes encodedAST) returns (bytes) {
        var ast = encodedAST.toRLPItem();
        bytes memory emptyList = hex"c0";
        var context = emptyList.toRLPItem();
        return eval(ast, context).toBytes();
    }
    */
    function lookup(RLP.RLPItem key, RLP.RLPItem list) internal returns (RLP.RLPItem) {
        var iter = list.iterator();
        for (var i = 0; i<list.items(); i++) {
            var potential = iter.next();
            if (equal(first(potential), key)) {
                return second(potential);
            }
        }
        bytes memory output = new bytes(0);
        return output.toRLPItem();
    }

    function testLookup(bytes key, bytes contextList) returns (bytes) {
      return lookup(key.toRLPItem(), contextList.toRLPItem()).toBytes();
    }

    function eval(RLP.RLPItem ast) internal returns (RLP.RLPItem) {
      mapping (bytes => RLP.RLPItem) memory context;
      while(true) {
        if (isApp(ast)) {
            //Application is the interesting case
            var iter = ast.iterator();
            var lhs = iter.next();
            var rhs = iter.next();
            if (isAbs(lhs) && isAbs(rhs)) {
                var param = getParam(lhs);
		context[param.toBytes()] = rhs;
                ast = eval(getBody(lhs));
            }
            else if (isAbs(lhs)) {
                rhs = eval(rhs);
            }
            else {
                lhs = eval(lhs);
            }
        }
        else if (isId(ast)) { //term is just an identifier
	  ast = context[first(ast).toBytes()];
        }
        //Abstraction is a value already
	else {
            return ast;
        }
      }
    }
    /*
    function eval(RLP.RLPItem ast, RLP.RLPItem context) internal returns (RLP.RLPItem) {
        if (isApp(ast)) {
            //Application is the interesting case
            var iter = ast.iterator();
            var lhs = iter.next();
            var rhs = iter.next();
            if (isAbs(lhs) && isAbs(rhs)) {
                var param = getParam(lhs);
                var extraContext = RLPW.push(RLPW.makeList(param), rhs);
                context = RLPW.push(context, extraContext);
                return eval(getBody(lhs), context);
            }
            else if (isAbs(lhs)) {
                rhs = eval(rhs, context);
            }
            else {
                lhs = eval(lhs, context);
            }
            return eval(RLPW.combineInAList(lhs, rhs), context);
        }
        else if (isId(ast)) { //term is just an identifier
	  bytes memory tet = new bytes(1);
	  tet[0] = byte(0x45);
	  return tet.toRLPItem();
	  //            return eval(lookup(ast, context), context);
        }
        //Abstraction is a value already
        else if (isAbs(ast)) {
            return ast;
        }
        else {
	  return ast;
	  }///return [ast, RLPW.push(context, extraContext)];
    }*/
    
    function test_eval(bytes encodedAST) returns (bytes) {
      var ast = encodedAST.toRLPItem();
      //delete context;
      return eval(ast).toBytes();
    }

    function test_listCombine(bytes encLHS, bytes encRHS) returns (bytes) {
      return RLPW.combineInAList(encLHS.toRLPItem(), encRHS.toRLPItem()).toBytes();
    }
    
    /*
    function eval(bytes encodedAst, bytes encodedContext) returns (bytes) {
    //function eval(bytes encodedAst) returns (uint) {
        RLP.RLPItem memory ast = encodedAst.toRLPItem(true);
        //RLP.RLPItem memory context = encodedContext.toRLPItem(true);
        //RLP.RLPItem[] memory contextList = context.toList();
        byte[] memory contextBytes;
        //RLP.RLPItem[] memory contexter ;
        var iter = ast.iterator();
        var firstElem = iter.next();
        if (compare(firstElem.toData(), "λ")) { //abstraction. Is a value
            return ast.toBytes();
        }
        
        else if (firstElem.toData() == "") { //case of application
            var fun = iter.next();
            var arg = iter.next();
            if (fun.toUint() == 1 && arg.toUint() == 1) { //both fun and arg are abstractions
                var iterFun = fun.iterator();
                var param = iterFun.next();
                var name = param.iterator().next();
                keyValList = RLPW.push(RLPW.toList(iterLHS),
                contextList = RLPW.push(contextList, 
                //iter = fun.iterator();
                var lhs = iter.next();
                var rhs = iter.next();
                
                
            }
        }
    }*/
}