3 ms·

For the reasons you give, it is perhaps more reasonable to say that Lisp is a Maxwell's Equations of software. But there are several. Forth has another reasonab

• kragen 4y ago
  i wasn't able to get a runnable forth to less than a couple of pages written in itself https://github.com/kragen/stoneknifeforth 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 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 4y ago
    > maybe wolfram knows of a simpler alternative Wolfram on combinators: https://writings.stephenwolfram.com/2020/12/combinators-a-centennial-view/ https://writings.stephenwolfram.com/2020/12/combinators-a-ce... not any simpler, but maybe these are: https://en.wikipedia.org/wiki/Iota_and_Jot https://en.wikipedia.org/wiki/Iota_and_Jot
    • kragen 4y ago
      oh yeah, how could I forget iota and jot, that was stupid of me
  • Gordonjcp 4y ago
    > 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