Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

McMaster University

$48,000.00

Lean Programming

EF 2024-25

Résumé
The long-term goal of this research program is to simplify program development and make programs more reliable. A recommendable step is to model a problem before implementing it. Modelling involves abstractly describing the state space and operations on it. This project challenges the necessity for the gap between modelling and programming languages by proposing a "very high-level" programming language. Programming languages support data types like sets, maps, sequences, and disjoint unions with basic operations either in the language itself or through libraries. Modelling languages like UML and SysML support more complex data types such as relations ("associations") with multiplicities and ordered structures; the OCL sublanguage allows to express constraints on those. Model-oriented specification languages like Alloy, B, Event-B, TLA, VDM, and Z have demonstrated how complex sequential, concurrent, and distributed systems can be concisely and precisely modelled using fundamental data types with a richer set of operations than in common modelling and programming languages (like restricting the domain or range of a relation or function, algebraic operations and Kleene star on relations). Recent programming languages include efficient implementations of maps in the language itself. The goal of this project is to support all modelling data types, relations, maps, sets, bags, sequences, and ordered structures with efficient implementations of a large set of operations directly in a programming language: (1) The need for refinement from a model to a program is reduced. (2) The same notation for program expressions can be used for invariants and other program properties, making it easier to express those. (3) With relations as a data type, the difficulty of verifying programs with graph-like heap structures with pointers is reduced. (4) Programs can be "debugged" effectively with model-checkers, as counterexamples on models are easier to comprehend than counterexamples on implementations. The goal is to be achieved as follows: (1) SIMD instructions will be used for runtime- and power-efficient implementations of operations on modelling data types. New data structures suitable for SIMD-assisted hashing will be developed. (2) Algebraic optimizations of complex expressions will be used to avoid constructing expensive intermediate data structures and to make execution time and memory consumption predictable. (3) With the prevalence of multi-core processors, (mostly) lock-free, thread-safe variants of data type implementations will be developed that are sound under relaxed memory models. An experimental programming language will be implemented and used to evaluate the expressiveness and efficiency of executable models. The data type implementations will be verified. This extends the work of the author's group on high-level programming languages with concurrency specified by guarded commands and flexible but safe program composition by dynamic mixins.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
RGPIN-2024-06779
Name nom
Sekerinski, Emil
Department département
Department of Computing and Software
Organization id
27
Institution établissement
McMaster University
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2024
Competition year année de concours
2024
Award amount
48000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
801
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Computer software
Area of application fr
Logiciel
Research subject code
2706
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Software engineering
Research subject fr
Génie logiciel
Field of research list names en
Not available
Field of research list names fr
Non disponible
Socioeconomic objective list names en
Not available
Socioeconomic objective list names fr
Non disponible
Application title
Lean Programming
Keywords
systems modelling; data type implementations; concurrency; verification; teaching; code generation
Application summary
The long-term goal of this research program is to simplify program development and make programs more reliable. A recommendable step is to model a problem before implementing it. Modelling involves abstractly describing the state space and operations on it. This project challenges the necessity for the gap between modelling and programming languages by proposing a "very high-level" programming language. Programming languages support data types like sets, maps, sequences, and disjoint unions with basic operations either in the language itself or through libraries. Modelling languages like UML and SysML support more complex data types such as relations ("associations") with multiplicities and ordered structures; the OCL sublanguage allows to express constraints on those. Model-oriented specification languages like Alloy, B, Event-B, TLA, VDM, and Z have demonstrated how complex sequential, concurrent, and distributed systems can be concisely and precisely modelled using fundamental data types with a richer set of operations than in common modelling and programming languages (like restricting the domain or range of a relation or function, algebraic operations and Kleene star on relations). Recent programming languages include efficient implementations of maps in the language itself. The goal of this project is to support all modelling data types, relations, maps, sets, bags, sequences, and ordered structures with efficient implementations of a large set of operations directly in a programming language: (1) The need for refinement from a model to a program is reduced. (2) The same notation for program expressions can be used for invariants and other program properties, making it easier to express those. (3) With relations as a data type, the difficulty of verifying programs with graph-like heap structures with pointers is reduced. (4) Programs can be "debugged" effectively with model-checkers, as counterexamples on models are easier to comprehend than counterexamples on implementations. The goal is to be achieved as follows: (1) SIMD instructions will be used for runtime- and power-efficient implementations of operations on modelling data types. New data structures suitable for SIMD-assisted hashing will be developed. (2) Algebraic optimizations of complex expressions will be used to avoid constructing expensive intermediate data structures and to make execution time and memory consumption predictable. (3) With the prevalence of multi-core processors, (mostly) lock-free, thread-safe variants of data type implementations will be developed that are sound under relaxed memory models. An experimental programming language will be implemented and used to evaluate the expressiveness and efficiency of executable models. The data type implementations will be verified. This extends the work of the author's group on high-level programming languages with concurrency specified by guarded commands and flexible but safe program composition by dynamic mixins.