[Richard Suchenwirth] 2004-12-04 - John Backus turned 80 these days. 
For creating FORTRAN and the BNF style of language description, he
received the ACM Turing Award in 1977. In his Turing Award lecture [http://www.stanford.edu/class/cs242/readings/backus.pdf],

''Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs. (Comm. ACM 21.8, Aug. 1978, 613-641)''

he developed an amazing framework for [functional programming], from
theoretical foundations to implementation hints, e.g. for installation,
user privileges, and system self-protection. 
In a nutshell, his FP system comprises
   * a set O of objects (atoms or sequences)
   * a set F of functions that map objects into objects (f : O |-> O}
   * an operation, ''application'' (very roughly, [eval])
   * a set FF of functional forms, used to combine functions or objects to form new functions in F
   * a set D of definitions that map names to functions in F

I'm far from having digested it all, but like so often, interesting reading 
prompts me to do Tcl experiments, especially on weekends. 
I started with Backus' first Functional Program example,
 Def Innerproduct = (Insert +) o (ApplyToAll x) o Transpose
and wanted to bring it to life - slightly adapted to Tcl style,
especially by replacing the infix operator "o" with a Polish prefix style:
 Def Innerproduct = {o {Insert +} {ApplyToAll *} Transpose}
Unlike [proc]s or [lambda]s, more like [APL] or [RPN], this definition needs 
no variables - it declares (from right to left) what to do with the input;
the result of each step is the input for the next step (to the left of
it). In an RPN language, the example might look like this:
 /Innerproduct {Transpose * swap ApplyToAll + swap Insert} def
which has the advantage that execution goes from left to right, but
requires some stack awareness (and some swaps to set the stack right ;^)

Implementing '''Def''', I took an easy route by just creating a
proc that adds an argument and leaves it to the
"functional" to do the right thing (with some quoting heaven :-)
 proc Def {name = functional} {
    proc $name x "\[$functional\] \$x"
 }
For [functional composition], where, say for two functions f and g,
 [{o f g} $x] == [f [g $x]]
again a [proc] is created that does the bracket nesting:
 proc o args {
    set body return
    foreach f $args {append body " \[$f"}
    set name [info level 0]
    proc $name x "$body \$x [string repeat \] [llength $args]]"
    set name
 }
Why Backus used '''Transpose''' on the input, wasn't first clear
to me, but as he (like we Tclers) represents a matrix as a list of rows,
which are again lists (also known as vectors), it later made much sense
to me. This code for [transposing a matrix] uses the fact that variable names 
can be any string, including those that look like integers, so the column
contents are collected into variables named 0 1 2 ... and finally turned
into the result list:
 proc Transpose matrix {
    set cols [iota [llength [lindex $matrix 0]]]
    foreach row $matrix {
        foreach element $row col $cols {
            lappend $col $element
        }
    }
    set res {}
    foreach col $cols {lappend res [set $col]}
    set res
 }
An [integer range generator] produces the variable names, e.g
 iota 3 => {0 1 2}
 proc iota n {
    set res {}
    for {set i 0} {$i<$n} {incr i} {lappend res $i}
    set res
 }
 #-- This "functional form" is mostly called [map] in more recent FP:
 proc ApplyToAll {f list} {
    set res {}
    foreach element $list {lappend res [$f $element]}
    set res
 }
...and '''Insert''' is better known as '''fold''', I suppose. 
My oversimple implementation assumes that the operator is one that [expr]
understands:
 proc Insert {op arguments} {expr [join $arguments $op]}
 
#-- Prefix multiplication comes as a special case of this:
 interp alias {} * {} Insert *

#-- Now to try out the whole thing:
 Def Innerproduct = {o {Insert +} {ApplyToAll *} Transpose}
 puts [Innerproduct {{1 2 3} {6 5 4}}]

which returns 28 just as Dr. Backus ordered (= 1*6 + 2*5 + 3*4). Ah, the
joys of weekend Tcl'ing... - and belatedly, Happy Birthday, John! :)

Another example, cooked up by myself this time, computes the average of
a list. For this we need to implement the '''construction''' operator,
which is sort of inverse mapping - while mapping a function over a
sequence of inputs produces a sequence of outputs of that function
applied to each input, Backus' construction maps a sequence of
functions over one input to produce a sequence of results of each
function to that input, e.g.
 [f,g](x) == <f(x),g(x)>
Of course I can't use circumfix brackets as operator name, 
so let's call it ''constr'':
 proc constr args {
    set functions [lrange $args 0 end-1]
    set x [lindex $args end]
    set res {}
    foreach f $functions {lappend res [eval $f [list $x]]}
    set res
 }
 #-- Testing:
 Def mean = {o {Insert /} {constr {Insert +} llength}}
 puts [mean {1 2 3 4 5}]

which returns correctly 3. However, as integer division 
takes place, it would be better to make that
 proc double x {expr {double($x)}}

 Def mean    = {o {Insert /} {constr {Insert +} dlength}}
 Def dlength = {o double llength}
 
 puts [mean {1 2 3 4}]

giving the correct result 2.5. However, the auxiliary definition
for ''dlength'' cannot be inlined into the definition of ''mean'' - so
this needs more work... But this version, that maps ''double'' first, works:

 Def mean = {o {Insert /} {constr {Insert +} llength} {ApplyToAll double}}

One more experiment, just to get the feel:
 Def hypot  = {o sqrt {Insert +} {ApplyToAll square}}
 Def square = {o {Insert *} {constr id id}}

 proc sqrt x {expr {sqrt($x)}}
 proc id x   {set x}

 puts [hypot {3 4}]
 
which gives 5.0. Compared to an RPN language, ''hypot'' would be
 /hypot {dup * swap dup * + sqrt} def
which is shorter and simpler, but meddles more directly with the stack.

An important functional form is the conditional, which at Backus looks
like
 p1 -> f; p2 -> g; h
meaning, translated to Tcl,
 if {[p1 $x]} then {f $x} elseif {[p2 $x]} then {g $x} else {h $x}
Let's try that, rewritten Polish-ly to:
 cond p1 f p2 g h
 proc cond args {
    set body ""
    foreach {condition function} [lrange $args 0 end-1] {
        append body "if {\[$condition \$x\]} {$function \$x} else"
    }
    append body " {[lindex $args end] \$x}"
    set name [info level 0]
    proc $name x $body
    set name
 }
 #-- Testing, with [K] in another role as Konstant function :)
 Def abs = {cond {> 0} -- id}

 proc > {a b} {expr {$a>$b}}
 proc < {a b} {expr {$a<$b}}
 proc -- x {expr -$x}
 puts [abs -42],[abs 0],[abs 42]
 
 Def sgn = {cond {< 0} {K 1} {> 0} {K -1} {K 0}}
 proc K {a b} {set a}

 puts [sgn 42]/[sgn 0]/[sgn -42]
 
 #--Another famous toy example, reading a file's contents:
 Def readfile = {o 1 {constr read close} open}
 #--where Backus' '''selector''' (named just as integer) is here:
 proc 1 x {lindex $x 0}

----

[IL]: I just started reading Backus's paper last night, and it hurts!  I'd envisioned a similar alternative to modern languages a while ago; except my ideas which i though revolutionary had been documented in 1978.  I see a lot of similarities between unix philosophy and Backus's core premise (summarized poorly by myself here): modern languages and tools need to angle towards simpler interfaces, not bloated systems of apis.  

I think even in his examples perhaps his functional forms are still too basic, though I like some ideas, like his sequences, which like you mention, are very similar to tcl's treatment of lists.  
The introduction mentions he was tasked with developing a language around these ideas, 
what happened to it?

[RS]: The first implementation was simply calls "FP"  ([http://en.wikipedia.org/wiki/FP_programming_language]). From 1989 on, there was a successor "FL" ([http://en.wikipedia.org/wiki/FL_programming_language]). The latest chip off that tree seems to be "NGL" ([http://en.wikipedia.org/wiki/NGL_programming_language]).

[NEM]: The style of programming by composing functions, without mentioning any variables, 
is sometimes referred to as "Point Free Style". A discussion at [http://lambda-the-ultimate.org/classic/message7365.html] has some links to material of related interest. Incidentally, does anyone know where this use of the term "point" to mean argument/name/variable comes from? e.g. "point-free", "fixpoint" (in relation to the Y-combinator) etc. 
-- [RS] 2009-06-04: http://haskell.org/haskellwiki/Pointfree discusses the term.

[IL]: why work when you can research fascinating languages? :)  Following the wiki links, 
the J language also appears to be a member in the philosophy, and according to the limited propaganda on the site enjoys appreciation at the least, as well as a 64 bit implementation! "J" ([http://www.jsoftware.com/])
----
See also [Tacit programming] for another chapter to this story... e.g.
 Def mean = fork /. sum llength

----
IL, what is the difference between an interface and an API? Is an API not an interface? -Moritz

Moritz, sorry, bad choice of terms. I guess I meant flexible and expressive language design vs. a more traditional approach with a look that resembles the look of C++, and but has a very large runtime download... (but I'm not naming names!)
----
[gold]10/10/2020, added appendix, but above text and code unchanged.
----
 
----
*** References ***
----
   * [eval] &  [integer range generator]
   * [Tacit programming] 
   * [A little math language revisited]
   * [Playing with Recursion] by [RS]
   * [Functional Programming]
   * see [sed] & [awk] & [expr] & [regexp]
   * [recursion]
   * [func]
   * John McCarthy: A basis for a mathematical theory of computation, in: 
   * Computer Programming and Formal Systems.
   * P.Braffort, D.Hirschberg (ed.), Amsterdam:North Holland 1963,
   * several versions, archived pdf [http://www-formal.stanford.edu/jmc/basis1.pdf]
   * McCarthy’s LISP and Basis for Theory of Computation, archived pdf[https://hapoc2015.sciencesconf.org/conference/hapoc2015/pages/Dai.pdf]
   * en.wikipedia.org search on <John McCarthy computer> [https://en.wikipedia.org/wiki/John_McCarthy_(computer_scientist)]
   * John McCarthy at Stanford web site, archived [https://web.archive.org/web/20131011125002/http://www-formal.stanford.edu/jmc/]
   * Towards a Mathematical Science of Computation, J. McCarthy,
   * Computer Science Department,Stanford University, archived pdf [https://web.archive.org/web/20130319040125/http://www-formal.stanford.edu/jmc/towards.pdf]
   * Elephant 2000: A Programming Language Based on Speech Acts
   * John McCarthy, Stanford University, archived [https://web.archive.org/web/20130319040119/http://www-formal.stanford.edu/jmc/elephant.pdf]
   * Elephant input and output statements are characterized
   * as speech acts and programs, which 
   * can refer directly to the past.
   * Elephant proposal contains summary
   * on  McCarthy mathematical theory of computation  
   * King that learns? [A Program That Learns]
   * [upvar sugar]
   * [Salt and Sugar]
   * [Math sugar]
   * [A little math language]
   * [args]
   * [RS]
   * [LV]     
   * [Radical Language Modification]
   * [Functional Programming]
   * [Custom curry] 
   * [Playing with recursion]
   * [Modeling COND with expr]
   * [Sample Math Programs]
   * Professor Frisby's Mostly Adequate Guide to Functional Programming [https://github.com/MostlyAdequate/mostly-adequate-guide]
   * [expr shorthand for Tcl9]
   * [Steps towards functional programming]
   * [Tacit programming]
   * The fortran call statement appeared in Fortran2 (1958).  example of call exit, fortran 4     
   * Thocp code, http://www.thocp.net/software/languages/fortran.htm
   * [Natural User Interface]
   * [Natural Languages] category
   * [Game kingdom of strategy]
   * wikipedia.org wiki The_Sumerian_Game
   * [Find all words]
   * [Things German]
   * [How to synthesize a query]
   * [Writing Tk programs so that the user can extend or interact with them without modifying the application]
   * [Ruslish]
   * [Accumulator Generators]
   * [Accumulator Generator]
   * [Whadjasay]
   * disassemble byte code [https://www.magicsplat.com/blog/disassemble/]
   *  One Liners Programs Compendium [https://wiki.tcllang.org/page/One+Liners+Programs+Compendium++and+TCL+demo+examples+calculations%2C+numerical+analysis]
   * [One Liners]
   * [Oneliner's Pie in the Sky]
   * Ref. WIKI BOOKS, Tcl_Programming_Introduction, [https://en.wikibooks.org/wiki/Tcl_Programming/Introduction]
   * Book Section  contrasts one liners programs
   * versus  traditional procedural  approach, 
   * Multiple  Wiki Books on TCL programming  [https://en.wikibooks.org/wiki/Category:Book:Tcl_Programming]
   * [if]
   * [New Control Structures]
   * Kernighan and Pike: The practice of programming  
----  

**Hidden Comments Section**

<<discussion>>
Please include your wiki MONIKER and date in your comment   Thanks, [gold] 12Aug2020 

                              
----
<<categories>> Numerical Analysis | Toys | Calculator | Mathematics| Example| Toys and Games | Games | Application | GUI
----
<<categories>> Development | Concept| Algorithm  | Language 
----
<<categories>> Arts and crafts of Tcl-Tk programming | Category Functional Programming