ik

Ivan Kusalic - home page

Interesting Language Concepts - Presentation at Software Craftsmanship Meetup

Yesterday I gave a presentation about various language constructs at Software Craftsmanship Berlin meetup.

This post is a quick retrospective on the meetup as well as collections of examples I used so you can look at them at your leisure.

Why this presentation?

In Software Craftsmanship Berlin meetup we (organisers) usually try to have hands-on meetups. It is almost our trademark. We’ll have a short presentation followed by a kata to try it out. Or we would directly go for a fun kata or game. This meetup was a bit different – there was no hands-on part, just a presentation and discussion.

I wanted to have this topic for two reasons:

  • I think the topic is important
  • I wanted to try presenting it

Know your tools

While pairing on meetups or Code Retreats I’ve realised that most developers who show up aren’t too familiar with Functional Programming. Often they are deeply familiar with Java, but rarely with some more exotic and interesting languages.

Programming languages are the tools we use every day. Because of that we need to know how to use them properly. We also need to know when a particular language is a good choice for the job. For me this is a crucial part of being a Software Craftsman.

Giving loosely structured presentation

So far I’ve given a few presentation in front of audiences of varying sizes. Presenting is fun. It is also an useful skill. Until yesterday all the presentations I’ve given were shorter and had a lot of structure. I would rehearse them at least a couple of times and mostly knew what I’m going to say and how.

I wanted to try something different – long presentation with almost no structure and no dry runs.

Retrospective

Yesterday’s presentation lasted for two and half hours in front of some 40 attendees. Right from the start I’ve invited everybody to interrupt me with questions, comments, use-cases or with anything else they wanted.

I’ve chosen a dozen of topics in advance and prepared some notes and accompanying examples. Notes were there as my safety net – if I got stuck I could check the notes. Additionally, they would serve as a reminder for certain things I wanted to touch upon.

Overall I think that the presentation went pretty well. From the feedback we got it looks like most participants have learned something new. That means the main goal was achieved. I was positively surprised when only one or two people left during the break.

My presentation experiment wasn’t perfect, but it was a success. I ended up looking at the notes less than a dozen of times – mostly to make sure I didn’t miss out on anything important before moving to the next topic. One major thing I forgot to do – I should have recorded myself to analyze bad habits I have. Oh well, maybe I’ll do that next time.

I would have preferred if we had even more discussions and interruptions, but it was not too bad. While presenting, I wasn’t sure if the complexity level was appropriate. The poll at the end seems to indicate that it was just about right for the majority of attendees. My personal communication style is quite verbose and abstract (heh, ENTP). That’s hard to change at my current skill level. Maybe in the future I’ll need to move a bit toward neutral communication style while presenting.

In the first half I’ve presented a few topics I considered more useful/practical for the participants. In second half I’ve asked the audience for topics we would prioritise as there wouldn’t be enough time for all of them. This worked out really well. For the last topic – Type classes – I’ve committed beforehand to presenting it in 7 minutes and somehow managed that.

What follows should be useful if you want to learn more about the topics covered.

More details

You can learn more about a particular concept by looking it up on wiki or just plain DuckDuckGoing1 it.

If you’re in interested in the concepts presented at the meetup, The Neophyte’s Guide to Scala is a great source of easy-to-understand explanations with Scala examples. No deep knowledge of Scala required.

Here’s a scattering of links that could be interesting:

I’m also tweeting articles I find interesting regularly. @ikusalic

Examples

What follows are the examples that I’ve created or borrowed for this presentation. The topics we managed to cover:

  • Rich type system
  • Higher-order functions
  • Pattern matching
  • Multiple dispatch
  • Macros
  • Type classes

Here’s the table of content of examples for convenience.

Rich type system

Tuples

Python repl
1
2
3
4
5
>>> t = (1, "foobar")
>>> t
(1, 'foobar')
>>> type(t), type(t[0]), type(t[1])
(<type 'tuple'>, <type 'int'>, <type 'str'>)
Scala repl
1
2
scala> (1, "foobar")
res0: (Int, String) = (1,foobar)

