### Maxwell's equations of software

I haz dem:

To grok Nock, construct a formula

As you'll quickly see if you try this exercise, raw Nock is not a usable programming language. But nor is it an esoteric language or automaton, like SK combinators. Rather, Nock is a tool for defining higher-level languages - comparable to the lambda calculus, but meant as foundational system software rather than foundational metamathematics.

To define a language with Nock, construct two nouns,

For context and comparison, see this or this or this. Here at UR, axioms are axioms - we leave no "niceties such as arithmetic" to the programmer's imagination. Just sayin'.1 Context

This spec defines one function, Nock.

2 Structures

A noun is an atom or a cell. An atom is any unsigned integer.

A cell is an ordered pair of any two nouns.

3 Pseudocode

Brackets enclose cells. [a b c] is [a [b c]].

*a is Nock(a). Reductions match top-down.

4 Reductions

?[a b] => 0

?a => 1

^[a b] => ^[a b]

^a => (a + 1)

=[a a] => 0

=[a b] => 1

=a => =a

/[1 a] => a

/[2 a b] => a

/[3 a b] => b

/[(a + a) b] => /[2 /[a b]]

/[(a + a + 1) b] => /[3 /[a b]]

/a => /a

*[a 0 b] => /[b a]

*[a 1 b] => b

*[a 2 b c d] => *[a 3 [0 1] 3 [1 c d] [1 0] 3 [1 2 3] [1 0] 5 5 b]

*[a 3 b] => **[a b]

*[a 4 b] => ?*[a b]

*[a 5 b] => ^*[a b]

*[a 6 b] => =*[a b]

*[a [b c] d] => [*[a b c] *[a d]]

*a => *a

To grok Nock, construct a formula

`f`

such that `*[s f]`

equals `(s - 1)`

for any atomic nonzero subject `s`

. The equivalent formula for `(s + 1)`

is `[5 0 1]`

. The first 16 people who mail me a correct answer may (or may not) win a prize, which may (or may not) be valuable. (Please include your interpreter - in any language, it should fit on a page. Please do not post the answer here or anywhere, and let me know if you see it posted. This is not a difficult problem.)As you'll quickly see if you try this exercise, raw Nock is not a usable programming language. But nor is it an esoteric language or automaton, like SK combinators. Rather, Nock is a tool for defining higher-level languages - comparable to the lambda calculus, but meant as foundational system software rather than foundational metamathematics.

To define a language with Nock, construct two nouns,

`q`

and `r`

, such that `*[q r]`

equals `r`

, and `*[s *[p r]]`

is a useful functional language. In this description, `p`

is the function source; `q`

is your language definition, as source; `r`

is your language definition, as data; `s`

is the input data. You will find this a tractable and entertaining problem.
## 66 Comments:

Dude, this isn't funny. Write something real.

ps. First.

I seriously have no idea what this post is about.

Can anyone translate and explain?

Author does not appear to have defined a reduction for *[a b], which appears to render much of the post meaningless. Too much raw pork & opium?

He has a reduction for *[a, b] if you understand a,b... to range over cells rather than just atoms.

I'm not quite sure what he intends for the reduction order, but instead of his axioms like:

=a => =a

I have implemented the axiom:

a => b

--------

=a => = b

With this I can reduce his testcase (NB: it actually reduces to *(s +1), not (s + 1)):

**[10, [5, [0, 1]]]

*^*[10, [0, 1]]

*^/[1, 10]

*^10

*11

Boo!

Can anyone who knows about such things tell me if this is good/important/interesting?

Off topic: Has anybody seen a show on PBS called "The Human Spark"? I saw about two minutes last night before my wife made me change the channel. Alan Alda was on, clearly talking about the Calivinist "Divine Spark" but treating it as if it were some kind of scientific concept. I believe he even informed the audience that scientists are close to figuring out why humans have "the spark" and not so chimpanzees. I would have thought this "spark" business would have dies out more completely from the progressive "meme-plex".

@Max: you get (s + 1) like this:

*[s 5 0 1]

= ^*[s 0 1]

= ^/[1 s]

= ^s

= s + 1

J. McCarthy had them in 1958.

@Abishek:

You are right - my outer * comes from my interpreting the statement that "*a is Nock(a)" as saying that before starting reduction of a nock program a, you slap a * on the front.

Dropping that assumption leads to the reduction to (s + 1).

It's not immediately obvious to me how to do subtraction :-(

OK, now that we have this new kind of MM postwaster, is anyone a little bit nostalgic for a nice poem?

