[KBK] (25 April 2002) -
The fact that Tcl allows new control structures to be defined at the script level by means of [uplevel] and [upvar] has led to its being a popular platform for prototyping search algorithms that require backtracking.  The general idea is that you can program a proc that makes a nondeterministic choice, and evaluates a script to follow through on the consequences of that choice.

The Wiki offers one toy example, used for [Solving cryptarithms] like

    S E N D
  + M O R E
 -----------
  M O N E Y

[RS] examines some of the possibilities in [Playing Prolog] and [Playing predicate logic].  [Searching a star in space] is also interesting, as is [Neil Madden]'s [State Space Searching in Tcl].

Joseph Konstan and his grad students (notably Alex Safonov and Sunanda Iyengar) did a tremendous amount of related work in the early days of Tcl.  Much of their system was based on imaginative uses of the [trace] command rather than on a nondeterministic-choice procedure.
Their first paper is abstracted at [http://www.usenix.org/publications/library/proceedings/tcl95/iyengar.html], but alas, the full text there appears to be damaged.  There is also a project page at [http://www.cs.umn.edu/Research/GIMME/tclprop.html].

Dayton Clark and David Arnow implemented code that is a more direct inspiration for [Solving cryptarithms].  In their paper, [http://www.usenix.org/publications/library/proceedings/tcl96/clark.html], they introduce a more general Tcl-based framework for constraint management and backtracking.

See also [non-deterministic search]

[[rest of the community is invited to add references and commentary!]]

----
[[
[Category Control structure]
]]