Re: [TCLCORE] Empty list is not a list -- using twoPtrValue for NULL type

[Alexandre F. <ale...@gm...>]

On 1/17/08, miguel sofer <mig...@gm...> wrote:
> Alexandre Ferrieux wrote:
> >
> > Look near the end, I have tried to illustrate the script-level aspects:
> > http://groups.google.com/group/comp.lang.tcl/tree/browse_frm/thread/b6c26a33f5ebd3e0/c8c452ad6386d7b2?hl=en&rnum=91&_done=%2Fgroup%2Fcomp.lang.tcl%2Fbrowse_frm%2Fthread%2Fb6c26a33f5ebd3e0%3Fhl%3Den%26#doc_5966ecb98c4ad8a6
>
> Not what I need right now :( That there talks a lot about the
> implementation aspects - Tcl_Objs and stringReps and generation counters
> and whatHaveYou.
>
> What I am missing is the perspective of the script writer - the changes
> (if any) to Tcl.n, the manpage for whatever new commands you'll define,
> manpage changes elsewhere.
>
> IOW, I cannot process the "how do we get there" until I really grokked
> where "there" is. Not requesting that you write all of that s**t for me,
> but could use some help in getting the big picture.

OK, sorry for the delay :-) Here it goes.
Sorry in advance for the obvious introduction, but let's start from
the basics to be sure.

Mutability - principle
-----------------------------

Values in Tcl, be they "scalars" like integers or strings, or
"containers" like lists or dicts, are so far strictly independent from
one another.  Hence, in

       # assuming no trick like upvar #0 x y
       set x [function call returning some value]
       set y $x
       do anything to y

the $x value will *never* be touched by whatever is done to the
variable y, including "in-place" operations like [lappend], [lset],
etc. In other words, as seen from the script level, values can just be
copied, never passed "by reference".

Now let's introduce a special state for Tcl values: "mutable".
We define it by the fact that all the usual "copy" operations are now
turned into "pass a reference". Thus:

       set m [function call returning a mutable value]
       set n $m
       do something in-place to m (or $m)
       # $n is updated too !

Mutability and Containers
-------------------------------------

If a mutable scalar can be imagined, a mutable container is much more
interesting.
Indeed, if a container contains a mutable value, we must define what
happens to the container's overall value when the child is mutated.
Two options are a priori possible:
   (a) The container's value stays unchanged. This is equivalent to
having an immutable "snapshot" of the child inserted into the
(immutable) container.
   (b) The container's value is updated too. This qualifies the
container as mutable itself.
Thus, arbitrarily deep trees (or even acyclic graphs) or mutable
containers can be built. Any mutation inside them is defined to
"propagate" up. This implies that mutability is an *increasing*
function wrt the order of container inclusion: the only forbidden case
is an immutable container containing a mutable value.

So, we must define what happens in case of [list $m] when m is mutable.
The options are:
  (a) Snapshot. An immutable list is built containing an immutable copy of $m.
  (b) Silent contagion. The list being built is promoted to mutable state
  (c) Enforced contagion. The call raises an error. To do the same,
one must use a specific mutable list creator, or add $m to an already
mutable empty list.

I have a slight preference for (c) as it helps people maintain a clear
boundary between mutables and immutables in their programs, which is
IMO a Good Thing considering that mutability basically violates what
was previously nearly a fundamental principle of Tcl.

Mutability and existing commands
-------------------------------------------------

Defining mutability as a *state* of existing Tcl values has one
notable advantage: we may reuse many existing commands, only adapting
their behavior slightly to respect the new "reference" semantics
instead of the old "copy" mechanism when writing. This makes [lappend]
[lset] and [dict set] the canonical tools to update mutable lists and
dicts. Also, [lindex] and [dict get] need no modification to be the
natural read-only accessors.

Now, we need primitives to change the mutability state. This is done with

             set l [list 1 2 3] ;# $l is immutable
             set m [mutable $l]  ;# $l is untouched, still immutable

and

             set l2 [immutable $m] ;# $l2 is a snapshot or $m at this spot

A deep variant of [mutable] is handy to build nested mutables in one step:

             set m [mutable -deep [list 1 2 [list 3 4]]]

it is needed because

             set m [mutable [list 1 2 [mutable [list 3 4]]]]

raises an error trying to do

             list 1 2 [mutable [list 3 4]]

by the monotonicity rule stated above.

An alernative is to define one-step mutable creators [mlist] and [mdict]:

             set m [mlist 1 2 [mlist 3 4]]

Applications of Mutability
------------------------------------

Apart from aesthetic considerations, mutability also helps define
modular in-place algorithms. For example, a large mutable list of
mutable dicts can be maintained, and from time to time pass one of its
dicts to a an in-place manipulation function that doesn't know (nor
wants to) about the nesting:

            foreach d $mutable_list_of_mutable_dicts {
                  transitive_closure d
            }

Part of the beauty of the idiom above is that "transitive_closure"
takes "d" and not "$d": its implementation may not use mutability at
all. Instead it [upvar]s a variable "d" , and believes it modifies
in-place the *variable*. The fact that it also modifies the value is
here a secret well kept by the caller.

Notice that the same is doable in Tcl today:

            for {set i 0} {$i<$n} {incr i} {
               set d [lindex $m $i]
               lset m $i nope
               transitive_closure d
               lset m $i $d
            }

but writing this implies to go down to extra knowledge of Tcl
internals (COW and refcounts), is not quite as elegant and fast, and
scales up poorly (imagine a 4-level list of dicts of lists of dicts).

(Miguel, may I ask your permission to have a bit of sleep before continuing ?)

-Alex