• Strange Loop
• Coursera
• Compose Conference

• Point-Free or Die: Tacit programming in Haskell and Beyond
• Idealized Commit Logs - Alan Shreve
• An Introduction to Combinator Compilers and Graph Reduction Machines

Youtube - “Point-Free or Die: Tacit Programming in Haskell and Beyond” by Amar Shah

Point-free style is a tool for tacitness, and tacitness is a tool for comunication

• Calibrate abstraction
• Be more expressive

outside . inside is a composition.

totalNumber = sum . map length

Think in a general way when programming. wholemeal programming.

totalnumber = aggregate length
  where aggregate f = sum . map f

Remove arguments with eta-reduction

aggregate f = sum . map f
aggregate f = (.) sum (map f) -- Infix change
aggregate f = (.) sum $ map f
aggregate f = (.) sum . map $ f -- As a composition
aggregate   = \f -> (.) sum . map $ f -- Annonymous function
aggregate   = (.) sum . map
aggregate   = (sum .) . map

\f g -> (f .) . g
\f g x y -> f (g x y) -- eta reduced

A combinator is a lambda expression that refers only to its arguments

Book: “To Mock a Mockingbird - and other logic puzzles including an amazing adventure in combinatory logic” - Raymon Smullyan PDF

Blackbird is the composition of composition and composition.

1. Learn eta-reduction to calibrate tacitness
2. Learn combinators to find elegant expressions

Tacit code isn’t better unless it comunicates better.

Youtube - “Idealized Commit Logs: Code Simplification via Program Slicing” by Alan Shreve

Code is read much more often than it is written - Raymon Chen

How to understand software:

• Documentation
• Debugger
• Print logs
• White boarding boxes + lines

An expert computer programmer encodes and processes information semantically, ignoring programming language systanctix details - Weiser, 1982

• Small programs are easy to read and amenable to understand.
• Can we reduce a program into a samller, easier-to-read equivalent program?

Algorithm:

1. Write a test case
2. Run a code coverage report
3. Prune all statements not marked by coverage
4. Clean up the AST
5. Write the code back out

Properties:

1. It compiles.
2. Is passes the test case(s) used to compute it.

• Described in 1979 by Mark Weiser
• Diferent types of slices:
  • Forward Slicing
  • Dynamic slicing
  • Thin slicing
  • Observational slicing

Existing Tools

• Indus
• Giri
• Wala
• Frama-C plugin
• JSlice
• CodeSurfer

Going from the core structure to a more rich structure with aditional features.

Algorithm:

• Run code coverage for all test cases in a project
• Heuristically choose a best ordering of test cases
• Then iteratively for each test:
  • Create Slice from Test0..TestN
  • Create Slice from Test0..TestN+1
  • diff these slices

• We need more tools to aid reading/undestanding code
• Program Slicing can be an effective tool
  • Reduce large programs into smaller conceptual pieces
  • Practical Dynamig Slicing by leveragin code-coverage tools
  • Language independent algorithm
  • Idealized commit log for iterative mental model building

Youtube - “An Introduction to Combinator Compilers and Graph Reduction Machines” by David Graunke

@graunked

Origins and motivation of Functional Programming.

Graph Reduction Machine

A virtual machine for functional laguages that works by repeatedly modifying a graph data structure in place.

Combinator Compiler

A compiler that rewrites functional programs into a version that only uses a reduced set of functions.

Abstract virtual machine. Rather than a vector of instructions, is a graph of instructions, representing a data structure.

Graph reduction is model for VM’s that’s close to the semantics of our high-level language. Using lazy evaluation, currying and pure functions.

Computing by Rewriting

Evaluate the body of the procedure with each formal parameter replaced by the corresponding argument.

(λ x. e)y ⟶ e[x:=y]

