miller@DOUGHNUT.CS.ROCHESTER.EDU (Brad Miller) (10/21/87)
Maybe I should have used SCHEME... Seems that lately, every time I try to do something that seems conceptually elegant, the only way (I) perceive of doing it in CL is something of a kludge. Yet, Scheme already captures the notion. Does this mean that CL is flawed, or just out of touch? Or am I trying to do something abnormal? In building a backward chaining system (similar to PROLOG) I considered the proof tree to be similar to a chart of the activation stack structure for the prover, if it were to only make successful choices. That is, you can consider each subgoal to be proved a (recursive) call on the prover, or you can imagine creating a generator for the subgoal: one that will return successive proofs for each call. Backtracking, then, involves discarding some proof from a generator and reinvoking it for the next proof. [Sorry if this is too vague] Kludge #1: the fact that we had to build generators which means we have to have other add-on mechanisms for caching the proofs a generator provides ... that is, if somewhere else in the proof tree we want to reuse the generator, we can't, since it's state wouldn't (re) provide the earlier proofs. instead we have to cons up an new generator. To avoid duplication, we may have our generators cache their results, so new generators would know what is already provable. But how much more nicely this fits into the scheme idea of a stream. A stream, like our generator, may provide one proof for each "read" of the stream, but it is lazy-evaluated: the system invokes the generator for successive proofs, so I don't have to set it up. Further, new opens of the stream read it from the beginning, so you don't have to redo work. <You can argue, that one can build such a thing in CL, and you would be right. But you would have to use macros and other nonsense (consider accessing the stream: you must check if it's empty and if so invoke the generator, etc). I would claim your implementation would be approximately what my kludge implementation is. Further, the interface wouldn't be as nice, since it wouldn't be 1st class... The point is, it isn't something the user should have to reinvent: Scheme discovered it, it looks good, why isn't it more available?> The second notion is something of an extension to CATCH and THROW. That is, Catch and Throw allow you to Throw a tag to a function that dominates (is below, invoked, etc.) you on the stack. This captures the notion that even if I am a pretty low-level routine, if I run into problems, I can summon presidential aid immediately. In effect, it means that unusual conditions can avoid returning from long lists of functions, since the stack below the catcher is irrelevant anyway. The extension is to say that what I *really* want to do is not "return" to some grandancestor, because I've discovered that the work done by the children he called is irrelevant; what I *really* want to do is snapshot some instant of the computation, and be able to return to *that* (this is a superset of catch/throw). Why? Well, to cast it into the above example is complex, but consider: what you are really doing is allowing processing to proceed to a "choice" point and it is marked. Processing continues, and runs into trouble. So, you reintroduce computation at the choice point, throwing it some form indicating that this choice is bad. So it picks a different route. This effectively captures the idea of a machine to solve NP problems with an oracle. If we ignore the work done to determine that a choice was bad (time is backed up and restarted) we see that our machine behaves as if an oracle tells it at each choice what choice is the right one (or at least, provides it with a list of the wrong choices). This fits in very nicely with how you might conceptually want to build a backward chaining mechanism, and it is pretty much exactly what you can do with continuations in Scheme. In Common Lisp? well, you can't get "into" anything that isn't active on the stack, i.e. dominates you. So, if you *do* want to get this effect, you have to spend a lot of effort recreating the saved stack. The language doesn't help, you have to do some kludgework with continuations, macros, and tags. Mainly, what the language seems to need is 1st class continuations (yes, even into currently inactive closures). So I don't know. Maybe the real problem is that the problem wasn't approached the way someone needs to approach the problem if they don't plan on using Scheme. But my personal opinion is that if we want to standardize LISP, the language that's supposed to make my building ai research tools easy, then it should give serious attention to the capabilities of sister languages. I'm not talking about syntactic sugar, I am talking about the expressibility of what seems to me some pretty fundamental concepts. You can argue that no lisp can keep up with new ideas for symbolic computation and functional programming, but I am only arguing that SCHEME has been around for a while, and I'm disappointed it's merits haven't been adopted by the larger forces in the lisp world (i.e. the common-lisp committees and the lisp machine manufacturers)... Well, this was a semi-flame, not carefully written enough to be taken as a serious proposal, but at least I've had my say. I'll note in closing that I don't consider myself an expert in computer languages, just someone trying to do a job hacking lisp on a lispm in an AI research environment for fun, profit, and a thesis. Brad Miller ------ miller@cs.rochester.edu {...allegra!rochester!miller} Brad Miller University of Rochester Computer Science Department