Skip to content

Instantly share code, notes, and snippets.

@MrChico

MrChico/Lambda.sol

Created September 9, 2016 09:38
Show Gist options
  • Save MrChico/df5e04622bc84e10dae9e317687392e5 to your computer and use it in GitHub Desktop.
Save MrChico/df5e04622bc84e10dae9e317687392e5 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
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();
}
}
}*/
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment