chik@icot.or.jp (Chikayama Takashi) (07/02/90)
Although I see much debate on the "purity" problem/non-problem of logic programming language, I think one important aspect is missing in the discussion. In article <1990Jun18.221058.11331@chaos.cs.brandeis.edu> dsmith@chaos.cs.brandeis.edu (Donald A. Smith) writes: > 5. Because of its single-assignment property, Prolog uses lots of memory. > In C we can write an in-place quicksort. In any Prolog I know of, the > input list would be copied. (Has anyone figured out how to make quicksort > in-place in Prolog? Is there a workable implementation of declarative > vectors?) The worst thing about single-assignment property of Prolog is _not_ that it consumes up lots of memory. Garbage collection, at most, takes time proportional to the time required to pile the garbage. A more serious problem is that random access memory that computer hardware provides (or, at least, tries to do so) is not available from the programming language level. This means that certain algorithms, including dynamically updated hash tables, cannot be expressed in standard Prolog with the same computational complexity. This, however, can be solved by certain implementation technique without disturbing the single-assignment semantics. See, for example: author = "L. H. Eriksson and M. Rayner", title = "Incorporating Mutable Arrays into Logic Programming", booktitle = "Proceedings of the Second International Conference on Logic Programming", pages = "76--82", year = "1984" Takashi Chikayama
pgl@cup.portal.com (Peter G Ludemann) (07/06/90)
> What I meant to say was that I want to present a left-recursive grammar > to the parser generator and let it figure out how to do the transformation > without altering the associativity. In other words I want to write: > expr(app(E1,E2)) --> expr(E1), prim(E2). > expr(E) --> prim(E). There's another technique, which no-one seems to have mentioned: meta-grammar rules. What you want here is a sequence of "prim"s: expr(E) --> seq(prim,E) . No problem: just define a meta-rule: seq(X,[E1|E2]) --> X(E1), seq(X,E2) . seq(X,[]) --> [] . The resulting "E" is the list of "prim" values, which is what you probably want and not the app(app(...(app(E1,E2),E3...),En) which your solution provides. If you really do want the app structure, it's easy to write a seq//2 rule which provides it (hint: add a 3rd argument). Now, every time you want a "left-recursive" rule, just use the seq//2 meta-rule. Other meta-rules for `optional sequence', 'sequence with a separator', etc. are easy to create. They greatly simplify the writing of grammars (look at the C grammar in Kernighan&Richie for an example of using the "opt" and "seq" notations). Of course, most DCG translators won't handle meta-rules, but they're not difficult to add (about a dozen lines in my translator). - peter ludemann (standard disclaimer) Disclaimer: I haven't actually run the above code; but I have done something very similar and it worked very nicely. Minor note: The "X(E)" notation won't work in most Prologs (it does in the one I use). Your Prolog might require something like "{Z=..[X,E]}, call(Z)" --- and then your DCG translator must recognize that call/1 is special and should get the extra arguments added at run-time.
kjell@spica.ucsc.edu (Kjell Post) (07/06/90)
In article <31467@cup.portal.com> pgl@cup.portal.com (Peter G Ludemann) writes: >There's another technique, which no-one seems to have mentioned: >meta-grammar rules. I wrote an SLR(1)-parser generator last week (~250 Prolog-lines) and the associated LR-parser driver that goes with it (~20 lines). I could easily extend it to LALR(1) or STLR(1) if I need more power but right now I'm just happy with the fact that I can use left-recursive grammars again :-)
jeff@aiai.ed.ac.uk (Jeff Dalton) (07/10/90)
In article <3305@goanna.cs.rmit.oz.au> ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes: >> Isn't Prolog an awkward, often obscure programming >> language useful for just a few application domains? [Richard goes on to defend Prolog at length.] There would be a lot fewer disagreements of this sort if it were not for the difference between what certain advocates of Prolog promise and what the language actually delivers, and if not for the attitude certain advocates of Prolog take towards other languages. Some skepticism about Prolog is, I think, a natural result. I think Richard's defense is, on the whole, a fair one. Nonetheless, he is too quick to dismiss certain points and he uses a bit too much rhetoric along the lines of "Gods below, but I'm sick of this. When will these people grow up?". >There are several points that can be made even without knowing anything >about Prolog. > > -- obscurity as a property of a programming language has much to do > with the person making the claim and the instructional material > that person has been exposed to. This sort of observation is all very well, but it's far from the whole story. If something's hard to understand, maybe it really *is* hard to understand. If instructional material tends to be confusing, maybe that says something about the language. You happen to be very good at explaining Prolog, but maybe it says something about the language that many other people meet with less success. Another thing to bear in mind is that different people are good at different things, and it's not surprising that some people find that Prolog suits them very well. However, we can't ignore the problems of the rest. For example, I happen to like the syntax of Lisp and to find it very readable. Moreover, I have found that many people who find Lisp's syntax difficult have not been taught the effective techniques for dealing with it or have been using editors which fail to help them. Nonetheless, this does not mean that everyone will come to like the syntax if only they are taught the right ways of thinking and given appropriate tools. And even if everyone could come to like Lisp, the fact remains that the syntax often works against it in practice. > -- the awkwardness of a language is best assessed by someone who has > made a determined effort to become fluent in it. Pascal is more > awkward than a zooful of mules. C is as awkward as a greased hammer. > > A *very* good way to experience a language X as awkward is to try > to use it as if it were language Y which you already know. This is true in some cases but not in others. It is often very effective to use one language in the style of another. To pick a fairly extreme example, I have used Basic as if it were Lisp with good results. > -- I myself don't see Prolog as a general-purpose language. So what? > If Prolog is useful for a few application domains, that's all the > justification it needs. Maybe so, but that's not all the justification it gets. >What has quicksort to do with Prolog? The large number of times it is used to show how easy and natural it is to express things in Prolog. [To be fair, the functional language folk often do the same.] >Prolog has never failed any one of *my* expectations. Surprise! Remember that you understand Prolog very well. A number of other people aren't in the same position. >> 1. Notwithstanding Peter van Roy's admirable benchmark results, Prolog >> implementations tend to be slow for many programs. (e.g., quicksort >> in Prolog vs. in C). [Lots about performance on quick and other sorts deleted] But Richard, do you deny that Prolog implementations tend to be slow for many applications as compared to, say, C? Are all the people who have experience that would suggest this just mistaken? >> 2. I have yet to see an elegant marriage of logic and functional >> programming. It seems clear that functional syntax is needed. > >I thought we disposed of that just a little while ago. Yes, you think a little syntactic sugar is enough; others don't. If enough is added to prolog so that one can write higher-order functions and anonymous functions (lambda expressions), though, I suppose *I'd* be satisfied. Having most things curried, as in SML, would be nice too. >> 3. Prolog's fixed depth-first search order and left-to-right computation >> rule are too inflexible (e.g., for AI and expert system applications). >Gods below, but I'm sick of this. When will these people grow up? >Prolog is a *PROGRAMMING* *LANGUAGE*. Ada, C, Lisp, Scheme, they all >have exactly the same depth-first left-to-right computation rule as >Prolog. This makes them useless for AI and expert systems applications? >Get real! Yes, but again and again one is told that Prolog *has* search or that it *has* backtracking or that it *has* pattern-matching -- they don't have to be *added* like they do in other (inferior) languages. The expectation is created that Prolog will do a lot of things as-is, when the reality is that one often has to write code to do them, just as one has to when using other languages. >- You have to pass all needed parameters to procedures. > This really is not a big deal in practice if you will only try to write > *Prolog* code instead of trying to write Pascal code in Prolog. If you > want to know how to do that, my services as a teacher of advanced Prolog > courses _are_ for hire... Maybe it's not a big deal for *you*, but quite a few people, some of whom haven't learned any language other than Prolog (and so haven't been influenced by Pascal directly), and others who are very experienced Prolog programmers (and so should have learned better if it's as easy as you say), write procedures with unreasonable numbers of parameters. >- Adding new parameters is a pain. > > (a) Design your program right in the first place. I'm serious. > (b) This is a property of programming environments, not of languages. > Ever use Masterscope? (.EDIT WHERE ANY CALLS FRED) Great tool. Given tools that do enough of the work for you, all problems go away. Thus, we can remove all the problems of COBOL, FORTRAN, etc, and all languages are perfect. So? >There is an ambiguity in "uses lots of memory". It could mean "turns over >a lot of cells" (true). It could mean "needs a lot of storage at any one >time" (false). A good point, and one that needs to be made. >It's worth noting that the single-assignment property is precisely what >makes functional languages like ML and logic-based languages attractive >for parallelism. (It's getting late or I'd elaborate on this.) Ditto, although it's made rather too often. >About cuts and assert, I will only say that competent Prolog programmers >know that the fewer of them they use, the faster their programs are likely >to be. One wonders how they become competent Prolog programmers when so many Prolog texts give the opposite impression about the role of cut. >At this late date, do I need to say once again that Prolog is not the >only logic programming language? This is another way in which all problems can be made to disappear. Let's deal with one language at a time. -- Jeff
RCAPENER@cc.utah.edu (07/11/90)
In article <2952@skye.ed.ac.uk>, jeff@aiai.ed.ac.uk (Jeff Dalton) writes: > In article <3305@goanna.cs.rmit.oz.au> ok@goanna.cs.rmit.oz.au > (Richard A. O'Keefe) writes: >> -- obscurity as a property of a programming language has much to do >> with the person making the claim and the instructional material >> that person has been exposed to. > [much stuff deleted, but Jeff replies] > > This sort of observation is all very well, but it's far from the whole > story. If something's hard to understand, maybe it really *is* hard > to understand. If instructional material tends to be confusing, maybe > that says something about the language. You happen to be very good > at explaining Prolog, but maybe it says something about the language > that many other people meet with less success. > [more stuff deleted, Richard asserts another point] >> >> This really is not a big deal in practice if you will only try to write >> *Prolog* code instead of trying to write Pascal code in Prolog. If you >> want to know how to do that, my services as a teacher of advanced Prolog >> courses _are_ for hire... > > Maybe it's not a big deal for *you*, but quite a few people, some of > whom haven't learned any language other than Prolog (and so haven't > been influenced by Pascal directly), and others who are very > experienced Prolog programmers (and so should have learned better > if it's as easy as you say), write procedures with unreasonable > numbers of parameters. > But Jeff, Richard is making a *VERY* valid critique here! More than once I have observed people with Pascal backgrounds drag that accursed language over into *EVERY* other language out there. Right now, I am not too happy at all about their Pascalization of C in the latest ANSI version. Why the h**l couldn't they have added type complex and type BCD rather than worrying incessently about adding prototypes? And now they are dragging in their MixedCASEVars AreWonderfulConcept SinceWeALWAYSReadEnglishThisWayAnyway! Yes, sad but true, the effects of a previous language DO have an effect on learning a new language. And they have also created new styles of indentation that depart from the standard, bloating the size of the files (tabs show as 8 spaces but only cost 1 char) and actually making the code *LESS* readable! By the way, do you really know people that have PROLOG as their first computer language? Prolog (shouldn't it be in all caps?) as a declarative logic language has its uses, and it should be used differently than Pascal is. People that gripe about the awkwardness of PROLOG, are really going to have fun when they try using Smalltalk or some other object-oriented language for the first time! The gist of this is, when you learn a new computer language you really MUST try to think in the style that is natural for that language. It seems to me that this holds for natural human languages as well. Does PROLOG have its uses? It certainly does, and although it may not do everything (I haven't noticed anyone I know claiming it does), it does what it does well. Sure, we can do it faster in C, but we also pay the price of having to write more code. And it takes most of us the same amount of time (assuming we can write with equal effectiveness in multiple languages) to write X lines of code regardless of the language we code it in. This means we can finish the job faster in languages that are more expressive (ie, SQL code vs. doing it all by hand in C). Do we pay a price for this convenience? Yes, usually slower execution times. But this is nothing new, and we observe this trade-off all of the time in Computer Science. It just depends on which is most valuable at the time we write the code, execution time vs. development time. Rather than focusing on this, we should be spending far more time on integrating the various languages together so that we can write mixed language applications easily and effectively. And if some poor soul is incapable of working in 3 or more languages effectively, I choose to believe they are a dolt who shouldn't be in CS! We have all too many in that class now. For myself, that means C++, Prolog (wouldn't you have guessed that by now 8-)), LISP, and Sybase (or take your own pick of relational or object oriented data base). On occasion, use of an Expert System shell might be nice too. It all depends on what you are doing. If you find that PROLOG doesn't have the capabilities to do whatever you want to get done, then don't use it! Use hammers for pounding in the nails, not wrenches. Seriously, if someone finds PROLOG all that difficult to learn, I question whether they have what it takes to be an effective Computer Scientist. I am NOT saying they are dumb! There are people who are brilliant in other fields that seem to die on the vine when it comes to doing even the simplest programming tasks. I know some of these people personally. Conversely, there are people who can write code at the drop of the hat in many computer languages that have very serious problems with Math or Physics. The gist of it is, if you can't do it, get out of the field. It is overloaded with incompetents as it is. Note, I do NOT consider you to be one of these people!
marti@inf.ethz.ch (Robert Marti) (07/13/90)
Editorial comment: I know this doesn't really belong here, but I just can't keep my mouth shut. Judging from past experience, I'll probably soon regret jumping into a fray on the net, anyway ... In article <76740@cc.utah.edu> RCAPENER@cc.utah.edu writes in response to articles by Jeff Dalton and Richard O'Keefe: >Right now, I am not too happy at all about their Pascalization of >C in the latest ANSI version. Why the h**l couldn't they have added >type complex and type BCD rather than worrying incessently about >adding prototypes? [ More flaming deleted ... ] You should have heard Brian Kernighan (of K&R fame, no less) trying to sell us the concept of function prototypes in ANSI C in 1986, at the very place where Niklaus Wirth designed Pascal (around 1971) and Modula-2 (in 1979). It was definitely a case of preaching to the converted, I can assure you. At any rate, let me point out that the prototypes in C owe a lot to C++, a language you seem to like (see below). >And if some >poor soul is incapable of working in 3 or more languages effectively, >I choose to believe they are a dolt who shouldn't be in CS! We have >all too many in that class now. For myself, that means C++, Prolog >(wouldn't you have guessed that by now 8-)), LISP, and Sybase (or >take your own pick of relational or object oriented data base). I haven't heard of the language Sybase yet. You wouldn't by chance be talking about SQL (or the non-standard extension called Transact-SQL)? -- Robert Marti Phone: +41 1 254 72 60 Institut fur Informationssysteme ETH-Zentrum Internet: marti@inf.ethz.ch CH-8092 Zurich, Switzerland UUCP: ...uunet!mcvax!ethz!marti
jeff@aiai.ed.ac.uk (Jeff Dalton) (07/13/90)
In article <76740@cc.utah.edu> RCAPENER@cc.utah.edu writes: >But Jeff, Richard is making a *VERY* valid critique here! More >than once I have observed people with Pascal backgrounds drag >that accursed language over into *EVERY* other language out there. Richard is making a valid point, but so am I. In the passages you quote, Richard is saying: (1) when someone finds a language obscure this has much to do with the person and the instructional material; and (2) having to pass all required parameters to a Prolog procedure isn't a problem if you write Prolog instead of Pascal-in-Prolog. Well, there's more to it than that, and I have tried to say something for the other side. In particular, when someone does *not* find a language obscure, that certainly says something about them; just as in the other case, however, it is less clear what it says about the language. For almost any subject, there are some people who find it clear as can be and some who find it difficult. And that shouldn't be surprising; we can't expect everyone to have the same skills, even within a given field. I certainly cannot agree with you when you say: Seriously, if someone finds PROLOG all that difficult to learn, I question whether they have what it takes to be an effective Computer Scientist. I wouldn't care to make such a significant test out of any single issue. Besides, who ever said only computer scientists were worth considering? On the other hand, a language does have some effect on whether or not people find it obscure. Indeed, we can often identify some of the weaknesses of particular languages in this way. We can't forget about this just because the people and the teaching also have an effect. As for the point about Pascal-in-Prolog, yes, that can be a problem. However, again I don't think that's all there is to it; and indeed I have seen some pretty poor code in cases that are not just due to the influence of Pascal or other languages of that sort. >Yes, sad but true, the effects of a previous language DO have an >effect on learning a new language. I haven't said otherwise. >By the way, do you really know people that have PROLOG as their first >computer language? Yes. >Prolog (shouldn't it be in all caps?) I hope not. >Prolog ... as a declarative logic language >has its uses, and it should be used differently than Pascal is. I'd like to remind you at this point that when Richard said "a *very* good way to experience a language X as awkward is to try to use it as if it were language Y which you already know", he was making one of "several points that can be made even without knowing anything about Prolog". Some of my remarks should be read in the same light. I would not say Prolog should be used as if it were Pascal; but on the more general question I would still say that using one language in the style of another can have good results. You may wish the world were simpler and that this were not so, but in my experience it happens to be true. >People that gripe about the awkwardness of PROLOG, are really going >to have fun when they try using Smalltalk or some other object-oriented >language for the first time! It wasn't my intention to contribute to a language war, and I hope one does not develop. However, the fact is that some of the people who find Prolog awkward are already happy with some object-oriented language. -- Jeff
ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) (07/20/90)
In article <31467@cup.portal.com>, pgl@cup.portal.com (Peter G Ludemann) writes: > There's another technique, which no-one seems to have mentioned: > meta-grammar rules. What you want here is a sequence of "prim"s: > > expr(E) --> seq(prim,E) . > > No problem: just define a meta-rule: > > seq(X,[E1|E2]) --> X(E1), seq(X,E2) . > seq(X,[]) --> [] . > In current Quintus Prolog, use 'phrase': seq(X, [E1|E2]) --> {augment_term(X1, X, E1)}, phrase(X1), seq(X, E2). seq(X, []) --> []. I'll add phrase/N for N > 3 (i.e. phrase//M for M > 1) to the library so that you'll be able to write seq(X, [E1|E2]) --> phrase(X, E1), seq(X, E2). Generally speaking, where you would have used call/N in ordinary code you would use phrase//N in a grammar rule. -- Science is all about asking the right questions. | ok@goanna.cs.rmit.oz.au I'm afraid you just asked one of the wrong ones. | (quote from Playfair)