Can some explain what is happening here?

Wayne Cuddy

unread,

Mar 31, 2010, 4:01:57 PM3/31/10

to

On this page: The Performance http://wiki.tcl.tk/348
This section: A fast in-place list update scheme.

Contains this code:

proc K {x y} {set x}
set theList [lreplace [K $theList [set theList {}]] 7 42]

Can someone explain to me how this works and why it's called "in-place"
it stills seems to me like we're allocating a new list and returning it
as the result. But perhaps I'm not understanding the title.

Thanks,
Wayne

Alexandre Ferrieux

unread,

Mar 31, 2010, 5:45:27 PM3/31/10

to

On Mar 31, 10:01 pm, Wayne Cuddy <wcu...@cox.net> wrote:
> On this page: The Performancehttp://wiki.tcl.tk/348

The so-called K combinator allows to write in a single function call
the extraction of a variable's value *and* any side-effect, returning
the value. If this side-effect erases the variable (which is the case
here), the net effect of the whole [K ...] construct is to yield the
former value of the variable as a "free-floating" value, ie whose only
reference in the system is at this very spot. In Tcl internals this
means a refcount of 1, or "unshared value".

Now passing such an unshared value to some optimized List operations
like [lreplace] or [lrange] allows to do things in-place: basically
the list op "consumes" this value (and nukes it since it is the last
reference) and generates a fresh one, which is indistinguishable from
"modifying" it in-place and returning it.

An alternative to [K $x [set x {}]] is the "K-free K" idiom:

$x[unset x]

here the idea is to "concatenate" the extracted $x value with the
empty "result" of [unset x], having the desired side effect and
unshared result. The key here is that the Tcl compiler is smart enough
to detect that we're concatenating the empty string, and just use $x
without spoiling its internal representation.

-Alex

Alexandre Ferrieux

unread,

Mar 31, 2010, 5:48:34 PM3/31/10

to

On Mar 31, 11:45 pm, Alexandre Ferrieux <alexandre.ferri...@gmail.com>
wrote:

>
> The key here is that the Tcl compiler is smart enough
> to detect that we're concatenating the empty string, and just use $x
> without spoiling its internal representation.

Correction: not "the Tcl compiler", but "the Tcl concatenation
operator", be it compiled or not.

-Alex

Wayne Cuddy

unread,

Apr 1, 2010, 12:20:25 PM4/1/10

to

Once again, thanks for the explanation Alex!

Be nice if the wiki contained your explanation which details why it is
actually faster instead of simply stating it so.

Thanks,
Wayne

Alexandre Ferrieux

unread,

Apr 1, 2010, 1:01:53 PM4/1/10

to

On Apr 1, 6:20 pm, Wayne Cuddy <wcu...@cox.net> wrote:
>
> Be nice if the wiki contained your explanation which details why it is
> actually faster instead of simply stating it so.

Just added a link to this thread on the page, since the other link is
broken.

-Alex

Kevin Kenny

unread,

Apr 2, 2010, 11:49:30 AM4/2/10

to

Alexandre Ferrieux wrote:
> An alternative to [K $x [set x {}]] is the "K-free K" idiom:
>
> $x[unset x]
>
> here the idea is to "concatenate" the extracted $x value with the
> empty "result" of [unset x], having the desired side effect and
> unshared result.

A nit: That idiom also introduces considerable overhead in deleting
and recreating the variable 'x'. Preferable for "K-free K" is:

$x[set x {}]

--
73 de ke9tv/2, Kevin

Alexandre Ferrieux

unread,

Apr 2, 2010, 12:04:26 PM4/2/10

to

On Apr 2, 5:49 pm, Kevin Kenny <kenn...@acm.org> wrote:
>
> A nit: That idiom also introduces considerable overhead in deleting
> and recreating the variable 'x'. Preferable for "K-free K" is:
>
> $x[set x {}]

Very nice indeed, since we're after speed in the first place !
Thanks Kevin.

-Alex