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 [L1 ],

*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 procs or lambdas, 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" ([L2 ]). From 1989 on, there was a successor "FL" ([L3 ]). The latest chip off that tree seems to be "NGL" ([L4 ]).

NEM: The style of programming by composing functions, without mentioning any variables, is sometimes referred to as "Point Free Style". A discussion at [L5 ] 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" ([L6 ])

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

gold10/10/2020, added appendix, but above text and code unchanged.

- 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 [L7 ]
- McCarthy’s LISP and Basis for Theory of Computation, archived pdf[L8 ]
- en.wikipedia.org search on <John McCarthy computer> [L9 ]
- John McCarthy at Stanford web site, archived [L10 ]
- Towards a Mathematical Science of Computation, J. McCarthy,
- Computer Science Department,Stanford University, archived pdf [L11 ]
- Elephant 2000: A Programming Language Based on Speech Acts
- John McCarthy, Stanford University, archived [L12 ]
- 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 [L13 ]
- 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 [L14 ]
- One Liners Programs Compendium [L15 ]
- One Liners
- Oneliner's Pie in the Sky
- Ref. WIKI BOOKS, Tcl_Programming_Introduction, [L16 ]
- Book Section contrasts one liners programs
- versus traditional procedural approach,
- Multiple Wiki Books on TCL programming [L17 ]
- if
- New Control Structures
- Kernighan and Pike: The practice of programming

Please include your wiki MONIKER and date in your comment Thanks, gold 12Aug2020

Category Numerical Analysis | Category Toys | Category Calculator | Category Mathematics | Category Example | Toys and Games | Category Games | Category Application | Category GUI |