Check-in [aba779d300]

Login
Bounty program for improvements to Tcl and certain Tcl packages.
Tcl 2019 Conference, Houston/TX, US, Nov 4-8
Send your abstracts to tclconference@googlegroups.com
or submit via the online form by Sep 9.

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Added TIP 513 for Florian Murr
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA3-256:aba779d30057321aa10787f2c29362f644cfcacfa70eca46d3d4bc2ace95cc65
User & Date: dkf 2018-07-07 10:03:07
Context
2018-07-07
10:04
Fix silly editorial error check-in: 0918a6150f user: dkf tags: trunk, minor change
10:03
Added TIP 513 for Florian Murr check-in: aba779d300 user: dkf tags: trunk
09:03
Add [myclass] to documented changes. check-in: 4b1c4395c1 user: dkf tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Added attach/513/agendas.tcl.

            1  +# ****************************************************************************
            2  +# Synopsis:
            3  +#     arrayHasElem ?options? arrName ?keyVar? ?valueVar?
            4  +# 
            5  +# Options:
            6  +#     -remove
            7  +#         does "unset arrName($key)" iff a key has been found.
            8  +#     --
            9  +#         end of option list
           10  +# 
           11  +# Take any key (the very first) and assign it to keyVar and its value to valueVar.
           12  +# Return value is 1 iff an element has been found and 0 otherwise.
           13  +# ****************************************************************************
           14  +
           15  +proc arrayHasElem {args} {
           16  +    set optli [list -remove --]
           17  +    set rm 0
           18  +    for {set i 0} {$i < [llength $args]} {incr i} {
           19  +        if {[string index [set a [lindex $args $i]] 0] ne "-"} break
           20  +        set a [::tcl::prefix match -error {-level 1} $optli $a]
           21  +        switch -- $a {
           22  +            -remove { incr rm  }
           23  +            -- { incr i;  break }
           24  +        }
           25  +    }
           26  +    # --- $i is on the first non-option.
           27  +    lassign [set akv [lrange $args $i end]] arrName aKey aValue
           28  +    switch [llength $akv] {
           29  +        0 { return -code error "missing: arrName" }
           30  +        1 { upvar 1 $arrName arr }
           31  +        2 { upvar 1 $arrName arr $aKey key }
           32  +        3 { upvar 1 $arrName arr $aKey key $aValue value }
           33  +        default { return -code error "too many arguments: $akv" }
           34  +    }
           35  +    # payload:
           36  +    if {![info exists arr]} { return 0 }
           37  +    set id [array startsearch arr]
           38  +    set nm [array nextelement arr $id]
           39  +    array donesearch arr $id
           40  +    if {$nm eq ""} { ;# check: nothing-found or ""-is-a-valid-key; (annoying!)
           41  +        # --- already 'donesearch' => no [array anymore] any more.
           42  +        if {![info exists arr([list])]} { return 0 }
           43  +    }
           44  +    set key $nm
           45  +    set value $arr($key)
           46  +    if {$rm} { unset arr($key) }
           47  +    return 1
           48  +}
           49  +
           50  +# ****************************************************************************
           51  +apply {{} {
           52  +    set dct [namespace ensemble configure ::array -map]
           53  +    if {[dict exists $dct haselem]} return
           54  +    dict set dct haselem ::arrayHasElem
           55  +    namespace ensemble configure ::array -map $dct
           56  +}}
           57  +
           58  +# ############################################################################
           59  +# ****************************************************************************
           60  +# Synopsis:
           61  +#     dHaselem ?-remove? dictVar ?keyVar? ?valueVar?
           62  +#    
           63  +# ****************************************************************************
           64  +
           65  +proc dHaselem {args} {
           66  +    set rm 0 ;# option-handling:
           67  +    switch [llength $args] {
           68  +        0 { return -code error "dict argument missing" }
           69  +        1 { upvar 1 [lindex $args 0] d }
           70  +        default {
           71  +            if {[string index [set a [lindex $args 0]] 0] eq "-"} {
           72  +                switch -- [::tcl::prefix match {-remove} $a] {
           73  +                    -remove {
           74  +                        incr rm
           75  +                        set args [lrange $args 1 end]
           76  +                    }
           77  +                }
           78  +            }
           79  +            lassign $args dvar keyVar valueVar
           80  +            switch [llength $args] {
           81  +                0 { return -code error "dict argument missing" }
           82  +                1 { upvar 1 $dvar d }
           83  +                2 { upvar 1 $dvar d  $keyVar key }
           84  +                3 { upvar 1 $dvar d  $keyVar key  $valueVar val }
           85  +                default { return -code error "unknown arguments: $args" }
           86  +            }
           87  +        }
           88  +    }
           89  +    # payload:
           90  +    if {![info exists d]} { return 0 }
           91  +    dict for {key val} $d {
           92  +        if {$rm} { dict unset d $key }
           93  +        return 1
           94  +    }
           95  +    return 0
           96  +}
           97  +
           98  +# ############################################################################
           99  +apply {{} {
          100  +    set dct [namespace ensemble configure ::dict -map]
          101  +    if {[dict exists $dct haselem]} return
          102  +    dict set dct haselem ::dHaselem
          103  +    namespace ensemble configure ::dict -map $dct
          104  +}}
          105  +
          106  +# ############################################################################
          107  +# ****************************************************************************
          108  +# Synopsis:
          109  +#     lhaselem ?options? listVar ?valueVar?
          110  +#    
          111  +# Options:
          112  +#     -index index
          113  +#         only look at the required index
          114  +#     -remove
          115  +#         does remove the item iff it has been found.
          116  +#     --
          117  +#         end of option list
          118  +# 
          119  +# Return value is 1 iff an element has been found and 0 otherwise.
          120  +# ****************************************************************************
          121  +
          122  +proc lhaselem {args} {
          123  +    set optli [list -index -remove --]
          124  +    set index end
          125  +    set rm 0
          126  +    switch [llength $args] {
          127  +        0 { return -code error "wrong number of arguments" }
          128  +        1 { upvar 1 [lindex $args 0] livar }
          129  +        default {
          130  +            for {set i 0} {$i < [llength $args] - 1} {incr i} {
          131  +                if {[string index [set a [lindex $args $i]] 0] ne "-"} break
          132  +                set a [::tcl::prefix match -error {-level 1} $optli $a]
          133  +                switch -- $a {
          134  +                    -index  { set index [lindex $args [incr i]] }
          135  +                    -remove { incr rm  }
          136  +                    -- { incr i;  break }
          137  +                }
          138  +            }
          139  +            # --- $i is on the first non-option.
          140  +            if {$i < [llength $args] -2} {
          141  +                return -code error "wrong number of arguments"
          142  +            } elseif {$i == [llength $args] -2} {
          143  +                upvar 1 [lindex $args end-1] livar  [lindex $args end] val
          144  +            } else {
          145  +                upvar 1 [lindex $args end] livar
          146  +            }
          147  +        }
          148  +    }
          149  +    # payload:
          150  +    if {![info exists livar]} { return 0 }
          151  +    set len [llength $livar]
          152  +    set index [string map [list end [incr len -1]] $index]
          153  +    set index [expr $index]
          154  +    if {$index < 0 || $index >= [llength $livar]} { return 0 }
          155  +    set val [lindex $livar $index]
          156  +    if {$rm} { set livar [lreplace $livar $index $index] }
          157  +    return 1
          158  +}