Moldbug, I have a solution but I do not know your email. It is surprisingly difficult to find.

ref email: found moldbug@gmail.com

Please inform me if this is incorrect.

The 3 operator is more important than 2. They should be switched. Maybe 2 can be dispensed with altogether. It certainly doesn't deserve its current place. Perhaps not even in the top 10 places; or at the end of it.

Indeed, with operators 0 1 3 you already have a universal system. Then come 5 and 6 (though 6 I suppose could be restricted to integers). 4 isn't as essential as them (especially with static typing discipline), though it is admittedly quite useful. 2 is quite nice to have but not necessary as a primitive.

@Fare

5 is needed for data manipulation. 6 is needed for equality testing. Without these two, I don't think the language is turing complete. Also, the last form with [] is IMO necessary for turing completeness -- recursion/looping is impossible without it.

If I am wrong, please demonstrate how.

I think

that operators should be renamed in the next version of NOCK. Here is

my argumented proposal.

Renaming of operators, current number to proposed new number:

0 => 0 / (accessor)

1 => 2 (quote)

2 => 8 (if)

3 => 1 (eval)

4 => 6 (cell test)

5 => 5 ^ (increment)

6 => 4 = (comparison)

Or in order of importance, in the proposed new encoding:

0 <= 0 / (accessor)

1 <= 3 * (eval)

2 <= 1 ' (quote)

-gap-

4 <= 6 = (comparison)

5 <= 5 ^ (increment)

6 <= 4 ? (cell test)

-gap-

8 <= 2 if (conditional)

Indeed, with the cell distributivity law and accessors, you can a

semi-useful data extraction language; add the recursive evaluation,

you have Turing-equivalent language modulo adding magic constants in

the input; add the quote, you can actually add the constants on the

code side. In some handwriting styles, a Q and a 2 look alike, so 2 is

good for Quote. Either comparison or increment alone isn't too useful,

but comparison alone is more useful (at least if it applies to

arbitrary structures, even if it only applies to integers). With both

comparison and increment, arithmetic becomes possible. Cell test good

to have for dynamic data structures, but with static typing or other

discipline, you can do without, and with explicit tagging you could

encode a system with it in a system without it though it'd be painful.

The conditional is nice to have, but it's definitely a derivative

construct and so deserves to be singled out; plus the glyph for 8 has

two components, unlike glyphs for other digit, which makes it well

suited for a two-pronged conditional construct.

@Fare

Your analysis of nock seems spot on. Personally, I would get rid of the cell test. MM seems to want a complete bare-bones language and for that, a cell-test is extraneous.

On another topic, you may have given out too much information with your descriptions of the operators.

You appear to have discovered Scheme.

newt:

If that's too much information, please illuminate the uninitiated as to why.

Also Leonard, hell yes I'd rather have a poem but this is also interesting -- though it would be moreso if I knew what in the heck in meant.

@GM Palmer

with the pseudo-code given, figuring out the solution is just coming up with the correct algorithm which is pretty simple. This probably changes by person.

I'm having some trouble with the slash rule:

/[(a + a) b] => /[2 /[a b]]

Can someone please tell me what I'm doing wrong:

/[4 0]

/[2 /[2 0]]

/[2 /[2 /[1 0]]]

/[2 /[2 0]]

OH NOES INFINITE LOOP!

@Anon,

Miss-application. the /[(a+a) b] rule does not apply for a = 1. Perhaps MM should have been clearer on this...

Basically, /[4 0] is malformed. It will result in a halt (in a properly functioning interpreter).

Awesome, thanks Newt. It makes my interpreter do the categorical dual of a halt, but I thought it was a bug in my code as opposed to my thought process.

@newt

Yeah, that wouldn't be enough information. I, for one, have not the first idea what MM has done (other than write something in pseudo-code, which I'm supposing is different from "sudo" code).

Sorry for the ignorance but delighted to be informed. . .

@GM Palmer

