“Maxwell's equations of software” examined (2008) | Hacker News Reader

“Maxwell's equations of software” examined (2008)

righto.com

70 pointslelf48 comments

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

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

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.

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.

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.

As someone who spent years studying Computational Plasma Physics, it feels strange to see someone cite "Maxwell's Equations" as some sort of platonic form of simplicity

I think the comparison might be subtly apt. Maxwell's is clean when deriving EM waves in a vacuum, but once you add in particles and go to the real world it becomes a mess just as you need much more than lambda expressions and evals to build software.

I have never understood the need in the Computer field or other fields for that matter to make unnecessary and incorrect analogies to physics. It is silly and I have to look past this as many things have worth where the author does this as some sort of way to make what they did seem more impressive rather than just advance something on its own merits.

I guess there's something to be gained by doing that. (By contrast, electrodynamics wouldn't gain anything by calling Maxwell's equations "the lambda calculus of physics.")

I would say that we as CS people could learn from physics but when name things God Particle... Arguably to grab headlines I wonder about the Physics world... Then again I guess things like funding and getting people interested are important.

As Lederman explains, "This boson is so central to the state of physics today, so crucial to our final understanding of the structure of matter, yet so elusive, that I have given it a nickname: the God Particle. Why God Particle? Two reasons. One, the publisher wouldn't let us call it the Goddamn Particle, though that might be a more appropriate title, given its villainous nature and the expense it is causing. And two, there is a connection, of sorts, to another book, a much older one..."

Haven't read Lederman's book but sounds interesting. If he is referencing the Bible that makes me not like the name even more however names really are pretty trivial and aren't the real science so I guess it doesn't even matter. It is just my opinion doesn't really mean much in the grand scheme of things, both my opinion and what he names the Higgs-Boson.

I think current bootstrapping work clearly shows that the Maxwell equations of software are:

   pop rx -> sp--; rx := mem[sp]
   push rx -> mem[sp] := rx; sp++
   sub rx ry -> rx := rx - ry
   jmp rx $I -> if rx is zero jump $I bytes from end of instruction.

One might also argue:

   call rx -> mem[sp] := IP; sp++; IP := rx
   ret -> sp--; IP := mem[sp]
   nand rx ry -> rx := rx nand ry

but those are just optimizations