Changes to index.json.

cannot compute difference between binary files

Changes to index.md.

   102    102   <th>#</th>
   103    103   <th>Type</th>
   104    104   <th>Tcl Version</th>
   105    105   <th>Status</th>
   106    106   <th>Title</th>
   107    107   </tr></thead><tbody>
   108    108   
          109  +<tr class='project projectdraft projectdraft87 project87'>
          110  +<td valign='top'><a href='./tip/513.md'>513</a></td>
          111  +<td valign='top'>Project</td>
          112  +<td valign='top'>8.7</td>
          113  +<td valign='top'>Draft</td>
          114  +<td valign='top'># TIP 512: Better support for &apos;agendas&apos; as arrays, dictionaries or lists</td>
          115  +</tr>
   109    116   <tr class='project projectdraft projectdraft87 project87'>
   110    117   <td valign='top'><a href='./tip/512.md'>512</a></td>
   111    118   <td valign='top'>Project</td>
   112    119   <td valign='top'>8.7</td>
   113    120   <td valign='top'>Draft</td>
   114    121   <td valign='top'># TIP 512: No stub for Tcl_SetExitProc()</td>
   115    122   </tr>

Added tip/513.md.

            1  +# TIP 512: Better support for 'agendas' as arrays, dictionaries or lists
            2  +	Author:         Florian Murr <florian.murr@siemens.com>
            3  +	State:          Draft
            4  +	Type:           Project
            5  +	Vote:           
            6  +	Created:        02-Aug-2017
            7  +	Post-History:   
            8  +	Keywords:       Tcl,data structure
            9  +	Tcl-Version:	8.7
           10  +-----
           11  +
           12  +# Abstract
           13  +
           14  +This proposes new commands for Tcl to support efficient dynamically-changing
           15  +data structures.
           16  +
           17  +# Proposal
           18  +
           19  +The word 'agenda' has been chosen for a highly _dynamic collection_ of items,
           20  +i.e. the collection is likely to change all the time - “pulsating”.  (To
           21  +contrast the concept of an agenda with something that is not, think of `array
           22  +startseach'`+ `array nextelement` which abort the operation the very moment
           23  +any change to the array happens.)  Depending on the type of agenda, it has a
           24  +built in order, or not.
           25  +
           26  +Such agendas crop up frequently in practice and Tcl should support them with
           27  +best performance and readability.  All three, better performance, better
           28  +readability and more expressivenes can be achieved simultaneously, as shown
           29  +below.  Most are familiar with agenda-types like “Stack” and “Queue”, which
           30  +can be implemented as a Tcl-list, but sometimes an array or dictionary is more
           31  +appropriate. (For an example consider Huet's unification algorithm)
           32  +
           33  +The most important methods for an agenda are:
           34  +
           35  +1. **check** for (non-)emptiness of the agenda
           36  +2. **put** an item on the agenda
           37  +3. **get** an item from the agenda and optionally remove it
           38  +
           39  +All these operations should be O(1) and/or have maximum C-level performance.
           40  +
           41  +This TIP proposes 3 functions to achieve this goal, with a synopsis close to this (details below):
           42  +
           43  +1. **array haselem** ?**-remove**? _arrVar_ ?_keyVar_? ?_valueVar_?
           44  +2. **dict haselem** ?**-remove**? _dictVar_ ?_keyVar_? ?_valueVar_?
           45  +3. **lhaselem** ?_options_? _listVar_ ?_valueVar_?
           46  +
           47  +Each of these functions checks the existence, gets the element and optionally
           48  +removes it in one step.  The various advantages are examined below.
           49  +
           50  +## Readability Advantages
           51  +
           52  +With **lhaselem** and using **lappend** to put an item on the agenda (in a Tcl
           53  +list in a variable), we can now process the elements in a Stack-agenda stack
           54  +in one single line:
           55  +
           56  +    while {[lhaselem -remove -index end stack item]} {
           57  +        # use $item, lappend, ...
           58  +    }
           59  +
           60  +Likewise a Queue-agenda requires just a single line:
           61  +
           62  +    while {[lhaselem -remove -index 0 queue item]} {
           63  +        # use $item, lappend, ...
           64  +    }
           65  +
           66  +Processing an array-agenda or dict-agenda is just as easy:
           67  +
           68  +    while {[array haselem -remove arr key val]} {
           69  +        # use $key, $val, set, unset, ...
           70  +    }
           71  +
           72  +These one-liners improve readability because their semantics is not scattered
           73  +upon multiple functions, that access the data multiple times and must be
           74  +mentally put together to understand it.  Their semantics is immediately
           75  +obvious, once the new functions are known.  To value how much readability
           76  +improves, consider the “payload” section in each of the prototypical
           77  +implementations (linked below) and compare that to the respective one-liner.
           78  +
           79  +## Expressiveness Advantages
           80  +
           81  +1. **array haselem**. Here we must pause and consider that we have a certain
           82  +   _semantic gap_ with dynamic arrays, i.e. array-agendas: Checking for
           83  +   (non-)emptiness is currently not possible with a simple O(1) operation. The
           84  +   obvious candidate `if {[array size arr]} ` is an O(N) operation. The
           85  +   alternative is using `array startseach`, `array nextelement` + `array
           86  +   donesearch` just to check whether an array is empty or not, but that is not
           87  +   appealing either. These functions are useful for more static collections,
           88  +   not for agendas. Also, typically for array-agendas cropping up in practice
           89  +   is the requirement for “anonymous access”, i.e., we need to get an element
           90  +   of the collection without having to know beforehand which specific element
           91  +   to ask for. The only direct access to array elements is currently
           92  +   `$arr($elem)`, but this is not anonymous, because you have to know `$elem`
           93  +   beforehand. With **array haselem** we gain more expressiveness, because now
           94  +   we can check (non-)emptiness with a single O(1) function call and we can
           95  +   now anonymously access an item in the collection.
           96  +
           97  +2. **dict haselem**. With dicts it is not quite as bad as with arrays, but
           98  +   still we have to employ `dict for` to gain anonymous access to an
           99  +   element. And `dict size` might also not be the best we can do to check for
          100  +   (non-)emptyness, despite being an O(1) operation.
          101  +
          102  +3. **lhaselem**. (see the Stack and Queue example above) 
          103  +
          104  +Anyway, to have a single “atomic” operation that checks the existence, gets
          105  +the item, and optionally removes it from the collection, is a new expressive
          106  +feature.
          107  +
          108  +## Performance Advantages
          109  +
          110  +1. **array haselem**. At the C-level we do not need even a single hash-access
          111  +   to get an element: just pick the first one in the first bucket. And
          112  +   removing it can be done immediately, while we are at it. In contrast, when
          113  +   using current Tcl functions to get an value and remove the key, we need at
          114  +   least `if {[info exists arr]}` to check existence of the array, `array
          115  +   nextelement` to get the key, `$arr($key)` to get the value, and `unset
          116  +   arr($key)` to remove it. These employ 2 or 3 hash-accesses to get the job
          117  +   done, when in fact we need none.
          118  +
          119  +2. **dict haselem**. (c.f. “payload” section in `dHaselem` in the sample
          120  +   code). We need to access the dict only once to check and remove the item,
          121  +   not twice.
          122  +
          123  +3. **lhaselem**. (c.f. “payload” section in `lhaselem` in the sample code). We
          124  +   need to access the list only once to check and remove the item, not twice.
          125  +
          126  +# Prototype Implementation
          127  +
          128  +The [prototype implementation](../assets/513/agendas.tcl) has the desired
          129  +semantics, but does not even come close to the performance desired.  These
          130  +functions have to be implemented in C and take advantage of the internal
          131  +representation to fulfill the proposed performance gains.
          132  +
          133  +# Copyright
          134  +
          135  +This document has been placed in the public domain.