What MM has done is create a new DFA (though he won't admit it himself -- apparently, he does not like the idea of an automaton).

The challenge that he has put to you people is to use this automaton to make is spit out an answer that we want -- decrement. The key is to find the correct group of numbers which will accomplish the goal.

@Anon,

Categorical dual of a halt -- infinite loop? (judging by your comment, assuming that it

wasyour comment).Also, get a nick.

newt --

So it's:

* here's some programming stuff -- if you're a programmer you know what I'm talking about -- perhaps it's quite interesting

* if you can figure it out, email me for a maybe prize

* maybe I'll post something less-confusing to the luddites next week

'zat bout right?

@GM Palmer

Change "programmer" to "programmer-who-engages-in-esoteric-exercises-about-computer-languages" and it seems about right.

Of course, it's pure mathematicians who are

reallygood at this sort of thing.*It's not that difficult a problem (speaking as a mathematician). It provided some nice two hours of entertainment. If you give me your email address, I can give you a hint. my email address is newt0311@gmail.com

* That's what I am -- a pure mathematician. As a general rule, all theoretical CS people and most economists are wannabe mathematicians who couldn't cut it among the pros. I probably shouldn't be this haughty because I may be joining them soon. Only time will tell.

@ G.M.

"As a general rule, all theoretical CS people and most economists are wannabe mathematicians who couldn't cut it among the pros."

Or people who were thinking about income. We routinely hire economists as consultants and expert witnesses for anywhere from $200-600 per hour. We have yet to hire a mathemetician.

@anon above RE: lawyer talk

oooooh it's a status seeking lawyer throwing his dick around. YOU HAVE SUUUUUUUCH A BIG PENIS. BIIIIIG PENIS.

and lol@your argument.

HAI GUISE, DEM DUR MATH PEOPLE DON'T GET HIRED AT MY BUMFUCK IDAHO AMBULANCE CHASING FOURTH TIER PRACTICE. THEREFORE, MATH PEOPLE DON'T GET PAID MUCH. HYUCK HYUCK.

@Anon,

Yes, but how many?

Most economists end up in universities and that is the expectation. If money is the desired goal, finance seems like a much better option to me.

So, just for complete clarification; this is just a somewhat entertaining math problem that you need to understand computer programming terminology to attempt? There is no broader significance?

As far as I can tell. To be sure, it is much more entertaining than many other math problems I have come across.

Now I know how my friend felt when I made the mistake of showing him a fascinating chess problem. Qg3!!

Get back to disparaging democracy.

newt0311,

I'm a mathematician as well. What kind of math do you study?

I haven't specialized much (I am still an undergraduate) but I am gravitating to groups and modules. Abstract Algebra basically.

It's not just a math problem. I think MM is proposing this as a "core language" for implementing other programming languages in. Your machine would implement the primitive "maxwells equations" (i.e. Nock), and then more practical languages would compile down into Nock for execution/to give them a semantics.

To those who have said this is just like Lisp: I think its a bit more interesting because MM gets away without any name binding (like if you use combinators) but also has data structures, and you can probably define a metacircular interpreter in it. I haven't seen that combination before, which is kind of fun.

I'm not clear on why this is not an automaton (it certainly looks like a state machine to me), or exactly what "foundational system software" is. The lambda calculus is certainly serving the functional programming community perfectly well as a basis of large systems (and even operating systems) - I'm not clear what benefits MM envisages from Nock adoption.

Not other programing languages, just his languages. I doubt many other compiler writers will care for nock.

@ anonymous trolling anon.

Or I suppose first anon's argument could be rephrased, CS Phds and Econ Phds have more options outside of academia, which results in option to make more $, compared to pure math Phds. I guess a reference to hiring an expert witness screams status-seeking pissing contest, but calling two entire groups of Phd-holders "wannabes" who couldn't cut it in math "as a general rule," doesn't? Personally, I'd be willing to bet that median salries of econ and CS phds are higher than median salaries of math phds. And $ aside, many probably just found econ or CS more interesting than pure math when selecting an educational path. It's pretty insulting and arrogant to call them a group of "wannabes" who "couldn't cut it among the pros."

@newt there are lots of econ phds in consulting companies and Ibanks, but an MBA is probably a more efficient way to get there.

Newt's comment about 'wannabe mathematicians' reminds me that J.P. Morgan, Sr. was educated in mathematics at Goettingen - when it was the premier university for the study of mathematics in the world. When young Pierpont left to join his father's business, his instructors told him he was making a great mistake; that if he stayed at Goettingen, he stood a good chance of becoming a professor.

@Michael S. and Anon,

1) I specifically did not include Business and Finance because they have another perfectly good explanation: money (as both have mentioned in so many words). I alluded to this myself when I stated when I responded to another anon post.

2) I don't (or at least didn't) think the expert witness claim "screams status-seeking pissing contest." I responded to it as normal argument.

3)

And $ aside, many probably just found econ or CS more interesting than pure math when selecting an educational path.This is a joke right? The reason I specifically singled out econ and theoretical CS is because these fields are in the middle of nowhere. To "enjoy" anything like modern day econ requires that a person enjoy math and/or enjoy analyzing politics and be able to tolerate much mathematics. Either way, pure mathematics and sociology (notwithstanding the sorry state of modern political science and sociology) are better options. The same thing applies to CS. If a person enjoys building things, ie. is of the engineering persuasion, they are much better off in not-so-theoretical CS often better known as software engineering. If they are on the math side, they are better off in pure math.