Option

Haskell
1
data Maybe a = Nothing | Just a
pseudo-Scala
1
Option[A] = if (x == null) None else Some(x)

Try

Scala repl
1
2
3
4
scala> Try(1 / 0)
res3: scala.util.Try[Int] = Failure(java.lang.ArithmeticException: / by zero)
scala> Try(1 / 1)
res4: scala.util.Try[Int] = Success(1)

Either

Scala repl
1
2
val l: Either[String, Int] = Left("flower")
val r: Either[String, Int] = Right(42)

Existential types

Scala repl: error - runtype type exists
1
2
3
4
5
6
7
8
scala> var implementingClass = "".getClass
implementingClass: Class[_ <: String] = class java.lang.String

scala> implementingClass = 1.getClass
<console>:8: error: type mismatch;
 found   : Class[Int]
 required: Class[_ <: String]
       implementingClass = 1.getClass
Scala repl: ok - not the same type
1
2
3
4
5
6
7
8
scala> def className(implementingClass: Class[_]) =
     |     implementingClass.getName

scala> className("".getClass)
res3: String = java.lang.String

scala> className(1.getClass)
res4: String = int

Previous example seemed to confuse some people as they were wondering why does Class need a type parameter, i.e. why is it a type constructor and not a regular type. For the purpose of the topic this is irellavant, but if you’re interested check Java Class for more details.

If List is used instead of Class, the example is less prone to confusion, as it’s more intuitive that List takes a type parameter:

Scala repl: previous 2 examples with List
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
scala> var list = "to" :: "be" :: "or" :: Nil
list: List[String] = List(to, be, or)

scala> list = 1 :: 42 :: Nil
<console>:8: error: type mismatch;
 found   : Int
 required: String
       list = 1 :: 42 :: Nil

scala> def length(list: List[_]) =
     |     list.size

scala> length("to" :: "be" :: "or" :: Nil)
res0: Int = 3

scala> length(1 :: 42 :: Nil)
res1: Int = 2

Structural types

Scala - toy demo repl
1
2
3
4
5
6
7
8
9
10
11
scala> type WithId = { def getId(): String }
scala> def id[T <: WithId](e: T) = e.getId()

scala> class Foo { def getId() = "foo" }
scala> class Bar { def getId() = "bar" }

scala> id(new Foo)
res5: String = foo

scala> id(new Bar)
res6: String = bar
Scala - real-life usage
1
2
type WithId = { def getId(): String }
def canaryFilter[T <: WithId](instances: Seq[T], groupName: String): T

Higher-order functions

Ruby repl
1
2
pry(main)> [1,2,3].select { |e| e.odd? }
=> [1, 3]
Scala repl
1
2
scala> List(1, 2, 3).filter(_ % 2 == 1)
res1: List[Int] = List(1, 3)

WordFrequencies

Scala
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
object WordFrequencies {

    type Word = String

    val WordRegex = "([\\w\\d]+)".r

    case class WordFrequency(word: Word, frequency: Int) {
        override def toString: String = s"${word} - ${frequency}"
    }

    def main(args: Array[String]) = {
        val words =
            "to be or not to be == 2b || !2b".split(' ')
            .collect { case WordRegex(w) => w }

        println(frequenciesFor(words).mkString("\n"))
    }

    def frequenciesFor(words: Seq[Word]): Seq[WordFrequency] = {
        words
            .groupBy(identity)
            .map { case (word, occurrences) => WordFrequency(word, occurrences.size) }.toSeq
            .sortWith { case (a, b) =>
                (a.frequency == b.frequency && a.word < b.word) || a.frequency > b.frequency
            }
    }
}
Output
1
2
3
4
5
be - 2
to - 2
2b - 1
not - 1
or - 1

The most interesting part of this example is frequenciesFor function that manipulates the date in functional style.

FutureSum

