Search

Your search keyword '"Timothy Bourke"' showing total 103 results
Start Over Author "Timothy Bourke"
103 results on '"Timothy Bourke"'

1. Sundials/ML: Connecting OCaml to the Sundials Numeric Solvers

Author

Timothy Bourke, Jun Inoue, and Marc Pouzet

Subjects
Mathematics, QA1-939, Electronic computers. Computer science, QA75.5-76.95
Abstract

This paper describes the design and implementation of a comprehensive OCaml interface to the Sundials library of numeric solvers for ordinary differential equations, differential algebraic equations, and non-linear equations. The interface provides a convenient and memory-safe alternative to using Sundials directly from C and facilitates application development by integrating with higher-level language features, like garbage-collected memory management, algebraic data types, and exceptions. Our benchmark results suggest that the interface overhead is acceptable: the standard examples are rarely twice as slow in OCaml than in C, and often less than 50% slower. The challenges in interfacing with Sundials are to efficiently and safely share data structures between OCaml and C, to support multiple implementations of vector operations and linear solvers through a common interface, and to manage calls and error signalling to and from OCaml. We explain how we overcame these difficulties using a combination of standard techniques such as phantom types and polymorphic variants, and carefully crafted data representations.

Published
2018
Full Text
View/download PDF

16. Scheduling and Compiling Rate-Synchronous Programs with End-To-End Latency Constraints

Author

Timothy Bourke and Vincent Bregeon and Marc Pouzet, Bourke, Timothy, Bregeon, Vincent, Pouzet, Marc, Timothy Bourke and Vincent Bregeon and Marc Pouzet, Bourke, Timothy, Bregeon, Vincent, and Pouzet, Marc

Abstract

We present an extension of the synchronous-reactive model for specifying multi-rate systems. A set of periodically executed components and their communication dependencies are expressed in a Lustre-like programming language with features for load balancing, resource limiting, and specifying end-to-end latencies. The language abstracts from execution time and phase offsets. This permits simple clock typing rules and a stream-based semantics, but requires each component to execute within an overall base period. A program is compiled to a single periodic task in two stages. First, Integer Linear Programming is used to determine phase offsets using standard encodings for dependencies and load balancing, and a novel encoding for end-to-end latency. Second, a code generation scheme is adapted to produce step functions. As a result, components are synchronous relative to their respective rates, but not necessarily simultaneous relative to the base period. This approach has been implemented in a prototype compiler and validated on an industrial application.

Published
2023
Full Text
View/download PDF

30. Verified Lustre Normalization with Node Subsampling

Author

Basile Pesin, Paul Jeanmaire, Marc Pouzet, Timothy Bourke, Université Paris sciences et lettres (PSL), Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Parallélisme de Kahn Synchrone ( Parkas), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), BPI 'Programme d'Investissements d'Avenir' - ES3CAP, ANR-19-CE25-0014,FidelR,FidelR(2019), Département d'informatique - ENS Paris (DI-ENS), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Département d'informatique - ENS Paris (DI-ENS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure - Paris (ENS-PSL), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL)

Subjects
CCS Concepts: • Software and its engineering → Formal language definitions, Normalization (statistics), interactive theorem proving, Correctness, Computer science, Semantics (computer science), Dataflow, • Computer systems organization → Embedded software stream languages, 02 engineering and technology, computer.software_genre, Software verification, 020204 information systems, 0202 electrical engineering, electronic engineering, information engineering, computer.programming_language, [INFO.INFO-PL]Computer Science [cs]/Programming Languages [cs.PL], Assembly language, Programming language, Lustre (programming language), Proof assistant, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], 020207 software engineering, verified compilation, Compilers, Hardware and Architecture, TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS, [INFO.INFO-ES]Computer Science [cs]/Embedded Systems, Compiler, computer, Software
Abstract

