Non-deterministic computing (was: What python can NOT do?)

[Joshua Judson Rosen]

Steven D'Aprano <steve at REMOVE-THIS-cybersource.com.au> writes:
>
> On Sat, 29 Aug 2009 05:37:34 +0200, Tomasz Rola wrote:
> 
> > My private list of things that when implemented in Python would be
> > ugly to the point of calling it difficult:
> > 
> > 1. AMB operator - my very favourite. In one sentence, either language
> > allows one to do it easily or one would not want to do it (in an ugly
> > way).
> > 
> > http://www.randomhacks.net/articles/2005/10/11/amb-operator
> 
> 
> Fascinating, but I don't exactly see how that's actually *useful*. It 
> strikes me of combining all the benefits of COME FROM with the potential 
> performance of Bogosort, but maybe I'm being harsh. 

There's a chapter on this (non-deterministic computing in general,
and `amb' in particular) in Abelson's & Sussman's book,
`Structure and Interpretation of Computer Programs':

    http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-28.html#%_sec_4.3

It's an interesting read (the chapter, as well as the rest of the book).

> On the other hand, it sounds rather like Prolog-like declarative 
> programming. I fear that, like Prolog, it risks massive performance 
> degradation if you don't apply the constraints in the right order.

One of the classic arguments in the other direction is that
imperative programming (as is common in Python ;)) risks
massive *incorrect results* if you don't apply the side-effects
in the right order :)

-- 
Don't be afraid to ask (Lf.((Lx.xx) (Lr.f(rr)))).