SCOPE: Scoped Contextual Operations and Effects.

Lead Research Organisation: Imperial College London
Department Name: Dept of 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.

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.
 
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