Zen and the Art of Motorcycle Maintenance

It was a long time I’d like to read “Zen and the Art of Motorcycle Maintenance“. It came to my knowledge several years ago while browsing hacker culture stuff, like the Jargon File. Regrettably I can’t find now, even with the power of modern web search engines, which reference I stumbled upon.

I knew that this book has not much to do with real motorbike maintenance (and not much about Zen as well), but motorbike maintenance is used by the author to make his points about a more general pictures. So, when I found this book on the Amazon Kindle daily deals, purchasing it was a no brainer.

The book is about a journey through USA on an old motorcycle. The main character is a dad, traveling with his son. The book is written in first person and is split between the present where the road unfolds before the duo and the past, when the character worked as a University professor, so intelligent and focused that became mad while restructuring in his mind the whole philosophy.

Eventually his journey through philosophical systems ended with an electroshock that turned him into another self. A less introverted person, possibly somewhat less sharp (even if his reconstruction of the thought of the previous self is really deep).

I liked the book, but I cannot define it an eye-opener. Here and there you can find interesting notes and thoughts on issues like technology and people, technology and maintenance, quality. On the other hand, if you are interested in philosophy, you will find this book quite interesting since it tackles about all major philosophers and their systems, applying their thoughts to concrete aspects of life.

[Btw, all these Amazon ads you find in this post (and in the next ones), are just a desperate attempt in recovering some cents to contribute to my website hosting. I don’t want you to but anything you wouldn’t have bought, but if you are interested you can click on the link.]

Lambda World 2017 – Lambda Core, hardcore

Despite of the title which is a bit obscure, this talk has been very clear and entertaining. The speaker Jarek Ratajski (@jarek000000) who defines himself a functional programmer, wizard and anarchitect, definitively knows his art and how to make an engaging speech.

Btw, an anarchitect is the person that breaks the rules so that something can be eventually done.

As usual, mistakes, errors, inaccuracies are all my faults. A last note: you need Scala 2.12 to compile the code presented here, older versions are likely to fail.

I really recommend to watch the presentation video on youtube.


Let’s start with a question for the attendees – you are on a desert island and you can take just one thing from the civilized world. What would you like to have to survive?

[someone from the audience shouts “wifi”]

Well, you need Math. Math is the base for everything, but it is huge! So, maybe we can find a small subset, a core, that allows us to recreate the whole Math.

Lambda is a building block of math. Using lambda calculus we can build – one step at time – the whole Math. Historically Math has been built using sets, unfortunately sets had some problems in terms of paradoxes, so mathematicians resorted to this simpler mechanism.

So lambda (λ) is a function that takes some lambda as parameter and produces another lambda. A lambda is written as:

λ x. some expression

A λ x is applied to λ y with the following notation –

x(y)

to a scala developer:

trait Lambda {
    def apply(x: Lambda) : Lambda
}

Now suppose we on a deserted island with just our Scala compiler. Just the compiler – no jars, no collections, no scala utils, no Boolean, Int, Float, Double, String… anything at all.

The only exception to this nothingness is the badlam package in order to simplify and help the presentation of concepts.

Let’s define the identity, that is a function that returns the function accepted as an argument:

λ x. x

In Scala it turns out to be:

val identity : Lambda = (x) => x

val id2 = identity(identity)

Now we can define function that accepts multiple arguments (via the curry mechanism) and always returns the first one:

val funny: Lambda = (x) => (y) => x

Note that names are not important, but the structure is. The “funny” function structure can be used to implement true and false concepts:

val aTrue = funny
val aFalse : Lambda = (x) => (y) => y

Note that aFalse is complementary with respect to aTrue. Now that we have true and false symbols we can define boolean operators:

val and : Lambda = (p) => (q) => p(q)(p)

You can read this like: and is a function that via currying accepts two arguments p and q. Consider p: it can be either true or false. If it is true its lambda evaluates to its first argument, otherwise to the second. So, when p is true, the and expression evaluates to q, so and is true when both arguments are true. If p is false, then p is returned – no need to consider q.

Let’s check with Scala:

val result1 : Lambda = and ( aFalse)(aTrue)

This evaluate to aFalse, while

val result2:Lambda = and ( aTrue)(aTrue)

This evaluate to aTrue.

Or function is based on the same scheme used by and:

val or:Lambda = (p) => (q) => p(p)(q)

To define not is a matter of reversing the true/false definition:

val not: Lambda = (p) => (a) => (b) => p(b)(a)

So long, so far, we have defined all the tools we need for boolean calculus. Let’s see if we can express numbers. One approach could be:

val zero: Lambda = (f) => (x) => x
val one: Lambda = (f) => (x) => f(x)
val two: Lambda = (f) => (x) => f(f(x))
val three: Lambda = (f) => (x) => f(f(f(x)))

