Fluent API is an object-oriented pattern for elegant APIs and embedded DSLs. A smart fluent API can enforce the API protocol or DSL syntax at compile time. Since fluent API implementations typically rely on overloading function names, they are hard to realize in functional programming languages. This work shows how functional fluent APIs can be implemented in the absence of name overloading, by relying on parametric polymorphism and Hindley-Milner type inference. The implementation supports fluent API protocols in the regular- and deterministic context-free language classes, and even beyond.

We present the first general and practical solution of the fluent API problem - an algorithm, that given a deterministic language (equivalently, LR(k), k >= 0 language) encodes it in an unbounded parametric polymorphism type system employing only a polynomial number of types. The theoretical result is accompanied by an actual tool Fling - a fluent API compiler-compiler in the venue of YACC, tailored for embedding DSLs in Java.

Care and great e.ort are often taken to dress program code of libraries, just as model implementations, in its most presentable form, which includes adherence to strict coding standards, careful selection of identifiers, avoiding unnecessary constructs, etc. However, a presentable dress is not a janitor's uniform and is often inferior to the more lax working outfit.The spartanizer is a tool that brings Java code into a canonical, short form. Trying to say the most with the fewest words. In contrast, the athenizer is a tool that expands the code, placing it in a more maintainable form, using plenty of auxiliary variables, many potential locations for breakpoints and for change.The tool reported on here allows developers to interactively use their joystick and its buttons for code navigation, and in particular for zooming-in into the code (athenizing) and zooming-out of it (spartanizing).

This paper raises the idea of giving end users the ability to modify and extend the control flow constructs (if, while, etc.) of the underlying programming language, just as they can modify and extend the library standard implementation of function printf and class String. Pluggable Controllers are means for modular design of control constructors, e.g., if, while, do, switch, and operators such as short circuit conjunction (&&) and the “?.” operator of the Swift programming language. We propose a modular, pluggable controllers based, design of a language. In this design there are control constructors which are core, augmented by a standard library of control constructors, which just like all standard libraries, is extensible and replaceable. The control constructors standard library can then follow a course of evolution that is less coupled with that of the main language, where a library release does not mandate new language release. At the same time, the library could be extended by individuals, corporate and communities to implement more or less idiosyncratic Nano-Patterns. We demonstrate the imposition of pluggable control constructors on Java by employing Lola-a Turing-complete and programming language independent code preprocessor.

The Spartanizer is an eclipse plugin featuring over one hundred and fifty refactoring techniques, all aimed at reducing various size complexity of the code, without changing its design, i.e., inheritance relations, modular structure, etc. Typical use case of the Spartanizer is in an automatic mode: refactoring operations are successively selected and applied by the tool, until the code is reshaped in spartan style (a frugal coding style minimizing the use of characters, variables, tokens, etc.). The Spartanizer demonstrates the potential of automatic refactoring: tens of thousands of transformations are applied in matter of seconds, chains of dependent applications of transformations with tens of operations in them, significant impact on code size, and extent reaching almost every line of code, even of professional libraries.

Summary Power laws can fit a variety of distributions coming from real data, so a systematic approach to the measurement of the accuracy of fitting algorithms is essential. We discuss the limits of the analysis of empirical fat‐tailed distributions, which can describe a variety of evolving systems, both natural and man‐made. An algorithm to fit fat‐tailed distributions is presented and tested against samplings of the power law, the Yule, the log‐normal, and Weibull distributions. We compute the parameters defining the shape of each distribution and test the results against simulations. We compare our method with another state‐of‐the‐art technique to estimate the parameters of empirical distributions. The accuracy of the estimations is discussed, and we conclude that our method based on a weighted iterated χ2 test performs better than the other. Our algorithm is general and can be applied to any numerical dataset.

This paper is a theoretical study of a practical problem: the automatic generation of Java Fluent APIs from their specification. We explain why the problem's core lies with the expressive power of Java generics. Our main result is that automatic generation is possible whenever the specification is an instance of the set of deterministic context-free languages, a set which contains most "practical" languages. Other contributions include a collection of techniques and idioms of the limited meta-programming possible with Java generics, and an empirical measurement demonstrating that the runtime of the "javac" compiler of Java may be exponential in the program's length, even for programs composed of a handful of lines and which do not rely on overly complex use of generics.

