gjohnson@cornell.UUCP (05/22/84)
Here is a problem/challenge: Say you have two vectors A and B of length n, and both of them are in ascending numeric order. Write an APL expression which sums those elements of B which occur somewhere in A, and which operates in linear time. Alternatively, prove that there is no such APL expression. (I have not solved this problem, but it seems to me that the latter alternative more likely.) There are a few ways to appropriately restrict the set of allowable expressions. For instance, there is an annual contest to take the digits of the current year and write the shortest expressions involving those digits which evaluate to each of the numbers from 1 to 100. The contest has certain rules about permissible APL expressions. Assuming that "epsilon" operates in (m+n)log( n ) time, an nlog( n ) expression is: +/( B epsilon A ) / B In a conventional programming language, one can write a loop which in effect merges the two lists, and detects elements of B which occur in A. Of course, such a program would be unintelligible without careful study, whereas anyone who knows APL would immediately recognize what the above phrase does; in fact, the phrase might even be taken as a specification of the problem. Several researchers are active in "program transformation" techniques. Might it be possible to extend APL so that one could take an easily understandable APL expression and algebraically transform it into an equivalent efficient but perhaps unintelligible expression? - Greg Johnson gjohnson@cornell