Backtracking in the Icon language
One of the more unusual constructs in Icon is the reversible assignment operators "<-" and "<->". Here is a posting from comp.lang.icon that sheds some light on the use of these operators.
From: firstname.lastname@example.org (Marc Espie) Newsgroups: comp.lang.icon Subject: Re: How to think about Icon? Date: 10 Apr 1996 13:44:12 GMT Organization: Ecole Normale Superieure, Paris Lines: 90 Distribution: inet Message-ID: <email@example.com> References: <firstname.lastname@example.org> NNTP-Posting-Host: bireme.ens.fr In article <email@example.com>, Peter Seebach <firstname.lastname@example.org> wrote: >I've made periodic stabs at learning icon for some time now, >and I've come to the conclusion that it's completely unlike >the languages I've learned previously. In particular, I have >no good mental model for backtracking, so I get confused by >programs which do it. This makes Icon hard for me to take >advantage of. :) > >What kind of conceptual model do you use for programming in >Icon? How do you use it differently from "simple" procedural >languages, like C or Perl? > I don't know how it works for other people, but `iterator' is the key for me. The classical problem that is difficult to work in other languages is graph traversal. In C, you usually will code a given graph traversal algorithm that takes a call back function as a parameter---this call back will be called with each vertex you encounter. In Icon, you will design a generator that suspends every vertex you encounter. Up to the calling program to decide what to do with the vertex. This goes farther than it seems. For instance, I usually don't hardcode my definition of a graph, but use a generator that gives me the neighbors of a given neighbor instead. Sample Connected Component program (this is what I actually use in practice): procedure build_cc(v, neighors, para, cc) local todo todo := [v] /cc := set() # initialize set if needed insert(cc, v) # cc initially holds v while v := pop(todo) do every neighbor := neighbors(v, para) do member(cc, neighbor) | (insert(cc, neighbor) & put(todo, neighbor)) return cc end As far as backtracking goes, the sanest way is perhaps to just consider it as a kind of shorthand (at first): all the logical structure and all the C variables are there, you just don't have to write it down explicitly, i.e., going from every i:= 1 to 10 do write(i) to every write(1 to 10) or if (i = 0) | (i = 1) to if i = (0|1) isn't that difficult. Then you can go farther to recursive generators and such intricate stuff. This is the same conceptual leap as recursive invariants in functional languages. The only thing you have to watch for is the precise semantics of failure/multiple success... If I counted all the times I had a generator resume on me when I wasn't expecting it, reverse the first result, and finally fail---\1 is very handy at times, or all these procedural functions that forgot to return anything and just failed, simply ! Another fun example: this one generates all permutations of a given list, and is quite nice to understand generator resumption. procedure do_permute(l, i, n) if i >= n then return l else suspend l[i to n] <-> l[i] & do_permute(l, i+1, n) end procedure permute(l) suspend do_permute(l, 1, *l) end I should add that, again, this is a real life example. Icon code tends to be very compact, elegant, and not so easy to understand at times :-) If you haven't already, go out and buy the Icon programming language book, by Griswold. This is a very nice book, that gives lots of applications of the generator/backtracking paradigm. -- [nosave]<http://www.eleves.ens.fr:8080/home/espie/index.html> microsoft network is EXPLICITLY forbidden to redistribute this message. `Moon purismu powa, make up.... Tsuki ni kawatte, oshiokiyo !' Marc Espie (Marc.Espie@ens.fr)
John Shipman, email@example.com
Last updated: 1996/04/11 05:32:21 UT