BIO
Ira Pohl has contributed importantly to artificial intelligence (1,2,4,5) analysis of algorithms (3), programming languages (7-9), computer science education (11,12,14,16), and societal implications of computer science (6). In 1970 through 1986, he published seminal work on the theory of heuristic search (1, 5). He pioneered in the development of adversary techniques (3). This work on min-max selection became a textbook example displayed in many standard texts including Knuth's volume 3 of The Art of Programming: Searching and Sorting; and Aho, Hopcroft and Ullman's The Analysis of Algorithms. Pohl's work on the theory of heuristic search, and the invention of bi-directional methods of heuristic search are standard in major artificial intelligence texts.
In 1981, his book (10) with Alan Shaw was pioneering in taking the view that basic CS should be analogous to other basic science courses, studying the whole field rather than being a programming course. In 1984, his A Book on C (11), revolutionized the view of C as a general purpose programming language - not just a systems implementation language. This book also introduced the method of dissection. This teaching and code-understanding scheme has since become a hallmark of his subsequent books for teaching programming (11-17) and has been widely imitated. They have won a world audience and are translated into Japanese, Korean, Chinese, German, Italian, Spanish, and Dutch. In 1995, he pioneered online web-based training for C and C++ by developing courses for DigitalThink.com. He likewise pioneered eMatter books by consulting with and developing original documents for MighyWords.com (17).
A Sampling of Technical Publications
Professor Pohl has taught and lectured on Computer Science throughout the world. He was an early member of the Information Sciences Department at UCSC and helped transform it to a prominent research Computer Science Department. He also developed an internationally recognized summer program under the auspices of the UCSC Extension service. This enabled it to become the pre-eminent professional education outreach service in Silicon Valley.
Detailed Descriptions
More detail in each of the following major areas follows:
Most influential was Pohl's work in heuristic search algorithms for AI, both theory and implementation. Pohl's work on bidirectional search and a worst-case (adversary analysis) of such algorithms was pioneering. It is accepted in the literature as foundational. See for example the treatment on Search in the Handbook of Artificial Intelligence or in Nils Nilsson's Principles of AI. Ideas from this work continue to be explored. Most recently Henry Davis has shown that his proposals on dynamically weighted search were both empirically and theoretically well founded. Bidirectional search which Pohl pioneered is a fundamental technique in the field.
In 1984, Pohl's paper with George Politowski, "D-node retargeting in bi-directional heuristic search", gave significant impetus to correcting earlier problems in making search efficient. The D-node is analogous to a proved lemma that is used to reshape the deductive search. In 1986, Pohl's paper with D. Ratner on "Joint and LPAI" investigated piecewise approximation algorithms that are highly efficient. These together with other work in this period further explored several of Pohl's innovations in heuristic search.
Pohl's work is now standard AI theory as found in the major AI texts.
"Pohl has proposed several generalizations of AI, including a scheme for bidirectional search, and a method that changes the relative weighting of h and g as search proceeds. Our use (Nilsson's Principles) of the monotone restriction is based on Pohl. Pohl … analyzes the effects of errors in the heuristic search algorithm" - Nilsson: Principles of AI, page 95 .
"Heuristics" by Judea Pearl (the definitive monograph in the mid
80's on the topic) has 12 references to Pohl's work (see p376), the most
except for the author and one other researcher in a list of close to
200 researchers.Into the Heart of the Mind by Frank Rose. This book published in 1984 has a chapter "Should Robots have Civil Rights," a topic Pohl pioneered and published several papers on. The book dealt with the leading AI researchers at UC Berkeley and devoted one chapter to me (a visitor to UCB at the time).
Achievements
Pohl's early work in sorting theory has become a standard example in the algorithms text. Pohl's min-max finding algorithm was pioneering in proving by adversary analysis that an algorithm was optimal. The technique at this point was not yet understood as a standard proof methodology. Here much credit is due Knuth and Ullman in pointing out that various researchers had used such techniques to prove optimality. Knuth's volumne 3 of The Art of Programming: Searching and Sorting, was key to this understanding. Pohl later proved the same algorithm was expected case optimal.
Other work includes a first successful efficient bidirectional shortest path algorithm and a proof that the cardinality comparison rule is optimal in selecting search direction. The Pohl-Warnsdorf (Knuth's name for this algorithm) recursive descent algorithm for finding Hamiltonians (see Pohl :CACM 1967).
Achievements
Pohl has an interest in the social implications of computer science. Here Pohl's work resulted in the paper, "Should Robots Have Nuclear Arms". It is an outgrowth of two of Pohl's themes. One is that we have to be careful in our implementation and control of AI technology as it is not automatically benign. Two there is a three stage schema for how technology integrates into society. The last stage of which involves paradigmatic change. Pohl's last efforts here have been in guiding the occasional student, most recently Wynship Hillier, who won a UCSC undergraduate award for his work on caller-id and its social impacts.
Two papers explaining Pohl's point of view were given
in 1984, "A Hierarchy for Classifying AI Implications", and "Social
Implications of AI". In both Pohl pro-
moted a tripartite classification of impact of technology on society. Pohl further
explored this in the context of criticism of SDI in "Should Robots have
Nuclear Arms", published in 1987.
Papers
Pohl, I. 1987. "Should Robots Have Nuclear Arms?" in Future Generations Computer Systems. v.3, pp. 111-115.
Pohl, I. 1986. "SDI Software: AI is not the answer," appeared in SIGART Newsletter, April 1986, pp. 2-3, Software Engineering Notes, April 1986, pp. 18-19 and ABACUS Magazine, Summer 1986, pp. 1-3.
Recently Pohl's most active work has been in publishing books on C (with Al Kelley) , C++ programming, and Java (with C. McDowell). Pohl has now published a large number of books on C, C++ programming, Java, and one book on the foundations of computer science The Nature of Computation (with Al Shaw).
The Nature of Computation was used both
at UCSC and at the Uni-
versity of Washington for a long time. Internationally, it was used at VU in
Amsterdam, one of Europe's leading CS departments as their foundational curriculum,
and was taught by Prof. R.P. Van de Riet together with Dutch notes augmenting
and updating this work. The book was ahead of its time and worse used pseudocode
instead of Pascal for describing algorithms. It inspired much better successors
such as David Harel's Algorithmics.
In 1984 A Book on C (with Al Kelley) came out. It did two novel things: It treated C as a general purpose programming language suitable for beginning students and it use an innovative teach by example method which Pohl and Al Kelley invented called "dissection". Subsequently many such books have come out. Why this is surprising is that between 1972-84, C as a language was the provenance of system programmer and thought to be too complex and opaque for beginners. It was treated as a specialized systems implementation language. This book is now in its 4th edition. Its success can be measured in its longevity and in the fact that it is translated into Japanese, Dutch, German and Spanish. It is considered, along with K&R and Harbison and Steele, as one of the handful of premiere books in this literature. For example in his recent book, C with Excellence, Henry Ledgard, a leading programming methodologist, singles out Pohl's text for its programming craftsmanship.
In 1985, Pohl began efforts in assimilating C++ and object-oriented programming. His first book on this subject, C++ for C Programmers is now in its 3rd edition and is translated into Japanese and Korean. It was among the firsts books to argue for this transition and to treat C++ as evolutionary and a better C. Again this is now a standard theme and treated as the norm. It also has warnings about C++'s complexities and the need for simplifications and built-in garbage collection to simplify the programming and debugging task. To some degree JAVA's success is a ratification of these criticism. The book also endorses Grady Booch's view of the need to have a systematic approach to object-oriented programming, as found in his critical work in Object-Oriented Analysis and Design. An offshoot from this book is C++ for Pascal Programmers also in second edition.
In the 1990's many of these books have been substantially revised to include new developments in the C and C++ community. Most importantly C++ has been vastly enhanced in its basic facilities and in its standard libraries. Most recently the STL library has been added to the standard. Pohl has a new book C++ Distilled (Addison-Wesley 1997) appearing on these developments. Also Pohl's Object-Oriented Programming Using C++, now in its 2nd edition, contains discussion of how STL classes are developed and used.
The book Java by Dissection, by Pohl and Charlie McDowell, (Addison-Wesley 1999) uses dissection to discuss and explain Java and Swing programming for the computer science student. It is intended for the CS 1 course as well as for a generic advance programming course where the students learn GUI programming, sockets and threads. Pohl also wrote the first original content eMatter book, STL Distilled and Generic Programming, (MightyWords, 1999, 95 pages).
Achievements
Programming Languages and Methodology
Pohl's programming books include key books on C, C++ and Java. They discuss object-oriented programming and generic programming using STL. They pioneered the use of C as a standard general purpose language. They pioneered the switch from Pascal, Fortran and C to C++ as a better C. They exploited the "dissection" method of explication of new ideas to teach programming.
Pohl's work with his PhD student, Daniel Edelson, on embedding garbage collection in C++ through the use of smart pointers is highly regarded as a model for the smart pointer pattern (see Scott Meyers: More Effective C++, Addison Wesley 1996 and Gamma, etal, Design Patterns, Addison-Wesley 1995 p209 the proxy pattern). Edelson and Pohl published three joint papers. The work by Edelson included the invention of smart pointers. A paper we published jointly in a strongly refereed conference was D. Edelson and I. Pohl (1991), " A Copying Collector for C++", Usenix C++ Conference pp85-102.This was principally Daniel's work, Pohl collaborated on early papers exploring these ideas. Ideas on polymorphism as being more important then inheritance (a form of polymorphism) were given in the keynote address to the Netherland's computer Society (1991).
AchievementsIra Pohl currently is the online line C++ columnist with FATBRAIN.com. He has written over 20 columns including these:
To date Pohl has overseen 5 PhD's. In the mid 1980's these were largely tied to AI, especially heuristic search theory, which was jointly developed with Danny Ratner, Karim Said, and George Politowki. More recently, Pohl worked with Phil Levy on software reuse and Daniel Edelson on criticizing C and C++, and adding garbage collection to C++ libraries using the smart pointer proxy pattern.
Pohl supervised Daniel Edelson in his PhD work. This work on embedding garbage collection in C++ through the use of smart pointers is highly regarded as a model for the smart pointer pattern (see Scott Meyers: More Effective C++, Addison-Wesley 1996 and Gamma, etal, Design Patterns, Addison-Wesley 1995 p209 the proxy pattern). We collaborated on early papers exploring these ideas.
In 1984, Pohl's paper with George Politowski "D-node retargeting in bi-directional heuristic search", gave significant impetus to correcting earlier problems in making search efficient. The D-node is analogous to a proved lemma that is used to reshape the deductive search. In 1986, Pohl's paper with D. Ratner on "Joint and LPAI" investigated piecewise approximation algorithms that are highly efficient. These together with other work in this period further explored several of his innovations in heuristic search. D. Ratner together with M. Warmuth were able to prove Pohl's conjecture that sliding tile puzzles were NP complete.