IRList Digest Friday, 14 Mar 1986 Volume 2 : Issue 14 Today's Topics: CSLI Seminars - Feature Structures in Unif. Grammars, Text Editor Based on Structural Regular Expressions COGSCI Seminars - Delegation & Inheritance - Theories of Natural Language Understanding - Parallel Inference Machine of ICOT - Word Neighborhoods in Mental Lexicon - Parallelism in Production Systems ---------------------------------------------------------------------- From: Emma Pease Subject: Calendar February 27, No. 5 [Extract - Ed] C S L I C A L E N D A R O F P U B L I C E V E N T S February 27, 1986 Stanford Vol. 1, No. 5 NEXT WEEK'S COLLOQUIUM Logical Specifications for Feature Structures in Unification Grammars William C. Rounds and Robert Kasper, University of Michigan In this paper we show how to use a simple modal logic to give a complete axiomatization of disjunctively specified feature or record structures commonly used in unification-based grammar formalisms in computational linguistics. The logic was originally developed as a logic to explain the semantics of concurrency, so this is a radically different application. We prove a normal form result based on the idea of Nerode equivalence from finite automata theory, and we show that the satisfi- ability problem for our logical formulas is NP-complete. This last result is a little surprising since our formulas do not contain negation. Finally, we show how the unification problem for term-rewriting systems can be expressed as the satisfiability problem for our formulas. PIXELS AND PREDICATES Sam: A Text Editor Based on Structural Regular Expressions Rob Pike, Bell Labs 1:00 pm, Monday, March 3, CSLI trailers This talk will assume some familiarity with the `cut and paste' model of editing supported by the mouse interface, and will focus on the command language. `Sam' has two interfaces: a mouse-based language very similar to `jim'(9.1), and a command language reminiscent of `ed'(1). `Sam' is based on `structural regular expressions': the application of regular expressions to describe the form of a file. Conventional Unix tools think of their input as arrays of lines. The new notation makes it easy to make changes to files regardless of their structure, to define structure within the elements (e.g., the pieces of a line), and to change the apparent shape of a file according to the change being made. The use of structural regular expressions makes it possible for the mouse and command languages to operate on the same objects, so that editing commands from the mouse and keyboard may be mixed comfortably and effectively. Of course, either mouse or keyboard may be used exclusively of the other, so `sam' can be used as if it were `jim', `ed' or even `sed'---a `stream' version of `sam' is forthcoming. ------------------------------ From: Peter de Jong Date: Fri, 28 Feb 1986 12:00 EST Subject: Cognitive Science Calendar [Extract - Ed] Thursday , March 6 4:00pm Room: NE43- 8th floor Playroom The Artificial Intelligence Lab Revolving Seminar Series Delegation And Inheritance: Two Mechanisms for Sharing Knowledge in Object-Oriented Systems Henry Lieberman AI Lab, MIT When a group of objects in an object oriented programming system shares some common behavior, how can we avoid re-programming behavior in every object that needs it? I will explore the consequences of two mechanisms for sharing knowledge, Inheritance and Delegation, for expressiveness and performance of object oriented languages. Using Inheritance, behavior common to a group of objects is encoded in a Class object, which contains procedures for responding to messages, and the names of variables that the procedure may access. Each class may create a set of Instances, which share the procedures of the class, but may have their own private values for the variables. Subclasses may extend classes by adding additional procedures and variables. Another way of sharing behavior is Delegation, which views each object as a prototype capable of creating new objects by copying or reference, removing the distinction between classes and instances. General and specialized objects communicate using message passing rather than a "hard wired" mechanism. Communication patterns can be determined at message reception time rather than at compile time or object creation time. There is a time/space tradeoff between inheritance and delegation, delegation permitting smaller objects at the cost of increased message traffic. ------------------------------ From: Peter de Jong Date: Tue, 25 Feb 1986 12:54 EST Subject: Cognitive Science Calendar [Extract - Ed] Tuesday, 25, February 4:00pm Room: Lecture Hall 101, Aiken Computation Laboratory, 33 Oxford St, Cambridge Harvard University Center for Research in Computing Technology "On Some Inadequate Theories of Natural Language Understanding" Dr. Mitch Marcus ------------------------------ From: Peter de Jong Date: Mon, 10 Mar 1986 12:28 EST Subject: Cognitive Science Calendar [Extract - Ed] Friday, 14 March 11:00am Room: NE43-512a Evaluation of the PSI Micro-Interpreter and Discussion of PIM, the Parallel Inference Machine of ICOT Katsushi Nakajima and Akira Matsumoto Institute for New Generation Computing Technology (ICOT) and Mitsubishi Electric Company This talk describes the evaluation of the microprogrammed interpreter of the personal sequential inference machine (PSI) developed in the Japanese Fifth Generation Computer Project. The execution speed of PSI is almost the same as that of DEC-10 Prolog on DEC 2060. Particularly PSI is a little slower with some simple benchmark programs and a little faster with the programs in which a lot of backtrackings may occur. We evaluate some application programs in PSI's machine language, KLO. In evaluating these programs, we consider some dynamic characteristics such as "Backtrack Ratio," "Predicate Call Ratio," and "Execution Time Ratio." In particular, we show that the call ratio of user-defined predicates is 7% to 30%, lower than that of built-in predicates, although the "Execution Time Ratio" for these predicates is very high (46% to 77%). We also present an alternate execution method, in which clauses are compiled to specially designed machine instructions. This alternative method is implemented experimentally on PSI. This method speeds up execution by a factor of two, though the load for compilation is somewhat heavy. The current status and future plans of PIM, the Parallel Inference Machine, will also be discussed. Host: Prof. Arvind ------------------------------ From: Peter de Jong Date: Tue, 11 Mar 1986 15:04 EST Subject: Cognitive Science Calendar [Extract - Ed] Thursday, 13 March 12:00pm Room: E25-401 VISION LUNCH "Neighborhoods of Words in the Mental Lexicon" Dr. David Pisoni Indiana University ------------------------------ From: Peter de Jong Date: Tue, 11 Mar 1986 09:47 EST Subject: Cognitive Science Calendar Friday, 14 March 3:30pm (refreshments 3:15) Room: NE43-512a "Parallelism in Production Systems" Anoop Gupta Carnegie-Mellon University Production systems (or rule-based systems) are widely used in Artificial Intelligence for modeling intelligent behavior and building expert systems. Most production system programs, however, are extremely computation intensive and run quite slowly. The slow speed of execution has prohibited the use of production systems in domains requiring high performance and real-time response. The talk will elaborate on the role of parallelism in the high-speed execution of production systems. On the surface, production system programs appear to be capable of using large amounts f parallelism -- it is possible to perform match for each production in a program in parallel. Our research shows that in practice, however, the speed-up obtainable from parallelism is quite limited, around 10-fold as compared to initial expectations of 100-fold to 1000-fold. The main reasons for the limited speed-up are: (1) there are only a small number of productions that are affected (require significant processing) as a result of a change to working memory and (2) there is a large variation in the processing not controlled by the implementor of the production system interpreter (it is governed mainly by the author of the program and the nature of the problem), the solution to the problem of limited speed-up is to somehow decrease the variation in the processing cost of affected productions. We propose a fine grain to reduce this variation. We further suggest that to exploit the fine-grained parallelism, a shared-memory multiprocessor with 32-64 high performance processors should be used. For scheduling the fine-grained tasks consisting of about 5-100 instructions, a hardware task scheduler is proposed. The results presented in the talk are based on simulations done for a large set of production systems exploiting different sources of parallelism. The simulation results show that using the suggested multiprocessor architecture (with individual processors performing at 2 MIPS), it is possible to obtain execution speeds of 5000-27000 working memory element changes per second. This corresponds to a speed-up of 5-fold to 27-fold over the best known sequential implementation using a 2 MIPS processor. This performance is also higher than that obtained by other proposed parallel implementations of production systems. Host: Prof. Gerald Jay Sussman