Alists for Tcl

SS 2004Mar12: The code at the end of this page implements alists data structures for Tcl. The following text is my brainstorm during the design of this implementation/API written in form of tutorial.

WHAT ARE ALISTS? edit

Alists, or Association Lists are lists of a special format. Each two elements of the list represent a key and an associated value. The following Tcl list is an alist with three elements:

  [list a 1 b 2 c 3]

The key a is associated with the value 1, b with value 2, and so on. (Note: alists are very used in Lisp dialects, but the format is a bit different. Every alist element is a two element list, so the format is like [list [list a 1] [list b 2] [list c 3]]. In Tcl the flat list format is more convenient).

Alists are very powerful, because they have many advantages of structures (in the sense of C struct or Scheme structs) but are more dynamic because fields are not accessed by index.

Alists can be incrementally augmented just adding two elements to their list representation. Because functions to get/set values by keys search the alist from left to right, an added key/value can shadow the next identical key in the alist.

Alists can be viewed as a mapping from keys to data that can be extended, reduced or non-destructively altered at runtime, and at the same time be a valid list.
[CMCc — incidentally, mappings from keys to data can also be fruitfully looked at as partial functions]
[DKF — Actually, the alist value is not updatable; it is the variable containing the alist that is updatable; model the variable as a higher-order function from "abstract time" (i.e., generation sequence number) to the relation representing the current alist.]

Alists are very generic, but the first goal of this library is provide a way to encapsulate an object representation in a simple but powerful data structure.

RATIONALE edit

(skip it if you want just the tutorial)

The alist representation has the benefit to be a valid dict representation, but the usage and design is a bit different. Basically they are very similar but the API is different: dicts are designed to be generic, while this implementation of alists is designed to make it easy to be used as powerful structures (in the sense of C "struct").

Alists require a struct-like declaration, that creates a command to create new alists of the defined types with pre-initialized fields.

To get or set a key that does not exists always raises an error (of course the programmer may add keys by hand just appending a key/value pair to the list representation of the alist, but the main idea is that alists are used to access named fields of a pre-defined data structure, so to set an unknown key can't just create a new key/value pair: it's not defensive programming).

