1 of 68

Samantha Frohlich

1

The Monadic Profunctor Paradigm of Bidirectional Programming

2 of 68

2

The paradigm of monadic bidirectional programming or “monadic bx” is applicable in numerous domains: parsers/printers, pickling, lenses, generators/predicates, and logic programming. We shall focus on its new application in property based testing.

We will begin with a tale I like to call “There and Back Again Monadically”. It covers the dawn of this paradigm”: Li-yao et al’s “Composing Bidirectional Programs Monadically”, a paper which I joined at the start of my PhD to help extend into a journal version.

It turned out that I was not the only one building upon this work. Harry from the US was working on applying the work to generators of property based testing (PBT).

We joined forces to write “Reflecting on Random Generation”.

I’ll get you up to speed on PBT and his work “Free Generators”, then tell you all about Reflectives!

---

Time for intro = 1 min 25

Time so far = 1min 25s

3 of 68

The Monadic Profunctor Paradigm of Bidirectional Programming

Li-yao Xia, Samantha Frohlich, Dominic Orchard & Meng Wang

4 of 68

Bidirectional Programming

Bidirectional Transformation (BX) =

a piece of code that can be run in two directions and is expected to satisfy some round-tripping properties

Advantages: saves time, saves implementation effort, and avoids sync issues

There

Back again

Round tripping

5 of 68

Bidirectional Programming

Biparsers

parse

"1"

print

1

"1"

1

6 of 68

Profunctors

class Profunctor p where

lmap :: (d → c) → p c a → p d a

rmap :: (a → b) → p c a → p c b

rmap = post-comp (a → a')

lmap = pre-comp (b → b')

b -> a

contravariant

covariant

7 of 68

Monadic

Profunctors

data Biparser b a = Biparser

{ parse :: String → (a, String)

, print :: b → (a, String) }

newtype Parser a

= Parser (String -> [(a,String}])

print :: a -> String

newtype Reader a b

= Reader { runReader :: a -> b }

newtype Writer a b

= Writer { runWriter :: (a, b)

8 of 68

Monadic

Profunctors

data Biparser b a = Biparser

{ parse :: String → (a, String)

, print :: b → (a, String) }

Example

letter :: Biparser Char Char

number :: Biparser Int Int

data LorN = Letter Char | Number Int

lOrN :: Biparser LorN LorN

lOrN = (lmap ?l? . prune) letter >>=

\l → return (Letter l))

<|> (lmap ?n? . prune) number >>=

\n → return (Number n))

9 of 68

Monadic

Profunctors

data Biparser b a = Biparser

{ parse :: String → (a, String)

, print :: b → (a, String) }

Example

letter :: Biparser Char Char

number :: Biparser Int Int

data LorN = Letter Char | Number Int

lOrN :: Biparser LorN LorN

lOrN = (letter >>=

\l -> return (Letter l))

<|> (number >>=

\n -> return (Number n))

(>>=) :: BP LorN Int -> (Int -> BP LorN LorN) -> BP LorN LorN

lorN combines together letter and number to make a biparser for letters or numbers

It is written in two parts, combined together using using the alternative "or" construct, that’s the bar symbol

Each part is a monadic biparser built upon one of the sub-biparsers letter or number

So the number case, uses the number biparser, to get a number n, and then wraps that up with the Number constructor

Likewise with the letter case

For those familiar with monadic and alternative programming, this is the natural solution.

However, to get the bidirectional functionality, we are no longer programming just monads, we are programming PMPs, and this means we cant just use the monad interface, we also need the operations associated with partial profunctors

Let’s explore why we need the partial profunctor operations, starting with the profunctor ones and then going on to the partial ones.

The Profunctor operations are motivated by the fact that this term doesn't quite type check

And this is because bind only operates on the second type parameter.

So in this example, in the number case, bind expects its first argument (number) to have type BP LorN Int, but that is not the type of number!

We need a function that will change the first parameter of the profunctor

10 of 68

Monadic

Profunctors

data Biparser b a = Biparser

{ parse :: String → (a, String)

, print :: b → (a, String) }

Example

letter :: Biparser Char Char

number :: Biparser Int Int

data LorN = Letter Char | Number Int

lOrN :: Biparser LorN LorN

lOrN = (?l? letter >>=

\l -> return (Letter l))

<|> (?n? number >>=

\n -> return (Number n))

?l? :: Biparser Char Char -> Biparser LorN Char

?n? :: Biparser Int Int -> Biparser LorN Int

11 of 68

Monadic

Profunctors

data Biparser b a = Biparser

{ parse :: String → (a, String)

, print :: b → (a, String) }

Example

letter :: Biparser Char Char

number :: Biparser Int Int

data LorN = Letter Char | Number Int

lOrN :: Biparser LorN LorN

lOrN = (lmap ?l? letter >>=

\l -> return (Letter l))

<|> (lmap ?n? number >>=

\n -> return (Number n))

lmap :: (d -> c) -> p c a -> p d a

?l? :: LorN -> Char

?l? (Letter c) = c

?n? :: LorN -> Int

?n? (Number n) = n

Lmap can change the first type parameter, meaning that we can fix this type error in our example by applying lmap with a function from LorN->Char or LorN->Number to the letter or number sub-biparsers respectively

We call the functions given to lmap "backward annotations”

More generally, when programming with monadic profunctors,

These will appear on every recursive call

And will always be a projection function from the bigger structure (in this case LorN) to smaller contained one (in this case Int or Char)

This typically makes them straight forward to define, as you can see from our example annotations

It is worth remembering at this point that we do indeed need the both type params. We need profunctors with their co and contravariant type params to do the bidirectionality.

In the biparser example, this allows us to parse and print different things

You can think of the first parameter as our ultimate goal, and the second as an intermediary type, which needs to be changeable so that we can use bind and have a monadic interface

Now, lets motivate the partiality by considering what happens if

our L annotation gets a Number

Or what happens if the N annotation gets a Letter?

Currently, these functions cannot be total

This is why we use Partial Monadic Profunctors

12 of 68

Monadic

Profunctors

data Biparser b a = Biparser

{ parse :: String → (a, String)

, print :: b → (a, String) }

Example

letter :: Biparser Char Char

number :: Biparser Int Int

data LorN = Letter Char | Number Int

lOrN :: Biparser LorN LorN

lOrN = (lmap ?l? . prune) letter >>=

\l -> return (Letter l))

