Updated 2012-08-17 00:20:59 by RLE

Arjen Markus This is the second part of the tutorial - it is not ideal to split the whole thing, but I do not want to run the risk that my Internet browser does not allow me to edit the page anymore because it is too large ;)

5. A library example

The second example we are going to examine is a small mathematical library, that is, a set of related procedures that do something more or less useful and that we want to be able to use in various applications. Such libraries can be small or extensive, coherent or simply a collection of lots of procedures that can be useful at times.

For a library to be useful, it is important to have:

  • A user manual, i.e. a description of what the library is meant for

and how to use its contents, but from a programmer's point of view.

  • A set of test cases, so that we can check that the library is

working as expected and will continue to do so if we change something.

We also need to take care that we do not define procedures that an application might also define for itself (so-called name clashes) or that global variables are kept out of each others' way.

To avoid problems we will use namespaces: our procedures and our variables "live" in a different world than the application that will use the library. The application can choose to import procedures from the library, but does not need to. For instance: our library contains a procedure "add", but an application can define its own procedure "add", as long as it does not import ours. (More on namespaces: Will Duquette's tutorial)

Here is the code to create the namespace (::Poly - the double colons indicate the namespace is located directly under the global namespace):
   namespace eval ::Poly {
      variable pcount   0
      variable pcoeffs

      namespace export polynomial add deriv
   }

We define a few namespace variables - they exist, just like global variables outside any procedure. By means of the command "namespace export" we identify the commands that are useful for an application and that can be imported (via a command "namespace import ::Poly::*" for instance).

To use this library in our applications, we have two choices:

  • The application sources the files containing the code directly
  • We provide the library as a genuine package

The latter is preferable, because then we do not need to know too much about the way the library is implemented - this is taken care of by the package mechanism.

How does this mechanism work? Well, by using a "package provide" statement:
   package provide Polynomials 1.0
   namespace eval ::Poly {
      ...
   }

(Note: the name of the package is independent of the namespace it lives in. Normally you would choose them equal. The number 1.0 is the version number)

Now, this is the first part. When the application asks for the package, via:
   package require Polynomials

Tcl will search through all directories listed in the variable auto_path to see if there is such a package. This process depends on the presence of a file called "pkgIndex.tcl" that contains information about the packages available in the directory.

As a developer of the library, you can use commands to generate this file for you, but in simple cases, it is easy enough to make it yourself:
   package ifneeded Polynomials 1.0 [list source [file join $dir poly.tcl]]

The variable "dir" is filled in during the directory search done by Tcl and enables you to keep any specific directory out of the file.

What remains is:

  • Store the source file (poly.tcl) and the package index (pkgIndex.tcl) in a suitable directory (check the auto_path variable for this or extend it yourself in your application)
  • Have your application "require" the package

Here is the code for our little package (this is actual working code!)
 # poly.tcl --
 #    Library for defining and manipulating polynomials
 #
 package provide Polynomials 1.0

 # Poly --
 #    Namespace for the procedures handling polynomials
 #    Variables:
 #    pcount  - counts the polynomials that have created,
 #              used to construct a unique name
 #    pcoeffs - array holding the coefficients of each polynomial:
 #              each array element has the name of the polynomial
 #              and its value is the list of coefficients
 #
 #

 namespace eval ::Poly {
    variable pcount   0
    variable pcoeffs

    namespace export polynomial add deriv
 }

 # EvalPolynomial --
 #    Private procedure to actually evaluate the given polynomial
 #    for a given argument
 # Arguments:
 #    pname     Name of the polynomial
 #    x         Value of the variable
 # Result:
 #    Value of the polynomial at the given variable
 #
 proc ::Poly::EvalPolynomial { pname x } {
    variable pcoeffs

    set result 0.0
    set powx   1.0
    foreach c $pcoeffs($pname) {
       set result [expr {$result+$c*$powx}]
       set powx   [expr {$powx*$x}]
    }
    return $result
 }

 # polynomial --
 #    Create a procedure that can evaluate the given polynomial
 # Arguments:
 #    coeffs    List of coefficients
 # Result:
 #    Name of new procedure
 #
 proc ::Poly::polynomial { coeffs } {
    variable pcount
    variable pcoeffs

    #
    # Create a unique ID for the new procedure
    # Careful - we will create the new procedure in the _current_
    # namespace
    #
    incr pcount
    set pname  "[namespace current]::P$pcount"

    #
    # Store the coefficients under the name of the new procedure
    # (easier access)
    #
    set pcoeffs($pname) $coeffs

    #
    # Create the procedure - yes, we can do that from within
    # a procedure: "proc" is just a command like any others!
    # (Note: we need to be careful with the special
    # characters though - the name "$pname" must be filled in
    #
    proc $pname { x } "return \[EvalPolynomial $pname \$x\]"

    #
    #
    return $pname
 }

 # add --
 #    Add two polynomials to give a new one
 # Arguments:
 #    p1        First polynomial (name of)
 #    p2        Second polynomial (name of)
 # Result:
 #    Name of new procedure implementing the sum
 #
 proc ::Poly::add { p1 p2 } {
    variable pcoeffs

    #
    # Get the coefficients of each
    #
    set pc1 $pcoeffs($p1)
    set pc2 $pcoeffs($p2)

    #
    # As the polynomials do not necessarily have the same
    # degree, first make the lists equal in length
    #
    # Note:
    # We use a clever trick to avoid too much and unnecessary
    # checking: at most one of the for-loops is actually
    # run.
    #
    set ncoeffs1 [llength $pc1]
    set ncoeffs2 [llength $pc2]

    for { set i $ncoeffs1 } { $i < $ncoeffs2 } { incr i } {
       lappend pc1 0.0
    }

    for { set i $ncoeffs2 } { $i < $ncoeffs1 } { incr i } {
       lappend pc2 0.0
    }

    #
    # Now we can easily loop over the two sets of coefficients
    # - they have the same length
    #
    set sumcoeffs {}

    foreach c1 $pc1 c2 $pc2 {
       lappend sumcoeffs [expr {$c1+$c2}]
    }

    #
    # Create the new polynomial, and return its name
    #
    return [polynomial $sumcoeffs]
 }

 # deriv --
 #    Determine the derivative of a polynomial
 # Arguments:
 #    pname     First polynomial (name of)
 # Result:
 #    Name of new procedure implementing the derivative
 #
 proc ::Poly::deriv { pname } {
    variable pcoeffs

    #
    # Get the coefficients
    #
    set pc $pcoeffs($pname)

    #
    # Loop over the coefficients: the first disappears
    # Note:
    # The command [lrange ...] is executed only once
    #
    set derivcoeffs {}

    set degree 1
    foreach c [lrange $pc 1 end] {
       lappend derivcoeffs [expr {$c*$degree}]
       incr degree
    }

    #
    # Create the new polynomial, and return its name
    #
    return [polynomial $derivcoeffs]
 }

 #
 # Some test code
 #
 if { [info script] == "" || [file tail $::argv0] == [info script] } {
    set p  [::Poly::polynomial {1 1 1}]
    set q  [::Poly::polynomial {-1 -1 1}]
    set p' [::Poly::deriv $p]
    set pq [::Poly::add $p $q]
    puts "Eval  = Actual      - Expected"
    puts "p(1)  = [$p 1]      - 3.0"
    puts "p(2)  = [$p 2]      - 7.0"
    puts "p(3)  = [$p 3]      - 13.0"
    puts "p'(1) = [${p'} 1]   - 3.0"
    puts "p'(2) = [${p'} 2]   - 5.0"
    puts "p'(3) = [${p'} 3]   - 7.0"
    puts "pq(1) = [$pq 1]     - 2.0"
    puts "pq(2) = [$pq 2]     - 8.0"
    puts "pq(3) = [$pq 3]     - 18.0"
 }

At the end you see a clever little trick:
 if { [info script] == "" || [file tail $::argv0] == [info script] } {
    ...
 }

If we copy and paste the code into an interactive Tcl shell, tclsh or wish say, then the command [info script] returns an empty string.

If on the other hand we put this code in a file and run it via:
   % tclsh polynomials.tcl

the global variable argv0 will hold the full name (including the directory) of the script that is being executed at start-up by tclsh or wish. The command [info script] will return the name of the script file that is being sourced.

So, if these two file names match, or there is no file being sourced, then we can be (almost) sure that the library's source file is being run standalone - a perfect opportunity for running a few tests.

5.1 Explanation of the package

The package has been designed such that each new polynomial becomes a new Tcl command. To keep the amount of (repeated) code as low as possible, it uses the command ::Poly::polynomial to create any new polynomial.

The package uses an array (pcoeffs) to hold the data for a polynomial:

  • Each array element has a name that is the name of a polynomial
  • The value of the element is a list of coefficients, starting with the zeroth order coefficient
  • The new command that is created merely needs to pass its own name to the private routine EvalPolynomial and that picks up the coefficients.

But the current set-up is just one possibility and it is tuned to make evaluating a polynomial easy. You could call this a command-centric approach. If, instead, polynomials are merely data, you might want a more data-centric approach: some algorithms require the creation of many intermediate polynomials and it is useless to keep them around after the algorithm is completed.

To achieve that approach, you might benefit from a "tagged" list:
   proc ::Poly::polynomial { coeffs } {
      return [concat POLYNOMIAL $coeffs]
   }

The return value of this procedure is a list with the first element indicating its type. As it does not create a procedure or private data, the polynomial represented by this list disappears as soon as the variable holding it is destroyed. So, no problem of unnecessary procedures.

The first element of the list can be used to distinguish the list of data from, say, a Fourier series. Of course, the procedure deriv and all other procedures will have to be revised too. For instance, deriv might become:
   proc ::Poly::deriv { polyn } {
      set derivcoeffs {POLYNOMIAL}

      set degree 1
      foreach c [lrange $polyn 1 end] {
         lappend derivcoeffs [expr {$c*$degree}]
         incr degree
      }

      return $derivcoeffs
   }

Again, just a list is returned, no command is created.

(An advantage could be that you can easily support a broader class of functions, like the rational functions, if you distinguish other "tags" too)

What works best, depends on the purpose and usage of a package.

5.2 Tcltest

PM

6. A library in object-oriented style

Proponents of the object-oriented style of programming, in short OO, sometimes criticise Tcl for not being object-oriented. Well, apart from the lack of special syntax, they are quite wrong. If you want to criticise Tcl on this account, rather say that Tcl has too many approaches to OO!

Here are the four approaches that are best-known:

  • [incr Tcl] is the oldest and best known. It is a compiled extension to Tcl and, when you realise its name is a pun (compare it to C++), you can imagine what type of OO approach it takes: it mimicks to some extent the OO flavour found in C++
  • XoTcl on the other hand is a highly versatile and, perhaps, experimental extension that allows various flavours of OO.
  • stooop is a Tcl-only extension that works in a similar way as [incr Tcl]
  • Snit is yet another Tcl-only OO approach. It differs from the others because it relies on "delegation" rather than ''inheritance to achieve the typical OO characteristics.

Whatever flavour suits you best, never say that you can not do OO in Tcl :). If none suits you, you can always roll your own extension ... the language provides enough support!