Dataflow languages allow the specification of reactive systems by mutually recursive stream equations, functions, and boolean activation conditions called clocks. Lustre and Scade are dataflow languages for programming embedded systems. Dataflow programs are compiled by a succession of passes. This article focuses on the normalization pass which rewrites programs into the simpler form required for code generation. Vélus is a compiler from a normalized form of Lustre to CompCert’s Clight language. Its specification in the Coq interactive theorem prover includes an end-to-end correctness proof that the values prescribed by the dataflow semantics of source programs are produced by executions of generated assembly code. We describe how to extend Vélus with a normalization pass and to allow subsampled node inputs and outputs. We propose semantic definitions for the unrestricted language, divide normalization into three steps to facilitate proofs, adapt the clock type system to handle richer node definitions, and extend the end-to-end correctness theorem to incorporate the new features. The proofs require reasoning about the relation between static clock annotations and the presence and absence of values in the dynamic semantics. The generalization of node inputs requires adding a compiler pass to ensure the initialization of variables passed in function calls.

Published
2021
Full Text
View/download PDF

39. Dependable Software Engineering. Theories, Tools, and Applications : 10th International Symposium, SETTA 2024, Hong Kong, China, November 26–28, 2024, Proceedings

Author

Timothy Bourke, Liqian Chen, Amir Goharshady, Timothy Bourke, Liqian Chen, and Amir Goharshady

Subjects
Software engineering, Computer science, Artificial intelligence, Computer engineering, Computer networks
Abstract

This book constitutes the refereed proceedings of the 10th International Symposium on Dependable Software Engineering. Theories, Tools, and Applications, SETTA 2024, held in Hong Kong, China, during November 26–28, 2024. The 21 full papers included in this book were carefully reviewed and selected from 47 submissions. The purpose of the SETTA symposium series is to bring international researchers together to exchange research results and ideas on bridging the gap between formal methods and software engineering.

Published
2024

40. Mechanized semantics and verified compilation for a dataflow synchronous language with reset

Author

Lélio Brun, Timothy Bourke, Marc Pouzet, Université Paris sciences et lettres (PSL), Département d'informatique - ENS Paris (DI-ENS), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Parallélisme de Kahn Synchrone ( Parkas), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Département d'informatique - ENS Paris (DI-ENS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Sorbonne Université (SU), Bpifrance Invest for the Future Program ('Programme d’Investissements d’Avenir') in the ES3CAP project, ES3CAP, École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris)

Subjects
CCS Concepts: • Software and its engineering → Formal language definitions, Interactive theorem proving, Computer science, Dataflow, Stateflow, 02 engineering and technology, computer.software_genre, • Computer systems organization → Embedded software Additional Key Words and Phrases: stream languages, Software verification, 0202 electrical engineering, electronic engineering, information engineering, Verified compilation, Safety, Risk, Reliability and Quality, computer.programming_language, Finite-state machine, [INFO.INFO-PL]Computer Science [cs]/Programming Languages [cs.PL], Assembly language, Programming language, Lustre (programming language), Proof assistant, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], 020207 software engineering, computer.file_format, 020202 computer hardware & architecture, Compilers, TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS, [INFO.INFO-ES]Computer Science [cs]/Embedded Systems, Compiler, Executable, computer, Software
Abstract

Specifications based on block diagrams and state machines are used to design control software, especially in the certified development of safety-critical applications. Tools like SCADE Suite and Simulink/Stateflow are equipped with compilers that translate such specifications into executable code. They provide programming languages for composing functions over streams as typified by Dataflow Synchronous Languages like Lustre. Recent work builds on CompCert to specify and verify a compiler for the core of Lustre in the Coq Interactive Theorem Prover. It formally links the stream-based semantics of the source language to the sequential memory manipulations of generated assembly code. We extend this work to treat a primitive for resetting subsystems. Our contributions include new semantic rules that are suitable for mechanized reasoning, a novel intermediate language for generating optimized code, and proofs of correctness for the associated compilation passes.

Published
2020
Full Text
View/download PDF

41. Sundials/ML: Connecting OCaml to the Sundials Numeric Solvers