<|> (lmap ?n? . prune) number >>=

\n -> return (Number n))

prune :: p b a -> p (Maybe b) a

?l? :: LorN -> Maybe Char

?l? (Letter c) = Just c

?l? _ = Nothing

?n? :: LorN -> Maybe Int

?n? (Number n) = Just n

?n? _ = Nothing

13 of 68

14 of 68

14

15 of 68

Advantages of PBT:

More thorough
Shrinking

15

Background: PBT + Generators

-- property based testing:

prop xs = reverse (reverse xs) == xs

-- unit testing:

test1 = reverse (reverse []) == []

test2 = reverse (reverse [1]) == [1]

test3 = reverse (reverse [1..10]) == [1..10]

Random data generators are at the core of property based testing.

As opposed to unit testing, where code is tested using specific examples, property based testing tests properties that should hold for all values.

For example, if you wanted to ensure that reversing a list twice acted as the identity function,

instead of testing it on the specific examples of the empty list, a singleton list and a normal list

property based testing defines a property that is general over all lists this uses a generator to create lots of lists (xs) to test the prop against.

Property based testing is an excellent addition to your test suite because:

it will generate more examples than a tester ever would, and importantly random ones, which may find errors in places the tester did not expect�it will "shrink" values that violate the property to the smallest example that causes the error

This style of testing was popularised by Haskell's QuickCheck, which features its own language for generating values.

The cool thing about this generator language is that it can produce values that uphold some validity condition.

**Next Slide**

16 of 68

16

6

/ \

4 8

/ \ / \

2 5 7 9

. . .

bstProp :: BST -> Bool

bstProp bst = prop bst

mostlyVacuousProp :: Tree -> Bool

