Emulating lisp cons cells in Tcl

Question

A list in lisp is a series of cons cells, but in Tcl, a list is a string with whitespace separating the elements. For translating code from lisp to tcl, one might simply take lisp lists and translate them to Tcl lists. However, this runs into trouble with side effecting cons cells not coming across to the Tcl code. For example, consider this code in lisp:

(setq a (list 1 2 3 4))
(let ((b a)
      (a (cddr a)))
  (declare (special a b))
  (setf (cadr b) ‘b)
  (setf (cadr a) ‘d)
  (print a))
(print a)

;; Results in:
(3 d)
(1 b 3 d)

Is there a Tcl package that would provide a better emulation of lisp lists in Tcl? Does such package offer easy conversion to regular Tcl lists?

What might the above code look like in Tcl using such package?

Answer 1

Lisp cons cells can't be directly modeled as Tcl values because of fundamentally different semantic models. Lisp uses a model whereby values are directly updatable; the value is the memory cell. Tcl uses a different model with values which are conceptually immutable and where there is no difference in principle between any “1 2 3 4” that happens to be lying around from any other; mutable entities in Tcl are variables with names (the name strings themselves are immutable, of course…) This immutability makes sense at the level of simple values, but it extends also to Tcl's lists and dictionaries; mutation operations all either return a new value or update a variable. (The implementation is more efficient than this, using a copy-on-write strategy to preserve the semantic model of immutability while being able to implement things with mutation of the value itself when that is actually known to be semantically equivalent.)

Because of this, you have to construct updatable cons cells as variables. Here's how you might do it:

proc cons {a b} {
    global gensym cons
    set handle G[incr gensym]
    set cons($handle) [list $a $b]
    return $handle
}
proc car {handle} {
    global cons
    return [lindex $cons($handle) 0]
}
proc cdr {handle} {
    global cons
    return [lindex $cons($handle) 1]
}
proc setCar {handle value} {
    global cons
    lset cons($handle) 0 $value
}
# Convenience procedures
proc makeFromList args {
    set result "!nil"
    foreach value [lreverse $args] {
        set result [cons $value $result]
    }
    return $result
}
proc getAsList {handle} {
    set result {}
    while {$handle ne "!nil"} {
        lappend result [car $handle]
        set handle [cdr $handle]
    }
    return $result
}

set a [makeFromList 1 2 3 4]
# Use some local context; Tcl doesn't have anything exactly like Lisp's "let"
apply {a {
    set b $a
    set a [cdr [cdr $a]]
    setCar [cdr $b] "b"
    setCar [cdr $a] "d"
    puts [getAsList $a]
}} $a
puts [getAsList $a]

This produces the expected output (given that Lisp and Tcl have different ideas how a list should be formatted).