Author

Marc Pouzet, Timothy Bourke, Jun Inoue, Université Paris sciences et lettres (PSL), Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Parallélisme de Kahn Synchrone ( Parkas), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), National Institute of Advanced Industrial Science and Technology (AIST), Département d'informatique - ENS Paris (DI-ENS), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Département d'informatique - ENS Paris (DI-ENS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure - Paris (ENS-PSL), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL)

Subjects
FOS: Computer and information sciences, Computer science, Interface (Java), 010103 numerical & computational mathematics, 02 engineering and technology, computer.software_genre, 01 natural sciences, lcsh:QA75.5-76.95, ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, 0202 electrical engineering, electronic engineering, information engineering, Overhead (computing), 0101 mathematics, [INFO.INFO-MS]Computer Science [cs]/Mathematical Software [cs.MS], [INFO.INFO-PL]Computer Science [cs]/Programming Languages [cs.PL], Computer Science - Programming Languages, OCaml, Programming language, lcsh:Mathematics, Numeric simulation, [INFO.INFO-NA]Computer Science [cs]/Numerical Analysis [cs.NA], lcsh:QA1-939, Data structure, 020202 computer hardware & architecture, Memory management, Interfacing, Algebraic data type, Benchmark (computing), Computer Science - Mathematical Software, lcsh:Electronic computers. Computer science, Mathematical Software (cs.MS), Differential algebraic equation, computer, Programming Languages (cs.PL)
Abstract

This paper describes the design and implementation of a comprehensive OCaml interface to the Sundials library of numeric solvers for ordinary differential equations, differential algebraic equations, and non-linear equations. The interface provides a convenient and memory-safe alternative to using Sundials directly from C and facilitates application development by integrating with higher-level language features, like garbage-collected memory management, algebraic data types, and exceptions. Our benchmark results suggest that the interface overhead is acceptable: the standard examples are rarely twice as slow in OCaml than in C, and often less than 50% slower. The challenges in interfacing with Sundials are to efficiently and safely share data structures between OCaml and C, to support multiple implementations of vector operations and linear solvers through a common interface, and to manage calls and error signalling to and from OCaml. We explain how we overcame these difficulties using a combination of standard techniques such as phantom types and polymorphic variants, and carefully crafted data representations., In Proceedings ML/OCAML 2016, arXiv:1812.10891

Published
2018
Full Text
View/download PDF

42. Building a Hybrid Systems Modeler on Synchronous Languages Principles

Author

Jean-Louis Colaço, Albert Benveniste, Cédric Pasteur, Timothy Bourke, Benoît Caillaud, Marc Pouzet, Modélisation hybride & conception par contrats pour les systèmes embarqués multi-physiques (HYCOMES), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-LANGAGE ET GÉNIE LOGICIEL (IRISA-D4), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Université Paris sciences et lettres (PSL), Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Parallélisme de Kahn Synchrone ( Parkas), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Département d'informatique de l'École normale supérieure (DI-ENS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS), Esterel Technologies / Ansys [Toulouse], Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Département d'informatique - ENS Paris (DI-ENS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)

