If you do it that way, you can binary right shift a number by consing a nil at the front, or binary left shift by taking the cdr. You can increment, decrement, add and subtract efficiently, too. Even take logarithms.
I had to use this to replace Lisp's namesake linked lists with another data structure that allowed many of the same niceties, but required some math, and therefore naturals, to find elements in the data structure. It was an interesting project. If you made it through the whole article, you might want to look:
This is the old representation of numbers in raw Lisp, which uses lists of length n to represent the number n. Incrementing and decrementing are easy, you simply cons or cdr. Subtraction and addition are slower, though, and multiplication, division, left- and right-shifting are really slow.
Beyond that, I'm talking about creating natural numbers for internal use; no outside interpretation happens, as it does in Automated Mathematician. At no point does the computer output these natural numbers; it just uses them to navigate a data structure so it can run a REPL.
'(λ args body)
($vau args env body) 
Arguably then, Kernel is more fundamental than Lisp.
: Manuel Simoni has a short overview of $vau here:
Besides that, I think you're overstating its significance.
a) Maxwell's equations don't claim to be 'most fundamental'. They are a concise basis set for a space of problems. They occupy a memetic sweet spot; abstractions both above and below them are more verbose. The metacircular interpreter of Kernel can't compete with McCarthy's version.
b) Any language with fexprs is 'as fundamental' as Kernel. Including LISP 1.
c) In its search for hygiene Kernel eliminates quote. Scheme folks will likely find this a useful tradeoff, while common lisp folks with their backquoted macros will shudder. In kernel you 'create macros' by explicitly consing code.
By this metric, Lisp is obviously the analogue in the programming world. It would have been nice though if Lisp had triggered a sudden paradigm shift instead of this painful 50 year burn we're living through.
First, it doesn't cover macros, while Kernel subsumes functions and hygienic macros with a single construct. Second, I don't think a toy version of a Kernel metacircular evaluator would be much more complex than the toy McCarthy evaluator.
"Any language with fexprs is 'as fundamental' as Kernel. Including LISP 1."
Only if said language is lexically scoped, and fexprs receive the lexical environment in which they are called as parameter, as in Kernel. Otherwise you'll miss hygiene.
Maybe it's just me, but I don't consider 'better supports hygiene' to imply 'more fundamental'. It doesn't add new capabilities. It merely prevents certain kinds of errors.
Lambda in Kernel is defined as follows:
($vau (formals . body) env
(wrap (eval (list* $vau formals #ignore body)
(lambda args body)
(wrap ($vau args #ignore body))
I recommend shutt's thesis.
Here's a discussion on LtU about Pitman-vs-Kernel: http://lambda-the-ultimate.org/node/3640
b) Pitman actually points out that dynamic binding makes compilation of fexprs harder. That was also one of the original selling points of scheme: lexical binding simplifies compiler implementation.
c) Issues of practical compilability are extremely likely to be context-sensitive and hard to generalize from. That some lisp 35 years ago had a hard time compiling some language involving fexprs doesn't help decide if this language here and now can use them.
d) Finally, you're attacking a strawman of your own creation. Pitman didn't focus on dynamic binding, sure. Who said otherwise? That insight was one of Kernel's contributions, that a world where lisps are lexically scoped is actually quite a good fit for fexprs.
Pitman was working on large software systems where compilation was the norm and useful.
In any case, the claim that fexprs make compilation challenging for large software systems is much more nuanced than what you were implying earlier, that Kernel's no different from "the 1960s".
Now that compilation is less challenging thanks to lexical scope, and with computers being so much faster, it's worth considering whether fexprs can be compiled to be fast enough (say to ruby levels for a start). That would still be valuable. Right?
I think it's very superficial to claim that only 'two sentences' of Shutt's thesis were about 'Pitman'. He mentioned the concerns in the abstract, for crying out loud. He's addressing the issues throughout even if he isn't constantly paying homage to some sort of Pitman deity.
However, I'm not so sure this is really so important in practice. We tend to operate within bounded layers of abstraction for any given problem and it's far more important that those layers are predictable, comprehensible, and, ideally, well-documented.
This is why a language like Java, for instance, can be very productive even though the fundamental abstractions are not plastic. And this is also why more malleable languages like Scheme or Lisp can be less productive because there's not enough consensus on how the higher layers should be defined.
Oh and for everyone who wants to get into functional programming, very quick (and very hard) simply has to read this Wikibook. It's short, but you will most likely have _understood_ two functional languages (Scheme and Haskell), if you do it seriously:
So Racket for a great (free) time and the latter one for Hackers. At least that's what it looks to me. I just have skimmed through them, but they are the best two things I have found in a while.
So, cool, but why not push this metaphor further? That's the dangerous idea.
The dangerous idea is that Maxwell's equations don't use voltages. We love voltages. They're useful everywhere. In Einstein's special relativity, once you invent voltages (and their magnetic counterpart, the vector potential) all four Maxwell equations stop being separate, they all take the same form. So you tack the charges ρ onto the current j to get the 4-current Jⁿ = (ρ c, j). You tack the voltage V onto the vector potential a to get the 4-potential Aⁿ = (V/c, a). Then the entire set of Maxwell's equations becomes a single wave equation of your voltages emanating from your currents:
∂ᵢ ∂ⁱ Aⁿ = μ₀ Jⁿ
Fᵤᵥ = ∂ᵤ Aᵥ − ∂ᵥ Aᵤ
Now, before this becomes a rant, here is the idea. Is there a way in which apply can look like eval, and eval can look like apply? If Einstein is a lesson, we might have to invent a means of programming where you look directly at invariants which you want to create.
The goal is that you should just specify an inhomogeneity, a little piece of data and some information on how it should be. The computer then constructs the invariants through some sort of "computational wave" -- and from this the computer can derive the actual field, the instructions needed to actually run the process on a computer.
There are some tantalizing suggestions and possibilities. The Meta II compiler (recently extended in JS as the OMeta project, which is definitely on my source-code reading list) works by realizing that a bunch of different stages in compilation are all just the same idea of pattern matching.
Perhaps one day we'll do what we do with photomultiplier tubes: we just visualize the voltages that we'd need to focus and accelerate electrons into the metal plates, and not even pay attention to the lower-level picture of how these fields are being generated to do the right thing.
However, don't you think the reason for the success of Maxwell is because the objects it describes are well behaved and can be completely described by a set of partial differential equations? Where as the constituent atoms (hehe) of software are themselves complex objects - more than just point particles whose state can be completely described by say a wave function. And their behvior effectively solvable by simple deduction from physical postulates and the axioms of mathematics. I believe I saw a story about Feynman deriving a bunch of partial differential equations to predict the behavior of a program. But I do not think such an approach is scalable.
But the core of your idea I believe is that by specifying invariant in some theory which encapsulates the possible evolution of all possible programs then you can write programs far more simply? Essentially the next level of a synthesis of programming with unit tests, data and automatic programming. I believe the main impedance to this (I think) is that any such general evolution function would be incomputable. And where as with Maxwell equations the space is limited and the boundaries defined and embodied and easily deductively traversed, for a program the search space would be massive and difficult to search effectively. In effect, I believe you have just specified an AI complete problem.
Notice also that even a classical theory like general relativity yields few analytic solutions and numerical simulations are expensive. Perhaps this hints at why a unified theory is so difficult to come by? While the constituents are still simple particulates, the size of a theory/program which encompasses in totality all possible behaviors in nature might require a chain of reasoning so deep it lies beyond the ken of unaugmented humans. I believe a unified theory of efficiently searchable programs would be even more difficult - such a theory would yield a unified theory of nature as a special case.
I remember seeing a program that would output Haskell functions given just their type signatures. If you think of type signatures as invariants, this is exactly what drostie described. Alas my Google-fu was unable to find a reference to it.
I have considered this road, see this LtU discussion to see why this approach though wonderful, is still too limited for general programming. http://lambda-the-ultimate.org/node/1178
Essentially, as is found in many automatic program derivation attempts, recursion explodes complexity.
Vau, from kernel, may be a candidate.
It's also a pity that there is no discussion of the “label” special form, even though its implementation was right there in the code being discussed. This is a very fertile area for conversation.
For example, why is it that McCarthy was able to implement recursive procedures with “label” so simply without using any assignment or mutation?
Is that really what is implied here?