[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 LIST):
======
proc cons {a b} {list $a $b}
proc car {p} {lindex $p 0}
proc cdr {p} {lindex $p 1}
proc LIST args {
    if {![llength $args]} {
        return {}
    } else {
        return [cons [lindex $args 0] [LIST {*}[lrange $args 1 end]]]
    }
}
======
Then "LIST 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 LIST 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 to make it a circular list. 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 [LIST 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.

Ironically (given that Tcl is usually considered an [imperative programming] language), by using only pure [functional programming], we ensure that no assignments or copies are performed, and so the lack of references no longer poses a problem and the linked lists presented here behave identically to [Lisp]'s.

<<categories>>Data Structure