Perhaps a small example of how OO works in Tcl will help to appreciate the versatility of Tcl in this respect. We will take Snit as our OO extension and we are going to reuse the polynomials library as much as possible.

To achieve that, consider the following interface:

  • polynomial create $name {...} will create a new polynomial by the name $name
  • $name eval $x will evaluate the polynomial at x-coordinate $x
  • $name plot $xmin $xmax $xstep will plot the values of the polynomial over the given interval in a new toplevel window

(We could do the deriv and add commands in this fashion too, but to me it seems it would be too much of the same thing, so I leave that as an exercise.)

Well, the command polynomial represents a class and each instance of this class has a single isntance variable, pcmd. This is the name of the procedure that our original library creates and returns. By invoking that procedure when asked to evaluate the polynomial at a certain value, the class nicely wraps all details into the OO method "eval".

As a side effect, we can now give the polynomial a meaningful name (see the test code).
 package require snit
 package require Polynomial

 snit::type polynomial {
    variable pcmd

    #
    # The constructor stores the name of the actual command
    # in the variable pcmd
    #
    constructor {coeffs} {
       set pcmd [::Poly::polynomial $coeffs]
    }

    #
    # Wrapper for the original polynomial command
    #
    method eval {x} {
       return [$pcmd $x]
    }

    #
    # New command: plot
    # make sure the name of the toplevel widget is valid
    #
    method plot {xmin xmax xstep} {
       set width  300
       set height 200
       regsub -all {[^a-z0-9]} [string tolower $self] {} name
       toplevel .$name
       canvas   .$name.c -width $width -height $height
       set x      $xmin
       set ymin   1.0e20
       set ymax  -1.0e20
       set coords {}
       while { $x <= $xmax } {
          set y [$self eval $x]
          lappend coords $x $y
          set x [expr {$x+$xstep}]
          if { $y < $ymin } { set ymin $y }
          if { $y > $ymax } { set ymax $y }
       }
       if { $ymin == $ymax } { set ymax [expr {$ymax+1.0}] }

       set xscale [expr {$width/double($xmax-$xmin)}]
       set yscale [expr {$height/double($ymax-$ymin)}]

       set pixels {}
       foreach {x y} $coords {
          set px [expr {$xscale*($x-$xmin)}]
          set py [expr {$yscale*($ymax-$y)}]
          lappend pixels $px $py
       }

       .$name.c create line $pixels -fill red

       #
       # Axes
       #
       set px0 [expr {$xscale*(0.0-$xmin)}]
       set py0 [expr {$yscale*($ymax-0.0)}]
       .$name.c create line $px0 0    $px0   $height -fill black
       .$name.c create line 0    $py0 $width $py0    -fill black
    }
 }

 #
 # Some test code
 #
 if { [info script] == "" || [file tail $::argv0] == [info script] } {
    polynomial create P1 {1 1 1}
    puts [P1 eval 1.0]
    P1 plot -1.0 1.0 0.02
 }

