{"_id":"@calculemus/abt","_rev":"6-65f4de6b4ed45eaf016b092c05cc8014","name":"@calculemus/abt","dist-tags":{"latest":"0.1.3"},"versions":{"0.0.1":{"name":"@calculemus/abt","version":"0.0.1","description":"Abstract Binding Trees","main":"lib/index.js","scripts":{"watch":"tsc -w","prettier":"prettier --write src/**/*.ts *.json","prepare":"tsc"},"author":{"name":"Calculemus LLC"},"license":"ISC","dependencies":{"immutable":"^3.8.2"},"devDependencies":{"prettier":"^1.11.1","typescript":"^2.7.2"},"repository":{"type":"git","url":"git+https://github.com/calculemuscode/abt-js.git"},"prettier":{"printWidth":110,"tabWidth":2},"bugs":{"url":"https://github.com/calculemuscode/abt-js/issues"},"homepage":"https://github.com/calculemuscode/abt-js#readme","_id":"@calculemus/abt@0.0.1","_npmVersion":"5.0.3","_nodeVersion":"8.1.4","_npmUser":{"name":"calculemus","email":"rob@calculem.us"},"dist":{"integrity":"sha512-IX2asKNNXc/Db6zEffQBPy5cMn3VrXYck14JxB1l9cAxM6j0GV0ju4tRizg5In31Tw8lZp9BPU0p4N302fChqQ==","shasum":"55ef36d683ecd798d908f41a170feeb3ec764941","tarball":"https://registry.npmjs.org/@calculemus/abt/-/abt-0.0.1.tgz","fileCount":4,"unpackedSize":14245,"signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEQCIBynRaSM+2rj5v52ZW6Vc4N8dEYRJYmV2dpC4t0Fym1qAiAONoF3ewsW8KbMNd964uSMCrb6H/4aSfJ/pFB+7t4Q2g=="}]},"maintainers":[{"name":"calculemus","email":"rob@calculem.us"}],"directories":{},"_npmOperationalInternal":{"host":"s3://npm-registry-packages","tmp":"tmp/abt_0.0.1_1521411886901_0.12634437146441058"},"_hasShrinkwrap":false},"0.1.0":{"name":"@calculemus/abt","version":"0.1.0","description":"Abstract Binding Trees","main":"lib/index.js","scripts":{"watch":"tsc -w","prettier":"prettier --write src/*.ts src/**/*.ts *.json","prepublishOnly":"tsc","test":"nyc mocha -r ts-node/register src/**/test/*.ts","coveralls":"nyc report --reporter=text-lcov | coveralls"},"author":{"name":"Calculemus LLC"},"license":"ISC","dependencies":{"immutable":"^3.8.2"},"devDependencies":{"@types/chai":"^4.1.2","@types/mocha":"^2.2.48","chai":"^4.1.2","chai-immutable":"^1.6.0","coveralls":"^3.0.0","mocha":"^5.0.4","mocha-lcov-reporter":"^1.3.0","nyc":"^11.6.0","prettier":"^1.11.1","ts-node":"^5.0.1","typescript":"^2.7.2"},"nyc":{"include":["src/**/*.ts"],"exclude":["src/**/test/*.ts"],"extension":[".ts"],"require":["ts-node/register"],"sourcemap":true,"instrument":true},"repository":{"type":"git","url":"git+https://github.com/calculemuscode/abt-js.git"},"prettier":{"printWidth":110,"tabWidth":4},"gitHead":"b9e055c412e98ea1da9e0b53eb140e4e40431f4e","bugs":{"url":"https://github.com/calculemuscode/abt-js/issues"},"homepage":"https://github.com/calculemuscode/abt-js#readme","_id":"@calculemus/abt@0.1.0","_npmVersion":"5.0.3","_nodeVersion":"8.1.4","_npmUser":{"name":"calculemus","email":"rob@calculem.us"},"dist":{"integrity":"sha512-XdFx6igaIP+Pp3CFia2HMcbXRNlgGJzGWWCIEveI8i/1hzsJSEbR2zsDfOxkEp2ddCR6dN1C7Z3QDDmOX6PPRA==","shasum":"7d2798e0b261257abeb982254552d290e6403145","tarball":"https://registry.npmjs.org/@calculemus/abt/-/abt-0.1.0.tgz","fileCount":13,"unpackedSize":74568,"signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEQCIFfJqXo/VR+96L344uVgXmYom7gzmNMoXCFlFIZSgdoJAiA845yOJx8i8NS/HKe6lKcgajWXZc0+rthDPCavUhpY/Q=="}]},"maintainers":[{"name":"calculemus","email":"rob@calculem.us"}],"directories":{},"_npmOperationalInternal":{"host":"s3://npm-registry-packages","tmp":"tmp/abt_0.1.0_1521594816997_0.19406866802888012"},"_hasShrinkwrap":false},"0.1.1":{"name":"@calculemus/abt","version":"0.1.1","description":"Abstract Binding Trees","main":"lib/index.js","scripts":{"watch":"tsc -w","prettier":"prettier --write src/*.ts src/**/*.ts *.json","prepublishOnly":"tsc","test":"nyc mocha -r ts-node/register src/**/test/*.ts","coveralls":"nyc report --reporter=text-lcov | coveralls"},"author":{"name":"Calculemus LLC"},"license":"ISC","dependencies":{"immutable":"^3.8.2"},"devDependencies":{"@types/chai":"^4.1.2","@types/mocha":"^2.2.48","chai":"^4.1.2","chai-immutable":"^1.6.0","coveralls":"^3.0.0","mocha":"^5.0.4","mocha-lcov-reporter":"^1.3.0","nyc":"^11.6.0","prettier":"^1.11.1","ts-node":"^5.0.1","typescript":"^2.7.2"},"nyc":{"include":["src/**/*.ts"],"exclude":["src/**/test/*.ts"],"extension":[".ts"],"require":["ts-node/register"],"sourcemap":true,"instrument":true},"repository":{"type":"git","url":"git+https://github.com/calculemuscode/abt-js.git"},"prettier":{"printWidth":110,"tabWidth":4},"gitHead":"43113d181bcc58227910688528adcc22d313271f","bugs":{"url":"https://github.com/calculemuscode/abt-js/issues"},"homepage":"https://github.com/calculemuscode/abt-js#readme","_id":"@calculemus/abt@0.1.1","_npmVersion":"5.0.3","_nodeVersion":"8.1.4","_npmUser":{"name":"calculemus","email":"rob@calculem.us"},"dist":{"integrity":"sha512-aKbo1GIINjHeeNXtQ//CIzgMGEP2upynTTCHOo3OcU0Ji4JskNUGugnzGB8VqX8T0DNXB64L4UL+QB2G1yk12w==","shasum":"30f2bf339f4223c22ca54a3b21f1d734787ff449","tarball":"https://registry.npmjs.org/@calculemus/abt/-/abt-0.1.1.tgz","fileCount":13,"unpackedSize":76843,"signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEYCIQDCcI4Dg6vNDI+PkibXts7+FO7DNGHsObIxBc3ex/8uIAIhAJ8SpqmLjGv1v+BdmEE2WTs6RuZqPVkHkANvOpC+QOBW"}]},"maintainers":[{"name":"calculemus","email":"rob@calculem.us"}],"directories":{},"_npmOperationalInternal":{"host":"s3://npm-registry-packages","tmp":"tmp/abt_0.1.1_1521639839762_0.1886066314371624"},"_hasShrinkwrap":false},"0.1.2":{"name":"@calculemus/abt","version":"0.1.2","description":"Abstract Binding Trees","main":"lib/index.js","scripts":{"watch":"tsc -w","prettier":"prettier --write src/*.ts src/**/*.ts *.json","prepublishOnly":"rm -f *~ && tsc","test":"nyc mocha -r ts-node/register src/**/test/*.ts","coveralls":"nyc report --reporter=text-lcov | coveralls"},"author":{"name":"Calculemus LLC"},"license":"ISC","dependencies":{"immutable":"^3.8.2"},"devDependencies":{"@types/chai":"^4.1.2","@types/mocha":"^2.2.48","chai":"^4.1.2","chai-immutable":"^1.6.0","coveralls":"^3.0.0","mocha":"^5.0.4","mocha-lcov-reporter":"^1.3.0","nyc":"^11.6.0","prettier":"^1.11.1","ts-node":"^5.0.1","typescript":"^2.7.2"},"nyc":{"include":["src/**/*.ts"],"exclude":["src/**/test/*.ts"],"extension":[".ts"],"require":["ts-node/register"],"sourcemap":true,"instrument":true},"repository":{"type":"git","url":"git+https://github.com/calculemuscode/abt-js.git"},"prettier":{"printWidth":110,"tabWidth":4},"gitHead":"43113d181bcc58227910688528adcc22d313271f","bugs":{"url":"https://github.com/calculemuscode/abt-js/issues"},"homepage":"https://github.com/calculemuscode/abt-js#readme","_id":"@calculemus/abt@0.1.2","_npmVersion":"5.0.3","_nodeVersion":"8.1.4","_npmUser":{"name":"calculemus","email":"rob@calculem.us"},"dist":{"integrity":"sha512-ePBfukRe7nKCiZ6BrtY6fRFYR30ykxs/Vs014wLcDYGzA83Io4prpy53dMpB4t7LChvekJlVEBaE2jkgfKg7AQ==","shasum":"f66783e31a5e2e4073574849610631fa91af78df","tarball":"https://registry.npmjs.org/@calculemus/abt/-/abt-0.1.2.tgz","fileCount":19,"unpackedSize":78047,"signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEYCIQCJ3b+xNpm+44TGI3YZBM4v4XecITtFJeUv8LHVk9vf2AIhAPT63C26QVgtrhrI+A5871kO2uGvsIRXztQmLvImy4On"}]},"maintainers":[{"name":"calculemus","email":"rob@calculem.us"}],"directories":{},"_npmOperationalInternal":{"host":"s3://npm-registry-packages","tmp":"tmp/abt_0.1.2_1521640327001_0.6014773682125203"},"_hasShrinkwrap":false},"0.1.3":{"name":"@calculemus/abt","version":"0.1.3","description":"Abstract Binding Trees","main":"lib/index.js","scripts":{"watch":"tsc -w","prettier":"prettier --write src/*.ts src/**/*.ts *.json","prepublishOnly":"rm -f *~ && tsc","test":"nyc mocha -r ts-node/register src/**/test/*.ts","coveralls":"nyc report --reporter=text-lcov | coveralls"},"author":{"name":"Calculemus LLC"},"license":"ISC","dependencies":{"immutable":"^3.8.2"},"devDependencies":{"@types/chai":"^4.1.2","@types/mocha":"^2.2.48","chai":"^4.1.2","chai-immutable":"^1.6.0","coveralls":"^3.0.0","mocha":"^5.0.4","mocha-lcov-reporter":"^1.3.0","nyc":"^11.6.0","prettier":"^1.11.1","ts-node":"^5.0.1","typescript":"^2.7.2"},"nyc":{"include":["src/**/*.ts"],"exclude":["src/**/test/*.ts"],"extension":[".ts"],"require":["ts-node/register"],"sourcemap":true,"instrument":true},"types":"lib/index.d.ts","repository":{"type":"git","url":"git+https://github.com/calculemuscode/abt-js.git"},"prettier":{"printWidth":110,"tabWidth":4},"gitHead":"b9df47d59fdac7afa9939f3f58a4be76e44595bd","bugs":{"url":"https://github.com/calculemuscode/abt-js/issues"},"homepage":"https://github.com/calculemuscode/abt-js#readme","_id":"@calculemus/abt@0.1.3","_npmVersion":"5.0.3","_nodeVersion":"8.1.4","_npmUser":{"name":"calculemus","email":"rob@calculem.us"},"dist":{"integrity":"sha512-k4j1GH1jmaty6/lgHVrzBl/ioZGKmzrVXFzhwFt5oG6fP0wy6QyrpB1PXNBWy4R5PXgV7jt1UziRhrAT34o7vw==","shasum":"ae65dae4ebcf51e91487fbe489ae129bacbf2abc","tarball":"https://registry.npmjs.org/@calculemus/abt/-/abt-0.1.3.tgz","fileCount":19,"unpackedSize":78078,"signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEUCIEy4Qg+J1Yb2wgRPN2JijJeT7xoAuqetSR1G/024sMQRAiEAsqh608KnJTZhwA9tpI5x2eZMwhO80KaPDZV55e4FkCA="}]},"maintainers":[{"name":"calculemus","email":"rob@calculem.us"}],"directories":{},"_npmOperationalInternal":{"host":"s3://npm-registry-packages","tmp":"tmp/abt_0.1.3_1521678977173_0.8770056822806578"},"_hasShrinkwrap":false}},"time":{"created":"2018-03-18T22:24:46.826Z","0.0.1":"2018-03-18T22:24:46.975Z","modified":"2022-04-04T21:31:44.186Z","0.1.0":"2018-03-21T01:13:37.081Z","0.1.1":"2018-03-21T13:43:59.872Z","0.1.2":"2018-03-21T13:52:07.065Z","0.1.3":"2018-03-22T00:36:17.290Z"},"maintainers":[{"name":"calculemus","email":"rob@calculem.us"}],"description":"Abstract Binding Trees","homepage":"https://github.com/calculemuscode/abt-js#readme","repository":{"type":"git","url":"git+https://github.com/calculemuscode/abt-js.git"},"author":{"name":"Calculemus LLC"},"bugs":{"url":"https://github.com/calculemuscode/abt-js/issues"},"license":"ISC","readme":"A Typescript library for Abstract Binding Trees\n===============================================\n\n[![npm version](https://badge.fury.io/js/%40calculemus%2Fabt.svg)](https://badge.fury.io/js/%40calculemus%2Fabt)\n[![Build Status](https://travis-ci.org/calculemuscode/abt-js.svg?branch=master)](https://travis-ci.org/calculemuscode/abt-js)\n[![Dependency Status](https://david-dm.org/calculemuscode/abt-js.svg)](https://david-dm.org/calculemuscode/abt-js)\n[![Dev Dependency Status](https://david-dm.org/calculemuscode/abt-js/dev-status.svg)](https://david-dm.org/calculemuscode/abt-js?type=dev)\n[![Coverage Status](https://coveralls.io/repos/github/calculemuscode/abt-js/badge.svg?branch=master)](https://coveralls.io/github/calculemuscode/abt-js?branch=master)\n\nThis ABT library is based on Prof. Robert Harpers's book, Practical Foundations of Programming Languages, and\non course infrastructure used at Carnegie Mellon's Foundations of Programming Languages course. Compared to\nthe ABT library that was historically used in CMU's course, this ABT library:\n\n * Results in nicer looking output. The CMU course takes an approach to ABTs that has a failure mode: after\n   you do some computation, the perfectly reasonable return-the-identity-function function that you wrote as\n   `fn x => fn x => x` gets pretty-printed as the jibberish `fn x1251 => fn x1245 => x1245`. This ABT library\n   (in default configuration) will print this out as the IMO much more reasonable `fn x => fn x1 => x1`.\n\n * Harder to use without screwing up. This is a direct consequence of printing nicer looking output. Most\n   functions require an `immutable.Set<string>` of all free-or-potentially-free variables as an input, and if\n   you get this wrong the behavior of the library is undefined. (The CMU-style ABT construction assumes that\n   any variable ever exposed outside the library is free-or-potentially-free, which is why you end up with\n   overly-renumbered variables floating around.)\n\n * More complicated in its implementation. Substitution and ABT equality are implemented \"under the hood,\" and\n   when students try to implement substitution and ABT equality under the hood in Foundations of Programming\n   Langauges we tell them to not do that, and for good reasons: it's hard to get it right, even if it's a bit\n   faster.\n\nFor an introduction to what Abstract Binding Trees are, see (XXX a blogpost I have yet to write), or [Chapter\n1 in PFPL](http://www.cs.cmu.edu/~rwh/pfpl.html) for a mathematically rigorous introduction. For an\nintroduction to implementing and programming with ABTs in a functional programming langauge, see [this\npost](http://semantic-domain.blogspot.com/2015/03/abstract-binding-trees.html) and [this\nfollowup](http://semantic-domain.blogspot.com/2015/03/abstract-binding-trees-addendum.html) by Neel\nKrishnaswami. In particular, I would point anyone interested in _implementing_ abstract binding trees to\nNeel's code over my own.\n\nInterface\n=========\n\nAn Abstract Binding Tree has this Typescript type:\n\n```typescript\ntype ABT = string | { tag: string, ... }`\n```\n\nTo respect this library's interface, _do not access any fields of a non-string ABT_ aside from `tag`.\n\n``` typescript\nimport { ABT, abt } from \"@calculemus/abt\";\n\nfunction abtBoolToBool(syn: ABT): boolean {\n    if (typeof syn === \"string\") throw new Error(`Expected true() or false(), got variable ${x}`);\n    switch(x.tag) {\n    case \"true\": return true;\n    case \"false\": return false;\n    default: throw new Error(`Expected true() or false(), got unexpected operator ${x.tag}`);\n    }\n}\n```\n\nABTs are built and inspected by the methods of an `AbstractBindingTree` class; the default instantiation of\nthis class is provided in the library and called `abt`, which you can see imported in the example\nabove.\n\nObjects of type `ABT` don't have any methods, they're only data objects.\n\nCreating Abstract Binding Trees\n-------------------------------\n\nThe introduction form for Abstract Binding Trees is the `oper` method.\n\n``` typescript\nabt.oper(tag: string, ...args: (ABT | [string[], ABT])[]): ABT\n```\n\nLet's unpack that a little bit. The first argument is the operator, or tag, and the remainder of the arguments\n_can_ just be abstract binding trees:\n\n``` typescript\nimport { ABT, abt } from \"@calculemus/abt\";\n\nconst twp: ABT = abt.oper(\"succ\", abt.oper(\"succ\", abt.oper(\"zero\")));\nconst bintree: ABT = abt.oper(\"node\", abt.oper(\"leaf\"), abt.oper(\"leaf\"));\n```\n\nThis style doesn't give us any way to bind variables, though. It's a shorthand for the full syntax, where\nevery sub-ABT is a tuple `[xs, subsyn]`, where `xs` is the (possibly empty) list of bound variables and\n`subsyn` is the ABT sub-expression.\n\n``` typescript\n// ABT syntax lam(x.x)\n// PL syntax: x => x\nconst id: ABT = abt.oper(\"lam\", [[\"x\"], \"x\"]);\n\n// ABT syntax: letrec(f.x.ap(f,x),ap(f,y))\n// PL syntax: letrec f(x) = f(x) in f(y)\nconst loop: ABT = abt.oper(\n    \"letrec\",\n    [[\"f\", \"x\"], abt.oper(\"ap\", \"f\", \"x\")],\n    [[\"f\"], abt.oper(\"ap\", \"f\", \"y\")]);\n\n// succ(succ(zero)), same as before\nconst two: ABT = abt.oper(\"succ\", [[], abt.oper(\"succ\", [[], abt.oper(\"zero\")])]);\n```\n\nTraversing Abstract Binding Trees\n---------------------------------\n\nIn order to get the subterms of a non-variable ABT, it is necessary to call the `args` method.\n\n```typescript\nabt.args(fv: Set<string>, syn: ABT): [string[], ABT][]\n```\n\nThe structure of the returned array matches the arity, so as long as you use tags (a.k.a. operators) with\nconsistent bound variables and arguments, you can predict the output of `abt.args` and pattern match against\nit:\n\n```typescript\nfunction lambdaToString(fv: Set<string>, e: ABT): string {\n    if (typeof e === \"string\") return e;\n    switch (e.tag) {\n        case \"fn\": { // fn(x.e0)\n            const [[[x], e0]] = abt.args(fv, e);\n            return `(${x} => ${toString(fv.add(x), e0)})`;\n        }\n        case \"ap\": { // ap(e1,e2)\n            const [[[], e1], [[], e2]] = abt.args(fv, e);\n            return `(${toString(fv, e1)} ${toString(fv, e2)})`;\n        }\n        case \"let\": { // let(e1,x.e2)\n            const [[[], e1], [[x], e2]] = abt.args(fv, e);\n            return `(let ${x} = ${toString(fv, e1)} in ${toString(fv.add(x), e2)}`;\n        }\n        default: throw new Error(`Expected expression, got unexpected operator ${x.tag}`);\n    }\n}\n```\n\nThe variable identifiers output by `abt.args` will always be distinct from each other and from any identifier\nin `fv`.\n\n```javascript\n> const abt = require(\"@calculemus/abt\").abt;\n> const Set = require(\"immutable\").Set;\n> abt.args(Set([]), abt.oper(\"fn\", [[\"x\"], \"x\"]));\n[ [ [ 'x' ], 'x' ] ]\n> abt.args(Set([\"x\"]), abt.oper(\"fn\", [[\"x\"], \"x\"]));\n[ [ [ 'x1' ], 'x1' ] ]\n> abt.args(Set([\"x\", \"x1\", \"x2\"]), abt.oper(\"fn\", [[\"x\"], \"x\"]));\n[ [ [ 'x3' ], 'x3' ] ]\n```\n\nAlpha-equality\n--------------\n\nAbstract binding trees should be treated as equal if only the names of bound variables differ. The `abt.equal`\nfunction needs to be given the current free variable context, but will then compute alpha-equality.\n\n```typescript\nfunction abt.equal(fv: Set<string>, syn1: ABT, syn2: ABT): boolean\n```\n\n```javascript\n> abt.equal(Set([\"x\"]), abt.oper(\"lam\", [[\"y\"], \"y\"]), abt.oper(\"lam\", [[\"z\"], \"z\"]));\ntrue\n> abt.equal(Set([\"x\"]), abt.oper(\"lam\", [[\"y\"], \"y\"]), abt.oper(\"lam\", [[\"x\"], \"x\"]));\ntrue\n> abt.equal(Set([\"x\"]), abt.oper(\"lam\", [[\"y\"], \"y\"]), abt.oper(\"lam\", [[\"z\"], \"x\"]));\nfalse\n```\n\nSubstitution\n------------\n\nCapture-avoiding substitution is the key feature of an abstract binding tree library. You can compute\n`[syn1/x]syn2` is by using the `abt.subst` function:\n\n```\nabt.subst(fv: Set<string>, syn1: ABT, x: string, syn2: ABT): ABT\n```\n\nIn this example, `fv` must contain all the free variables in `syn1`, and `fv.add(x)` must contain all the free\nvariables in `syn2`.\n\nABT substitution avoids variable capture: the classic problem is that if you substitute `[x / y] lam(x.ap(x,y))`,\nyou want to get something alpha-equivalent to `lam(z.ap(z,x))`. Just textually replacing `y` with `x` would\ngive you `lam(x.ap(x,x))`, which is the wrong answer: the free variable `x` has been captured by the binder.\nTo avoid variable capture, the ABT library renames the bound variable _x_ to avoid capture.\n\n```javascript\n> const abt = require(\"./lib\").abt;\n> const Set = require(\"immutable\").Set;\n> const ex = abt.oper(\"lam\", [[\"x\"], abt.oper(\"ap\", \"x\", \"y\")]);\n> abt.toString(Set([\"x\"]), \"x\", \"y\", ex);\n'x'\n> abt.toString(Set([\"x\"]), abt.subst(Set([\"x\"]), \"x\", \"y\", ex));\n'lam(x1.ap(x1,x))'\n```\n\nIt's possible (though usually unnecessary) to do simultaneous substitution `[synA synB synC / x y z] syn2` as\nwell. This can be done by calling:\n\n```typescript\nabt.subst(fv, [synA, synB, synC], [\"x\", \"y\", \"z\"], syn2)\n```\n\nThe lengths of the two arrays must be equal, and `synA`, `synB`, and `synC` must all be well formed in the\ncontext `fv`.\n\nThere are some examples of how substitution is intended to behave (which I intend to turn into actual test cases\nat some point) at [src/test/subst.abt](https://github.com/calculemuscode/abt-js/blob/master/src/test/subst.abt).\n\n","readmeFilename":"README.md"}