- 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
Def Innerproduct = (Insert +) o (ApplyToAll x) o Transposeand 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} defwhich 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} defwhich is shorter and simpler, but meddles more directly with the stack.An important functional form is the conditional, which at Backus looks likep1 -> f; p2 -> g; hmeaning, 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" ([2]). From 1989 on, there was a successor "FL" ([3]). The latest chip off that tree seems to be "NGL" ([4]).NEM: The style of programming by composing functions, without mentioning any variables, is sometimes referred to as "Point Free Style". A discussion at [5] 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" ([6])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? -MoritzMoritz, 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!)
