First pass over introduction

[tpetricek]

Plan of introduction/overview

Introduction

Identifying the problem

• visualisations central to communicating science and public policy, but easy to misuse/misinterpret
• can improve this by making them more explorable – usually done through brushing & linking (and lots of viz frameworks support this: altair, vincent, bqplot, shiny, plotly, Glue)
• but there are various problems with this – automated linking usually only possible for visualisations provided by the library, or where the user specifies explicitly how things are to be linked
• can we solve this problem using PLT, so that programmer just writes purely functional visualisation code, and the infrastructure does the linking? this would make linking pervasive, automatic, and mathematically robust

Towards a solution: Galois slicing for linking visualisations

• the above requirements suggest that dependency analysis may be able to help
• Galois slicing in particular is a technique which lends itself to the bidirectional aspect of the problem
• namely: when two charts are “cognate” (depend on common data), we can link them by slicing backwards from one chart to identify the needed data, and then forward to see the parts of the other chart that depend on that data

  Problems with existing approaches (1)

• however, prior work on Galois slicing considers a slice to be a “partial term” or context (term with holes) – which isn’t a suitable notion of selection – one cannot formulation the question “what is needed for Y?” where Y focuses on an arbitrary part of the output
• prior work does propose differential slicing as a notion of selection, but this underapproximates the required dependency information
  • idea of differential slicing is to “focus” on a subtree v, compare the slice with respect to the “spine” which picks out v, and the slice with respect to that same spine with v included
  • if any of the input needed for v is also needed to compute the spine, this won’t show up in the differential slice (simple example with let/pair)
• to avoid this problem we will formalise the notion of selecting elements of interest directly in the Galois framework

  Problems with existing approaches (2)

• we also need to be able to ask a different but related kind of question: “what depends on X?”

Overview/motiving example(s)

• we will break down our problem of linking cognate visualisations into two subproblems: (a) what data does some part of V1 depend on, and (b) what parts of V2 depend on that data?
• problem (a) can be illustrated by considering a familiar example: matrix convolution
  • when we select an output cell, we can see what input cells and kernel cells were needed
  • there is an implicit dual to this question: what parts of V2 depend only on some data? i.e., what parts of V2 is that data sufficient for?
  • these questions (“what resources are needed for Y?” and “what can we do given resources X?”) are dual (adjoint)
• problem (b) is distinct from problem (a) but also from its dual, and can also be illustrated using matrix convolution
  • when we select an input cell X, we can see what output cells needed it (in general X may not be sufficient for any cells, but there may be many cells which need it)
  • we can formulate this problem by flipping the polarity of (negating) the input, so that we have all resources apart from X; anything we can no longer compute must depend on X
  • in turn, the negation of this (the output) is exactly the things that depend on X

---

Some to dos:

• [x] (@rolyp) abstract
  • [x] alternative to “slicing” terminology (e.g. Galois dataflow, Galois data dependency, Galois provenance..)
• [x] (@tpetricek, @rolyp) initial plan for intro/overview (see notes in comments below)
  • example: matrix convolution (some nice lecture notes on convolutions and kernels)
  • [x] example: brushing-and-linking

[rolyp]

Possible related work from Levi:

• altair, vincent
• bqplot - Python/JS linking and brushing (conference 2017)
• shiny, plotly

[rolyp]

Tomas’ original notes (more focused around “vis paper based on PL techniques”, rather than “PL paper with viz application”):

Introduction

Making visualizations more explorable Done through brushing & linking
Lots of work on specific implementations
We have general mechanism based on PLT
This means you just write code and we do linking

Motivating example

Consider case where we want two charts showing two aggregations
In Python, I load data, do some Pandas aggregation, build charts
This does not give me linking! We do not know how the charts relate!
I have to use Bokeh, but then I also have to rewrite how I aggregate
Then you’re also restricted in what you can do
This is stupid, we should not have to do this.

Background

Problem overview

More details about brushing and linking

Related dataviz work

Seminal work on the topic from long time ago
Some more recent work in the space
The problem is they’re hard coded and not flexible

Related PL work

We will use ideas from program slicing
Some concrete work in this space

Overview of our system

We implement brushing and linking
We get that for free based on the underlying mechanism
Including the diagram with two viz

Evaluation of our system

Discuss the example here
Interoperability with other systems, e.g. D3/Vega, and languages:

• intended primarily as a proof-of-concept, which could be implemented for libraries like D3
• with complex pipelines involving multiple languages/libraries, we can support some part of the pipeline only
• we can specify an API that third parties could implement (for a given library/language) in order to interoperate with our approach

[tpetricek]

Possible paper structure

Introduction

• On the one hand, PLT has been doing cool work on explaining what programs do
  • Some examples like taint tracking, previous slicing work
  • This has limitations - works on small languages, solves ad-hoc one-off problems
• On the other hand, data viz community has been trying to build libraries doing this
  • Some examples like Altair, something on convolution?
  • This has limitations - library specific and not very expressive
• Example bringing these two together - maybe linking?
  • Imagine you have this code, wouldn't it be nice if you could automatically see....
  • We do exactly this!
  • PLT people cannot do this, because (they did not have this negation trick?)
  • VIZ people cannot do this, at least not when using normal langauge to write their code
• We develop a new slicing framework that:
  • Can handle rich programming languages
  • Can be applied in different ways to implement different kinds of explanations
  • Has nice theoretical foundations
• TODO: Maybe have matrix convolution example here already?

Background

• Visualization work
• Work on explanation in PLT

Theory

• Core theory explained here

Applications

• Convolution (this is just propagating back)
  • Actually explain how this works
• Linking (propagating back, negating, propagating forward)
  • How we do the negation here
• Third thing (propagating back, then forward) - TODO: Figure out what this means

Full language

• Overview how desugaring looks, with details in appendix
• This is tricky to get right. For example, consider these one or two cases
• We did get it right. Here is a theorem (with proof in the appendix)

---

Issues

• Do not talk about "explainability", but about "data dependencies" (or something else, like "transparency")
• How to introduce this? (1) Hey, there is some cool PLT, here is how it can be used... or (2) There is this dataviz problem, look what we can do.