Universities would do very well to make theoretical CS a subfield of pure mathematics and Econ a subfield of applied sociology, in the same class as political science and friends.

4) This comment came in a footnote to a tertiary point in the post. Way to go on blowing an off-hand comment out of proportion.

This comment has been removed by the author.

@newt0311

Yes, with 0 1 3 it's Turing-equivalent, just like the lambda-calculus (exercise: encode application and SKI combinators in THAT). Turing equivalent does not mean usable. You'll have to construct such things as church numerals to express arithmetics in such a setting. 5 6 give you full arithmetics on a builtin type of natural numbers.

@josh

The significance of this post is that MM proposes a foundational model for computation as a fully well-specified minimalist mid-level pure functional applicative virtual machine. On top of that solid foundation, one could build a whole universe of computing.

@Max

I think you pinpoint the essentials of MM's proposal.

As the TUNES.org guy, I feel that the following things are missing elements from such a foundation:

(a) This foundation is lacking a linear logic fragment that could model resources, ownership, and interaction. In practice you'll need to extend your calculus, if only with a magic extension that makes input dynamically appear in some datastructure, in defiance of the otherwise pure paradigm (e.g. like Haskell does with its magic I/O Monad). And since they can't be expressed "intrinsically", these extensions may wreak havoc in the otherwise nice base model.

(b) MM's model is high-level enough to be a universal calculus, largely independent from the underlying machine: acyclic graphs of bignums. That's good. However, it is also low-level enough that you can't use it directly, but must build your own abstractions on top of it. Yet, it isn't such a good low-level paradigm because it supposes an unbounded implicit execution stack in its evaluator, doesn't have easily-optimized linear logic (again), etc. And so, if you're going to implement your language in this model, the first thing you'll want is to build some kind of SECD machine monad on top of it. And then, what value the original model bring you? It's just a middleman between what you care about (the high-level computation) and the real machine. With enough magic in the implementation, you could bring down the runtime cost of that middleman, but why bother with the middle-man at all?

(c) Maybe the point is that pure computations matter, or that well-defined semantics matter, and that we want to solid foundations for computation. The point is well-taken. Still, I think that a standardized virtual-machine execution model for the pure aspect of computation is only a small part of the answer. Other parts include how to deal with interaction without abandoning the model and losing semantic control (see a above), but also what kind of infrastructure do you offer for adding layers to your building (see d below)? If these two aspects (interaction, extension) are not part of your system but something outside, then the real system is whatever bigger system does handle these aspects, and if this bigger system is an ad-hoc collection of tools, the attempt to bring order to a subsystem may have failed to bring order to the overall system and may even have increased disorder.

(d) When you build a universe of computing, the structure of morphisms is more interesting than the arbitrary foundation: the way you allow to express one system of high-level meanings someone cares about in another system, how you implement one system in the other, how you share the code and data of one in the other, etc. So far, the only people who try to build a universe with a systematic such structure are the PLT Scheme team with their module languages. There are a few smaller groups of researchers who think about such structure, but don't seem to have the same knack at universe-building: rewrite logic in Maude has a decent story; Monads and similar things in Haskell provide insight as to how to compose stories; various Scheme macro systems, ML staged compilation techniques, etc., also count somewhat.

(e) Previous successful attempts at building universes of diverse without a clear structure of morphisms, but instead a virtual machine as a foundation, include POP-11, .NET, JVM. They are not designed to neatly distinguish a pure monotonic subset; but they do provide a lot of practically useful functionality, a standard way to pass around objects and invoke behavior. While these approach haven't been fully satisfactory so far, they still have had a great success. I would agree with MM that a better approach is possible, but I'm curious how MM would argue why this is better, and how he intends to displace it.

I suppose we could make a vague analogy with the political content of the blog, i.e. bringing order to the (political or computing) world.

The important point that MM makes is that order matters (i.e., well-defined semantics), truth matters (i.e. pure monotonic logic).

The points that I think his plan fails to explicitly address are a way to manage resources (property rights, linear logic), and a way for actors to exchange services in terms that are meaningful to them (contracts enforced by civil law, language morphisms enforced by the linker).

Also, while this blog has a good story about what is rotten in the current political institutions, I'm curious how MM would articulate something similar for our current computing institutions. Last but not least, I'd like to see a clear plan to get there from here (i.e. how to architect the process of building this new universe).

