Parents are shared parts of objects: Inheritance and encapsulation in SELF

The design of inheritance and encapsulation in SELF, an object-oriented language based on prototypes, results from understanding that inheritance allows parents to be shared parts of their children. The programmer resolves ambiguities arising from multiple inheritance by prioritizing an object's parents. Unifying unordered and ordered multiple inheritance supports differential programming of abstractions and methods, combination of unrelated abstractions, unequal combination of abstractions, and mixins. In SELF, a private slot may be accessed if the sending method is a shared part of the receiver, allowing privileged communication between related objects. Thus, classless SELF enjoys the benefits of class-based encapsulation.This work has been generously supported by National Science Foundation Presidential Young Investigator Grant #CCR-8657631, and by Sun Microsystems, IBM, Apple Computer, Cray Laboratories, Tandem Computers, NCR, Texas Instruments, and DEC.     

A Fuzzy Diagnostic Model and Its Application in Automotive Engineering Diagnosis

This paper describes a fuzzy diagnostic model that contains a fast fuzzy rule generation algorithm and a priority rule based inference engine. The fuzzy diagnostic model has been implemented in a fuzzy diagnostic system for the End-of-Line test at automobile assembly plants and the implemented system has been tested extensively and its performance is presented.     

Iterative type analysis and extended message splitting: Optimizing dynamically-typed object-oriented programs

Object-oriented languages have suffered from poor performance caused by frequent and slow dynamically-bound procedure calls. The best way to speed up a procedure call is to compile it out, but dynamic binding of object-oriented procedure calls without static receiver type information precludes inlining.Iterative type analysis andextended message splitting are new compilation techniques that extract much of the necessary type information and make it possible to hoist run-time type tests out of loops.Our system compiles code on-the-fly that is customized to the actual data types used by a running program. The compiler constructs a control flow graph annotated with type information by simultaneously performing type analysis and inlining. Extended message splitting preserves type information that would otherwise be lost by a control-flow merge by duplicating all the code between the merge and the place that uses the information. Iterative type analysis computes the types of variables used in a loop by repeatedly recompiling the loop until the computed types reach a fix-point. Together these two techniques enable our SELF compiler to split off a copy of an entire loop, optimized for the common-case types.By the time our SELF compiler generates code for the graph, it has eliminated many dynamically-dispatched procedure calls and type tests. The resulting machine code is twice as fast as that generated by the previous SELF compiler, four times faster than ParcPlace Systems Smalltalk-80, the fastest commercially available dynamically-typed object-oriented language implementation, and nearly half the speed of optimized C. Iterative type analysis and extended message splitting have cut the performance penalty for dynamically-typed object-oriented languages in half.This work has been generously supported by National Science Foundation Presidential Young Investigator Grant #CCR-8657631, and by Sun Microsystems, IBM, Apple Computer, Tandem Computers, NCR, Texas Instruments, the Powell Foundation, and DEC.This paper was originally published in theProceedings of the ACM SIGPLAN '90 Conference on Programming Language Design and Implementation (SIGPLAN Notices, 25, 6 (1990) 150–160).     

SELF: The power of simplicity

SELF is an object-oriented language for exploratory programming based on a small number of simple and concrete ideas: prototypes, slots, and behavior. Prototypes combine inheritance and instantiation to provide a framework that is simpler and more flexible than most object-oriented languages. Slots unite variables and procedures into a single construct. This permits the inheritance hierarchy to take over the function of lexical scoping in conventional languages. Finally, because SELF does not distinguish state from behavior, it narrows the gaps between ordinary objects, procedures, and closures. SELF's simplicity and expressiveness offer new insights into object-oriented computation. To thine own self be true. — William Shakespeare laggy     

Conjunction-type standard ML polymorphism

It has been long argued that the well known Milner type inference system implemented in the programming language Standard ML is inadequate [4]. The arguments were presented on the basis of intersection-type inference systems [3]. However no algorithm has been developed. The intersection-type inference systems are closed under-equality [1] and has been proved undecidable [7]. The paper presents a new type inference system using conjunction-types which extends the notion of intersection-types. The algorithm presented in the author's previous paper [9] is easily adoptable into the Standard ML. In this paper we shall discuss the features of the system and its semantic soundness. Unlike the intersection-type inference systems, the conjunction-type inference system is:

Inductive inference of logic programs based on algebraic semantics

In this paper we present a new inductive inference algorithm for a class of logic programs, calledlinear monadic logic programs. It has several unique features not found in Shapiro’s Model Inference System. It has been proved that a set of trees isrational if and only if it is computed by a linear monadic logic program, and that the rational set of trees is recognized by a tree automaton. Based on these facts, we can reduce the problem of inductive inference of linear monadic logic programs to the problem of inductive inference of tree automata. Further several efficient inference algorithms for finite automata have been developed. We extend them to an inference algorithm for tree automata and use it to get an efficient inductive inference algorithm for linear monadic logic programs. The correctness, time complexity and several comparisons of our algorithm with Model Inference System are shown.     

专家系统中的面向对象技术

面向对象程序的核心特征是封装、继承、多态、层次。面向对象的程序设计是一种结构化技术，它基于类型层次，匿名对象通过为它设计的普通协议进行相互通信。在专家系统中使用面向对象的程序设计方法有很多优点。本文介绍在推理机与知识表示的实现方案中面向对象方法的应用。     

An efficient implementation of SELF, a dynamically-typed object-oriented language based on prototypes

We have developed and implemented techniques that double the performance of dynamically-typed object-oriented languages. Our SELF implementation runs twice as fast as the fastest Smalltalk implementation, despite SELF's lack of classes and explicit variables.To compensate for the absence of classes, our system uses implementation-levelmaps to transparently group objects cloned from the same prototype, providing data type information and eliminating the apparent space overhead for prototype-based systems. To compensate for dynamic typing, user-defined control structures, and the lack of explicit variables, our system dynamically compilesmultiple versions of a source method, eachcustomized according to its receiver's map. Within each version the type of the receiver is fixed, and thus the compiler can statically bind andinline all messages sent toself.Message splitting andtype prediction extract and preserve even more static type information, allowing the compiler to inline many other messages. Inlining dramatically improves performance and eliminates the need to hard-wire low-level methods such as+, ==, andifTrue:.Despite inlining and other optimizations, our system still supports interactive programming environments. The system traverses internal dependency lists to invalidate all compiled methods affected by a programming change. The debugger reconstructs inlined stack frames from compiler-generated debugging information, making inlining invisible to the SELF programmer.This work has been generously supported by National Science Foundation Presidential Young Investigator Grant #CCR-8657631, and by IBM, Texas Instruments, NCR, Tandem Computers, Apple Computer, and Sun Microsystems.This paper was originally published inOOPSLA '89 Conference Proceedings (SIGPLAN Notices, 25, 10 (1989) 49–70).     

A stochastic EM algorithm for a semiparametric mixture model

Recently, there has been a considerable interest in finite mixture models with semi-/non-parametric component distributions. Identifiability of such model parameters is generally not obvious, and when it occurs, inference methods are rather specific to the mixture model under consideration. Hence, a generalization of the EM algorithm to semiparametric mixture models is proposed. The approach is methodological and can be applied to a wide class of semiparametric mixture models. The behavior of the proposed EM type estimators is studied numerically not only through several Monte-Carlo experiments but also through comparison with alternative methods existing in the literature. In addition to these numerical experiments, applications to real data are provided, showing that the estimation method behaves well, that it is fast and easy to be implemented.     

Types and trace effects for object orientation

Trace effects are statically generated program abstractions, that can be model checked for verification of assertions in a temporal program logic. In this paper we develop a type and effect analysis for obtaining trace effects of Object Oriented programs in Featherweight Java. We observe that the analysis is significantly complicated by the interaction of trace behavior with inheritance and other Object Oriented features, particularly overridden methods, dynamic dispatch, and downcasting. We propose an expressive type and effect inference algorithm combining polymorphism and subtyping/subeffecting constraints to obtain a flexible trace effect analysis in this setting, and show how these techniques are applicable to Object Oriented features. We also extend the basic language model with exceptions and stack-based event contexts, and show how trace effects scale to these extensions by structural transformations.     