Software metrics are easy to define, but not so easy to justify. It is hard to prove that a metric is valid, i.e., that measured numerical values imply anything on the vaguely defined, yet crucial software properties such as complexity and maintainability. This paper employs statistical analysis and tests to check some plausible assumptions on the behavior of software and metrics measured for this software in retrospective on its versions evolution history. Among those are the reliability assumption implicit in the application of any code metric, and the assumption that the magnitude of change, i.e., increase or decrease of its size, in a software artifact is correlated with changes to its version number. Putting a suite of 36 metrics to the trial, we confirm most of the assumptions on a large repository of software artifacts. Surprisingly, we show that a substantial portion of the reliability of some metrics can be observed even in random changes to architecture. Another surprising result is that Boolean-valued metrics tend to flip their values more often in minor software version increments than in major increments.

This paper presents WHITEOAK: a JAVA extension that introduces structural type equivalence and subtyping into the language. We argue that structural subtyping addresses common software design problems, and promotes the development of loosely coupled modules without compromising type safety.

Object layout schemes used in C++ and other languages rely on (sometimes numerous) compiler generated fields. We describe a language-independent object layout scheme, which is space optimal, that is, objects are contiguous, and contain no compiler generated fields other than a single type identifier. As in C++ and other multiple inheritance languages such as CECIL and DYLAN, the new scheme sometimes requires extra levels of indirection to access some of the fields. Using a data set of 28 hierarchies, totaling almost 50,000 types, we show that this scheme improves field access efficiency over standard implementations, and competes favorably with (the non-space-optimal) highly optimized C++ specific implementations. The benchmark includes an analytical model for computing the frequency of indirections in a sequence of field access operations. Our layout scheme relies on whole-program analysis, which requires about 10 microseconds per type on a contemporary architecture (Pentium III, 900Mhz, 256MB machine), even in very large hierarchies. We also present a layout scheme for separate compilation using the user-annotation of virtual inheritance edge that is used in C++.

Most software applications use a relational database for data man-agement and storage. Interaction with such a database is often done by letting the program construct strings with valid SQL statements, which are then sent for execution to the database engine. The fact that these statements are only checked for correctness at runtime is a source for many potential problems such as type and syntax errors and vulnerability to injection attacks. The ARARAT system presented here offers a method for dealing with these predicaments, by coercing the host C++ compiler to do the necessary checks of the generated strings. A library of templates (and preprocessor directives) effectively extends C++ with a little language representing an augmented relational algebra formalism. Type checking of this language extension, as done by the template library, assures, at compile-time, the correctness of the generated SQL strings. All SQL statements constructed by the system are immune to injection attacks. Standard techniques (e.g., “expression templates”) for compile time representation of symbolic structures, are enhanced by our system to support a type system and a symbol table lookup of the symbolic structure. Our work may also open the way for embed-ding other domain specific languages in C++. 1.

We give the first linear time (randomised) algorithm for thefirst order isomorphism problem, that is, the isomorphism of non-recursive types involving product- and function-type constructors, under the axioms of commutativity and associativity of products, currying and distributivity of functions over products. This problem can also be thought of as the problem of formal equality-testing of multi-variate expressions involving only multiplications and exponentiation. Previous work gave a deterministicO(nlog2n) time andO(n) space algorithm for the problem (nbeing the input size). Our specific contribution includes two randomised algorithms for the problem: (i) anO(n) timeMonte Carloalgorithm (that is, with a small probability it may decide erroneously that the two types are isomorphic), and (ii) anO(nlogn) expected time andO(n) spaceLas Vegasalgorithm (that is, with a small probability it may execute long). The algorithms rely on a preprocessing stage, which computes the sequence of the firstnprimes inO(nlogn/log logn) time and space.

