Skip to content

Instantly share code, notes, and snippets.

@PaulMaynard
Last active April 28, 2017 15:35

Revisions

  1. PaulMaynard revised this gist Apr 28, 2017. 1 changed file with 3 additions and 0 deletions.
    3 changes: 3 additions & 0 deletions lambda.pegjs
    Original file line number Diff line number Diff line change
    @@ -14,6 +14,9 @@ function free(e) {
    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) {
  2. PaulMaynard revised this gist Apr 28, 2017. 1 changed file with 48 additions and 89 deletions.
    137 changes: 48 additions & 89 deletions lambda.pegjs
    Original file line number Diff line number Diff line change
    @@ -1,106 +1,61 @@
    {
    // 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 }
    // 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)
    }
    function churchbool (v) {
    try {
    var b = v(true)(false)
    if(typeof b == "boolean") {
    return b
    } else {
    return null
    }
    } catch(e) { return null }
    // 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)
    }
    //Sugar
    // Sugar
    function lambda(a, r) {
    if(a.length == 1) {a
    return ["λ", a[0], r]
    if(a.length == 1) {
    return {
    type: 'Lambda',
    arg: a[0],
    body: r
    }
    } else {
    return ["λ", a[0], lambda(a.slice(1), r)]
    return {
    type: 'Lambda',
    arg: a[0],
    body: lambda(a.slice(1), r)
    }
    }
    }
    function call(f, a) {
    if(a.length == 1) {
    return [f, a[0]]
    return {
    type: 'Call',
    func: f,
    arg: a[0]
    }
    } else {
    return [call(f, a.slice(0, -1)), a[a.length-1]]
    return {
    type: 'Call',
    func: call(f, a.slice(0, -1)),
    arg: 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 }
    return [
    printlambda(e),
    [...free(e)]
    ]
    }

    exp
    = var
    @@ -109,8 +64,12 @@ exp
    / lparen _ e:exp _ rparen { return e }

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

    call
    = lparen f:exp a:(_ exp)+ rparen
    @@ -145,4 +104,4 @@ space "space"
    lambda "lambda"
    = ("λ" / "\\" / "lambda ") { return "λ" }

    _ "whitespace" = space?
    _ "whitespace" = space?
  3. PaulMaynard revised this gist Jul 21, 2016. 1 changed file with 4 additions and 17 deletions.
    21 changes: 4 additions & 17 deletions lispy.pegjs
    Original file line number Diff line number Diff line change
    @@ -1,13 +1,5 @@
    {
    function letter(num) {
    if(typeof num === 'number') {
    if(num < 26) {
    return String.fromCharCode(97 + num)
    } else {
    return letter(num - 26)
    }
    }
    }
    let varnum = 0
    function transform(ast) {
    //console.log(ast)
    //return ast
    @@ -180,18 +172,14 @@ function substitute(ast, name, node) {
    }
    },
    Lambda(n) {
    if(bound(node, n.arg) && !free(node, n.arg)) {
    if(!free(node, n.arg)) {
    return {
    type: 'Lambda',
    arg: n.arg,
    body: substitute(n.body, name, node)
    }
    } else {
    return {
    type: 'Lambda',
    arg: n.arg,
    body: n.body
    }
    return substitute(aconvert(n, n.arg.name, '$' + varnum++), name, node)
    }
    },
    Identifier(n) {
    @@ -222,8 +210,7 @@ function tolambda(ast) {
    test
    = a:prog n:var _ b:prog
    {
    //return [...free(a)]
    return tolambda(substitute(a, n.name, b))
    return [[...free(a)], tolambda(substitute(a, n.name, b))]
    }

    prog
  4. PaulMaynard revised this gist Jul 20, 2016. 2 changed files with 48 additions and 98 deletions.
    90 changes: 0 additions & 90 deletions astparser.js
    Original file line number Diff line number Diff line change
    @@ -1,90 +0,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 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)
    }
    56 changes: 48 additions & 8 deletions lispy.pegjs
    Original file line number Diff line number Diff line change
    @@ -1,4 +1,13 @@
    {
    function letter(num) {
    if(typeof num === 'number') {
    if(num < 26) {
    return String.fromCharCode(97 + num)
    } else {
    return letter(num - 26)
    }
    }
    }
    function transform(ast) {
    //console.log(ast)
    //return ast
    @@ -77,7 +86,37 @@ function transform(ast) {
    }
    function aequiv(ast) {
    }
    function arename(ast, n1, n2) {
    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) {
    }
    @@ -86,7 +125,7 @@ function breduce(ast) {
    let f = breduce(ast.func)
    let a = breduce(ast.arg)
    if(f.type === 'Lambda') {
    return substitute(breduce(f.body), f.arg.name, a)
    return breduce(substitute(breduce(f.body), f.arg.name, a))
    } else {
    return ast
    }
    @@ -141,7 +180,7 @@ function substitute(ast, name, node) {
    }
    },
    Lambda(n) {
    if(bound(node, n.arg)) {
    if(bound(node, n.arg) && !free(node, n.arg)) {
    return {
    type: 'Lambda',
    arg: n.arg,
    @@ -181,25 +220,26 @@ function tolambda(ast) {
    }

    test
    = a:prog n:var b:prog
    = a:prog n:var _ b:prog
    {
    //return [...free(a)]
    return 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 [...bound(ast)]
    return tolambda(breduce(ast))
    return {
    code: tolambda(ast),
    reduced: reduce(ast)
    //code: tolambda(ast),
    reduced: tolambda(breduce(ast)),
    free: [...free(ast)]
    }
    }

  5. PaulMaynard revised this gist Jul 20, 2016. 2 changed files with 111 additions and 9 deletions.
    Empty file removed lambda2.pegjs
    Empty file.
    120 changes: 111 additions & 9 deletions lispy.pegjs
    Original file line number Diff line number Diff line change
    @@ -1,6 +1,6 @@
    {
    function transform(ast) {
    console.log(ast)
    //console.log(ast)
    //return ast
    return {
    Program(node) {
    @@ -43,7 +43,7 @@ function transform(ast) {
    return {
    type: 'Call',
    func: transform({
    type: "Call",
    type: 'Call',
    func: node.func,
    args: node.args.slice(0, -1)
    }),
    @@ -75,14 +75,103 @@ function transform(ast) {
    }
    }[ast.type](ast)
    }
    function aequiv(ast) {
    }
    function arename(ast, n1, n2) {
    }
    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 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(bound(node, n.arg)) {
    return {
    type: 'Lambda',
    arg: n.arg,
    body: substitute(n.body, name, node)
    }
    } else {
    return {
    type: 'Lambda',
    arg: n.arg,
    body: n.body
    }
    }
    },
    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)})`
    return '(' + tolambda(node.func) + ' ' + tolambda(node.arg) + ')'
    },
    Lambda(node) {
    return `(λ (${tolambda(node.arg)}) ${tolambda(node.body)})`
    return '(λ (' + tolambda(node.arg) + ') ' + tolambda(node.body) + ')'
    },
    Identifier(node) {
    return node.name
    @@ -91,14 +180,27 @@ function tolambda(ast) {
    }
    }

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

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

    def
    @@ -115,10 +217,10 @@ exp
    = var
    / call
    / func
    / lparen _ e:exp _ rparen { return e }
    // lparen _ e:exp _ rparen { return e }

    var "identifier"
    = n:(!lambda !':=' $[^\(\)λ\\\.\r\n\t ])+
    = n:(!lambda !':=' $[^\(\)λ\\\.\r\n\t ;])+
    {
    return {
    type: 'Identifier',
    @@ -156,4 +258,4 @@ sp "space"
    lambda "lambda"
    = ("λ" / "\\" / "lambda ") { return "λ" }

    _ "whitespace" = sp?
    _ "whitespace" = sp? / ';' [^\r\n]* '\n'
  6. PaulMaynard revised this gist Jul 19, 2016. 2 changed files with 2 additions and 1 deletion.
    Empty file added lambda2.pegjs
    Empty file.
    3 changes: 2 additions & 1 deletion lispy.pegjs
    Original file line number Diff line number Diff line change
    @@ -102,7 +102,7 @@ prog
    }

    def
    = n:var _ ':=' _ v:exp
    = n:var _ assign _ v:exp
    {
    return {
    type: 'Definition',
    @@ -150,6 +150,7 @@ func
    lparen = "("
    rparen = ")"
    dot = "."
    assign = ":="
    sp "space"
    = [\r\n\t ]+
    lambda "lambda"
  7. PaulMaynard revised this gist Jul 19, 2016. 2 changed files with 143 additions and 206 deletions.
    158 changes: 0 additions & 158 deletions lambda2.pegjs
    Original file line number Diff line number Diff line change
    @@ -1,158 +0,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 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?
    191 changes: 143 additions & 48 deletions lispy.pegjs
    Original file line number Diff line number Diff line change
    @@ -1,63 +1,158 @@
    {
    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 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 lambda(args, body) {
    if(args.length === 1) {
    return ['lambda', args[0], body]
    } else {
    return [
    'lambda',
    args[0],
    lambda(args.slice(1), body),
    ]
    }
    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)
    }
    }

    Program
    = _ exprs:(Expression _)* {
    return exprs.map(e => e[0])
    prog
    = _ d:(def _)* body:(exp _) _
    {
    return tolambda(transform({
    type: 'Program',
    defs: d.map(d => d[0]),
    body: body[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)
    def
    = n:var _ ':=' _ v:exp
    {
    return {
    type: 'Definition',
    name: n,
    value: v
    }
    }

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

    Definition
    = lparen _ def sp name:ident sp val:Expression _ rparen {
    return ['def', name, val]
    var "identifier"
    = n:(!lambda !':=' $[^\(\)λ\\\.\r\n\t ])+
    {
    return {
    type: 'Identifier',
    name: n.map(c => c[2]).join('')
    }
    }

    Call
    = lparen _ func:Expression args:(sp Expression)+ _ rparen {
    return call(func, args.map(a => a[1]))
    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
    }
    }

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

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

    sp = [ \r\n\t]+
    _ = sp?
    _ "whitespace" = sp?
  8. PaulMaynard revised this gist Jul 19, 2016. 1 changed file with 90 additions and 0 deletions.
    90 changes: 90 additions & 0 deletions astparser.js
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,90 @@
    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)
    }
  9. PaulMaynard revised this gist Jul 19, 2016. No changes.
  10. PaulMaynard revised this gist Jul 19, 2016. 1 changed file with 158 additions and 0 deletions.
    158 changes: 158 additions & 0 deletions lambda2.pegjs
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,158 @@
    {
    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?
  11. PaulMaynard revised this gist Feb 22, 2016. 1 changed file with 63 additions and 0 deletions.
    63 changes: 63 additions & 0 deletions lispy.pegjs
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,63 @@
    {
    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?
  12. PaulMaynard revised this gist Dec 2, 2015. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion lambda.pegjs
    Original file line number Diff line number Diff line change
    @@ -143,6 +143,6 @@ dot = "."
    space "space"
    = [\r\n\t ]+
    lambda "lambda"
    = ("λ" / "\\") { return "λ" }
    = ("λ" / "\\" / "lambda ") { return "λ" }

    _ "whitespace" = space?
  13. PaulMaynard revised this gist Nov 18, 2015. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion lambda.pegjs
    Original file line number Diff line number Diff line change
    @@ -145,4 +145,4 @@ space "space"
    lambda "lambda"
    = ("λ" / "\\") { return "λ" }

    _ "whitespace" = space?
    _ "whitespace" = space?
  14. PaulMaynard revised this gist Nov 18, 2015. 1 changed file with 37 additions and 6 deletions.
    43 changes: 37 additions & 6 deletions lambda.pegjs
    Original file line number Diff line number Diff line change
    @@ -9,15 +9,38 @@ function compilejs(exp) {
    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")
    + "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 code + "\n====>\nRaw:\n" + (function() {
    return "Raw:\n" + (function() {
    try {
    var f = eval(code)
    console.log(f)
    @@ -69,7 +92,15 @@ function call(f, a) {
    }

    prog
    = _ e:(barecall / exp) _ { return print(compilejs(e)) }
    = _ 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
    @@ -114,4 +145,4 @@ space "space"
    lambda "lambda"
    = ("λ" / "\\") { return "λ" }

    _ "whitespace" = space?
    _ "whitespace" = space?
  15. PaulMaynard revised this gist Nov 17, 2015. 1 changed file with 8 additions and 6 deletions.
    14 changes: 8 additions & 6 deletions lambda.pegjs
    Original file line number Diff line number Diff line change
    @@ -54,9 +54,9 @@ function churchbool (v) {
    //Sugar
    function lambda(a, r) {
    if(a.length == 1) {a
    return ["lambda", a[0], r]
    return ["λ", a[0], r]
    } else {
    return ["lambda", a[0], lambda(a.slice(1), r)]
    return ["λ", a[0], lambda(a.slice(1), r)]
    }
    }
    function call(f, a) {
    @@ -77,7 +77,7 @@ exp
    / func
    / lparen _ e:exp _ rparen { return e }

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

    @@ -109,7 +109,9 @@ func
    lparen = "("
    rparen = ")"
    dot = "."
    space = [\r\n\t ]+
    lambda = ("λ" / "\\") { return "λ" }
    space "space"
    = [\r\n\t ]+
    lambda "lambda"
    = ("λ" / "\\") { return "λ" }

    _ = space?
    _ "whitespace" = space?
  16. PaulMaynard revised this gist Nov 17, 2015. 1 changed file with 13 additions and 8 deletions.
    21 changes: 13 additions & 8 deletions lambda.pegjs
    Original file line number Diff line number Diff line change
    @@ -69,42 +69,47 @@ function call(f, a) {
    }

    prog
    = e:(barecall / exp) { return print(compilejs(e)) }
    = _ e:(barecall / exp) _ { return print(compilejs(e)) }

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

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

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

    barecall
    = f:exp a:(space? exp)+
    = 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, r) }
    = 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 = ("λ" / "\\") { return "λ" }

    _ = [\r\n\t ]*
    _ = space?
  17. PaulMaynard revised this gist Nov 17, 2015. No changes.
  18. PaulMaynard revised this gist Nov 17, 2015. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion lambda.pegjs
    Original file line number Diff line number Diff line change
    @@ -78,7 +78,7 @@ exp
    / lparen e:exp rparen { return e }

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

    call
  19. PaulMaynard revised this gist Nov 17, 2015. 3 changed files with 16 additions and 16 deletions.
    2 changes: 1 addition & 1 deletion 2+2.lambda
    Original file line number Diff line number Diff line change
    @@ -1 +1 @@
    (λ+2.+22)(λmnfx.mf(nfx))((λs0.s(s0))(λnfx.f(nfx))(λfx.x))
    (λ+2.+22)(λmnfx.mf(nfx))((λs0.s(s0))(λnfx.f(nfx))(λfx.x))
    2 changes: 1 addition & 1 deletion boolean.lambda
    Original file line number Diff line number Diff line change
    @@ -1 +1 @@
    (λtf!&|.!(&f(|tf)))(λtf.t)(λtf.f)(λp.λtf.pft)(λpq.pqp)(λpq.ppq)
    (λtf!&|.!(&f(|tf)))(λtf.t)(λtf.f)(λp.λtf.pft)(λpq.pqp)(λpq.ppq)
    28 changes: 14 additions & 14 deletions lambda.pegjs
    Original file line number Diff line number Diff line change
    @@ -9,29 +9,29 @@ function compilejs(exp) {
    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')
    + "return " + compilejs(exp[2]).trim().split("\n").map(function(l) {
    return " " + l
    }).join("\n")
    + "\n})"
    }
    }
    // Output
    function print(code) {
    return code + '\n====>\nRaw:\n' + (function() {
    return code + "\n====>\nRaw:\n" + (function() {
    try {
    var f = eval(code)
    console.log(f)
    var n = dechurch(f)
    var n = churchnum(f)
    var b = churchbool(f)
    return f
    + '\nChurch number: ' + n
    + "\nChurch number: " + n
    + "\nChurch boolean: " + b
    } catch(e) {
    return 'Error: ' + e
    return "Error: " + e
    }
    })()
    }
    function dechurch(v) {
    function churchnum(v) {
    try {
    var n = v(function(x) { return x + 1 })(0)
    if(typeof n == "number") {
    @@ -54,9 +54,9 @@ function churchbool (v) {
    //Sugar
    function lambda(a, r) {
    if(a.length == 1) {a
    return ['lambda', a[0], r]
    return ["lambda", a[0], r]
    } else {
    return ['lambda', a[0], lambda(a.slice(1), r)]
    return ["lambda", a[0], lambda(a.slice(1), r)]
    }
    }
    function call(f, a) {
    @@ -78,7 +78,7 @@ exp
    / lparen e:exp rparen { return e }

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

    call
    @@ -103,8 +103,8 @@ func

    lparen = "("
    rparen = ")"
    dot = '.'
    space = ' '
    dot = "."
    space = " "
    lambda = ("λ" / "\\") { return "λ" }

    _ = [\r\n\t ]*
    _ = [\r\n\t ]*
  20. PaulMaynard revised this gist Nov 16, 2015. 2 changed files with 27 additions and 6 deletions.
    1 change: 1 addition & 0 deletions boolean.lambda
    Original file line number Diff line number Diff line change
    @@ -0,0 +1 @@
    (λtf!&|.!(&f(|tf)))(λtf.t)(λtf.f)(λp.λtf.pft)(λpq.pqp)(λpq.ppq)
    32 changes: 26 additions & 6 deletions lambda.pegjs
    Original file line number Diff line number Diff line change
    @@ -1,8 +1,9 @@
    {
    // Compilation
    function compilejs(exp) {
    if(exp.length == 1) {
    return exp[0].replace(/[^a-zA-Z_$]/g, function(c) {
    return "_$" + c.charCodeAt(0).toString(16) + "$_"
    return "_$" + c.charCodeAt(0).toString(16) + "$_ /* " + c + " */"
    })
    } else if(exp.length == 2) {
    return compilejs(exp[0]) + "(" + compilejs(exp[1]) + ")"
    @@ -14,24 +15,43 @@ function compilejs(exp) {
    + "\n})"
    }
    }
    // ----
    // Output
    function print(code) {
    return code + '\n====>\nRaw:\n' + (function() {
    try {
    var f = eval(code)
    console.log(f)
    var n = dechurch(f)
    var b = churchbool(f)
    return f
    + (typeof n == 'number' ? '\nChurch number:\n' + n : '')
    + '\nChurch number: ' + n
    + "\nChurch boolean: " + b
    } catch(e) {
    return 'Error: ' + e
    }
    })()
    }
    function dechurch(n) {
    return n(function(x) { return x + 1 })(0)
    function dechurch(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 ['lambda', a[0], r]
  21. PaulMaynard revised this gist Nov 12, 2015. 1 changed file with 1 addition and 0 deletions.
    1 change: 1 addition & 0 deletions 2+2.lambda
    Original file line number Diff line number Diff line change
    @@ -0,0 +1 @@
    (λ+2.+22)(λmnfx.mf(nfx))((λs0.s(s0))(λnfx.f(nfx))(λfx.x))
  22. PaulMaynard revised this gist Nov 12, 2015. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion lambda.pegjs
    Original file line number Diff line number Diff line change
    @@ -85,6 +85,6 @@ lparen = "("
    rparen = ")"
    dot = '.'
    space = ' '
    lambda = ("lambda" / "λ" / "\\") { return "lambda" }
    lambda = ("λ" / "\\") { return "λ" }

    _ = [\r\n\t ]*
  23. PaulMaynard revised this gist Nov 12, 2015. 1 changed file with 22 additions and 7 deletions.
    29 changes: 22 additions & 7 deletions lambda.pegjs
    Original file line number Diff line number Diff line change
    @@ -14,18 +14,26 @@ function compilejs(exp) {
    + "\n})"
    }
    }
    // ----
    function print(code) {
    return code + '\n====>\n' + (function() {
    return code + '\n====>\nRaw:\n' + (function() {
    try {
    return eval(code)
    var f = eval(code)
    console.log(f)
    var n = dechurch(f)
    return f
    + (typeof n == 'number' ? '\nChurch number:\n' + n : '')
    } catch(e) {
    return 'Error: ' + e
    }
    })()
    }
    function dechurch(n) {
    return n(function(x) { return x + 1 })(0)
    }
    // ----
    function lambda(a, r) {
    if(a.length == 1) {
    if(a.length == 1) {a
    return ['lambda', a[0], r]
    } else {
    return ['lambda', a[0], lambda(a.slice(1), r)]
    @@ -41,8 +49,7 @@ function call(f, a) {
    }

    prog
    = f:exp space? a:exp { return print(compilejs([f, a])) }
    / e:exp { return print(compilejs(e)) }
    = e:(barecall / exp) { return print(compilejs(e)) }

    exp
    = var
    @@ -51,7 +58,7 @@ exp
    / lparen e:exp rparen { return e }

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

    call
    @@ -62,8 +69,16 @@ call
    }))
    }

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

    func
    = lambda a:var+ dot r:exp { return lambda(a, r) }
    = lambda a:var+ dot r:(barecall / exp) { return lambda(a, r) }


    lparen = "("
  24. PaulMaynard revised this gist Nov 12, 2015. 1 changed file with 15 additions and 7 deletions.
    22 changes: 15 additions & 7 deletions lambda.pegjs
    Original file line number Diff line number Diff line change
    @@ -31,6 +31,13 @@ function lambda(a, r) {
    return ['lambda', 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
    @@ -44,19 +51,20 @@ exp
    / lparen e:exp rparen { return e }

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

    call
    = lparen f:exp space? a:exp rparen { return [f, a] }

    func
    = lambda a:var+ dot r:exp
    = lparen f:exp a:(space? exp)+ rparen
    {
    //alert(JSON.stringify(a))
    return lambda(a, r)
    return call(f, a.map(function(e) {
    return e[1]
    }))
    }

    func
    = lambda a:var+ dot r:exp { return lambda(a, r) }


    lparen = "("
    rparen = ")"
  25. PaulMaynard revised this gist Nov 11, 2015. 1 changed file with 17 additions and 11 deletions.
    28 changes: 17 additions & 11 deletions lambda.pegjs
    Original file line number Diff line number Diff line change
    @@ -1,19 +1,29 @@
    {
    function compile(exp) {
    function compilejs(exp) {
    if(exp.length == 1) {
    return exp[0].replace(/[^a-zA-Z_$]/g, function(c) {
    return "_$" + c.charCodeAt(0).toString(16) + "$_"
    })
    } else if(exp.length == 2) {
    return compile(exp[0]) + "(" + compile(exp[1]) + ")"
    return compilejs(exp[0]) + "(" + compilejs(exp[1]) + ")"
    } else if(exp.length == 3) {
    return "(" + "function(" + compile(exp[1]) + "){\n "
    + "return " + compile(exp[2]).trim().split('\n').map(function(l) {
    return "(" + "function(" + compilejs(exp[1]) + ") {\n "
    + "return " + compilejs(exp[2]).trim().split('\n').map(function(l) {
    return ' ' + l
    }).join('\n')
    + "\n})"
    }
    }
    function print(code) {
    return code + '\n====>\n' + (function() {
    try {
    return eval(code)
    } catch(e) {
    return 'Error: ' + e
    }
    })()
    }
    // ----
    function lambda(a, r) {
    if(a.length == 1) {
    return ['lambda', a[0], r]
    @@ -24,12 +34,8 @@ function lambda(a, r) {
    }

    prog
    = f:exp a:exp { return compile([f, a]) }
    / e:exp
    {
    var r = compile(e)
    return r
    }
    = f:exp space? a:exp { return print(compilejs([f, a])) }
    / e:exp { return print(compilejs(e)) }

    exp
    = var
    @@ -42,7 +48,7 @@ var
    { return [n[1]] }

    call
    = lparen f:exp space a:exp rparen { return [f, a] }
    = lparen f:exp space? a:exp rparen { return [f, a] }

    func
    = lambda a:var+ dot r:exp
  26. PaulMaynard created this gist Nov 11, 2015.
    61 changes: 61 additions & 0 deletions lambda.pegjs
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,61 @@
    {
    function compile(exp) {
    if(exp.length == 1) {
    return exp[0].replace(/[^a-zA-Z_$]/g, function(c) {
    return "_$" + c.charCodeAt(0).toString(16) + "$_"
    })
    } else if(exp.length == 2) {
    return compile(exp[0]) + "(" + compile(exp[1]) + ")"
    } else if(exp.length == 3) {
    return "(" + "function(" + compile(exp[1]) + "){\n "
    + "return " + compile(exp[2]).trim().split('\n').map(function(l) {
    return ' ' + l
    }).join('\n')
    + "\n})"
    }
    }
    function lambda(a, r) {
    if(a.length == 1) {
    return ['lambda', a[0], r]
    } else {
    return ['lambda', a[0], lambda(a.slice(1), r)]
    }
    }
    }

    prog
    = f:exp a:exp { return compile([f, a]) }
    / e:exp
    {
    var r = compile(e)
    return r
    }

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

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

    call
    = lparen f:exp space a:exp rparen { return [f, a] }

    func
    = lambda a:var+ dot r:exp
    {
    //alert(JSON.stringify(a))
    return lambda(a, r)
    }


    lparen = "("
    rparen = ")"
    dot = '.'
    space = ' '
    lambda = ("lambda" / "λ" / "\\") { return "lambda" }

    _ = [\r\n\t ]*