The plot method may seem complicated, but all it does is:

  • Create a new toplevel window with a canvas in it
  • Evaluate the polynomial over the given interval
  • Scale the values to pixel coordinates
  • Draw the line and some very basic axes

As given here, it is not fool-proof:

  • There is no check that xmin < xmax and xstep > 0
  • There is no check that the value of the polynomial does not exceed 1.0e20 (then our determination of the minimum and maximum is wrong!)

It is, as usual, just a simple example.

If you are interested and want to get some exercise in the usage of Snit:

  • Implement the deriv and add methods in analogy with the original library
  • Implement methods for introspection (get the coefficients back)
  • Implement a plotting method that can take a particular canvas as

its option and then draw in that canvas - mind you: the canvas becomes an object in its own right! Two or more polynomials in the same canvas require sharing the scaling.

Note 1: one of the reasons Snit is gaining popularity, is the way it allows you to set up "mega widgets", that is widgets that actually contain other widgets that should cooperate in some fashion.

Note 2: this was my first actual experience with Snit. I wrote this chapter, including the Snit wrapping code, in half an evening, after reading the manual page. I mention this not to brag about my proficiency with Tcl or about the speed with which I can write, but rather to show you that OO is very simple with Tcl. As is almost anything :)

KPV Actually I find that clever trick to be very annoying. I like to test out new code from a Wiki page by pasting it into tkcon, and this trick does the wrong thing.

