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 ...
Integrating functional and imperative programming | Proceedings of the 1986 ACM conference on LISP and functional programming
We present a new model, based on monads, for performing input/output in a non-strict, purely functional language. It is composable, extensible, efficient, requires no extensions to the type system, and extends smoothly to incorporate mixed-language ...
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 ...
Generic deriving of generic traversals | Proceedings of the ACM on Programming Languages
Functional programmers have an established tradition of using traversals as a design pattern to work with recursive data structures. The technique is so prolific that a whole host of libraries have been designed to help in the task of automatically ...
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.
Abstract syntax and variable binding
We develop a theory of abstract syntax with variable binding. To every binding signature we associate a category of models consisting of variable sets endowed with compatible algebra and substitution structures. The syntax generated by the signature is the initial model. This gives a notion of initial algebra semantics encompassing the traditional one; besides compositionality, it automatically verifies the semantic substitution lemma.
Efficient and flexible incremental parsing | ACM Transactions on Programming Languages and Systems
Previously published algorithms for LR (k) incremental parsing are inefficient, unnecessarily restrictive, and in some cases incorrect. We present a simple algorithm based on parsing LR(k) sentential forms that can incrementally parse an arbitrary number ...
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 ...
Coeffects: a calculus of context-dependent computation
The notion of context in functional languages no longer refers just to variables in scope. Context can capture additional properties of variables (usage patterns in linear logics; caching requirements in dataflow languages) as well as additional resources or properties of the execution environment (rebindable resources; platform version in a cross-platform application). The recently introduced notion of coeffects captures the latter, whole-context properties, but it failed to capture fine-grained per-variable properties.We remedy this by developing a generalized coeffect system with annotations indexed by a coeffect shape. By instantiating a concrete shape, our system captures previously studied flat (whole-context) coeffects, but also structural (per-variable) coeffects, making coeffect analyses more useful. We show that the structural system enjoys desirable syntactic properties and we give a categorical semantics using extended notions of indexed comonad.The examples presented in this paper are based on analysis of established language features (liveness, linear logics, dataflow, dynamic scoping) and we argue that such context-aware properties will also be useful for future development of languages for increasingly heterogeneous and distributed platforms.
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 ...
Simply Typed Reverse-Mode Automatic Differentiation with Variants: Denotational Correctness via Idempotent Completion
Reverse-mode automatic differentiation can be derived denotationally as a structure-preserving interpretation of program syntax. In the usual simply typed model, each source type has one cotangent type. Variants break this representation because the valid cotangent space depends on the branch selected at run time; established correctness results therefore use primal-indexed families of cotangent spaces, whose direct internal language is dependent.
Functional programming with bananas, lenses, envelopes and barbed wire
We develop a calculus for lazy functional programming based on recursion operators associated with data type definitions. For these operators we derive various algebraic laws that are useful in deriving and manipulating programs. We shall show that all example functions in Bird and Wadler's “Introduction to Functional Programming” can be expressed using these operators.
Introduction - Tree-sitter
Tree-sitter is a parser generator tool and an incremental parsing library. It can build a concrete syntax tree for a source file and efficiently update the syntax tree as the source file is edited. Tree-sitter aims to be:
Tree-sitter - a new parsing system for programming tools - Strange Loop
Strange Loop is a conference for software developers covering programming langs, databases, distributed systems, security, machine learning, creativity, and more!
A theory of type polymorphism in programming
The aim of this work is largely a practical one. A widely employed style of programming, particularly in structure-processing languages which impose n…