A fundamental problem in the implementation of object-oriented languages is that of a frugal implementation of dynamic dispatching, that is, a small footprint data structure that supports quick response to runtime dispatching queries of the following format: which method should be executed in response to a certain message sent to a given object. Previous theoretical algorithms for this problem tend to be impractical due to their conceptual complexity and large hidden constants. In contrast, successful practical heuristics lack theoretical support. The contribution of this article is in a novel type slicing technique, which results in two dispatching schemes: TS and CT d . We make the case for these schemes both practically and theoretically. The empirical findings on a corpus of 35 hierarchies totaling some 64 thousand types from eight different languages, demonstrate improvement over previous results in terms of the space required for the representation, and the time required for computing it. The theoretical analysis is with respect to ι, the best possible compression factor of the dispatching matrix. The results are expressed as a function of a parameter κ, which can be thought of as a metric of the complexity of the topology of a multiple inheritance hierarchy. In single inheritance hierarchies κ = 1, but although κ can be in the order of the size of the hierarchy, it is typically a small constant in actual use of inheritance; in our corpus, the median value of κ is 5, while its average is 6.4. The TS scheme generalizes the famous interval containment technique to multiple inheritance. TS achieves a compression factor of ι/κ, that is, our generalization comes with an increase to the space requirement by a small factor of κ. The pay is in the dispatching time, which is no longer constant as in a naive matrix implementation, but logarithmic in the number of different method implementations. In practice, dispatching uses one indirect branch and, on average, only 2.5 binary branches. The CT schemes are a sequence of algorithms CT 1 , CT 2 , CT 3 , …, where CT d uses d memory dereferencing operations during dispatch, and achieves a compression factor of 1/ d ι 1−1/ d in a single inheritance setting. A generalization of these algorithms to a multiple inheritance setting, increases the space by a factor of (2κ) 1−1/ d . This trade-off represents the first bounds on the compression ratio of constant-time dispatching algorithms. We also present an incremental variant of the CT d suited for languages such as Java.

We present an overview of JTL (the Java Tools Language, pronounced "Gee-tel"), a novel language for querying JAVA [8] programs. JTL was designed to serve the development of source code software tools for JAVA, and as a small language which to aid programming language extensions to JAVA. Applications include definition of pointcuts for aspect-oriented programming, fixing type constraints for generic programming, specification of encapsulation policies, definition of micro-patterns, etc. We argue that the JTL expression of each of these is systematic, concise, intuitive and general.JTL relies on a simply-typed relational database for program representation, rather than an abstract syntax tree. The underlying semantics of the language is restricted to queries formulated in First Order Predicate Logic augmented with transitive closure (FOPL).Special effort was taken to ensure terse, yet readable expression of logical conditions. The JTL pattern public abstract class, for example, matches all abstract classes which are publicly accessible, while class (public clone();) matches all classes in which method clone is public. To this end, JTL relies on a DATALOG-like syntax and semantics, enriched with quantifiers and pattern matching which all but entirely eliminate the need for recursive calls.JTL's query analyzer gives special attention to the fragility of the "closed world assumption" in examining JAVA software, and determines whether a query relies on such an assumption.The performance of the JTL interpreter is comparable to that of JQuery after it generated its database cache, and at least an order of magnitude faster when the cache has to be rebuilt.

Micro patterns are similar to design patterns, except that micro patterns are stand at a lower, closer to the implementation, level of abstraction. Micro patterns are also unique in that they are mechanically recognizable, since each such pattern can be expressed as a formal condition on the structure of a class.This paper presents a catalog of 27 micro-patterns defined on Java classes and interfaces. The catalog captures a wide spectrum of common programming practices, including a particular and (intentionally restricted) use of inheritance, immutability, data management and wrapping, restricted creation, and emulation of procedural-, modular-, and even functional- programming paradigms with object oriented constructs. Together, the patterns present a set of prototypes after which a large portion of all Java classes and interfaces are modeled. We provide empirical indication that this portion is as high as 75%.A statistical analysis of occurrences of micro patterns in a large software corpus, spanning some 70,000 Java classes drawn from a rich set of application domains, shows, with high confidence level that the use of these patterns is not random. These results indicate consciousness and discernible design decisions, which are sustained in the software evolution. With high confidence level, we can also show that the use of these patterns is tied to the specification, or the purpose, that the software realizes.The traceability, abundance and the statistical significance of micro pattern occurrence raise the hope of using the classification of software into these patterns for a more founded appreciation of its design and code quality.

The first-order isomorphism problem is to decide whether two non-recursive types using product- and function-type constructors are isomorphic under the axioms of commutative and associative products, and currying and distributivity of functions over products. We show that this problem can be solved in time of the best previous algorithm for this problem.

