Principal Investigator(s) Name(s): John E. Savage PI Institution: Brown University PI Phone Number: (401) 863-7600 PI E-mail Address: darpa@cs.brown.edu Grant or Contract Title: Multiparadigm Design Environments High Performance Design Environments Grant or Contract Number: N00014-83-K-196 Reporting Period: 1 Oct 90 - 30 June 91 (MDE) 1 July 91 - 30 Sept 91 (HPDE) Dear Sirs This is the annual report for N00014-83-K-196. The period 1 Oct 90 - 30 June 91 was the last period for the three-year grant Multiparadigm Design Environments (MDE). Funding was continued for the period 1 July 91 - 30 Sept 91, renewed under the three-year grant High Performance Design Environments (HPDE). The work in HPDE is a natural continuation of the work in MDE. Whereas MDE demonstrated the feasibility of the concept of Multiparadigm Design Environments, HPDE emphasizes more the performace aspects of these environments as well as their use in designing high performance systems. From the point of view of funding HPDE replaced the MDE funding. Given the close connection between MDE and HPDE in theme, PIs, and co-PIs, we are submitting one annual report. Principal Investigator(s) Name(s): John E. Savage PI Institution: Brown University PI Phone Number: (401) 863-7600 PI E-mail Address: darpa@cs.brown.edu Grant or Contract Title: Multiparadigm Design Environments High Performance Design Environments Grant or Contract Number: N00014-83-K-196 Reporting Period: 1 Oct 90 - 30 June 91 (MDE) 1 July 91 - 30 Sept 91 (HPDE) 1. Productivity measures. Refereed papers submitted but not yet published: 41 Refereed papers published: 38 Unrefereed reports and articles: 32 Books or parts thereof submitted but not yet published: 7 Books or parts thereof published: 1 Patents filed but not yet granted: 0 Patents granted (include software copyrights): 0 Invited presentations: 40 Contributed presentations: 17 Honors received (fellowships, technical society appointments, 20 conference committee roles, editorships, etc.): also include descriptions of the specific honors. HONORS: J. Savage: Senior Member of IEEE and IEEE Computer Society. J. Vitter: Senior Member of IEEE and IEEE Computer Society. P. Wegner: Chair IBM Professorship, Keio University, Summer 1991. PROGRAM COMMITTEE CHAIRS AND CO-CHAIRS: P. Kanellakis: 3rd International Conference on Database Theory, (Paris France, December 1990) 3rd International Workshop on Database Programming Languages, (Nafplion Greece, August 91) 11th ACM Symp. on the Principles of Database Systems, (San Diego, June 1992) J. Savage: MIT-Brown Conference on Parallelism and VLSI, Providence, R.I., March 1992. NEW EDITORIAL POSITIONS: J. Vitter: Mathematical Systems Theory: An International Journal on Mathematical Computing Theory J. Vitter: Guest Editor, special issue of Algorithmica on Disk I/O and Memory Access. S. Zdonik: Editor of Proceedings of Persistent Object Systems Workshop S. Zdonik: Journal of Intelligent Information Systems P. van Hentenryck: International Journal of Logic Programming PROGRAM COMMITTEE MEMBERSHIPS: J. Vitter: 31st Annual IEEE Symposium on Foundations of Computer Science, St. Louis, MO, October 1990. IEEE Data Compression Conference, Snowbird, UT, April 1991. MIT-Brown Conference on Parallelism and VLSI, Providence, R.I., March 1992. P. Kanellakis: 2nd International Conference on Deductive and Object-Oriented Databases, (Munich, Germany December 1991). S. Zdonik: Conference on Organizational Computer Systems R. Tamassia: 1991 Workshop on Algorithms and Data Structures PROFESSIONAL SOCIETY ELECTIONS: J. Vitter: Vice-Chair of the ACM SIGACT Executive Committee CONFERENCE LOCAL ARRANGEMENTS: J. Vitter: 23rd Annual ACM Symposium on Theory of Computing, New Orleans, LA, May 1991. Prizes or awards received (Nobel, Japan, Turing, etc.): 3 AWARDS: Andries van Dam: 1991 ACM SIGGRAPH Steven A. Coons Award for Outstanding Creative Contributions to Computer Graphics. P. Klein: NSF Presidential Investigator Award F.K. Zadeck: Best paper award in computer science department of IBM Research Division, 1990. Promotions obtained: 1 Graduate students supported >= 25% of full time: 0 Post-docs supported >= 25% of full time: 0 Minorities supported (include Blacks, Hispanics, American Indians 0 and other native Americans such as Aleuts, Pacific Islanders, etc.; do not include Asians or Asian-Americans): Principal Investigator(s) Name(s): John E. Savage PI Institution: Brown University PI Phone Number: (401) 863-7600 PI E-mail Address: darpa@cs.brown.edu Grant or Contract Title: Multiparadigm Design Environments High Performance Design Environments Grant or Contract Number: N00014-83-K-196 Reporting Period: 1 Oct 90 - 30 June 91 (MDE) 1 July 91 - 30 Sept 91 (HPDE) 2. Detailed summary of technical progress. OBJECTIVES: ----------- The goal of our three-year research program on Multiparadigm Design Environments (MDE), which concluded June 30 1991, was to examine the foundations on which to build design environments, especially those permitting the use of natural paradigms, to express design concepts. The goal of our three-year research program on High Performance Design Environments (HPDE), which started July 1 1991, is to focus our attention on the use of MDEs in the design of high performance applications as well as on performance issues in these environments. During the last year, our work in MDE and HPDE has led to further development of the advanced programming environment FIELD, to research in compiler optimization for high-level languages, and to new advanced languages using constraint paradigms. We have worked on the supporting technologies of databases and graphics: on methods to integrate new and existing computational paradigms in the context of databases, as well as transaction models for heterogeneous multidatabases; on new animation systems and graph drawing techniques. We have performed extended research on algorithms for parallelism in I/O, for caching strategies, for dynamic problems, for good serial approximation and good parallelizable heuristics of hard combinatorial problems. Finally, in this framework we have designed and constructed programmable systolic arrays. APPROACH: --------- ENVIRONMENT AND LANGUAGE DESIGN: On advanced programming environments, we developed a simple and effective integration mechanism, based on selective broadcasting, that allowed us to exploit the synergy offered by integrating a wide variety of new and existing tools. We also developed a variety of simple but powerful tools that dramatically illustrate the power of this integration mechanism. Industry is very interested in this work. On advanced languages progress has been achieved on the design and implementation of Constraint Logic Programming languages and abstract interpretation. On compiler optimization, we developed powerful analysis and transformational techniques applicable to languages that make heavy use of data abstraction and object-oriented programming constructs. Much of this language work is done with industry-based collaborators and finds its way into industrial products. SUPPORTING TECHNOLOGIES, DATABASES AND GRAPHICS: On the principles of database programming languages, we examined methods to integrate new and existing programming paradigms and new approaches to computation for database systems. We examined the principles of object-oriented, logical and constraint-based programming in environments with data persistence. This work will lead to the design and implementation of prototype database programming languages which will considerably extend the power and applicability of existing systems. On the issue of concurrent use of databases, we have developed InterActions: a global transaction model for heterogeneous multidatabases. InterActions support the consistent access of applications that require interacting with multiple databases. They attempt to maximize concurrency while preventing undesirable interference among applications. However, they differ from traditional global multidatabase transactions in that they use a correctness criterion that is weaker than serializability or quasi-serializability. On graphics our research focuses on time-parameterized modeling (sometimes called 4D modeling). We have completed the framework for a large-scale, object-oriented, modeling and animation system. The modeling is accomplished through the exchanging of messages with time-varying parameters between objects, thus inherently providing animation capabilities to the model. The system supports both keyframe specifications and dynamic simulations. ALGORITHMIC TECHNIQUES: On I/O performance we studied new techniques for sorting in disk array environments. We studied new caching strategies based on ideas from data compression. We also studied techniques for making very efficient data structures dynamic. These areas are critical for the implementation of high performance design environments. On approximation algorithms, we studied hard optimization problems arising in the analysis and synthesis of networks, such as to minimize the cost of a network satisfying given communication requirements, by developing algorithms with given bounds on performance. This work has considerable practical import. On parallelizable heuristics, we studied techniques without known approximations for parallelizing hard combinatorial problems and compared their performance to that of proven serial heuristics for these problems. We also show that some heuristics are hard to parallelize. This work has applications in VLSI and routing in multidimensional computer networks. APPLICATION TO HARDWARE DESIGN: On programmable systolic arrays, we developed a programmable architecture, implemented the design in silicon, built a simulator for it, and produced a high-level programming language (NSL) to simplify programming of systolic arrays used as attached co-processors. This work has potential to influence the design of computational engines for research on the Human Genome Project. RECENT ACCOMPLISHMENTS: ----------------------- ENVIRONMENT AND LANGUAGE DESIGN: During the past year, the FIELD environment has been enhanced and expanded by a) rewriting the message facilities for better security and support for multiple message servers, b) integrating of version management, c) completing of a distributed build facility, d) development of a policy server, based on the ideas of Garlan and Notkin, to buffer communicating tools and to define the way tools are used. For example, it can be used to insure testing of a module before it is checked in. Finally, we have introduced a new suite of tools offering dynamic views of the workings of a program such as a view of heap-allocation and I/O to files and other devices. In constraint logic programming, new arc-consistency algorithms (linear in the size of the domain and the number of constraints for specific class of networks) have been designed and implemented. Further results have also been obtained for the handling of disequations and the detection of redundancies inside the simplex algorithm. A new language is also being designed and prototyped. It includes combinators to handle disjunctions of constraints, set-expressions, and user-defined constraints. In abstract interpretation, the generic algorithm we initially designed and analysed has been fully implemented and tested on a sophisticated domain including types, sharing, aliasing, and modes. The results are encouraging and show the viability of the approach. A release of the software is expected for the end of the year. We have developed two new compiler techniques, one to analyze programs containing pointers and another to find and eliminate redundancies. We are also completing a co-edited book for ACM Press entitled ``Code Optimization in Compilers'' as well as studying techniques to aid in restructuring of large software systems. SUPPORTING TECHNOLOGIES, DATABASES AND GRAPHICS: We have developed the concept of constraint query languages for database systems, a new generation of declarative database and knowledge base query languages that generalize the logic-based (relational and deductive) query languages of the 70's and 80's. We also are co-editing the book ``Building an Object-Oriented Database System: The Story of O2'' to appear in the fall of 1991. This is the first collection that addresses the design and implementation of the object-oriented database system O2 developed at INRIA. We developed the formal data model of this system. We investigated the requirements of certain types of planning applications that use and/or modify information in multiple databases. Due to the autonomy requirements of the local databases in the multidatabase, the standard cooperative transaction concepts do not translate into the multidatabase environment in a straightforward way. We worked on determining how to support cooperation in a multidatabase environment. We developed a new approach to the architecture of a query optimizer for object-oriented database systems. Unlike other current research, which approaches query optimization by searching for specific new techniques to solve particular optimization problems, our research involves extensibility of the optimization process itself. We studied new powerful user interfaces for the modeler. The components of the user interface are built into the system instead of on top of the underlying system. Since these components are themselves objects in the system, with time-varying behavior, we investigated this novel idea of a time-varying user interface. This research is currently focused on 3D widgets that provide intuitive functionality for complex object manipulations that cannot be obtained from normal 2D widgets. The user interface capabilities will play a central role in our research towards the design of a unified framework for handling anything from conventional 2-D widgets to 6-D input devices. ALGORITHMIC TECHNIQUES: We have examined a realistic model for parallel disk I/O and present an optimal randomized version of distribution sort giving I/O times significantly less than with disk striping. We have also presented an optimal deterministic sorting algorithm which is an interesting variant of merge sort that positions records for easy sorting. We have also developed optimal algorithms for prefetching based on data compression techniques. The algorithms are both theoretically (in the limit) optimal and good in practice. We have started exploring new approaches to graph connectivity problems in a dynamic environment, where the graph is updated by inserting and deleting vertices and edges. We have obtained significant preliminary results on the on-line maintenance of 3-connected graphs and their 4-connected components. A number of algorithmic investigations have been carried out on graph layout, and network design problems. We have developed an analyzed an algorithm useful in solving large sparse linear systems by Gaussian elimination. The order in which variables are eliminated in solving sparse systems has a major impact on the time and storage required by the elimination process. Our algorithm finds the first elimination ordering that approximately minimizes both time and storage requirements. The algorithm is being implemented and tested on linear systems arising in large-scale scientific computation. We have developed a new parallelizable heuristic that handles graph partitioning and embedding problems that are 100 to 1,000 times as large as those previously handled. We have implemented this massively parallel heuristic on a Connection Machine CM-2, and the results are extremely encouraging. We expect to extend the heuristic to the solution of the planar Traveling Salesman Problem. APPLICATION TO HARDWARE DESIGN: We have built and tested B-SYS, a systolic array prototype system consisting of an 85,000-transistor, 47-processor, fully-custom chip. This prototype, handicapped by a slow bus interface, can perform sequence comparison, a problem crucial to the Human Genome Project, 80 times faster than its 80386 host. Principal Investigator(s) Name(s): John E. Savage PI Institution: Brown University PI Phone Number: (401) 863-7600 PI E-mail Address: darpa@cs.brown.edu Grant or Contract Title: Multiparadigm Design Environments High Performance Design Environments Grant or Contract Number: N00014-83-K-196 Reporting Period: 1 Oct 90 - 30 June 91 (MDE) 1 July 91 - 30 Sept 91 (HPDE) 3. Lists of publications, presentations and reports. Abiteboul, S., Kanellakis, P.C., ``The Two Facets of Object-Oriented Data Models''. IEEE Data Engineering Bulletin, Vol. 14, No. 2, June 1991. A. Agrawal, P.N. Klein and R. Ravi, ``When trees collide: An approximation algorithm for the generalized Steiner tree problem on networks,'' Proceedings, 23nd ACM Symposium on Theory of Computing (1991), pp. 134-144. A. Agrawal, P.N. Klein and R. Ravi,``Ordering Problems Approximated: Single-Processing Scheduling and Interval Graph Completion,'' Proceedings, 18th International Colloquium on Automata, Languages, and Programming (1991). A. Agrawal, P.N. Klein, R. Ravi, and S. Rao, ``Approximation through multicommodity flow,'' with Ajit Agrawal, Ramamurthy Ravi, and Satish Rao, Proceedings, 31th Annual Symposium on Foundations of Computer Science (1990), pp. 726-737. A. Agrawal, P.N. Klein and R. Ravi, ``How tough is the minimum-degree Steiner tree? A new approximate min-max equality (complete with algorithms),'' submitted to Symposium on Discrete Algorithms Bancilhon, F. Delobel, C., Kanellakis, P.C. (editors) ``Building an Object-Oriented Database System: The Story of O2'' Morgan-Kaufmann, to appear fall 1991. A. L. Buchsbaum, P. C. Kanellakis and J.S. Vitter, ``A Data Structure for Arc Insertion and Regular Path Finding'' Annals of Mathematics and Artificial Intelligence, special issue on Deductive Databases (edited by S. A. Naqvi and S. Tsur), 3 (2-4), March 1991. B. Le Charlier, K. Musumbu, and P. Van Hentenryck. "Efficient and Accurate Algorithms for the Abstract Interpretation of Prolog Programs." Eighth International Conference on Logic Programming (ICLP-91), Paris (France), June 1991 Le Charlier, B. and Van Hentenryck, P. "Experimental Evaluation of a Generic Abstract Interpretation Algorithm for Prolog," Technical Report, CS-91-55, Brown University, 1991 Y.-J. Chiang, A R. Tamassia, "Dynamization of the Trapezoid Method for Planar Point Location" Proc. ACM Symp. on Computational Geometry, 61-70, 1991. B. Codenotti, R. Tamassia, "A Network Flow Approach to the Reconfiguration of VLSI Arrays" IEEE Trans. on Computers, 40, 1, 118-121, 1991. R.F. Cohen, R. Tamassia, "Dynamic Expression Trees and their Applications" Proc. ACM-SIAM Symp. on Discrete Algorithms, 52--61, 1991. D. Brookshire Conner, Scott S. Snibbe, Kenneth P. Herndon, Daniel C. Robbins, Robert C. Zeleznik, Andries van Dam, "Extending Widgets in Three-Dimensional Geometry and Behavior", Submitted for publication in 1992 SIGGRAPH Symposium on Interactive 3D Graphics Cytron, R., Ferrante, J., Rosen, B.K., Wegman, M.N., Zadeck, F. K. "Efficiently Computing Static Single Assignment Form and the Control Dependence Graph", to appear in TOPLAS October 1991. Y. Deville and P. Van Hentenryck. "An Efficient Arc Consistency Algorithm for a Class of CSP Problems," International Joint Conference on Artificial Intelligence (IJCAI-91), Sidney, Australia, August 1991. G. Di Battista, A. Giammarco, G. Santucci, R. Tamassia, "The Architecture of Diagram Server" Proc. IEEE Workshop on Visual Languages (VL'90), 1990. Tinsley A. Galyean, John F. Hughes, "Sculpting: An Interactive Volumetric Modeling Technique", SIGGRAPH 1991 Proceedings, 25(4), p.267-274 M.T. Goodrich, R. Tamassia, "Dynamic Trees and Dynamic Point Location" Proc. 23th ACM Symp. on Theory of Computing, 523-533, 1991. C. L. Harkness, D. P. Lopresti, "Interval Methods for Modeling Uncertainty in RC Timing Analysis," to appear in IEEE Transactions on Computer-Aided Design. C. L. Harkness, D. P. Lopresti, "VLSI Placement Using Uncertain Costs," Proc. of the 1990 International Conference on Computer-Aided Design, November 1990, pp. 340-343. G. Hillebrand, P.C. Kanellakis, H. Mairson, M.Y. Vardi, ``Tools for Datalog Boundedness'' 10th ACM PODS Symposium on the Principles of Database Systems, Denver Colorado USA, pp. 1-12, May 1990. Philip M. Hubbard, Matthias M. Wloka, Robert C. Zeleznik, "UGA: A Unified Graphics Architecture", Brown University Technical Report CS-91-30, 1991 R. Hughey and D.P. Lopresti, "B-SYS: A 470-Processor Programmable Systolic Array," International Conference on Parallel Processing, pp 580-583, 1991. R. Hughey, and D.P. Lopresti, "A Software Approach to Fault Detection on Programmable Systolic Arrays," Proceedings of the Second IEEE Symposium on Parallel and Distributed Processing, IEEE Computer Society Press, Dec. 1990, pp. 523-526. P. G. Howard and J.S. Vitter, ``Analysis of Arithmetic Coding for Data Compression'' invited paper in Proceedings of the 1991 Data Compression Conference, April 1991, 3-12. P. G. Howard and J.S. Vitter, ``New Methods for Lossless Image Compression Using Arithmetic Coding'' Proceedings of the 1991 Data Compression Conference, April 1991, 257-266. P.C. Kanellakis, G. Kuper, P.Z. Revesz, ``Constraint Query Languages''. 9th ACM PODS Symposium on the Principles of Database Systems, Nashville Tennessee USA, pp. 299--314, March 1990. Full version was invited to JCSS special issue on 9th PODS and was completed in the fall of 1990, see Brown CS-90-31 November 1990. S. Kang, P. Klein, ``Approximating concurrent flow with uniform demands and capacities: an implementation,'' DIMACS Implementation Challenge Workshop: Network Flows and Matching, 1991. P. Klein, ``A parallel randomized approximation scheme for shortest paths,'' submitted to Journal of Algorithms, 1991. C. M. Kenyon and J.S. Vitter, ``Maximum Queue Size and Hashing with Lazy Deletion,'' Algorithmica, 6 (4), 1991, 597-619. C. M. Kenyon and J.S. Vitter, ``General Methods for the Analysis of the Maximum Size of Dynamic Data Structures,'' SIAM Journal on Computing, 20 (5), October 1991. P. Krishnan and J.S. Vitter, ``Optimal Prefetching via Data Compression,'' 32nd Annual IEEE Symposium on Foundations of Computer Science, San Juan, Puerto Rico, October 1991. D. P. Lopresti, Mark H. Nodine and J.S. Vitter, ``I/O Overhead and Parallel VLSI Architectures for Lattice Computations'' IEEE Transactions on Computers, to appear 1991. M. Lejter, S. Meyers, and S.P. Reiss, "Adding Semantic Information to C++ Development Environments," Proc of C++ at Work '90, September 1990. M. Lejter, S. Meyers, and S. P. Reiss, "Support for Maintaining Object-Oriented Programs," Proc. of the Conference on Software Maintenance, October 1991 (to appear). S. Meyers and S.P. Reiss, "A Semantic Basis for Multiple Views of Programs," Advance working papers of the 2nd Intl Workshop on Computer-Aided Soft. Eng., July 1988. S. Meyers, "Working with Object-Oriented Programs: The View from the Trenches is Not Always Pretty," Proc. of the Symposium on Object-Oriented Programming emphasizing Practical Applications, September 1990. S. Meyers and M. Lejter, "Automatic Detection of Programming Errors: Initial Thoughts on a Lint++," Proc of the 1991 USENIX C++ Conference, April 1991. S. Meyers and S.P. Reiss, "A System for Multiparadigm Development of Software Systems," Proc 6th Intl Workshop on Software Specification and Design, October 1991 (to appear). Gail Mitchell, Stanley B. Zdonik and Umeshwar Dayal, "Object-Oriented Query Optimization: What's the Problem?", Brown University, Department of Computer Science Tech. Report, CS-91-41, 1991. Gail Mitchell, Stanley B. Zdonik and Umeshwar Dayal, "An Architecture for Query Processing in Persistent Object Stores", to appear in Proceedings of the Hawaii International Conference on System Sciences, January, 1992. Marian H. Nodine, Sridhar Ramaswamy, and Stanley B. Zdonik "A Cooperative Transaction Model for Design Databases", in Transaction Models for Advanced Database Applications A. K. Elmagarmid, Ed., Morgan-Kaufmann, 1991 (to appear) Marian H. Nodine and Stanley B. Zdonik "Cooperative Transaction Hierarchies" to appear in VLDB Journal. Mark H. Nodine and J.S. Vitter, ``Large-Scale Sorting in Parallel Memories,'' Proceedings of the 3rd Annual ACM Symposium on Parallel Algorithms and Architectures, Hilton Head, SC, July 1991. F. P. Preparata, J.S. Vitter, and M. Yvinec, ``Output-Sensitive Generation of the Perspective View of Isothetic Parallepipeds,'' Algorithmica, to appear 1992. F. P. Preparata and J.S. Vitter, ``A Simplified Technique for Hidden-Line Elimination in Terrains,'' Technical Report No.CS-91-40 Dept. of Computer Science, Brown University June 1991. S. P. Reiss, " Connecting Tools Using Message Passing in the FIELD Program Development Environment," IEEE Software, July 1990 S. P. Reiss, "Interacting with the FIELD Environment," Software Practice and Experience, June 1990 S. P. Reiss, "On the Use of Annotations for Integrating the Source in a Program Development Environment," IFIP Intl Conf on Human Factors in Info Systems Analysis and Design, June 1990 P. Revesz, ``A Closed Form Evaluation for Datalog Queries with Integer Order Constraints''. 3rd International Conference on Database Theory, LNCS 470 pp. 187-201, Paris France, December 1990. Full version has been invited to TCS special issue on 3rd ICDT and was completed May 1991. J.E. Savage and M.G. Wloka, ``Parallelism in Graph-Partitioning,'' to appear in Journal of Parallel and Distributed Computing. J.E. Savage and M.G. Wloka, ``Parallel Graph-Embedding and the Mob Heuristic,'' submitted for publication. J.E. Savage and M.G. Wloka, ``Parallelizing SA for Graph-Embedding is Hard'' Proceedings IMACS vol.2 pp. 818-823, Dublin, July 91. J.E. Savage and M.G. Wloka, ``Parallel Graph-Embedding Heuristics'' Proceedings of the 5th SIAM Conference on Parallel Processing for Scientific Computing, 1991. J.E. Savage and M.G. Wloka, ``The Parallel Complexity of a Channel Routing Heuristic,'' submitted for publication. R. Tamassia, "An Incremental Reconstruction Method for Dynamic Planar Point Location" Information Processing Letters, 37, 79-83, 1991. R. Tamassia, "Drawing Algorithms for Planar st-Graphs" Australasian Journal of Combinatorics, 2, 217-235, 1990. R. Tamassia, I.G. Tollis, "Representations of Graphs on a Cylinder" SIAM J. on Discrete Mathematics, 4, 1, 139-149, 1991. R. Tamassia and J.S. Vitter, ``Parallel Transitive Closure and Point Location in Planar Structures'' , SIAM Journal on Computing, 20 (3), June 1991. P. Van Hentenryck and Y. Deville. "Operational Semantics of Constraint Logic Programming over Finite Domains," Third International Symposium on Programming Language Implementation and Logic Programming (PLILP-91}, Passau, Germany, August 1991. P. Van Hentenryck and Y. Deville. "The Cardinality Operator: A new Logical Connective and its Application to Constraint Logic Programming" In Eighth International Conference on Logic Programming (ICLP-91), Paris (France), June 1991. J.S. Vitter ``Efficient Memory Access in Large-Scale Computation,'' invited paper in Proceedings of the 1991 Symposium on Theoretical Aspects of Computer Science (STACS '91), Hamburg, West Germany, February 1991. Published in Lecture Notes in Computer Science, Springer-Verlag, Berlin. Wegman, M. N. and Zadeck, F. K., "Constant Propagation with Conditional Branches", TOPLAS, 13,2, 181-210, April 1991. P. Wegner ``Perspectives on Object-Oriented Design'' Brown Univ. Tech. Rep. TR 91-01. P. Wegner ``Trends in Epistemology'' Brown Univ. Tech. Rep. TR 91-31. Robert C. Zeleznik, D. Brookshire Conner, Andries van Dam, Matthias M. Wloka, Daniel G. Aliaga, Nathan T. Huang, Philip M. Hubbard, Brian Knep, Henry Kaufman, John F. Hughes, "An Object-Oriented Framework for the Integraion of Interactive Animation Techniques", SIGGRAPH 1991 Proceedings, 25(4), p.105-112. Principal Investigator(s) Name(s): John E. Savage PI Institution: Brown University PI Phone Number: (401) 863-7600 PI E-mail Address: darpa@cs.brown.edu Grant or Contract Title: Multiparadigm Design Environments High Performance Design Environments Grant or Contract Number: N00014-83-K-196 Reporting Period: 1 Oct 90 - 30 June 91 (MDE) 1 July 91 - 30 Sept 91 (HPDE) 4. Transitions and DoD interactions. Bill Scherlis cited the adoption of FIELD by Digital in a news release to DoD this spring. There has been a great deal of interaction between a number of co-PIs and various research groups (e.g., on compilers, constraint logic languages, databases) from the IBM T.J. Watson Labs. There has been interaction with Texas Instruments for object-oriented database language technology. There has been interaction with Cadre Technologies, and Andersen Consulting for graph drawing technology. Principal Investigator(s) Name(s): John E. Savage PI Institution: Brown University PI Phone Number: (401) 863-7600 PI E-mail Address: darpa@cs.brown.edu Grant or Contract Title: Multiparadigm Design Environments High Performance Design Environments Grant or Contract Number: N00014-83-K-196 Reporting Period: 1 Oct 90 - 30 June 91 (MDE) 1 July 91 - 30 Sept 91 (HPDE) 5. Software and hardware prototypes. In June of 1990 Brown licensed the FIELD software development environment to the Digital Equipment Corporation. FIELD, which was supported in part by DARPA, uses a selective broadcast tool communications interface to facilitate communication among existing and newly developed tools. The environment supports a variety of visual interfaces including graphical presentations of user data structures, call graphs, class hierarchies, and configuration dependencies. Digital licensed the software and converted it into a product called DEC/FUSE in about six months. The technology used in FIELD has also been adopted by HP in Softbench and by Sun in Tooltalk. It is also being considered by many other vendors as a basis for tool integration. In addition to FIELD a number of other prototypes have been developed in the last year: (The B-SYS (A 470-Processor Programmable Systolic Array) is an operational hardware prototype. The generic algorithm for abstract interpretation of Prolog has been fully implemented and tested on a sophisticated domain including types, sharing, aliasing, and modes.