Alists can be implemented very well using dict, but since dict is still only available in Tcl >= 8.5 this implementation uses only commands available in Tcl 8.4 (notably lset). BTW, note that alists implemented with dict lost some interesting priprietis (because the lookup is no longer from "left" to "right", and also can't hold multiple identical keys).
(DKF — As implemented in the 8.5.0 release, dictionaries are order-preserving and so have effective right-to-left lookup order. This was a late change in the 8.5 betas. They still can't hold multiple identical keys by design.)

BASIC USAGE edit

To define a new alist, the alist command is used:

: alist type fieldSpec ?fieldSpec ...?

For example:

    alist flower petals color type

The call to the alist command with this arguments creates a command named [make-flower] that returns a list representing an alist with the specified keys/values pairs.

To access fields we use the alget and alset commands.

For example, to create a flower that's a red rose with 5 petals we may write:

    set rose [make-flower]
    alset rose petals 5
    alset rose color red
    alset rose type rose

alset has the following signature:

: alset alistVar keyPath keyValue ?keyPath keyValue ...?

The alset command takes as arguments the name of a variable that holds a valid alist, the name of the key to set, and the new value. It's possible to specify more than just one key/value pair, so the previous last three lines of code are equivalent to:

    alset rose petals 5 color red type rose

To access the value associated with a given key we use alget, that has the following signature:

: alget alistValue keypath

We may for example create a function that pretty-prints a flower object:

    proc print-flower flower {
        puts "This flower is a [alget $flower type] with [alget $flower petals] [alget $flower color] petals"
    }

    print-flower $rose

Will print: "This flower is a rose with 5 red petals".

Both alget and alset will raise an error if the specified key does not exists.

DEFAULT VALUES AND INITIALIZATION edit

When alists are declared, we can specify the default value for every key. This way, the [make-<alistname>] command will create alists with every value initialized to the default value specified in the declaration.

For example we may want to re-declare the flower structure in this way:

   alist flower {petals 0} {color none} {type unknown}

Now every new flower alist created using [make-flower] will be initialized with the default values we provided. As you can see to specify a default value, instead to use the key name, we use a two-element list with the key name and the default value.

This is the behaviour of the new definition:

   set someflower [make-flower]
   print-flower $someflower

Will output: "This flower is a unknown with 0 none petals".

Another way to initialize fields at creation time is to pass arguments to the [make-flower] function. For example to create a flower with the default values but with 3 white petals we can write:

   set someflower [make-flower petals 3 color white]

It should be noted that if no default value is specified in the alist declaration, nor arguments are passed to the [make-...] command, all the fields are initialized to an empty string.

NESTING edit

alists (like dicts) are able to nest. Let's see why and how to use this feature.

Suppose you are creating a program for a florist that ships different kind of flowers in a box to different addresses.

The program is used to manage shipping of boxes, so to define the box object can be handy. A box in our case is some container with a flower inside and a shipping address. It is also available in different colours.

To start, we may want to define the 'address' object.

   alist address street number city

The second step is to define the 'box' object.

   alist box color content shipaddr

To create a yellow box object with a red rose with 10 petals inside to be shipped in Rome, Appia Street, 40, we may write something like this:

    set aflower [make-flower color red petals 10 type rose]
    set addr [make-address street Appia number 40 city Rome]
    set box [make-box color red content $aflower shipaddr $addr]

Now the alist box contains two nested alists. How to access them? We can just use the dot to create "key paths" that describe the path to reach a given key inside nested alist.

For example to get the city of the box's shipping address we can just write:

   alget $box shipaddr.city

alset works just the same way. That's OK, but to create a box with a flower inside and a shipping address was a bit verbose. We can use the default initialization of alists and define boxes this way:

   alist box color [list content [make-flower]] [list shipaddr [make-address]]

This way all the box created using [make-box] will contain nested flower and address alists.

Now to create the previous box we can write:

    set box [make-box color red \
            content.color red content.petals 10 content.type rose \
            shipaddr.city Rome shipaddr.street Appia shipaddr.number 40]

That's it. Note that after we created the box, we may like to, for example, change the flower inside. If $whiteflower already contains a flower alist with a 30 petals yellow marguerite we have just to write:

    alset box content $whiteflower

For complex manipulation of alists it can be a good idea to write functions that do the work for us. Remember that alists are just values (so, just strings), so you can pass and return they with normal procedures.

LISTS OF ALISTS edit

Our florist wants to expand its product line, so it plans to ship boxes with more than one flower. The florist's software development division face a new problem: to describe boxes with N flowers inside.

A simple solution is to make the ‘content’ field of the box alist, a list of alists. Every element is a flower alist. This works as representation, but it can be uncomfortable to read/modify boxes's content. Fortuantely our alists have support for this. If an element in a key path is a number, it is used to index a particular list element.

For example:

   alget $alist foo.3

Will return the value of the element with index 3 of the list stored in the ‘foo’ field of $alist.

For extension:

   alget $somebox content.5.color

Will return the value of the ‘color’ key of the alist at index 5 in the list-of-alists stored in the ‘content’ field.

Still to add new boxes to the content may be tricky. We need to get the content list of alists, append a new flower to it, and then set this new list.

So, assuming we created an empty red box in this way, with some shipping address,

   set box [make-box color red content {} shipaddr $addr]

to add a new flower inside the box we need the following commands:

   set l [alget $box content]
   lappend content [make-flower color blue type tulipan]
   alset box content $content

In order to make it more simple, the alist library provides the allappend command that works like lappend but against alist fields. So we can rewrite the above three lines of code into:

   allappend box content [make-flower color blue type tulipan]

ALISTS TYPE SYSTEM edit

Every time an alist is created by the [make-<name>] command, the generated alist contains all the keys the user specified in the alist definition of that name, plus an additional key __alisttype__ that has as default value the name of the alist's type.

To make it simpler, if we create an alist, “point”, with:

   alist point x y

and we create a point:

   set p [make-point x 1 y 2]

then the following command will return the string "point":

   alget $p __alisttype__

Instead to directly get the __alisttype__ key, there is the command altype that does just this. So the above code is equivalent to:

   altype $p

Programmers can use the type information in different ways: for function overloading, type checking, and so on.

The following is an example of function overloading using alist's type information.

    alist string value
    alist list value
    alist int value
     
    proc + {a b} {
        set A [alget $a value]
        set B [alget $b value]
        switch -- [altype $a] {
            string {make-string value $A$B}
            list {make-list value [concat $A $B]}
            int {make-int value [expr {$A+$B}]}
            default {error "don't know how to add '[altype $a]'"}
        }
    }

    set a [make-string value 10]
    set b [make-string value 20]
    lappend res [+ $a $b]
    set a [make-list value 10]
    set b [make-list value 20]
    lappend res [+ $a $b]
    set a [make-int value 10]
    set b [make-int value 20]
    lappend res [+ $a $b]
    foreach r $res {puts [alget $r value]}

The output will be 1020, 10 20 and 30

OTHER UTILITIES edit

alincr increments the integer at the specified alist's key. Example:

   alincr alistVarName x.y -3

The last argument (the increment) can be omitted and defaults to 1.

alsappend is like allappend but append strings to the specified string instead to elements to the specified list.

it's called ‘sappend’ because append strings. Since allappend is similar to lappend, and alsappend is similar to append you may wonder why the name of this command is not just alappend. That's because it's too simple to write “alappend” instead of “allappend”.

Happy nesting.


 # Alists - Lisp-like alist data structures.
 # Copyright (C) 2004 Salvatore Sanfilippo <antirez@invece.org>.
 # Under the same license as Tcl/Tk 8.4
 
 namespace eval ::alist {}
 
 # Return the index of the specified key.
 # -1 is returned if the alist key is not found.
 proc alist::alindex {alist key} {
     set i 1
     foreach {f _} $alist {
        if {$f eq $key} {return $i}
        incr i 2
     }
     return -1
 }
 
 # Return a list of list idexes that can be used as arguments
 # to lset or lindex to access to the list element identified
 # by the 'keys' list.
 proc alist::alpath {alist keys} {
     set l $alist
     set path {}
     foreach f $keys {
        if {[string is integer -strict $f]} {
            set i $f
        } else {
            set i [::alist::alindex $l $f]
        }
        if {$i == -1} {
            error "No such key '[join $keys ->]' in alist"
        }
        set l [lindex $l $i]
        lappend path $i
     }
     return $path
 }
 
 # Get the value of the alist's key 'field'.
 # Example: alget $l foo.bar
 proc alist::alget {alist field} {
     set path [::alist::alpath $alist [split $field .]]
     switch -- [llength $path] {
        1 {lindex $alist [lindex $path 0]}
        2 {lindex $alist [lindex $path 0] [lindex $path 1]}
        3 {lindex $alist [lindex $path 0] [lindex $path 1] [lindex $path 2]}
        0 {error "No key specified"}
        default {eval [list lindex $alist $path]}
     }
 }
 
 # Set the value of one ore more alist's keys.
 # Example: alset $l foo 5 bar 6 attrib.color 10
 proc alist::alset {alistVar args} {
     upvar $alistVar alist
     foreach {field val} $args {
        set path [::alist::alpath $alist [split $field .]]
        switch -- [llength $path] {
            1 {lset alist [lindex $path 0] $val}
            2 {lset alist [lindex $path 0] [lindex $path 1] $val}
            3 {lset alist [lindex $path 0] [lindex $path 1] [lindex $path 2] $val}
            0 {error "No key specified"}
            default {eval [list lset alist $path $val]}
        }
     }
     return $alist
 }
 
 # Define a new alist. As side effect, a command [make-<name>] to
 # create new alists of the specified type is created.
 proc alist::alist {name args} {
        set template [list __alisttype__ $name]
        foreach slot $args {
                set initializer {}
                if {[llength $slot] > 1} {
                    set initializer [lindex $slot 1]
                    set slot [lindex $slot 0]
                }
                lappend template $slot $initializer
        }
        proc ::make-$name args [format {
            set s %s
            foreach {slot val} $args {
                    alset s $slot $val
            }
            return $s
        } [list $template]]
        return $args
 }
 
 # Return the list of (non nested) keys of the specified alist.
 proc alist::alkeys alist {
     set fields {}
     foreach {f _} $alist {
        lappend fields $f
     }
     return $fields
 }
 
 # Return the alist's type name
 proc alist::altype alist {
     ::alist::alget $alist __alisttype__
 }
 
 # Increment the (integer) value of the specified key.
 proc alist::alincr {alistVar field {increment 1}} {
     upvar $alistVar alist
     set int [::alist::alget $alist $field]
     incr int $increment
     ::alist::alset alist $field $int
 }
 
 # Lappend the arguments to the list at the alist's key.
 proc alist::allappend {alistVar field args} {
     upvar $alistVar alist
     set list [::alist::alget $alist $field]
     ::alist::alset alist $field {} ;# May reduce the $list refcount to 1
     foreach e $args {
        if {[catch {lappend list $e} err]} {
            # Restore the alist state
            ::alist::alset alist $field $list
            # Propagate the error
            error $err
        }
     }
     ::alist::alset alist $field $list
 }
 
 # append the arguments to the string at the alist's key.
 proc alist::alsappend {alistVar field args} {
     upvar $alistVar alist
     set str [::alist::alget $alist $field]
     ::alist::alset alist $field {} ;# May reduce the $str refcount to 1
     foreach e $args {
        append str $e
     }
     ::alist::alset alist $field $str
 }
 
 namespace eval alist {
     namespace export alget alset alist alkeys altype alincr allappend alsappend
 }

Contributions and Discussion edit

kruzalex With some changes in the code it is possible to use also name of the keys to get values by nesting. See below modified code and attached examples:

  proc alist::alindex {alist key} {
         upvar path p
     set i 1
     foreach {f _} $alist {
        if {$f eq $key} {
            return $i
        } 
        if {[string is integer -strict $p]} {
            set i [lsearch [lindex $alist $p] $key]
            incr i
            return $i
        }
        incr i 2
     }
     return
 
  proc alist::alpath {alist keys} {
     set l $alist
     set path {}
     foreach f $keys {
        if {[string is integer -strict $f]} {
            set i $f
        } else {
            set i [::alist::alindex $l $f]
        }
        lappend path $i
     }
     return $path
  }
 
  proc alist::allappend {alistVar field args} {
     upvar $alistVar alist
     set list [::alist::alget $alist $field]
     ::alist::alset alist $field {} ;# May reduce the $list refcount to 1
     foreach arg $args {
             foreach e $arg {
        if {[catch {lappend list $e} err]} {
            ::alist::alset alist $field $list
            error $err
        }
      }
     }
     ::alist::alset alist $field $list
   }

   #Example1
   alist someflower petals color
   set rose [make-someflower]
   alset rose petals 5 
   alset rose color red
   
   proc print-flower flower {
   puts "This flower is a with [alget $flower petals] [alget $flower color] petals"
   }
   print-flower $rose
   
   #Example2
   alist someflower petals color
   set rose [make-someflower petals 0 color red]

   proc print-flower flower {
   puts "This flower is a with [alget $flower petals] [alget $flower color] petals"
   }
   print-flower $rose
   
   #Example3   
   alist aflower color petals type
   alist addr street number city
   alist box color content shipaddr
     
   set aflower [make-aflower color red petals 10 type rose]
   set addr [make-addr street Appia number 40 city Rome]
   set box [make-box color red shipaddr $addr]
   puts [alget $box shipaddr.city]
   
   #Example4
   alist aflower color petals type
   alist addr street number city
   alist box color content shipaddr
      
   set aflower [make-aflower]
   alset aflower color red
   alset aflower petals 10
   alset aflower type rose

   set addr [make-addr]
   alset addr street Appia
   alset addr number 40
   alset addr city Rome
   
   set box [make-box]
   alset box color red 
   alset box content $aflower 
   alset box shipaddr $addr
   
   #puts [alget $box shipaddr.7]
   puts [alget $box shipaddr.city]
   
   #Example5
   alist aflower color petals type
   alist addr street number city
   alist box color content shipaddr
      
   set aflower [make-aflower color red petals 10 type rose]
   set addr [make-addr street Appia number 40 city Rome]
   set box [make-box color red content {} shipaddr $addr]
    
   allappend box content [make-aflower color blue type tulipan]
   #puts [alget $box content.3]
   puts [alget $box content.color]

There's "ihash" if you want to speed up things for 8.4 (not sure you're aiming at large alists) - see [1] and Adding a hashed datatype -jcw

I've not a lot of experience with them, but are these alists similar to Tclx's keyed lists? Also, they seem, in layout, to be similar to the values returned from an array get command - is that a valid understanding?

DKF: They're similar to dicts and the lack of property duplication can be construed to be a good thing. :^) Oh, and yes, they are similar semantically to keyed lists, though different syntactically.

Category Package

Category Data Structure