[[[RMS] faults Tcl for its linked-lists-lessness.  Explain
what linked lists are, who RMS is, and Tcl perspective--mostly that Tcl doesn't need 'em.]]

[Arjen Markus] I do not know who RMS is, but "woe , ye of little imagination", Tcl lists can be used as linked lists - if you regard a linked list as some abstract data structure (apart from the implementation!). I regard his/her statement as an example that most people can not distinguish implementation and concept!

[RS] RMS is Richard M Stallman, a famous programmer in the GNU scene, but not enthusiastic about Tcl. (See [Who says Tcl sucks...]) I also have problems understanding the need for linked lists - Tcl's are contiguous in memory, so the benefit of links, i.e. iterating over it, is easily reached with [foreach]. OTOH, recursing over lists involves copying in Tcl, so real linked lists like LISP's CAR/CDR also have their advantages.

[LV] I'd say the issue is likely this - people used to algorithmic solutions requiring specific data structures, such as structures, linked lists, etc. find it difficult to envision how to efficiently implement such solutions in Tcl with only flat lists and hash tables.

[davidw] the real problem is not linked lists in and of themselves, but the lack of references.  Linked lists aren't really all that necessary in Tcl for the simple case, but references allow you to easily construct more complex data structures.

[Arjen Markus] Can this not be achieved in a very similar way as in Scheme (the LISP dialect I am gradually learning because of the [SICP] book)? For instance:

   set complex_data_struct {A {B C {D E {F G}}}

Such a structure (lists within lists) allows one to define recursive lists as well:

   set recursive_list {A {B {C {D {E {F {G}}}}}}

[davidw] - maybe it's visually similar, but what's going on underneath is not the same.  Have a look at this scheme code, and try and accomplish the same thing in Tcl:

    > (define a (list 1 2))
    > (define b (list 3 4))
    > (define l1 (list a b))
    > l1
    ((1 2) (3 4))
    > (set-car! b 30)
    > l1
    ((1 2) (30 4))

As far as I know, it's not possible.  Everything gets turned into a string at some point, so references don't get preserved.

[Stephen Trier] - back in the dark ages, I wrote LISP-style linked list routines in BASIC that used arrays.  The internal pointers were array indexes.  One could do the same in Tcl with [lset] or an array.

---- 

[Arjen Markus] It was a bit of a challenge, but here it is - with Tcl lists!

   #
   # Simple data references
   #
   set ::referenced_data {}

   proc dataref { data } {
      set idx [lsearch $::referenced_data $data ]
      if { $idx < 0 } {
         set idx [llength $::referenced_data]
         lappend ::referenced_data $data
      }
      return $idx
   }

   proc getdata { ref } {
      lindex $::referenced_data $ref
   }

   proc replacedata { ref new } {
      set ::referenced_data [lreplace $::referenced_data $ref $ref $new]
   }

   proc reflist { a b } {
      dataref [list "REF" $a $b]
   }

   proc set-car! { aref b } {
      set adata   [getdata $aref]
      set refcdr  [lindex $adata 2]
      set newdata [list "REF" $b $refcdr]
      replacedata $aref $newdata
   }

   proc print-reflist { aref } {
      set print_data {}
      set adata [getdata $aref]
      if { [lindex $adata 0] == "REF" } {
         foreach {dummy car cdr} $adata {
            append print_data "( " [print-reflist $car] " " \
               [print-reflist $cdr] " )"
         }
      } else {
         append print_data [getdata $aref]
      }
      return $print_data
   }

   set ref1 [dataref "A"]
   set ref2 [dataref "B"]
   set ref3 [dataref "C"]
   set ref4 [dataref "D"]

   set alist [reflist $ref1  $ref2 ]
   set blist [reflist $ref3  $ref4 ]
   set clist [reflist $alist $blist]

   puts $alist
   puts $blist
   puts $clist
   puts [print-reflist $alist]
   puts [print-reflist $blist]
   puts [print-reflist $clist]

   set-car! $alist $ref3
   puts $clist
   puts [print-reflist $clist]

Note that the whole trick is that the data in the list are either tagged and hence identifiable as a reference (or better a pair of references) or not, in which case they are ordinary data. References are regarded as ordinary data and stored in the global list that holds all information. 

It can undoubtedly be done more elegantly, but that is not the point: I have proven (I hope) the concept of referenced data in pure Tcl.

[davidw] - now add garbage collection to it.