Subjects
0209 industrial biotechnology, Synchronous Languages, Modeling language, Computer science, 02 engineering and technology, computer.software_genre, 020901 industrial engineering & automation, 0202 electrical engineering, electronic engineering, information engineering, Electrical and Electronic Engineering, Numerical Simulation, Implementation, computer.programming_language, [INFO.INFO-PL]Computer Science [cs]/Programming Languages [cs.PL], Programming language, Lustre (programming language), Cyber-physical system, Solver, Hybrid Systems, [INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation, 020202 computer hardware & architecture, HybridLang, Conservative extension, Hybrid system, Computer Science::Programming Languages, [INFO.INFO-ES]Computer Science [cs]/Embedded Systems, Compiler, computer
Abstract

International audience; Hybrid systems modeling languages that mix discrete and continuous time signals and systems are widely used to develop Cyber-Physical systems where control software interacts with physical devices. Compilers play a central role, statically checking source models, generating intermediate representations for testing and verification, and producing sequential code for simulation and execution on target platforms.This paper presents a novel approach to the design and implementation of a hybrid systems language, built on synchronous language principles and their proven compilation techniques. The result is a hybrid systems modeling language in which synchronous programming constructs can be mixed with Ordinary Differential Equations (ODEs) and zero-crossing events, and a runtime that delegates their approximation to an off-the-shelf numerical solver.We propose an ideal semantics based on non standard analysis, which defines the execution of a hybrid model as an infinite sequence of infinitesimally small time steps. It is used to specify and prove correct three essential compilation steps: (1) a type system that guarantees that a continuous-time signal is never used where a discrete-time one is expected and conversely; (2) a type system that ensures the absence of combinatorial loops; (3) the generation of statically scheduled code for efficient execution.Our approach has been evaluated in two implementations: the academic language Zélus, which extends a language reminiscent of Lustre with ODEs and zero-crossing events, and the industrial prototype Scade Hybrid, a conservative extension of Scade 6.

Published
2018
Full Text
View/download PDF

43. Towards a verified Lustre compiler with modular reset

Author

Lélio Brun, Marc Pouzet, Timothy Bourke, Parallélisme de Kahn Synchrone ( Parkas), Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Université Paris sciences et lettres (PSL), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS), Département d'informatique de l'École normale supérieure (DI-ENS), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Département d'informatique - ENS Paris (DI-ENS), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)

Subjects
Verified Compilation, [INFO.INFO-PL]Computer Science [cs]/Programming Languages [cs.PL], Lustre (programming language), Computer science, Programming language, business.industry, Correctness proofs, 020207 software engineering, 02 engineering and technology, Modular design, Formal software verification, computer.software_genre, Sketch, Semantics, Compilers, 020204 information systems, Formal specification, TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS, 0202 electrical engineering, electronic engineering, information engineering, [INFO.INFO-ES]Computer Science [cs]/Embedded Systems, Compiler, business, computer, computer.programming_language, Synchronous Languages (Lustre)
Abstract

International audience; This paper presents ongoing work to add a modular reset construct to a verified Lustre compiler. We present a novel formal specification for the construct and sketch our plans to integrate it into the compiler and its correctness proof.

Published
2018
Full Text
View/download PDF

44. A Type-based Analysis of Causality Loops in Hybrid Systems Modelers

Author

Marc Pouzet, Bruno Pagano, Timothy Bourke, Benoît Caillaud, Albert Benveniste, Modélisation hybride & conception par contrats pour les systèmes embarqués multi-physiques (HYCOMES), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-LANGAGE ET GÉNIE LOGICIEL (IRISA-D4), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Parallélisme de Kahn Synchrone ( Parkas), Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Esterel Technologies / Ansys [Toulouse], Université Paris sciences et lettres (PSL), Sorbonne Université (SU), This work has been partially funded by the Sys2Soft, Briques Génériques du Logiciel Embarqué, Investissements d’Avenir French national project, Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Département d'informatique - ENS Paris (DI-ENS), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure - Paris (ENS Paris), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Département d'informatique de l'École normale supérieure (DI-ENS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)

