James - Algebraic Refactoring

Question 1

Meanwhile, when you are choosing the best implementation of a design, you are picking from a space of possible programs that all do the same thing. Where do these possibilities come from?

Answer 1

They come from simple rules for turning one program into an equivalent one. And the best part is you learned most of them in high school.

Question 2

When you are choosing the best implementation of a design, you are picking from a space of possible programs that all do the same thing. Where do these possibilities come from?

Answer 2

They come from simple rules for turning one program into an equivalent one.

Question 3

We can roughly split software design into three levels, what are these?

Answer 3

Design -> At a high level, what should it do -> A spec saying that I need a positive integer

Behavior -> At a low level -> what does it do -> A low-level spec saying it returns the number five

Implementation -> How does it do it? -> Choosing from possible implementations how the low-level spec should be met.

Question 4

What is a reduction?

Answer 4

Is a single step of computation

1 + 5 -> 6
69 -> 54
(1+5)(72) -> 6(72)
(1+5)(72) -> (1+5)9

For refactoring, we allow reduction in different orders and that gives us a graph of all the ways we can reduce an expression.

        (1+5)*(7*2)  6*(7*2)                  (1+5)*9
             6*9
             54

Since we can reduce in any order, we can also go backward and unreduce expressions.
(1+5)(72) -> (1+10/2)(72)

Reducing and unreducing give us an infinite space of possible expressions that all give us the same answer.

Question 5

What is equivalence?

Answer 5

If A can be rewritten to B by a series of reductions and backwards reductions, then A and B are equivalent.

Question 6

What is a substitution?

Answer 6

In an expression with variables, we can substitute all instances of the same variable for a value.

1/z
x^2 + xy + 1

Question 7

What is equality?

Answer 7

You can say that a + b = b + a, because no matter what concrete values I choose for a and b they reduce to the same result. In a sense, we can derive equality from equivalence.

Question 8

What ability equality give us?

Answer 8

We can use substitution and unsubstitution along with reduction and unreduction to explore the infinite space of all possible expressions that give us the same answer.

unsubstitution is the beginning of an add parameter refactoring and also a case of the extract method refactoring.

1+sqrt((x1-x2)(x1-x2)+(y1-y2)(y1-y2)))

1+[x1-x2/x, y1-y2/y]sqrt(xx+yy)
1+(fn (x, y) -> sqrt(xx+yy) (x1-x2, y1-y2))
1+(fn (x, y) -> sqrt(xx+yy*))/mag

mag = (x, y) -> sqrt(xx+yy*)
1+mag (x1-x2, y1-y2)

Question 9

What are the three fundamental constructs for data structures?

Answer 9

Products, Sums and Exponentials

Question 10

What is a product?

Answer 10

|A x B| = |A| * |B|

Product is an and.

C structs, python tuples, python dictionaries are products. They only differ in how their elements are indexed. Classes are also like structs.

Question 11

What are the laws associated with products?

Answer 11

We have commutativity (you can reorder):
A x B = B x A

We have associativity:
(A x B) x C = A x (B x C)

((1, 2), 3) = (1, (2, 3))

class Employee 
    int id
class Engineer extends Employee
    String name
    int deskno

is equivalent to

class Employee 
    int id
    String name
class Engineer extends Employee
    int deskno

Question 12

What is a Sum?

Answer 12

Sum is an OR.

Sum = Left | Right
case sum of
Left -> do something
Right -> do otherstuf

In C we have unions, in Java we can use subclasses, in Python everything is a sum because of dynamic typing.

Question 13

Does Int + Int = Int?

Answer 13

No, because in a Sum we have knowledge of which value is each, it can be either the first one or the second one.

Int + Int = Int * 2 = Int * Bool

Question 14

What is the unit type?

Answer 14

Its the type that only contains one thing.
In C/Java is called void. If we have a void function, is not that it never returns, it just doesn’t return anything interesting, like returning the same thing everytime.
Or enum Unit { UNIT } is also a unit in C.

Question 15

What is a boolean?

Answer 15

bool = 1 + 1 = 2

It’s either the left of nothing interesting (unit type) or it’s right of nothing interesting.

boolean is also called two, it’s the type with two values. And is equivalent to any other type with two values.

Question 16

How would you express a nullable object in Java?

Answer 16

Nullable object = 1 + (Non Nullable Object)

It’s a non nullable thing or nothing and you know which one is each.

Question 17

Which law is this?

datatype Animal
= Dog String Breed
| Cat String int

To

datatype Animal =
Animal String OtherInf

datatype OtherInf
= DogInf Breed
| CatInf int

Answer 17

Distributive law

Question 18

What are exponentials?

Answer 18

A function that assigns 10 people to 3 colors can have 3^10 possible results.
So a function from People -> Color codifies Color^People functions.

Because of that functions are exponentials.
A->B codifies B^A functions
B^A is how many functions there are.

Question 19

Use exponential laws to refactor this code:

public int addTimeOrTemp(int x, boolean isTime)

Answer 19

