hping wiki



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
}

 
Edit this page Upload file Page history - Page last update: Tue Nov 16 09:21:19 GMT 2004 by 80.181.43.200 | Your address: 54.226.227.175 | Admin