Subjects
0209 industrial biotechnology, State variable, Theoretical computer science, Hybrid systems, Modeling language, Computer science, Semantics (computer science), [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], 0211 other engineering and technologies, Stateflow, Type systems, 02 engineering and technology, ACM: F.: Theory of Computation/F.3: LOGICS AND MEANINGS OF PROGRAMS/F.3.2: Semantics of Programming Languages/F.3.2.2: Operational semantics, Causality (physics), 020901 industrial engineering & automation, Operator (computer programming), [INFO.INFO-AU]Computer Science [cs]/Automatic Control Engineering, 0202 electrical engineering, electronic engineering, information engineering, 021106 design practice & management, computer.programming_language, [INFO.INFO-MS]Computer Science [cs]/Mathematical Software [cs.MS], ACM: G.: Mathematics of Computing/G.1: NUMERICAL ANALYSIS/G.1.7: Ordinary Differential Equations, Numerical solver, SIGNAL (programming language), Static analysis, [INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation, Computer Science Applications, Control and Systems Engineering, HybridLang, Hybrid system, 020201 artificial intelligence & image processing, [INFO.INFO-ES]Computer Science [cs]/Embedded Systems, Mathematical modelling language, Algorithm, computer, Analysis, Synchronous programming languages
Abstract

International audience; Explicit hybrid systems modelers like Simulink/Stateflow allow for programming both discrete-and continuous-time behaviors with complex interactions between them. An important step in their compilation is the static detection of algebraic or causality loops. Such loops can cause simulations to deadlock and prevent the generation of statically scheduled code. This paper addresses this issue for a hybrid modeling language that combines synchronous data-flow equations with Ordinary Differential Equations (ODEs). We introduce the operator last x for the left-limit of a signal x. The last x operator is used to break causality loops and permits a uniform treatment of discrete and continuous state variables. The semantics of the language relies on non-standard analysis, defining an execution as a sequence of infinitesimally small steps. A signal is deemed causally correct when it can be computed sequentially and only changes infinitesimally outside of announced discrete events like zero-crossings. The causality analysis takes the form of a type system that expresses dependencies between signals. In well-typed programs, signals are provably continuous during integration provided that imported external functions are also continuous, and sequential code can be generated. The effectiveness of the system is illustrated with several examples written in Zélus, a Lustre-like synchronous language extended with ODEs.

Published
2017
Full Text
View/download PDF

45. A Synchronous Look at the Simulink Standard Library

Author

Cédric Pasteur, Francois Carcenac, Bruno Pagano, Timothy Bourke, Jean-Louis Colaço, Marc Pouzet, Parallélisme de Kahn Synchrone ( Parkas), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Département d'informatique - ENS Paris (DI-ENS), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Esterel Technologies / Ansys [Toulouse], Université Pierre et Marie Curie - Paris 6 (UPMC), Département d'informatique - ENS Paris (DI-ENS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Bourke, Timothy, École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS), and Département d'informatique de l'École normale supérieure (DI-ENS)

Subjects
0209 industrial biotechnology, [INFO.INFO-LO] Computer Science [cs]/Logic in Computer Science [cs.LO], Computer science, Synchronous Languages, Block diagram, 02 engineering and technology, computer.software_genre, Set (abstract data type), 020901 industrial engineering & automation, 0202 electrical engineering, electronic engineering, information engineering, Code (cryptography), computer.programming_language, Block Diagrams, [INFO.INFO-PL]Computer Science [cs]/Programming Languages [cs.PL], Programming language, Lustre (programming language), [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], Hybrid Systems, [INFO.INFO-ES] Computer Science [cs]/Embedded Systems, [INFO.INFO-PL] Computer Science [cs]/Programming Languages [cs.PL], 020202 computer hardware & architecture, Automaton, Imperative programming, Hardware and Architecture, Hybrid system, Ordinary differential equation, Computer Science::Programming Languages, [INFO.INFO-ES]Computer Science [cs]/Embedded Systems, computer, Software
Abstract

Hybrid systems modelers like Simulink come with a rich collection of discrete-time and continuous-time blocks. Most blocks are not defined in terms of more elementary ones—and some cannot be—but are instead written in imperative code and explained informally in a reference manual. This raises the question of defining a minimal set of orthogonal programming constructs such that most blocks can be programmed directly and thereby given a specification that is mathematically precise, and whose compiled version performs comparably to handwritten code. In this paper, we show that a fairly large set of blocks of a standard library like the one provided by Simulink can be programmed in a precise, purely functional language using stream equations, hierarchical automata, Ordinary Differential Equations (ODEs), and deterministic synchronous parallel composition. Some blocks cannot be expressed in our setting as they mix discrete-time and continuous-time signals in unprincipled ways that are statically forbidden by the type checker. The experiment is conducted in Zélus, a synchronous language that conservatively extends L ustre with ODEs to program systems that mix discrete-time and continuous-time signals.

Published
2017

46. Real-Time Ticks for Synchronous Programming

Author

Timothy Bourke, Alain Girault, Reinhard von Hanxleden, Department of Computer Science [Kiel], Christian-Albrechts-Universität zu Kiel (CAU), Parallélisme de Kahn Synchrone ( Parkas), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Département d'informatique - ENS Paris (DI-ENS), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Sound Programming of Adaptive Dependable Embedded Systems (SPADES), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'Informatique de Grenoble (LIG ), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), German Science Foundation, as part of the Precision-Timed Synchronous Reactive Processing project (PRETSY2,DFG HA 4407/6-2), Electronic Chips & System Design Initiative (ECSI), Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL)

