3 ms·

> but schönfinkel's ski-combinators are maybe the simplest practical basis Okay, but how much code goes into creating those operators?

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

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