2 ms·
it depends on what you're implementing them in, but in a term-rewriting language all you need is the two lines above. in js you need to implement some kind of
by kragen 4y ago
it depends on what you're implementing them in, but in a term-rewriting language all you need is the two lines above. in js you need to implement some kind of term-rewriting. in 02006 i wrote a compiler from λ-calculus (using \ for λ, so you can write for example \x.\y.x for λx.λy.x, which is equivalent to the k combinator) to an augmented sk-combinator language in js that's at http://canonical.org/~kragen/tmp/sk.html http://canonical.org/~kragen/tmp/sk.html
the definitions of s and k in it are
S: [3, function(f, g, x) { return App(App(f, x), App(g, x)) }],
K: [2, function(k, _) { return Ind(k) }],
which are used as templates for matching by the 33-line-long sk_reduce function, which i'll spare you here
the λ-calculus parser, the compiler from λ-calculus to sk-combinators, the sk-combinator parser, and the sk-combinator evaluator together are 391 lines of js
if you just want to define the s and k combinators in js they look like this
s = f => g => x => f(x)(g(x))
k = a => b => a
but that is depending on the js interpreter to do the actual evaluation
more recently i implemented a term-rewriting language in i386 assembly, it's about 800 bytes and 400 instructions: http://canonical.org/~kragen/sw/dev3/qfitzah.s http://canonical.org/~kragen/sw/dev3/qfitzah.s but i haven't quite figured out how to handle arithmetic, i/o, and variadic lists
i think you could probably implement sk combinatory logic in about half a page of c if you were okay with leaking memory, you don't really need the flexibility of variadic lists and arbitrary identifiers in the sk-combinator language. every term is either a function application (of one function to one argument), s, or k
- Gordonjcp 4y ago> it depends on what you're implementing them in, but in a term-rewriting language all you need is the two lines above Okay, so what do I type those two lines into to implement that? How many lines of code does that involve? > more recently i implemented a term-rewriting language in i386 assembly, it's about 800 bytes and 400 instructions: http://canonical.org/~kragen/sw/dev3/qfitzah.s http://canonical.org/~kragen/sw/dev3/qfitzah.s but i haven't quite figured out how to handle arithmetic, i/o, and variadic lists Have you considered having a parameter stack that arithmetic operators pull their arguments from and push their results onto? Oh wait... ;-)
- kragen 4y ago> so what do I type those two lines into to implement that? How many lines of code does that involve? i just answered that in the comment you are replying to > Have you considered having a parameter stack this is a remarkably bad answer to my explanation of how much code i needed to write a self-compiling forth that generates machine code what is wrong with you i am sad now