Scala
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import scala.concurrent._
import scala.concurrent.duration._
import ExecutionContext.Implicits.global

case class SlowInt(value: Int, delay: Duration) {
  def toFuture = Future { Thread.sleep(delay.toMillis); value }
}

object FutureSum {

  def main(args: Array[String]) = {
      val delayedNumbers = SlowInt(100, 1.second) :: SlowInt(42, 2.second) :: Nil
      val futureNumbers = Future.traverse(delayedNumbers)(_.toFuture)
      val futureSum = futureNumbers.map(_.sum)
      println(Await.result(futureSum, 2.5.seconds))
  }
}
Output
1
142

The focus of this example is the usage of Future.traverse function. It is a great example of extremely powerful and useful higher-order function.

Partial functions

Scala repl - map is partial function
1
2
scala> val t: PartialFunction[Int, Int] = Map.empty[Int, Int]
t: PartialFunction[Int,Int] = Map()
Scala repl - complex sqrt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
scala> val realSqrt = new PartialFunction[Double, String] {
     |     override def apply(x: Double): String = Math.sqrt(x).toString
     |     override def isDefinedAt(x: Double): Boolean = x >= 0
     | }

scala> val complexSqrt = {
     |     val imaginarySqrt: PartialFunction[Double, String] =
     |         { case x: Double => realSqrt(-x) + "i" }
     |     realSqrt.orElse(imaginarySqrt)
     | }

scala> complexSqrt(4)
res14: String = 2.0

scala> complexSqrt(-4)
res15: String = 2.0i

Pattern matching

Scala repl - assignment examples
1
2
3
4
5
6
7
8
9
10
11
12
scala> val (even, odd) = List(1,2, 3, 4, 5).partition(_ % 2 == 0)
even: List[Int] = List(2, 4)
odd: List[Int] = List(1, 3, 5)

scala> val (head :: tail) = List(1, 2, 3)
head: Int = 1
tail: List[Int] = List(2, 3)

scala> val (h :: t, Some(s)) = (Seq(1, 2, 3), Some(4))
h: Int = 1
t: List[Int] = List(2, 3)
s: Int = 4
Scala - typical usage
1
2
3
4
5
def getDomains(groupName: String) =
    All.find(_.name == groupName) match {
        case Some(domainGroup) => domainGroup.domains.map(_.domain)
        case None              => Nil
    }
Scala - tree depth
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/*
 * NOTE: example from blog post "Structural Pattern Matching in Java" * http://danielwestheide.com/blog/2013/02/06/the-neophytes-guide-to-scala-part-12-type-classes.html
 * http://blog.higher-order.com/blog/2009/08/21/structural-pattern-matching-in-java/
 */

sealed trait Tree
case object Empty extends Tree
case class Leaf(n: Int) extends Tree
case class Node(l: Tree, r: Tree) extends Tree

object TreeDepth {

    def main(args: Array[String]) = {
        val tree = Node(Node(Node(Leaf(1), Leaf(2)), Leaf(3)), Leaf(4))
        println(
            s"""depth of full tree:     ${depth(tree)}
               |depth of left subtree:  ${depth(tree.l)}
               |depth of right subtree: ${depth(tree.r)}
             """.stripMargin
        )
    }

    def depth(t: Tree): Int = t match {
        case Empty      => 0
        case Leaf(_)    => 1
        case Node(l, r) => 1 + Math.max(depth(l), depth(r))
    }
}
Output
1
2
3
depth of full tree:     4
depth of left subtree:  3
depth of right subtree: 1
Scala repl - case class
1
2
3
4
5
6
7
8
9
10
scala> case class Person(name: String, age: Int, gender: String)

scala> val people = Seq(
     |     Person("John", 11, "M"),
     |     Person("Jenny", 27, "F"),
     |     Person("Tom", 42, "M")
     | )

scala> people.collect { case Person(_, age, "M") => age }
res9: Seq[Int] = List(11, 42)
Scala repl - …just a partial function
1
2
3
4
5
6
7
8
9
10
11
12
13
14
scala> val maleAge: PartialFunction[Person, Int] =
    { case Person(_, age, "M") => age }

