Functions As Values

Code

# Functions as values for Tcl
# An example implementation using the 'unknown' function, just
# to show the idea in pratical terms.
#
# Copyright (C) 2003 Salvatore Sanfilippo <[email protected]>
#
# RATIONALE:
#
# There is little theoretical justification for functions don't
# be strings in Tcl. The only change required to Tcl, is that
# the first argument of a command will not be the command name,
# but the function itself.
#
# The following is a Tcl function to add two numbers:
#
# proc add {x y} {expr {$x+$y}}
#
# It's used in the following way:
#
# add 1 2
#
# The first argument of the command, is the name of the procedure.
# The following, is the same code rewritten to use a function value
# as first argument:
#
# {{x y} {expr $x+$y}} 1 2
#
# So, as value, how a function looks like? Just as a list of two elements.
# The first element is the argument list, the second the body of the function.
#
# There is no reason to don't put the function inside a variable.
#
# set add {{x y} {expr $x+$y}}
#
# $add 1 2
#
# But it can be more handy to define a 'setfunc' function in order
# to make the syntax like the Tcl's [proc] command.
#
# set setfunc {
#     {varname arglist body} {
#         uplevel [list set $varname [list $arglist $body]]
#     }
# }
#
# This way, to set the 'add' variable to the function we write:
#
# setfunc add {x y} {
#   expr {$x+$y}
# }
#
# That's as comfortable as [proc] is.
#
# Still we need to use $add as first argument to call the
# function. But a valid function is composed of at least
# a two-elements list. So we can add a bit of syntax glue,
# and modify the interpreter to just expand the first-argument
# of the command to the value of the variable, if the first
# argument is a single-element list.
#
# After this change, we can just write:
#
# add 1 2
#
# To write [lambda] is trivial with the new semantics:
#
# setfunc lambda {arglist body} {
#    list $arglist $body
# }
#
# Of course, being functions just values, to assign a variable
# to a previoulsy create function is prefectly valid:
#
# set foo $add
#
# foo 1 2
#
# RESULT:
#
# We got first-class functions in Tcl. We can write in a very
# natural way functions that gets functional arguments, like [map],
# or functions that returns functions. Many expects of
# functional programming are now natural, and programming
# in general is more powerful this way. "Creating abstractions
# with functions" was explored for many decades in functional
# languages like Lisp.
#
# With functions as values, [dict], and functions for math operations,
# we have a more powerful language, with many of the advantages
# of the good Tcl, but more orthogonal, and powerful. If all is
# a string, and the idea is to pass stuff around by value, there
# is no reason for functions don't behave the same.
#
# FUTURE WORK:
#
# Immutable variables can be used to bind variables to functional
# arguments that can't be modified after the creation.
# [define] may be a good command name. Defined variables with
# a functional values (or with any other), are guaranteed to don't change,
# allowing for the creation of high-speed Tcl implementations: inlining,
# JIT compilers, code specialization, multi-port representation, and so on.
#
# Another field to investigate is the possibility to have closures.
# In such a case the functional representation should be a three-element
# list: arglist, body, a closures dictionary. Commands in order to
# access/modify the closure's variables from the function should be provided.
#
# EXAMPLE IMPLEMENTATION:
#
# The following code implements functions as values in pure Tcl.
# The goal of the implementation is to show the idea in
# pratical terms to people interested to new directions for the
# future of the Tcl language.
#
# FEEDBACKS
#
# Please, send feedbacks to <[email protected]>

namespace eval funcval {set counter 0}
rename unknown funcval::unknown

proc unknown args {
    set e [catch [list uplevel ::funcval::unknown $args] retval]
    if {!$e} {
        return $retval
    }
    set func [lindex $args 0]
    set funcargs [lrange $args 1 end]
    if {[llength $func] == 1} {
        set x1 {}
        set x2 {}
        catch {set x1 [uplevel set $func]}
        catch {set x2 [uplevel set ::$func]}
        if {[llength $x1] == 2} {
            set func $x1
        } elseif {[llength $x2] == 2} {
            set func $x2
        }
    }
    if {[llength $func] == 2} {
        set c [incr ::funcval::counter]
        set t [list proc ::funcval::lambda$c [lindex $func 0] [lindex $func 1]]
        set e [catch [list uplevel $t]]
        if {!$e} {
            set retval [uplevel ::funcval::lambda$c $funcargs]
            rename ::funcval::lambda$c {}
            return $retval
        }
        catch {rename ::funcval::lambda$c {}}
    }
    return -code error "invalid command name \"$func\""
}

proc lambda {arglist body} {
    return [list $arglist $body]
}

proc setfunc {varname arglist body} {
    uplevel [list set $varname [list $arglist $body]]
}

Examples

# A raw example using 'set'
set add {
    {x y} {
        expr {$x+$y}
    }
}

puts [add 1 2]

# setfunc is better than 'set' to create functions.
setfunc square x {
    expr {$x*$x}
}

# Functions are just values, an example
setfunc mytest {} {
    setfunc myadd {x y} {expr $x+$y}
    set foobar $myadd
    set x 10
    set y 20
    puts [foobar $x $y]
}

mytest

# You can pass functions as arguments, an implementation of 'map'.
setfunc map {f l} {
    set res {}
    foreach t $l {
        lappend res [$f $t]
    }
    return $res
}

set l {1 2 3 4 5 6}

puts [map $square $l]

# Anonymous functions are no longer a problem

puts [map [lambda x {expr $x-1}] $l]

# A more interesting example,
# a function foo that takes a number n and returns a function that takes
# a number i, and returns n plus i.
setfunc foo n {
    return [lambda i "expr $n+\$i"]
}

# Usage:
set g [foo 5]
puts [g 1] ; # => 6
puts [g 3] ; # => 8

# Curring can be used to generalize the previous example.
setfunc curry {func arg} {
    list args "[list eval $func $arg] \$args"
}

# Now to create the function that adds 5 to the argument we can
# just use the curry function.
set g [curry add 5]
puts [g 1]
puts [g 3]

# Another currying example, to curry [puts] to create
# a version that output to the stderr channel.
set eputs [curry puts stderr]
eputs {Hello World on stderr}

# A one-argument functional composition example
# Returns a function that computes [f [g arg]]
setfunc compose {f g} {
    lambda x "[list $f] \[[list $g] \$x\]"
}

# Example of functional composition
setfunc suc x {
    expr {$x+1}
}

set suc_square [compose $suc $square]

puts [suc_square 5]; # => 26
puts [[compose $square $suc] 5]; # => 36

Discussion

FW: Note that this is mainly just another Lambda in Tcl implementation. RS: I'd say it's much more - a comprehensive grand tour of many aspects of functional programming that have been discussed in this Wiki over years:

  • Lambda in Tcl - the idea that "the lambda is the value" of a function, here implemented as define proc - eval proc - delete proc. This may be slow in runtime, but avoids the garbage collection problem. In fact, with the above approach lambda is just list:
   interp alias {} lambda {} list
  • Function mapping
  • Currying - see Custom curry. For the cost of global persistent curry names (and uglier syntax), this can also be had with (compare the example above):
   interp alias {} g {} add 5 ;# vs. set g [curry add 5]