thom@tuhold (Thom Fruehwirth) (08/17/88)
When commenting on permutations the last time I asked if it is possible to write a permutation predicate using only a single predicate permute/n for its definition. Richard O'Keefe in article <209@quintus.UUCP> did it by a welldone transformation from the initial permute/2 predicate ending up in permute/6. I agree with him that: >I don't think it's particularly useful to have permutation done >with only one recursive predicate, but I think the derivation of >the result may be of interest. Anyway, here is my version: permute(A,B) :- permut permute([],[],[]). permute([X|A],[X|B],C) :- B=[_|_],permute(A,B,C);permute(C,B,A). permute([X|A],B,C) :- permute(A,B,[X|C]). The explicit unification in the second clause of permute/3 avoids duplication of every solution (this happens as both subgoals of the disjunction can match the first, base clause). This can also be avoided by partial evaluation resulting in: perm11([],[]). perm11(A,B) :- perm11(A,B,[]). perm11([X],[X],[]). perm11([X|A],[X|B],C) :- perm11(A,B,C);perm11(C,B,A). perm11([X|A],B,C) :- perm11(A,B,[X|C]). The idea of permute/3 is that the third argument is an intermediate storage for elements of the first argument. So the head X of the first argument is either passed to the resulting second argument directly or to the third argument for later use. The third argument is utilized by simply exchanging it with the first argument (expressed by the disjunction in the second clause). In article <1394@kulcs.kulcs.uucp> bimbart@kulcs.uucp (Bart Demoen) also uses same_length/2 to ensure commutative behaviour of perm/2: > permute_6(X, Y) :- > same_length(X,Y), > permute_2(X,Y) . > > same_length([], []) . > same_length([X|L1],[Y|L2]) :- > same_length(L1,L2) . > > permute_2([], []). > permute_2([X|Xs], Ys1) :- > permu> select(X, Ys1, Ys). and adds: > permute_6 is symmetric, so it is easier to understand that it > can be used in a symmetric way But permute_2 itself isn't symmetric. Here is a full symmetric version of permute_2/2 (unfortunately non-commutative and tail-recursive thus inefficient): permute_2([],[]). permute_2([X|Xs],[X|Ys]):- permute_2(Xs,Ys). permute_2([X|Xs],[Y|Ys select(X,Ys,Ys1), select(Y,Xs,Xs1), permute_2(Xs1,Ys1). Note that the first two clauses are equivalent to same_length/2. I conclude the discussion on permutations has shown two things: -for determinstic predicates use tail recursion, for indeterministic predicates left recursion is more efficient (this was pointed out by Bart Demoen) - it is fun to play around with predic Sometimes its even useful. thom fruehwirth technical university of vienna
jax@well.UUCP (Jack J. Woehr) (08/19/88)
Pardon my ignorance. No, don't pardon it! Cure it! May I have an example of a predicate that would accept keystroke input and return via the predicate name/2 a list of ascii chars, i presume in single-quotes? May I please have another predicate? ( Pass that non-determinate clause, it looks tasty!) A predicate that would write to a file a list of binary ops, say the code for AX AX MOV in assembler? Denk U. *************** well!jax@lll-winken.arpa " I think i've never seen a non-determinate computation but i'm not sure." ***************
ok@quintus.uucp (Richard A. O'Keefe) (08/20/88)
In article <6850@well.UUCP> jax@well.UUCP (Jack J. Woehr) writes: > May I have an example of a predicate that would accept >keystroke input and return via the predicate name/2 a list of >ascii chars, i presume in single-quotes? Is this serious? name/2 is used for converting constants to lists of character codes and vice versa. You wouldn't use it in this context, but would just read the characters using get0/1. Single quotes go around atoms; it is double quotes which indicate a list of codes ("it" = [105,116]). You mention keystrokes: arrangements for reading from the terminal vary from operating system to operating system, hence also from Prolog to Prolog. If line-buffering + echoing is ok, get0/1 should do. > May I please have a predicate that would write to a file >a list of binary ops, say the code for AX AX MOV in assembler? Sounds as though you are using a PC. Your Prolog will probably have some equivalent of C's open(filename, "wb"); just use put/1 to write bytes to that.
jax@well.UUCP (Jack J. Woehr) (08/22/88)
In article <298@quintus.UUCP> ok@quintus.UUCP (Richard A. O'Keefe) writes: >In article <6850@well.UUCP> jax@well.UUCP (Jack J. Woehr) writes: >> May I have an example of a predicate that would accept >>keystroke input and return via the predicate name/2 a list of >>ascii chars, i presume in single-quotes? > >Is this serious? name/2 is used for converting constants to lists >of character codes and vice versa. You wouldn't use it in this >context, but would just read the characters using get0/1. Single >quotes go around atoms; it is double quotes which indicate a list >of codes ("it" = [105,116]). Ok, Richard, maybe we are getting somewhere here. Am I serious? Stupid but serious. It's not like every corner has someone standing on it to answer our Prolog questions! Excuse me for cloggin the Net with my iggerance. What I am trying to do is accept user input, that, unlike ALL the examples in common texts on prolog IS NOT all in lower case, one word, period delimited. I want to get strings, wrap them in whatever they have to be wrapped in, and store them as terms. Then I want to write these predicates to a file, in forms like: customer('Joe Blow',bought('seven bananas and a Tricycle'), owes(13040),rated('a nuisance to Customer Service'). ***************** jax@well " I got a million of 'em!" jax@chariot " Quintus, huh? Any relation to Quintus Fabius Maximus?" JAX on GEnie " I'll teach you Forth if you'll teach me Prolog!"
ok@quintus.uucp (Richard A. O'Keefe) (08/23/88)
In article <6880@well.UUCP> jax@well.UUCP (Jack J. Woehr) writes: > What I am trying to do is accept user input, that, unlike >ALL the examples in common texts on prolog IS NOT all in lower >case, one word, period delimited. I want to get strings, wrap them >in whatever they have to be wrapped in, and store them as terms. >Then I want to write these predicates to a file, in forms like: > > customer('Joe Blow',bought('seven bananas and a Tricycle'), > owes(13040),rated('a nuisance to Customer Service'). > Does Clocksin&Mellish count as a "common text on Prolog"? See section 5.2 "Reading and Writing Characters" and section 5.3 "Reading English Sentences" (I have the 3rd edition). If you have Quintus Prolog and want to read a list of character codes from the terminal after printing a suitable prompt, you just do | ?- ensure_loaded(library(print_chars)). | ?- ensure_loaded(library(prompt)). | ?- prompted_line('Say something: ', X). Say something: Some Thing! Gloss: ^^^prompt^^^^^^***reply*** X = "Some Thing!" More simply, to read a line from the current input stream as a list of character codes, call get_line(Chars) where get_line(Chars) :- get0(Char), get_rest_of_line(Char, Line), Chars = Line. % postponed to make it steadfast get_rest_of_line(Char, Line) :- ( Char =:= 10 /* newline character */ -> Line = [] ; Line = [Char|Rest], get0(Next), get_rest_of_line(Next, Rest) ). You can then split the line up as you wish (grammar rules are easily the clearest way of doing that). The new-line character is system-dependent; it was 31 in DEC-10 Prolog, and is 13 in some systems. As for prompts, the built-in predicate prompt(OldPrompt,NewPrompt) sets the prompt for character input, or you might just write(ThePrompt). E.g. in Quintus Prolog | ?- write('Who is John Galt? '), get_line(Answer). Who is John Galt? never heard of him. Answer = "never heard of him." >JAX on GEnie "I'll teach you Forth if you'll teach me Prolog!" No thanks, I already know it. (One of the papers at the Seattle conference was about defining Forth using Prolog.)