(1)
int addTimeOrTemp(int x, boolean isTime) == int^(int * 2)
(2)
datatype TimeOrTemp = Time int | Temp int
int addTimeOrTemp(TimeOrTemp x) == int^(int + int)
(3)
int addTimeOrTemp(int x)
int addTimeOrTemp(int x)
== int^int * int^int

Question 20

List each fundamental data structure constructors and destructors.

Answer 20

Constructor | Destructor
(1, 2) | x, y = foo
inl 42 | case foo of
Left x => x + 1
Right y => len(y)
(x,y) -> (x+y) | foo(1, 2, 3)

Question 21

Why the datastructures we choose have inescapable consequences in the shape of our code?

Answer 21

Every value is useless unless destructed.

Implications:

• Every sum type will be cased over (Nullable objects)
• Every boolean will be used in an if/else
• Every recursive type will be recursed over
• Every list will be mapped over
• In Python, if a variable can be of multiple types, you will need to case over it

The shape of your code follows the shape of your data. That is another instance of the data over code principle.

Question 22

What is defunctionalizations and refunctionalization?

Answer 22

Defunctionalization occurs when we exchange a high order function to a sum type like an enum.
Refunctionalization occurs when we exchange a sum type to a high order function.
It’s an instance of the open closed principle when we replace cases with function calls.
Another example would be putting either a function or a message in a queue to be processed latter.

The defunctionalized version is more inspectable, we can print it, send it over the wire.
The refunctionalized version is more open, it is easier to add new alternatives.

For more read: https://en.wikipedia.org/wiki/Defunctionalization

Question 23

Refactor:

def intersect((low1, hi1), (low2, hi2)):
  if low1 > low2:
    if hi1 < hi2:
      return (low1, hi1)
    else:
      return (low1, hi2)
  else:
    if hi1 < hi2:
      return (low2, hi1)
    else:
      return (low2, hi2)

Answer 23

AC+AD+BC+BD=(A+B)(C+D)

def intersect((low1, hi1), (low2, hi2)):
  return (max(low1, low2), min(hi1, hi2))

Question 24

Just like in the algebra of numbers, a law will assert the equality of two objects - in our case, the objects will be types. What does it mean for two objects to be equal in the algebra of types?

Answer 24

When two types a and b are equal, you could write two functions:

from :: a -> b
to :: b -> a

that pair up values of a with values of b, so that the following equations always hold (here the == is genuine, Haskell-flavored equality):

to (from a) == a
from (to b) == b

For example, I contend that the types Bool and Add () () are equivalent. I can demonstrate the equivalence with the following functions:

to :: Bool -> Add () ()
to False = AddL ()
to True = AddR ()

from :: Add () () -> Bool
from (AddL _) = False
from (AddR _) = True

Question 25

Just like in the algebra of numbers, a law will assert the equality of two objects - in our case, the objects will be types. What does it mean for two objects to be equal in the algebra of types?

Answer 25

When two types a and b are equal, you could write two functions:

from :: a -> b
to :: b -> a

that pair up values of a with values of b, so that the following equations always hold (here the == is genuine, Haskell-flavored equality):

to (from a) == a
from (to b) == b

For example, I contend that the types Bool and Add () () are equivalent. I can demonstrate the equivalence with the following functions:

to :: Bool -> Add () ()
to False = AddL ()
to True = AddR ()

from :: Add () () -> Bool
from (AddL _) = False
from (AddR _) = True

Question 26

List simple laws for sum types

Answer 26

there are as many values of type Add Void a as there are of type a
Add Void a === a

it doesn’t matter which order you add things in
Add a b === Add b a

In math:

0+x=x
x+y=y+x

Question 27

List simple laws for product types

Answer 27

if you multiply anything by Void, you get Void back
Mul Void a === Void

if you multiply by () you don’t change anything
Mul () a === a

it doesn’t matter which order you multiply in
Mul a b === Mul b a

distributive law
Mul a (Add b c) === Add (Mul a b) (Mul a c)

in math:
0⋅x=0
1⋅x=x
x⋅y=y⋅x
a⋅(b+c)=a⋅b+a⋅c

Question 28

List all functions Bool -> Bool

Answer 28

f1 :: Bool -> Bool – equivalent to ‘id’
f1 True = True
f1 False = False

f2 :: Bool -> Bool – equivalent to ‘const False’
f2 _ = False

f3 :: Bool -> Bool – equivalent to ‘const True’
f3 _ = True

f4 :: Bool -> Bool – equivalent to ‘not’
f4 True = False
f4 False = True

That’s why when we have a function a->b, b^a enumerates literaly all possible functions.

Question 29

List simple laws for exponentials types

Answer 29

there are as many functions () -> a as there are values of type a:
() -> a === a

there is only one function a -> () – in particular, it is const ():
a -> () === ()

factoring out of common arguments:
(a -> b, a -> c) === a -> (b,c)

we can curry and uncurry functions:
a -> (b -> c) === (b,a) -> c
or:
a -> b -> c === (a,b) -> c

In math:
a^1=a
1^a=1
b^a⋅c^a = (bc)^a
(c^b)^a=c^(b⋅a)