Given a type hierarchy, a subtyping test determines whether one type is a direct or indirect descendant of another type. Such tests are a frequent operation during the execution of object-oriented programs. The implementation challenge is in a space-efficient encoding of the type hierarchy that simultaneously permits efficient subtyping tests. We present a new scheme for encoding multiple- and single-inheritance hierarchies, which, in the standard benchmark hierarchies, reduces the footprint of all previously published schemes. Our scheme is called PQ-encoding (PQE) after PQ-trees , a data structure previously used in graph theory for finding the orderings that satisfy a collection of constraints. In particular, we show that in the traditional object layout model, the extra memory requirements for single-inheritance hierarchies is zero. In the PQE subtyping, tests are constant time, and use only two comparisons. The encoding creation time of PQE also compares favorably with previous results. It is less than 1 s on all standard benchmarks on a contemporary architecture, while the average time for processing a type is less than 1 ms. However, PQE is not an incremental algorithm. Other than PQ-trees, PQE employs several novel optimization techniques. These techniques are applicable also in improving the performance of other, previously published, encoding schemes.

A fundamental problem in the implementation of object-oriented languages is that of a frugal dispatching data structure, i.e., support for quick response to dispatching queries combined with compact representation of the type hierarchy and the method families. Previous theoretical algorithms tend to be impractical due to their complexity and large hidden constant. In contrast, successful practical heuristics, including Vitek and Horspool's compact dispatch tables (CT) [16] designed for dynamically typed languages, lack theoretical support. In subjecting CT to theoretical analysis, we are not only able to improve and generalize it, but also provide the first non-trivial bounds on the performance of such a heuristic.Let n,ml denote the total number of types, messages, and different method implementations, respectively. Then, the dispatching matrix, whose size isnm, can be compressed by a factor of at most ι ≡ (nm)/l. Our main variant to CT achieves a compression factor of ½ √ι. More generally, we describe a sequence of algorithms CT1, CT2, CT3,..., where CTd achieves compression by a factor of (at least) 1overdι1—1/d, while using d memory dereferencing operations during dispatch. This tradeoff represents the first bounds on the compression ratio of constant-time dispatching algorithms.A generalization of these algorithms to a multiple-inheritance setting, increases the space by a factor of κ1-1/d, where κ is a metric of the complexity of the topology of the inheritance hierarchy, which (as indicated by our measurements) is typically small. The most important generalization is an incremental variant of the CTd scheme for a single-inheritance setting. This variant uses at most twice the space of CTd, and its time of inserting a new type into the hierarchy is optimal. We therefore obtain algorithms for efficient management of dispatching in dynamic-typing, dynamic-loading languages, such as Smalltalk and even the Java invokeinterface instruction.

The first order isomorphism problem is to decide whether two nonrecursive types using product- and function-type constructors, are isomorphic under the axioms of commutative and associative products, and currying and distributivity of functions over products. We show that this problem can be solved in 2 is the input size. This result improves upon the space bounds of the best previous algorithm. We also describe an time algorithm for the linear isomorphism problem, which does not include the distributive axiom, whereby improving upon the time of the best previous algorithm for this problem.

With the adoption of UML by the OMG and industry as the linguae-francae of visual systems modelling, one begins to ponder what will come next in this field? This tutorial brings a vision for visual modelling beyond UML. We present and consolidate radical new notations, proposed in a series of research papers and with quickly increasing adoption by industry, for the specification of complex systems in an intuitive visual, yet precise manner. The recurring theme of these notations is the upgrading of familiar diagrams into a powerful visual language. Spider diagrams considerably extend Venn-diagrams to the specification of OO-systems. Most familiar OO-concepts are translated to set theoretical terms: class into set of objects, inheritance corresponding to subset, and even Harel's statecharts interpreted as the set of objects in that state. Constraint diagrams enhance the arrow notation to describe static system invariants which cannot be described by UML class-object diagram. Reasoning rules are developed for the notation and strong completeness results are given. Finally, 3D-diagrams show how the third dimension and VRML modelling can be used for a conceptual modelling of dynamic system behaviour. Much of the tutorial will be based on a case study developed in industry, illustrating how the new notations are combined with those of UML, including OCL.Highlights include:• A crash critical overview in UML, stressing its weaknesses and strengths,• A rich visual constraint language and an insight into subtle issues that arise when defining a visual language, for applying the popular design-by-contract using a visual formalism• A discussion of diagrammatic reasoning with the notation, including completeness results• A case study• A demonstration of a graphical editor for the constraint-diagrams language• A look to the future of visual modelling, including ideas about 3D modelling notations and visual modelling tools.

