DN626306323

Subject: ANNOUNCE: Dictionary 1.0: a new Tcl object type - DN [1]

Frederic BONNET <frederic.bonnet@ciril.fr> - 23 May 2000 - comp.lang.tcl

 Dictionary: a new Tcl object type
 =================================

 Copyright (c) 1999-2000 Frédéric BONNET <frederic.bonnet@ciril.fr>

 Please read the file license.txt

 What's new: version 1.0.0, May 23th 2000
 ----------------------------------------

 - The package is now final and no longer alpha.
 - Added the "foreach" method for dictionary iteration.

 Introduction
 ------------

 This piece of software implements a new Tcl object type called "dictionary". I
 decided to create it after a discussion in comp.lang.tcl, when I issued a RFC on
 arrays as first class object. The primary purpose was to turn arrays into
 objects so that they can be used everywhere Tcl objects are expected: as proc
 arguments or inside other objects. In the current implementation, arrays have no
 existence outside of their variable; one could see arrays as a collection of
 variables, and not as a data structure like lists. The only means of passing
 arrays to a proc is by reference and not by value. Dictionaries are an attempt
 to define an alternative to lists as a data structure, with array semantics.

 Dictionaries can be seen as a hybrid between arrays and lists. They look like
 lists, can be used as lists (thanks to the "everything is a string" Tcl
 paradigm), but their internals are closer to arrays in the sense that they use
 hash tables to store data. Some form of dictionary already exists in Tcl: the
 result of "array get" (also used as argument in "array set") has an external
 representation which is the same as a dictionary: an even-sized list whose even
 elements are keys and odd elements are values. The idea behind dictionaries is
 to give these pairlists an internal representation, rather than use the plain
 list representation. That way, the internal hash table never gets lost, and
 dictionaries can be used as arrays without performance hit. This is the main
 difference with other solutions such as TclX's keyed list, which don't use hash
 tables and then yields O(n) performances on element access. Arrays and
 dictionaries yield nearly-O(1) performances on element access.

 A quick comparison between the different data structures:
 ---------------------------------------------------------

 =============================================================================
            Access        First-class  Order         Variable    Immutable
            performances     object       Preservation  operations    operations
 =============================================================================
 List        O(1)         Yes          Yes           Yes         Yes

 Keyedlist   O(n)         Yes          Yes           Yes         No

 Array       O(1)         No           No (via       Yes         No (variable)
                                       "array get")

 Dictionary  O(1)         Yes          No            Yes         Yes
 =============================================================================

 Here "Immutable operations" mean operations on pure values that affect no
 variable or other objects, such as "lreplace". "Variable operations" are
 operations that affect variables, such as "lappend".

 Arrays have no immutable operation since they are only implemented as variables.
 Keyedlists are regular Tcl objects but their interface define no immutable
 operation, only variable operation. There is no mean to use anonymous (ie as
 value) keyedlists. Lists only define "list" and "lappend" as variable
 operations, others are all immutable operations (lreplace, lrange...).
 Dictionaries provide both variable and immutable "write" operations (such as
 set/create, unset/substract, add/merge), and immutable "read" operations (get,
 size, exists...). So dictionaries can be used as arrays with variable ops, and
 as lists with immutable ops.

 Order preservation is only useful for those who want to interchange objects with
 lists. Keyedlists preserve the order in which elements are set. Arrays aren't
 objects so this notion hardly applies, but "array get" returns a Tcl list from
 an array, and the  elements order is undefined (it depends on the order in which
 elements are stored in the hash table). Dictionary follows array semantics in
 the sense that their external representation looks like a list, but the list
 elements are also undefined, only the key-value associations are considered
 meaningful.

 Where to get it
 ---------------

 The dictionary source archive can be found there:

     http://www.purl.org/net/bonnet/pub/dictionary.tar.gz

 It contains sources, a Visual C++ makefile for Windows and TEA-compatible (well,
 I hope so :) configure scripts.

 Version
 -------

 The current version is 1.0.0 and follows the Tcl convention, that is
 major.minor.patchlevel. It means that this version is the first release (.0
 suffix) of version 1.0, and considered stable enough to be safely used in most
 applications, even mission-critical. If a bug is spotted or a feature needs to
 be slightly corrected, modifications will be made available as patches.

 It is intended to be used with Tcl8.2 or above.

 Building the package
 --------------------

 On Windows:

     the provided makefile.vc is a MS Visual C++ -compatible makefile.
     Simply edit it then run nmake on it.

 On TEA-compatible architectures: Unix, Windows with Cygwin:

     To make type:

       ./configure
       make
       make install

     The configure script will deduce $PREFIX from the tcl installation.
     The generated Makefile uses the file $PREFIX/lib/tclConfig.sh that was left
     by the make of tcl for most of its configuration parameters.

     The Makefile generates pkgIndex.tcl files that are compatible with
     tcl7.6.   If you are using tcl7.5 then you will need to edit
     $PREFIX/lib/pkgIndex.tcl by hand.

 On Macintosh

     No project file is provided on Macintosh platforms for now. However the
 source code is written in portable C and uses no system-specific calls, only
 the cross-platform Tcl API. Thus porting to MacOS should be as easy as
 creating a proper project file for your favorite environment (eg. MPW or
 CodeWarrior). Feel free to contribute any Macintosh port, be it project
 files or compiled binaries for various architectures.

 Using the package
 -----------------

 To use the package, simply add "package require dictionary" to your scripts. It
 will register a new command "::dictionary" in the global namespace. This command
 in turn provides a number of subcommands that operate on dictionary variables
 and objects.

 List of subcommands
 ----------------

     "add",          "array",      "create",        "exists",
     "foreach",      "get",        "merge",         "names",
     "set",          "size",       "subtract",      "unset"

  * Dictionary creation

     They build new dictionary objects.

     dictionary create ?list?
     dictionary create ?key value ...?

     Return a new dictionary initialized with the specified
     arguments, either inline:

         set d [dictionary create 1 foo 2 bar]

     or as one even-sized list:

         set d [dictionary create [list 1 foo 2 bar]]

     Dictionaries can be used as an even-sized list:

         set d2 [dictionary create $d]

     But in this case it is faster to do:

         set d2 $d

     "dictionary create" is similar to the "list" command.

 * Dictionary value access

     These are immutable methods and thus return new objects from existing ones,
     like concat or lrange.

     dictionary size dict

     Query size of dictionary.

     dictionary get dict pattern

     Return a new dictionary from selected elements of another one.

     dictionary exists dict keyName

     Return whether the given key exists in the dictionary.

     dictionary names dict ?pattern?

     Return a list of keys that match the given pattern. If no pattern
     is specified, return all the keys.

     dictionary merge dict dict
     dictionary merge dict ?key value ...?

     Return a new dictionary made of the union of both dictionaries

     dictionary substract dict dict
     dictionary substract dict ?key value ...?

     Return a new dictionary made of the first dictionary elements
     minus the second's

 * Dictionary variable access

     These are similar to set or lappend in the sense that they alter the value
     of a variable.

     dictionary set varName keyName ?newValue?

     Query or set the value of an element named keyName in
     dictionary variable varName.

     dictionary unset varName keyName ?keyName ...?

     Unset elements with the given key names in dictionary variable
     varName .

     dictionary add varName key value ?key value...?
     dictionary add varName list

     Add specified elements to dictionary variable varName.
     Here list can also be a dictionary.

 * Dictionary iteration

     dictionary foreach {keyName valueName} ?{keyName valueName} ...? command

     Iterate over a dictionary's keys and values. This is very similar to the
     "foreach" Tcl command, except that it needs exactly two variables to be
     specified for each dictionary. Moreover, it causes no type shimering
 (dictionaries are not converted to lists).

 * Dictionary interface to arrays

     These 2 methods don't provide extra functionality over existing array
     get/set methods, but the binary extension will provide optimizations given
     that array methods expect lists and thus may create object type shimmering.
     Dictionary methods won't create shimmering.

     dictionary array get arrayName ?pattern?

     Return a new dictionary with elements of array arrayName.
     An optional pattern is used to restrict elements by key.

     dictionary array set arrayName dict
     dictionary array new arrayName dict

     Fill array arrayName with dictionary dict's elements. The
     "new" form unsets any existing variable first.

 --
 Frédéric BONNET                        frederic.bonnet@ciril.fr
 ---------------------------------------------------------------
 "Theory may inform, but Practice convinces"
                                                     George Bain