Re: linked lists in Tcl, part II.

Peter da Silva (
Tue, 18 Oct 1994 00:53:01 GMT

In article <37ttid$>,
Adam Sah <asah@ginsberg.CS.Berkeley.EDU> wrote:
> I have received independent pieces of email from Tom Tromey and Matt Dillon
> pointing out an error in my analysis of Tcl's ability to support linked
> lists. In forming my response, I concentrated on the plethora of posts
> attempting to claim that Tcl lists are the same as linked lists; in
> fact, I failed to consider Tcl's hash tables properly, on which both
> authors use their counterexample-based arguments. However,
> both proposed designs fail on several accounts: first, they don't take into
> accounts the memory mamagement issues involved (ie. leaking memory).

Neither do dozens of other languages that have "real" linked lists.

> Second, they don't consider the scoping issues (ie. given a "reference",
> can I really access my array element?).

I don't see why they need to address that issue at all. Being able to add the
ability to *protect* accesses by means of scoping is an advantage, not a

> Lastly, they neglect the detail
> that sublist creation in a hash table implementation is no longer O(1)
> in time complexity.

Neither is pointer dereferencing in modern VM systems. The scale factor is
smaller in that case, but it's still there.

In addition, you completely miss the point of Tcl not having "real" pointers:

> For example, this is the
> reason Tcl doesn't have "pointers" or other references; if it did, you'd
> quickly run into cases when you couldn't trivially reclaim unreachable data.

The reason Tcl doesn't have "pointers" is because it has no types. Untyped
pointers are inherently dangerous.

Tcl *does* have garbage collection for the objects Tcl manages. It's possible
to build structures that defeat that (such as explicit lists) but that's also
true in lisp:

Reclaimer spare that tree!
Take not a single bit!
It used to point to me...
Now I'm protecting it!

> - how do I return a linked list as the return value from a proc?

Return the name of the array and the name of the head element.

> how do I return a sublist as the return value from a proc?


> - if a locally-scoped linked list [...]

If two lists have references to each other they must be in the same array
and this have the same scope. This is an advantage, not a disadvantage.

> Second, in Tromey's proposal, we use the STRING names of linked lists as
> references to them. But what about a function whose return value is an
> element of a linked list scoped locally to that function?

Doctor, it hurts if I do this!

If you want to share indexes, use a global array with a swizzled name.

(lots of stuff not having anything to do with linked lists deleted... if
you want to attack Tcl for not having closures I'd accept that as a
valid complaint, but it's got nothing to do with linked lists)

No question but that real lisps are more powerful than this bastard child
of lisp and awk, but for what it does it does a better job than either
parent. Which is all you need to ask of it.

> # no reasonable way to check if "l" is already something other than an array
> # in the caller's scope.

Try the "info" command. You can upvar and then use info.

> At the high level, it is naive and dangerous to try to oversimply the
> problems here.

So, dear boy, why the hell do you insist on doing so? You create a straw man
and attack that, then bring up bogus arguments when people point that out,
and finally hide some *real* problems down in the body of yet another straw
man message. Do you have a point to all this or are you just trying to
confuse people?

> The fact that the language theorists haven't packaged
> their work with pleasing syntax

I LIKE the syntax of lisp. You can't get rid of the syntax without breaking
the semantics... Tcl itself is a perfect example of that. And Tcl's syntax
can't safely be softened without breaing *its* semantics... and so on down
the line.

Peter da Silva                                            `-_-'
Network Management Technology Incorporated                 'U`
1601 Industrial Blvd.     Sugar Land, TX  77478  USA
+1 713 274 5180                       "Hast Du heute schon Deinen Wolf umarmt?"