Devoxx France@DevoxxFR / #DevoxxFR

Survival guide - Programming Languages Theory


Why this talk?

One of the challenges that I face today is to make programmers believe that learning new stuff will only help them think better. It's not mandatory that they will need all of these tools as part of their day job. But broadening your mental model can only help your thought process to leverage a wider playground.

Debasish Ghosh, It's the familiarity model!


Theoritical Foundations

Computer Science and Philosophy

What philosophy gave us

What philosophy can teach us

Finding your way among alternatives 1/2

[...] engineering design is a social process [...] When there are alternatives, [Bucciarelli] says, then there can be better and worse. In such a situation, "The really important and interesting question becomes: What do we mean by a better design?"

Bucciarelli (1994), p. 197

Finding your way among alternatives 2/2

Alternatives and choice


  1. There is more than one truth
  2. What to do when the inherent philosophy of a language is not enough for solving a given problem?

Defining main concepts

What's in a Language


Connected concepts

What's in a Program?

Q: what's more important, the calculation or its result? Are you declarative or procedural?

My definition: Programming is about transforming a specification into phrases that could be understood by a machine.

The nature of Programming

"natural" programming style

A Social Aspect to Programming

Starts at school, with pedagogy

Social pressure and local culture

Culture and Environment

the former imposes the later

lttle research on what matters

The Tasks of Programming

programming subtasks

Q: do people actually take those into accounts?

Programming is a complex cognitive and social task: need for abstraction

Language Design and Acquisition of Programming

Evolution implies changes in truth, because we have a better understanding of the problems

started with ingeneers/hackers

moved in the hands of theoricians

what we see today

On Language design

Language design

Good language design may be summarized in five catch phrases: simplicity, security, fast translation, efficient object code, and readability. [...] Many language designers have adopted alternative principles.

Hoare, 73


Obviously related to syntax!

Orthogonality and Complexity

In a truly orthogonal language, a small set of basic facilities may be combined without arbitrary restrictions according to systematic rules.

M. Petre, Expert Programmers and Programming Languages

Q: is Scala complex or difficult?


Hoare's principles

This lead us to Correctness



Programs are read by people: the language should encouraged clarity, hence:

The readability of programs is immeasurably more important than their writability.


Authors choose stylistics factors commonly thought to influence style with little or no supporting evidence demonstrating the importance of effect of that characteristic on program comprehension and maintainability.

Homan and Cook, 88

Clarity of structure



The influence of the programming language on programming

Vehiculing meaning

The highest goal of programming language design [is] to enable good ideas to be expressed

Hoare, 81

I view a programming language as a vehicule for the description of (potentially highly sophisticated) abstract mechanisms.

Dijsktra, 76

The goal should be: language design should not influence thinking but reflect it clearly

On Programming Paradigms


A paradigm is what members of a scientific community, and they alone, share.

Thomas Khun, The Essential Tension, 1977

Imperative programming style

usually related to

Procedural Programming


Declarative programming style

Logic programming

ancestor(X,Y) :- parent(X,Y).
ancestor(X,Y) :- parent(X,Z),ancestor(Z,Y).


On Languages




what about


How to parse

Formal Grammar

Abstract Syntax Tree

    Add(Int(1), Int(2))
  Call("println", "true"),
  Call("println", "false"))


Commonalities in Programming Languages


// Java
String i;
i = "foo";
i = "bar";

// Scala
val i = new java.lang.StringBuilder("foo")
i = new java.lang.StringBuilder("foobar") // not valid
i.append("bar") // valid

// PHP
$i // the value depends on the context

Lazy evaluation 1/2

