----- Original Message -----
From: "cpcogan" <ccogan@...>
To: <concatenative@yahoogroups.com>
Sent: Sunday, January 07, 2007 5:40 PM
Subject: [stack] Comments on Trade-Offs in Systems of Notation/Programming Languages

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.)

a couple of points about spencer-brown and his notation.

first, the notation itself is a typographic variant of one
devised a century earlier by charles sanders peirce, the
so-called "existential graphs". a second notation, in which
juxtaposition denotes disjunction, the so-called "entitative
graphs", was also described by peirce.

these notations aren't truly two-dimensional. that is,

AB

and

A
B

(A and B in any relative orientation) have the same meanings,
viz. assertion of both A and B. similarly, zero or more
assertions under a "cut" (for peirce, a circle, for GSB an
open angle) denotes the negation of the conjunction of the
assertions, but the relative orientation of the enclosed
assertions carries no meaning. (hilbert and ackermann use
a bar drawn above the section of the formula to be negated.)

these notations aren't truly two-dimensional because, as you
point out, formulas can be re-written with parentheses:

((A B) C) etc.

i describe a truly two-dimensional notation for elementary
logic here:

http://nsl.com/papers/tl.htm

in box notation

AB

denotes conjunction, and

A
B

denotes disjuction. A formula F begins as a disjunction-free
formula, and then two rules mechanically generate the conjunctional
normal form for F as a two-dimensional array of atoms and negated
atoms. (note: this page looks right on some browsers, not on
others. i don't know why. any ideas?) i used this notation to
teach elementary logic some years ago, and i found it particularly
"blackboard friendly" -- chalk in one hand, eraser in the other,
you could zip through a proof pretty quickly. my paper contains
the code for generating proof-trees.

another point about spencer-brown's notation: peirce extended
his graphical notation to quantification theory and modal logic,
at the cost of ever-more-abstruse graphic devices. the "beta"
graphs use a "line of identity" to connect the argument positions
of predicates, so that e.g. Exists x(Fx & Gx) becomes

F ------ G

written in any orientation. (the single axiom of the beta graphs
is

--

i.e. "something exists.")

the argentinian biologist and buddhist theoretician varela
developed several extensions of spencer-brown's notation in
which imaginary values are first-class. the work is contained
in a book called "principles of biological autonomy", and is
particularly difficult to get hold of. the work also predates
varela's work with warren mcculloch's sometime research partner
maturana ("what the frog's eye tells the frog's brain.") and
by the way, you might want to look at the very strange notation
devised by mcculloch and pitts for truth-functional logic,
contained in the collection "embodiments of mind". (mcculloch
was also a fine amateur poet.)

j.j. zeman and don roberts have done some interesting exegetical
work in this area, and work is still being done on this aspect
of peirce's logic. the "gamma" graphs are really wild. peirce
adapts the terminology of classical heraldry to force concepts
of modality and intensionality into the graphs. it's a fascinating
mess!

texas a&m university seems to be the current hot-spot for research
on peirce's logical systems. deriving from hans herzberger's
papers on peirce's theory of relations, the philosopher robert
burch published a wonderfully interesting book, "a peircean
reduction thesis" some years ago. (the thesis is that triadic
relations can't be reduced to dyadic relations.) you might
also want to look at the mammoth collection of papers on peirce's
logic edited by don roberts.

the brilliant knot-theorist lou kauffman is the one first-class
mathematician i know of who takes spencer-brown's work seriously.
i have some links on my website: http://www.nsl.com/links.html.

somewhere on the net, at some point, there were some hilarious
remarks by john horton conway recalling his one encounter with
spencer-brown. these are worth searching out.

finally, there is jeffrey james' master's thesis on "spatial
forms for number". i can't say i've read or understood this
amazing production, but i suspect that you will enjoy it. and
it will probably make billy nuts!

http://www.rgshoup.com/lof/doc/jjames-thesis.txt

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).

Re: [stack] Comments on Trade-Offs in Systems of Notation/Programming Languages

stevan apter — 2007-01-08 15:41:55

William Tanksley, Jr — 2007-01-08 16:21:41

stevan apter — 2007-01-10 22:56:54

stevan apter — 2007-01-11 12:38:17