Why don't people like lisp?

[Darius]

Joe Marshall <jrm at ccs.neu.edu> wrote in message news:<oew6u18w.fsf at ccs.neu.edu>...
> ddarius at hotpop.com (Darius) writes:
> 
> > pythagoreanTriples n =
> >     [ (opposite,adjacent,hypotenuse) |
> >         opposite   <- [1..n],
> >         adjacent   <- [1..n],
> >         hypotenuse <- [1..n],
> >         opposite^2 + adjacent^2 == hypotenuse^2]
> >
> > {- or with alternative syntax
> > pythagoreanTriples n = do
> >     opposite   <- [1..n]
> >     adjacent   <- [1..n]
> >     hypotenuse <- [1..n]
> >     guard (opposite^2 + adjacent^2 == hypotenuse^2)
> >     return (opposite,adjacent,hypotenuse)
> > -}
> >
> >> and (pythagorean-triples 10)
> >> would return ((3 4 5) (4 3 5) (6 8 10) (8 6 10))
> >
> > *Main> pythagoreanTriples 10
> > [(3,4,5),(4,3,5),(6,8,10),(8,6,10)]
> >
> > Oops!  Wrong language.  Also forgot to extend the language. *sigh* I
> > can't do anything right.
> 
> Yes, the suggestion was extending the language to support
> nondeterminism.  That particular problem was illustrative, but it can
> obviously be solved via nested looping.

That isn't looping... or it is.  It depends on how you look at it. 
The above is the standard (naive) way of encoding non-determinism in
Haskell.  The list monad is also known as the non-determinism monad.
(Actually Set would be more appropriate theoretically but there are
some technical and semantical issues with that.)  The actual runtime
behavior is a depth-first backtracking search due to laziness.

At any rate, below the following is the massively altered version that
very likely works just like Screamer.
Hinze's backtracking monad transformer; will be handy later.

-- Raffael would cry.

newtype BacktrT m a 
    = BTT { runBacktrT :: forall b.(a -> m b -> m b) -> m b -> m b }

instance Monad m => Monad (BacktrT m) where
    return a = BTT ($ a)
    (BTT f) >>= k = BTT (\c -> f (\a -> runBacktrT (k a) c))
    fail s = mzero

instance Monad m => MonadPlus (BacktrT m) where
    mzero = BTT (\c -> id)
    (BTT m) `mplus` (BTT n) = BTT (\c -> m c . n c)

instance MonadTrans BacktrT where
    lift m = BTT (\c f -> m >>= \a -> c a f)

collect m = runBacktrT m (\a fk -> do as <- fk; return (a:as))
                         (return [])

This is a bit overpowerful for this purpose, but here's the above
promised massively altered example,

pythagoreanTriples n = allValues $ do
    opposite   <- amb [1..n]
    adjacent   <- amb [1..n]
    hypotenuse <- amb [1..n]
    guard (opposite^2 + adjacent^2 == hypotenuse^2)
    return (opposite,adjacent,hypotenuse)

amb = msum . map return

allValues = runIdentity . collect

Far enough from a loop for ya?  More seriously, that was part of my
point; this was a rather pathetic example.

> I think this one may be more difficult:

Okay.
[moved]
> The LOCAL macro arranges for the side effects in its body to be undone
> upon failure.  Assume that a node is a structure with a field that can
> be used to count visits and a field that contains a list of children.

Changing the spec, eh?  Now I have to add state to a pure language as
well as non-determinism.  So, some preliminaries; luckily I have them
lying around, along with Hinze's backtracking monad. Knew they'd come
in handy some time and now they're handy two times.

-- I have a more general version of this
type LP s = BacktrT (ST s)

runLP :: (forall s. LP s a) -> [a]
runLP m = runST (collect m)

type LPRef = STRef

newLPRef :: a -> LP s (LPRef s a)
newLPRef = lift . newSTRef

readLPRef :: LPRef s a -> LP s a
readLPRef = lift . readSTRef

writeLPRef :: LPRef s a -> a -> LP s ()
writeLPRef ref a = BTT (\k fk -> do
                            a' <- readSTRef ref
                            writeSTRef ref a
                            k () (writeSTRef ref a' >> fk))

> In a directed graph a `k-simple' path is a path from a vertex U to a
> vertex V that does not contain any vertex more than K times.  A simple
> non-deterministic algorithm for enumerating the k-simple paths between
> two verticies is this:

data Node a s = Node !Int a [LPRef s (Node a s)]
-- quick cheezy node type
 
> (defun k-simple-paths (u v k)
>   (if (= (node-visits u) k) (fail))
>   (local (incf (node-visits u)))
>   (either (progn (unless (eq u v) (fail)) (list u))
>           (cons u (k-simple-paths (a-member-of (node-children node)) v k))))

kSimplePaths u v k = do
    Node uVisits a uChildren <- readLPRef u
    guard (uVisits /= k)
    writeLPRef u (Node (uVisits+1) a uChildren)
    mplus (do guard (u == v)
              return [u]) 
          (do child <- aMemberOf uChildren -- you have node; I assume
u
              liftM (u:) (kSimplePaths child v k))

> (defun a-member-of (x)
>   (if (null x) (fail))
>   (either (car x) (a-member-of (cdr x))))

aMemberOf = amb

Note: I've tested most of this code and this is all of it except for
some imports and compiler flags.  I have however changed it some while
copying.  So this isn't exactly the code in my files.  I'm fairly
confident that it still works, but I haven't run it through a type
checker ;).  It does something that looks like working.

> > (posted mostly for my own amusement

this still holds

> I'll try it out when I get home.  My work computer does not have
> Screamer installed.

I didn't know what function to call because I just downloaded it,
hacked it to work with CLISP, and never read the documentation or even
extracted it.  I'm not sure the version posted by another person does
what I want in general, though I'd be very surprised if I couldn't get
precisely what I wanted.

Personally, I had the impression that you were advocating that macros
let you easily extend Lisp without effectively writing a good chunk of
compiler*, yet Screamer does this.  So I don't find Screamer a
particularly good example, especially coupled with the fact that it
isn't a complete or seamless integration.  So ranking them: Scheme's
got us both beat hands-down. call/cc let's you define (some of) the
primitives in less than a page and the result is utterly seamless
(with perhaps a few simple syntax-rules to thunkify things).  I put
Haskell second for this one.  The implementation is pretty simple, the
interface is pretty clean and it's more or less normal monadic Haskell
programming. CL/Screamer is third.  It probably wins for speed (it'd
better!), but that isn't too surprising since it's basically a
compiler for a non-deterministic lisp**.  If I'm not mistaken Screamer
implements local by searching the form for setf's and replacing them
with it's own version, which makes me wonder what it does if the
setf's aren't obvious (e.g. a compiled closure), I severely doubt it
delivers on it's seeming promise of interopability (no doubt
disclaimed in the documentation unless I'm mistaken), considering it
works be redefining defun, among others, and translation to CPS and
via a codewalker. Basically, I don't see writing the equivalent using
Template Haskell for Haskell, or whatever for Python, or as an
external tool being significantly more complicated than Screamer.  No
word from the Pythonistas.

* I agree with this.  Macros are the characterizing feature of
(Common) Lisp for me.  I think they can be used to good effect and
would like to see Template Haskell move much more toward Lisp macros.

** Actually, I wouldn't be too surprised if a Scheme with a good
call/cc could beat or at least be comparable with Screamer, or even
the Haskell (with a few obvious optimizations).  It depends on how
much static analysis and optimization transformations Screamer
performs.   If it's mainly just getting CL to CPS then there's
probably a good chance.