Lambda calculus parser & compiler.

2+2.lambda

(λ+2.+22)(λmnfx.mf(nfx))((λs0.s(s0))(λnfx.f(nfx))(λfx.x))

astparser.js

function transform(ast) {
 console.log(ast)
 //return ast
 return {
  Program(node) {
   if(node.defs.length > 1) {
    return {
     type: 'Call',
     func: {
      type: 'Lambda',
      arg: transform(node.defs[0].name),
      body: transform({
       type: 'Program',
       defs: node.defs.slice(1),
       body: node.body
      })
     },
     arg: transform(node.defs[0].value)
    }
   } else if(node.defs.length > 0) {
    return {
     type: 'Call',
     func: {
      type: 'Lambda',
      arg: transform(node.defs[0].name),
      body: transform(node.body)
     },
     arg: transform(node.defs[0].value)
    }
   } else {
    return transform(node.body)
   }
  },
  Call(node) {
   if(node.args.length === 1) {
    return {
     type: 'Call',
     func: transform(node.func),
     arg: transform(node.args[0])
    }
   } else {
    return {
     type: 'Call',
     func: transform({
      type: "Call",
      func: node.func,
      args: node.args.slice(0, -1)
     }),
     arg: transform(node.args[node.args.length-1])
    }
   }
  },
  Lambda(node) {
   if(node.args.length === 1) {
    return {
     type: 'Lambda',
     arg: transform(node.args[0]),
     body: transform(node.body)
    }
   } else {
    return {
     type: 'Lambda',
     arg: transform(node.args[0]),
     body: transform({
      type: "Lambda",
      args: node.args.slice(1),
      body: node.body
     })
    }
   }
  },
  Identifier(node) {
   return node
  }
 }[ast.type](ast)
}
function tolambda(ast) {
 //return ast
 return {
  Call(node) {
   return `(${tolambda(node.func)} ${tolambda(node.arg)})`
  },
  Lambda(node) {
   return `(λ (${tolambda(node.arg)}) ${tolambda(node.body)})`
  },
  Identifier(node) {
   return node.name
  }
 }[ast.type](ast)
}

boolean.lambda

(λtf!&|.!(&f(|tf)))(λtf.t)(λtf.f)(λp.λtf.pft)(λpq.pqp)(λpq.ppq)

lambda.pegjs

{
// Compilation
function compilejs(exp) {
 if(exp.length == 1) {
  return exp[0].replace(/[^a-zA-Z_$]/g, function(c) {
   return "_$" + c.charCodeAt(0).toString(16) + "$_ /* " + c + " */"
  })
 } else if(exp.length == 2) {
  return compilejs(exp[0]) + "(" + compilejs(exp[1]) + ")"
 } else if(exp.length == 3) {
  return "(" + "function(" + compilejs(exp[1]) + ") {\n  "
   + "return " + compilejs(exp[2]).trim().split("\n").map(function(l) {
    return " " + l
   }).join("\n")
  + "\n})"
 }
}
function compilelambda(exp) {
 if(exp.length == 1) {
  return exp[0]
 } else if(exp.length == 2) {
  return "(" + compilelambda(exp[0])  + compilelambda(exp[1]) + ")"
 } else if(exp.length == 3) {
  return "(λ" + compilelambda(exp[1]) + "." + compilelambda(exp[2]) + ")"
 }
}
function compilelisp(exp) {
 if(exp.length == 1) {
  return exp[0].replace(/[^a-zA-Z!$%&\*\+\-\.\/:<=>\?@\^_~]/g, function(c) {
   return "_$" + c.charCodeAt(0).toString(16) + "$_ #| " + c + " |#"
  })
 } else if(exp.length == 2) {
  return "(" + compilelisp(exp[0]) + " " + compilelisp(exp[1]) + ")"
 } else if(exp.length == 3) {
  return "(lambda (" + compilelisp(exp[1]) + ")\n"
   + compilelisp(exp[2]).trim().split("\n").map(function(l) {
    return " " + l
   }).join("\n") + ")"
 }
}
// Output
function print(code) {
 return "Raw:\n" + (function() {
  try {
   var f = eval(code)
   console.log(f)
   var n = churchnum(f)
   var b = churchbool(f)
   return f
    + "\nChurch number: " + n
    + "\nChurch boolean: " + b
  } catch(e) {
   return "Error: " + e
  }
 })()
}
function churchnum(v) {
 try {
  var n = v(function(x) { return x + 1 })(0)
  if(typeof n == "number") {
   return n
  } else {
   return null
  }
 } catch(e) { return null }
}
function churchbool (v) {
 try {
  var b = v(true)(false)
  if(typeof b == "boolean") {
   return b
  } else {
   return null
  }
 } catch(e) { return null }
}
//Sugar
function lambda(a, r) {
 if(a.length == 1) {a
  return ["λ", a[0], r]
 } else {
  return ["λ", a[0], lambda(a.slice(1), r)]
 }
}
function call(f, a) {
 if(a.length == 1) {
  return [f, a[0]]
 } else {
  return [call(f, a.slice(0, -1)), a[a.length-1]]
 }
}
}

prog
 = _ e:(barecall / exp) _
 {
  var s = "", j = compilejs(e)
  s += "Pure lambda calculus:\n" + compilelambda(e) + "\n"
  s += "Javascript:\n" + j + "\n"
  s += "Lisp:\n" + compilelisp(e) + "\n"
  s += "====>\n"
  s += print(compilejs(e))
  return s }

