Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!usc!zaphod.mps.ohio-state.edu!sdd.hp.com!decwrl!hayes.fai.alaska.edu!accuvax.nwu.edu!anaxagoras!krulwich
From: krulwich@ils.nwu.edu (Bruce Krulwich)
Newsgroups: comp.lang.lisp
Subject: Re: FALSE vs empty list
Message-ID: <1621@anaxagoras.ils.nwu.edu>
Date: 5 Sep 90 17:09:31 GMT
References: <24305@uflorida.cis.ufl.EDU> <119011@linus.mitre.org> <STEPHEN.90Sep4173036@estragon.uchicago.edu>
Sender: news@anaxagoras.ils.nwu.edu
Reply-To: krulwich@ils.nwu.edu (Bruce Krulwich)
Distribution: usa
Organization: Institute for the Learning Sciences, Northwestern University, Evanston, IL 60201
Lines: 41
In-reply-to: stephen@estragon.uchicago.edu (Stephen P Spackman)

stephen@estragon (Stephen P Spackman) writes:
>Suppose, just as plausibly, that I'm doing theorem-proving. Each
>strategy takes a proposition as an argument and needs to return one of
>TRUE, FALSE and FAIL. Now, isn't it natural to represent failure with
>#f, so ANY will behave? But wait! #f is ALREADY falsity! Conflict of
>interests again.
>
>Amusingly enough, BOTH of these happened to me in real life (I once
...
>The second difficulty was dealt with by having "truth" and "falsity"
>bound to gensyms to represent object-model truthvalues, with nil being
>the _absence_ of truthness.

The best answer that I've found to all of these problems is to have the
function take continuation parameters for all of the end-cases that it has to
handle.  This obviates the need to have the return value signal the result,
because different pieces of code can be called instead.

The following could be how a database retrieval system could be called.  The
first arg is the proposition, the second is the continuation to call in the
success case, and the third is the continuation to call in the failure case.

(query '(on a b) 
  #'(lambda (bindings) (format t "A is ~S" (cdr (assoc 'a bindings))))
  #'(lambda () (format t "I failed...")))

(query prop
  #'(lambda (bindings) 
       (if bindings (format t "Match.") (format t "Exact match.")))
  #'(lambda () (format t "No match.")))

This has the overhead of CONSing the continuations (unless you've got a
compiler that handled downward-funargs well), but I've found that if you want
to do backtracking in a matcher (when handling more complex expressions),
continuation CONSing is no more expensive than other schemes.


Bruce Krulwich
Institute for the Learning Sciences