Devoxx France@DevoxxFR / #DevoxxFR

Survival guide - Programming Languages Theory

#me

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!

Agenda

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

Assumption

  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

Specification

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

Simplicity

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?

Security

Hoare's principles

This lead us to Correctness

Correctness

Readability

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

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

Hoare

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

Modularity

Abstraction

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

Paradigm

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

Scripting

Declarative programming style

Logic programming

parent(bill,mary).
parent(mary,john).
ancestor(X,Y) :- parent(X,Y).
ancestor(X,Y) :- parent(X,Z),ancestor(Z,Y).

Datalog

On Languages

Language

Syntax

Semantics

what about

Parsing

How to parse

Formal Grammar

Abstract Syntax Tree

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

Semantics

Commonalities in Programming Languages

Variables

// 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()
  computation
  println(System.currentTimeMillis() - timestamp)
}

time(Thread.sleep(2000))

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

(im)mutability

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

remarks

in practice

Functional programming

Disclaimer

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

You should buy his book Functional Programming in Scala

Programming with Functions

Function

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
  println(reverseOnce.toString())
  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

map

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

foldLeft

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

Object Oriented Programming

Objects

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

Abstraction

General

In the case of objects

Subtyping / substitutibity

Inheritance

Virtual method / overriding

Semantics of super

Virtual method table

Class

Multiple inheritence and diamond problem

Diamond problem

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

Mixins

Mixins example

taken from Programming in Scala

linearization

Prototypes

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):
    self.data = []

Static methods

Bridging the gap between FP and OOP

Types

Types

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

Inference

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

Alternatives

Lying with Types

Effects

Examples

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

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))
}

Variance

Higher-Kinded Types

Typeclass

import java.util.Comparator

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

def max2[T](l: List[T])(implicit comparator: Comparator[T]): Option[T] =
  l.reduceLeftOption{ (x, y) => if (comparator.compare(x, 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 (comparator.compare(x, 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().withTomato.build() // 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 }
}

PizzaBuilder().withTomato.build()

Types at runtime

Dependent Types

Singleton Types

Self Types

class Foo() { ... }

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

val foobar = new Foo() with Bar

HList

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

← →

/

#