ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) (06/11/90)
I'm posting this for Thomas Puls, thp@iddth.dk I have added some new text beginning with "% ". ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes: >In article <14557@dime.cs.umass.edu>, pop@cs.umass.edu writes: >> The length of a list is more easily defined in ML than in Prolog as: >> fun length([]) = 0 | >> length(x::L) = 1 + length(L); % This can be expressed directly in Prolog as % length([]) = 0. % Call this the "tower" version % length(_.L) = 1+length(L). >(a) That's not a particularly efficient implementation of length(-). > The definition I would use (sorry about the syntax, but the ML > compiler I have is supposed to work on Encores but _doesn't_) is > length(L) = length(L, 0). % Call this the "linear" version > length([], N) = N. > length(_.T, N) = length(T, N+1). >(b) You did realise that the preceding three rules are _Prolog_, didn't you? > There's this little package that plugs into term_expansion/2. (Well, > two little packages: I have one, Lee Naish has another better one.) Re (a): Richard A. O'Keefe must be thinking of some specific implementations, when he talks about efficiency, because it seems to me that the two algorithms have the same complexity. % COMPLEXITY and EFFICIENCY are related concepts, but they are not the % same thing at all. Yes, they are both O(N) algorithms, but they have % different constant factors. For example, in SICStus Prolog version % 0.7 (Beta) the "tower" version is pretty consistently 2.5 times slower % than the "linear" version. In T "a dialect of Lisp" version 3.1 the % tower/linear ratio is about 1.67 for long lists, more like 2 for short. % What I'm thinking about is the fact that in _many_ implementations of % Prolog-like languages and strict functional languages the "tower" % version will build a tower of stack frames which the "linear" version % won't, and that _costs_. A smart compiler will notice that "+" is % associative with left identity 0, and compile the "tower" version as % if it were the "linear" version, but a smarter compiler will realise % that in the presence of floating-point numbers "+" is _not_ associative % and won't do that transformation without explicit permission. Re (b): The rules certainly don't seem to be any ordinary kind of Prolog to me. % Ah, but by the time the Prolog compiler or 'assert' equivalent gets % anywhere near them, they _are_. That's the point. Just as Lisp has % macros and (some) Schemes have extend-syntax, Prolog has term_expansion/2 % (well, good ones like Quintus Prolog, NU Prolog, SICStus Prolog, ZYX % Prolog, and so on, have it). Anything you can translate to Prolog _is_ % Prolog, as far as the Prolog system is concerned; grammar rules, % equations, you name it. The translation required for definitions like % this is *TRIVIAL*, I mean, it's the kind of thing you'd give as an end- % of-year project. Let's consider the "linear" version. % length(L) = length(L, 0). % => length(L, X1) :- length(L, 0, X1). % length([], N) = N. % => length([], N, X1) :- X1 = N. % => length([], N, N). % length(_.T, N) = length(T, N+1). % => length(_.T, N, X1) :- X2 is N+1, length(T, X2, X1). >(c) It might be clearer to express it as > length(L) = scan_list(plus, map_list(k(1), L), 0). > and have the definition in (a) generated automatically. > (I assume that k(_, K) = K is already defined.) > Oh, which language do you think that definition's written in? Re (c): This definition of the length of a list has a one to one counterpart in ML. % Whoever said it didn't? That's the _point_! Re (a) + (b) + (c): Now the most important comment: I certainly find the first definition of lengths of lists the most clear both as an algorithmic description and as a declarative definition. % In context, this is _not_ an important comment. The question was % the expressiveness of functional notation -vs- Prolog, and the point % of my posting was that it is a false contrast; whatever the benefits % of functional *syntax* are you don't have to abandon Prolog to get % them. EACH of the three methods quoted or presented in my posting % is expressible in ML *and* Prolog in essentially the same syntax. Especially I don't find the third definition clear at all, to ME the length of a list is not the result of replacing the elements of the list with the number 1, and then taking the sum of the numbers in this list added to the number 0 (which is apparently (and of course naturally) the sum of a sequence of numbers, if it is empty). % Well, I find the definition "the length of a list is obtained by % counting 1 for each element" natural. But so what? What has that % to say to anything? We were talking about expressiveness. The % point was that I _can_ define things in Prolog using ``higher-order'' % functions if I want to. (How efficient that is depends on the % implementation. It is likely to be rather slow.) It would be interesting to hear how Richard A. O'Keefe would define the level of nesting of terms of the structure: q(q(q(...q(nil)...))), or can this notion not be defined at all, because it is not possible to create a copy of such a term, which contains natural numbers to be summed. % I am sorry, but I simply cannot make sense of this paragraph. % To be brutally frank about it, the term as it stands is a perfectly % good representation of its own depth; if the only choices are 'nil' % and q(_) then in everything that matters it _is_ a natural number. % If you want the thing as a binary number, use % depth(QN) = depth(QN, 0). % depth(nil, N) = N. % depth(q(X), N) = depth(X, N+1). % (By the way, the "tower" version of this is about 2.3 times slower % than the code presented here, in SICStus 0.7, on an Encore Multimax.) My point is that the length, depth, or the like of an object have nothing to do with the object's capability to contain numbers, but with the structure of the object. % What is an object's capability to contain numbers but its structure? % And what has this to do with the example in question? There may or % may not have been any numbers in the original list; what made the % `scan_list' version of the definition work was our ability to create % a list of 1s the same length as the original list. If you want to % see that for the 'q' example, here goes: % q_list(nil, X) = []. % q_list(q(T), X) = X.q_list(T, X). % sum(L) = scan_list(plus, L, 0). % depth(X) = sum(q_list(X, 1)). % /* "The sum of as many 1s as there are qs" */ % Remember, the original thread had nothing whatsoever to do with % "how to define length &c"; the topic was whether bracktracking was % useful enough to sacrifice functional syntax for, and the point is % that there isn't any need to sacrifice functional syntax. The first two definitions rely on this structural definition of objects, the third does not, it relies on the somewhat awkward corespondence between the sum of the elements in a list containing only ``ones'' as elements and the length of such a list. % Oh yes the third definition (the `scan_list' one) *does* rely on % the structural definition of lists. It does so via % scan_list(F, [], X) = X. % scan_list(F, H.T, X) = scan_list(F, T, call(F,X,H)). % map_list(F, []) = []. % map_list(F, H.T) = call(F,H).map_list(F, T). % which are as structural as you please. Oddly enough, I've been arguing % against Aaron Sloman in comp.lang.functional, saying that what he can do % with the PopLog pattern matcher I can do in a few lines of Prolog with % as much or more generality. Here I find myself arguing his position: % sometimes it is clearer to express what you intend in terms of operations % on the whole list, rather than hacking around with the implementation of % lists. Thomas Puls, thp@iddth.dk % R.A.O'K. -- "A 7th class of programs, correct in every way, is believed to exist by a few computer scientists. However, no example could be found to include here."