[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.
Arjen Markus You are not satisfied quickly, are you? :-) Well, the whole model must be elaborated a bit, as now it will work only for examples structured in the same way as the original - pairs of pairs of elements and the like. But all references are stored as data, so when a reference variable gets set or unset, you may register this event and do a bit of cleaning up.
davidw - no, because I know I'm right;-) Basically what you are doing, in a clever way, is building your own memory system on top of everything else, which is neat, but the point of a higher-level language is that memory management gets done for you. You shouldn't have to build a whole new system. I think that feather will resolve some of these problems.
Arjen Markus Yes, I realise that it would be a lot of work, I had thought of a quick implementation like:
proc GC { } {
if { [day_of_week] != "wednesday" } {
puts "No garbage collected today!"
} else {
puts "We are out on an extended lunchbreak"
}
}but that is just a feeble attempt to a joke. Still, if feather might solve that, why not try and revive that? I think I heard from Paul Duffin that it never came past a bunch of ideas.