Lambda calculus parser & compiler.

2+2.lambda

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

boolean.lambda

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

lambda.pegjs

{
// Printing
function printlambda(e) {
 return {
  Var: e => e.name,
  Call: e => `(${printlambda(e.func)}${printlambda(e.arg)})`,
  Lambda: e => `(\\${printlambda(e.arg)}.${printlambda(e.body)})`
 }[e.type](e)
}
// Manipulation
function free(e) {
 return {
  Var: e => new Set(e.name),
  Call: e => new Set([...free(e.func), ...free(e.arg)]),
  Lambda: e => new Set([...free(e.body)].filter(x => x != e.arg.name))
 }[e.type](e)
}
function beta(e) {

}
// Sugar
function lambda(a, r) {
 if(a.length == 1) {
  return {
   type: 'Lambda',
   arg: a[0],
   body: r
  }
 } else {
  return {
   type: 'Lambda',
   arg: a[0], 
   body: lambda(a.slice(1), r)
  }
 }
}
function call(f, a) {
 if(a.length == 1) {
  return {
   type: 'Call',
   func: f, 
   arg: a[0]
  }
 } else {
  return {
   type: 'Call',
   func: call(f, a.slice(0, -1)),
   arg: a[a.length-1]
  }
 }
}
}

prog
 = _ e:(barecall / exp) _
 {
  return [
   printlambda(e),
   [...free(e)]
  ]
 }

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

var "variable"
 = n:$(!lambda [^\(\)λ\\\.\r\n\t ]) { 
  return {
   type: 'Var',
   name: n
  }
 }

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?

lispy.pegjs

{
let varnum = 0
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 aequiv(ast) {
}
function aconvert(ast, n1, n2) {
 if(free(ast, n2)) {
  return ast
 } else {
  return {
   Call(node) {
    return {
     type: 'Call',
     func: aconvert(node.func, n1, n2),
     arg: aconvert(node.arg, n1, n2)
    }
   },
   Lambda(node) {
    return {
     type: 'Lambda',
     arg: aconvert(node.arg, n1, n2),
     body: aconvert(node.body, n1, n2)
    }
   },
   Identifier(node) {
    if(node.name === n1) {
     return {
      type: 'Identifier',
      name: n2
     }
    } else {
     return node
    }
   }
  }[ast.type](ast)
 }
}
function areduce(ast) {
}
function breduce(ast) {
 if(ast.type === 'Call') {
  let f = breduce(ast.func)
  let a = breduce(ast.arg)
  if(f.type === 'Lambda') {
   return breduce(substitute(breduce(f.body), f.arg.name, a))
  } else {
   return ast
  }
 } else {
  return ast
 }
}
function free(ast, name) {
 let vars = {
  Call(node) {
   return new Set([...free(node.func), ...free(node.arg)])
  },
  Lambda(node) {
   let vars = new Set(free(node.body))
   vars.delete(node.arg.name)
   return vars
  },
  Identifier(node) {
   return new Set([node.name])
  }
 }[ast.type](ast)
 return name ? vars.has(name) : vars
}
function bound(ast, name) {
 console.log(ast)
 let vars = {
  Call(node) {
   if(node.func.type === 'Lambda') {
    let vars = new Set([...bound(node.arg), ...bound(node.func.body)])
    vars.delete(node.func.arg.name)
    return vars
   } else {
    return new Set(bound(node.arg))
   }
  },
  Lambda(node) {
   return new Set([node.arg.name, ...bound(node.body)])
  },
  Identifier(node) {
   return new Set()
  }
 }[ast.type](ast)
 return name ? vars.has(name) : vars
}
function substitute(ast, name, node) {
 return {
  Call(n) {
   return {
    type: 'Call',
    func: substitute(n.func, name, node),
    arg: substitute(n.arg, name, node)
   }
  },
  Lambda(n) {
   if(!free(node, n.arg)) {
    return {
     type: 'Lambda',
     arg: n.arg,
     body: substitute(n.body, name, node)
    }
   } else {
    return substitute(aconvert(n, n.arg.name, '$' + varnum++), name, node)
   }
  },
  Identifier(n) {
   if(n.name === name) {
    return node
   } else {
    return n
   }
  }
 }[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)
}
}

test
 = a:prog n:var _ b:prog
 {
  return [[...free(a)], tolambda(substitute(a, n.name, b))]
 }

prog
 = _ d:(def _)* body:(exp _) _
 {
  console.log('=====')
  let ast = transform({
   type: 'Program',
   defs: d.map(d => d[0]),
   body: body[0]
  })
  return ast
  return {
   //code: tolambda(ast),
   reduced: tolambda(breduce(ast)),
   free: [...free(ast)]
  }
 }

def
 = n:var _ assign _ 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    = "."
assign = ":="
sp "space"
 = [\r\n\t ]+
lambda "lambda"
 = ("λ" / "\\" / "lambda ") { return "λ" }

_ "whitespace" = sp? / ';' [^\r\n]* '\n'