Hacker News Reader

Comment by tromp | Hacker News Reader

In my opinion, "Maxwell's equations of software" ought to be based on the simplest possible computational framework, which one could argue is the lambda calculus.

A meta circular interpreter working on a simple binary encoding of lambda calculus (where abstraction is 00, application is 01, and a variable is 1^{n}0) is only 206 bits long [1][2], over 20 times smaller than the article's equations.

[1] https://tromp.github.io/cl/cl.html

[2] https://tromp.github.io/cl/LC.pdf

View on HN

One issue with lambda calculus that could indicate it is not the "simplest possible computational framework" is that there is no bound on the amount of work a single step of beta reduction will do. It is dubious to call such a black box computational action simple. You can decompose beta reduction into smaller steps but I wouldn't say it's obvious which refinement of lambda calculus is simplest.

Furthermore, the complexity of beta reduction means that there are a multiplicity of strategies for executing it which are external to the definition of lambda calculus. Not so simple.

Lambda calculus also has a bias for the flow of information from the leaves of a term up to its root while demands flow from the root to the leaves. This is basically how functions work but it produces an asymmetry between a term and its environment. Higher order terms allow information to flow in very complex ways but there are simple computational ideas that are hard to capture in lambda calculus without monstrously complicated recursion schemes or modifications to lambda calculus. Think of the symmetric possibilities of flow of information in a spreadsheet.

Asynchronous computation, concurrent processing, and sharing of work have been with us since the dawn of computers and have their own basic mechanisms and principles, but they are at odds with beta reduction and functional information flow.

Lambda calculus is amazing but there surely is a frontier beyond it. Human reasoning is frequently biased to think functionally, in terms of inputs and outputs where outputs are treated differently from inputs, but the world and computation are full of relations and processes, too.

I think the SKI combinators are quite a bit simpler than lambda calculus. In lambda calculus the renaming of dummy variables is quite tricky. E.g., these lecture notes actually get substitution wrong: https://www21.in.tum.de/teaching/lambda/WS1718/lambda.pdf but I only found out after using the substitution rules on page 7 in a formalization of lambda calculus.

As mentioned in my other comment, combinatory logic is simpler, but it's also less expressive, and results in a larger self-interpreter in the corresponding language. For conciseness in language self-interpreters, (binary) lambda calculus is hard to beat.

SKI, Lambda Calculus, Turing Machines... FWIW, I think concatenative notation is the simplest useful computational framework. ( https://joypy.osdn.io disclosure: it's my project.) But I'm not mathematically sophisticated enough to make the formal argument.

How about a 2 state 3 symbol Turing machine? That’s pretty simple, and universal too.

https://en.m.wikipedia.org/wiki/Wolfram%27s_2-state_3-symbol...

As tromp has a meta-circular implementation of lambda calculus maybe that Turing Machine could be implemented in lambda calculus and we could have an objective measure of which one is "simplest"?

It takes 829 bits of binary lambda calculus to interpret BrainFuck, which is very simple programming language modeled after Turing Machines. A self-interpreter in BrainFuck takes well over a thousand bits though [2]. Lambda calculus is not only very simple, but also very expressive. While combinatory logic, with only S and K, is even simpler than lambda calculus, and also has a trivial binary encoding (00 for S, 01 for K, and 10 for application), the shortest known self-interpreter is 263 bits, appreciably larger than for lambda calculus. My IOCCC entry [3] has more examples of the conciseness of binary lambda calculus.

[1] https://tromp.github.io/cl/Binary_lambda_calculus.html#Brain...

[2] https://arxiv.org/html/cs/0311032

[3] http://www.ioccc.org/2012/tromp/hint.html

How does this logic compare to say Forth, APL or Joy? As far as I'm aware, they are all combinatorial languages - are they effectively implementations of SK combinators?

"The Theory of Concatenative Combinators" (http://tunes.org/~iepos/joy.html) connects combinatorial logic with Joy.

FWIW, I think concatenative notation is the simplest useful computational framework. ( https://joypy.osdn.io disclosure: it's my project.) But I'm not mathematically sophisticated enough to make the formal argument.

It's not directly comparable, since this Turing Machine is not a self-interpreter in the sense of interpreting arbitrary programs in a language of Turing Machines.

First off, I admit I didn’t do my homework so I have no idea what I’m talking about, but couldn’t the Turing machine make a Turing machine interpreter and therefore be a self interpreter? It is universal, no?

There's different notions of universality.

In the more abstract one, you can emulate arbitrary computation by preparing the system (in case of the 2 state 3 symbol TM, its tape) in an appropriate configuration, letting it run until some the configuration satisfies some condition, and then extracting the result from the final configuration.

In a more concrete one, you have a language of programs, and a universal program takes a program description as input, and interprets it. I give a slightly more formal definition of such a notion of universality, as applicable to Algorithmic Information Theory, in [1].

[1] https://tromp.github.io/cl/Binary_lambda_calculus.html#Unive...

Reply on news.ycombinator.com