On: Lisp as the Maxwell’s Equations of Software (2012)

[kragen]

i wasn't able to get a runnable forth to less than a couple of pages written in itself https://github.com/kragen/stoneknifeforth but schönfinkel's ski-combinators are maybe the simplest practical basis

    s f g x → f x (g x)
    k a b   → a
    i = s k k (one of many possible definitions)

maybe wolfram knows of a simpler alternative

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

    {f = ς(v)b, g = ς(v)c, ...}{f = ς(v)d} → {f = ς(v)d, g = ς(v)c, ...}
    {f = ς(v)b, g = ς(v)c, ...}.f          → b[{f = ς(v)b, g = ς(v)c, ...}/v]

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. here's factorial(10) in the notation above (untested)

    {fac = ς(env){
        n = ς(_)3,
        return = ς(o)
            (o.n < 2).if_true{
                then = ς(_)1
                else = ς(_)o.n * env.fac{n = ς(_)o.n - 1}.return
            }.return
        }
    }.fac{n = ς(10)}.return

bicicleta has a lot of syntactic sugar which reduces this to (tested)

    {env: fac = {fac:
        arg1 = 3
        '()' = (fac.arg1 < 2).if_true(
            then = 1
            else = fac.arg1 * env.fac(fac.arg1 - 1)
         )
    }}.fac(10)

in particular to be able to define infix operators inside the language, bicicleta rewrites

    x * y

as

    x.'*'{arg1 = y}.'()'

and analogously for -, <, etc.

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 except as a compilation target or to prove theorems about

[gradschool → kragen]

> maybe wolfram knows of a simpler alternative

Wolfram on combinators:

https://writings.stephenwolfram.com/2020/12/combinators-a-ce...

not any simpler, but maybe these are:

https://en.wikipedia.org/wiki/Iota_and_Jot

[kragen → gradschool]

oh yeah, how could I forget iota and jot, that was stupid of me

[Gordonjcp → kragen]

> but schönfinkel's ski-combinators are maybe the simplest practical basis

Okay, but how much code goes into creating those operators?

[kragen → Gordonjcp]

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

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 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 → kragen]

> 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 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 → Gordonjcp]

> 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