Exactly what bootstrapping work? Looks interesting (and like Forth, but that's no surprise).

There is really nothing to it. A Lisp interpreter runtime can be made to interpret a subset of Lisp.

It is very much more impressive that you can make a whole computer out of nothing but NAND or NOR gates, but still the same sort of thing.

Depends very much on gates. They would have to be idealized, with constant non-zero input-to-output propagation time. Best approach is then to simulate them, perhaps in Lisp.

I'm guessing that's because you envision using some of those gates to fake a clock. Wouldn't you also have to make some assumptions about wire propagation delays to guarantee hazard-free operation?

Any wire propagation would work, zero or positive, as long as it is deterministic (it can all be compensated by extra NAND/NOR gates). And with negative propagation delays you could do wonders! Anyway, my comment was a quick jab to circle back to Lisp after parent dismissed its elegant core.

Are you aware that CDC did, in fact, make mainframe computers out of physical NOR gates? One gate per PC board.

Maxwell's equations are linear (solutions are superimposable etc.)

I think if you'd call something "Maxwell's equations of software", a similar property should hold, somehow ...

Only if you take U(1) as your gauge group. If you pick a non-abelian group the equations are not linear and solutions are not superposable.

Maxwell's equations are linear. The nonlinearity of quantum field theory is not relevant here.

I was trying to convey that "Maxwell's equations" can name not just the equations that describe electromagnetism, which has a U(1) gauge group, but can name an entire category of gauge theory equations---one for each gauge group. If the gauge group isn't abelian Maxwell's equations are _not_ linear.

Can you give a example of a set of gauge theory equations for a non-U(1) gauge group? This seems interesting but I'm not really sure what it would actually look like.

QCD is a nonabelian gauge theory, for example. The generalized Maxwell action is called the Yang-Mills action. The corresponding equations are very similar, except the gauge-covariant derivatives do not take a particularly simple form (which they do in the U(1) case because U(1) is abelian).

https://physicstravelguide.com/equations/yang_mills_equation...

We should think about linear computing axioms.

side question : i remember a course in my logic class where our teacher showed us a programming language made of only two letters, and where all operations, numbers, etc were all defined with just those two letters. It was created by some famous logician but i can't find anything on the web about it.

Anyone here knows what that could be ?

edit : i think the lesson was showing curry's work on combinator logic..

Perhaps this is related. I learned that in fact you do not need for "God made the integers". The definition of every object in mathematics can be bootstrapped from the empty set. 0 is the set containing the empty set. 1 is the set containing 0 and the empty set. Etc. Perhaps the two symbols you are thinking of are equivalent to "{" and "}".

> 0 is the set containing the empty set. 1 is the set containing 0 and the empty set. Etc. Perhaps the two symbols you are thinking of are equivalent to "{" and "}".

This is not the usual von Neumann encoding (https://en.wikipedia.org/wiki/Ordinal_number#Von_Neumann_def...), so I think you may have started one level too encoded. The usual encoding puts 0 equal to the empty set, and n + 1 equal to the union of n (a set with n elements) and {n} (a singleton with 1 element).

In other words, if I understand the meaning of 'Etc.', your encoding puts

    0 = {Ø}, 1 = {0, Ø} = {{Ø}, Ø}, 2 = {1, Ø} = {{{Ø}, Ø}, Ø}, …,

whereas the usual encoding puts

    0 = Ø, 1 = 0 ∪ {0} = {Ø}, 2 = 1 ∪ {1} = {Ø, {Ø}}, ….

One advantage of this latter encoding is that the set n has n elements, and that the set n is n-times nested, in the sense that longest chain of elements x ∈ y ∈ z ∈ … ∈ n has length n. It also generalises nicely to ordinals (a transfinite generalization of the natural numbers), as explained in the above link (https://en.wikipedia.org/wiki/Ordinal_number#Von_Neumann_def...).

Probably it was indeed combinatory logic, but see also https://en.wikipedia.org/wiki/Iota_and_Jot

'0' and '1'? Sorry :P

You can technically do it with only one character (via Godel numbering and unary), but it gets annoying fast for obvious reasons.

https://en.wikipedia.org/wiki/SK_combinator_calculus ?

Sounds like SKI combinators. Three combinators: S,K and I. I is technically optional.

https://en.m.wikipedia.org/wiki/SKI_combinator_calculus

I would guess the SK combinators.

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

Thanks, that was the one. This looks like a more fundamental axiomatic than lisp meta-circular evaluator. I'm surprised it didn't give birth to more experimentation (maybe because i remember it had some very weird properties and things that looked a lot like inconsistencies..)

"very weird properties and things that looked a lot like inconsistencies"

Any idea what they were - as my final year project of my CS degree I did an implementation of a simple purely functional programming language that macro expanded into lambda calculus and then was converted into various sets of combinators for evaluation (from SK upwards). I thought there was actually a stunning lack of weirdness and inconsistency - mind you this did also come with a stunning lack of performance!

NB The trickiest bit of the whole project was writing a garbage collector so I could actually get these things to run on a shared Unix mini-computer....

Edit: Getting Y (and therefore recursion) working purely in terms of SK still amazes me.

I think to remember something about being able to compute the fixed point of the function x -> x+1 (that is, a number for which this function returns the same number). Our teacher showed us this function, and i think he also told us, curry reaction when people showed him this was something along the line of « well, that just means my theory is more powerful than yours, because it can express things yours can’t ».

that was 20 years ago, but it made a big impression on me, so i think my memories are correct :)

The language Whitespace [1] has 3 characters only: spaces, tabs and linefeeds.

[1] https://en.wikipedia.org/wiki/Whitespace_(programming_langua...

Reply on news.ycombinator.com