@Fare

My mistake! You are right in that the arithmetic operators are unnecessary -- church numbers can handle it, badly as it may be.

I am still not sure that we could do without *[a [b c] d] but that would take more work. Data structures, I guess, can be calculated dynamically in a and b for storage...

a) Yes. I can imagine a few easy ways of doing so with MMs calculus which still preserve most of its simplicity.

b) Thats what I thought. According to MM, nock can actually be reasonably optimized through pattern matching though I am not yet convinced by his argument.

c) Always a problem but indeed much more of a problem with something like nock.

d & e) Yes, a better approach than a VM spec is possible but I don't think Nock is it.

@newt0311

Without the [a [b c] d] rule, you'd need another numbered operator that does essentially the same. Think of it as a variant of the Schoenfinkel combinator.

@Fare

Ah. You are correct. Foolish of me to forget SKI here.

What do you guys think of Conal Elliott's recent post "Can functional programming be liberated from the von Neumann paradigm?"

http://conal.net/blog/posts/can-functional-programming-be-liberated-from-the-von-neumann-paradigm/

about math:

Newt: my old HS math teacher (perfect SATs, perfect grades at Princeton) majored in economics and not math (in the 1980s) because she liked mathematics and not theory. Then she came back home to teach high school because she liked playing with calculus.

For whippersnappers, this should provide some useful context for the latest post.

This comment has been removed by the author.

Dammit!

a) I was expecting a long read-and-forget MM rant that would take no more time than what is required for reading it and maybe looking up a few references. Instead, I got something that distracted me for the better half of the day from productive work.

b) Thiblo cannot handle this. Yet.

A substitute for MM's usual political fare, from the guy who previously extended my Straussian interpretation of neocameralism.

Hey Jocks, get a load of the NERDS! Nerrrrd!

Although really I'm just jealous of those whose skills allow them to actually produce something of value for society, unlike thoroughly cathedralized academic economist's such as myself.

Solution submitted. It was fun.

@Daniel A.

Could you send me yours (and I can send you mine). I just want to compare the different approaches.

My email: newt0311@gmail.com

When I coded up my ugly-ugly interpreter (in java), I had no idea how Nock worked. Now that I have learned to use it, I could, of course, write a much better interpreter that would not stack-overflow on an infinite loop such as [[3 [0 1] 0 1] 3 [0 1] 0 1].

However, in order to make Nock practical, I believe that it should be made more esoteric: to hell with integer atoms, make atoms bits! The selector would then take a string of bits.

If one would implement such a machine in hardware, it would have the added benefit of being easily extensible by adding more hardware, even during operation. The current Nock leaves integer representation to the imagination of the implementer.

@Daniel A.

You are welcome to choose any representation you would like though IMO one based on bit markers seems best suited.

"Today he is Senior Fellow at Hewlett-Packard Labs and president of Viewpoints Research Institute, a nonprofit organization whose goal is to change how children are educated by creating a sample curriculum with supporting media for teaching math and science. This curriculum will use Squeak as its media, and will be highly interactive and constructive. Kay’s deep interests in children and education have been the catalysts for many of his ideas over the years. "

Dear Mencicus: Please PM Mr Kay at once and inform him of his noxious Progresivist Utopianism. Doesn't he realize that smart kids will always be smart, and dumb kids will always be dumb (and disproportionately negroid?). Another fuzzy-head foolishly trying to tinker with the Great Chain of Being, I see. Please at least try, so you can sleep at night.

Qg3!!,

I am so happy to see someone mention the 'Showers of Gold' game in this thread! Thank you very much.

- Anonymous Twit

Call-by-need or call-by-value?

Fun. My Python interpreter came out at 38 lines for the core, and double that including parser, tostring, and trace output. It's properly tail-recursive and, since it automatically uses Python's bignums, should handle all practical nouns.

It reminds me a bit of my own language, Io, which I designed a long time ago. I just blogged about that a bit here.

Consider moving to Mexico, Thailand, Argentina, Uruguay. Babysitters are a lot less expensive there and private schools are everywhere. Jewish community well in evidence in all of them, except Thailand, of course. You can program from anywhere, why live in the US?

By Jove! I fail to see what makes Nock not an esolang, or indeed what Maxwell has to do with any of this, poor fellow.

I also take exception with the claim that a Nock interpreter should fit in a page in *any* programming language. It betrays an acute shortage of imagination w.r.t. programming languages. And pages.

Post a Comment

Subscribe to Post Comments [Atom]

<< Home