Lambda the Ultimate

In 2017, a team from Northeastern University released Turnstile, a framework for implementing propositionally typed languages in Racket; cf. naasking's story Type Systems as Macros. The system was really nice because it allowed type systems to be expressed in a manner similar to the way theoretical PL researchers would in a paper, and because it hooked into Racket's clean compiler backend.

Now Stephen Chang, one of that team, together with new coauthors Michael Ballantyne, Usamilo Turner and William Bowman, have released a rewrite that they call Turnstile+, together with a POPL article, Dependent Type Systems as Macros. From that article's introduction:

Turnstile+ represents a major research leap over its predecessor. Specifically, we solve the major challenges necessary to implement dependent types and their accompanying DSLs and extensions (which Turnstile could not support), while retaining the original abilities of Turnstile. For example, one considerable obstacle was the separation between the macro expansion phase and a program’s runtime phase. Since dependently typed languages may evaluate expressions while type checking, checking dependent types with macros requires new macrology design patterns and abstractions for interleaving expansion, type checking, and evaluation. The following summarizes our key innovations.

• Turnstile+ demands a radically different API for implementing a language’s types. It must be straightforward yet expressive enough to represent a range of constructs from base types, to binding forms like Π-types, to datatype definition forms for indexed inductive type families.
• Turnstile+ includes an API for defining type-level computation, which we dub normalization by macro expansion. A programmer writes a reduction rule using syntax resembling familiar on-paper notation, and Turnstile+ generates a macro definition that performs the reduction during macro expansion. This allows easily implementing modular type-level evaluation.
• Turnstile+’s new type API adds a generic type operation interface, enabling modular implementation of features such as error messages, pattern matching, and resugaring. This is particularly important for implementing tools like tactic systems that inspect intermediate type-checking steps and construct partial terms.
• Turnstile+’s core type checking infrastructure requires an overhaul, specifically with first-class type environments, in order to accommodate features like dependent binding structures of the shape[x:τ]...,i.e., telescopes [de Bruijn 1991; McBride 2000].
• Relatedly, Turnstile+’s inference-rule syntax is extended so that operations over telescopes, or premises with references to telescopes, operate as folds instead of as maps

The code is available at https://github.com/stchang/macrotypes.

Histogram: You have to know the past to understand the present by Tomas Petricek, University of Kent

Programs are created through a variety of interactions. A programmer might write some code, run it interactively to check whether it works, use copy and paste, apply a refactoring or choose an item from an auto-complete list. Programming research often forgets about these and represents programs as the resulting text. Consequently, thinking about such interactions is often out of scope. This essay shifts focus from programs to a more interesting question of programming.

We represent programs as lists of interactions such as triggering an auto-complete and choosing an option, declaring a value, introducing a variable or evaluating a piece of code. We explore a number of consequences of this way of thinking about programs. First, if we create functions by writing concrete code using a sample input and applying a refactoring, we do not lose the sample input and can use it later for debugging. Second, if we treat executing code interactively as an interaction and store the results, we can later use this information to give more precise suggestions in auto-complete. Third, by moving away from a textual representation, we can display the same program as text, but also in a view inspired by spreadsheets. Fourth, we can let programmers create programs by directly interacting with live previews as those interactions can be recorded and as a part of program history.

We discuss the key ideas through examples in a simple programming environment for data exploration. Our focus in this essay is more on principles than on providing fine tuned user experience. We keep our environment more explicit, especially when this reveals what is happening behind the scenes. We aim to show that seeing programs as lists of interactions is a powerful change of perspective that can help us build better programming systems with novel features that make programming easier and more accessible. The data exploration environment in this interactive essay may not yet be that, but it gives a glimpse of the future.

An enjoyable 25-minute introductory talk: YOW! Lambda Jam 2019 - Ken Scambler - Applied Category Theory (slides)

What do programming, quantum physics, chemistry, neuroscience, systems biology, natural language parsing, causality, network theory, game theory, dynamical systems and database theory have in common?