Subjects
0209 industrial biotechnology, Computer science, Semantics (computer science), Synchronous Languages, media_common.quotation_subject, Physical Time, 02 engineering and technology, computer.software_genre, Reactive Systems, Electronic mail, Instruction set, 020901 industrial engineering & automation, 0202 electrical engineering, electronic engineering, information engineering, Real-Time Systems, Function (engineering), Reactive system, computer.programming_language, media_common, Abstraction (linguistics), [INFO.INFO-PL]Computer Science [cs]/Programming Languages [cs.PL], Programming language, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], 020202 computer hardware & architecture, Esterel, [INFO.INFO-ES]Computer Science [cs]/Embedded Systems, Synchronous motor, computer
Abstract

International audience; We address the problem of synchronous programs that cannot be easily executed in a classical time-triggered or event-triggered execution loop. We propose a novel approach, referred to as dynamic ticks, that reconciles the semantic timing abstraction of the synchronous approach with the desire to give the application fine-grained control over its real-time behavior. The main idea is to allow the application to dynamically specify its own wake-up times rather than ceding their control to the environment. As we illustrate in this paper, synchronous languages such as Esterel are already well equipped for this; no language extensions are needed. All that is required is a rather minor adjustment of the way the tick function is called.

Published
2017

47. Symbolic Simulation of Dataflow Synchronous Programs with Timers

Author

Timothy Bourke, Marc Pouzet, Guillaume Baudart, IBM T. J. Watson Research Centre, Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Parallélisme de Kahn Synchrone ( Parkas), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Université Pierre et Marie Curie - Paris 6 (UPMC), Electronic Chips & System Design Initiative (ECSI), Daniel Große, Sara Vinco, Hiren Patel, Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Département d'informatique - ENS Paris (DI-ENS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris)

Subjects
Computer science, Dataflow, Synchronous Languages, Symbolic Simulation, Symbolic simulation, 0102 computer and information sciences, 02 engineering and technology, computer.software_genre, 01 natural sciences, Formal specification, 0202 electrical engineering, electronic engineering, information engineering, Timed Automata, computer.programming_language, [INFO.INFO-PL]Computer Science [cs]/Programming Languages [cs.PL], Lustre (programming language), Programming language, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], Solver, Type System, Compilation, Hybrid Systems, [INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation, Automaton, Nondeterministic algorithm, 010201 computation theory & mathematics, Hybrid system, Computer Science::Programming Languages, 020201 artificial intelligence & image processing, computer
Abstract

International audience; The synchronous language Lustre and its descendants have long been used to program and model discrete controllers. Recent work shows how to mix discrete and continuous elements in a Lustre-like language called Zélus. The resulting hybrid programs are deterministic and can be simulated with a numerical solver. In this article, we focus on a subset of hybrid programs where continuous behaviors are expressed using timers, nondeterministic guards, and invariants, as in Timed Safety Automata. We propose a source-to-source compilation pass to generate discrete code that, coupled with standard operations on Difference-Bound Matrices, produces symbolic traces that each represent a set of concrete traces.

Published
2017
Full Text
View/download PDF

48. Mechanizing a Process Algebra for Network Protocols

Author

Rob van Glabbeek, Timothy Bourke, Peter Höfner, Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Parallélisme de Kahn Synchrone ( Parkas), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), National ICT Australia [Sydney] (NICTA), University of New South Wales [Sydney] (UNSW), Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Département d'informatique - ENS Paris (DI-ENS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)