def time(computation: => Unit) = {
  val timestamp = System.currentTimeMillis()
  println(System.currentTimeMillis() - timestamp)


Lazy evaluation 2/2

Sometimes I searched eight hours for the source of a space leak. Other times I had to really dig around the internet to learn how to force a computation so that I could measure the time of said computation.

Eugen Kiss, The Functional View of the New Languages


can be achieved

Q: What about your favorite language?

Immutable data-structure 1/4

sealed trait ListInt

case class Node(i: Int, next: ListInt) extends ListInt

case class Empty() extends ListInt

def concat(l1: ListInt, l2: ListInt): ListInt = l1 match {
  case Empty() => l2
  case Node(i, next) => Node(i, concat(next, l2))

Immutable data-structure 2/4

concat list before

Immutable data-structure 3/4

concat list after

Immutable data-structure 4/4


in practice

Functional programming


Shamelessly stolen from Rúnar's Guerilla Guide to Functional Programming

You should buy his book Functional Programming in Scala

Programming with Functions


A function f: A => B relates every value of type A to exactly one value of type B

A partial function is the same but for a subset of A

no side-effect

Referential Transparency

An expression e is referentially transparent if for every program p every occurrence of e in p can be replaced with the value of e without affecting the observable result of p.

A function f is pure if the expression f(x) is referentially transparent for all referentially transparent x.

Referential Transparency - example 1/3

val e1 = "scala"
val e2 = e1.reverse
val e3 = e2.reverse
val e4 = e1 + e2 + e3

Referential Transparency - example 2/3

val e2 = "scala".reverse
val e3 = e2.reverse
val e4 = "scala" + e2 + e3

Referential Transparency - example 3/3

val e4 = "scala" + "alacs" + "scala"

Benefits of being pure

Q: Is this pure?

def reverseTwice(l: List[Int]): List[Int] = {
  val reverseOnce = l.reverse
  val reverseAgain = reverseOnce
  return reverseAgain
def sum(l: List[Int]): Int = {
  var acc = 0
  for {
    i <- 0 to (l.size - 1)
  } acc += l(i)
  return acc

Are there limits to being pure?

Everything is an expression

Higher-order function

A higher-order function is a function that takes other functions as input.

val isOdd: Int => Boolean = { x: Int => x % 2 == 0 }

// List(0, 2, 4, 6, 8, 10)  
val odd_numbers = (0 to 10).toList.filter(isOdd)

Functional patterns


List(a, b, c).map(f) == List(f(a), f(b), f(c))


List(a, b, c).foldLeft(x)(f) == f(f(f(x, a), b, c))

Object Oriented Programming


Objects in the real world have only one thing in common -- they are all different.

Antero Taivalsaari, Classes vs. Prototypes Some Philosophical and Historical Observations

Main concepts

Dynamic lookup

Dynamic lookup =? overloading



In the case of objects

Subtyping / substitutibity


Virtual method / overriding

Semantics of super

Virtual method table


Multiple inheritence and diamond problem

Diamond problem

Fantom's way to solve it: name restriction to avoid collision


Mixins example

taken from Programming in Scala



Philosophical considerations on Objects

OOP is hard(er than you think)

and you probably get it wrong

Comparing concepts

Implementation details

Objects in Python

class MyClass:
  """A simple example class"""
  i = 12345
  def f(self):
    return 'hello world'
  def __init__(self): = []

Static methods

Bridging the gap between FP and OOP



A type indicates a set of values that have the same sort of generic meaning or intended purpose

Some types, such as abstract types and function types, might not be represented as values in the running computer program.

Types can be annotated or inferred.

Type System

A type system defines

Type Checker

A type checker verifies if an expression has a type that belongs to the type system


An inference engine

What's in a name? static and dynamic

Let's ask the public :-)

And what about strong vs weak?

Static / dynamic type system

static type system

dynamic type system

the static-vs-dynamic drama

Chris Smith, What To Know Before Debating Type Systems

Critics about being Static or Dynamic 1/2

[Types] are mainly good for documentation — documentation for both man and machine. The idea that they make your programs more reliable is a myth.

Gilad Bracha, Software Engineering Radio, episode 140

Critics about being Static or Dynamic 2/2

[...] what type-checkers do is they attempt to prove that your program conforms to the type system. The type system guarantees you that, if you conform to it, certain types of bad thing won’t happen. That doesn’t mean that if you don’t conform to it bad things will happen. They do not prove that your program is bad; they prove that your program isn’t good, according to their definition of good.

Gilad Bracha, Software Engineering Radio, episode 140


Lying with Types



Type System: expressivity and limits

Static Analysis

Type safety

You know, maybe the dynamic crowd just wants freedom to not have to think as carefully about what they're doing. The software might not be correct or robust, but maybe it doesn't have to be.

Rúnar Bjarnason

Q: Are types enough to achieve safety? Is testing a mandatory phase in any programming language?

Proofs and Types


Polymorphism: how to achieve it

Polymorphism, literally means “having multiple forms”, refers to constructs that can take on different types as needed.

Dynamically typed languages support all kind of polymorphism by definition.

Parametric polymorphism

reverse : 'a list -> 'a list

Ad-hoc polymorphism@@

Subtype polymorphism

When a function takes a value of type T, and that S is a subtype for T, then we can apply the substitution principle.

Liskov substitution principle

The Liskov Substitution Principle defines that a subtype may be substituted for a super type and the behavior remains unchanged.

Let q(x) be a property provable about objects x of type T. Then q(y) should be provable for objects y of type S where S is a subtype of T.

B. Liskov and J. Wing, 94

counter-example: Rectangle / Square, getter / setter / area

Programming with Types

void / Unit

Structural Type

Union Type

instanceOfUnionType match {
  case o: SomeType => ...
  case o: SomeType(x, y, z) => ...

oh, wait, I'm told that Scala type system is powerful enough to encode unboxed Union Types :-)

Intersection Type

T extends Foo & Bar

Algebraic Data Type

case class Foo(s: String, i: Int)

class Bar(val s: String, val i: Int)

object Bar {
  def unapply(bar: Bar): Option[(String, Int)] =
    Some((bar.s, bar.i))


Higher-Kinded Types


import java.util.Comparator

def max1[T](l: List[T], comparator: Comparator[T]): Option[T] =
  l.reduceLeftOption{ (x, y) => if (, y) < 0) x else y }

def max2[T](l: List[T])(implicit comparator: Comparator[T]): Option[T] =
  l.reduceLeftOption{ (x, y) => if (, y) < 0) x else y }

implicit val intComparator = new Comparator[Int] {
  def compare(i: Int, j: Int) = i - j

max2(List(1, 2, 3))

def max3[T : Comparator](l: List[T]): Option[T] = {
  val comparator = implicitly[Comparator[T]]
  l.reduceLeftOption{ (x, y) => if (, y) < 0) x else y }

Phantom Types

Phantom Type - example 1/3

class Pizza()

class PizzaBuilder() {
  def withTomato = new PizzaBuilder()
  def build() = new Pizza()

object PizzaBuilder {
  def apply() = new PizzaBuilder

val pizza = PizzaBuilder().build()

Phantom Type - example 2/3

class Pizza()

trait TRUE
trait FALSE

class PizzaBuilder[HasTomato] private () {
  def withTomato = new PizzaBuilder[TRUE]()
  def build()(implicit ev: HasTomato =:= TRUE) = new Pizza()

object PizzaBuilder {
  def apply() = new PizzaBuilder[FALSE]

PizzaBuilder().build() // Cannot prove that FALSE =:= TRUE
PizzaBuilder() // OK

Phantom Type - example 3/3

class Pizza()

trait TRUE
trait FALSE

class PizzaBuilder private () {
  type HasTomato
  def withTomato = new PizzaBuilder() { type HasTomato = TRUE }
  def build()(implicit ev: HasTomato =:= TRUE) = new Pizza() { type HasTomato = TRUE }

object PizzaBuilder {
  def apply() = new PizzaBuilder() { type HasTomato = FALSE }


Types at runtime

Dependent Types

Singleton Types

Self Types

class Foo() { ... }

trait Bar { this: Foo => ... }

val foobar = new Foo() with Bar


A HList with a List with heterogenous types, but still supports the usual operations (map, head, tail, etc.)

trait Fruit
case class Apple() extends Fruit
case class Pear() extends Fruit

type FFFF = Fruit :: Fruit :: Fruit :: Fruit :: HNil
type APAP = Apple :: Pear :: Apple :: Pear :: HNil

val a : Apple = Apple()
val p : Pear = Pear()

val apap : APAP = a :: p :: a :: p :: HNil
val ffff : FFFF = apap  // APAP <: FFFF 

Revisiting the visitor pattern

Demo! Remember all we learnt about ADT, dispatch, higher-order function