scala> people.collect(maleAge)
res10: Seq[Int] = List(11, 42)

scala> maleAge(Person("Jenny", 27, "F"))
scala.MatchError: Person(Jenny,27,F) (of class Person)
  at scala.PartialFunction$$anon$1.apply(PartialFunction.scala:253)
  at scala.PartialFunction$$anon$1.apply(PartialFunction.scala:251)
  at $anonfun$1.applyOrElse(<console>:9)
  at $anonfun$1.applyOrElse(<console>:9)
  at scala.runtime.AbstractPartialFunction.apply(AbstractPartialFunction.scala:36)
  ... 33 elided

Traits

Ruby - Enumerable
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Colors
  include Enumerable

  def each
    yield "red"
    yield "green"
    yield "blue"
  end
end

[5] pry(main)> cs.each { |c| puts "\tcolor: #{c}" }
  color: red
  color: green
  color: blue
=> nil

[7] pry(main)> puts "upper case: #{ cs.map { |c| c.upcase } }"
upper case: ["RED", "GREEN", "BLUE"]
=> nil

[8] pry(main)> puts "sorted alphabetically: #{ cs.sort }"
sorted alphabetically: ["blue", "green", "red"]
=> nil

[10] pry(main)> puts "'free' methods:\n#{ Enumerable.instance_methods.sort.join(", ") }"
'free' methods:
all?, any?, chunk, collect, collect_concat, count, cycle, detect, drop,
drop_while, each_cons, each_entry, each_slice, each_with_index,
each_with_object, entries, find, find_all, find_index, first, flat_map, grep,
group_by, include?, inject, lazy, map, max, max_by, member?, min, min_by,
minmax, minmax_by, none?, one?, partition, reduce, reject, reverse_each,
select, slice_before, sort, sort_by, take, take_while, to_a, to_h, zip
=> nil

Closures

Scala repl - preserving state
1
2
3
4
5
6
7
8
9
10
11
12
13
scala> def getCounter: () => Int = {
     |     var counter = 0
     |
     |     { () => counter += 1; counter }
     | }

scala> val nextCount = getCounter

scala> nextCount()
res17: Int = 1

scala> nextCount()
res18: Int = 2
Scala repl - exclusive state sharing
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
scala> def getCommunicators = {
     |     var msg = "initial message"
     |
     |     val setter = { s: String => msg = s}
     |     val getter = { () => msg }
     |     setter -> getter
     | }

scala> val (s, g) = getCommunicators

scala> g()
res19: String = initial message

scala> s("foobar")
scala> g()
res21: String = foobar
Scala - tail-recursion encapsulation
1
2
3
4
5
6
7
8
9
10
11
def factorsOf(num: Int): Seq[Int] = {

    @tailrec def f(num: Int, divisor: Int, factorsSoFar: List[Int]): List[Int] =
        if (num % divisor == 0)
            f(num / divisor, divisor, factorsSoFar :+ divisor)
        else if(divisor < num)
            f(num, divisor + 1, factorsSoFar)
        else factorsSoFar

    f(num, 2, Nil)
}
Scala - encapsulation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def evolve(current: CellCollection): CellCollection = {

   def neighbourhood(pos: GridPosition): CellCollection =
       (for (dx <- Seq(-1, 0, 1); dy <- Seq(-1, 0, 1))
           yield GridPosition(pos.x + dx, pos.y + dy)).toSet

   def neighboursCount(pos: GridPosition) =
       (neighbourhood(pos) - pos)
           .foldLeft(0) { case (sum, pos) =>
               if (current.contains(pos)) sum + 1 else sum
           }

   current
       .flatMap(neighbourhood)
       .filter { pos =>
           Cell.willLive(isAlive = current.contains(pos), neighboursCount(pos))
       }
}

Implicits (Scala)