exp
 = var
 / call
 / func
 / lparen _ e:exp _ rparen { return e }

var "variable"
 = n:(!lambda $[^\(\)λ\\\.\r\n\t ])
 { return [n[1]] }

call
 = lparen f:exp a:(_ exp)+ rparen
 {
  return call(f, a.map(function(e) {
   return e[1]
  }))
 }

barecall
 = f:exp a:(_ exp)+
 {
  return call(f, a.map(function(e) {
   return e[1]
  }))
 }

func
 = lambda a:(_ var)+ _ dot _ r:(barecall / exp)
 {
  return lambda(a.map(function(e) {
   return e[1]
  }), r)
 }


lparen = "("
rparen = ")"
dot    = "."
space "space"
 = [\r\n\t ]+
lambda "lambda"
 = ("λ" / "\\" / "lambda ") { return "λ" }

_ "whitespace" = space?

lambda2.pegjs

{
function transform(ast) {
 console.log(ast)
 //return ast
 return {
  Program(node) {
   if(node.defs.length > 1) {
    return {
     type: 'Call',
     func: {
      type: 'Lambda',
      arg: transform(node.defs[0].name),
      body: transform({
       type: 'Program',
       defs: node.defs.slice(1),
       body: node.body
      })
     },
     arg: transform(node.defs[0].value)
    }
   } else if(node.defs.length > 0) {
    return {
     type: 'Call',
     func: {
      type: 'Lambda',
      arg: transform(node.defs[0].name),
      body: transform(node.body)
     },
     arg: transform(node.defs[0].value)
    }
   } else {
    return transform(node.body)
   }
  },
  Call(node) {
   if(node.args.length === 1) {
    return {
     type: 'Call',
     func: transform(node.func),
     arg: transform(node.args[0])
    }
   } else {
    return {
     type: 'Call',
     func: transform({
      type: "Call",
      func: node.func,
      args: node.args.slice(0, -1)
     }),
     arg: transform(node.args[node.args.length-1])
    }
   }
  },
  Lambda(node) {
   if(node.args.length === 1) {
    return {
     type: 'Lambda',
     arg: transform(node.args[0]),
     body: transform(node.body)
    }
   } else {
    return {
     type: 'Lambda',
     arg: transform(node.args[0]),
     body: transform({
      type: "Lambda",
      args: node.args.slice(1),
      body: node.body
     })
    }
   }
  },
  Identifier(node) {
   return node
  }
 }[ast.type](ast)
}
function print(ast) {
 //return ast
 return {
  Call(node) {
   return `(${print(node.func)} ${print(node.arg)})`
  },
  Lambda(node) {
   return `(λ (${print(node.arg)}) ${print(node.body)})`
  },
  Identifier(node) {
   return node.name
  }
 }[ast.type](ast)
}
}

prog
 = _ d:(def _)* body:(exp _) _
 {
  return print(transform({
   type: 'Program',
   defs: d.map(d => d[0]),
   body: body[0]
  }))
 }

def
 = n:var _ ':=' _ v:exp
 {
  return {
   type: 'Definition',
   name: n,
   value: v
  }
 }

exp
 = var
 / call
 / func
 / lparen _ e:exp _ rparen { return e }

var "identifier"
 = n:(!lambda !':=' $[^\(\)λ\\\.\r\n\t ])+
 {
  return {
   type: 'Identifier',
   name: n.map(c => c[2]).join('')
  }
 }

call
 = lparen _ f:exp a:(_ exp)+ _ rparen
 {
  return {
   type: 'Call',
   func: f,
   args: a.map(a => a[1])
  }
 }

func
 = lparen lambda _ lparen a:(_ var)+ _ rparen _ r:exp _ rparen
 {
  return {
   type: 'Lambda',
   args: a.map(a => a[1]),
   body: r
  }
 }


lparen = "("
rparen = ")"
dot    = "."
sp "space"
 = [\r\n\t ]+
lambda "lambda"
 = ("λ" / "\\" / "lambda ") { return "λ" }

_ "whitespace" = sp?

lispy.pegjs

{
function call(func, args) {
 if(args.length === 1) {
  return [func, args[0]]
 } else {
  return [call(func, args.slice(0, -1)), args[args.length-1]]
 }
}
function lambda(args, body) {
 if(args.length === 1) {
  return ['lambda', args[0], body]
 } else {
  return [
   'lambda',
   args[0],
   lambda(args.slice(1), body),
  ]
 }
}
}

Program
 = _ exprs:(Expression _)* {
  return exprs.map(e => e[0])
 }

Expression
 = Variable
 / Lambda
 / Definition
 / Call

Variable
 = id:ident { return [id] }

Lambda
 = lparen _ lambda sp lparen _ 
  args:(args:(ident sp)* last:ident {
   return args.map(a => a[0]).concat([last])
  })
  _ rparen sp body:Expression _ rparen {
   return lambda(args, body)
  }

Definition
 = lparen _ def sp name:ident sp val:Expression _ rparen {
  return ['def', name, val]
 }

Call
 = lparen _ func:Expression args:(sp Expression)+ _ rparen {
  return call(func, args.map(a => a[1]))
 }

ident = $(!sp !def !lambda [^\(\)])+

lparen = '('
rparen = ')'
lambda = '\\' / 'λ' / 'lambda'
def = 'def'

sp = [ \r\n\t]+
_ = sp?