40264513
Avoiding Unnecessary Updates
Graph reduction underlies most implementations of lazy functional languages, allowing separate computations to share results when sub­ terms are evaluated. Once a term is evaluated, the node of the graph representing the computation is updated with the value of the term. How­ ever, in many cases, no other computation requires this value, so the up­ date is unnecessary. In this paper we take some steps towards an analysis for determining when these updates may be omitted.
8161135
Binding-Time Analysis for Polymorphic Types
Offline partial evaluators specialise programs with annotations which distinguish specialisation-time (or static) computations from run-time ones. These annotations are generated by a binding-time analyser, via type inference in a suitable type-system. Henglein and Mossin developed a type system which allows polymorphism in binding-times, so that the same code can be specialised with different computations being static at different uses. We extend their work to permit polymorphism in types as well. This is particularly important for separately compiled libraries.Following Henglein and Mossin, binding-times are passed as parameters during specialisation, but types are not. Instead, we pass coercion functions when necessary, which makes specialisation less "interpretive" than it would otherwise be. We keep track of the coercions needed by assigning qualified types to polymorphic functions.We also consider hand-annotations to provide limited user control over the binding-time analysis, which our prototype implementation showed to be necessary.
218895568
How to give a good research talk
Giving a good research talk is not easy. We try to identify some things which we have found helpful, in the hope that they may be useful to you.
27745403
Type Specialisation for the lambda-Calculus; or, A New Paradigm for Partial Evaluation Based on Type Inference
14958709
Making choices lazily
We present a natural semantics that models the untyped, normal order A-calculus plus McCarthy’s amb in the context of call-by-need parameter passing. This results in a singular semantics for amb. Previous work on singular choice has concentrated on erratic choice, a less interesting nondeterministic choice operator, and only in relation to callby-value parameter passing, or call-by-name restricted to deterministic terms. The natural semantics contains rules for both convergent and divergent behaviour, allowing it to distinguish programs that differ only in their divergent behaviour. As a result, it is more discriminating than current domain-theoretic models. This, and the fact that it models singular amb, makes the natural semantics suitable for reasoning about lazy, functional languages containing McCarthy’s amb.
14804186
Proving the correctness of reactive systems using sized types
We have designed and implemented a type-based analysis for proving some basic properties of reactive systems. The analysis manipulates rich type expressions that contain information about the sizes of recursively defined data structures. Sized types are useful for detecting deadlocks, nontermination, and other errors in embedded programs. To establish the soundness of the analysis we have developed an appropriate semantic model of sized types.
27941486
Distributed probabilistic diagnosis of MCMs on large area substrates
This paper addresses the issue of testing MCMs on large-area substrates. The cost of testing each MCM may be as high as 40% of the total manufacturing cost. It is critical that the test process be parallelized in order that multiple MCMs may be tested for the cost of testing one MCM. With this objective in mind, we propose a distributed probabilistic diagnosis algorithm for MCMs on large-area substrates. Our algorithm performs better than the existing diagnosis algorithms and can correctly identify almost all MCMs even when the yield is very low (35%). Further it provides upto an order of magnitude reduction in test application time as opposed to serial MCM probe test.
2210
Length-Based Attacks for Certain Group Based Encryption Rewriting Systems
In this note, we describe a probabilistic attack on public key cryptosystems based on the word/conjugacy problems for finitely presented groups of the type proposed recently by Anshel, Anshel and Goldfeld. In such a scheme, one makes use of the property that in the given group the word problem has a polynomial time solution, while the conjugacy problem has no known polynomial solution. An example is the braid group from topology in which the word problem is solvable in polynomial time while the only known solutions to the conjugacy problem are exponential. The attack in this paper is based on having a canonical representative of each string relative to which a length function may be computed. Hence the term length attack. Such canonical representatives are known to exist for the braid group.
197963
An interactive 3D toolkit for constructing 3D widgets
Today’s user interfaces for most 3D graphics applications still depend heavily on 2D GUIs and keyboard input. There have been several recent attempts both to extend these user interfaces into 3D and to describe intermediary 3D widgets that control application objects [3; 4; 5; 7; 13; 15]. Even though this style of interaction is a straightforward extension of interaction through intermediary 2D widgets such as dials or sliders, we know of no efforts to develop interactive 3D toolkits akin to UIMX or Garnet [11]. The Brown Graphics Group has had considerable experience using its Unified Graphics Architecture (UGA) system [16] to script 3D widgets such as deformation racks [14], interactive shadows [9], parameterized models, and other constrained 3D geometries. Using this experience, we have developed an interactive toolkit to facilitate the visual programming of the geometry and behavior of such interactive models. The toolkit provides both a core set of 3D widget primitives for constructing interactive behaviors based on constrained affine transformations, and an interactive 3D interface for combining these primitives into more complex widgets. This video paper describes the fundamental concepts of the toolkit and its core set of primitives. In particular, we describe (i) the conceptual structure of the primitives, (ii) the criteria used to select a particular primitive widget set that would be expressive enough to let us construct a wide range of interactive 3D objects, and (iii) the constraint relationships among the primitives.
247123
Defocus video matting
Video matting is the process of pulling a high-quality alpha matte and foreground from a video sequence. Current techniques require either a known background (e.g., a blue screen) or extensive user interaction (e.g., to specify known foreground and background elements). The matting problem is generally under-constrained, since not enough information has been collected at capture time. We propose a novel, fully autonomous method for pulling a matte using multiple synchronized video streams that share a point of view but differ in their plane of focus. The solution is obtained by directly minimizing the error in filter-based image formation equations, which are over-constrained by our rich data stream. Our system solves the fully dynamic video matting problem without user assistance: both the foreground and background may be high frequency and have dynamic content, the foreground may resemble the background, and the scene is lit by natural (as opposed to polarized or collimated) illumination.
53245851
A suggestive interface for 3D drawing
This paper introduces a new type of interface for 3D drawings that improves the usability of gestural interfaces and augments typical command-based modeling systems. In our suggestive interface, the user gives hints about a desired operation to the system by highlighting related geometric components in the scene. The system then infers possible operations based on the hints and presents the results of these operations as small thumbnails. The user completes the editing operation simply by clicking on the desired thumbnail. The hinting mechanism lets the user specify geometric relations among graphical components in the scene, and the multiple thumbnail suggestions make it possible to define many operations with relatively few distinct hint patterns. The suggestive interface system is implemented as a set of suggestion engines working in parallel, and is easily extended by adding customized engines. Our prototype 3D drawing system, Chateau, shows that a suggestive interface can effectively support construction of various 3D drawings.