1,721,106 research outputs found
Safe & robust reachability analysis of hybrid systems
Full text linkHybrid systems—more precisely, their mathematical models—can exhibit behaviors, like Zeno behaviors, that are absent in purely discrete or purely continuous systems. First, we observe that, in this context, the usual definition of reachability—namely, the reflexive and transitive closure of a transition relation—can be unsafe, i.e., it may compute a proper subset of the set of states reachable in finite time from a set of initial states. Therefore, we propose safe reachability, which always computes a superset of the set of reachable states.
Second, in safety analysis of hybrid and continuous systems, it is important to ensure that a reachability analysis is also robust w.r.t. small perturbations to the set of initial states and to the system itself, since discrepancies between a system and its mathematical models are unavoidable. We show that, under certain conditions, the best Scott continuous approximation of an analysis A is also its best robust approximation. Finally, we exemplify the gap between the set of reachable states and the supersets computed by safe reachability and its best robust approximation
AutoBayes: A System for Generating Data Analysis Programs from Statistical Models
No full textData analysis is an important scientific task which is required whenever information needs to be extracted from raw data. Statistical approaches to data analysis, which use methods from probability theory and numerical analysis, are well-founded but difficult to implement: the development of a statistical data analysis program for any given application is time-consuming and requires substantial knowledge and experience in several areas. In this paper, we describe AutoBayes, a program synthesis system for the generation of data analysis programs from statistical models. A statistical model specifies the properties for each problem variable (i.e., observation or parameter) and its dependencies in the form of a probability distribution. It is a fully declarative problem description, similar in spirit to a set of differential equations. From such a model, AutoBayes generates optimized and fully commented C/C++ code which can be linked dynamically into the Matlab and Octave environments. Code is produced by a schema-guided deductive synthesis process. A schema consists of a code template and applicability constraints which are checked against the model during synthesis using theorem proving technology. AutoBayes augments schema-guided synthesis by symbolic-algebraic computation and can thus derive closed-form solutions for many problems. It is well-suited for tasks like estimating best-fitting model parameters for the given data. Here, we describe AutoBayes's system architecture, in particular the schema-guided synthesis kernel. Its capabilities are illustrated by a number of advanced textbook examples and benchmarks
System analysis and robustness
Full text linkSoftware is increasingly embedded in a variety of physical contexts. This imposes new requirements on tools that support the design and analysis of systems. For instance, modeling embedded and cyber-physical systems needs to blend discrete mathematics, which is suitable for modeling digital components, with continuous mathematics, used for modeling physical components. This blending of continuous and discrete creates challenges that are absent when the discrete or the continuous setting are considered in isolation. We consider robustness, that is, the ability of an analysis of a model to cope with small amounts of imprecision in the model. Formally, we identify analyses with monotonic maps between complete lattices (a mathematical framework used for abstract interpretation and static analysis) and define robustness for monotonic maps between complete lattices of closed subsets of a metric space. © 2019, Springer Nature Switzerland AG
A Semantic Account of Rigorous Simulation
No full textHybrid systems are a powerful formalism for modeling cyber-physical systems. Reachability analysis is a general method for checking safety properties, especially in the presence of uncertainty and non-determinism. Rigorous simulation is a convenient tool for reachability analysis of hybrid systems. However, to serve as proof tool, a rigorous simulator must be correct w.r.t. a clearly defined notion of reachability, which captures what is intuitively reachable in finite time. As a step towards addressing this challenge, this paper presents a rigorous simulator in the form of an operational semantics and a specification in the form of a denotational semantics. We show that, under certain conditions about the representation of enclosures, the rigorous simulator is correct. We also show that finding a representation satisfying these assumptions is non-trivial. © 2018, Springer International Publishing AG, part of Springer Nature.</p
Compiling dynamic languages via statically typed functional languages
No full textDynamic languages enable rapid prototyping, but are generally not viewed as providing the best performance. As a result, software developers generally build a prototype in a dynamic language and then rewrite the application in C or Fortran for high performance. This costly rewriting step can be avoided by improving the performance of dynamic languages. Dynamic languages are usually interpreted for easier implementation. The traditional approach to improve their performance is to build an optimizing compiler. However, building a compiler from scratch is much more time-consuming than implementing an interpreter. Our thesis is that we can build effective compilers for dynamic languages by translating them into statically typed functional languages which have good compilers and automatic memory management. In particular, we believe that modern statically typed languages provide precise control over data representations, and come with runtime systems that have competitive performance.
To investigate the viability of this approach, we have built a compiler for the dynamic language Python by translating it into the statically typed functional language OCaml. An interesting practical advantage of using modern statically typed functional languages is that they use Hindley-Milner type systems, which means that there is no need for the translation to construct type terms.
We compare the performance of our implementation, Monty, with that of CPython, the reference Python implementation, and with Jython, a Java implementation of Python, using a suite of 370 benchmarks. Our experiments show that some programs compiled using our approach run up to 4.6 times faster than CPython. However, due to a number of engineering reasons, some programs also run significantly slower than CPython. We pinpoint the specific causes of performance degradation and assess the potential for removing these causes in future work. Our implementation is significantly faster than Jython, up to a factor of 100 in some cases.
A by product of our research is a proposal for an improved array copying implementation in OCaml
Static analysis for circuit families
No full textAs predicted by Gordon Moore, the number of transistors on a chip has roughly doubled every two years. Microprocessors featuring over a billion transistors are no longer science fiction. For example, Intel's Itanium 9000 series and Intel's Xeon 7400 series of processors feature 1.7 and 1.9 billion transistors respectively. To keep up with the emerging needs of contemporary very large scale integration (VLSI) design, industrial hardware description languages (HDLs) like Verilog and VHDL must be significantly enhanced. This thesis pinpoints some of the main shortcomings of the latest Verilog standard (IEEE 1364-2005) and shows how to overcome them by extending the language in a backward compatible way.
To be able to cope with more complex circuits, well-understood higher-level abstraction mechanisms are needed. Verilog is already equipped with promising generative constructs making it possible to concisely describe a family of circuits as a parameterized module; however these constructs suffer from two problems: First, their expressivity is limited and second, they are not adequately supported by current tools. For instance, there are no static guarantees about the properties of the description generated as a result of instantiating a generic description with particular parameter values.
Addressing both problems while remaining backward compatible led us to select a statically typed two-level languages (STTL) formal framework. By formalizing a core subset of Verilog as an STTL, we were able to define a static type system capable of: (1) checking the realizability of a description, (2) detecting bus width mismatches and array bounds violations, and (3) providing parametric guarantees on the resources required to realize a generic description. The power of the chosen framework is once more demonstrated as it also allows us to enrich the language with a new set of constructs that are designed to be expanded away when instantiated.
To experiment with these ideas we implemented VPP, a Verilog Preprocessor with a built-in type checker. VPP is an unobtrusive tool accepting extended Verilog descriptions but generating descriptions compatible with any tool compliant with the Verilog standard.
Our experience throughout this research showed that STTLs present a particularly suitable framework to formalize and implement generative features of a language
PreVIEW: An untyped graphical calculus for resource-aware programming
No full textAs visual programming languages become both more expressive and more popular in the domains of real-time and embedded software, the need for rigorous techniques for reasoning about programs written in these languages becomes more pressing. Indeed, due to a subtle but fundamental mismatch between graphical and textual representations of programs, semantic concepts established in the textual setting cannot be mapped to the graphical setting without a careful analysis of the connection between the two representations.
Focusing on operational (as opposed to type-theoretic) aspects of Resource-aware Programming (RAP), we analyze the connection between graphical and textual representations of programs that can express both higher-order functions and staging constructs. After establishing a precise connection between the two, we illustrate how this connection can be used to lift a reduction semantics from the textual to the graphical setting
A transactional compiler for E-FRP with priorities
No full textE-FRP is declarative language for programming resource-bounded, event-driven systems. Its original high-level semantics requires that each event handler execute atomically. This facilitates reasoning about E-FRP programs, and therefore is a desirable feature of the language. However, the original compilation strategy requires that each handler complete execution before another event can occur. This implementation treats all events equally; it forces the upper bound on the time needed to respond to any event to be the same. While acceptable for many applications, often some events are more urgent than others. We show we can improve the compilation strategy without altering the high-level semantics. Thus, the programmer has more control over responsiveness without taking away the ability to reason about programs at a high level. The programmer controls responsiveness by declaring priorities for events, and the compilation strategy produces code that uses preemption to enforce these priorities. The compilation strategy enjoys the same properties as the original, with the change being that the programmer reasons modulo permutations on the order of event arrivals
Reasoning About Staged Programs
No full textThis thesis establishes formal equational properties of multi-stage
calculi and related proof techniques that support analyses of staged
programs. A key promise of staging is to make programs efficient
without destroying clarity, thereby reducing the likelihood of bugs.
However, few publications rigorously verify that their staged
programs indeed behave as intended. In fact, little is known about
how staged programs can be verified, or what correctness issues
staging introduces. To solve this problem, I show a reduction of
the correctness of a staged program to that of an unstaged program.
This reduction not only clarifies the effects of staging on program
behavior but also eases verification, as unstaged programs are more
susceptible to existing reasoning techniques. I also demonstrate
that important single-stage reasoning techniques apply to staged
programs. These techniques are useful for establishing side
conditions for the reduction and for discovering or validating
further reasoning principles.NSF grant CCF-074743
Acumen: An environment for rapid prototyping of Cyber-Physical Systems
No full textCyber-Physical Systems (CPS) combine discrete and continuous physical processes. Developing a new cyber-physical system is an iterative process that involves design, simulation, prototyping, and production. Writing simulation code using current techniques is time consuming. My thesis is that a carefully designed, domain-specific language can alleviate this difficulty. To demonstrate this thesis, I designed and implemented a prototype of a novel simulation environment called Acumen. The centerpiece of Acumen is a physical description language called PhyDL, which allows the user to directly describe dynamic equations governing the system being modeled, making the writing of simulation code much easier for engineers. A series of automatic transformations convert the high-level descriptions into a form that is directly machine executable. This thesis presents the design of PhyDL and several case studies of using PhyDL for designing CPS systems, which show that PhyDL is accurate and easy to use for domain experts
- …