So numbers are functions (of course) that accepts a function and an argument, and returns zero or more applications of the function to the argument.

Zero is the identity. One is the single application of lambda f to the identity. Two is the single application of lambda f to one, that is that application of lambda f to the application of lambda f to the identity, and so on…

This may work, but it is boring to encode all numbers in this way. A function that computes the successor of a given number could be a good tool to lessen the burden:

val succ:Lambda = (n) => (f) => (x) => f(n(f)(x))

[NdM – well this is mind boggling and I have a hard time to decode. Conceptually is simple – just remember that an integer n is represented by a lambda that accepts a function f and an argument x and returns a function composing n nested applications of f over x. So replace x with f(x) and you are done.]

Now we can define addition and multiplication

val plus: Lambda = (m) => (n) => (f) => (x) => m(f)(n(f)(x))
val mult:Lambda = (m) => (n) => (f) => m(n(f))

[NdM -It takes a while for these two as well. Sum is intuitively easy, take 3+2=5, in lambda is: x => f(f(f(x))) + x => f(f(x)) = x => f(f(f(f(f(x))))). You may read plus as: (m,n,f) => (x) => m(f)(n(f)(x)) , that is a function that takes two operands and one function. Remember that m represents and integer by applying a function m times to an operand. So swap in f as operand and you have m times the application of f, now applies this function to an argument that is n times the application of f to x.

Multiplication is similar, x is omitted to keep the code terse, but you can read it as:

val mult:Lambda = (m) => (n) => (f) => (x) => m(n(f))(x)

Keeping the sum approach in mind, this is similar – applies m times a function that is composed by n application of f to x. I needed quite a neuron effort to figure this out.]

Predecessor can be defined as:

val pred: Lambda = (n) => (f) => (x) => n((g) => (h) => h(g(f)))((u) => x)((u) => u)

[NdM. I tried hard to understand this, but simply I couldn’t wrap my mind on it. I don’t have even the slightest idea of how this is expected to work. If you figure it out, let me know, please… well indeed, I think that the last part (u) => u, being an identity, is used to skip an application in the application list, therefore reducing by 1 the application list…]

[NdM. I found this thoroughly explanation of the predecessor on stackoverflow]

Now we can do something even more interesting – conditionals:

val ifLambda: Lambda = (c) => (t) => (f) => c(t)(f)((x) => x)
val isZero: Lambda = (n) => n((x) => aFalse)(aTrue)

Recursion would be a nice addition to the computing arsenal of lambda calculus since it allows to express iterative algorithms. But how are we supposed to call a function when lambda functions are anonymous?

First let’s define a function that makes its argument call itself:

val autocall:Lambda = (x) => x(x)

Then we need a helper function that makes something call itself

val Y: Lambda = (f) => autocall((y) => f((v) => y(y)(v)))

And finally we define a function containing the body of the recursive function:

val G:Lambda = (r) => (b) =>
  (ifLambda(isZero(n))
    ((x) => one )
    ((x) => mult(n)(r(pred(n))))
  )

Now we have everything to recursively compute a factorial:

val fact = Y(G) // this makes G recursive

[NdM: Once more I have a hard time in trying to understand this part. It makes sense intuitively, but I’m lost at details such as function Y. The overall idea is pretty well laid out]

Turing Equivalent?
Lambda calculus has been proved to be Turing- equivalent, meaning that every algorithm that can be implemented on a Turing Machine, can also be implemented using Lambda Calculus. Therefore, you have no excuse, everything can be done purely functional!

Equivalence

In mathematics there are lot of problems, an interesting one is about theorems.

For a mathematician a theorem is something like

if ( condition(args)) then statement(args)

That is, if something holds, then something else is true. It would be nice to build a machine that automatically checks this. This is what about a century ago, mathematicians were looking for – a machine that renders us useless by proving theorems by itself.

In the same way we used lambda calculus to represent numbers, booleans and statements, we could rewrite the theorem as a lambda calculus expression and then execute it to let it show true or false to determine whether the theorem holds or not.

This could be such a machine:

def main( args: Array[String]) : Unit = {
    val autocall: Lambda = x => x(x)
    println( SmartDisplay.web.display(autocall))
    val OMEGA = autocall(autocall)
}

[NdM: also after having watched the youtube video of the conference, I can’t tell where this function comes from. I believe Jarek, but I have no explanation of why this function should prove theorems.]

That would be awesome, regrettably it doesn’t work. In fact autocall function is invoked over autocall itself causing a stack overflow. This is generally what happens when you try to analyze a lambda function for equivalence.

This fact has been proved in 1936 by Alonzo Church: “No computable function can decide the equivalence of two different lambda functions”.

Despite of this there are two guys on stack overflow that are trying to do exactly this in C#.