Subjects
FOS: Computer and information sciences, Computer Science - Logic in Computer Science, Theoretical computer science, Computer science, Process calculus, HOL, 0102 computer and information sciences, 02 engineering and technology, Interactive Theorem Proving (Isabelle/HOL), Mathematical proof, Wireless Mesh Networks, 01 natural sciences, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], C.2.2, Artificial Intelligence, F.3.1, 0202 electrical engineering, electronic engineering, information engineering, Invariant (mathematics), Compositional Invariant Proofs, Mobile Ad hoc Networks, Wireless mesh network, Proof assistant, bepress|Physical Sciences and Mathematics|Computer Sciences, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], 020207 software engineering, Mobile ad hoc network, Logic in Computer Science (cs.LO), Process Algebra, Computational Theory and Mathematics, 010201 computation theory & mathematics, TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS, Networks, Communications protocol, Software
Abstract

This paper presents the mechanization of a process algebra for Mobile Ad hoc Networks and Wireless Mesh Networks, and the development of a compositional framework for proving invariant properties. Mechanizing the core process algebra in Isabelle/HOL is relatively standard, but its layered structure necessitates special treatment. The control states of reactive processes, such as nodes in a network, are modelled by terms of the process algebra. We propose a technique based on these terms to streamline proofs of inductive invariance. This is not sufficient, however, to state and prove invariants that relate states across multiple processes (entire networks). To this end, we propose a novel compositional technique for lifting global invariants stated at the level of individual nodes to networks of nodes., This paper is an extended version of arXiv:1407.3519. The Isabelle/HOL source files, and a full proof document, are available in the Archive of Formal Proofs, at http://afp.sourceforge.net/entries/AWN.shtml

Published
2015
Full Text
View/download PDF

49. A Synchronous-Based Code Generator for Explicit Hybrid Systems Languages

Author

Jean-Louis Colaço, Marc Pouzet, Bruno Pagano, Timothy Bourke, and Cédric Pasteur

Subjects
Source code, Programming language, Modeling language, business.industry, Computer science, media_common.quotation_subject, computer.software_genre, Software, Embedded software, Hybrid system, KPI-driven code analysis, Code generation, Compiler, business, computer, media_common
Abstract

Modeling languages for hybrid systems are cornerstones of embedded systems development in which software interacts with a physical environment. Sequential code generation from such languages is important for simulation efficiency and for producing code for embedded targets. Despite being routinely used in industrial compilers, code generation is rarely, if ever, described in full detail, much less formalized. Yet formalization is an essential step in building trustable compilers for critical embedded software development.

Published
2015
Full Text
View/download PDF

50. FORMAL MODELS IN INDUSTRY STANDARD TOOLS: AN ARGOS BLOCK WITHIN SIMULINK

Author

Arcot Sowmya and Timothy Bourke

Subjects
Computer Networks and Communications, Computer science, Programming language, Industry standard, Stateflow, computer.software_genre, Notation, Computer Graphics and Computer-Aided Design, Artificial Intelligence, ComputerSystemsOrganization_SPECIAL-PURPOSEANDAPPLICATION-BASEDSYSTEMS, Reactive system, computer, Software, Block (data storage), computer.programming_language
Abstract

Simulink is widely used within the industry for simulation and model-driven development, and reactive behaviors are often modeled using an add-on called Stateflow. Argos is one of the synchronous languages that have been proposed for the specification, validation and implementation of reactive systems. It is a rigorously defined graphical notation which, though not as powerful as Stateflow, is much less complicated. This paper describes the implementation of an Argos block for Simulink.

Published
2005
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results