Lambda the Ultimate

Just the kind of help I was looking for.

You can find Icon here. It's a woefully overlooked language with some very interesting concepts, e.g. goal-directed evaluation, success or failure instead of a boolean type, generators, and so on. Some of the ideas have wormed their way into more familiar languages; some still have not, but arguably should.

I dunno, I think once you have list comprehensions you have most of what Icon offers, without contaminating the entire program with the possibility of unexpected backtracking.

> I dunno, I think once you have list comprehensions you have most of what
> Icon offers, without contaminating the entire program with the possibility
> of unexpected backtracking.

Backtracking in Icon is never unexpected because the rules are very clearly defined. But what's really clever - and this is something that's far from obvious when you first hear about it - is that Icon's evaluation rules mean that bog-standard expression evaluation work the same as in any other language. What that means is that when you want to use the clever aspects of goal-directed evaluation, they're ready and waiting to serve - but they're not there waiting to bite you on the arse in normal usage.

That said, there is in my opinion one unnecessary flaw in Icon which is that functions without an explicit "return" statement default to returning "fail". That can cause no end of fun, and can cause unintended (but note - not unexpected) backtracking when the programmer forgets to put a return statement in.

Backtracking is certainly unexpected if it was unintended. Let's not be ridiculous.
List comprehensions give you goal directed evaluation. I prefer to use this tool only where I need it instead of wrapping a big backtracking loop around my whole program, ready to unravel havoc whenever I forget where an expression might fail.

I think the point is that once you actually learn a language, it becomes hard to justify calling fundamental aspects of its semantics "unexpected." Would you call backtracking in Prolog unexpected? In that sense, Icon is no different. You don't think or talk about backtracking in Icon because it's part and parcel of goal-directed evaluation. I personally think the point about normal expressions working exactly as you would expect is an excellent one: goal-directed evaluation is really just a generalization of the alternative. Instead of saying "I have to chop this string up into all of its substrings that begin with 'x' in order to find the Nth one," you just say "scan" and it succeeds as many times as it can, which may be zero, one, or more than one.

Generators and list comprehension definitely were the concepts I had in mind from Icon that have made it into better-known languages, but they've done so in a kind of attenuated sense, since these languages exhibit more of a traditional C-style semantics generally, vs. the admittedly more distinct semantics of Icon.

Paul neatly summed up what I was talking about with respect to unexpected and unintended.

With respect to backtracking in Icon, I rather suspect you've got the wrong end of the stick. Icon is not like e.g. Prolog where a program can be merrily executing for quite some time, fail in a ceratin place, and then end up backtracking almost to the very beginning of the program. There is nothing even remotely like a "big backtracking loop" in Icon.

Icon has the concept of "bounded expressions" beyond which backtracking doesn't occur. The most obvious time this occurs is that backtracking does not occur between statements splits over multiple lines. So in pseudocode:

  func f():
    i := 0
    while true:
      yield i
      i += 1
    return fail

  func main():
    x := f()
    if x < 2:
      // This branch always taken
    else:
      // This branch never taken

In other words, just because f could produce more values, it won't in this situation; x will be set to 0 and that's it. If you did want backtracking to occur you would need to join the call to f and the test on x.

I'd suggest you read "The Icon Programming Language" by Griswold and Griswold (you can download it from the Icon website if memory serves correct), looking for references to "bounded expressions". I think you'll find it most enlightening.

Here is a bit of Prolog code (using Prolog's built-in DCG preprocessor):

bonjour --> "hello";"namaste".
evaltext --> "hellothisisatextstring",bonjour,"somemoreenglishtext".

with this query:

| ?- evaltext(S,nil).

If "bonjour" has to be inline text then it's more complicated.

I would have to disagree with this, because it seems to posit a world in which the success of every operation is the only acceptable outcome, and the real world doesn't work that way. To me, one of the nice things about Icon's semantics is precisely that it acknowledges that "failure" may only occur in a context in which, when you exit that context, the failure is irrelevant: there are other successes to draw from in order to achieve the (expected? desired?) result.

The other language that really seems to have a good handle on failure is Erlang, even if their model is more radical: failure kills a process, but that's OK, because you have thousands of others just like it to pick up the slack.

To me, one of the nice things about Icon's semantics is precisely that it acknowledges that "failure" may only occur in a context in which, when you exit that context, the failure is irrelevant:
This is just what backtracking does! As you back out you undo actions that need to be retracted. The same action occurs with a throw/catch mechanism. Backtracking is just a means of expression it doesn't mandate any order of behavior any more than Erlang. The ordering must be represented somehow and understood.

Hank Thediek: The ordering must be represented somehow and understood.

I think Laurence did an excellent job of explaining how Icon scopes its backtracking and orders its evaluation. All I can add is that I worked with Icon on the job for a couple of years, and not once did I experience any unexpected backtracking behavior, and I wasn't coming to Icon with anything more than an academic background in Prolog that might have colored my expectations. As I wrote before, I don't think of Icon as doing "backtracking" at all; I think of expressions generating zero, one, or more results, and the language constructs do an excellent job of supporting that view in a way that's largely intuitive for people with a traditional Algol-like language background, and probably would be even more so for someone with a Python or Ruby background.

I have nothing against Icon after all it does backtracking and that is what I am advocating. What is curious to me is that so many people have an "attitude" about backtracking even though it can be seen as functional programming with multivalues. As you seem to imply. This gets to the point. Backtracking languages "express" programming in a goal oriented fashion with rules. I find this usefull in many situations, but I don't advocate backtracking and goal orientation as a single solution for everything.