FUZZY LOGIC-BASED TARGET CLASSIFICATION USING KINEMATIC DATA

The need for fast and accurate decisions in activities related to air surveillance and control has led to the development of systems to reduce operators' workload. In this context, a solution for aerial target classification is presented, using kinematic data (speed and acceleration) as input parameters. These can be estimated by a system composed of primary surveillance radar and a tracking algorithm. The implemented classifier is based on a fuzzy inference system that is capable of giving in real-time the membership degrees of a target to three defined classes, which is useful in the absence of data from secondary/IFF (Identification Friend or Foe) radars or imaging sensors.     

Pairwise data clustering by deterministic annealing

Partitioning a data set and extracting hidden structure from the data arises in different application areas of pattern recognition, speech and image processing. Pairwise data clustering is a combinatorial optimization method for data grouping which extracts hidden structure from proximity data. We describe a deterministic annealing approach to pairwise clustering which shares the robustness properties of maximum entropy inference. The resulting Gibbs probability distributions are estimated by mean-field approximation. A new structure-preserving algorithm to cluster dissimilarity data and to simultaneously embed these data in a Euclidian vector space is discussed which can be used for dimensionality reduction and data visualization. The suggested embedding algorithm which outperforms conventional approaches has been implemented to analyze dissimilarity data from protein analysis and from linguistics. The algorithm for pairwise data clustering is used to segment textured images     

Latent ranking analysis using pairwise comparisons in crowdsourcing platforms

Ranking items is an essential problem in recommendation systems. Since comparing two items is the simplest type of queries in order to measure the relevance of items, the problem of aggregating pairwise comparisons to obtain a global ranking has been widely studied. Furthermore, ranking with pairwise comparisons has recently received a lot of attention in crowdsourcing systems where binary comparative queries can be used effectively to make assessments faster for precise rankings. In order to learn a ranking based on a training set of queries and their labels obtained from annotators, machine learning algorithms are generally used to find the appropriate ranking model which describes the data set the best.In this paper, we propose a probabilistic model for learning multiple latent rankings by using pairwise comparisons. Our novel model can capture multiple hidden rankings underlying the pairwise comparisons. Based on the model, we develop an efficient inference algorithm to learn multiple latent rankings as well as an effective inference algorithm for active learning to update the model parameters in crowdsourcing systems whenever new pairwise comparisons are supplied. The performance study with synthetic and real-life data sets confirms the effectiveness of our model and inference algorithms.     

SELF: The power of simplicity

SELF is an object-oriented language for exploratory programming based on a small number of simple and concrete ideas: prototypes, slots, and behavior. Prototypes combine inheritance and instantiation to provide a framework that is simpler and more flexible than most object-oriented languages. Slots unite variables and procedures into a single construct. This permits the inheritance hierarchy to take over the function of lexical scoping in conventional languages. Finally, because SELF does not distinguish state from behavior, it narrows the gaps between ordinary objects, procedures, and closures. SELF's simplicity and expressiveness offer new insights into object-oriented computation.To thine own self be true. — William Shakespeare laggyThis work is partially supported by Xerox, and partially by National Science Foundation Presidential Young Investigator Grant #CCR-8657631, Sun Microsystems, the Powell Foundation, IBM, Apple Computer, DEC, NCR, Texas Instruments, and Cray Laboratories.This paper is a substantial revision of [20], originally published inOOPSLA '87 Conference Proceedings (SIGPLAN Notices, 22, 12 (1987) 227-241).     

A type system for logic programs

A theory for a type system for logic programs is developed which addressesthe question of well-typing, type inference, and compile-time and run-time type checking. A type is a recursively enumerable set of ground atoms, which is tuple-distributive. The association of a type to a program is intended to mean that only ground atoms that are elements of the type may be derived from the program. A declarative definition of well-typed programs is formulated, based on an intuitive approach related to the fixpoint semantics of logic programs. Whether a program is well typed is undecidable in general. We define a restricted class of types, called regular types, for which type checking is decidable. Regular unary logic programs are proposed as a specification language for regular types. An algorithm for type-checking a logic program with respect to a regular type definition is described, and its complexity is analyzed. Finally, the practicality of the type system is discussed, and some examples are shown. The type system has been implemented in FCP for FCP and is incorporated in the Logix system.     

