Index  Comments

Under review is this document.

As I continue writing reviews, I feel concern over pacing, and so will begin to review these shorter documents when I feel the want. Having recently read this, I can recommend it. Amusingly, it isn't the lightest read I've reviewed, reading it over three weeks. My third review took but one weekend.

The document titularly describes a method of programming which is divorced from what is typical. It isn't nearly so alien as one may expect, and programmers with APL experience will immediately notice the general idea, although what Backus calls functional programming goes further than APL could.

He begins by clarifying ideas of aspects of programming models, describing several most readers will recognize, and then introduces his style by contrast. Even if one ultimately disagrees with what he suggests, the paper is a valuable read purely due to the clarity of thought it should instill. Then he clarifies his model with concise mathematical definitions which shouldn't be merely scanned over.

The algebra of this system is introduced next, with several laws provided. Due to my casual reading and minor confusion over some finer details of the notation, I'd issues in the law I.11. I was able to prove part of it, and wondered if I'd proven the entirety of it, but a proof was stated following immediately thereafter, and so I learned I'd only proven part of what was stated. After this, given are theorems presenting alternative forms of programs more amenable to certain analysis. His system has a simple reduction rule, single parameter functions, a lack of inconsistency and state, notation suited to the problems, and a meaningful bottom value for what would otherwise be forms somewhat erroneous; importantly, it instills the sense of easy program manipulation, as if writing compilers.

Of particular interest is the construction functional form, which satisfies a want I'm left with by other languages: for a value to be used in multiple contexts without a name. Now knowing this, I see similarities with mine own ideas for satisfying this want, and find it poor that it's not met by what's currently available to me, causing unnecessary hardships and attempts to use but one context.

The final third of the document describes Formal Systems for Functional Programming that use and extend the functional programming system described. It uses a system of cells and symbols that will be familiar to any Lisp programmer, and this was a major shift in the reading I could easily handle.

The lone most novel idea in the paper, in mine eyes, is the Applicative State Transition system, which details the basics of a computing system using the previous systems described, in which events arrive and result in processing, but with state updating only at the highest level. I wondered what such a system would be like and how it could be implemented, and I know of two examples I'll detail.

Firstly, Urbit is an example of such an AST system, in that it receives events which command it, and produce the next state; any failure can simply be discarded without changing the state. Where Urbit deviates from the document is in its complete lack of compelling foundation. Nock is nothing at all like the style described by Backus, being practically useless and uninteresting; it lacks primitives that are useful, has a dearth of types, and lacks reasonable transition to an efficient system; Hoon is needlessly confusing and, again, rather uninteresting, being so opaque I didn't bother with fully understanding it. Knowing this, it's queer Urbit supposedly had over a decade of thought set to it.

Secondly, I realized that reimplementation of mine MMC was unintentionally structured as such an AST system. Commands are issued by a disconnected primary loop and perform work to collect any required information, then going on without further guidance, to return new information to be instated by the machinery, or to more deeply affect that main state directly. If a command is aborted, it's without effect, and the MMC continues without acknowledging it. This example reassured me of the document's practicality, and the validity of mine improved design, albeit the true implementation not so clean.

There's, of course, other value in this document I've not acknowledged. It will affect one's ideas.