mostlyVacuousProp t = isBST t => prop t

BST

Background: PBT + Generators

17 of 68

17

Background: PBT + Generators

-- QuickCheck generator for BSTs:

bst :: (Int, Int) -> Gen Tree

bst (lo, hi) | lo > hi = return Leaf

bst (lo, hi) =

frequency

[ ( 1, return Leaf ),

( 5, do

x <- choose (lo, hi)

l <- bst (lo, x - 1)

r <- bst (x + 1, hi)

return (Node l x r) ) ]

A generator for BSTs in this language may look like this

QuickCheck generators are monadic, where you can consider the Gen monad as a function from Int -> Value where the Int is a random seed

This generator creates BST by taking the current value bounds as an argument.

When there is no value that could be placed at a node, it stops generating by returning a Leaf.

When it could place a value at the node, it uses the frequency start constructor to make a weighted choice between generating a leaf and a node, where a node is generated by using the choose combinator to generate the value, and recursing for the subtrees with updated value bounds. (the monadic do notation interface is used to compose together these sub-generations into the node)

The key thing to notice here: this generator bakes in the validity condition of what it means to be a BST: smaller values on the left, bigger one the right

So surely it can do more than just generate…

**Next Slide*

18 of 68

Bigenerators

gen

check

6

/ \

4 8

True

6

/ \

4 8

19 of 68

Student Research Competition

Harrison Goldstein

Benjamin C. Pierce

20 of 68

20

Free generators are a PBT tool that allows us to view a generator of random things as a parser.

Normally generators are just thought of as taking a bunch of random choices to create a value, but you could think about it as parsing those choices into a value.

Free Generators formalise this idea.

For example, let’s say that we wanted to test that inserting a value into a BST maintains its validity, so we create a generator of BSTs.

What free generators do is allow us to decompose our generator into two stages, instead of just pulling a value out of thin air:

we pull some random choices out of thin air

and then we make those choices

Free Generators are created using the Freer Monad, which is kind of like an abstract syntax tree of a monad program

(check familiarity with free monad, if none go to live demo)

On top of the monad operations, another operation called pick is added

This is either interpreted

as a random choice

or it's interpreted as parsing the first choice in a sequence

When you write a free generator, it looks just like a normal monatic generator

but now you can do some extra cool things with it

for example you can manipulate the random choices after you've made them but before you've parsed them which allows for some cool manipulation of values

21 of 68

Motivation: Internal Shrinking

Shrinking is useful.

We don’t want to manually shrink or write shrinkers.

MacIver and Donaldson [2020] show how to do shrinking with the help of a generator.

21

22 of 68

22

{

"name": "reflective-generators",

"description": "What a great project",

"scripts": {

"start": "node ./src/server.js",

"build": "babel ./src -out-dir ./dist",

"test": "mocha ./test"

},

…

}

NPM Package

Analyzer

23 of 68

23

{

"name": "reflective-generators",

"description": "What a great project",

"scripts": {

"start": "node ./src/server.js",

"build": "babel ./src -out-dir ./dist",

"test": "mocha ./test"

},

…

}

Oops, this breaks the code!

- Some User

24 of 68

24

