Subject: Re: [SWIPL] keysort

From: "Richard A. O'Keefe" <[email-masked]>
Date: Wed, 28 Feb 2001 13:18:56 +1300 (NZDT)

I mean: efficient in design, coding and testing effort; making use of
	well-documented and well-tested library ADTs and of higher-order (?)
	predicates such as maplist, versus writing a new edge/3 ADT from scratch.
	
Right, now I understand you.  "Do the simplest thing that could possibly
work", "if you didn't write it you didn't wrong it", all that kind of stuff.

	It shouldn't be, but it is too easy (for inexperienced or undisciplined
	programmers) to make trivial mistakes (e.g. re: steadfastness or stray
	choicepoints) when coding; sometimes I forget to put terminating facts
	e.g. this_to_that([], Ys, Ys) in my procedures!

I once wrote a checker for that.  Dunno what happened to it.  Never
fixed it to handle modules.

Basically, what you do is construct a 'context-free skeleton' of the program.
Take the clauses, replace p(T1,...,Tn) by 'n p', drop calls to built-in
predicates including cuts.  Also, treat \+X, setof(..,X,..), bagof(..,X,..)
and so on as plain X. Now you have a set of propositional clauses.
(This is linear in the size of the original file.)
Find a minimal model of the skeletal program.
(This is linear in the size of the skeletal program, because we're
dealing with Horn clauses.  Negation disappeared, remember?)
Any 'n p' which is false in this minimal model corresponds to a p/n
which is affected by a missing base case somewhere (possibly even an
entire missing or wrongly spelled predicate).

You can filter that set even further, but for the couple of weeks that I
played with it there was never any need to.  (Come to think of it, it may
have been on that tape of all my files that I was given when I left
Edinburgh, where the ****ing TOPS-10 archival program had flattened out
all the directories and clobbered most of the files.)

Once I adopted a strict habit of always writing the base case first,
so that a recursive predicate looked *wrong* if there wasn't a non-recursive
clause right at the beginning, I stopped making that mistake.

	Maybe we should use code templates for common patterns, although
	I suspect the best solution is decent partial evaluation.

One commercial Prolog system I came across while still at Quintus
(so >10 years ago) boasted a partial executor, but it was dreadful.
It did just enough to make your program bigger and slower.

Perhaps someone should port Mixtus to SWI.  Has this already been done?

	Whatever, too often Prolog coding feels
	like assembler coding; I think: I can't believe I'm writing this code
	pattern *again*!  why can't I specify it in some concise, abstract
	syntax and turn a handle to get efficient code out?

Amazing how a language so clunky is still better than C, isn't it?

I'm sorry to say that I agree with you.

Mercury has higher-order predicates and a compiler that can do deforestation.
Worth a try?

	And in some sense I think the same goes for data structures...
	
I've seen some papers on automatically unrolling data structures (which was
a blow, because I was working on the topic myself when I saw them, and that
made me abandon them).  Tends to rely on strong types (such as Mercury has).

	NB why is
	
	  type bag --> bag( element, multiplicity, bag)
	            |  bag
	
	rather than
	
	  type bag --> ordset(pair(element,multiplicity))
	
Surely it's obvious?  Date, time, space, abstraction, and correctness.

Date:	I wrote library(bag) before I wrote library(ordset).
Time:	Matching bag(E,M,R) = X costs 4 memory references.
	Matching [E-M|R]    = X costs 5 memory references.
Space:	bag(E,M,R) costs 4 words (3 in Mercury).
	[E-M|R]    costs 5 words (4 in Mercury).
Abstraction:  you cannot actually implement bag in terms of ordset(pair)
	without cracking open the ordset abstraction.  For example, taking
	the union of two ordsets of pairs is *NOT* the same as taking the
	union of two bags, so special-purpose code has to be written
	anyway.  That is, you have to work *inside* the ordset abstraction.
Correctness:
	The intersection of bag(a,2,bag) with bag(a,1,bag) is bag(a,1,bag).
	The intersection of [a-2] with [a-1] is [].

If you meant why isn't it list(pair(Element,integer)), then the answer is
time, space, debugging, and error prevention.

Debugging:
	By attaching a distinctive functor to bags, I could give them their
	own portray/1 definition.
Error prevention:
	I did NOT want bags to unify with lists.  Distinct abstract data
	types should have implementations that do not unify.  And wrappers
	are Bad Style, so it is not enough to put a wrapper around a list.

Since special-purpose code had to be written anyway (for correctness),
and a special-purpose data structure had to be written anyway (so that
it would not incorrectly match something with different properties), it
seemed good to me to use a design that was time- and space-efficient.

You should combine existing data types WHEN THAT WILL WORK.