The dispatching problem can be solved very efficiently in the single-inheritance~(SI) setting. In this paper we show how to extend one such solution to the multiple-inheritance~(MI) setting. This generalization comes with an increase to the space requirement by a small factor of κ This factor can be thought of as a metric of the complexity of the topology of the inheritance hierarchy.On a data set of~35 hierarchies totaling some~64 thousand types, our dispatching data structure, based on a novel type slicing technique, exhibits very significant improvements over previous dispatching techniques, not only in terms of the time for creating the underlying data structure, but also in terms of total space used.The cost is in the dispatching time, which is no longer constant, but doubly logarithmic in the number of types. Conversely, by using a simple binary search, dispatching time is logarithmic in the number of different implementations. In practice dispatching uses one indirect branch and, on average, only~2.5 binary branches.Our results also have applications to the space-efficient implementation of the more general problem of dispatching multi-methods.A by-product of our type slicing technique is an incremental algorithm for constant-time subtyping tests with favorable memory requirements. (The incremental version of the subtyping problem is to maintain the subtyping data structure in presence of additions of types to the inheritance hierarchy.)

We propose an efficient and deterministic algorithm for computing the one-dimensional dilation and erosion (max and min) sliding window filters. For a p-element sliding window, our algorithm computes the 1D filter using 1.5 + o(1) comparisons per sample point. Our algorithm constitutes a deterministic improvement over the best previously known such algorithm, independently developed by van Herk (1992) and by Gil and Werman (1993) (the HGW algorithm). Also, the results presented in this paper constitute an improvement over the Gevorkian et al. (1997) (GAA) variant of the HGW algorithm. The improvement over the GAA variant is also in the computation model. The GAA algorithm makes the assumption that the input is independently and identically distributed (the i.i.d. assumption), whereas our main result is deterministic. We also deal with the problem of computing the dilation and erosion filters simultaneously, as required, e.g., for computing the unbiased morphological edge. In the case of i.i.d. inputs, we show that this simultaneous computation can be done more efficiently then separately computing each. We then turn to the opening filter, defined as the application of the min filter to the max filter and give an efficient algorithm for its computation. Specifically, this algorithm is only slightly slower than the computation of just the max filter. The improved algorithms are readily generalized to two dimensions (for a rectangular window), as well as to any higher finite dimension (for a hyperbox window), with the number of comparisons per window remaining constant. For the sake of concreteness, we also make a few comments on implementation considerations in a contemporary programming language.

Subtyping tests, i.e., determining whether one type is a subtype of another, are a frequent operation during the execution of objectoriented programs. The challenge is in encoding the hierarchy in a small space, while simultaneously making sure that subtyping tests have efficient implementation. We present a new scheme for encoding multiple and single inheritance hierarchies, which, in the standardized hierarchies, reduces the footprint of all previously published schemes. The scheme is called PQ-encoding after PQ-trees, a data structure previously used in graph theory for finding the orderings that satisfy a collection of constraints. In particular, we show that in the traditional object layout model, the extra memory requirements for single inheritance hierarchies is zero. In the PQ-encoding subtyping tests are constant time, and use only two comparisons. Other than PQ-trees, PQ-encoding uses several novel optimization techniques. These techniques are applicable also in improving the performance of other, previously published, encoding schemes.

We consider the type system formed by a finite set of primitive types such as integer, character, real, etc., and three type construction operators: (i) Cartesian product, (ii) disjoint sum, and (iii) recursive type definitions. Type equivalence is defined to obey the arithmetical rules: commutativity and associativity of product and sum and distributivity of product over sum. We offer a compact representation of the types in this system as multivariate algebraic functions. This type system admits two natural notions of subtyping: "multiplicative", which roughly corresponds to the notion of object-oriented subtyping, and "additive", which seems to be more appropriate in our context. Both kinds of subtyping can be efficiently computed if no recursive definitions are allowed. Our main result is that additive subtyping is undecidable in the general case. Perhaps surprisingly, this undecidability result is by reduction from Hilbert's Tenth Problem (HIO): the solution of Diophantine equations.

