## cons

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 references, 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.

 Category Data Structure