Resource-Oriented Multicommodity Market Algorithms

In search for market equilibrium in multicommodity markets, price-oriented schemes are normally used. That is, a set of prices (one price for each commodity) is updated until supply meets demand for each commodity. In some cases such an approach is rather inefficient, and a resource-oriented scheme can be highly competitive. In a resource-oriented scheme the allocations are updated until the market equilibrium is found. It is well known that in a two-commodity market resource-oriented schemes are possible. In this article we show that resource-oriented algorithms can be used for the general multicommodity case as well, and present and analyze an algorithm. The algorithm has been implemented and some performance properties, for a specific example, are presented.     

HELIC-II: Legal reasoning system on the parallel inference machine

This paper presents HELIC-II, a legal reasoning system on the parallel inference machine. HELIC-II draws legal conclusions for a given case by referring to a statutory law (legal rules) and judicial precedents (old cases). This system consists of two inference engines. The rule-based engine draws legal consequences logically by using legal rules. The case-based engine generates legal concepts by referencing similar old cases. These engines complementally draw all possible conclusions, and output them in the form of inference trees. Users can use these trees as material to construct arguments in a legal suit. HELIC-II is implemented on the parallel inference machine, and it can draw conclusions quickly by parallel inference. As an example, a legal inference system for the Penal Code is introduced, and the effectiveness of the legal reasoning and parallel inference model is shown.     

GPS信号串行捕获算法研究

传统串行搜索算法在时域内对所有可能的频点和相位进行串行搜索,搜索的过程只需要加法和乘法运算,无论是在硬件还是软件中都容易实现,在GPS接收机设计中得到大量应用.但由于串行搜索算法在实际接收机中实现时,捕获过程需要大量的相乘、累加运算,需要较长的捕获时间.文中从降低相乘和累加运算个数入手,提出一种改进算法,使得捕获速度得到明显提高.利用MATLAB分别对传统的和改进的算法进行了算法仿真;根据信号捕获理论结合仿真实验结果,对两种算法进行了比较和分析,认为改进算法可以有效的应用于GPS信号捕获,而且提高了捕获的速度.该算法时于其它系统的伪随机码捕获也是适用的.     

Efficient Inference of Object Types

M. Abadi and L. Cardelli have recently investigated a calculus of objects (1994). The calculus supports a key feature of object-oriented languages: an object can be emulated by another object that has more refined methods. Abadi and Cardelli presented four first-order type systems for the calculus. The simplest one is based on finite types and no subtyping, and the most powerful one has both recursive types and subtyping. Open until now is the question of type inference, and in the presence of subtyping "the absence of minimum typings poses practical problems for type inference." In this paper, we give an O(n³) algorithm for each of the four type inference problems and we prove that all the problems are P-complete. We also indicate how to modify the algorithms to handle functions and records.     

Composition of Semantic Web services using Linear Logic theorem proving

This paper introduces a method for automatic composition of Semantic Web services using Linear Logic (LL) theorem proving. The method uses a Semantic Web service language (DAML-S) for external presentation of Web services, while, internally, the services are presented by extralogical axioms and proofs in LL. LL, as a resource conscious logic, enables us to capture the concurrent features of Web services formally (including parameters, states and non-functional attributes). We use a process calculus to present the process model of the composite service. The process calculus is attached to the LL inference rules in the style of type theory. Thus, the process model for a composite service can be generated directly from the complete proof. We introduce a set of subtyping rules that defines a valid dataflow for composite services. The subtyping rules that are used for semantic reasoning are presented with LL inference figures. We propose a system architecture where the DAML-S Translator, LL Theorem Prover and Semantic Reasoner can operate together. This architecture has been implemented in Java.