Scala repl - built in implicit
1
2
scala> 1 -> "one"
res22: (Int, String) = (1,one)
Scala repl - silly example
1
2
3
4
scala> implicit def seqToInt(seq: Seq[_]): Int = seq.size

scala> val t: Int = Seq(0, 42)
t: Int = 2
Scala - map signature - scary?
1
def map[B, That](f: A => B)(implicit bf: CanBuildFrom[Repr, B, That]): That
Scala - adding functionality to classes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
implicit class AugmentedFuture[+T](private val future: Future[T]) extends AnyVal {

    final def mapTry[U](f: Try[T] => U)(implicit executor: ExecutionContext): Future[U] = {
        val p = Promise[U]()
        future.onComplete(result => p.complete(Try(f(result))))
        p.future
    }

    final def flatMapTry[U](fn: Try[T] => Future[U])(implicit executor: ExecutionContext): Future[U] = {
        val p = Promise[U]()
        future.onComplete(result => p.completeWith(fn(result)))
        p.future
    }
}
Scala - adding general functionality
1
2
3
4
5
6
7
8
9
10
implicit final class EnsuringWithExpectationException[A](private val self: A) extends AnyVal {
    def withExpectation(cond: A => Boolean, message: A => String): A = {
        if(!cond(self)) throw ExpectationException(message(self))
        self
    }
}

allZones
    .filter(z => availabilityZoneRestrictions.contains(z.name))
    .withExpectation(_.size == availabilityZoneRestrictions.size, found => s"Couldn't find all AZ restrictions for environment $name. Only found: $found")

Type classes

Haskell - Eq type class example
1
2
3
4
5
6
7
8
9
10
11
12
-- example from wiki: https://en.wikipedia.org/wiki/Type_class

-- type a belongs to class Eq if there are functions named (==) and
-- (/=) of the appropriate types, defined on it
-- Eq in not a type, there are no values of type Eq
class Eq a where
(==) :: a -> a -> Bool
(/=) :: a -> a -> Bool

member :: (Eq a) => a -> [a] -> Bool
member y [] = False
member y (x:xs) = (x == y) || member y xs
Scala - Neophyte’s Guide’s example
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
package neophytes

import org.joda.time.Duration._

/*
 * NOTE: example from The Neophyte's Guide to Scala
 * http://danielwestheide.com/blog/2013/02/06/the-neophytes-guide-to-scala-part-12-type-classes.html
 */

object NeophytesTypeClasses {
    import neophytes.Statistics._
    import neophytes.JodaImplicits._

    def main(args: Array[String]) = {
        val durations = Vector(
            standardSeconds(20), standardSeconds(57), standardMinutes(2),
            standardMinutes(17), standardMinutes(30), standardMinutes(58),
            standardHours(2), standardHours(5), standardHours(8),
            standardHours(17), standardDays(1), standardDays(4)
        )
        println(s"median: ${median(durations).getStandardMinutes}")
        println(s"mean: ${mean(durations)(NumberLikeDuration).getStandardMinutes}")
    }
}

object Math {
    // type class specification
    import scala.annotation.implicitNotFound
    @implicitNotFound("No member of type class NumberLike in scope for ${T}")
    trait NumberLike[T] {
        def plus(x: T, y: T): T
        def divide(x: T, y: Int): T
        def minus(x: T, y: T): T
    }

    object NumberLike {
        // default implementations

        implicit object NumberLikeDouble extends NumberLike[Double] {
            def plus(x: Double, y: Double): Double = x + y
            def divide(x: Double, y: Int): Double = x / y
            def minus(x: Double, y: Double): Double = x - y
        }

        implicit object NumberLikeInt extends NumberLike[Int] {
            def plus(x: Int, y: Int): Int = x + y
            def divide(x: Int, y: Int): Int = x / y
            def minus(x: Int, y: Int): Int = x - y
        }
    }
}

// client code
object Statistics {
    import neophytes.Math.NumberLike

    def mean[T](xs: Vector[T])(implicit ev: NumberLike[T]): T =
        ev.divide(xs.reduce(ev.plus(_, _)), xs.size)