{

"name": "reflective-generators",

"description": "What a great project",

"scripts": {

"start": "node ./src/server.js",

"build": "babel ./src -out-dir ./dist",

"test": "mocha ./test"

},

"repository": {

"type": "git",

"url": "https://example.com"

},

"keywords": [

"reflective",

"generators"

],

"author": "test",

"license": "mit",

"devDependencies": {

"babel-cli": "^6.24.1",

"babel-core": "^6.24.1",

"babel-preset-es2015": "^6.24.1"

},

"dependencies": {

"express": "^4.15.3",

"reflective": "^0.0.1"

}

25 of 68

25

{

"name": "reflective-generators",

"description": "What a great project",

"scripts": {

"start": "node ./src/server.js",

"build": "babel ./src -out-dir ./dist",

"test": "mocha ./test"

},

"repository": {

"type": "git",

"url": "https://example.com"

},

"keywords": [

"reflective",

"generators"

],

"author": "test",

"license": "mit",

"devDependencies": {

"babel-cli": "^6.24.1",

"babel-core": "^6.24.1",

"babel-preset-es2015": "^6.24.1"

},

"dependencies": {

"express": "^4.15.3",

"reflective": "^0.0.1"

}

26 of 68

26

{

"name": "a",

"description": "a",

"scripts": {

"start": "a",

"build": "a",

"test": "a"

},

"repository": {

"type": "a",

"url": "a"

},

"keywords": [],

"author": "a",

"license": "a",

"devDependencies": {},

"dependencies": {

"express": "^4.15.3"

}

{

"name": "reflective-generators",

"description": "What a great project",

"scripts": {

"start": "node ./src/server.js",

"build": "babel ./src -out-dir ./dist",

"test": "mocha ./test"

},

"repository": {

"type": "git",

"url": "https://example.com"

},

"keywords": [

"reflective",

"generators"

],

"author": "test",

"license": "mit",

"devDependencies": {

"babel-cli": "^6.24.1",

"babel-core": "^6.24.1",

"babel-preset-es2015": "^6.24.1"

},

"dependencies": {

"express": "^4.15.3",

"reflective": "^0.0.1"

}

27 of 68

27

{

"name": "a",

"description": "a",

"scripts": {

"start": "a",

"build": "a",

"test": "a"

},

"repository": {

"type": "a",

"url": "a"

},

"keywords": [],

"author": "a",

"license": "a",

"devDependencies": {},

"dependencies": {

"express": "^4.15.3"

}

{

"name": "reflective-generators",

"description": "What a great project",

"scripts": {

"start": "node ./src/server.js",

"build": "babel ./src -out-dir ./dist",

"test": "mocha ./test"

},

"repository": {

"type": "git",

"url": "https://example.com"

},

"keywords": [

"reflective",

"generators"

],

"author": "test",

"license": "mit",

"devDependencies": {

"babel-cli": "^6.24.1",

"babel-core": "^6.24.1",

"babel-preset-es2015": "^6.24.1"

},

"dependencies": {

"express": "^4.15.3",

"reflective": "^0.0.1"

}

28 of 68

28

{

"name": "a",

"description": "a",

"scripts": {

"start": "a",

"build": "a",

"test": "a"

},

"repository": {

"type": "a",

"url": "a"

},

"keywords": [],

"author": "a",

"license": "a",

"devDependencies": {},

"dependencies": {

"express": "^4.15.3"

}

{

"name": "reflective-generators",

"description": "What a great project",

"scripts": {

"start": "node ./src/server.js",

"build": "babel ./src -out-dir ./dist",

"test": "mocha ./test"

},

"repository": {

"type": "git",

"url": "https://example.com"

},

"keywords": [

"reflective",

"generators"

],

"author": "test",

"license": "mit",

"devDependencies": {

"babel-cli": "^6.24.1",

"babel-core": "^6.24.1",

"babel-preset-es2015": "^6.24.1"

},

"dependencies": {

"express": "^4.15.3",

"reflective": "^0.0.1"

}

29 of 68

29

{

"name": "a",

"description": "a",

"scripts": {

"start": "a",

"build": "a",

"test": "a"

},

…

"dependencies": {

"express": "^4.15.3"

}

{

"name": "reflective-generators",

"description": "What a great project",

"scripts": {

"start": "node ./src/server.js",

"build": "babel ./src -out-dir ./dist",

"test": "mocha ./test"

},

…

}

010010101010

100101011101

101101110111…

(Remember, generators are parsers!)

30 of 68

30

{

"name": "a",

"description": "a",

"scripts": {

"start": "a",

"build": "a",

"test": "a"

},

…

"dependencies": {

"express": "^4.15.3"

}

{

"name": "reflective-generators",

"description": "What a great project",

"scripts": {

"start": "node ./src/server.js",

"build": "babel ./src -out-dir ./dist",

"test": "mocha ./test"

},

…

}

010010101010

100101011101

101101110111…

101011011101…

Test-Case Reduction via Test-Case Generation

MacIver and Donaldson 2020

31 of 68

31

{

"name": "a",

"description": "a",

"scripts": {

"start": "a",

"build": "a",

"test": "a"

},

…

"dependencies": {

"express": "^4.15.3"

}

{

"name": "reflective-generators",

"description": "What a great project",

"scripts": {

"start": "node ./src/server.js",

"build": "babel ./src -out-dir ./dist",

"test": "mocha ./test"

},

…

}

010010101010

100101011101

101101110111…

101011011101…

32 of 68

32

{

"name": "a",

"description": "a",

"scripts": {

"start": "a",

"build": "a",

"test": "a"

},

…

"dependencies": {

"express": "^4.15.3"

}

{

"name": "reflective-generators",

"description": "What a great project",

"scripts": {

"start": "node ./src/server.js",

"build": "babel ./src -out-dir ./dist",

"test": "mocha ./test"

},

…

}

010010101010

100101011101

101101110111…

101011011101…

33 of 68

33

{

"name": "a",

"description": "a",

"scripts": {

"start": "a",

"build": "a",

"test": "a"

},

…

"dependencies": {

"express": "^4.15.3"

}

{

"name": "reflective-generators",

"description": "What a great project",

"scripts": {

"start": "node ./src/server.js",

"build": "babel ./src -out-dir ./dist",

"test": "mocha ./test"

},

…

}

010010101010

100101011101

101101110111…

101011011101…

34 of 68

Student Research Competition

Harrison Goldstein

Benjamin C. Pierce

35 of 68

35

data Pick a where

Pick :: [(Weight, Choice, Freer Pick a)] -> Pick a

-- return :: a → p b a

-- (>>=) :: p b a → (a → p b b) → p b b

-- lmap :: (d → c) → p c a → p d a

-- prune :: p b a → p (Maybe b) a

type FreeGen a = Freer Pick a

FreeGen.hs

36 of 68

36

-- lmap :: (d → c) → p c a → p d a

-- prune :: p b a → p (Maybe b) a

type FreeGen a = Freer Pick a

FreeGen.hs

data Pick a where

Pick :: [(Weight, Choice, Freer Pick a)] -> Pick a

37 of 68

37

data Pick b a where

Pick :: [(Weight, Choice, Freer (Pick b) a)] -> Pick b a

-- lmap :: (d → c) → p c a → p d a

-- prune :: p b a → p (Maybe b) a

type FreeGen a = Freer Pick a

FreeGen.hs

38 of 68

38

data Pick b a where

45

-- QuickCheck generator for BSTs:

bst :: (Int, Int) -> Reflective Tree Tree

bst (lo, hi) | lo > hi

= (lmap (\ a' -> if a==a' then Just a else Nothing) . prune)

(return Leaf)

bst (lo, hi) =

frequency

[ ( 1, TODO return Leaf ),

( 5, do

x <- TODO choose (lo, hi)

l <- TODO bst (lo, x - 1)

r <- TODO bst (x + 1, hi)

return (Node l x r) ) ]

BST.hs

46 of 68

46

-- QuickCheck generator for BSTs:

bst :: (Int, Int) -> Reflective Tree Tree

bst (lo, hi) | lo > hi = exact Leaf

bst (lo, hi) =

frequency

[ ( 1, exact Leaf ),

( 5, do

x <- TODO choose (lo, hi)

l <- TODO bst (lo, x - 1)

r <- TODO bst (x + 1, hi)

return (Node l x r) ) ]

BST.hs

47 of 68

47

-- QuickCheck generator for BSTs:

bst :: (Int, Int) -> Reflective Tree Tree

bst (lo, hi) | lo > hi = exact Leaf

bst (lo, hi) =

frequency

[ ( 1, exact Leaf ),

( 5, do

x <- TODO choose (lo, hi)

l <- TODO bst (lo, x - 1)

r <- TODO bst (x + 1, hi)

return (Node l x r) ) ]

BST.hs

48 of 68

48

-- QuickCheck generator for BSTs:

bst :: (Int, Int) -> Reflective Tree Tree

bst (lo, hi) | lo > hi = exact Leaf

bst (lo, hi) =

frequency

[ ( 1, exact Leaf ),

( 5, do

x <- (lmap (\Node _ n _ -> Just n) . prune) (choose (lo, hi))

l <- (lmap (\Node l' _ _ -> Just l) . prune) (bst (lo, x - 1))

r <- (lmap (\Node _ _ r' -> Just r) . prune) (bst (x + 1, hi))

return (Node l x r) ) ]

BST.hs

49 of 68

49

-- QuickCheck generator for BSTs:

bst :: (Int, Int) -> Reflective Tree Tree

bst (lo, hi) | lo > hi = exact Leaf

bst (lo, hi) =

frequency

[ ( 1, exact Leaf ),

( 5, do

x <- focus (_Node._2) (choose (lo, hi))

l <- focus (_Node._1) (bst (lo, x - 1))

r <- focus (_Node._3) (bst (x + 1, hi))

return (Node l x r) ) ]

BST.hs

50 of 68

50

GenInterp.hs

generate :: Reflective b a -> Gen a

generate = interp where

� interp (Return a) = return a

interp (Bind r f) = interpR r >>= interp . F

� interpR :: R b a -> Gen a

interpR (Pick gs) = QC.frequency [(w, interp g) | (w, _, g) <- rs]

interpR (Lmap _ r) = interpR r

interpR (Prune r) = interpR r

51 of 68

51

> QC.generate generate bst

(Node Leaf 1 Leaf)

> QC.generate generate bst

(Node (Node Leaf 5 Leaf) 6 Leaf)

> check bst ((Node Leaf 1 Leaf))

True

> check bst (Node (Node Leaf 6 Leaf) 5 Leaf)

False

52 of 68

52

53 of 68

53

{

"name": "a",

"description": "a",

"scripts": {

"start": "a",

"build": "a",

"test": "a"

},

…

"dependencies": {

"express": "^4.15.3"

}

{

"name": "reflective-generators",

"description": "What a great project",

"scripts": {

"start": "node ./src/server.js",

"build": "babel ./src -out-dir ./dist",

"test": "mocha ./test"

},

…

}

010010101010

100101011101

101101110111…

101011011101…

54 of 68

54

{

"name": "reflective-generators",

"description": "What a great project",

"scripts": {

"start": "node ./src/server.js",

"build": "babel ./src -out-dir ./dist",

"test": "mocha ./test"

},

"repository": {

"type": "git",

"url": "https://example.com"

},

"keywords": [

"reflective",

"generators"

],

"author": "test",

"license": "mit",

"devDependencies": {

"babel-cli": "^6.24.1",

"babel-core": "^6.24.1",

"babel-preset-es2015": "^6.24.1"

},

"dependencies": {

"express": "^4.15.3",

"reflective": "^0.0.1"

}

55 of 68

55

{

"name": "reflective-generators",

"description": "What a great project",

"scripts": {

"start": "node ./src/server.js",

"build": "babel ./src -out-dir ./dist",

"test": "mocha ./test"

},

"repository": {

"type": "git",

"url": "https://example.com"

},

"keywords": [

"reflective",

"generators"

],

"author": "test",

"license": "mit",

"devDependencies": {

"babel-cli": "^6.24.1",

"babel-core": "^6.24.1",

"babel-preset-es2015": "^6.24.1"

},

"dependencies": {

"express": "^4.15.3",

"reflective": "^0.0.1"

}

010010101010

100101011101

101101110111…

56 of 68

56

{

"name": "reflective-generators",

"description": "What a great project",

"scripts": {

"start": "node ./src/server.js",

"build": "babel ./src -out-dir ./dist",

"test": "mocha ./test"

},

"repository": {

"type": "git",

"url": "https://example.com"

},

"keywords": [

"reflective",

"generators"

],

"author": "test",

"license": "mit",

"devDependencies": {

"babel-cli": "^6.24.1",

"babel-core": "^6.24.1",

"babel-preset-es2015": "^6.24.1"

},

"dependencies": {

"express": "^4.15.3",

"reflective": "^0.0.1"

}

010010101010

100101011101

101101110111…

57 of 68

57

{

"name": "reflective-generators",

"description": "What a great project",

"scripts": {

"start": "node ./src/server.js",

"build": "babel ./src -out-dir ./dist",

"test": "mocha ./test"

},

"repository": {

"type": "git",

"url": "https://example.com"

},

"keywords": [

"reflective",

"generators"

],

"author": "test",

"license": "mit",

"devDependencies": {

"babel-cli": "^6.24.1",

"babel-core": "^6.24.1",

"babel-preset-es2015": "^6.24.1"

},

"dependencies": {

"express": "^4.15.3",

"reflective": "^0.0.1"

}

010010101010

100101011101

101101110111…

58 of 68

58

{

"name": "reflective-generators",

"description": "What a great project",

"scripts": {

"start": "node ./src/server.js",

"build": "babel ./src -out-dir ./dist",

"test": "mocha ./test"

},

"repository": {

"type": "git",

"url": "https://example.com"

},

"keywords": [

"reflective",

"generators"

],

"author": "test",

"license": "mit",

"devDependencies": {

"babel-cli": "^6.24.1",

"babel-core": "^6.24.1",

"babel-preset-es2015": "^6.24.1"

},

"dependencies": {

"express": "^4.15.3",

"reflective": "^0.0.1"

}

010010101010

100101011101

101101110111…

59 of 68

59

{

"name": "a",

"description": "a",

"scripts": {

"start": "a",

"build": "a",

"test": "a"

},

…

"dependencies": {

"express": "^4.15.3"

}

{

"name": "reflective-generators",

"description": "What a great project",

"scripts": {

"start": "node ./src/server.js",

"build": "babel ./src -out-dir ./dist",

"test": "mocha ./test"

},

…

}

010010101010

100101011101

101101110111…

101011011101…

60 of 68

60

{

"name": "a",

"description": "a",

"scripts": {

"start": "a",

"build": "a",

"test": "a"

},

…

"dependencies": {

"express": "^4.15.3"

}

{

"name": "reflective-generators",

"description": "What a great project",

"scripts": {

"start": "node ./src/server.js",

"build": "babel ./src -out-dir ./dist",

"test": "mocha ./test"

},

…

}

010010101010

100101011101

101101110111…

101011011101…

61 of 68

61

{

"name": "a",

"description": "a",

"scripts": {

"start": "a",

"build": "a",

"test": "a"

},

…

"dependencies": {

"express": "^4.15.3"

}

{

"name": "reflective-generators",

"description": "What a great project",

"scripts": {

"start": "node ./src/server.js",

"build": "babel ./src -out-dir ./dist",

"test": "mocha ./test"

},

…

}

010010101010

100101011101

101101110111…

101011011101…

62 of 68

62

{

"name": "reflective-generators",

"description": "What a great project",

"scripts": {

"start": "node ./src/server.js",

"build": "babel ./src -out-dir ./dist",

"test": "mocha ./test"

},

…

}

{ 01 => 12%,

10 => 9%,

… }

{

"name": "reflective-generators",

"description": "What a great project",

"scripts": {

"start": "node ./src/server.js",

"build": "babel ./src -out-dir ./dist",

"test": "mocha ./test"

},

…

}

Inputs from Hell: Learning Input Distributions for Grammar-Based Test Generation

Soremekun et al. 2020

63 of 68

63

> complete (bst (1,10)) (Node Leaf undefined Leaf)

Just (Node Leaf 8 Leaf)

�> parse (bst (1,10)) ["leaf","leaf","leaf"]

[(Leaf,["leaf","leaf"])]

��> unparse (bst (1,10)) (Node Leaf 4 Leaf)

Just ["node","4","leaf","leaf"]

��> QC.generate $ weighted (bst (1,4)) True (\case {"leaf" -> 100; "node" -> 0; _ -> 0})

Node (Node Leaf 1 Leaf) 2 (Node Leaf 3 (Node Leaf 4 Leaf))

> enum (bst (1,10))

[Leaf,Node Leaf 1 Leaf,Node Leaf 2 Leaf,...]

64 of 68

Student Research Competition

Harrison Goldstein

Benjamin C. Pierce

65 of 68

65

~demo~

66 of 68

66

The Monadic Profunctor Paradigm of Bidirectional Programming

67 of 68

Li-yao Xia, Dominic Orchard, and Meng Wang. 2019. Composing bidirectional programs monadically. In European Symposium on Programming. Springer, 147–175. https://doi.org/10.1007/978-3-030-17184-1_6

Harrison Goldstein and Benjamin C. Pierce. 2022. Parsing Randomness. Proceedings of the ACM on Programming Languages 6,OOPSLA2(Oct.2022),128:89–128:113. https://doi.org/10.1145/3563291

Harrison Goldstein, Samantha Frohlich, Meng Wang, and Benjamin C. Pierce. 2023. Reflecting on Random Generation. Proc. ACM Program. Lang. 7, ICFP, Article 200 (August 2023), 34 pages. https://doi.org/10.1145/3607842

Koen Claessen and John Hughes. 2000. QuickCheck: a lightweight tool for random testing of Haskell programs. In Proceedings of the Fifth ACM SIGPLAN International Conference on Functional Programming (ICFP ’00), Montreal, Canada, September 18 21,2000, Martin Odersky and Philip Wadler(Eds.). ACM, Montreal, Canada, 268–279. https://doi.org/10.1145/351240.351266

Oleg Kiselyov and Hiromi Ishii. 2015. Freer monads, more extensible effects. ACM SIGPLAN Notices 50, 12 (2015), 94–105. https://dl.acm.org/doi/10.1145/2804302.2804319 Publisher: ACM New York, NY, USA.

David R. MacIver and Alastair F. Donaldson. 2020. Test-Case Reduction via Test-Case Generation: Insights from the Hypothesis Reducer (Tool Insights Paper). In 34th European Conference on Object-Oriented Programming (ECOOP 2020) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 166), Robert Hirschfeld and Tobias Pape (Eds.). Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 13:1–13:27. https://doi.org/10.4230/LIPIcs.ECOOP.2020. 13 ISSN: 1868-8969.

Ezekiel Soremekun, Esteban Pavese, Nikolas Havrikov, Lars Grunske, and Andreas Zeller. 2020. Inputs from Hell: Learning Input Distributions for Grammar-Based Test Generation. IEEE Transactions on Software Engineering (2020). https://doi.org/10.1109/TSE.2020.3013716 Publisher: IEEE.

References

68 of 68

Round tripping

The Monadic Profunctor Paradigm of Bidirectional Programming

Li-yao Xia, Samantha Frohlich, Dominic Orchard & Meng Wang

Bidirectional Programming

Biparsers

Bigenerators

Partial Monadic Profunctors (PMPs)

Bidirectional Transformation (BX) = a piece of code that can be run in two directions and is expected to satisfy some round-tripping properties

Advantages: saves time, saves implementation effort, and avoids sync issues

There

Back again

parse

"1"

print

1

"1"

1

gen

check

1

True

1

data Biparser b a = Biparser

{ parse :: String → (a, String)

, print :: b → (a, String) }

class Profunctor p where

lmap :: (d → c) → p c a → p d a

rmap :: (a → b) → p c a → p c b

rmap = post-comp (a → a')

lmap = pre-comp (b → b')

b -> a

contravariant

covariant

Profunctors

PMP Biparser

Example

letter :: Biparser Char Char

number :: Biparser Int Int

data LorN = Letter Char | Number Int

lOrN :: Biparser LorN LorN

lOrN = (lmap ?l? . prune) letter >>=

\l → return (Letter l))

<|> (lmap ?n? . prune) number >>=

\n → return (Number n))

return :: a → p b a

(>>=) :: p b a → (a → p b b) → p b b

lmap :: (d → c) → p c a → p d a

rmap :: (a → b) → p c a → p c b

prune :: p b a → p (Maybe b) a

Operations