Backtracking in the Icon language
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: espie@bireme.ens.fr (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: <4kgdvc$1v6@nef.ens.fr>
References: <4kgc8d$j7h@solutions.solon.com>
NNTP-Posting-Host: bireme.ens.fr
In article <4kgc8d$j7h@solutions.solon.com>,
Peter Seebach <seebs@solon.com> 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)