My research activities pertain to "Informatics" and in particular "Interactive Graphics" i.e. dynamic graphics on a 2D screen that a user can interact with by means of input devices such as a mouse or a multitouch surface. I have conducted research on Interactive Graphics along three themes: interactive graphics development (how should developers design the architecture of the code corresponding to graphical interactions?), interactive graphic design (what graphical interactions should User Experience (UX) specialists use in their system?) and interactive graphics design process (how should UX specialists design? Which method should they apply?) I invented the MDPC architecture that relies on Picking views and Inverse transforms. This improves the modularity of programs and improves the usability of the specification and the implementation of interactive graphics thanks to the simplification of description. In order to improve the performance of rich-graphic software using this architecture, I explored the concepts of graphical compilers and led a PhD thesis on the topic. The thesis explored the approach and contributed both in terms of description simplification and of software engineering facilitation. Finally, I have applied the simplification of description principles to the problem of shape covering avoidance by relying on new efficient hardware support for parallelized and memory-based algorithms. Together with my colleagues, we have explored the design and assessment of expanding targets, animation and sound, interaction with numerous tangled trajectories, multi-user interaction and tangible interaction. I have identified and defined Structural Interaction, a new interaction paradigm that follows the steps of the direct and instrumental interaction paradigms. I directed a PhD thesis on this topic and together with my student we designed and assessed interaction techniques for structural interaction. I was involved in the design of the "Technology Probes" concept i.e. runnable prototypes to feed the design process. Together with colleagues, I designed VideoProbe, one such Technology Probe. I became interested in more conceptual tools targeted at graphical representation. I led two PhD theses on the topic and explored the characterization of visualization, how to design representations with visual variables or ecological perception and how to design visual interfaces to improve visual scanning. I discovered that those conceptual tools could be applied to programming languages and showed how the representation of code, be it textual or "visual" undergoes visual perception phenomena. This has led me to consider our discipline as the "Science of Controlled Transformations". The fifth chapter is an attempt at providing this new account of "Informatics" based on what users, programmers and researchers actually do with interactive systems. I also describe how my work can be considered as contributing to the science of controlled transformations.