As functional programmers, we know how useful category theory can be for our work - or perhaps how abstruse and distant it can seem. What is less well known is that applying category theory to the real world is an exciting field of study that has really taken off in just the last few years. It turns out that we share something big with other fields and industries - we want to make big things out of little things without everything going to hell! The key is compositionality, the central idea of category theory.

Previously: Seven Sketches in Compositionality: An Invitation to Applied Category Theory.

(via Brian McKenna)

Tensor Considered Harmful, by Alexander Rush

TL;DR: Despite its ubiquity in deep learning, Tensor is broken. It forces bad habits such as exposing private dimensions, broadcasting based on absolute position, and keeping type information in documentation. This post presents a proof-of-concept of an alternative approach, named tensors, with named dimensions. This change eliminates the need for indexing, dim arguments, einsum- style unpacking, and documentation-based coding. The prototype PyTorch library accompanying this blog post is available as namedtensor.

Thanks to Edward Z. Yang for pointing me to this "Considered Harmful" position paper.

Seven Sketches in Compositionality: An Invitation to Applied Category Theory

2018 by Brendan Fong and David I. Spivak

Category theory is becoming a central hub for all of pure mathematics. It is unmatched in its ability to organize and layer abstractions, to find commonalities between structures of all sorts, and to facilitate communication between different mathematical communities. But it has also been branching out into science, informatics, and industry. We believe that it has the potential to be a major cohesive force in the world, building rigorous bridges between disparate worlds, both theoretical and practical. The motto at MIT is mens et manus, Latin for mind and hand. We believe that category theory—and pure math in general—has stayed in the realm of mind for too long; it is ripe to be brought to hand.

A very approachable but useful introduction to category theory. It avoids the Scylla and Charybdis of becoming incomprehensible after page 2 (as many academic texts do), and barely scratching the surface (as many popular texts do).

The transcript of Three Things I Wish I Knew When I Started Designing Languages, a talk given by Peter Alvaro somewhere or other, is up at Info Q.

Peter Alavaro's main research interest is in taming distributed systems. He starts his talk with the provocative thesis, "In the future, all radical new languages will be domain-specific languages." He talks of the evolution of his ideas about dealing with distributed systems:

1. Little interest by designers of programming-language designers in filling huge difficulty of debugging in context of distributed systems;
2. PLs often make handling of data somewhat implicit, even with functional programming, which he says is dangerous in distributed programming;
3. To talk about the flow of data properly, we need to talk about time;
4. Two things that influenced him as a grad student: Jeff Ullman's claim that encapsulation and declarativity are in tension, and Fagin's theorem (the existential fragment of second-order logic characterises NP);
5. Idea that distributed systems can be considered as protocols specified a bit like SQL or Datalog queries;
6. Triviality with query languages of characterising the idea of place in distributive systems: they are just another relation parameter;
7. Describing evolution of a system in time can be done with two other things: counters and negation, leading to Bertram Ludäscher's language Statelog. But this way of doing things leads to the kind of low-level overexpressive modelling he was trying to avoid;
8. "What is it about...protocols that they seem to require negation to express?” Turns out that if you drop negation, you characterise the protocols that deliver messages deterministically.

He summarises by saying the only good reason to design a programming language (I assume he means a radically novel language) is to shape your understanding of the problem. No regrets of being the only user of his first language, Datalist, because the point is that it shaped all his later thought in his research.

From Andrey Mokhov's twitter feed:

Is there any intermediate abstraction between applicative functors and monads? And if yes, what is it? In a new paper with @geo2A, @simonmar and @dimenix we explore "selective functors", which are essentially applicative functors with branching: https://www.staff.ncl.ac.uk/andrey.mokhov/selective-functors.pdf

We've implemented selective functors in Haskell: https://github.com/snowleopard/selective, OCaml: https://github.com/snowleopard/selective-ocaml, and even Coq: https://github.com/tuura/selective-theory-coq (the Coq repository contains some proofs of correctness that our selective instances are lawful). And there is also a PureScript fork!

A new introductory book about dependent types, involving some familiar names:

The Little Typer

