1989-90 ACADEMIC ACTIVITIES REPORT NAME: TIMOTHY J. HICKEY DEPARTMENT: Computer Science I. INSTRUCTIONAL ACTIVITY (Summer 1988, Fall 1988, Spring 1989) a Semester Course Number and Title Class Contact Enrollment Hours Undergrad. Graduate Weekly 1. Autumn 1989 CS140 Logic Programming 6 hr/wk 5 u.g., 2 gr. 2. Spring 1990 CS150 Compiler Design 9 hr/wk 1 u.g., 6 gr. b) Advising (total contact hours per week: ) 5 hr/wk 1) number of general or freshman advisees: 13 2) number of undergraduate departmental advisees: 9 3) number of graduate advisees: 3 c) Please describe your involvement in the direction of senior theses, graduate dissertations and other student research projects. 1. I have three graduate students (S. Mudambi, D. Smith, X. Wang) whose dissertation work I am guiding. 2. I am on the dissertation committee for two CoSci graduate students (Xiru Zhang, Evangelos Simoudis) 2. I am on the dissertation committee for two Chemistry graduate students whose research involves some computer science (Todd Miller[Chemistry], Ping Wan[Chemistry]) 3. I am also providing ongoing help to 2 graduate students working on their dissertations (R. Sun, L. Bookman) 4. There will be two undergraduates participating in research this summer funded by an NSF grant of which I am a co-PI (with J. Cohen) II. RESEARCH, PUBLICATIONS, ARTISTIC CREATION (use additional page if necessary.) a) Describe current research activities or work in progress: My current research is in two areas: Microanalysis and Logic Programming. In MICROANALYSIS, I am currently working on one solo project 1. COMPLETE AUTOMATION OF A CLASS OF FUNCTIONAL PROGRAMS. This is work building on my paper [HICK 88] w J. Cohen and on work by P. Flajolet and his group. It views functional programs as maps between vector spaces of distributions on the input and output and seeks to completely describe these maps when the input is restricted to a finite dimensional subspace of distributions parameterized using the APG idea from [HICK 88]. Previous work [FLAJ] viewed these programs as linear functionals which map input distributions to execution times and this prevents the study of the composition of functional programs. This greatly limits the class of programs that can be analyzed. My work is directed at removing this restriction and hence greatly increasing the class of programs that can be analyzed. and two collaborative projects: 2. DEVELOPING THEORETICAL MODELS AND PRACTICAL TOOLS FOR THE ANALYSIS OF PARALLEL ALGORITHMS (w J. COHEN). We have submitted a paper on this topic and are continuing research in this area. 3. MICROANALYSIS OF SIMD PROGRAMS (w ZG MOU) We are applying the techniques of microanalysis to automatically determine the execution time of DIVACON programs which execute on the 64K processor Connection Machine. We are preparing a paper on this research. In LOGIC PROGRAMMING, my main project for the past year has been 1. CONSTRAINT ABSTRACTION. I have been developing a new language, CLP*, that is based on a new model of computation which encompasses both the lambda calculus model of LISP and the first order logic model of PROLOG. This language can be viewed as a synthesis of the two best known AI languages (LISP and PROLOG). It differs from all previous work in that it is based on a new model of computation and is not simply an "ad hoc" joining of the two languages. I have developed a theoretical foundation for CLP* and have implemented an efficient compiler. I am currently preparing a paper on this work which will be submitted in the next month or two. I am also involved in collaborative research with colleagues and graduate students: 2. PARTIAL EVALUATION OF CONSTRAINT LOGIC PROGRAMS (w D. SMITH) We are extending the partial evaluation technique to CLP programs and building both elegant theoretical models and practical software tools that perform very well for real programs. We have submitted a conference paper on a special case of this project and are preparing a journal article describing the general theory and implementation. 3. PARALLEL CONSTRAINT SOLVING (w XJ WANG). We are developing and analyzing parallel algorithms for constraint solving. Currently we are implementing a parallel version of the simplex algorithm for solving linear inequalities on the Connection Machine (a SIMD machine with 64,000 processors). Current research in parallel execution of logic programs has focussed on AND and OR-parallelism, our goal is to develop the first CLP interpreter which makes use of a new source of parallelism, Constraint parallelism. 4. OR-PARALLEL PROLOG SYSTEMS (w S. MUDAMBI). We are studying the implementation and analysis of OR-parallel Prolog systems on state-of-the-art parallel processors. Shyam has ported the SICS Aurora system from the Sequent (w maximum of 30 processors) to the Butterfly class of machines and has been the first person to execute Prolog on a machine with 40 processors. In the coming months, we will have access to a 128 processor Butterfly II (on the internet) and expect to have the world's fastest Prolog system. It should be over 1000 times faster (4 MLIPS) than the best commercial Prolog system running on a standard workstation. My collaboration with Shyam involves developing models to analytically study the performance of this type of large program (30,000 lines of C code) on large parallel machines, and to develop strategies for increasing the efficiency of such programs, as well as finding and developing interesting applications (e.g. the Human Genome project, Molecular Biology, ...) 5. METALEVEL INTERPRETATION OF CLP. (w J. COHEN). Our goal is to develop a new theory of constraint logic programming which is based on rewriting systems (similar to A. Colmerauer), but which maintains the rigor of classical CLP theory (as with Lassez and Jaffar). We have developed an implementation based on this theory and have used it to implement several new CLP languages. Articles submitted for publication: 1. Computer Assisted Microanalysis of Parallel Programs (with J. Cohen, H. Hotta, T. Petitjean) submitted to ACM TOPLAS Currently being revised according to referee's suggestions. 2. Partial Evaluation of CLP(FT), (with D. Smith) submitted to the North American Conference on Logic Programming -- 1990. Articles in preparation 1. Constraint Abstraction and the Mu Calculus 2. DIVACON - the language and its implementation (w ZG Mou) 3. Partial Evaluation of Constraint Logic Programs (w D. Smith) b) Manuscript (s) or artistic work accepted for publication (List journal or publisher and anticipated publication date.) c) Publications since June, 1989 (with inclusive page reference for articles). Please use standard form: author(s) or editor(s), title, number of pages, publisher, location, date. 1. ``Global Compilation of Prolog'', with S. Mudambi, J. Logic Programming, 7:3, 193-230 d) Artistic creation (please describe) III. AWARDS AND HONORS (dates) Distinguished Lectures: Research Awards: 1. Second year continuation of an NSF research grant in Logic Programming CCR-8718989, $170,786, co-PI with J. Cohen. 2. Second year continuation of an NSF research grant in Microanalysis CCR-8814261, $75,566, participant w J. Cohen, 3. REU supplement to CCR-8814261 supporting undergraduate research $8,800, co-PI with J. Cohen IV. PROFESSIONAL ACTIVITIES OUTSIDE THE UNIVERSITY (lectures, activities in professional societies, legislative testimony, paid consulting, equity arrangements, etc.) 1. Refereed articles submitted for publication in a) Journal of Logic Programming (2) b) Journal of the ACM (1) c) International Conference on Logic Programming 1990 (8) d) International Journal of Parallel Programming (1) e) North American Conference on Logic Programming 1989 (2) 2. Refereed 1 NSF proposal V. PARTICIPATION IN DEPARTMENTAL ACTIVITIES AND ADMINISTRATION 1. Performed applicant search for Systems Administrator and am currently the supervisor of our System Administrator, Richard Congdon who administers the departments Computing Resources, including (HP9000/850 mainframe, 11 Sun Workstation, 5 HP workstations, 1 BBN parallel computer, 2 Lisp Machines, 25 PCs) 2. Participated in developing requirements for a Master's program in Computer Science and in the selection of new graduate students. VI. PARTICIPATION IN UNIVERSITY ACTIVITIES, COMMITTEES, ETC. 1. Member of Wien Advisory Committee 2. Member of Curriculum Advisory Group for Brandeis Summer Disc. Program 3. Member of University Studies Council Sub-Committee on Math. and Science