Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
{
"metadata": {
"language": "Julia",
"name": ""
},
"nbformat": 3,
"nbformat_minor": 0,
"worksheets": [
{
"cells": [
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"# The Design Impact of Multiple Dispatch\n",
"## As the core paradigm of Julia\n",
"[@StefanKarpinski](http://twitter.com/StefanKarpinski)\n",
"presented at Strange Loop on September 19, 2013"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"# What is Multiple Dispatch?\n",
"\n",
"- **dynamic** \u2014 based on actual run-time type, not static type\n",
"- **mulitple** \u2014\u00a0based on all arguments, not just the receiver\n",
"\n",
"Tends to be written as **function application**:\n",
"\n",
"- `f(a,b,c)` \u27f8 LIKE THIS\n",
"- `a.f(b,c)` \u27f8 NOT THIS"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"## Multiple Dispatch \u2260 Method Overloading\n",
"\n",
"In Java or C++ you can provide these virtual methods:\n",
"\n",
" Parent this: f(Parent that)\n",
" Parent this: f(Child that)\n",
" Child this: f(Parent that)\n",
" Child this: f(Child that)\n",
"\n",
"Dispatched on `this` but not on `that`\n",
"\n",
"- can dispatch on both using the **double dispatch** pattern\n",
"\n",
"However, quoting [Double Dispatch is a Code Smell][1]:\n",
"\n",
"> The presence of Double Dispatch generally means that each type in a hierarchy has special handling code within another hierarchy of types. This approach to representing variant behavior leads to code that is less resilient to future changes as well as being more difficult to extend.\n",
"\n",
"Something smells, but it's not necessarily the double dispatch\n",
"\n",
"- *double dispatch is only a code smell in single dispatch languages*\n",
"\n",
"[1]: http://lostechies.com/derekgreer/2010/04/19/double-dispatch-is-a-code-smell/"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"# Multiple Dispatch in Julia\n",
"\n",
"#### Basic dispatch:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"f(a::Any, b) = \"fallback\"\n",
"f(a::Number, b::Number) = \"a and b are both numbers\"\n",
"f(a::Number, b) = \"a is a number\"\n",
"f(a, b::Number) = \"b is a number\"\n",
"f(a::Integer, b::Integer) = \"a and b are both integers\""
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 1,
"text": [
"f (generic function with 5 methods)"
]
}
],
"prompt_number": 1
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"f(1.5,2)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 2,
"text": [
"\"a and b are both numbers\""
]
}
],
"prompt_number": 2
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"f(1,\"bar\")"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 3,
"text": [
"\"a is a number\""
]
}
],
"prompt_number": 3
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"f(1,2)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 4,
"text": [
"\"a and b are both integers\""
]
}
],
"prompt_number": 4
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"f(\"foo\",[1,2])"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 5,
"text": [
"\"fallback\""
]
}
],
"prompt_number": 5
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"#### \"Diagonal\" dispatch:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"f{T<:Number}(a::T, b::T) = \"a and b are both $(T)s\""
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 6,
"text": [
"f (generic function with 6 methods)"
]
}
],
"prompt_number": 6
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"f(big(1.5),big(2.5))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 7,
"text": [
"\"a and b are both BigFloats\""
]
}
],
"prompt_number": 7
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"f(big(1),big(2)) #<== integer rule is more specific"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 8,
"text": [
"\"a and b are both integers\""
]
}
],
"prompt_number": 8
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"f(\"foo\",\"bar\") #<== still doesn't apply to non-numbers"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 9,
"text": [
"\"fallback\""
]
}
],
"prompt_number": 9
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"#### Varargs methods:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"f(args::Number...) = \"$(length(args))-ary heterogeneous call\"\n",
"f{T<:Number}(args::T...) = \"$(length(args))-ary homogeneous call\""
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 10,
"text": [
"f (generic function with 8 methods)"
]
}
],
"prompt_number": 10
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"f(1)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 11,
"text": [
"\"1-ary homogeneous call\""
]
}
],
"prompt_number": 11
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"f(1,2,3)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 12,
"text": [
"\"3-ary homogeneous call\""
]
}
],
"prompt_number": 12
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"f(1,1.5,2)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 13,
"text": [
"\"3-ary heterogeneous call\""
]
}
],
"prompt_number": 13
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"f() #==> why is it heterogeneous not homogeneous?"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 14,
"text": [
"\"0-ary heterogeneous call\""
]
}
],
"prompt_number": 14
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"f(1,2) #<== previous 2-arg method is more specific"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 15,
"text": [
"\"a and b are both integers\""
]
}
],
"prompt_number": 15
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"f(\"foo\") #<== doesn't apply to non-numbers"
],
"language": "python",
"metadata": {},
"outputs": [
{
"ename": "LoadError",
"evalue": "no method f(ASCIIString,)\nat In[16]:1",
"output_type": "pyerr",
"traceback": [
"no method f(ASCIIString,)\nat In[16]:1"
]
}
],
"prompt_number": 16
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"# Multiple Dispatch in Ruby\n",
"\n",
"Arithmetic operators:\n",
"\n",
" Number + Number | String + String | Array + Array\n",
" Number - Number | Time - Time | Time - Number | Array - Array\n",
" Number * Number | Array * Integer | Array * String | String * Integer\n",
" Integer << Integer | String << String | String << Integer\n",
"\n",
"Arrays, Hashes & Strings:\n",
"\n",
" (Array|Hash).fetch(index,default|block)\n",
" (Array|Hash).new(object|block) | String.new(string)\n",
" (Array|Hash)[int|range] | String[int|range|regex|string]\n",
" (Array|Hash)[int|range]= | String[int|range|regex|string]=\n",
" Array.slice(int|range) | String.slice(int|range|regex|string)\n",
" Array.slice!(int|range) | String.slice!(int|range|regex|string)\n",
"\n",
"Just Strings:\n",
"\n",
" String.index(string|int|regex)\n",
" String.rindex(string|int|regex)\n",
" String.sub(pattern,replacement|block)\n",
" String.sub!(pattern,replacement|block)\n",
" String.gsub(pattern,replacement|block)\n",
" String.gsub!(pattern,replacement|block)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"# Multiple Dispatch in English\n",
"\n",
"Related meanings:\n",
"\n",
" \"she goes (home|away)\" go(subj::Noun, where::PlaceAdverb)\n",
" \"it went (wrong|well)\" go(subj::Noun, how::MannerAdverb)\n",
"\n",
"Default arguments:\n",
"\n",
" \"go (home|away|well)\" go(adv::Adverb) = go(Person(\"addressee\"), adv)\n",
" \"he goes\" go(subj::Noun) = go(subj, PlaceAdverb(\"somewhere\"))\n",
" \"go\" go() = go(PlaceAdverb(\"somewhere\"))\n",
"\n",
"Fragment of type hierarchy:\n",
"\n",
" Person <: Noun\n",
" PlaceAdverb <: Adverb\n",
" MannerAdverb <: Adverb"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"# Multiple Dispatch is Object-Oriented\n",
"\n",
"Not surprising that o.o. languages are emulating multiple dispatch\n",
"\n",
"- convenient, natural way to exress complex polymorphic behaviors\n",
"- and it's all about dispatch and subtyping of data\n",
"\n",
"But they're missing a really crucial ingredient\n",
"\n",
"- a bit like having `eval` without being able to manipulate code as data"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"# Generic Functions are Functional\n",
"\n",
"A generic function is a **first-class object**\n",
"\n",
"- can be passed around, e.g. to higher-order functions\n",
"- but remains extensible unlike \"classical\" functions"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"f"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 17,
"text": [
"f (generic function with 8 methods)"
]
}
],
"prompt_number": 17
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"methods(f)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 18,
"text": [
"# 8 methods for generic function \"f\":\n",
"f(a::Integer,b::Integer) at In[1]:5\n",
"f{T<:Number}(a::T<:Number,b::T<:Number) at In[6]:1\n",
"f{T<:Number}(args::T<:Number...) at In[10]:2\n",
"f(a::Number,b::Number) at In[1]:2\n",
"f(args::Number...) at In[10]:1\n",
"f(a::Number,b) at In[1]:3\n",
"f(a,b::Number) at In[1]:4\n",
"f(a,b) at In[1]:1"
]
}
],
"prompt_number": 18
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"typeof(f)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 19,
"text": [
"Function"
]
}
],
"prompt_number": 19
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"f2(x) = f(x,x)\n",
"\n",
"f2(\"foo\")"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 20,
"text": [
"\"fallback\""
]
}
],
"prompt_number": 20
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"f(a::String, b::String) = \"a and b are both strings\";\n",
"f2(x) = f(x,x) #<== to reset method cache (issue #265)\n",
"\n",
"f2(\"foo\")"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 21,
"text": [
"\"a and b are both strings\""
]
}
],
"prompt_number": 21
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"# The Expression Problem\n",
"\n",
"Mads Torgersen's paper [The Expression Problem Revisited][2]:\n",
"\n",
"> To which degree can your application be structured in such a way that both the data model and the set of virtual operations over it can be extended without the need to modify existing code, without the need for code repetition and without runtime type errors.\n",
"\n",
"[2]: http://www.daimi.au.dk/~madst/ecoop04/main.pdf\n",
"\n",
"Basically you want to be able to add:\n",
"\n",
"1. **new types** to which you can apply existing operations \u2192 easy in o.o., hard in functional\n",
"2. **new operations** which you can apply to existing types \u2192 easy in function, hard in o.o."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"# Interval Arithmetic"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"immutable Interval{T<:Real} <: Number\n",
" lo::T\n",
" hi::T\n",
"end\n",
"\n",
"(a::Real)..(b::Real) = Interval(a,b)\n",
"\n",
"Base.show(io::IO, iv::Interval) = print(io, \"($(iv.lo))..($(iv.hi))\")"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 22,
"text": [
"show (generic function with 96 methods)"
]
}
],
"prompt_number": 22
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"1..2"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 23,
"text": [
"(1)..(2)"
]
}
],
"prompt_number": 23
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"typeof(ans)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 24,
"text": [
"Interval{Int64} (constructor with 1 method)"
]
}
],
"prompt_number": 24
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"sizeof(1..2) #==> two 8-byte ints"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 25,
"text": [
"16"
]
}
],
"prompt_number": 25
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"(1.5)..(2.5)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 26,
"text": [
"(1.5)..(2.5)"
]
}
],
"prompt_number": 26
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"typeof(ans)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 27,
"text": [
"Interval{Float64} (constructor with 1 method)"
]
}
],
"prompt_number": 27
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"(1//2)..(2//3)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 28,
"text": [
"(1//2)..(2//3)"
]
}
],
"prompt_number": 28
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"typeof(ans)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 29,
"text": [
"Interval{Rational{Int64}} (constructor with 1 method)"
]
}
],
"prompt_number": 29
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"sizeof((1//2)..(2//3)) #==> just four 8-byte ints"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 30,
"text": [
"32"
]
}
],
"prompt_number": 30
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"#### Allowing end-points of different types"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"methods(Interval)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 31,
"text": [
"# 1 method for generic function \"Interval\":\n",
"Interval{T<:Real}(lo::T<:Real,hi::T<:Real)"
]
}
],
"prompt_number": 31
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"#(0.5)..(1) #<== would be a no method error because of\u00a0mixed types"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 32
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"Interval(lo::Real, hi::Real) = Interval(promote(lo,hi)...)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 33,
"text": [
"Interval{T<:Real} (constructor with 2 methods)"
]
}
],
"prompt_number": 33
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"(0.5)..1"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 34,
"text": [
"(0.5)..(1.0)"
]
}
],
"prompt_number": 34
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"1..pi"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 35,
"text": [
"(1.0)..(3.141592653589793)"
]
}
],
"prompt_number": 35
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"e..pi"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 36,
"text": [
"(2.718281828459045)..(3.141592653589793)"
]
}
],
"prompt_number": 36
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"#### Extending the `+` and `-` operators\n",
"\n",
"Adding and subtracting intervals:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"a::Interval + b::Interval = (a.lo + b.lo)..(a.hi + b.hi)\n",
"a::Interval - b::Interval = (a.lo - b.hi)..(a.hi - b.lo)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 37,
"text": [
"- (generic function with 107 methods)"
]
}
],
"prompt_number": 37
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"(2..3) + (-1..1)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 38,
"text": [
"(1)..(4)"
]
}
],
"prompt_number": 38
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"(2..3) - (1..2)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 39,
"text": [
"(0)..(2)"
]
}
],
"prompt_number": 39
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"What about arithmetic mixing intervals and numbers?\n",
"\n",
"- It's tempting to implement start implementing all combinations\n",
"- However, there's a better, more \"Julian\" way.\n",
"\n",
"Instead, we'll hook `Intervals` into Julia's promotion system:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"import Base: convert, promote_rule #<== allows extending them\n",
"\n",
"convert{T<:Real}(::Type{Interval{T}}, x::Real) = (x = convert(T,x); x..x)\n",
"convert{T<:Real}(::Type{Interval{T}}, iv::Interval) =\n",
" convert(T,iv.lo)..convert(T,iv.hi)\n",
"\n",
"promote_rule{A<:Real,B<:Real}(::Type{Interval{A}}, ::Type{B}) = \n",
" Interval{promote_type(A,B)}\n",
"promote_rule{A<:Real,B<:Real}(::Type{Interval{A}}, ::Type{Interval{B}}) =\n",
" Interval{promote_type(A,B)}"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 40,
"text": [
"promote_rule (generic function with 126 methods)"
]
}
],
"prompt_number": 40
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Presto! Everything now Just Works\u2122:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"1..2 + 1"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 41,
"text": [
"(2)..(3)"
]
}
],
"prompt_number": 41
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"1..2 + 1.5"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 42,
"text": [
"(2.5)..(3.5)"
]
}
],
"prompt_number": 42
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"3 - 1..2 + 2//3"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 43,
"text": [
"(5//3)..(8//3)"
]
}
],
"prompt_number": 43
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"big(2)^100 + (1//3)..(2//3)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 44,
"text": [
"(3802951800684688204490109616129//3)..(3802951800684688204490109616130//3)"
]
}
],
"prompt_number": 44
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"#### Wait? What's going on here?\n",
"\n",
"Let's examine the last computation in detail:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"big(2)^100 + (1//3)..(2//3)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 45,
"text": [
"(3802951800684688204490109616129//3)..(3802951800684688204490109616130//3)"
]
}
],
"prompt_number": 45
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"typeof(ans)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 46,
"text": [
"Interval{Rational{BigInt}} (constructor with 1 method)"
]
}
],
"prompt_number": 46
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"@which big(2)^100 + (1//3)..(2//3)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"+("
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"x::Number,y::Number) at promotion.jl:148\n"
]
}
],
"prompt_number": 47
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The left-hand-side is a `BigInt`:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"big(2)^100"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 48,
"text": [
"1267650600228229401496703205376"
]
}
],
"prompt_number": 48
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"typeof(ans)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 49,
"text": [
"BigInt (constructor with 7 methods)"
]
}
],
"prompt_number": 49
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The right-hand-side is an interval of rationals of 64-bit integers:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"typeof((1//3)..(2//3))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 50,
"text": [
"Interval{Rational{Int64}} (constructor with 1 method)"
]
}
],
"prompt_number": 50
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"There are no methods for adding these specific types\n",
"\n",
"- a very general fallback method defined for adding numbers is called\n",
"\n",
"This method is defined in `base/promote.jl`:\n",
"\n",
" +(x::Number, y::Number) = +(promote(x,y)...)\n",
"\n",
"The `promote` function for two arguments looks like this:\n",
"\n",
" promote{T,S}(x::T, y::S) =\n",
" (convert(promote_type(T,S),x), convert(promote_type(T,S),y))\n",
"\n",
"where `promote_type` is defined in terms of `promote_rule` \u2014\u00a0it's a bit complicated.\n",
"\n",
"Now, the following promotion rules exist:\n",
"\n",
"```\n",
"promote_rule{A<:Real,B<:Real}(::Type{Interval{A}}, ::Type{B}) = \n",
" Interval{promote_type(A,B)}\n",
"\n",
"promote_rule{A<:Integer,B<:Integer}(::Type{Rational{A}}, ::Type{B}) =\n",
" Rational{promote_type(A,B)}\n",
"\n",
"promote_rule{T<:Integer}(::Type{BigInt}, ::Type{T}) = BigInt\n",
"```\n",
"\n",
"These all kick in when computing `promote_type`, producing this result:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"promote_type(Interval{Rational{Int64}}, BigInt)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 51,
"text": [
"Interval{Rational{BigInt}} (constructor with 1 method)"
]
}
],
"prompt_number": 51
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"So `promote` converts both `big(2)^100` and `(1//3)..(2//3)` to `Interval{Rational{Int64}}`:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"convert(Interval{Rational{BigInt}}, big(2)^100)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 52,
"text": [
"(1267650600228229401496703205376//1)..(1267650600228229401496703205376//1)"
]
}
],
"prompt_number": 52
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"convert(Interval{Rational{BigInt}}, (1//3)..(2//3))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 53,
"text": [
"(1//3)..(2//3)"
]
}
],
"prompt_number": 53
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"After that adding them is just a call to the `+` method for same-typed `Intervals`."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"#### Defining a new \u00b1 operator\n",
"\n",
"The syntax for \u00b1 already exists in the parser, but its behavior is undefined:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
":(2 \u00b1 1)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 54,
"text": [
":(\u00b1(2,1))"
]
}
],
"prompt_number": 54
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"2 \u00b1\u00a01"
],
"language": "python",
"metadata": {},
"outputs": [
{
"ename": "LoadError",
"evalue": "\u00b1 not defined\nat In[55]:1",
"output_type": "pyerr",
"traceback": [
"\u00b1 not defined\nat In[55]:1"
]
}
],
"prompt_number": 55
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let's define it:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"a::Real \u00b1 b::Real = (a - b)..(a + b)\n",
"a::Interval \u00b1 b::Interval = (a.lo - b.hi)..(a.hi + b.hi)\n",
"a::Number \u00b1\u00a0b::Number = \u00b1(promote(a,b)...)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 56,
"text": [
"\u00b1 (generic function with 3 methods)"
]
}
],
"prompt_number": 56
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"1 \u00b1 2"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 57,
"text": [
"(-1)..(3)"
]
}
],
"prompt_number": 57
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"pi - (2 \u00b1 1//2)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 58,
"text": [
"(0.6415926535897931)..(1.6415926535897931)"
]
}
],
"prompt_number": 58
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Notice that:\n",
"\n",
"- hooking into the promotion system requires a bit of thought\n",
"- but it's a one-time cost \u2013\u00a0adding new promoting operations is easy\n",
"- types can work together smoothly without knowing about each other"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"## Interval Arithmetic Recap\n",
"\n",
"#### Basic type definition\n",
"\n",
" immutable Interval{T<:Real} <: Number\n",
" lo::T\n",
" hi::T\n",
" end\n",
" Interval(lo::Real, hi::Real) = Interval(promote(lo,hi)...)\n",
" \n",
" (a::Real)..(b::Real) = Interval(a,b)\n",
" \n",
" Base.show(io::IO, iv::Interval) = print(io, \"($(iv.lo))..($(iv.hi))\")\n",
" \n",
"#### Conversion & promotion rules\n",
"\n",
" import Base: convert, promote_rule\n",
" \n",
" convert{T<:Real}(::Type{Interval{T}}, x::Real) = (x = convert(T,x); x..x)\n",
" convert{T<:Real}(::Type{Interval{T}}, iv::Interval) =\n",
" convert(T,iv.lo)..convert(T,iv.hi)\n",
" \n",
" promote_rule{A<:Real,B<:Real}(::Type{Interval{A}}, ::Type{B}) = \n",
" Interval{promote_type(A,B)}\n",
" promote_rule{A<:Real,B<:Real}(::Type{Interval{A}}, ::Type{Interval{B}}) =\n",
" Interval{promote_type(A,B)}\n",
" \n",
"#### Core arithmetic\n",
"\n",
" a::Interval + b::Interval = (a.lo + b.lo)..(a.hi + b.hi)\n",
" a::Interval - b::Interval = (a.lo - b.hi)..(a.hi - b.lo)\n",
" \n",
" a::Real \u00b1 b::Real = (a - b)..(a + b)\n",
" a::Interval \u00b1 b::Interval = (a.lo - b.hi)..(a.hi + b.hi)\n",
" a::Number \u00b1\u00a0b::Number = \u00b1(promote(a,b)...)\n",
"\n",
"Generic functions elegantly and smoothly solve the expression problem:\n",
"\n",
" - new `Interval` type works with built-in `+` and `-` operators\n",
" - new `\u00b1` operator works with built-in `Int` type"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"# Taking Multiple Dispatch Seriously\n",
"\n",
"Generic function in Julia aren't special \u2013\u00a0they're the default\n",
"\n",
"- even really basic things like `+` are generic functions"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"+"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 59,
"text": [
"+ (generic function with 96 methods)"
]
}
],
"prompt_number": 59
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This means you're free to extend *everything*\n",
"\n",
"- not just functions that were planned to be extended"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"# Performance"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"code_llvm(+,(Int,Int))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"\n",
"define i64 @\"julia_+2202\"(i64, i64) {\n",
"top:\n",
" %2 = add i64 %1, %0, !dbg !10575\n",
" ret i64 %2, !dbg !10575\n",
"}\n"
]
}
],
"prompt_number": 60
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"code_llvm(+,(Int,Float64))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"\n",
"define double @\"julia_+2208\"(i64, double) {\n",
"top:\n",
" %2 = sitofp i64 %0 to double, !dbg !10605\n",
" %3 = fadd double %2, %1, !dbg !10605\n",
" ret double %3, !dbg !10605\n",
"}\n"
]
}
],
"prompt_number": 61
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"## User Code is Also Fast\n",
"\n",
"Let's define a scalar-valued function using the `Interval` type we just defined:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"lo(a,b) = (a \u00b1 b).lo\n",
"hi(a,b) = (a \u00b1 b).hi"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 62,
"text": [
"hi (generic function with 1 method)"
]
}
],
"prompt_number": 62
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"lo(3,2), hi(3,2)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 63,
"text": [
"(1,5)"
]
}
],
"prompt_number": 63
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"code_llvm(lo,(Int,Int))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"\n",
"define i64 @julia_lo2227(i64, i64) {\n",
"top:\n",
" %2 = sub i64 %0, %1, !dbg !10684\n",
" ret i64 %2, !dbg !10684\n",
"}\n"
]
}
],
"prompt_number": 64
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"code_llvm(hi,(Int,Int))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"\n",
"define i64 @julia_hi2228(i64, i64) {\n",
"top:\n",
" %2 = add i64 %1, %0, !dbg !10690\n",
" ret i64 %2, !dbg !10690\n",
"}\n"
]
}
],
"prompt_number": 65
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Even for complex combinations of types, generated code is very efficient:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"code_native(hi,(Float64,Rational{Int}))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"\t.section\t__TEXT,__text,regular,pure_instructions\n",
"Filename: In[62]\n",
"Source line: 2\n",
"\tpush\tRBP\n",
"\tmov\tRBP, RSP\n",
"Source line: 2\n",
"\tvcvtsi2sd\tXMM1, XMM0, RSI\n",
"\tvcvtsi2sd\tXMM2, XMM0, RDI\n",
"\tvdivsd\tXMM1, XMM2, XMM1\n",
"\tvaddsd\tXMM0, XMM1, XMM0\n",
"\tpop\tRBP\n",
"\tret\n"
]
}
],
"prompt_number": 66
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"# Design Impact\n",
"\n",
"Since generic functions are **open**:\n",
"\n",
"- functions are more like *protocols* which users can also implement\n",
"\n",
"We're forced to think much harder about the **meaning** of opearations\n",
"\n",
"- can't just describe their behavior.\n",
"\n",
"Example:\n",
"\n",
"> `search(string, pattern, [start])`\n",
"> \n",
"> Search for the first occurance of the given pattern within the given string (or byte array). The pattern may be a single character, a vector or a set of characters, a string, or a regular expression (regular expressions are only allowed on contiguous strings, such as ASCII or UTF-8 strings). The third argument optionally specifies a starting index. The return value is a range of indexes where the matching sequence is found, such that `s[search(s,x)] == x`. The return value when the pattern is not found is `0` when the pattern is a character, or `0:-1` when searching for a substring or regular expression match."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"# Meaning is Hard but Powerful\n",
"\n",
"The `split` function is defined generically in terms of the `search` abstraction:\n",
"\n",
"```\n",
"function split(str::String, splitter, limit::Integer, keep_empty::Bool)\n",
" strs = String[]\n",
" i = start(str)\n",
" n = endof(str)\n",
" r = search(str,splitter,i)\n",
" j, k = first(r), nextind(str,last(r))\n",
" while 0 < j <= n && length(strs) != limit-1\n",
" if i < k\n",
" if keep_empty || i < j\n",
" push!(strs, str[i:prevind(str,j)])\n",
" end\n",
" i = k\n",
" end\n",
" if k <= j; k = nextind(str,j) end\n",
" r = search(str,splitter,k)\n",
" j, k = first(r), nextind(str,last(r))\n",
" end\n",
" if keep_empty || !done(str,i)\n",
" push!(strs, str[i:])\n",
" end\n",
" return strs\n",
"end\n",
"split(s::String, spl, n::Integer) = split(s, spl, n, true)\n",
"split(s::String, spl, keep::Bool) = split(s, spl, 0, keep)\n",
"split(s::String, spl) = split(s, spl, 0, true)\n",
"```\n",
"\n",
"This gives the ability to:\n",
"\n",
"- create a new pattern type for matching patterns in strings\n",
" - e.g. context-free grammars, etc.\n",
"- define `search(str, pattern)` for the new pattern\n",
" - get `split` functionality for free"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"### Example: spliting on regular expressions\n",
"\n",
"Regex doesn't know anything about `split`:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"methods(split)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 67,
"text": [
"# 5 methods for generic function \"split\":\n",
"split(str::String,splitter,limit::Integer,keep_empty::Bool) at string.jl:1250\n",
"split(s::String,spl,keep::Bool) at string.jl:1272\n",
"split(s::String,spl,n::Integer) at string.jl:1271\n",
"split(s::String,spl) at string.jl:1273\n",
"split(str::String) at string.jl:1277"
]
}
],
"prompt_number": 67
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Yet split works when with `Regex` patterns:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"split(\"foobarbazqux\", r\"[aeiou]+\"i)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 68,
"text": [
"5-element Array{String,1}:\n",
" \"f\" \n",
" \"b\" \n",
" \"rb\"\n",
" \"zq\"\n",
" \"x\" "
]
}
],
"prompt_number": 68
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Works because `Regex` provides the `search` function\n",
"\n",
"- and `split` is defined generically in terms of `search`"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"## We're Not There Yet\n",
"\n",
"Meaning is hard and there are a lot of \"protocols\" that we still need to abstract out.\n",
"\n",
"- There are separate `plot` functions in every plotting package\n",
"- Ideally, there should be a single commong `plot` function\n",
"\n",
"These kinds of abstract protocols are \"narrow waists\"\n",
"\n",
"- like TCP/IP in networking or byte streams in UNIX\n",
"\n",
"Figuring out the right ones is hard but essential work."
]
}
],
"metadata": {}
}
]
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment