Wolfram on combinators:
https://writings.stephenwolfram.com/2020/12/combinators-a-ce...
not any simpler, but maybe these are:
Okay, but how much code goes into creating those operators?
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 herethe λ-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 evaluationmore 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 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
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 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... ;-)
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
my favorite is abadi and cardelli's object-calculus on which i based bicicleta. it has two reduction rules rather than the λ-calculus's one. using a hybrid of bicicleta's syntax and abadi and cardelli's
the first of these derives an inherited object with a new definition for method f. the second one invokes method f on an object, which is evaluated by replacing its self-variable v with the object itself throughout its body, using the standard β-reduction semantics with α-renaming that we're familiar with from the λ-calculus (b[x/y] means b but with x replacing y)despite the simplicity of the semantics the ς-calculus is enormously more usable for actually writing down functions than the λ-calculus
they published a bunch of papers and a book on this but they were more interested in static typing than anything else. a paper on one imperative variation of the thing is http://lucacardelli.name/Papers/PrimObjImpSIPL.A4.pdf
you can implement a turing machine in a few lines of c, making it internally simpler than the other alternatives, but as you point out it's unusable