Functional programs are particularly well suited to formal manipulation by equational reasoning. In particular, it is straightforward to use calculational methods for program transformation. Well-known transformation techniques, like tupling or the ...
Quotient lenses | Proceedings of the 13th ACM SIGPLAN international conference on Functional programming
Bidirectional programming languages are a practical approach to the view update problem. Programs in these languages, called lenses, define both a view and an update policy - i.e., every program can be read as a function mapping sources to views as well ...
Symmetric lenses | Proceedings of the 38th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages
A lens is a bidirectional transformation between a pair of connected data structures, capable of translating an edit on one structure into an appropriate edit on the other. Many varieties of lenses have been studied, but none, to date, has offered a ...
Boomerang | Proceedings of the 35th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages
Bidirectional programming languages are a practical approach to the view update problem. Programs in these languages, called lenses, define both a view and an update policy - i.e., every program can be read as a function mapping sources to views as well ...
Principal type-schemes for functional programs | Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages
As part of the Digital Library's transition to Open Access, new features for researchers are available in the Premium Edition. Click here to learn more.
The mythical matched modules | Proceedings of the 24th ACM SIGPLAN conference companion on Object oriented programming systems languages and applications
Certified compilers are complex software systems. Like other large systems, they demand modular, extensible designs. While there has been progress in extensible metatheory mechanization, scaling extensibility and reuse to meet the demands of full ...
Resugaring | Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation
Syntactic sugar plays a crucial role in engineering programming languages. It offers convenient syntax and higher-level of abstractions, as witnessed by its pervasive use in both general-purpose and domain-specific contexts. Unfortunately, the ...
Bidirectional Programming Languages
The need to edit source data through a view arises in a host of applications across many different areas of computing. Unfortunately, few existing systems provide support for updatable views. In practice, when they are needed, updatable views are usually implemented using two separate programs: one that computes the view from the source and another that handles updates. This rudimentary design is tedious for programmers, difficult to reason about, and a nightmare to maintain. This dissertation presents bidirectional programming languages, which provide an elegant and effective mechanism for describing updatable views. Unlike programs written in an ordinary language, which only work in one direction, programs in a bidirectional language can be run both forwards and backwards: from left to right, they describe functions that map sources to views, and from right to left, they describe functions that map updated views back to updated sources. Besides eliminating redundancy, these languages can be designed to ensure correctness, guaranteeing by construction that the two functions work well together. Starting from the foundations, we define a general semantic space of well-behaved bidirectional transformations called lenses. Then, building on this foundation, we describe a particular language for defining lenses on strings with syntax based on the familiar regular operators (union, concatenation, and Kleene star). We present extensions to the basic framework that address the subtle complications that arise when lenses are used to manipulate, data containing unimportant details, ordered data, and confidential data.
Profunctor Optics, a Categorical Update
Optics are bidirectional data accessors that capture data transformation patterns such as accessing subfields or iterating over containers. Profunctor optics are a particular choice of representation supporting modularity, meaning that we can construct accessors for complex structures by combining simpler ones. Profunctor optics have previously been studied only in an unenriched and non-mixed setting, in which both directions of access are modelled in the same category. However, functional programming languages are arguably better described by enriched categories; and we have found that some structures in the literature are actually mixed optics, with access directions modelled in different categories. Our work generalizes a classic result by Pastro and Street on Tambara theory and uses it to describe mixed V-enriched profunctor optics and to endow them with V-category structure. We provide some original families of optics and derivations, including an elementary one for traversals. Finally, we discuss a Haskell implementation.
Bidirectionalization for free! (Pearl) | Proceedings of the 36th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages
A bidirectional transformation consists of a function get that takes a source (document or value) to a view and a function put that takes an updated view and the original source back to an updated source, governed by certain consistency conditions ...
Delta Lenses over Inductive Types
Existing bidirectional languages are either state-based or operation-based, depending on whether they represent updates as mere states or as sequences of edit operations.In-between both worlds are delta-based frameworks, where updates are represented using alignment relationships between states.In this paper, we formalize delta lenses over inductive types using dependent type theory and develop a point-free delta lens language with an explicit separation of shape and data.In contrast with the already known issue of data alignment, we identify the new problem of shape alignment and solve it by lifting standard recursion patterns such as folds and unfolds to delta lenses that use alignment to infer meaningful shape updates.
Compiling Higher-Order Specifications to SMT Solvers: How to Deal with Rejection Constructively | Proceedings of the 12th ACM SIGPLAN International Conference on Certified Programs and Proofs
We present a decision procedure that combines reasoning about datatypes and codatatypes. The dual of the acyclicity rule for datatypes is a uniqueness rule that identifies observationally equal codatatype values, including cyclic values. The procedure ...
Packrat parsing: | Proceedings of the seventh ACM SIGPLAN international conference on Functional programming
For decades we have been using Chomsky's generative system of grammars, particularly context-free grammars (CFGs) and regular expressions (REs), to express the syntax of programming languages and protocols. The power of generative grammars to express ...
@tomlarkworthy/svg-lens
The drawing syncs to the code and vice versa. Switch between using code and UI. Built on composable lens [Foster et al. 2007] and edit-lens [Hofmann et al. 2012] theory, but applied in the string domain so unknown semantics like SVG animations are preserved without parsing. Follows the path of Sketch-n-Sketch [Chugh et al. 2016] [Hempel et al. 2019] but applied to an existing image format: SVG. Generated with a novel prompting strategy of requesting an LLM to use property checking against mathematical laws as a architecture, leading to strong implementation consistency over an expansive domain.
Foundations of Algebraic Specification and Formal Software Development
This book provides foundations for software specification and formal software development from the perspective of work on algebraic specification, concentrating on developing basic concepts and studying their fundamental properties. These foundations are built on a solid mathematical basis, using elements of universal algebra, category theory and logic, and this mathematical toolbox provides a convenient language for precisely formulating the concepts involved in software specification and development. Once formally defined, these notions become subject to mathematical investigation, and this interplay between mathematics and software engineering yields results that are mathematically interesting, conceptually revealing, and practically useful. The theory presented by the authors has its origins in work on algebraic specifications that started in the early 1970s, and their treatment is comprehensive. This book contains five kinds of material: the requisite mathematicalfoundations; traditional algebraic specifications; elements of the theory of institutions; formal specification and development; and proof methods. While the book is self-contained, mathematical maturity and familiarity with the problems of software engineering is required; and in the examples that directly relate to programming, the authors assume acquaintance with the concepts of functional programming. The book will be of value to researchers and advanced graduate students in the areas of programming and theoretical computer science.
Combinators for bidirectional tree transformations: A linguistic approach to the view-update problem: ACM Transactions on Programming Languages and Systems: Vol 29, No 3
We propose a novel approach to the view-update problem for tree-structured data: a domain-specific programming language in which all expressions denote bidirectional transformations on trees. In one direction, these transformations---dubbed lenses---map ...
A modal analysis of staged computation | Journal of the ACM
We show that a type system based on the intuitionistic modal logic S4 provides an expressive framework for specifying and analyzing computation stages in the context of typed λ-calculi and functional languages. We directly demonstrate the sense in which ...
