There isn't really a unique set of Maxwell's equations in software.
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 alternativemy 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
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
Wolfram on combinators:
https://writings.stephenwolfram.com/2020/12/combinators-a-ce...
not any simpler, but maybe these are:
Okay, but how much code goes into creating those operators?
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 herethe λ-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 evaluationmore 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
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... ;-)
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
Lisp had assignments and goto before it had recursion, and started as a dialect of Fortran! It was only later that Lisp programmers investigated the benefits of pure functions. Lisp was not based on lambda calculus, but rather Kleene's work on recursive functions. At the time, McCarthy had heard of lambda calculus but had not yet studied it!
FLPL already used the CAR and CDR terminology in its naming, with extra characters: XCARF and XCDRF (and others). The "extract CAR function" and "extract CDR function".
(λ11)(λλλ1(λλλλ3(λ5(3(λ2(3(λλ3(λ1 2 3)))(4(λ4(λ3 1(2 1))))))(1(2(λ1 2))(λ4(λ4(λ2(1 4)))5))))(3 3)2)(λ1((λ1 1)(λ1 1)))
[1] https://tromp.github.io/cl/Binary_lambda_calculus.htmlIt's literally just notation:
- It doesn't matter how you name variables. (if you want to sound cool: "lambda terms are invariant under alpha-conversion")
- Each new variable introduces a scope.
- Therefore, how scopes are nested defines the entire expression.
- Instead of the usual way, we represent scopes with numbers, with the index representing "how nested the scope is". Imagine it's python, and you're pressing tab that many times.
Look at how ugly decorators are in python when in lisp you get them for free and they don't even need a name.
Python is optimized towards simple pseudo-code like imperative OOP. That's easier for most programmers.
You might not have noticed the userid of the person you're replying to ;)
Maybe there's an infinite amount of mathematical theories that are turing complete. Why is lambda calculus chosen as the foundational one?
I would argue, the Maxwells equation of software should be MORE foundational. Not some arbitrarily specific turing complete language.
This is what I think it should be (link is a comment in the same thread): https://news.ycombinator.com/item?id=33533321
For Turing machines I recommend the book "The annotated Turing".
What does it mean to be Maxwells Equations? Does it mean absolutely most fundamental? Most practical? What?
Maybe there's something more fundamental then turing. Thanks for the book recommendation
In a word: elegant.
Maxwell’s equations are arguably the most successful existing physical theory. They are incredibly accurate over a huge range of scales. They are used in essentially unaltered form all over modern day engineering and have astonishing predictive power.
On top of this, they are a useful tool without modification! They are the working tool for all electrical engineers. They’re not some lower-level substrate that exists in the background. They are used directly to model and generate other, simpler approximate theories (such as geometric and physical optics) which are powerful and elegant in their own right.
I don’t think Lisp, lambda calculus, Turing machines, or similar can make this kind of claim.
1. take a situation observed or designed in the contingent universe,
2. translate it into the abstract entities maxwell's equations talk about,
3. deduce consequences in the world of abstract entities,
4. translate those consequences back into the contingent universe, and then
5. find that the consequences in the contingent universe are within narrow uncertainty bounds we translated from the abstract world of ideas
the meaning of turing universality is precisely that any turing-complete programmable system can be used to model any other logical or mathematical system, including other turing-complete systems, in exactly the same way that maxwell's equations model electromagnetism
for example, you can model risc-v execution in lisp and predict what a risc-v processor will do, you can model lisp execution in the λ-calculus and predict what a lisp interpreter will do, you can model the λ-calculus in a turing machine and predict what λ-reduction will do, and you can model a turing machine in a risc-v processor and predict what the turing machine will do
there is a significant sense in which this sort of modeling is much more perfect than the kind done with maxwell's equations
when we apply maxwell's equations, we are subject to measurement error in steps 1 and 5; our measurements are never complete and correct, and heisenberg's uncertainty principle strongly suggests that they never can be. and in step 3, because maxwell's equations are continuous-time continuous-space differential equations, we often also introduce numerical error in our calculations as well, because we usually have to integrate them numerically rather than algebraically
on the other hand, in the case of computational universality all the entities being discussed are discrete, algebraic, mathematically abstract entities, so our simulations are absolutely perfect unless we run out of memory or suffer a rare hardware error
obviously these universal machines are not limited to modeling other universal machines; we can also use lisp or turing machines or risc-v processors to model things like gravitation, taxation, or maxwell's equations. and they are obviously also the main working tool for all electrical engineers today, having displaced slide rules and load lines generations ago
ultimately, though, we are also using maxwell's equations (and other equations describing electromagnetism, like the ebers-moll transistor model) to design our electronic computers which we use to simulate lisp
Maxwell's equations are "the Maxwell's equations" of physics because they are "the most successful" physical theory: i.e., incredible accuracy, wide applicability, and concision. This is relative to other physical theories. (I guess you could debate whether this is actually the case---obviously this is all subjective, and not everyone agrees. Maybe someone thinks Einstein's field equations should really be "the Maxwell's equations" of physics.)
To say that the lambda calculus or anything else are "the Maxwell's equations" of computer science is to say that they have the same set of properties relative to other let's theoretical constructs in computer science. But is this actually the case? It seems like Turing machines, lambda calculus, etc. are all similar in terms of relative modeling utility and concision. I disagree that they are widely applicable---in practice, just about any commonly used programming language is far more widely applicable than anything of these. And as you pointed out, by Turing universality, they're all logically equivalent---so the question of difference in modeling "power" is not relevant here.
I guess I just don't think it makes much sense to talk about anything in CS being "the Maxwell's equations" of CS. In physics, a wide variety of disparate physical phenomena are being modeled, with individual models having a quite varied range of power and applicability. In CS, things are much different.
Incidentally, even if you simulate Maxwell's equations on a computer using Lisp, a Turing machine, or whatever else, you will not go far if you insist on algebraically exact computations. :-) As you say yourself, you must integrate them numerically, which means numerical error introduced through your discretization. But I honestly can't say I understand your point including this information above.
similarly there are lots of equivalent formulations of universal computation. lisp and the λ-calculus are analogous to the geometric-algebra formulation above and the more commonly used form in terms of vector field derivatives: they look very different, and they make different problems easy, but ultimately they all model the same thing, just like the various formulations of maxwell's equations
maxwell's equations are the maxwell's equations of classical electrodynamics, not of physics. without a lot of extra assumptions they won't get you very far in understanding why solid things are solid (which depends on the pauli exclusion principle) or why some nuclei break down or how transistors work or how stars can burn or why mercury's orbit precesses or why hot things go from red to orange to yellow when you heat them further
my point about modeling maxwell's equations in lisp (etc.) is that lisp (etc.) can model maxwell's equations (at least, as well as anything else we know of can model them), so if we're looking for incredible accuracy, wide applicability, and concision, lisp (etc.) would seem to trump maxwell's equations — but good luck trying to build a computer without electromagnetism, maybe you can in some sense do it on a neutron star but not with atoms
So, yes, since I've used the lc in these ways I believe the same claim can be made regarding the lambda calculus.
[1] http://www.verostko.com/tur-doc.html#B0,%20Universal%20Turin...
For that reason, only _typed_ lambda calculi have any hope of corresponding to a proof system. You could rephrase Lisp as a Unityped system, but I seriously doubt it would be consistent.
Perhaps a para-consistent logic might work, but we're getting very exotic here.
It's not. (x -> x) is always inhabited, so if you have a fixed point combinator (x -> x) -> x then every theorem is true.
Syntax is not semantics.
The only thing that s-expressions do that is mathematically interesting is make the abstract syntax tree of expressions explicit in a way that standard notation does not. The whole point of them is that they make string rewriting into tree rewriting which is vastly easier and lets you write your own DSLs a breeze.
From a practical point of view they are also the simplest way to serialize any expression which is why I can type them out in a text only comment as they are. Meanwhile doing the same with a math (or lambda calculus) expression requires a type setting system like latex to be understandable.
Lisp has decided that application is nameless in its syntax which means that things like ((lambda (x) (+ x 1)) 2) work when semantically they mean (apply (lambda (x) (+ x 1)) 2). This makes programming with multivariable functions very clean but partial application incredibly messy, e.g. ((((lambda (x) (lambda (y) (lambda (z) (+ x y z)))) 1) 2) 3). This is not something that can be fixed because the ABS of partial application when thought of as a tree is indeed very messy. The only reason why it works in languages like Haskell as well as it does is that as long as you only have single variable function - goodbye thunks and multivariable functions - you can treat the partial application trees as a list instead.
You can of course do the same in lisp using a DSL:
'(partial
((lambda (x)) (lambda (y)) (lambda (z)) (lambda (w) (+ x y z w)))
(1 2 3 4))
But it doesn't fit very well with the rest of the language and feel quite pointless.In lambdatalk the implementation of lambdas does not make them closures (no free variables) but is such that they accept de facto partial application and a number of values higher than the number of arguments. This compensates for the lack of closure. So for instance:
((lambda (x)) (lambda (y)) (lambda (z)) (lambda (w) (+ x y z w))) (1 2 3 4))
is written this way
{{{{{lambda {x y z w} {+ x y z w}} 1} 2} 3} 4} -> 10
and obviously
{{lambda {x y z w} {+ x y z w}} 1 2 3 4} -> 10
- http://lambdaway.free.fr/lambdawalks - http://lambdaway.free.fr/lambdawalks/?view=lambdacode5
No need for cons, car, cdr and other historical names. We can rebuild everything from scratch, from abstractions and applications. No need for Lisp, Scheme, Common Lisp and other Clojure, even if they remain excellent examples. So in my opinion the Maxwell equations of computation are to be seen more in the lambda-calculus than in LISP and its dialects. We just need to make the syntax a little more human.