Lambda is convenient, but it undergoes the incompleteness theorem by Kurt Gödel – For any consistent, effectively generated formal theory that proves certain basic arithmetic truths, there is an arithmetical statement that is true, but not provable in the theory.

In other words it doesn’t matter how cool your formalism is, you still can’t fully automate through an algorithm to prove properties of another algorithm.

So this is what nearly a century ago a group of mathematicians, led by Alonzo Church, devised in search for a more elegant mathematics.

What I presented today is called Untyped Lambda Calculus. Take plus and try to add true and factorial together. It doesn’t make sense. So, by using this notation you can also write correct expressions that don’t make sense.

Since not every expression you can write makes sense, it is a programmer’s duty to write and use only those that make sense.

Typed lambda calculus check correctness for you. Untyped lambda is very much like javascript in which you can write everything and is not checked for type correctness.

I haven’t talked about Lazy/Eager evaluations in lambda calculus. This is a very complicated issue, even if very fun. If you do lambda calculus on paper you will notice that sometime you need to evaluate lazy and other times you need to evaluate eager.

Usually when you read about lambda calculus in Scala, you don’t find what I have shown you, you find something else – lambda calculus done on type system of Scala:

sealed trait True extends Bool {
    type If[ T <: Up, F <: Up, Up ] = T
}

sealed trait False extends Bool {
    type If[T <: Up, F <: Up, Up] = F
}

This is not performed at run-time, but at compile time. This is awesome because the compiler does all the calculations and produce such fine errors you can’t even figure out where they end.

