Next / Previous / Index / ITC Help System / Publications / Site map / NM Tech homepage

Backtracking in the Icon language

Tech Computer Center logo

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)

Next: Writing CGI handlers with the Icon language
See also: The Icon trick bag
Site map
Index: Keyword index to help pages
Help: New Mexico Tech Information Technology and Communications: Help System
ITC Publications
To report a problem: File a ticket
Send mail to the User consultant on duty or call them at 575-835-5437
Home: About New Mexico Tech

John Shipman, john@nmt.edu
Last updated: 1996/04/11 05:32:21 UT
URL: http://www.nmt.edu/tcc/help/lang/icon/backtrack.html
QR two-dimensional bar code