Path: utzoo!utgpu!attcan!uunet!lll-winken!ames!pasteur!ucbvax!decwrl!megatest!djones
From: djones@megatest.UUCP (Dave Jones)
Newsgroups: comp.lang.misc
Subject: Re: Clever programming tricks wanted
Message-ID: <1184@goofy.megatest.UUCP>
Date: 12 Jan 89 23:49:25 GMT
References: <47380@yale-celray.yale.UUCP)
Organization: Megatest Corporation, San Jose, Ca
Lines: 33

From article <47380@yale-celray.yale.UUCP), by wald-david@CS.YALE.EDU (david wald):
) In article <4061@hubcap.UUCP) mcvax!etive.ed.ac.uk!gvw@uunet.UU.NET (MOBY) writes:
))I'm looking for "clever" programming tricks.
) 
) A year or so ago someone showed me a paper in which the author described
) a semi-automated hack generator (my phrasing, not the author's).
) Essentially, the generator would be given a description of a common
) function (say, min() or max() or some such), and would then attempt to
) generate the shortest-length sequence of assembly language instructions
) (or perhaps, shortest sequence with fewest branch instructions) that
) would compute the function.  Yes, I know this is uncomputable in
) general.  The point was that 1) the functions given were all both simple
) and reasonably common, thus being perhaps worth a certain amount of
) effort (from the point of view of writers of code generators), and 2)
) the program didn't actually try to prove its answers.  It would test its
) generated functions for equality with the supplied function at (say) 100
) scattered points.  If the hack worked on those points it would be
) returned to the user, who could then attempt to prove it correct.
) 
) Some of the code generated by this thing was extremely non-intuitive,
) even when it was correct, making use of obscure flag settings and such,
) and certainly qualified for the "hack" title.
) 
) Does any one recognize this work?  I'll try to dig up the reference.
) 
) 

I recall having read such a paper in some computer journal.
But as I recall, this paper claimed to prove that the result correctly
computed the function, and was optimum.  I found a counterexample (a shorter
instruction sequence computing one of the functions -- min() I think
it was.  I mailed the counterexample to the author, but I never received
a response.