The tutorial is example driven and illustrates how the new notations are combined with those of UML, including OCL. Some of the examples are drawn from industrial contexts, in particular the telecomms sector. Highlights include:

Traditional implementations of multiple inheritance bring about not only an overhead in terms of run-time but also a significant increase in object space. For example, the number of compiler-generated fields in a certain object can be as large as quadratic in the number of its subobjects. The problem of efficient object layout is compounded by the need to support two different semantics of multiple inheritance: shared, in which a base class inherited along distinct paths occurs only once in the derived class, and repeated, in which this base has multiple distinct occurrences in the derived. In this theoretical and foundational paper, we introduce two new techniques to optimize memory layout for multiple inheritance. The main ideas behind these techniques are the inlining of virtual bases and bidirectional memory layout. Our techniques never increase time overhead, and usually even decrease it. We show that in some example hierarchies, more than ten-fold reduction in the space overhead can be achieved. We analyze the complexity of the algorithms to apply these techniques, and give theorems to estimate the efficacy of this application. For concreteness, techniques and examples are discussed in the context of C++.

Traditionally, diagrams used in software systems modelling have been two dimensional (2D). This is probably because graphical notations, such as those used in object-oriented and structured systems modelling, draw upon the topological graph metaphor, which, at its basic form, receives little benefit from three dimensional (3D) rendering. This paper presents a series of 3D graphical notations demonstrating effective use of the third dimension in modelling. This is done by e.g. connecting several graphs together, or in using the Z co-ordinate to show special kinds of edges. Each notation combines several familiar 2D diagrams, which can be reproduced from 2D projections of the 3D model. 3D models are useful even in the absence of a powerful graphical workstation: even 2D stereoscopic projections can expose more information than a plain planar diagram.

The paper is concerned with those properties of software that can be statically surmised from the source code. Many such properties have been extensively studied from the perspective of compiler construction technology. However, live variable analysis, alias analysis and the such are too low level to be of interest to the software engineer. The authors identify a family of statically checkable properties that should represent a higher level abstraction, and reach the detailed design level. Properties in this family which is defined by five precise distinguishing criteria are called traits. Some examples of traits include mutability, const correctness, ownership, and pure functions. In fact, in many ways, traits are non-standard types. They argue that traits should bring about similar benefits to these of static typing in terms of clarity, understandability, adherence to design decisions, and robustness. They further argue that traits can be used for better checking of substitutability in inheritance relationships. Having made the case for traits, they proceed to describing a taxonomy for classifying and understanding traits and show how it can be used to better understand previous work on this topic. The paper also discusses the abstract computational complexity of traits and compares previous research from that perspective.

A hash table is a representation of a set in a linear size data structure that supports constant-time membership queries. We show how to construct a hash table for any given set of n keys in O(lg lg n) parallel time with high probability, using n processors on a weak version of a concurrent-read concurrent-write parallel random access machine (crcw pram). Our algorithm uses a novel approach of hashing by "oblivious execution" based on probabilistic analysis. The algorithm is simple and has the following structure:Partition the input set into buckets by a random polynomial of constant degree. For t:= 1 to O(lg lg n) do Allocate M t memory blocks, each of size K t .Let each bucket select a block at random, and try to injectively map its keys into the block using a random linear function. Buckets that fail carry on to the next iteration. The crux of the algorithm is a careful a priori selection of the parameters M t and K t . The algorithm uses only O(lg lg n) random words and can be implemented in a work-efficient manner.

Despite vast interest in design patterns, the specification and application of patterns is generally assumed to rely on manual implementation. We describe a precise method of specifying how a design pattern is applied: by phrasing it as an algorithm in a meta-programming language. We present a prototype of a tool that supports the specification of design patterns and their realization in a given program. Our prototype allows automatic application of design patterns without obstructing the source code test from the programmer, who may edit it at will. We demonstrate pattern specification in meta-programming techniques and a sample outcome of its application.