Thesis (Ph.D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1982. / MICROFICHE COPY AVAILABLE IN ARCHIVES AND ENGINEERING. / Bibliography: leaves 756-761. / by Brian Cantwell Smith. / Ph.D.

Context-free grammars are the most suitable and most widely used method for describing the syntax of programming languages. They can be used to generate parsers, which transform a piece of source code into a tree-shaped representation of the code's syntactic structure. These parse trees can then be used for further processing or analysis of the source text. In this sense, grammars form the basis of many engineering and reverse engineering applications, like compilers, interpreters and tools for software analysis and transformation. Unfortunately, context-free grammars have the undesirable property that they can be ambiguous, which can seriously hamper their applicability. A grammar is ambiguous if at least one sentence in its language has more than one valid parse tree. Since the parse tree of a sentence is often used to infer its semantics, an ambiguous sentence can have multiple meanings. For programming languages this is almost always unintended. Ambiguity can therefore be seen as a grammar bug. A specific category of context-free grammars that is particularly sensitive to ambiguity are character-level grammars, which are used to generate scannerless parsers. Unlike traditional token-based grammars, character-level grammars include the full lexical definition of their language. This has the advantage that a language can be specified in a single formalism, and that no separate lexer or scanner phase is necessary in the parser. However, the absence of a scanner does require some additional lexical disambiguation. Character-level grammars can therefore be annotated with special disambiguation declarations to specify which parse trees to discard in case of ambiguity. Unfortunately, it is very hard to determine whether all ambiguities have been covered. The task of searching for ambiguities in a grammar is very complex and time consuming, and is therefore best automated. Since the invention of context-free grammars, several ambiguity detection methods have been developed to this end. However, the ambiguity problem for context-free grammars is undecidable in general, so the perfect detection method cannot exist. This implies a trade-off between accuracy and termination. Methods that apply exhaustive searching are able to correctly find all ambiguities, but they might never terminate. On the other hand, approximative search techniques do always produce an ambiguity report, but these might contain false positives or false negatives. Nevertheless, the fact that every method has flaws does not mean that ambiguity detection cannot be useful in practice. This thesis investigates ambiguity detection with the aim of checking grammars for programming languages. The challenge is to improve upon the state-of-the-art, by finding accurate enough methods that scale to realistic grammars. First we evaluate existing methods with a set of criteria for practical usability. Then we present various improvements to ambiguity detection in the areas of accuracy, performance and report quality. The main contributions of this thesis are two novel techniques. The first is an ambi- guity detection method that applies both exhaustive and approximative searching, called AMBIDEXTER. The key ingredient of AMBIDEXTER is a grammar filtering technique that can remove harmless production rules from a grammar. A production rule is harmless if it does not contribute to any ambiguity in the grammar. Any found harmless rules can therefore safely be removed. This results in a smaller grammar that still contains the same ambiguities as the original one. However, it can now be searched with exhaustive techniques in less time. The grammar filtering technique is formally proven correct, and experimentally validated. A prototype implementation is applied to a series of programming language grammars, and the performance of exhaustive detection methods are measured before and after filtering. The results show that a small investment in filtering time can substantially reduce the run-time of exhaustive searching, sometimes with several orders of magnitude. After this evaluation on token-based grammars, the grammar filtering technique is extended for use with character-level grammars. The extensions deal with the increased complexity of these grammars, as well as their disambiguation declarations. This enables the detection of productions that are harmless due to disambiguation. The extentions are experimentally validated on another set of programming language grammars from practice, with similar results as before. Measurements show that, even though character-level grammars are more expensive to filter, the investment is still very worthwhile. Exhaustive search times were again reduced substantially. The second main contribution of this thesis is DR. AMBIGUITY, an expert system to help grammar developers to understand and solve found ambiguities. If applied to an ambiguous sentence, DR. AMBIGUITY analyzes the causes of the ambiguity and proposes a number of applicable solutions. A prototype implementation is presented and evaluated with a mature Java grammar. After removing disambiguation declarations from the grammar we analyze sentences that have become ambiguous by this removal. The results show that in all cases the removed filter is proposed by DR. AMBIGUITY as a possible cure for the ambiguity. Concluding, this thesis improves ambiguity detection with two novel methods. The first is the ambiguity detection method AMBIDEXTER that applies grammar filtering to substantially speed up exhaustive searching. The second is the expert system DR. AMBIGUITY that automatically analyzes found ambiguities and proposes applicable cures. The results obtained with both methods show that automatic ambiguity detection is now ready for realistic programming language grammars.

Constructs for functional and logic programming can be smoothly integrated into an existing object-oriented language. We demonstrate this in the context of C++ (a statically-typed object-oriented language with effects and parametric polymorphism) via two libraries: FC++ and LC++. FC++ is a library for functional programming in C++; FC++ supports higher-order polymorphic functions, lazy lists, and a small lambda language; it also contains a large library of useful functions, datatypes, combinators, and monads. LC++ is a library for logic programming in C++; LC++ provides the same general functionality as Prolog, including the ability to return query results lazily (one at a time). Both libraries are embedded in C++ so that they share C++'s static type system, and the library interfaces provide straightforward ways for code from within one paradigm to ``call out' to another. Our work describes the techniques used to implement these libraries in C++ and shows that the resulting multiparadigm language has useful applications in real-world domains. We also describe how many of the implementation techniques can be generalized from C++ and applied to other programming languages to yield similar results.

Experimental game theory is the use of game theoretic abstractions—games, players, and strategies—in experiments and simulations. It is often used in cases where traditional, analytical game theory fails or is difficult to apply. This thesis collects three previously published papers that provide domain-specific language (DSL) support for defining and executing these experiments, and for explaining their results. Despite the widespread use of software in this field, there is a distinct lack of tool support for common tasks like modeling games and running simulations. Instead, most experiments are created from scratch in general-purpose programming languages. We have addressed this problem with Hagl, a DSL embedded in Haskell that allows the concise, declarative definition of games, strategies, and executable experiments. Hagl raises the level of abstraction for experimental game theory, reducing the effort to conduct experiments and freeing experimenters to focus on hard problems in their domain instead of low-level implementation details. While analytical game theory is most often used as a prescriptive tool, a way to analyze a situation and determine the best course of action, experimental game theory is often applied descriptively to explain why agents interact and behave in a certain way. Often these interactions are complex and surprising. To support this explanatory role, we have designed visual DSL for explaining the interaction of strategies for iterated games. This language is used as a vehicle to introduce the notational quality of traceability and the new paradigm of explanation-oriented programming. / Graduation date: 2012

Design synthesis is a fundamental engineering task that involves the creation of structure from a desired functional specification; it involves both creating a system topology as well as sizing the system's components. Although the use of computer tools is common throughout the design process, design synthesis is often a task left to the designer. At the synthesis stage of the design process, designers have an extensive choice of design alternatives that need to be considered and evaluated. Designers can benefit from computational synthesis methods in the creative phase of the design process. Recent increases in computational power allow automated synthesis methods for rapidly generating a large number of design solutions. Combining an automated synthesis method with an evaluation framework allows for a more thorough exploration of the design space as well as for a reduction of the time and cost needed to design a system. To facilitate computational synthesis, knowledge about feasible system configurations must be captured. Since it is difficult to capture such synthesis knowledge about any possible system, a design domain must be chosen. In this thesis, the design domain is hydraulic systems. In this thesis, Model-Driven Software Development concepts are leveraged to create a framework to automate the synthesis of hydraulic systems will be presented and demonstrated. This includes the presentation of a domain specific language to describe the function and structure of hydraulic systems as well as a framework for synthesizing hydraulic systems using graph grammars to generate system topologies. Also, a method using graph grammars for generating analysis models from the described structural system representations is presented. This approach fits in the context of Model-Based Systems Engineering where a variety of formal models are used to represent knowledge about a system. It uses the Systems Modeling Language developed by The Object Management Group (OMG SysML™) as a unifying language for model definition.

Thesis (Ph. D.)--University of Alabama at Birmingham, 2007. / Additional advisors: Jeff Gray, Marjan Mernik, Alan Sprague, Murat Tanik. Description based on contents viewed June 25, 2007; title from title screen. Includes bibliographical references (p. 132-138).

No description available.

Modern data intensive applications, such as multimedia systems require the ability to store and manipulate complex data. The classical Database Management Systems (DBMS), such as relational databases, cannot support these types of applications efficiently. This dissertation presents the salient features of Object Database Management Systems (ODBMS) and Persistent Programming Languages (PPL), which have been developed to address the data management needs of these difficult applications. An 'impedance mismatch' problem occurs in the traditional DBMS because the data and computational aspects of the application are implemented using two different systems, that of query and programming language. PPL's provide facilities to cater for both persistent and transient data within the same language, hence avoiding the impedance mismatch problem. This dissertation presents a method of implementing a PPL by extending the language C++ with pre-compiled classes. The classes are first developed and then used to implement object persistence in two simple applications. / Computing / M. Sc. (Information Systems)

Cette thèse traite de la conception et implémentationd’un langage de programmation pour les systèmes detraitement de flux en temps réel, comme l’encodagevidéo. Le modèle des réseaux de Kahn est bien adaptéà ce domaine et y est couramment utilisé. Dans cemodèle, un programme consiste en un ensemble deprocessus parallèles communicant à travers des filesmono-producteur, mono-consommateur. La force dumodèle réside en son déterminisme.Les langages synchrones fonctionnels comme Lustresont dédiés aux systèmes embarqués critiques. Un programmeLustre définit un réseau de Kahn synchronequi peut être exécuté avec des files bornées et sans blocage.Cette propriété est garantie par un système detypes dédié, le calcul d’horloge, qui établit une échellede temps globale à un programme. Cette échelle detemps globale est utilisée pour définir les horloges, sé-quences booléennes indiquant pour chaque file, et àchaque pas de temps, si un processus produit ou consommeune donnée. Cette information sert non seulementà assurer la synchronie mais également à générerdu logiciel ou matériel à état fini.Nous proposons et étudions les horloges entières, unegénéralisation des horloges booléennes autorisant desentiers naturels arbitrairement grands. Les horlogesentières décrivent la production ou consommation deplusieurs valeurs depuis une même file au cours d’uninstant. Nous les utilisons pour définir la constructiond’échelle de temps locale, qui peut masquer despas de temps cachés par un sous-programme au contexteenglobant.Ces principes sont intégrés à un calcul d’horloge pourun langage fonctionnel d’ordre supérieur. Nous étudionsses propriétés et prouvons en particulier que lesprogrammes bien typés ne bloquent pas. Nous compilonsles programmes typés vers des circuits numériquessynchrones en adaptant le schéma de générationde code dirigé par les horloges de Lustre. L’informationde typage contrôle certains compromis entre temps etespace dans les circuits générés. / This thesis addresses the design and implementationof a programming language for real-time streaming applications,such as video decoding. The model of Kahnprocess networks is a natural fit for this area and hasbeen used extensively. In this model, a program consistsin a set of parallel processes communicating via singlereader, single writer queues. The strength of the modellies in its determinism.Synchronous functional languages such as Lustre arededicated to critical embedded systems. A Lustre programdefines a synchronous Kahn process network, thatis, which can be executed using finite queues and withoutdeadlocks. This is enforced by a dedicated type system,the clock calculus, which establishes a global timescale throughout a program. The global time scale isused to define clocks: per-queue boolean sequences indicating,for each time step, whether a process producesor consumes a token in the queue. This information isused both for enforcing synchrony and for generatingfinite-state software or hardware.We propose and study integer clocks, a generalizationof boolean clocks featuring arbitrarily big natural numbers.Integer clocks model the production or consumptionof several values from the same queue in the courseof a time step. We then rely on integer clocks to definethe local time scale construction, which may hide timesteps performed by a sub-program from the surroundingcontext.These principles are integrated into a clock calculus fora higher-order functional language. We study its properties,proving among other results that well-typed programsdo not deadlock. We adjust the clock-directedcode generation scheme of Lustre to generate finite-statedigital synchronous circuits from typed programs. Thetyping information controls certain trade-offs betweentime and space in the generated circuits.