    def median[T : NumberLike](xs: Vector[T]): T = xs(xs.size / 2)

    def quartiles[T: NumberLike](xs: Vector[T]): (T, T, T) =
        (xs(xs.size / 4), median(xs), xs(xs.size / 4 * 3))

    def iqr[T: NumberLike](xs: Vector[T]): T = quartiles(xs) match {
        case (lowerQuartile, _, upperQuartile) =>
            implicitly[NumberLike[T]].minus(upperQuartile, lowerQuartile)
    }
}

// adding new type class member
object JodaImplicits {
    import neophytes.Math.NumberLike
    import org.joda.time.Duration

    implicit val x: NumberLike[Duration] = NumberLikeDuration

    implicit object NumberLikeDuration extends NumberLike[Duration] {
        def plus(x: Duration, y: Duration): Duration = x.plus(y)
        def divide(x: Duration, y: Int): Duration = Duration.millis(x.getMillis / y)
        def minus(x: Duration, y: Duration): Duration = x.minus(y)
    }
}

Currying & Partial application

Scala - parser example
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// trait
    def parseWith(parser: Parser[AccessLogEntry])(line: String): Option[AccessLogEntry] =
        parseAll(parser, line) match {
            case Success(e, _) => if (e.request.path.map(p => p.startsWith("/places")) | true) Some(e) else None
            case otherwise =>
                System.err.println(s"Cannot parse log entry: '$otherwise'")
                None
        }
// (...)

// concrete implementation
    private lazy val logEntry: Parser[AccessLogEntry] = ???

    val parse: String => Option[AccessLogEntry] = parseWith(logEntry)

Monads

Scala - for comprehensions
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
import java.util.{NoSuchElementException, Random}

object ForComprehensions {

    val rand = new Random()

    def inc(value: Int): Option[Int] =
        if (rand.nextInt(10) < 8) Some(value + 1)
        else None

    def withForComprehensions() =
        for {
            a <- inc(0)
            b <- inc(41)
            c <- inc(99)
        } yield a + b + c

    def withIfs(): Option[Int] = {
        val a = inc(0)
        if (a.isDefined) {
            val b = inc(41)

            if (b.isDefined) {
                val c = inc(99)

                if (c.isDefined) Some(a.get + b.get + c.get)
                else None
            }
            else None
        }
        else None
    }

    def abusingExceptions(): Option[Int] =
        try {
            val a = inc(0)
            val b = inc(41)
            val c = inc(99)
            Some(a.get + b.get + c.get)
        } catch { case e: NoSuchElementException => None }

    def main(args: Array[String]) = {
        1.to(5).foreach(_ => println(s"for comprehension: ${withForComprehensions()}"))
        1.to(5).foreach(_ => println(s"ifs: ${withIfs()}"))
        1.to(5).foreach(_ => println(s"exceptions: ${abusingExceptions()}"))
    }
}
Output
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
for comprehension: None
for comprehension: None
for comprehension: Some(143)
for comprehension: None
for comprehension: Some(143)
ifs: None
ifs: Some(143)
ifs: None
ifs: Some(143)
ifs: None
exceptions: Some(143)
exceptions: None
exceptions: Some(143)
exceptions: None
exceptions: None

The purpose of this example was to show that some languages have dedicated monadic notations. In Scala this notation is called for comrehensions.

Multiple dispatch

Common Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
;; example from wiki: https://en.wikipedia.org/wiki/Multiple_dispatch

(defmethod collide-with ((x asteroid) (y asteroid))
;; deal with asteroid hitting asteroid
)
(defmethod collide-with ((x asteroid) (y spaceship))
;; deal with asteroid hitting spaceship
)
(defmethod collide-with ((x spaceship) (y asteroid))
;; deal with spaceship hitting asteroid
)
(defmethod collide-with ((x spaceship) (y spaceship))
;; deal with spaceship hitting spaceship
)

  1. aka ‘googling’