3 ms·

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 calculu

by tromp 6y ago

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 https://tromp.github.io/cl/cl.html [2] https://tromp.github.io/cl/LC.pdf https://tromp.github.io/cl/LC.pdf

cjfd 6y ago
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 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.
- tromp 6y ago
  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.
esmi 6y ago
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_Turing_machine https://en.m.wikipedia.org/wiki/Wolfram%27s_2-state_3-symbol...
- arethuza 6y ago
  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"?
  - tromp 6y ago
    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#Brainfuck https://tromp.github.io/cl/Binary_lambda_calculus.html#Brain... [2] https://arxiv.org/html/cs/0311032 https://arxiv.org/html/cs/0311032 [3] http://www.ioccc.org/2012/tromp/hint.html http://www.ioccc.org/2012/tromp/hint.html
    - alexisread 6y ago
      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?
      - kryptiskt 6y ago
        "The Theory of Concatenative Combinators" (http://tunes.org/~iepos/joy.html http://tunes.org/~iepos/joy.html) connects combinatorial logic with Joy.
      - carapace 6y ago
        FWIW, I think concatenative notation is the simplest useful computational framework. ( https://joypy.osdn.io https://joypy.osdn.io disclosure: it's my project.) But I'm not mathematically sophisticated enough to make the formal argument.
- tromp 6y ago
  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.
  - esmi 6y ago
    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?
    - tromp 6y ago
      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#Universality https://tromp.github.io/cl/Binary_lambda_calculus.html#Unive...
danharaj 6y ago
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.
carapace 6y ago
SKI, Lambda Calculus, Turing Machines... FWIW, I think concatenative notation is the simplest useful computational framework. ( https://joypy.osdn.io https://joypy.osdn.io disclosure: it's my project.) But I'm not mathematically sophisticated enough to make the formal argument.

by tromp 6y ago

cjfd 6y ago

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 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.

tromp 6y ago
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.

esmi 6y ago

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_Turing_machine https://en.m.wikipedia.org/wiki/Wolfram%27s_2-state_3-symbol...

arethuza 6y ago
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"?
- tromp 6y ago
  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#Brainfuck https://tromp.github.io/cl/Binary_lambda_calculus.html#Brain... [2] https://arxiv.org/html/cs/0311032 https://arxiv.org/html/cs/0311032 [3] http://www.ioccc.org/2012/tromp/hint.html http://www.ioccc.org/2012/tromp/hint.html
  - alexisread 6y ago
    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?
    - kryptiskt 6y ago
      "The Theory of Concatenative Combinators" (http://tunes.org/~iepos/joy.html http://tunes.org/~iepos/joy.html) connects combinatorial logic with Joy.
    - carapace 6y ago
      FWIW, I think concatenative notation is the simplest useful computational framework. ( https://joypy.osdn.io https://joypy.osdn.io disclosure: it's my project.) But I'm not mathematically sophisticated enough to make the formal argument.
tromp 6y ago
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.
- esmi 6y ago
  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?
  - tromp 6y ago
    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#Universality https://tromp.github.io/cl/Binary_lambda_calculus.html#Unive...

danharaj 6y ago

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.

carapace 6y ago

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