A Review of ``Can Programming Be Liberated from the von Neumann Style?'' by John Backus

Information concerning the document under review may be found in that menu linking to 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.
.