total = sum [1 5 0 5]
total = + 1 (sum [5 0 5])
total = + 1 (+ 5 (sum [0 5])

First thing to do in a graph reduction is replace bindings with pointers.

foldr op a = f
  where f nil = a
        f x:xs = op x (f xs)
sum = foldr + 0
total = sum [1 5 0 5]

Then we replace the body.

sum = f
  where f nil = 0
        f x:xs = + x (f xs)

And then again with total = + 1 ( sum [5 0 5])

As we work with rewriting itself and with lazy evaluation, we don’t twice the work. Referential Transparency

A point-free expression is using combinators to define a function without specifying bound variables. A Combinator is a function without free varialbes that takes functions as argument and returns a function.

f x y = x - y
reversed_f = flip f

With this combinators, you can define any program:

S f g x = (f x) (g x)
K x y   = x
I x     = x

double x = + x x
double = (S +) I

S + I 5      -- S f g x = (f x) (g x)
(+ 5) (I 5)  -- I x = x
+ 5 5

This can be done with any function in lambda calculus.

Mapping to Stick Hardware

Using FPGA to run functional code, because in stock hardware it doesn’t perform very well.

• Reduceron
• Closure Reduction

Papers:

• “A New Implementation Technique for Applicative Languages,” David Turner, 1979
• Hudak on the state of FP in 1989: “The Conception, Evolution, and Application of Functional Programming Languages,”
• Reduceron Paper, 2008, Matthew Naylor and Colin Runciman
• “Towards a GPU-based implementation of interaction nets”
• “Implementing Functional Languages on Stock Hardware”, Simon Peyton-Jones, 1992

• Functional Program Design in Scala

• Week 1 - For expressions and Monads

• Lecture 1.1 - Queries with for
• Lecture 1.2 - Translation of For

• Interable
  • Seq
    • IndexedSeq

• Vector
  • LinearSeq
• List
  • Set
  • Map

map
flatmap
filter

foldLeft
foldRight

• Idealized implementation of map on Lists

abstract class List[+T] {
  
  def map[U](f: T => U): List[U] = this match {
    case x :: xs => f(x) :: xs.map(f)
    case Nil => Nil
  }
}

• Idealized Implementation of flatMap on Lists

abstract class List[+T] {

  def flatMap[U](f: T => List[U]): List[U] = this match {
    case x :: xs => f(x) ++ xs.flatMap(f)
    case Nil => Nil
  }
}

• Idealized Implementation of `filter` on Lists

 abstract class List[+T] {

   def filter(p: T => Boolean): List[T] = this match {
     case x :: xs =>
	 if (p(x)) x :: xs.filter(p) else xs.filter(p)
     case Nil => Nil
   }
 }

In practice, the implementation and type of these methods are different in order to:

• make them apply to arbitrary collections, not just lists.
• make them tail-recursive on lists.

Simplify combinations of core methods map, flatmap, filter

for {
  i <- 1 until n
  j <- 1 until i
  if isPrime (i + j)
} yield (i,j)

The Scala compiler translates for-expressions in terms of map, flatmap, filter.

for (x <- e1) yield e2  //for-expression
e1.map(x => e2)         //Translated

for (x <- e1 if f; s) yield e2  // f is a filter and s is a sequence of generators
for (x <- e1.withFilter(x => f); s) yield e2

for (x <- e1; y <- e2; s) yield e3
e1.flatMap(x => for (y <- e2; s) yield e3)

for (b <- books; a <- b.authos if a startsWith "Bird,")
yield b.title

{ for {
    b1 <- books
    b2 <- books
    if b1.title < b2.title
    a1 <- b1.authors
    a2 <- b2.authors
    if a1 == a2
  } yield a1
}.distinct

Scala compiler will translate for expressions to combinations of map, flatMap, and a lazy variant of filter.

for (x <- e1) yield e2
e1.map(x => e2)

for (x <- e1 if f; s) yield e2
for (x <- e1.withFilter(x => f); s) yield e2

for (x <- e1; y <- e2; s) yield e3
e1.flatMap(x => for (y <- e2; s) yield e3) //Translation continues

Now we want to transform this expression:

for (b <- books; a <- b.authors if a startsWith "Bird")
yield b.title

• Trasnformation 1

books.flatMap(b => 
  for (a <- b.authors if a startsWith "Bird")
) yield b.title

• Transformation 2

books.flatMap(b => 
  for (a <- b.authors.withFilter(a => a startsWith "Bird"))
) yield b.title

• Transformation 3

books.flatMap(b =>
  b.authors.withFilter(a => a startsWith "Bird").map(y => y.title)
)

This transformation is not limited to lists of sequences, or even collections. It is based solely on the presence of the methods map, flatMap and withFiler. This lets you use the for syntax for your own types as well, with only defining map, flatMap and withFiler for these types.

Useful for arrays, iterators, databases…

• Practical Programming in an Exception Free World

Youtube - Sharon Holliday - Practical Programming in an Exception Free World

Sharon’s universal code metri: How many coffee per LOC?

Exceptions break referential transparency. But this is not useful in real world.

def findMaxAge(ages: Vector[Int]):String = {
  s"The maximum age is ${ages.max}"
}

If the vector is empty, it will throw an exception, and nothings is telling me that.

def maxAge(ages: Vector[Int]): Try[Int] = {
  Try{ages.max}
}

Try[A can return a Failure or a Success

But this is creating exceptions. Another solution is creating our own error class.

case class AppError(message: String, throwable: Option[Throwable] = None)

And using scalaZ disjuntion to give us our return type:

type ErrorOr[A] = AppError \/ A which means: or AppError or A

def maxAge(ages: Vector[Int]): ErrorOr[Int] = {
  if (ages.isEmpty) {
    -\/(AppError("Ages vector is empty"))
  } else {
    AppTry{ages.max}
  }
}

Scala’s Either is ot right biased. The ScalaZ disjunction comes with type-class instances for Functor, Monad, Applicative and more

Type-classes – A mental model

\/ has a Functor instance that can add methods to our class (and Monads, Applicatives, Traversable…)

case class Agent(id: Int, name:String) case class Property(id: Int, description: String, agentId: Int)

Part of video explaining Real World Examples

We could have done the same thing with Futures, Options, FreeMonads…

• FP in Scala - Paul Chiusano and Runar Bjarnason
• “Cats” library documentation
  • http://typelevel.org/cats/index.html