Serial summing

Difference between version 8 and 9 - Previous - Next
if 0 {
[Richard Suchenwirth] 2002-05-05: Reading chapter 1.3 of [SICP], a highly
educational introduction to programming based on the [LISP] dialect Scheme,
I felt challenged to try to reproduce the Scheme examples for summation of a series in Tcl, for example:

======none
 b
---
\
/   f(n) = f(a) + ... + f(b)
---
n=a
======

[PYK] 2019-02-10:  I have modified this page to use a modern form of
`[lambda]`, and to use `[tailcall]` where appropriate.  The tradeoff is that
because Tcl doesn't do tail recursion on its own accord, an explicit
accumulator is necessary.



** See Also **

   [Tcl and LISP]:   



** Description **
   
Both ''f'' and ''next'' are "functional objects", which in Tcl just means "a
command prefix", i.e. the first few words of a command.

Oiginally `sum` looked like this: 


======
proc sum {f a next b} {
    expr {$a>$b? 0 : [{*}$f $a] + [sum $f [{*}$next $a] $next $b]}
}
======

But in order to avoid stack growth due to recursive calls, it has been replaced
with the version below that uses tailcall. 

======
}

proc demo args {
    puts $args
    puts \n\t[uplevel 1 $args]\n
}

proc sum {f a next b {accum 0}} {
    if {$a > $b} {
        return $accum
    }
    set accum [expr {$accum + [{*}$f $a]}]    ::tailcall sum $f [expr {[{*}$f $a] + [{*}$next $a]}] $next $b $accum
}
# --------------------------- small building blocks:
proc cube x {expr {$x*$x*$x}}
proc inc  x {incr x} ;# argument x is value, instead of name
proc lambda {argl body} {
    list ::apply [list $argl $body [uplevel 1 {namespace current}]]
}

if 0 {
======

This handful of code allows us to reproduce the Scheme results
from [SICP]. For more info, see there.

   * sum the cubes of 1..10:

======
}

demo sum cube 1 inc 10 ;# -> 3025 
demo sum cube 1 [lambda x {incr x}] 10 ;# -> 3025

if 0 {
======

   * sum the integers from 1 to 10:

======
}

demo proc identity x {set x}
demo sum identity 1 inc 10 ;# -> 55
demo sum [lambda x {set x}] 1 [lambda x {incr x}] 10 ;# -> 55

if 0 {
======

   * approximate ''Pi'' one slow way:

======
}

demo proc pi-term x {expr {1.0 / ($x * ($x+2))}}
demo proc pi-next x {expr {$x + 4}}
demo expr {[sum pi-term 1 pi-next 1000] *8 } ;# -> 3.1395926555897828

if 0 {
======

Previously, the run limit could be increased from 1000 until 2756 before
raising the "too many nested calls..." error --( and still gave a less precise
approximation than the good old ''atan(1)*4''.  Now that `sum` uses
`[tailcall]`, there is no run limit.


   * '''integrate a function''' f between limits a and b:

======
}

demo proc integral0 {f a b dx} {
    set ::globaldx $dx
    expr {[sum $f [expr {$a + $::globaldx / 2}] add-dx $b] * $dx}
}
demo proc add-dx x {expr {$x+$::globaldx}}
demo integral0 cube 0 1 .0016 ;# -> 0.2499996800000055

if 0 {
======

Here however I had to start to compromise: instead of Scheme's lexical
scoping, where dx is visible everywhere inside integral's body,
including the add-dx function, I had to elevate dx to global status,
which is ugly; and Tcl's recursion depth limit caught me before I could
try [SICP]'s dx value of 0.001 - the result is still close (but no cigar)
to the correct result of 0.25. Oh wait, at least in this case we can
emulate lexical scoping more closely, by embodying `$dx` into a "live proc
body" of add-dx:

======
}

demo proc integral {f a b dx} {
    proc add-dx x "expr {\$x+$dx}"
    expr {[sum $f [expr {$a+$dx/2}] add-dx $b] * $dx}
}
demo integral cube 0 1 .00146 ;# -> 0.25009974849771255

if 0 {
======

----

A cleaner way to implement this "closure" would be an added default argument, like they do in Python - the body can remain braced, but the argument list of ''add-dx'' now "inherits" from outside:

======
}

demo proc integral {f a b dx} {
    proc add-dx "x {dx $dx}" {expr {$x+$dx}}
    expr {[sum $f [expr {$a+$dx/2}] add-dx $b] * $dx}
}

if 0 {
======

----

Slightly off-topic, but as all building blocks are there, here's a stint on
the ''derivative'' of a function, using the default args method, inheriting one argument from ''deriv'', and one from global namespace:

======
}

demo proc deriv g {
    lambda [list x [list g $g] [list dx $::dx]] \
        {expr {([{*}$g [expr {$x+$dx}]] - [{*}$g $x])/$dx}}
}
demo set dx 0.00001 ;# well, in SICP they have it global too...
demo {*}[deriv [lambda x {expr $x*$x*$x}]] 5 ;# -> 75.0001499966

if 0 {
======

Anyway, I'm again surprised how many [steps towards functional programming]
are possible with Tcl .. and more to come.

<<categories>> functional programming | Arts and crafts of Tcl-Tk programming
}