Salvatore Sanfilippo 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?
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.
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=== (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: [dict]s
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).
BASIC USAGE
To define a new alist, the [alist] command is used:
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:
alest 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
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 unknow}
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 a null string.
NESTING
alists (like [dict]s) 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 $whitflower
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
Our florist wants to expand it's 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 am 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'''
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
[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
}
| | |