AM I have noticed this does not work under all circumstances! I was not aware of a problem in tkcon though. Any idea of how to circumvent that? How to make it "fool-proof"? (This is a perfect opportunity, I think, to get it right ...)

AM I amended the above code: the copy/paste method of testing should work now. (I will move/copy this discussion to its own page later).

Lars H My main concern is that even the first (supposedly non-object oriented) half of this page is far too object-oriented to be generally useful. IMO, polynomials are primarily data and should be treated as such. Having a procedure that evaluates a fixed polynomial at the point it is given may be convenient if you intend to evaluate it in a lot of points, but is extremely annoying for practically all other uses. If I were to implement something like polynomial division or the Buchberger algorithm on top of the procedures in this library then I would very quickly run out of memory because the package would store all intermediate results of all calculations (assigning each of them a separate array entry and separate procedure).

Another objection I have with respect to the comments as shown above is that they are all about the commands and completely ignore the data structures. The very important pcoeffs array is only explained as "coefficients of each polynomial", but it isn't explained what the array entries contain (they're lists of coefficients, with the coefficient of x^i at position i) or indeed even that it is an array! The latter fact may be apparent from the code, but the former definitely requires some analysis of it. In my experience, failure to document the data structures is a common reason that code becomes undecipherable and impossible to fix.

AM Hm, first point taken. Yes, the original code is a bit biased towards object-orientedness. But for the second point: I simply have not gotten to explaining the code properly - see my TODO list below :)

TODO/Explain:

  • Coefficients in array
  • Three procedures for creating a polynomial
  • Extra comments
  • Style guide Ray Johnson, Will Duquette
  • expr and {}
  • tcltest
  • several source files

The previous part of this tutorial is How to make a Tcl application. The next part of the tutorial is How to make a Tcl application - part three.