# Comments on Trade-Offs in Systems of Notation/Programming Languages

## cpcogan — 2007-01-07 22:40:46

    It's the LAW:

    Whenever a programming language is developed that eliminates the need

    for some conventional programming construct, that programming language

    will have partially compensating complexity in some other aspect of

    its use, thus somewhat reducing the value of the new language.

    In the case of old-time Lisp, for example, we get a simplification of

    syntax at the cost of a proliferation of parenthetical expressions

    that can get pretty confusing (and further complexities from its

    applicative nature). In older Forths (if not newer ones), we get stack

    manipulation activities, two-step retrieval of variable values (where

    the address of a value is first pushed in one step and then used to

    retrieve the actual data in another step).

    The real trick is to find those systems of notation that, for their

    purposes, offer the best choices in what is given up and what is

    gained by each choice. This is made complicated by the fact that the

    different aspects of a system of notation have to fit together, with

    the result that a way of adding a feature to one system may not work

    in another.

    I know of an incredibly elegant system of notation (G. Spencer-Brown's

    Calculus of Indications) that gains enormously in important ways by

    "magically" combining inversion of value (in a two-valued system, like

    Boolean algebra (see explanatory note at end of this post)) with

    expression-containment (like parentheses in many conventional systems

    of notation). But the cost of this notation is that it is

    two-dimensional, which makes it impossible to just type it into a word

    processor (though it would be relatively easy to make an editor

    (similar to MathCad's) that would automatically translate parentheses

    or brackets into this two-dimensional representation). The advantage

    of the two-dimensional representation is a major improvement in

    readability, and the major advantage of the notation functionally is

    that it makes basic logical "calculations" mostly trivially easy

    (allowing many expressions to be "collapsed" into their simplest form

    almost instantly). (Unfortunately, Spencer-Brown's book on his

    calculus is marred by bad philosophizing and by having most of the

    book written in a compact but cryptic style, so it takes a while to

    "get" what he's done and why it's of value, but there are

    more-accessible introductions now available online.)

    Joy rests on a re-conceptualization of functional programming. I think

    the key may be seeing how functional composition can be mapped so

    perfectly to concatenation, as long as we have a means of holding

    execution of code in abeyance (via quoting) until something following

    it is ready to execute it (or not). I think I mentioned in a much

    earlier post (in 2004) that I had come up with the idea of using

    bracketed code in this way in the 1970's but almost COMPLETELY missed

    most of the importance of it, because I was still thinking of the

    language I was designing as a variant of Forth with a stricter

    adherence to an "RPN" style (no explicit loops, etc.). My idea for the

    While "loop" was like this:

          [ <condition expression> ; <code to be repeated> ] While

    I was so close, yet so far away! If you look at this as just a

    modification of Forth (as I did), you can see why I missed what

    Manfred saw. In my view, the quoted code would not have been put on

    the stack (the brackets and the included code were not treated as a

    function in their own right, in other words), but would have been

    otherwise buffered until the While "word" (as it would be called in

    Forth) was encountered and executed (in keeping with the ingrained

    thinking of conventional programming languages, I think I even thought

    of "While" as a core language construct rather than as a function in

    its own right).

    Even when I read Backus's now-famous paper on functional programming

    (1977, I think), I *still* didn't see the potential. In my defense,

    most of my non-work time then was taken up with my interest in

    philosophy (which is still my main intellectual interest in life) but

    I feel a pang of lost-opportunity-regret at not having seen what

    Manfred saw. Also, I don't think even Backus saw the potential for

    composition by concatenation. (Or did he? And, did he also miss the

    value of treating *everything* (including literals) as functions? I

    don't remember. I remember his ideas as being more along the lines of

    APL operator notation (where operators are used to extend or modify

    the application of functions), but I'm not sure if this is correct.)

    At any rate, I see the light NOW, thanks to Joy.

     ===================================

    [Note on Spencer-Brown's calculus of indications, mostly for those

    interested in formal logic systems, though you may find it interesting

    if you are only interested in good systems of notation (and what

    serious programming-language student isn't?):

    I mentioned in the text above that Spencer-Brown's calculus used only

    a single symbol (not counting the equal sign) for both grouping and

    negation or value-inversion. The reason the same representation can be

    used as both a boundary marker and as value-inversion (or negation) is

    that a containment representation marks the boundary between what's

    inside (X, let's say) and what's outside (not-X, of course), so the

    idea of negation (or value-inversion) is implicit in any boundary

    indicator. There is even a type of "logic" called boundary logic

    (apparently developed to some extent by Charles Pierce, though I don't

    know the details yet). Spencer-Brown's calculus is an example of this

    type of logic (Venn diagrams are another, less formalized and far less

    useful, example). If we think of angle-brackets as indicating

    negation, and juxtaposition as representing a logical OR, and sequence

    on the page as irrelevant, then we can represent material implication by:

           < p > q          (not-p or q)

    or:

            q < p >          (logically identical to the expression above)

    Logical AND is

            < < p > < q > >  (not (not-p OR not-q) )

    (the complexity of AND is not as much of a problem as you might expect)

    Spencer-Brown's calculus uses a single symbol where I have used pairs

    of angle-brackets. His symbol has a horizontal component that extends

    over the items to be contained/negated, and is terminated by a

    vertical down-stroke (like an upside down capital L with the

    horizontal part being extended backward over all it encompasses). You

    can find one introduction to boundary logic at:

           http://www.boundarymath.org/papers/BLogic-intro.pdf

    but there are other introductions to it and to Spencer-Brown's

    calculus (sadly, "Laws of Form" is apparently no longer in print, and

    it's only available used at astonishing prices (at Amazon.com: $51.84

    (for a small paperback, at that), and one other seller want's $120.00

    (!) -- I'm glad I already have two copies because, if I need to, I can

    sell them and retire on the proceeds ;-) )).

    Interpreted as a Boolean algebra, Brown's calculus produces

    expressions that have the logical reductionism of using a

    Sheffer-stroke system but without the enormous proliferation of the

    stroke symbol and conceptually redundant references to variables that

    comes with the Sheffer-stroke system (at least until other connectives

    are defined -- which increases complexity of calculation). This is

    because disjunction is the default logical connective in a

    Spencer-Brown Boolean algebra, so the single symbol doesn't have to be

    an operator between other symbols to have meaning (as the

    Sheffer-stroke does, because a Sheffer-stroke is basically an XOR

    symbol, if I remember correctly). The economy of Spencer-Brown's

    calculus allows us to continue using just the single "cross" long

    after we would have been forced into defining new symbols in almost

    any other system.

    There is also a brief Wikipedia article on Spencer-Brown, which gives

    a little information about him (including the strong hints of

    Spencer-Brown's eccentricities). He was one of those people who was

    part genius and part crackpot (in my view). Fortunately, his book,

    "Laws of Form," *mostly* isolates part of his genius from what I

    regard as his crackpot tendencies (though he has been criticized for

    acknowledging that a proof that he had devised was unsound, which

    seems a strange basis for a criticism, to me, since admission of

    mistakes is not characteristic of true crackpots).

    One final note that may possibly encourage the reader to look at

    Spencer-Brown's system: He shows how to eliminate the apparent need

    for a theory of types as a means of avoiding the paradoxes of logic

    (e.g., the set-inclusion paradoxes and the liar's paradox, etc.). My

    own more-philosophical way of dealing with the paradoxes (along with

    formal undecidability and the incompleteness of formal systems) was

    inspired by Spencer-Brown's observations on the genuinely analogical

    relationship between imaginary numbers in ordinary mathematics and

    "imaginary" truth values in logics (they are genuinely analogical

    because the analogical features are not accidental parallel but arise

    from having to deal with situations where an expression or equation

    requires something that is not possible without the introduction of

    imaginaries).

## William Tanksley, Jr — 2007-01-10 17:18:37

    I'm not going to get the time for a while to address this properly and

    in full, but I think it provides (and the other documents posted

    provide) really valuable instigations to discussion on this list.

    Thank you.

    cpcogan <ccogan@...> wrote:

     > It's the LAW:

    > Whenever a programming language is developed that eliminates the need

    > for some conventional programming construct, that programming language

    > will have partially compensating complexity in some other aspect of

    > its use, thus somewhat reducing the value of the new language.

     That's quite pragmatic and reasonable.

     > In the case of old-time Lisp, for example, we get a simplification of

    > syntax at the cost of a proliferation of parenthetical expressions

    > that can get pretty confusing (and further complexities from its

    > applicative nature). In older Forths (if not newer ones), we get stack

    > manipulation activities, two-step retrieval of variable values (where

    > the address of a value is first pushed in one step and then used to

    > retrieve the actual data in another step).

     Careful. The two-step retrieval isn't an attribute of Forth's

    notation; it's a result of the fact that the only provision for

    variables was naming a chunk of memory inside the dictionary. It's

    easy to code alternate implementations of global variables (a common

    name is VALUE), and the ANSI standard makes it possible to code

    locals.

    But otherwise, great examples.

    The Forth example hits this discussion group on the head. Pardon the

    painfully mixed clich\'e.

    The stack shuffling problem is a fundamental attribute of stack-based

    concatenative languages; in a more general sense, the problem is that

    dataflow languages must explicitly express their dataflow, while

    lambda-based languages can keep dataflow hidden.

     > The real trick is to find those systems of notation that, for their

    > purposes, offer the best choices in what is given up and what is

    > gained by each choice. This is made complicated by the fact that the

    > different aspects of a system of notation have to fit together, with

    > the result that a way of adding a feature to one system may not work

    > in another.

     I can't delete this... I have to add "<aol>Me too!</aol>".

    It's made still more complex by the fact that in general you're not

    usually "giving up" a pure quality that the other language possesses;

    rather, you're reducing a quantity of one thing in return for a

    quantity of a qualitatively different thing. And, of course, you're

    almost never trading one for one; usually there are several things to

    give up and/or gain.

     > almost instantly). (Unfortunately, Spencer-Brown's book on his

    > calculus is marred by bad philosophizing and by having most of the

    > book written in a compact but cryptic style, so it takes a while to

    > "get" what he's done and why it's of value, but there are

    > more-accessible introductions now available online.)

     Where would you recommend going for an intro? Stevan's page on the

    subject was interesting (although "compact but cryptic"), but I want

    more. The PDF you linked to seems like a decent conceptual start, but

    lacks depth and application (as far as I could see).

     > bracketed code in this way in the 1970's but almost COMPLETELY missed

    > most of the importance of it, because I was still thinking of the

    > language I was designing as a variant of Forth with a stricter

    > adherence to an "RPN" style (no explicit loops, etc.).

     I made a similar error in my understanding of Forth as well (although

    mine wasn't as creative); it's easy to do when you think of Forth as

    "postfix" rather than dataflow RPN.

     >        http://www.boundarymath.org/papers/BLogic-intro.pdf

     Noted, skimmed, and saved.

     > (e.g., the set-inclusion paradoxes and the liar's paradox, etc.). My

    > own more-philosophical way of dealing with the paradoxes (along with

     We may have to take this particular part offline, unless you've got a

    webpage... But I want to hear more. Imaginary truth values... Very

    interesting.

    -Billy