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
likes@silver.bacs.indiana.edu (10/21/87)
Yes, Common Lisp is seriously flawed, and you were trying to do something abnormal. It is just because Common Lisp isn't able to handle such "abnormal" situations that I say it is flawed. If you look at it Common Lisp is just one series of kludges after another (extra arguments to assoc, packages, no first-class functions, etc...) On the other hand, Scheme has more of a unified picture of the world (if you ignore versions with first class environments ala M.I.T.). The world could do a lot worse than accept Scheme as the standard "lisp" to use (worse begin things like PSL, CL, Franz, etc ...). -- Kevin T. Likes "Flames off the starboard bow, captain." "All power to the shields, Mr. Scott."
likes@silver.bacs.indiana.edu (10/21/87)
/* Written 10:56 am Oct 21, 1987 by likes@silver.UUCP in silver:comp.lang.lisp */
>(extra arguments to assoc, packages, no first-class functions, etc...)
/* End of text from silver:comp.lang.lisp */
I guess I had better clarify this. I don't like the way CL makes you
do extra things to get first-class functions. Sure you can get the
functionality, but you have to wrap things in (function ...) and do
fun-apply (I think that is the word), to really make functions values.
Certainly you can do it, but it is definitely kludgy. Sorry if this
caused any confusion (as if anyone believed me in the first place).
--
Kevin T. Likes
"Flames off the starboard bow, captain."
"All power to the shields, Mr. Scott."
shebs@utah-orion.UUCP (Stanley T. Shebs) (10/22/87)
In article <23200001@silver> likes@silver.bacs.indiana.edu writes: >[...] If you >look at it Common Lisp is just one series of kludges after another >(extra arguments to assoc, packages, no first-class functions, etc...) >On the other hand, Scheme has more of a unified picture of the world >(if you ignore versions with first class environments ala M.I.T.). Kevin, I thought you knew more about Common Lisp and Scheme than that! Can anyone really think that R^3 Scheme's ASSQ, ASSV, ASSOC triad are better than CL's ASSOC that takes functional arguments? Looks to me like CL uses function objects *more* than Scheme does... The *only* difference between functions in Scheme and functions in CL is that CL requires a special syntax to invoke a function object and Scheme doesn't. It's the sort of thing I refer to as "semantic sugar"; it's not mere syntax, but it's not that important either. Packages were taken over almost verbatim from Symbolics, boycott their equipment if you don't like packages. Arguments about the comparative merit of language details border on the sophomoric, but alas, they seem to be sanctioned by eminent scientists who really should know better (exercise for the reader to think of five names). I think it's more important what the language does for realistically-sized programs. I have yet to see any 5,000+ line programs for which it made any significant difference which dialect (Scheme or CL) the program was written in. Call/cc and variables in the function position are at best a minute percentage of large Scheme programs, while CL programmers avoid many fancy features because of their expense or mismatch to the needs of the moment. >Kevin T. Likes stan shebs shebs@cs.utah.edu
likes@silver.bacs.indiana.edu (10/23/87)
As usual, Stan cuts right to the heart of the matter. I should have known better, but I was in bad mood about Common Lisp, and I let my anger post instead of thinking. The real differences between Scheme and Common Lisp aren't "semantic sugar", but most of them are, and any debate between proponents of Common Lisp and Scheme is bound to have those come up lot more than the real issues, and neither side is going to convince the other. Next time I post something nasty about Common Lisp (if I ever do) I will think a little more before I waste net bandwidth. Sorry about that Stan. Kevin (the suitably chastened programmer) Likes