[fut] In [Lisp], the cons function creates cells with two fields, customarily referred to as car and cdr. Lisp lists are cons cells whose cdr field points to the rest of the list. A special empty list value goes into the cdr of the last cell to indicate the end of the list. Since cons cells are always handled by reference, this makes Lisp lists [linked lists], with car holding data and cdr acting as the "next" pointer.

Cons can be had easily in Tcl (here Lisp's list function is renamed leest):
======
proc cons {a b} {list $a $b}
proc car {p} {lindex $p 0}
proc cdr {p} {lindex $p 1}
proc leest args {
    if {![llength $args]} {
        return {}
    } else {
        return [cons [lindex $args 0] [leest {*}[lreplace $args 0 0]]]
    }
}
======
Then "leest 1 2 3" returns "1 {2 {3 {}}}". Because of Tcl's [copy-on-write] semantics, such lists are true linked lists in that only pointers to the arguments of leest reside in the list it creates, with no copying involved. However, since Tcl has no [reference]s, we can't operate on linked lists the same way we do in Lisp. The following [Scheme] fragment:
======
> (define ls (list 1 2))
> (set-cdr! ls ls)
> ls
1 1 1 1 1 1 1...
======
cannot be had in Tcl. The second command makes ls's cdr point to ls itself. Here's what happens if we try to do the same in Tcl:
======
% proc set-cdr! {pName v} {upvar 1 $pName p; lset p 1 $v}
% set ls [leest 1 2]
1 {2 {}}
% set-cdr! ls $ls
1 {1 {2 {}}}
======
The problem is the second argument to set-cdr! is not a reference but an actual list. Before ls is modified, Tcl creates a new copy of it, and the old copy becomes the cdr of the new list.

<<categories>>Category Data Structure