Sources

  • wikipedia
  • blog: (C# Version) Dixin’s blog – this is the post where I took inspiration for this talk.
  • Book: Roger Penrose: The Emperor’s New Mind – this is not about only lambda calculus, but about computation. Reading this book will help you better grasping the subject.
  • Lambda Visualization – Badlam this is nothing special just a package to help the presentation. It is known to work only in presentation and not elsewhere.
  • This same presentation in Java – this is the original work. This presentation has been done first in Java (for fun and drinking beer of course).

NdM: that’s the end of presentation. Here I add my fragment of code I used to check the code. If you prefer you can use Badlam, the code below is in Scala.

Function to convert from lambda numbers to decimal –

def dec( y : Lambda ) : Int = {
    case class Counter( counter: Int) extends Lambda {
        def apply( x: Lambda ) : Lambda = {
            this
        }
    }
    case class Fun() extends Lambda {
        def apply( x: Lambda ) : Lambda = {
            Counter( x.asInstanceOf[Counter].counter+1 )
        }
    }

    y( Fun() )(Counter(0)).asInstanceOf[Counter].counter
}

The trick is to give function f of lambda the semantic of incrementing its argument by 1. If the argument has type int and start counting from zero the conversion is done.

The following code is just a pretty printer for lambdas that are not integers:

def del( x : Lambda ) : Unit = {
    x match {
        case `aTrue` => println( "true" )
        case `aFalse` => println( "false" )
        case `and` => println("<and>")
        case `or` => println("<or>")
        case `not` => println("<not>")
        case _ => println("?")
    }
}

(where aTrue, aFalse and all the other symbols are defined as in the Jarek’s presentation.

Lambda World 2017 – Workshop – Don’t fear the Optics

This talk by Jesús Lopez Gonzales has been quite clear (at least to my challenged functional understanding). As strange as it may sound the whole idea of optics (in Functional Programming) is to solve a problem that exists only because of the functional paradigm. Aside from cheap humor, it makes sense – in structured programming you do the same by forbidding the use of the goto statement, and you need other tools (e.g. break, continue, structured statements) to do the same job in a safe, sound and controlled way.

You can find sources for the running example here: https://github.com/hablapps/dontfeartheoptics.git

But I don’t want to steal the stage. As usual all mistakes and false predicates are mine (my only defense is that the talk was performed without a mike and loudspeaker system).

Just one last not, before starting – the original slides of the presentation used a compact syntax, relying on Scala high sucrose diet. I opted for a more verbose syntax that makes clear to those less fluent in Scala what’s happening behind the sugar curtain.

Functional Programming is a programming paradigm […] that treats computation as the evaluation of mathematical functions and avoids changing-state and mutable data.

(from Wikipedia)

In functional programming we decide to not change state of variables once assigned. That means that when we want to change something we have to create a new instance from the existing one.

Consider the position class:

case class Pos(i: Int, j: Int )
pos1 = Pos(1,1)

In order to change to position to a new one, the “changing” method just takes the existing pos1 and creates a new instance with the new state:

pos2 = pos1.move(1,2)

The running example for this talk is a CandyCrush clone. Here are the main classes:

case class Game( ups: Int, level: option[Level], )
case class Level( targetScore: Long,
                  targetMoves: Long,
                  board: Board,
                  currentScore: Long,
                  currentMoves: Long )
case class Board( height: Int, width: Int, matrix: Map[Pos,Option[Candy]])

Modules are defined as follows:

  • Candy REPL – IO
  • Candy Business logic – state program
  • Candy data layer – data structurs & optics

To face problems posed by state immutabile we resort to the Half Life narration – who better than Gordon Freeman – the man with a big lambda on his breast – could help us in the process?

The talk uses an explorative approach – you may want to explore the area to locate the problem (the Alien), then try to solve it using some techniques (equipping new weapons) and then refine the solution until you find an elegant way to fix the problem.

The first enemy to defeat is how to keep state unchanged.

CandyState.scala is the source file where “getter and setters” are located). There are several points where you need to update the state as the game progresses.

def modifyScore( f: Long => Long) : Level => Level..
def modifyMatrix( f: CandyMatrix => CandyMatrix ) : Level => Level

[NdM: note that specific to this paradigm these methods accepts a function that transforms score (or playfield) into a new score (or playfield) and return a function that change the Level accordingly. I found this revealing and somewhat mind boggling.]

How would you do in traditional way?
In order to modify you need copy:

def modifyScore( f: Long => Long ) : Level => Level =
  lv => lv.copy(currentScore = f(lv.currentScore))

def modifyMatrix( f: CandyMatrix => CandyMatrix ) : Level => Level
lv => lv.copy( board = lv.board.copy( matrix = f(lv.board.matrix)))

This is not straightforward, at least not in general, because you need to copy through several indirection levels. Functional programming is about elegance and modularity, not this.

(Alien identified!)

Lens come to the rescue (or, as Jesus put it, Lens – the crowbar in the half-life analogy – is the weapon to equip). Lens is a parametric class defined over two types: S – the whole and A – the part:

abstract class Lens[S,A] {
    def get( s: S): A
    def set(a: A): S => S
}

get  method accepts a whole and returns a part. set  accepts a part and tell you how to change the whole to incorporate that part.

val _currentScore: Lens[Level,Long] =
    Lens[Level,Long]( 
        lv => lv.currentScore
    )(
        cs => lv => lv.copy(currentScore=cs)
    )
val _board : Lens[Level,Board] =
    Lens[Level,Board](
        lv => lv.board
    )(
        br=>lv=>lv.copy(board=br)
    )
val _matrix : Lens[Board,CandyMatrix] =
    Lens[Board,CandyMatrix](
        bd => bd.matrix
    )(
        mx => bd => bd.copy(matrix=mx)
    )

modifyScore2( f: Long => Long) : Level => Level = {
    level : Level =>
        Level.currentScore.set( f( level.currentScore ))(level)
}

The code works, but it is lengthy and boring to write. So we can take advantage of the Lens defined for us by the @Lenses annotation.

[NdM: I’m going to expand the talk a little bit here because I lost some passages and I reconstructed them thanks to my Scala speaking friends]

This annotation instructs the compiler to create one lens method in the companion object for each case class field. [NdM: Oddly enough, for us coming from traditional programming languages, the lens has the same name of the case class field].

[NdM: original example exploited import to inject in the current scope the companion object’s fields, creating a bit of confusion in my mind. In the following examples I will avoid this shortcut in favor of readability].

What if we want to extract the matrix from a level? Operationally we have to navigate through the board (level->board->matrix). This can be done via composition, using the verb composeLens :

def getMatrix2 : Level => CandyMatrix = (Level.board composeLens Board.matrix).get

[NdM: my Scala speaking friend also told me that def  has been used without a real advantage over val . Having used val would have avoided an unneeded function call.]

The same can be applied for modify:

def modifyMatrix2( f: CandyMatrix => CandyMatrix ) : Level => Level = 
    (Level.board composeLens Board.matrix).modify(f)

This syntax is slick, but still more verbose than say Haskell where you write just a dot instead of the composeLens verb.

# 2nd Enemy – Threading State Zombie (State Monads)

Consider the function

crushPos( pos: Pos): Level => (Level, Long)

Its purpose is to crash a given position. This is accomplished by updating the map and updating the score. Additionally we want the function to return a pair composed by the level and the new score. The first implementation you may want to try is to navigate through the level to change the matrix, then navigate through the updated version of the level to update the score and then prepare the pair with the updated level and the score.

def crushPos( pos: Pos) : Level => (Level, Long) = {
    lv0 =>
        val lv1 = (board composeLens matrix).modify(mx => mx.updated(pos, None))(lv0)
        val lv2 = currentScore.modify( cs => cs +1)(lv1)
        (lv2, currentScore.get(lv2))
}

This works, but it is error prone because the programmer must ensure to properly pipe all the changes through the transformations.

The new weapon is the State:

abstract class State[S,A](run : S => (S,A))

This class defines a mechanism to execute a given action on an object and produce the updated object and a value. And it can be used like:

def crushPos2(pos: Pos): Level => (Level , Long) = {
    lv0 =>
        val (lv1, _ ) = State[Level,Unit] (
            lv => {
                (board composeLens matrix).modify(mx => mx.updated(pos, None))
                ((lv), ())
            }
        ).run( lv0 )
        State[Level,Long] (
            lv => {
                val nlv = currentScore.modify(cs => cs + 1)(lv)
                (nlv, currentScore.get(nlv))
            }
        ).run(lv1)
}

This maybe more elegant, but can be hardly defined as better, and nonetheless still requires the programmer to properly set up the execution pipe. [NdM: also note that the first part (from val  to run( lv0 )  may be replaced by a more compact val lv1 = (board composeLens matrix).modify(mx => mx.updated(pos, None))( lv0 )  ]

This can be improved by using an implicit MonadState, that is a class implicitly built from a State class that can be bound together using the >> operator. In code:

case class State[S,A](run : S => (S,A))

implict def monadState[S]: monad[State[S,?]] = ...

Our code becomes:

def crushPos3(pos: Pos): State[Level, Long] = {
    State[Level, Unit] {
        lv =>
            val lv1 = (board composeLens matrix).modify(mx => mx.updated(pos, None))(lv)
            (lv),()
    } >>
    State[Level,Long] {
        lv =>
            val nlv = currentScore.modify( cs => cs +1)(lv)
            (nlv,currentScore.get(nlv))
    }
}

[NdM: be careful in placing the >> operator! First IntelliJ is not able to recognize it and marks it as an unknown operator; second thanks to Scala forgiveness on syntax punctuation, you need to place >> on the same line of the closing bracket. I couldn’t figure out the right way to write this until I mailed the author of the talk for help. He responded quickly and kindly and set me in the right direction. Thanks Jesús]

[NdM: a quick word on binding. Bind is the same as flatMap, that is the way monads transform their content. In this case the binding allows you to compose the two run action into one. Since the computation accept one value and produces two, you may wonder what happens to the side value (in our case the score) of the first run. Answer – it gets discarded and only the last one is produced in the final result]

MonadState can be composed so they pipe the result one through the other.

def crushPos4( pos: Pos ) : State[Level, Long] =
    (board composeLens matrix).mod(mx => mx.updated( pos, None)) >> currentScore.mod(_ + 5)

[NdM: now, this is a bit more complex to digest – where does the .mod come out? And more importantly how does .mod know what to return? .mod is a method of the StateLens object (well, nearly true, but true enough for the sake of this analysis). Always remember that you are not dealing with actual values, but you are forging functions that will need to be called/applied on actual values. Note that the lenses in the expression are both on the Level class, so the state generated by mod operates on the Level class. The additional type is derived by the right operand of the >> operator.]

# Enemy 3: optional antlion

So far so good, but there are still other entities that cannot fit properly in the picture. What about getting and modifying the current score from the Game? The problem we face is that level is an option in Game. Lenses can’t be used with a plain-vanilla approach.

Let’s try a first attempt to the solution:

def getScore: State[Game, Option[Long]] =
    level.extract.map( olv => olv.map( lv => currentScore.get(lv)))

def modifyScore(f : Long => Long) : State[Game,Unit] =
    level.mod_(olv. => olv.map(lv => currentScore.modify(f)(lv)))

extract  is a method of the State

Nice, but cumbersome. The abstraction we can use now is the Prism (which is defined in monocle, roughly in the following way):

abstract class Prism[S,A] {
    def getOption : S => Option[A]
    def reverseGet : A => S
}

The first method takes an object and produces an option, the second method rebuilds the object given a part. So, let’s define our prism:

import monocle.Prism

def mySome[A] : Prism[Option[A], A] = Prism[Option[A],A]( s => s)(a=>Some(a))

This prism deals  with an Option[A] , but monocle already provides you with this tool and it’s called some :

import monocle.std.option.some

def getScore2: State[Game, Option[Long]] =
    (level composePrism some composeLens currentScore).extract

def modifyScore2( f : Long => Long) : State[Game,Unit] = 
    (level composePrism some composeLens currentScore).mod_(f)

# Final Enemy: Multiple Fast Zombies

Now we want to crush an entire column of the board.

We can combine lenses and prisms into something else:

 

abstract class Optional[S,A] {
    def getOption(s: S): Option[A]
    def set(a: A): S => S
}

As for the Prims we have a getOption method that exposes the Option, but, instead of the reverseGet, there is a set that transforms S into another S provided an A.

Optionals  can be created by composing prisms and lenses as follows:

val op: Optional[Game,CandyMtrix] =
    level composePrism some composeLens board composeLens matrix

So that we can write our first iteration of the crushColumn method as –

def crushColumn(j: Int): State[Game, Unit] =
    op.mod_(
        mx => mx.map {
            case (p,_) if p.j == j => (p,None)
            case x => x
        }
    )

This function operates on the game matrix and removes the candy when the column of the position is the same as j .

It is not bad per se, but that we are doing this in a manual way. The solution could be improved by using a filterIndex:

def crushColumn2( j : Int ) : State[Game,Unit] =
    op.mod_(
        mx => filterIndex[CandiMatrix,Pos,Option[Candy]]( p => p.j == j ).set(None)(mx)
    )

Let’s see how to automatize it. Let’s introduce the abstract metaclass Traversal:

abstract class Traversal[S,A] {
    def modifyF[F[_]: Applicative](f:A => F[A])(s:S): F[S]
}

Now it is possible to compose the Traversal with other lenses such as:

def crushColumn3( j: Int ) : State[Game,Unit] =
    (op composeTraversal filterIndex((p: Pos)=> p.j == j )).assign_(None)

FilterIndex is a monocle function, that along with the implict mapFilterIndex allows the lens to apply over the map collection.

Since compose syntax may tend to be a bit verbose, you can also use the following operators:

  • ^<-?  compose with prism
  • ^|->  compose with a Lens
  • ^|->> compose traversal

Conclusions: Optics are abstractions for changing parts of wholes. These abstractions are composable to access complex data. Monacle library provides hybrid of concrete e Van Laarhoveen optics [NdM: sorry I missed the explanation entirely]. State monads encapsulate state threading and produce output values.


Max’s comment – The talk has been very helpful in improving my understanding of this aspect of the functional programming. I still find Scala syntax to be a bit on the verge of cryptic and dealing with new concepts doesn’t help as well. Composing stuff in the way functional programming does is a really powerful mechanism that enables the programmer to recycle code in an effective way.

I find that the use of symbols to further reduce the characters count is really dangerous. But this is a topic for another post. Let’s just say that Scala is endangered of write-only code 🙂 Looking forward to attending next Lambda World!

Lambda World 2017 – Unconference – Category Theory Crash Course

Here I am in Cadiz to attend 2017 edition of Lambda World. Cadiz is really a nice frame for this conference and the weather is so good that it seems to be back at vacation time instead then in mid-Autumn.

Anyway, on this morning I attended the “unconference”, a sort of informal prelude to the real conference. After the first, planned talk, people could register to present their talk and other attendants could vote their preferred talk. This yield two interesting talk – one on declarative testing and the other one on category theory. Here is what I learned from the last one, by Rùnar Bjarnason.

First, this is algebra stuff, really. Not the kind of ‘a+b’ you do in mid schools, but the high order stuff you do later when you study groups, monoids and the likes.

How does these concepts applies to practical programming still eludes me, but I sense that something is there waiting for my brain to grasp it.

Basically an abstract algebra of function wants to answer to the following questions – what functions do? And what can we say about them? Here we go, all mistakes, errors, inconsistencies are just mine, blame me not Rùnar.

A Category is defined by objects and arrows and how we can compose those arrows.

If you consider language types as objects then functions can be thought as arrows from an object to another object:

Some types: A, B, C.
Some functions f, g.

f: A => B
g: B => C

a composite functions is formed by invoking a function on the result of another one:

g compose f = (x => g(f(x)))

As long as types line up we can concatenate function composition.

If a function links an object to itself (in the example a type to itself), this is the identity function:

identity function: identity[A] : A=>A
identity compose f = f
f compose identity = f

Sometime composition is expressed with a dot. An interesting property is that composition is associative:

h.g.f = (h.g).f = h.(g.f)

(so no need for parenthesis).

In Scala you have a category for functions and types, but also for types and inheritance (subtyping). This category is defined as follows:

Objects: Scala Types: A, B, C…
Arrows: Subtype relations: A <: B, B <: C…
Composition: [ A <: B, B <: C ] => A <: C
Associativity: A <: B <: C (no need for parenthesis)
Identity: A <: A

Another example of category is the the pre-order (<=). Objects are instances of a Type on which <= binary relationship is defined:

Objects a, b, c…
Arrows: a <= b, b <= c
Transitivity: <=
Identity: a <= a

E.g. natural numbers are a category for preorder.

Monoids are categories with one object. This object, by convention, is written as ‘*’. All arrows links * to itself. In a turn of notation I’ll use the symbol |+| for composition and ‘mzero’ for identity.

Objects: *
Arrows: f, g, h: * -> *
associativity
identity: * -> *
mzero |+| a = a
a |+| mzero = a

Object is just an anchor, to hold arrows.

Category of preorders:
A preorder is a set with <=
Objects: all the preorders (Scala integers)
arrows: Homomorphisms on preorders

[NdM: at this point things start to be complicated and I have likely lost the speaker. What follows are likely to be glimpses of his talk… the parts I got]

Monotonic functions.
e.g. string length : _.length is a monotonic function.
Preserves relationship:
x <= y then h(x) <= h(y)

Category of monoids:
Objects: all the monoids
Arrows: monoid homomorphism
h( x |+| y) == h(x) |+| h(y)

Category of categories
Objects: all the categories
Arrows: category homomorphism F
F( f . g ) = F(f) . F(g) e.g. _map( f compose g ) = _.map(f) compose _.map(g)
these are functors.

Given a category C, there is a category of endofunctors on C
endofunctor F[_]
Objects: functors
arrows: functor homomorphism
h: F[A] => G[A]
h compose _.map(f) = _.map(f) compose h

trait ~>[F[_].G[_]] { def apply[A](a: F[A]) : G[A] }

A monad on C is an endofunctor M[_] together with two natural transformations:

pure[A] : A=>M[A]
join[A] : M[M[A]] => M[A]

A monad is a kind of category:
M[M[M[A]]] : can be associated as we want, preserving the result.

A monad is a monoid in an endofunctor category.

[And with this truth the brief talk is over]

Livello di pericolosità dello step coreografico

(articolo originale)

Lo step coreografico è una delle mie attività sportive preferite. Come ho già scritto, mi piace lo step perchè richiede sia coordinazione che memoria e mette alla prova la memoria muscolare al ritmo della musica dance. Nello scorso anno e mezzo ho avuto la fortuna di avere un’istruttice stellare. Capace di proporre ad ogni lezione coreografie sempre nuove, emozionanti e a volte pazze. Le sue coreografie sono molto divertenti, ma a volte richiedono alcuni passaggi che presentano un qualche livello di pericolo. Se ti distrai o non sei abbastanza veloce a modificare la tua memoria muscolare puoi mancare lo step o scontrarti con qualcun altro.
Ho preparato una tabella (simile al mio “Grado di Efficacia del Weekend”) che definisce un numero di taschi per ogni caratteristica pericolosa della coreografia. Semplicemente bisogna aggiungerne uno per ogni caratteristiche della coreografia per avere il livello di pericolo. Oggi abbiamo raggiunto i 3 teschi.

  • Passo attraverso lo step – bisogna estendere la gamba oltre lo step con il rischio di colpire lo step con il tallone e perdere l’equilibrio.
  • Giro all’indietro sul pavimento che finisce con un piede sullo step – non si può vedere lo step mentre giri, ma bisogna avere un’idea abbastanza precisa di dove sia lo step, altrimenti puoi colpirlo con il piede o appoggiare il piede parzialmente perdendo l’equilibrio.
  • Due step a testa – di solito gli step sono abbastanza vicini l’uno all’altro e la coreografia solitamente prevede delle mosse con un piede tra i due step. E’ possibile inciampare in uno step o appoggiare male il piede. Se gli step sono molto vicini è possibile inciampare nelle proprie gambe.
  • Step vicini – quando il tuo step è accanto a quello di un’altra persona diventa necessaria una buona sincronia altrimenti ci si può scontrare. Distinguere la destra dalla sinistra solitamente aiuta.
  • Step condivisi – in determinati momenti della coreografia due persone condividono lo stesso step. Di solito la coreografia prevede abbastasnza spazio per entrambe. Ma anche in questo caso è necessaria una buona tempistica e una buona sincronia per muoversi nella giusta direzione.
  • Scambio step – ognuno ha il proprio step, ma ad un certo punto tutti si muovono verso un altro step allo stesso momento. Di solito la coreografia crea un corridoio a tempo per permetterti di raggiungere la destinazione. “A tempo” è la chiave.
  • Sincronizzazione precisa. Due persone sone abbastanza vicine, verosimilmente sullo stesso step, ma eseguono movimenti diversi. I movimenti si combinano con i tempi giusti in modo che non ci sia collisione. Questo è una delle situazioni più pericolose perchè non può affidarti alla simmetria o prendere spunto dai movimenti del tuo compagno/a; qualsiasi errore, anche piccolo, causa una collisione.

Step Choreography Danger Level

Choreographic step is one of my favorite fitness activities. As I wrote in the past I like step because it requires both coordination, memory and challenges your muscle memory at the rhythm of dance music. In the past year and half I was so lucky to have a stellar step instructor. She is able to propose new and exciting and sometimes crazy choreographies at each lesson. Her choreographies are usually a lot of fun but sometimes require you to perform some moves that may yield some danger level. If you get distracted or you are not fast enough to retrain your muscle memory you may miss the step or smash into another stepper. Here is a table (similar to my Week-end Effectiveness Degree table) that defines a number of skull for each dangerous feature of the choreography. Just add one for each of the feature in the choreography and you get the danger level. Today we reached 3 skulls.

Step across the step – you need to extend you leg across the step risking to hit the step edge with your talon, losing your balance.
Turn backward on the floor and end with a feet on the step – you can’t see the step though you need a fairly good idea about where the step is, otherwise you may hit with the feet or put your feet half on the step, losing your balance.
two steps per person – usually steps are quite close each other and the choreography expects you to move placing a feet between the two steps. You can stumble into a step, or half place a feet on a step. If the steps are really close you may stumble into your own legs.
close steps – when your step is adjacent to another person’s step, you need to properly synchronize, otherwise you may smash into each other. Knowing left from right is usually helpful.
shared steps – at some point of the choreography two people share the same step. Usually the choreography manages to get each one enough space to move, but again you need good timing and good sync to move the right way.
exchanging steps – each one has his/her own step, but at a given time everyone moves to another step all together. Usually the choreography manages to create a timed corridor to reach your destination without smashing into anyone. “Timed” is the key.
close synchro – two persons are close enough, likely on the same step and performs different moves in turn. Moves combine together at the right time so that there is no collision. This is one of the most dangerous since you can’t rely on symmetry or get any hint from your pal; also any slight error will cause a collision.

La Venaria Reale

On Easter Monday, for the traditional “Gita fuori porta” (out of town excursion) we went neat Turin to see the Venaria Reale an old royal palace repaired and rebuilt to its ancient splendor.

Ciaspolata Rheme Notre-Dame

Seiser Alm – pictures

From our latest vacations on the Sud Tirol Alps

Reacting to the movies: reactive systems and the lessons of narrative.

Another Reactive Summit 2016 talk. Speaker was Steve Moore – IBM story strategist. My comments at the end. (When writing about heros I used “she” as pronoun, if you are sensitive to this use sed s/she/she\/he/g).

Thinking differently helps you gaining new perspectives on your work. That’s the work for story strategist and this is the idea behind this talk. Finding analogies between reactive systems and movies.

Stories behave like reactive systems you can see three analogies:

  1. hero as scalability,
  2. plot as resilience,
  3. genre as elasticity.

Scalability : heroes are under constant pressure to scale. Scaling is usually achieved via some resource. The best resource a hero has at her disposal is a new understanding of the world.

There are three form of escaping in the scaling up of the hero.

Escape the skin. The hero is trying to escape the fake reality she’s living to reach the real and more complex reality behind. Paranoia and questioning foundation of the system are the mean to achieve this escape. This can be summed by the question: “Are you being paranoid enough”?

Escape stoicisms. The hero lives in a simple world that avoids emotional entanglement. The hero takes more responsibility that she think she can bear. Scalability and generosity go hand in hand. Question: “Are you being generous enough?”

Escape the story. The hero lives in a world she wants to escape. This is different from the deception of the escape the skin (first form). The question is “are you being patient enough?” Sometime you need to take the time to observe and understand.

plotasresilience

The plot directs the hero where is needed by the story. Stories are all about failures – the plot is just a sequence of failures that get the hero further and further away from his goal.

Heroes never ever give up. Likeability is not required by heros.

3 ways the hero fails:

Lure of the invisible. This is a kind of accumulation of something that is somewhat hiding. Can be a log file that is increasing without anyone noticing, or some peril that grows unnoticed over time. “What is the system accumulating?” This is not an issue until it is. This way of failure includes also non technical accumulation such as management attention, customer complaints…

Lure of inclination. The hero would like something, but she has to put away that to pursue his goal. Following inclinations may get the hero in hot water, but in the end brings benefits.  “Can you make the system fragile?” [NdM sorry, it is likely I missed something in the translation]

Lure of independence. The story has a lot of moving parts apparently in an unrelated way. Using micro services the system may be better managed and written by smaller teams. “Could coordination be fun?”

Coordination among the teams is needed.

Genre is elasticity.

Elasticity means that response does not change when workload changes or accidents happen. What defines the genre is a set of rules. Genres are categories of antagonists. An antagonist puts strain on the hero.

Three different kinds of genres:

Human v. Human. The analogy on system is threats posed by human hostile actions. “Can you change the game?”

Human v. Nature. The natural world is challenging the hero. Natural antagonists are simple, unbeatable and unchangeable. These stories are about survival. If you live, you deserve to live. “do you deserve to live?” If the system were in danger do these people would do something to protect it?

Human vs self. Hero is also the antagonist. The hero doesn’t want to push away something that is abundant in his life. This kind of abundance forces the hero to questioning the reality “can you endure abundance?” We need to transform ourselves and the system at the same time.

This is the only way the system has to survive.

This talk was very interesting even if not very practical or even theorical. I like the idea that adding word to vocabulary and concepts to the programmer resources may help to devise better system or to enhance the understanding of the system. It makes food for lateral thinking (lateral food?).

One of the first person we met at the luminaries barbecue the day we arrived, had the following job title “Chief Storyteller”. Maybe this is a sign of times.