Recursive list comprehension

[Peter-Henry Mander]

Hi Richard,

I've cc'ed the list too, I like a good argument, and the more the
merrier. Anyone else care to add oil to the flames?

As you probably realised, I'm talking out of the other orifice since I
know too little Prolog to make a qualified judgement. It's not long ago
that I stumbled on FP and COP and I still don't always grok it, and
logic programming ought to be my next learning curve to climb. Now that
I've #include <std_disclaim.h> I can forge ahead and embarrass myself,
again :-)

On Thu, 2006-01-19 at 13:45 +1300, Richard A. O'Keefe wrote:
> Peter-Henry Mander <erlang@REDACTED> wrote:
> 	Since Erlang was derived from Prolog a long time ago, I think
> 	Dr. Joe & colleagues omitted backtracking because of rampant
> 	memory consumption
> 
> Er, WHAT "rampant memory consumption"?
> Prolog-style backtracking is a way of ECONOMISING on memory,
> by holding different things at different TIMES rather than in
> different PLACES.

I agree that it avoids *explicitly* holding terms of computation in your
program code, but (and I speak from a C programming perspective with all
the incumbent memory management paranoia) this information is _still_
being implicitly stored in memory to enable the backtracking mechanism
to rewind to a previous decision branch in the search tree. A red or
green cut (I believe) discards sub-trees that can be reclaimed as free
memory. Otherwise if memory was not an issue, Prolog would not need cuts
at all.

> 	and the possibly iffy use of red/green cut that I for one never
> 	properly understood.
> 
> It is perfectly possible to have a language with backtracking but
> without cuts.  (The logic programming language Mercury, for example.)

My point above echos yours. But I guess that Mercury either has very
clever dead branch pruning to reclaim unreachable backtrack paths, or
just doesn't care and guzzles memory.

> 	Erlang gains clarity without backtracking methinks.
> 
> Well, no.   In fact, quite the opposite.
> Lazy functional languages like Haskell can cope without backtracking
> (at the price of taking lots more memory -- remember I said that
> backtracking is a way of SAVING memory), but Erlang is not a lazy
> language.  For problems where backtracking search is appropriate,
> Erlang is really rather clumsy.

I'm really smelling the stink of my own fart here. Erlang is easier for
my 'C' addled brain to cope with because there's no backtracking. But
that's only because *I* don't fully understand how to apply it, not
because the lack of backtracking is a virtue. If I learnt to use Prolog
correctly, my perception will no doubt be inverted.

Prolog is designed to solve problems like Zurg, I can't contest that.
But I don't agree that Prolog somehow magically stores a search space in
thin air. Backtracking needs memory, and please try hard to shake this
perception, 'cos the argument will be great fun! :-)

> The real issue is side effects.  Side effects and backtracking search
> are not a good match, because while you can undo variable bindings
> easily enough, it's hard to tell a process on another machine "er,
> that message I sent you half an hour ago? well, I didn't really mean it..."
> (Not impossible.  Time warp algorithms do something similar.)
> And Erlang is just *full* of side effects (sends and receives count
> as side effects here).

I agree, side effects must be one of the reason Dr. Joe et al. omitted
backtracking, not memory (sorry, another fart). But I'm not convinced
that backtracking in Prolog has no memory cost.

<warning: what follows is intentionally inflammatory>

There seems to be mutual suspicion between FP/logic programmers and
etch-bare-metal programmers. You imply that there's no cost at all in
using the high level features of Prolog, and I don't believe so.

An lisp/prolog weenie can write a program that is provably correct,
something a 'C' programmer may not even believe is possible, but may
require infinite resources to produce an answer (okay, I'm exaggerating
wildly, just hear me through).

A programmer whose professional obsession revolves around pointers and
other low level resource management knows by experience that these
wonderfully powerful tools *must* have a computational and resource
cost. The lisp/prolog weenies seem blissfully unaware of this cost. I
may be ignorant, maybe they're right to dismiss the cost as a sacrifice
for provably correct programs, but Turing's infinite tape is still
unavailable.

Erlang bridges a gap between these two camps. The design of the language
contains pragmatic compromises that keeps resource consumption low, and
preserves enough of the functional paradigm to enable proof of
correctness.

So my question(s) changes: Is backtracking essential? How much do Erlang
programmers suffer for not having backtracking? What other FP/logic
features are unavailable in Erlang that would be cool to have, and more
pertinently, why are they *NOT* included?

Pete.