by Daniel P. Friedman and David Thrane Christiansen.

Foreword by Robert Harper.

Afterword by Conor McBride.

An introduction to dependent types, demonstrating the most beautiful aspects, one step at a time.

A program's type describes its behavior. Dependent types are a first-class part of a language, and are much more powerful than other kinds of types; using just one language for types and programs allows program descriptions to be as powerful as the programs they describe. The Little Typer explains dependent types, beginning with a very small language that looks very much like Scheme and extending it to cover both programming with dependent types and using dependent types for mathematical reasoning. Readers should be familiar with the basics of a Lisp-like programming language, as presented in the first four chapters of The Little Schemer.

The first five chapters of The Little Typer provide the needed tools to understand dependent types; the remaining chapters use these tools to build a bridge between mathematics and programming. Readers will learn that tools they know from programming—pairs, lists, functions, and recursion—can also capture patterns of reasoning. The Little Typer does not attempt to teach either practical programming skills or a fully rigorous approach to types. Instead, it demonstrates the most beautiful aspects as simply as possible, one step at a time.

Jules Hedges has written a thought-provoking blog post, On compositionality where he connects the familiar idea of compositionality to the idea of emergent effects in nature, where systems can be understood as either having compositional properties or emergent properties.

The key point about emergent systems is that they are hard to understand, and this is as true for engineering as it is for science. He goes on to say "As a final thought, I claim that compositionality is extremely delicate, and that it is so powerful that it is worth going to extreme lengths to achieve it", so that avoiding emergent effects is a characteristic of good programming language design.

Some thoughts:

1. His examples of emergent systems are biology and game theory from an economic perspective. I would add to this list physics: of his co-authored paper showing that the spectral gap is undecidable, David Pérez-García said "For example, our results show that adding even a single particle to a lump of matter, however large, could in principle dramatically change its properties."
2. Spolsky's famous characterisation of interfaces built on shaky foundations as Leaky abstractions to me makes the distinction between compositional and emergent systems a little less than sharp.
3. We could talk endlessly about the list of what he regards as compositionality-breaking features of PLs. The evils of global state are well-documented, but I find dmbarbour's argument that Local state is poison a very interesting alternative way to look at what properties do we want from code; more generally, what kind of compositionalty PLs offer is very much paradigm dependent. Gotos are considered harmful, but the Linux kernel has little trouble with longjmp because of its mandated coding style: compositionality in engineering is a not just a matter of semantics but also of use. He targets OO and Haskell's type classes - I think he is quite correct - note that within these paradigms one can regain compositionality by restricting to LSP or algebraic classes, and supporting his thesis we see that these ideas have spawned ideas for the design of new, cleaner PLs.

History of Lisp (The history of LISP according to McCarthy's memory in 1978, presented at the ACM SIGPLAN History of Programming Languages Conference.)

This is such a fun paper which I couldn't find on LtU. It's about the very early history of programming (1950s and '60s), back when things we take for granted today didn't exist yet.

On taking apart complex data structures with functions like CAR and CDR:

It was immediately apparent that arbitrary subexpressions of symbolic expressions could be obtained by composing the functions that extract immediate subexpressions, and this seemed reason enough to go to an algebraic language.

On creating new data, i.e. CONS:

At some point a cons(a,d,p,t) was defined, but it was regarded as a subroutine and not as a function with a value. ... Gelernter and Gerberich noticed that cons should be a function, not just a subroutine, and that its value should be the location of the word that had been taken from the free storage list. This permitted new expressions to be constructed out of subsubexpressions by composing occurrences of cons

On inventing IF:

This led to the invention of the true conditional expression which evaluates only one of N1 and N2 according to whether M is true or false and to a desire for a programming language that would allow its use.

On how supreme laziness led to the invention of garbage collection:

Once we decided on garbage collection, its actual implementation could be postponed, because only toy examples were being done.

You might have heard this before:

S.R. Russell noticed that eval could serve as an interpreter for LISP, promptly hand coded it, and we now had a programming language with an interpreter.

And the rest is history...