SCOPE: Scoped Contextual Operations and Effects.
Lead Research Organisation:
Imperial College London
Department Name: Computing
Abstract
Language is undoubtedly the most formidable tool that humanity has
ever wielded. While most spoken languages evolved organically through
the common exchange of ideas and interactions of people, the best
programming languages have been carefully crafted to
communicate the solutions of problems with fluency and precision to
computers. Humans understand that the interpretation of a sentence is
affected by its surrounding context, and the extent of its
influence determines its scope. The SCOPE project caims to translate
and transfer these concepts to the field of programming languages, and
enrich the range of tools at the disposal of the next generation of
language designers.
In the realm of software engineering, the most critical task is to
predict and control the effects that an application will perform.
Effects have proven difficult to master: their interactions are often
complex and chaotic with unpredictable interference. To maintain
control, software engineers often employ domain-specific languages
(DSLs) that consist of operations which can be composed and
interpreted to produce desired effects within a particular domain.
An application developed as a block of monolithic code is soon
impossible to manage and understand effectively. Instead, engineers
work with smaller languages and libraries that deal with their own
specialised tasks. As such, DSLs are ubiquitous in software
engineering. They manifest themselves in every programming context
ranging from small libraries and frameworks to programming languages
in their own right.
However, as requirements and expectations have become increasingly
diverse, modern applications and their DSLs must be given multiple
interpretations. For instance, they must be analysed to understand
energy requirements, vulnerability to side-channel attacks, efficiency
in space and time, and interaction with resources.
Adding a new interpretation normally incurs a tremendous engineering
effort, either requiring considerable refactoring to calculate and
record more information, or the design of new compilers and program
analysis tools. This is clearly a costly and tedious exercise that can
quickly become overwhelming. This problem is exacerbated by the
presence of multiple interacting languages, where each one requires
its own tools and interpretations. There is therefore a pressing need
for new programming language techniques that support the developers
who must face these difficult challenges.
An exciting development in programming language research that offers
help has been the innovation of algebraic effect handlers, a
technique that allows programmers to describe and manipulate the
interaction of language features in a modular and sophisticated
manner. The main insight of the technique is to focus on a clean
separation between the syntax and the semantics of a language and to
give the semantics in a structured approach. When operations and their
effects are separated, it is easy to give different interpretations of
code. The modularity and conceptual simplicity of the methodology has
attracted much academic and industrial interest and has
quickly spread to encompass implementations in many different
languages and for a variety of purposes.
Unfortunately, not all useful operations are algebraic, and even some
of the most fundamental programming language constructs fall outside
of what can be handled by the approach. Yet there is hope: the goal of
the SCOPE project is to broaden the effect handlers technique to
embrace operations that are sensitive to scope and
context, thus covering a wide range of useful constructs. Extending
our understanding of algebraic effects in this way would not only be
important for the significant theoretical insight that will be
provided, but also for the practical benefits of helping software
engineers to use algebraic effect handlers
to design and manipulate DSLs.
ever wielded. While most spoken languages evolved organically through
the common exchange of ideas and interactions of people, the best
programming languages have been carefully crafted to
communicate the solutions of problems with fluency and precision to
computers. Humans understand that the interpretation of a sentence is
affected by its surrounding context, and the extent of its
influence determines its scope. The SCOPE project caims to translate
and transfer these concepts to the field of programming languages, and
enrich the range of tools at the disposal of the next generation of
language designers.
In the realm of software engineering, the most critical task is to
predict and control the effects that an application will perform.
Effects have proven difficult to master: their interactions are often
complex and chaotic with unpredictable interference. To maintain
control, software engineers often employ domain-specific languages
(DSLs) that consist of operations which can be composed and
interpreted to produce desired effects within a particular domain.
An application developed as a block of monolithic code is soon
impossible to manage and understand effectively. Instead, engineers
work with smaller languages and libraries that deal with their own
specialised tasks. As such, DSLs are ubiquitous in software
engineering. They manifest themselves in every programming context
ranging from small libraries and frameworks to programming languages
in their own right.
However, as requirements and expectations have become increasingly
diverse, modern applications and their DSLs must be given multiple
interpretations. For instance, they must be analysed to understand
energy requirements, vulnerability to side-channel attacks, efficiency
in space and time, and interaction with resources.
Adding a new interpretation normally incurs a tremendous engineering
effort, either requiring considerable refactoring to calculate and
record more information, or the design of new compilers and program
analysis tools. This is clearly a costly and tedious exercise that can
quickly become overwhelming. This problem is exacerbated by the
presence of multiple interacting languages, where each one requires
its own tools and interpretations. There is therefore a pressing need
for new programming language techniques that support the developers
who must face these difficult challenges.
An exciting development in programming language research that offers
help has been the innovation of algebraic effect handlers, a
technique that allows programmers to describe and manipulate the
interaction of language features in a modular and sophisticated
manner. The main insight of the technique is to focus on a clean
separation between the syntax and the semantics of a language and to
give the semantics in a structured approach. When operations and their
effects are separated, it is easy to give different interpretations of
code. The modularity and conceptual simplicity of the methodology has
attracted much academic and industrial interest and has
quickly spread to encompass implementations in many different
languages and for a variety of purposes.
Unfortunately, not all useful operations are algebraic, and even some
of the most fundamental programming language constructs fall outside
of what can be handled by the approach. Yet there is hope: the goal of
the SCOPE project is to broaden the effect handlers technique to
embrace operations that are sensitive to scope and
context, thus covering a wide range of useful constructs. Extending
our understanding of algebraic effects in this way would not only be
important for the significant theoretical insight that will be
provided, but also for the practical benefits of helping software
engineers to use algebraic effect handlers
to design and manipulate DSLs.
Planned Impact
The SCOPE project aims to enhance the capabilities of the effect
handler methodology to encompass a broader range of useful
computational effects, as well as enable the technique to be applied
to a wider family of languages. A such, this research makes it
possible to give domain-specific languages multiple interpretations,
while maintaining a modular approach to language design. Among the
main applications is the ability to control the effect of resources,
thus making it easier to describe their behaviour and interact with
them in safer ways.
The impact of programming languages research on society is profound
since advances in the field eventually translate to software that is
robust, reliable, predictable, and efficient. Thus, in addition to the
academic beneficiaries, this work will bring the cutting edge of
effect handler research to the front line of software development:
there the main beneficiaries are software developers.
However, the work of laying out the appropriate foundations and
developing libraries and languages must first be accomplished before
software developers can be reached. This is precisely the aim of the
SCOPE project, where we will first develop a good understanding of
scoped and contextual effects, before implementing them in existing
languages for effect handlers. Furthermore, the project will
demonstrate the use of such effects on a wide range of applications.
The project will make use of its advisory board, developers
conferences, and online materials to reach out to and educate early
adopters of this technology. In addition, a Summer School will be
hosted with the aim of further promoting this work.
handler methodology to encompass a broader range of useful
computational effects, as well as enable the technique to be applied
to a wider family of languages. A such, this research makes it
possible to give domain-specific languages multiple interpretations,
while maintaining a modular approach to language design. Among the
main applications is the ability to control the effect of resources,
thus making it easier to describe their behaviour and interact with
them in safer ways.
The impact of programming languages research on society is profound
since advances in the field eventually translate to software that is
robust, reliable, predictable, and efficient. Thus, in addition to the
academic beneficiaries, this work will bring the cutting edge of
effect handler research to the front line of software development:
there the main beneficiaries are software developers.
However, the work of laying out the appropriate foundations and
developing libraries and languages must first be accomplished before
software developers can be reached. This is precisely the aim of the
SCOPE project, where we will first develop a good understanding of
scoped and contextual effects, before implementing them in existing
languages for effect handlers. Furthermore, the project will
demonstrate the use of such effects on a wide range of applications.
The project will make use of its advisory board, developers
conferences, and online materials to reach out to and educate early
adopters of this technology. In addition, a Summer School will be
hosted with the aim of further promoting this work.
People |
ORCID iD |
| Nicolas Wu (Principal Investigator) |
Publications
Katsumata S
(2022)
Flexible presentations of graded monads
in Proceedings of the ACM on Programming Languages
Kidney D
(2021)
Algebras for weighted search
in Proceedings of the ACM on Programming Languages
Pickering M
(2019)
Working with source plugins
Pickering M
(2020)
Staged sums of products
Pickering M
(2019)
Multi-stage programs in context
Punchihewa H
(2021)
Safe mutation with algebraic effects
Schrijvers T
(2019)
Monad transformers and modular algebraic effects: what binds them together
| Description | The objectives of the project were categorised into three main areas: foundations, implementations, and applications. In each of these areas significant progress was made, and the majority of the objectives have been successfully accomplished. In addition, new, unexpected, applications were found and explored. From the foundations and implementation perspective, the paper on structured handling of scoped effects gave a robust and theoretically motivated implementation of scoped algebraic effects, which was the most important part of the project. Further work on foundations revealed the importance of fusion on the reasoning power of algebraic effects, and the work on monad transformers and modular algebraic effects showed how the framework fits into the larger class of effects captured by monads more generally. The more recent paper on latent effects showed how scoped effects could be further extended to include important operations such as binding. In terms of implementation alone, there was significant progress made by GitHub on the fused-effects library, which is an industry-ready library based on the work of this project. Other implementations, such as polysemy, also rest on foundations of scoped effects. The goal of using scoped effects to deal with resources was successfully explored in a paper that worked with safe mutation and algebraic effects. What was unexpected, however, was the line of research towards staging. Staging is an optimisation technique that relies on compile time code generation, and this turned out to have a fruitful synergy with algebraic effects. The implementation of the parsley parser combinator library inherently makes use of algebras, and uses techniques of staging to achieve excellent performance. |
| Exploitation Route | The outcomes of this work may lead to further, more sophisticated effect libraries. We anticipate that we will continue this work as a future project. |
| Sectors | Digital/Communication/Information Technologies (including Software) |
| Description | The clearest impact has been on the development of the `fused-effects` library, engineered by GitHub and based on the work of this project. This has been used by their Semantic team to perform code analysis on repositories that they host. |
| First Year Of Impact | 2019 |
| Sector | Digital/Communication/Information Technologies (including Software) |
| Impact Types | Economic |