http://www.urbit.org/2013/08/22/Chapter-2-nock.html

Why is Nock interesting? Just as another member of the menagerie of minimalist languages, with Turing machines and lambda calculus and SKI combinatory calculus and Graham’s Roots of Lisp lisp and Shen’s KL and asm.js and Haskell GHC Core and various other small languages and VMs (i don’t claim to know anything about most of those).

With Turing machines, you feel like the big thing is changing the state of memory locations; but with lambda calculus and SKI combinator and Nock, you are reducing expressions.

With lambda calculus, you feel like the big thing is substitution; but with Nock (and presumably with SKI combinators, i don’t know them that well), it doesn’t feel quite like substitution is the main thing.

Although Nock is functional, the first argument in the main Nock expressions (e.g. the ‘a’ in the expressions of the form (a SMALL_INTEGER b)) can be interpreted as a state, providing an intuitive bridge between the lambda-calculus-ish world of expression reduction and the Turing machine world of state mutation.

Unlike both lambda calculus and SKI combinators, there is a sort of ‘assembly language programming’ feel to Nock. It’s not quite as minimal as lambda calculus or SKI combinators but for the price of a little bit of extra initial complexity, you get a lot of bang for your buck in terms of more intuitive programming. And you might even think it’s more minimal than lambda calculus if you count the complexity of rules like alpha-conversion against lambda calculus.

Unlike both lambda calculus and SKI combinators, Nock gives you integers and lists (trees) as primitive data types, and HEAD and TAIL and GET-THE-NTH-LIST-ELEMENT and SUCCESSOR and ISEQUAL as primitive operations. Compare to e.g. lambda calculus where you don’t have the complexity cost of having to include integers in the language definition, but then when you want to program arithmetic you have to use Church numerals. Similarly, with the simpler Turing machine models, you just get a bunch of basic commands for moving a machine head on a tape and making and erasing binary marks, and you have to build arithmetic and lists out of that.

So, it’s more ‘full-featured’ than lambda calculus, SKI combinators, or Turing machines. But it’s much simpler than most VMs and programming languages, and is based on expression reduction, rather than variable or memory mutation.

Further notes: http://bayleshanks.com/notes-computer-programming-programmingLanguageDesign-prosAndCons-nock

## Recent Comments