|
Remembering Ken Iverson Acknowledgments I am indebted to Chris Burke, Eric Iverson, Eugene McDonnell, Donald McIntyre, Roland Pesch, Joey Tuttle, and Arthur Whitney for reading earlier drafts of the paper. 0. Beginnings I first met Ken Iverson early in 1981 in Toronto, when he invited me to dinner, along with Mrs. Jean Iverson, and Eugene McDonnell, Lib Gibson, David Keith, and Jane Minett of I.P. Sharp Associates. I believe the dinner happened because Eugene mentioned me to Ken, mainly due to The N Queens Problem paper [0] I had submitted to the Recreational APL column that he wrote and edited. So now not only was I to meet the great Ken Iverson, inventor of APL, but I was also to get a free dinner. The latter was a consideration: at the time I was a graduate student at the University of Toronto. At the appointed hour I went up to Ken’s apartment on the 47th floor of the Manulife Center. I was so in awe of the great man that I took scant notice of the spectacular view—from the apartment one can see Niagara Falls, a 90 minute drive away—until Ken directed me to do so. We then went for dinner at a restaurant on King Street. I don’t remember much about the dinner, except for the way Ken left the tip. The change came back from paying the dinner check, in the form of the dingiest looking bills you ever saw. Ken took out his wallet, extracted some crisp clean bills, and crumbled them up before leaving them on the tray. In another sense, I had “met” Ken Iverson years before, when I learned APL during my undergraduate studies at the University of Alberta, from reading the APL\360 User’s Manual [1] and from working at the computer terminal. Since I did not have direct access to Ken, I read his papers carefully, principally The Design of APL [2], The Evolution of APL [3], and Notation as a Tool of Thought [4]. I also further acquainted myself with APL during the summers of 1975 and 1976, when Lib Gibson hired me to work as a summer student at I.P. Sharp in Calgary. 1. From APL to J The late 70’s and early 80’s were an exciting time for APL. APL was a commercial success. APL was taught in schools and universities. APL conferences were well-attended. (I attended my first APL conference in 1979 in Rochester, and my recollected impression is that the parallel sessions at the conference each had audiences of over a hundred.) Ken had published his seminal paper Operators and Functions [5] in April 1978. He went from IBM to I.P. Sharp in Toronto in 1980, and there collaborated with Arthur Whitney on Practical Uses of a Model of APL [6] in 1981-82, leading to Rationalized APL [7] in January 1983, multiple editions of A Dictionary of the APL Language between 1984 and 1987, and A Dictionary of APL [8] in September 1987. Within I.P. Sharp, the phrase “dictionary APL” came into use to denote the APL specified by A Dictionary of APL, itself referred to as “the dictionary”. At that time, the main APL vendors were IBM, STSC, and I.P. Sharp, and all were active in developing and extending the language. IBM had APL2, based on the work of Trenchard More and Jim Brown [9, 10, 11]. Work on APL2 proceeded intermittently for 15 years [12], with actual coding starting in 1971 and APL2 becoming available as an IUP in 1982. STSC had an experimental APL implementation called NARS [13]. NARS and APL2 differed in fundamental respects from dictionary APL (and differed from each other). I.P. Sharp implemented the new APL ideas in stages, complex numbers, enclosed (boxed) arrays, match, and composition operators (on, over, under) in 1981 [14, 15], determinant in 1982 [16], and the rank operator, lev (left), dex (right), and link in 1983 [17]. However, the domains of operators were restricted to the primitive functions or subsets thereof. I.P. Sharp also had SHARP APL/HP [18], principally the work of Arthur Whitney with the assistance of Rob Hodgkinson. An important stepping stone from APL to J was SAX [19], SHARP APL/Unix, written in C and based on an implementation by STSC. An alpha version of SAX became available within I.P. Sharp around December 1986 or early 1987. From that time to August 1989, when the first J source line was written, I had access to SAX, and in the later part of that period used SAX on a daily basis. SAX implemented dictionary APL in part, and was upward-compatible with mainframe SHARP APL in order to run applications ported from there. It permitted derived or user-defined functions as arguments to operators, and had the special APL characters, workspaces, and the del-form function definition. However, it did not permit functions and operators to be named using the assignment arrow, as in the phrase sum←+/ , precluding what later came to be called tacit definition. (The dictionary specified such assignment.) It also did not have hooks and forks [20], for those were not yet invented. For Ken, an important drawback to SAX was that it was not widely and freely available. From a personal perspective, another important stepping stone from APL to J was the writing of my APL87 paper Some Uses of { and } [21]. At the time both Ken and I were working for I.P. Sharp in Toronto, and the ideas in the paper evolved over many conversations with Ken. Writing the paper refined and sharpened my understanding of dictionary APL. Arthur Whitney, from collaborating with Ken on Practical Uses of a Model of APL [6] in 1981-82, inventing the rank operator while on the train ride to the APL82 conference in Heidelberg in 1982 [22, 23], and implementing SHARP APL/HP in 1986 [18], went on to Morgan Stanley in 1988 and there invented A [24]. He later invented k [25] in 1993 and q [26] in 2003. (Arthur is a classmate from the University of Alberta; over the years our paths have crossed many times, and each time I had benefitted. But that is a story for another time.) In the wider world, the PC revolution was in full swing. It was now possible to have a computer (for example, the AT&T 3B1 UNIX PC or the IBM PC/AT) at home that was a reasonable platform for developing an APL system. Not too long ago, such a platform would be under lock and key in a room with a raised floor, inaccessible to mere mortals and not readily available for experimentation. The conditions were ripe for ... 2. J The story of how J began has been told in detail by Donald McIntyre [27]. Ken himself wrote in A Personal View of APL [28]:
It’s funny, but my recollection is that at the time I thought I recruited Ken. Whoever recruited whom, I won a great prize when Ken decided he and I should work together. The final impetus that got J started was the one-page interpreter fragment that Arthur wrote, recorded in Appendix A of An Implementation of J [29] and also reproduced in Appendix A below. My immediate reaction on seeing the page was recoil and puzzlement: it looked nothing like any C code I had ever seen. (“Is it even C?”) However, Ken counselled that I should reserve judgment. As recounted in An Implementation of J, it then happened that: I studied this interpreter for about a week for its organization and programming style; and on Sunday, August 27, 1989, at about four o’clock in the afternoon, wrote the first line of code that became the implementation described in this document. The name “J” was chosen a few minutes later, when it became necessary to save the interpreter source file for the first time. I consciously designed and built the system around “Table 2: Parsing Process” in A Dictionary of APL [8], which I had studied carefully and modelled at least two different ways between 1986 and 1989. The C data and program structures were designed so that the parse table in C corresponded as directly as possible to the parse table in the dictionary. I set as an objective of being able to show Ken the C source for the parser, and have him verify that the syntax being implemented was correct. We never did carry out the exercise (of Ken reading the C source), but I reckon I met my objective, because eventually Ken replaced the table in the dictionary with the parse table from the C source [30, section II E]. Other effects of trying to meet the objective were entirely beneficial. Years after the initial implementation, I happened to re-read Ken’s APL87 paper APL87 [31]. In retrospect, the paper, in five pages, prescribed all the essential steps in writing an APL interpreter, in particular the sections on word formation and parsing. Ken and I had in mind to implement A Dictionary of APL [8] together with hooks and forks (phrasal forms) [20]. For years, Ken had struggled to find a way to write f+g as in calculus, from the “scalar operators” in Operators and Functions [5, section 4], through the “til” operator in Practical Uses of a Model of APL [6] and Rationalized APL [7, p. 18], and finally forks. Forks are defined as follows:
The choice to implement forks was fortuitous and fortunate. We realized only later [32] that forks made tacit expressions (operator expressions) complete in the following sense: any sentence involving one or two arguments that did not use its arguments as an argument to an operator, can be written tacitly with fork and @: (compose) and [ (left) and ] (right) and constant functions. If @: were replaced by the equivalent special fork [: f g , then a sentence can be written as an unbroken train (sequence of forks). Because explicit definition (the analogue of del-form definitions in APL) was relatively complex, it was not implemented until some months had elapsed. As well, the restriction in APL that only nouns (arrays) can be assigned never made it past the first day, for there was no way other than by assignment to name verbs, adverbs, and conjunctions (functions and operators). Therefore, for some months all verbs were tacit; that is, all functions were defined as operator expressions. These circumstances forced us to explore tacit definition extensively. Meanwhile, Ken was concerned about the usefulness of forks, and worked hard at finding examples of forks beyond those in Phrasal Forms [20]. After a while, it seemed that everything was a fork. The explanation lies in the proof of completeness for tacit definition [32]: if the root (last) function in a sentence is applied dyadically, then a fork is required to write the sentence tacitly. Since we wrote tacit definitions exclusively, it was no wonder that we ran into forks constantly. As well, we had little trouble expressing computations tacitly because of the completeness. Eric Iverson founded Iverson Software Inc. in February 1990 to provide an improved SHARP APL/PC product. It quickly became obvious that we had shared interests and goals, and in May 1990 Ken and I joined Iverson Software Inc. The company soon became J only. The name was changed to Jsoftware Inc. (www.jsoftware.com) in April 2000. Eric adapted the session manager from SHARP APL/PC for J in time for the first release. Over the years, he was responsible for everything that was not the interpreter proper—the integrated development environment, the Windows interface, and all other interfaces—and made contributions to the language itself, including locatives, control structures, and memory-mapped files. Eric also handled product packaging and release details. Chris Burke joined us in early 1994 and wrote the application libraries, in particular the plot package, the debugger, the project manager, and the performance monitor. Work proceeded rapidly from August 1989. The first public presentation took place on 1990-02-26 when Ken and I gave a talk complete with a live demo to the Toronto APLSIG at the Toronto Board of Trade. The first release of the software was at APL90 [33] in Copenhagen in August 1990, when J was made available as shareware to the Software Exchange. (You can still get this version from various archives.) The first J conference was held on 1996-06-24 to -25 at the Koffler Institute of the University of Toronto. There were 123 attendees and 12 contributed papers in the proceedings [34]. In working with Ken, I soon realized that Ken had a flexibility of mind that is breathtaking. Two examples illustrate this point. Example 0: For the first few months, the special APL characters and the ASCII spelling co-existed in the system. It was Ken who first suggested that I should kill off the special APL characters. I myself resisted for a few weeks longer, until the situation became too confusing, for reasons described in J for the APL Programmer [35, p. 11]. Example 1: It came time to implement \ (“scan”). On that day (in the first half of 1990), during lunch at Josie’s Cafe on Yonge Street, I asked Ken innocently, “Have you ever wanted to scan something other than reduction?” The question was not even well-formed, because the APL paradigm is so powerful that it usually pushes aside alternative thoughts. Nevertheless, the discussion that then proceeded was productive, and quickly led to the realization that [35, p. 16]:
Much recent work involved “recognizing” phrases and implementing them with special code. The expressive power of tacit expressions makes this a fruitful approach. For example, if f is a primitive proposition, then:
are supported by special code. A primitive proposition is one of the relational atomic verbs (scalar functions) = ~: < <: > >: or the verbs E. or e. (respectively, “substring match” and “member of”; a legend of the J words used in the text is available in Appendix B below.) For example: 'boustrophedonic' (e.i.1:) 'aeiou' NB. index of first vowel 1 'boustrophedonic' (e.i:1:) 'aeiou' NB. index of last vowel 13 If the target is found near the beginning of the search, the result is computed instantaneously (and in time independent of the lengths of the arguments for atomic verbs f). Even if the target is found only at the end of the search, the improvement in time is by a factor of two or more. In either case the space used is constant for atomic verbs f . Another recent development is a port to the Linux and Windows XP 64-bit operating systems on the AMD64 and Intel EM64T processors [36]. J64 has 64-bit integers and a 64-bit address space. Ken had started to write a companion to the Abramowitz and Stegun classic, Handbook of Mathematical Functions [37]. Such writing was the motivation behind the extended-precision integer and rational number facilities; to the same end, extended-precision floating-point numbers will be also added. The following examples illustrate extended-precision integers and rational numbers: (+%)/\ 10 $ 1 1 2 1.5 1.66667 1.6 1.625 1.61538 1.61905 1.61765 1.61818 (+%)/\ 10 $ 1x 1 2 3r2 5r3 8r5 13r8 21r13 34r21 55r34 89r55 0j40 ": (+%)/ 100 $ 1x 1.6180339887498948482045868343656381177203 The hook x(+%)y is x plus the reciprocal of y , and so (+%)/ is the continued fraction. The first phrase computes convergents to the golden ratio phi in 64-bit IEEE floating-point numbers; the second computes rational convergents to phi; and the third computes phi to 40 decimal places. 3. Remembering Ken Ken and I worked on J in our homes in Toronto, I in my apartment in the High Park area and Ken in his apartment on Erskine Avenue and subsequently in the Manulife Center (a different apartment from the one in 1981, with an even more spectacular view). The arrangement placed me uniquely under Ken’s influence. Oftentimes I found myself at Ken’s house, delivering the latest J version or working on a computer, and many times Ken would invite me to stay for lunch or dinner, explaining that “thou shalt not muzzle the ox when he treadeth out the corn”. Little did I imagine in 1981 that the dinner I had with Ken and Jean then would be the first of many. It is said that if you keep playing chess with a grandmaster, your skills can not help but improve. I had been in almost daily contact with the master since late 1986, and the following are a few of the things I have learned. Credit. When Ken was at Harvard a fellow student habitually stamped his papers “Copyright” or “Confidential”. Howard Aiken, head of the Comp Lab and Ken’s thesis supervisor, advised, “Don’t worry about people stealing your ideas. If it’s any good, you’d have to ram it down their throats!” (A less picturesque version of this story is found in [38, p. 240].) Blame. Ken and I sometimes kidded each other about whose fault it was when something went wrong. He complained in jest that I as implementor had the attitude of “just tell me where to pour the concrete”. And I, in turn, complained in jest that he as designer had the attitude that he was never to blame: If it’s a mistake in the implementation, then it’s obviously my fault; and if it’s a mistake in the design, well then I should have caught it during the implementation. In truth, I am profoundly grateful to Ken for not complaining in the times when I failed him, even when I failed him the same way more than once. I believe that if necessary, he would have forgiven me for seventy times seven times (although even I would probably catch on before too long). Secret to Success. In January 1992, I was in the final struggles of writing my book An Implementation of J [29], having difficulty and under time pressure. Around that time, Ken was polishing off several books and papers, seemingly effortlessly. I asked him what his secret was. His reply was, basically, “First, write 500 papers.” (Ken subsequently gave me some more immediately useful advice about writing.) Reading and Writing Carefully. In the early days I did not have direct access to Ken, and therefore read his papers carefully. Another example is Arthur Whitney’s “one page thing”, which was the final thing I studied (for one week) before writing the first line of source code for J. Over the years, I have benefitted enormously from such careful reading. I later realized that Ken wrote carefully, in the expectation that what he wrote would be read carefully. An exemplar of such writing is the description of “cut” in Rationalized APL [7, p. 19-20]. It annoyed Ken to no end when accused of being “too terse”, for example as in “the dictionary is too terse”, when “terse” means “effectively concise”. Words. As others have recounted, Ken was deeply interested in words, their use and their etymology. He indeed did read the dictionary, and kept a copy of the American Heritage Dictionary [39] (along with other dictionaries) by his easy chair for ready reference. He especially encouraged me to consult the section on Indo-European roots in the back of the AHD, which makes deep and uncommon connections between words. Many of Ken’s relatives and friends received from him the AHD as a present. I myself did not because I’d already owned one years before I met Ken. In fact, I gave him the third edition of the AHD as a present. I think nothing I had ever done impressed Ken quite as much as when I found the word “rhematic” (meaning, pertaining to the formation of words), a word he had been searching for for some time. Thus the phrase “rhematic rules of J” made its way into the J dictionary [30]. Books. Before long, Ken and I discovered that we shared a love of books. We often recommended reading material to each other. A sample of our recommendations: I to Ken: The Language Instinct by Steven Pinker; Climbing Mount Improbable by Richard Dawkins; Lincoln at Gettysburg by Garry Wills. Ken to me: From Dawn to Decadence by Jacques Barzun; Calvin and Hobbes; The New York Review of Books. And, of course, both of us had read The Book of J [40]. Politics. Unsurprisingly, Ken stood up for what he believed in. He once spent a few hours in jail after being arrested during a protest against the Vietnam War. In the same cell was Garry Wills, the historian and author. Respect for People. Ken liked to tell the story of the stoic service agent: At an airport counter an irate traveller was berating the service agent over something or other, which the agent took with stoic forbearance. After the traveller went on his way, the next person in line told the agent, “I am amazed at how well you took that abuse.” The agent smiled thinly and replied, “Oh, the gentleman is flying to Chicago, but his luggage is going to Moscow.” Ken also suggested, “Be kind to someone trying to make a living.” I try to remember this every time a taxi or truck driver cuts me off on the road. A Questioning and Flexible Mind. The flexibility of mind that Ken brought to his work (noted above) was also demonstrated in his everyday life. For example, it astounded me how often and how thoroughly Ken rearranged the furniture in his home. His explanation was, our needs have changed, and we rearranged our surroundings to meet those needs. References
Appendix A. Incunabulum From An Implementation of J [29], Appendix A: Incunabulum. One summer weekend in 1989, Arthur Whitney visited Ken Iverson at Kiln Farm and produced—on one page and in one afternoon—an interpreter fragment on the AT&T 3B1 computer. I studied this interpreter for about a week for its organization and programming style; and on Sunday, August 27, 1989, at about four o’clock in the afternoon, wrote the first line of code that became the implementation described in this document. Arthur’s one-page interpreter fragment is as follows:
typedef char C;typedef long I;
typedef struct a{I t,r,d[3],p[2];}*A;
#define P printf
#define R return
#define V1(f) A f(w)A w;
#define V2(f) A f(a,w)A a,w;
#define DO(n,x) {I i=0,_n=(n);for(;i<_n;++i){x;}}
I *ma(n){R(I*)malloc(n*4);}mv(d,s,n)I *d,*s;{DO(n,d[i]=s[i]);}
tr(r,d)I *d;{I z=1;DO(r,z=z*d[i]);R z;}
A ga(t,r,d)I *d;{A z=(A)ma(5+tr(r,d));z->t=t,z->r=r,mv(z->d,d,r);
R z;}
V1(iota){I n=*w->p;A z=ga(0,1,&n);DO(n,z->p[i]=i);R z;}
V2(plus){I r=w->r,*d=w->d,n=tr(r,d);A z=ga(0,r,d);
DO(n,z->p[i]=a->p[i]+w->p[i]);R z;}
V2(from){I r=w->r-1,*d=w->d+1,n=tr(r,d);
A z=ga(w->t,r,d);mv(z->p,w->p+(n**a->p),n);R z;}
V1(box){A z=ga(1,0,0);*z->p=(I)w;R z;}
V2(cat){I an=tr(a->r,a->d),wn=tr(w->r,w->d),n=an+wn;
A z=ga(w->t,1,&n);mv(z->p,a->p,an);mv(z->p+an,w->p,wn);R z;}
V2(find){}
V2(rsh){I r=a->r?*a->d:1,n=tr(r,a->p),wn=tr(w->r,w->d);
A z=ga(w->t,r,a->p);mv(z->p,w->p,wn=n>wn?wn:n);
if(n-=wn)mv(z->p+wn,z->p,n);R z;}
V1(sha){A z=ga(0,1,&w->r);mv(z->p,w->d,w->r);R z;}
V1(id){R w;}V1(size){A z=ga(0,0,0);*z->p=w->r?*w->d:1;R z;}
pi(i){P("%d ",i);}nl(){P("\n");}
pr(w)A w;{I r=w->r,*d=w->d,n=tr(r,d);DO(r,pi(d[i]));nl();
if(w->t)DO(n,P("< ");pr(w->p[i]))else DO(n,pi(w->p[i]));nl();}
C vt[]="+{~<#,";
A(*vd[])()={0,plus,from,find,0,rsh,cat},
(*vm[])()={0,id,size,iota,box,sha,0};
I st[26]; qp(a){R a>='a'&&a<='z';}qv(a){R a<'a';}
A ex(e)I *e;{I a=*e;
if(qp(a)){if(e[1]=='=')R st[a-'a']=ex(e+2);a= st[ a-'a'];}
R qv(a)?(*vm[a])(ex(e+1)):e[1]?(*vd[e[1]])(a,ex(e+2)):(A)a;}
noun(c){A z;if(c<'0'||c>'9')R 0;z=ga(0,0,0);*z->p=c-'0';R z;}
verb(c){I i=0;for(;vt[i];)if(vt[i++]==c)R i;R 0;}
I *wd(s)C *s;{I a,n=strlen(s),*e=ma(n+1);C c;
DO(n,e[i]=(a=noun(c=s[i]))?a:(a=verb(c))?a:c);e[n]=0;R e;}
main(){C s[99];while(gets(s))pr(ex(wd(s)));}
Appendix B. J Words Used in the Text Full reference in J Introduction and Dictionary [30].
|
|
The last photograph of Ken Iverson, with Rachel Hui, Jean Iverson, and Nicholas Hui,
on Sunday, 2004-09-05,
at the roof-top garden of the Manulife Center,
Toronto, Canada.
[photo by Stella Hui] |
|