The class of an object is not necessarily the only determiner of its runtime behaviour. Often it is necessary to have an object behave differently depending upon the other objects to which it is connected. However, as it currently stands, object-oriented programming provides no support for this concept, and little recognition of its role in common, practical programming situations. This paper investigates a new programming paradigm, environmental acquisition in the context of object aggregation, in which objects acquire behaviour from their current containers at runtime. The key idea is that the behaviour of a component may depend upon its enclosing composite(s). In particular, we propose a form of feature sharing in which an object "inherits" features from the classes of objects in its environment. By examining the declaration of classes, it is possible to determine which kinds of classes may contain a component, and which components must be contained in a given kind of composite. These relationships are the basis for language constructs that supports acquisition. We develop the theory of acquisition that includes topics such as the kinds of links along which acquisition may occur, and the behaviour of routine (methods) and attribute features under acquisition. The proposed model for acquisition as a hierarchical abstraction mechanism is a strongly typed model that allows static type checking of programs exploiting this mechanism. We compare it to several other mechanisms including inheritance and delegation, and show that it is significantly different than these.

We define a new simple and general model for hashing. The basic model together with several variants capture many natural (sequential and parallel) hashing algorithms and represent common hashing practice. Our main results exhibit tight tradeoffs between hash-table size and the number of applications of a hash function on a single key.

Two linear time (and hence asymptotically optimal) algorithms for computing the Euclidean distance transform of a two-dimensional binary image are presented. The algorithms are based on the construction and regular sampling of the Voronoi diagram whose sites consist of the unit (feature) pixels in the image. The first algorithm, which is of primarily theoretical interest, constructs the complete Voronoi diagram. The second, more practical, algorithm constructs the Voronoi diagram where it intersects the horizontal lines passing through the image pixel centers. Extensions to higher dimensional images and to other distance functions are also discussed.>

Fast algorithms for computing min, median, max, or any other order statistic filter transforms are described. The algorithms take constant time per pixel to compute min or max filters and polylog time per pixel, in the size of the filter, to compute the median filter. A logarithmic time per pixel lower bound for the computation of the median filter is shown.>

It is demonstrated that randomization is an extremely powerful tool for designing very fast and efficient parallel algorithms. Specifically, a running time of O(lg* n) (nearly-constant), with high probability, is achieved using n/lg* n (optimal speedup) processors for a wide range of fundamental problems. Also given is a constant time algorithm which, using n processors, approximates the sum of n positive numbers to within an error which is smaller than the sum by an order of magnitude. A variety of known and new techniques are used. New techniques, which are of independent interest, include estimation of the size of a set in constant time for several settings, and ways for deriving superfast optimal algorithms from superfast nonoptimal ones.>

Article Free Access Share on Not all keys can be hashed in constant time Authors: J. Gil Dept. of Gomp. Sc. Hebrew University, Jerusalem, 91904, Israel Dept. of Gomp. Sc. Hebrew University, Jerusalem, 91904, IsraelView Profile , F. Meyer auf der Heide Fachbereich 17, Mathematik/Informatik, Univesität. Gll Paderborn, D-4790 Paderborn, Fed.Rep. of Germany Fachbereich 17, Mathematik/Informatik, Univesität. Gll Paderborn, D-4790 Paderborn, Fed.Rep. of GermanyView Profile , A. Wigderson Dept. of Gomp. Sc. Hebrew University, Jerusalem, 91904, Israel Dept. of Gomp. Sc. Hebrew University, Jerusalem, 91904, IsraelView Profile Authors Info & Claims STOC '90: Proceedings of the twenty-second annual ACM symposium on Theory of ComputingApril 1990Pages 244–253https://doi.org/10.1145/100216.100247Published:01 April 1990Publication History 10citation330DownloadsMetricsTotal Citations10Total Downloads330Last 12 Months29Last 6 weeks5 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Reaching agreement in an asynchronous environment is essential to guarantee consistency in distributed data processing. All previous asynchronous protocols were either probabilistic or they assumed a fail-stop mode of failure. The deterministic protocol presented in this paper reaches a Strong Byzantine Agreement in a system of asynchronous processors; and therefore can sustain arbitrary faults. In our model, processors can be completely asynchronous, though the communication network has the property that a message being sent by a correctly operating processor to a set of processors will reach its destinations within a predetermined period Δ. Additional results presented in the paper prove that in the above model one cannot reach a consensus within a bounded time. A correctly operating processor should wait to receive messages from other processors before making a decision. This result holds also for Weak Byzantine Agreement, but not for nontrivial consensus. We present a trivial protocol to reach a nontrivial consensus in bounded time.