Lazy evaluation illustrated
for Haskell divers
Takenobu T.
Rev. 0.01.0
exploring some mental models and implementations
WIP
Lazy,...
..., It’s fun!
NOTE
- Meaning of terms are different for each community.
- There are a lot of good documents. Please see also references.
- This is written for GHC’s Haskell.
1. Introduction
- Basic mental models
- Lazy evaluation
- Simple questions
2. Expressions
- Expression and value
- Expressions in Haskell
- Classification by values and forms
- WHNF
3. Internal representation of expressions
- Constructor
- Thunk
- Uniform representation
- WHNF
- let, case expression
4. Evaluation
- Evaluation strategies
- Evaluation in Haskell (GHC)
- Examples of evaluation steps
- Examples of evaluations
- Controlling the evaluation
5. Implementation of evaluator
- Lazy graph reduction
- STG-machine
6. Semantics
- Bottom
- Strict/Non-strict
- Lifted and boxed types
- Strictness analysis
- Sequential order
7. Appendix
- References
Contents
1. Introduction
Basic mental models
1. Introduction
How to evaluate a program in your brain ?
a program
code
code
code
:
How to evaluate (execute, reduce) the program in your brain?
What “mental model” do you have?
？
1. Introduction
One of the mental models for C program
main (...) {
code..
code..
code..
code..
}
？
A sequence of statements
How to evaluate (execute, reduce) the program in your brain?
What step, what order, ... ?
x = func1( func2( a ) );
y = func1( a(x), b(x), c(x) );
z = func1( m + n );
A nested structure
A sequence of arguments
A function and arguments
？
？
？
C program
1. Introduction
One of the mental models for C program
main (...) {
code..
code..
code..
code..
}
A program is a collection of statements.
Statements are
executed downward.
x = func1( func2( a ) );
from inner to outer
y = func1( a(x), b(x), c(x) );
from left to right
z = func1( m + n );
arguments first
apply second
Each programmer has some mental models in their brain.
A sequence of statements A nested structure
A sequence of arguments
A function and arguments
C program
1. Introduction
One of the mental models for C program
This is a syntactically straightforward model for programming languages.
Maybe, You have some implicit mental model in your brain for C program.
(1) A program is a collection of statements.
(2) There is the order between evaluations of elements.
(3) There is the order between termination and start of evaluations.
termination
start
termination
code..
code..
code..
code..
x = func1( func2( a ) ); func1( a(x), b(x), c(x) ); z = func1( m + n );
code..
code..
func1( func2( a ) );
start
(an implicit sequential order model)
1. Introduction
One of the mental models for Haskell program
How to evaluate (execute, reduce) the program in your brain?
What step, what order, ... ?
Haskell program
main = exp
aa
(exp
ab
exp
ac
exp
ad
)
exp
ac
= exp
aca
exp
acb
exp
ad
= exp
ada
exp
adb
exp
adc
:
？
1. Introduction
One of the mental models for Haskell program
main = exp
aa
(exp
ab
exp
ac
exp
ad
)
exp
ac
= exp
aca
exp
acb
exp
ad
= exp
ada
exp
adb
exp
adc
:
A entire program is regarded as a single expression.
The subexpression is evaluated (reduced) in some order.
The evaluation is performed by replacement.
main
exp
aa
exp
ab
exp
ac
exp
ad
exp
ada
exp
adb
exp
adc
exp
aca
exp
acb
Haskell program
A program is a collection of expressions.
main = exp
aa
(exp
ab
(exp
aca
exp
acb
) (exp
ada
exp
adb
exp
adc
) )
1. Introduction
One of the mental models for Haskell program
(1) A program is a collection of expressions.
(2) A entire program is regarded as a single expression.
(3) The subexpressions are evaluated (reduced) in some order.
main = e (e (e (e e) e (e e e) ) )
(4) The evaluation is performed by replacement.
f = e (e (e (e e) e (e e e) ) )
This is an example of an expression reduction model for Haskell.
1. Introduction
3+2 5
+ 3 2
Lazy evaluation
1. Introduction
To manipulate streames
pure is order free
2nd Church-Rosser theorem
...
fun
reactive
References : [H4], [H3], [B2], [B7], [B8], [D2], [D12], [D13], [D14]
Why lazy evaluation?
To manipulate infinite data structures
To manipulate huge data structures
potentially parallelism
out-of-order optimization
asynchronization
modularity
To implement non-strict semantics
There are various reasons
To avoid unnecessary computation
abstraction
amortizing
1. Introduction
References : [B2] Ch.7, [H4] Ch.11, 12, [D2]
Haskell(GHC) ‘s lazy evaluation
+
evaluate only when needed
evaluate only enough
+
evaluate at most once
need
eval
eval
need
eval
need
no re-eval
Lazy evaluation
“Lazy” is “delay and avoidance” rather than “delay”.
1. Introduction
+
+
References : [B2] Ch.7, [H4] Ch.11, 12, [D2]
Ingredient of Haskell(GHC) ‘s lazy evaluation
at most once
substitute pointers
update redex root with result
WHNF
evaluate
an expression
a value
only when needed normal order reduction
only enough
stop at WHNF
This strategy is implemented by lazy graph reduction.
1. Introduction
References : [B2] Ch.7, [H4] Ch.2, 11, 12, 15, [H5], [D2]
Techniques of Haskell(GHC) ‘s lazy evaluation
evaluate
only when needed
evaluate
at most once
evaluate
only enough
self-updating model
lazy constructor
normal order reduction
(leftmost outermost reduction)
call-by-need
substitute pointers
full laziness
stop at WHNF
pattern-matching
lazy graph reduction
thunk
update redex root with result
1. Introduction
Simple questions
1. Introduction
References : [H4] Ch.2, 11, [B6] Ch.5
What order?
An expression is evaluated by normal order (leftmost outermost redex first).
exp
0
exp
1
exp
2
exp
n
...
an expression
To avoid unnecessary computation, normal order reduction chooses to apply the function
rather than first evaluating the argument.
Normal order reduction guarantees to find a normal form (if one exists).
1. Introduction
How to postpone?
To postpone the evaluation, an unevaluated expression is built in the heap memory.
exp
0
(exp
1
exp
2
exp
3
)
heap memory
exp
1
exp
2
exp
3
Haskell code
an unevaluated expression
build/allocate
References : [H4], [H5]
1. Introduction
thunk
When needed?
Pattern-matching or forcing request drive the evaluation.
heap memory
exp
1
exp
2
exp
3
pattern-matching
an unevaluated expression
evaluation request
case x of
Just _ -> True
Nothing -> False
seq x y
f $! arg
forcing request
x + y
built-in (primitive operation)
References : [H4], [D2], [D5]
1. Introduction
:
:
References : [H4], [D2], [D5]
What to be careful about?
You can avoid the pitfalls by controlling the evaluation.
To consider hidden space leak
To consider performance cost to postpone unevaluated expressions
To consider evaluation (execution) order and timing in real world
heap
memory
heap
memory
build, force,
update, gc, ...
A
B
C
A
B
C
1. Introduction
2. Expressions
Expression and value
2. Expressions
References : [B1] Ch.1, [B2] Ch.2, [B6] Ch.3, [H4] Ch.2
What is an expression?
?
An expression
2. Expressions
References : [B1] Ch.1, [B2] Ch.2, [H1] Ch.1, [B6] Ch.3, [H4] Ch.2
An expression denotes a value
1 + 2
An expression
2. Expressions
References : [B1] Ch.1, [B2] Ch.2, [H1] Ch.1, [B6] Ch.3, [H4] Ch.2
An expression is evaluated to a value
evaluate
A value
1 + 2
An expression
3
2. Expressions
References : [B2] Ch.2, 7, [B6] Ch.3, [D1]
There are many evaluation approaches
( 1 + 2 ) ^ 2
An expression
A value
9
- Strict, Non-strict evaluation
- Eager, Lazy evaluation
- Call-by-value, Call-by-name,
Call-by-need, …
- Innermost, Outermost
- Normal order, Applicative order
- …
evaluation strategies
2. Expressions
References : [D3], [B2] Ch.2, 7, [B6] Ch.3, [D1]
There are some evaluation levels
WHNF
take 3 [1..]
An expression
A value
[ 1, 2, 3 ]
NF
(Weak Head Normal Form)
(Normal Form)
2. Expressions
Expressions in Haskell
2. Expressions
References : [B2] Ch.2, [H1] Ch.3
There are many expressions in Haskell
if b then 1 else 0
Expressions
categorizing
x : xs
case x of _ -> 0
do {x <- get; put x}
﹨x -> x + 1
let x = 1 in x + y
fun arg
(﹨x -> x + 1) 3
7
‘a’
take 5 xs
Just 5
1 + 2
[1, 2, 3]
map f xs
(1, 2)
xs
2. Expressions
References : [H1] Ch.3, [B2] Ch.2
Expression categories in Haskell
lambda abstraction let expression
conditional case expression do expression
variable
﹨x -> x + 1 let x = 1 in x + y
if b then 1 else 0 case x of _ -> 0
do {x <- get; put x}
general constructor, literal and some forms
7
‘a’
[1, 2, 3]
(1, 2)
x : xs
Just 5
function application
take 5 xs
map f xs
fun arg
(﹨x -> x + 1) 3 1 + 2
xs
2. Expressions
References : [H1] Ch.3, [B2] Ch.2
Specification is described in Haskell 2010 Language Report
“Haskell 2010 Language Report, Chapter 3 Expressions” [H1]
2. Expressions
Classification by values and forms
2. Expressions
References : [H5]
Classification by values
data values
Expressions
function values
values
unevaluated expressions
Values are data values or function values.
7
﹨x -> x + 1
Just 5
‘a’
[1, 2, 3]
(1, 2)
let x = 1 in x + y
if b then 1 else 0
case x of _ -> 0
do {x <- get; put x}
take 5 xs
map f xs fun arg
(﹨x -> x + 1) 3
1 + 2
Just (f x)
bottom
⊥
2. Expressions
References : [H4] Ch.11, [D3], [B6] Ch.3, [B2] Ch.2, 7, [D1], [W1]
Classification by forms
Expressions
Values are WHNF, HNF or NF.
WHNF
HNF
﹨x -> abs 1
unevaluated expressions
let x = 1 in x + y
if b then 1 else 0
case x of _ -> 0
do {x <- get; put x}
take 5 xs
map f xs fun arg
(﹨x -> x + 1) 3
1 + 2
values
bottom
⊥
NF
Just 5
‘a’
[1, 2, 3] (1, 2)
Just (f x)
7
﹨x -> x
﹨x -> x + (abs 1)
[f x, g y]
2. Expressions
WHNF
2. Expressions
References : [H4] Ch.11, [D3], [B6] Ch.3, [B2] Ch.2, 7, [D1], [W1]
WHNF is one of the form in the evaluated values
WHNF
exp
An expression
A value
NF
NF
(Weak Head Normal Form)
(Normal Form)
(2) normal order reduction
of inner level redexes
no redexes at all
no top-level redexes
(1) normal order reduction
of top- level (head) redexes
2. Expressions
References : [H4] Ch.11, [D3], [B5] Ch.2, [B4] Ch.24, [B6] Ch.3, [B2] Ch.2, 7, [D5], [D1]
WHNF
exp
0
exp
1
exp
2
exp
n
...
top-level (head) is
a constructor or
a lambda abstraction
no top-level redex
WHNF is a value which has evaluated top-level
2. Expressions
References : [H4] Ch.11, [D3], [B5] Ch.2, [B4] Ch.24, [B6] Ch.3, [B2] Ch.2, 7, [D5], [D1]
WHNF for a data value and a function value
exp
0
exp
1
exp
2
exp
n
...
constructor
a data value in WHNF
inner redexes
a function value in WHNF
﹨x
1
.. x
n
-> exp
lambda abstraction
no top-level redex
inner redexes
no top-level redex
2. Expressions
References : [H4] Ch.11, [D3], [B5] Ch.2, [B4] Ch.24, [B6] Ch.3, [B2] Ch.2, 7, [D5], [D1]
Examples of WHNF
Just (abs x)
Cons (f 1) (map f [2..] )
WHNF
no WHNF
Just 7
﹨x -> x + 1
if x then elseTrue False
abs 7
no top-level redex
top level-redex
no top-level redex
no top-level redex
no top-level redex
top level-redex
2. Expressions
References : [H4] Ch.11, [D3], [B3]
HNF
exp
0
exp
1
exp
2
exp
n
...
* GHC uses WHNF rather than HNF.
no top-level redex
top-level (head) is
a constructor or
a lambda abstraction with no top-level redex
HNF is a value which has evaluated top-level
2. Expressions
References : [H4] Ch.11, [D3], [B3]
HNF for a data value and a function value
exp
0
exp
1
exp
2
exp
n
...
constructor
a data value in HNF
inner redexes
a function value in HNF
﹨x
1
.. x
n
->
lambda abstraction
(same as WHNF)
exp
0
exp
1
exp
n
...
no redex
no top-level redex
2. Expressions
References : [H4] Ch.11, [D3], [B3]
Examples of HNF
Just (abs x)
HNF
no HNF
Just 7
abs 7
no top-level redex
top level-redex
no top-level redex
﹨x -> (abs 7)Just
no top-level redex
﹨x -> abs 7
top level-redex
2. Expressions
References : [H4] Ch.11, [D3], [B5] Ch.2, [B4] Ch.24, [B6] Ch.3, [B2] Ch.2, 7, [D5], [D1]
NF
exp
0
exp
1
exp
2
exp
n
...
no internal redex
top-level (head) is
a constructor or
a lambda abstraction
NF is a value which has no redex.
2. Expressions
References : [H4] Ch.11, [D3], [B5] Ch.2, [B4] Ch.24, [B6] Ch.3, [B2] Ch.2, 7, [D5], [D1]
NF for a data value and a function value
exp
0
exp
1
exp
2
exp
n
...
constructor
a data value in NF
a function value in NF
﹨x
1
.. x
n
->
lambda abstraction
exp
0
exp
1
exp
n
...
no internal redex
no internal redex
2. Expressions
References : [H4] Ch.11, [D3], [B5] Ch.2, [B4] Ch.24, [B6] Ch.3, [B2] Ch.2, 7, [D5], [D1]
Examples of NF
Cons 1
NF
no NF
Just 7
﹨x -> x + 1
no internal redex
﹨x ->
Nil
no internal redex
no internal redex
Just (abs 7)
redex
(abs 7)Just
redex
2. Expressions
References : [H4] Ch.11, [D3], [B5] Ch.2, [B4] Ch.24, [B6] Ch.3, [B2] Ch.2, 7, [D5], [D1]
WHNF, HNF, NF
exp
0
exp
1
exp
2
exp
n
...
exp
0
exp
1
exp
2
exp
n
...
exp
0
exp
1
exp
2
exp
n
...
WHNF
HNF
NF
no top-level redex
no top-level redex
no internal redex
top-level (head) is
a constructor or
a lambda abstraction with no top-level redex
top-level (head) is
a constructor or
a lambda abstraction
2. Expressions
References : [H4] Ch.11
Definition of WHNF and HNF
“The implementation of functional programming languages” [H4]
2. Expressions
3. Internal representation of expressions
Constructor
3. Internal representation of expressions
Constructor
Constructor is one of the key elements
to understand WHNF and lazy evaluation in Haskell.
3. Internal representation of expressions
Constructor
exp
0
exp
1
exp
2
exp
n
...
constructor
A constructor builds a structured data value.
a data value
+
data components (n ≥ 0)
(data constructor)
A constructor distinguishes the data value in expressions.
3. Internal representation of expressions
References : [B2], [H1], [H4] Ch.2, 10, [B6] Ch.11
Constructors and data declaration
data Maybe a = Nothing
| Just a
constructor data component
Constructors are defined by data declaration.
3. Internal representation of expressions
References : [B2], [H1]
Just
References : [H11], [H10], [H5], [H6], [H7]
Internal representation of Constructors for data values
Nothing
Just 7
Haskell code GHC’s internal representation
Nothing
header
header
payload
7
heap memory
3. Internal representation of expressions
References : [H11], [H10], [H5], [H6], [H7], [D15]
Constructors are represented uniformly
header
payload
...
in heap memory, stack or static memory
object type data components
constructor,
function,
thunk, ...
GHC’s internal representation
A data value is represented with header(constructor) + payload(components).
3. Internal representation of expressions
References : [H11], [H10], [H5], [H6], [H7]
Representation of various constructors
data Bool = False
| True
data Maybe a = Nothing
| Just a
data Either a b = Left a
| Right b
Just
Nothing
a
False
True
Left
a
Right
b
Haskell code GHC’s internal representation
3. Internal representation of expressions
References : [H11], [H10], [H5], [H6], [H7]
Primitive data types are also represented with constructors
Haskell code
I# 0#
I# 1#
:
GHC’s internal representation
C# ‘a’#
C# ‘b’#
:
data Int = I# Int#
data Char = C# Char#
heap memory
1 :: Int
‘a’ :: Char
3. Internal representation of expressions
boxed integer unboxed integer
List is also represented with constructors
[ 1, 2, 3 ]
syntactic desugar
1 : ( 2 : ( 3 : [] ) )
(:) 1 ( (:) 2 ( (:) 3 [] ) )
List
prefix notation by section
Cons 1 ( Cons 2 ( Cons 3 Nil ) )
equivalent data constructor
constructor
3. Internal representation of expressions
References : [H11], [H10], [H5], [H6], [H7]
List is also represented with constructors
[ 1, 2, 3 ]
syntactic desugar
1 : ( 2 : ( 3 : [] ) )
(:) 1 ( (:) 2 ( (:) 3 [] ) )
List
prefix notation by section
Cons 1 ( Cons 2 ( Cons 3 Nil ) )
equivalent data constructor
* pseudo code
type declaration
data List a = Nil
| Cons a (List a)
data List a = []
| : a (List a)
3. Internal representation of expressions
References : [H11], [H10], [H5], [H6], [H7]
References : [H11], [H10], [H5], [H6], [H7]
List is also represented with constructors
(:)
[]
Haskell code GHC’s internal representation
a List a
Cons
Nil
a List a
data List a = Nil
| Cons a (List a)
data List a = []
| : a (List a)
heap memory
* pseudo code
3. Internal representation of expressions
equivalent data constructor
References : [H11], [H10], [H5], [H6], [H7]
List is also represented with constructors
[ 1, 2, 3 ]
1 : ( 2 : ( 3 : [] ) )
(:) 1 ( (:) 2 ( (:) 3 [] ) )
Cons 1 ( Cons 2 ( Cons 3 Nil ) )
Haskell code
GHC’s internal representation
1
Cons (:)
2
Cons (:)
3
Cons (:)
Nil ([])
3. Internal representation of expressions
type declaration
Tuple is also represented with constructor
( 7, 8 )
(,) 7 8
Tuple (Pair)
prefix notation by section
Pair 7 8
equivalent data constructor
data Pair a = (,) a a
data Pair a = Pair a a
* pseudo code
constructor
3. Internal representation of expressions
References : [H11], [H10], [H5], [H6], [H7]
References : [H11], [H10], [H5], [H6], [H7]
Tuple is also represented with constructor
(,)
Haskell code GHC’s internal representation
a a
Pair
a a
data Pair a = Pair a a
data Pair a = (,) a a
heap memory
3. Internal representation of expressions
equivalent data constructor
References : [H11], [H10], [H5], [H6], [H7]
Tuple is also represented with constructor
( 7, 8 )
(,) 7 8
Pair 7 8
7
Pair (,)
8
Haskell code
GHC’s internal representation
3. Internal representation of expressions
Thunk
3. Internal representation of expressions
a thunk
(an unevaluated expression/
a suspended computation)
References : [B5] Ch.2, [D5], [W1], [H10], [H5], [D7]
Thunk
A thunk is an unevaluated expression in heap memory.
A thunk is built to postpone the evaluation.
Haskell code GHC’s internal representation
an unevaluated expression
heap memory
3. Internal representation of expressions
References : [H11], [H10], [D2], [H5], [H6], [H7], [B5] Ch.2, [D5], [W1]
Internal representation of a thunk
An unevaluated expression
header
payload
y ys
thunk
info ptr
take y ys
code
free variables
A thunk is represented with header(code) + payload(free variables).
Haskell code GHC’s internal representation
take y ys
3. Internal representation of expressions
thunk
References : [D2], [H11], [H10], [H5], [H6], [H7], [B5] Ch.2, [D5], [W1]
A thunk is a package
info ptr
header
payload
y ys
take y ys
code free variables
A thunk is a package of code + free variables.
3. Internal representation of expressions
References : [D7], [D2], [H11], [H10], [H5], [H6], [H7], [B5] Ch.2, [D5], [W1], [D15]
A thunk is evaluated by forcing request
Haskell code GHC’s internal representation
An unevaluated expression
header
payload
y ys
thunk
info ptr
take y ys
code
free variables
take y ys
[ 3 ]
An evaluated expression
evaluate
by forcing request
Cons (:)
3 Nil ([])
evaluate
by forcing request
3. Internal representation of expressions
Uniform representation
3. Internal representation of expressions
References : [H11], [H10], [H5], [H6], [H7], [D15]
Every object is uniformly represented in memory
header
payload
...
in heap memory, stack or static memory
object type data components
constructor,
function,
thunk, ...
3. Internal representation of expressions
References : [H11], [H10], [H5], [H6], [H7], [D15]
Every object is uniformly represented in memory
a thunka data value a function value
header
payload
...
3. Internal representation of expressions
References : [H11], [H10], [H5], [H6], [H7], [D15]
Every object is uniformly represented in memory
header
payload
...
code
free variables
info ptrinfo ptrinfo ptr
a thunka data value a function value
code
free variables
stack or
registers
arguments
data components
constructor
3. Internal representation of expressions
* At exactly, a thunk object has
a reserved field in second.
WHNF
3. Internal representation of expressions
References : [H11], [H5], [H6], [H7], [H10]
Internal representation of WHNF
exp
0
exp
1
exp
n
...
constructor
a data value in WHNF
a function value in WHNF
﹨x
1
.. x
n
-> exp
lambda abstraction
info ptr
constructor
data component(s)
heap memory
info ptr
code
(exp)
free variables
info ptr
...
info ptr
data component(s)
exp
1
exp
2
Haskell code GHC’s internal representation
3. Internal representation of expressions
References : [H11], [H5], [H6], [H7], [H10]
Example of WHNF for a data value
Just (take x [1..])
constructor
Just
constructor
a redex
an unevaluated expression
Haskell code GHC’s internal representation
info ptr
take x [1..]
x
thunk
free variables
Constructors can contain unevaluated expressions by thunks.
Haskell’s constructors are lazy constructors.
3. Internal representation of expressions
References : [H11], [H5], [H6], [H7], [H10]
Example of WHNF for a data value
Cons (map f xs)
constructor
Cons
constructor
Haskell code GHC’s internal representation
info ptr
map f xs
f
thunk
free variables
Nil
[ map f xs ]
syntactic desugar
xs
Nil
a redex
an unevaluated expression
3. Internal representation of expressions
let, case expression
3. Internal representation of expressions
let, case expression
let and case expressions are special role in the evaluation
3. Internal representation of expressions
References : [H5], [H6], [H7], [H10]
let/case expressions and thunk
thunk
(unevaluated expression/
suspended computation)
let expression case expression
(allocate)
build
force
(evaluate)
extract
(deconstruct)
A let expression may build a thunk.
A case expression evaluates (forces) and deconstructs the thunk.
3. Internal representation of expressions
References : [H5], [H6], [H7], [H10]
A let expression may allocates a heap object
let x = .....
(build)
allocate
heap memory
let expression
a thunk
(an unevaluated expression)
a function value
a data value
or
or
* At exactly, STG language’s let expression rather than Haskell’s let expression
A let expression may allocates an object in the heap.
(If GHC can optimize it, the let expression may not allocate.)
3. Internal representation of expressions
References : [H5], [H6], [H7], [H10]
Example of let expressions
let x = Just 5
(build)
allocate
let x = ﹨y -> y + z
let x = take y ys
Just
5
info ptr
﹨y -> y + z
free variables
z
info ptr
take y ys
free variables
y
allocate
allocate
Haskell code GHC’s internal representation
ys
a data value
a function value
a thunk
3. Internal representation of expressions
References : [H5], [H6], [H7], [H10], [D2]
A case expression evaluates a subexpression
case x of
pattern1 -> alt1
pattern2 -> alt2
heap memory
case expression
a data value or
a function value or
a thunk
* At exactly, STG language’s case expression rather than Haskell’s case expression
Pattern-matching drives the evaluation.
x
x
(1) pattern-matching drives
the evaluation
an evaluated value
(a data value or
a function value)
3. Internal representation of expressions
evaluate
References : [H5], [H6], [H7], [H10], [D2]
A case expression also perform case analysis
case x of
pattern1 -> alt1
pattern2 -> alt2
heap memory
case expression
a data value or
a function value or
a thunk
* At exactly, STG language’s case expression rather than Haskell’s case expression
A case expression evaluates a subexpression
and optionally performs case analysis on its value.
x
x
(1) pattern-matching drives
the evaluation
(2) select alternative
expression
with result value
an evaluated value
(a data value or
a function value)
3. Internal representation of expressions
evaluate
References : [H5], [H6], [H7], [H10], [D2]
Example of a case expression
case x of
Just _ -> True
Nothing -> False
(1) pattern-matching drives
the evaluation
heap memory
case expression
evaluate
(2) select alternative
expression
with result value
x
x
info ptr
f xs
free variables
f xs
a thunk
Just
5
A case expression’s pattern-matching says “I need the value”.
3. Internal representation of expressions
References : [H1]
Pattern-matching in function definition
f Just _ = True
f Nothing = False
pattern-matching in function definition
f x = case x of
Just _ -> True
Nothing -> False
pattern-matching in case expression
syntactic desugar
A function’s pattern-matching also drives the evaluation.
A function’s pattern-matching is syntactic sugar of case expression.
3. Internal representation of expressions
4. Evaluation
Evaluation strategies
4. Evaluation
References : [B1] Ch.1, [B2] Ch.2, [H1] Ch.1, [B6] Ch.3
Evaluation
evaluate
A value
1 + 2
An expression
3
4. Evaluation
The evaluation produces a value from an expression.
References : [B3] Ch.2, 7, [B6] Ch.3, [D1]
There are many evaluation approaches
[ 1 + 2 ]
An expression
A value
[ 3 ]
- Strict, Non-strict evaluation
- Eager, Lazy evaluation
- Call-by-value, Call-by-name,
Call-by-need, …
- Innermost, Outermost
- Normal order, Application order
- …
evaluation strategies
4. Evaluation
Evaluation concept layer
Implementation techniques
Operational semantics
(Evaluation strategies / Reduction strategies)
Denotational semantics
4. Evaluation
References : [D3], [D1], [D2], [D5], [D4], [B2] Ch.7, [B3] Ch.8, [B6] Ch.5, [W1], [W2], [W3], [B7], [B8]
Evaluation layer for GHC’s Haskell
Implementation
techniques
Strict semantics Non-strict semantics
Strict evaluation Non-strict evaluation
Lazy graph reduction
Call-by-Value Call-by-Name Call-by-Need
...
...
...
Denotational
semantics
(Evaluation strategies/
Reduction strategies)
Operational
semantics
Applicative order reduction Normal order reduction
Tree reduction
...
Eager evaluation Lazy evaluation
Nondeterministic
evaluation
Innermost reduction Outermost reductionRightmost reduction Leftmost reduction
4. Evaluation
References : [D3], [D1], [D2], [D5], [D4], [B2] Ch.7, [B3] Ch.8, [B6] Ch.5, [W1], [W2], [W3], [B7], [B8]
Evaluation layer for GHC’s Haskell
Implementation
techniques
Strict semantics Non-strict semantics
Strict evaluation Non-strict evaluation
Lazy graph reduction
Call-by-Value Call-by-Name Call-by-Need
...
...
...
Denotational
semantics
(Evaluation strategies/
Reduction strategies)
Operational
semantics
Applicative order reduction Normal order reduction
Tree reduction
...
Eager evaluation Lazy evaluation
Nondeterministic
evaluation
Innermost reduction Outermost reductionRightmost reduction Leftmost reduction
4. Evaluation
References : [D3], [D1], [D2], [D5], [D4], [B2] Ch.7, [B3] Ch.8, [B6] Ch.5, [W1], [W2], [W3], [B7], [B8]
Evaluation strategies
Each evaluation strategy decides how to operate the evaluation, about ...
ordering,
region,
trigger condition,
termination condition,
re-evaluation, ...
4. Evaluation
References : [D3], [D1], [D2], [D5], [D4], [B2] Ch.7, [B3] Ch.8, [B6] Ch.5, [W1], [W2], [W3], [B7], [B8]
One of the important points is the order
function arguments
which first?
eager evaluation,
call-by-value,
innermost reduction,
applicative order reduction
lazy evaluation,
call-by-name,
call-by-need,
outermost reduction,
normal order reduction
apply first argument first
4. Evaluation
apply
References : [B2] Ch.7, [B3] Ch.8, [D4], [B6] Ch.5
Simple example of typical evaluations
call-by-value call-by-need
square ( 1 + 2 ) square ( 1 + 2 )
argument
evaluation
first
apply
first
4. Evaluation
References : [B2] Ch.7, [B3] Ch.8, [D4], [B6] Ch.5
Simple example of typical evaluations
call-by-value call-by-need
square ( 1 + 2 ) square ( 1 + 2 )
square ( 3 ) ( 1 + 2 ) * ( 1 + 2 )
3 * 3 ( 3 ) * ( 3 )
9 9
evaluation is
delayed !
evaluation is
performed
4. Evaluation
Evaluation in Haskell (GHC)
4. Evaluation
References : [H4] Ch.11, 12, [H5], [H6], [D2]
Key concepts of GHC’s lazy evaluation
WHNF
An expression
A value
NF
fun args
postpone the evaluation of arguments
to evaluate only when needed
evaluate
stop at WHNF
to evaluate only enough
update itself
to evaluate at most once
drive the evaluation
by pattern-matching
4. Evaluation
reduce in normal order and
References : [H5], [H6], [H10]
Postpone the evaluation of arguments
postpone the evaluation by a thunk which build with let expression
heap memory
Haskell code
postpone
info ptr
map g1 ys
free variables
g1 ys
a thunk
fun (map g1 ys)
let thunk0 = map g1 ys
in fun thunk0
internal translation
(build)
4. Evaluation
(When GHC can optimize it by analysis, the thunk may not be build.)
References : [H5], [H6], [H7], [H10], [D2]
Pattern-matching drives the evaluation
case x of
pattern1 -> alt1
pattern2 -> alt2
heap memory
case expression
a thunk
x
pattern-matching drives
the evaluation
4. Evaluation
evaluate
drive the evaluation by pattern-matching
References : [H5], [H6], [H10]
Stop at WHNF
4. Evaluation
WHNF
an unevaluated expression
evaluate
heap memory
info ptr
code
free variables
a thunk
a value (WHNF)
evaluate
exp exp exp
...
...
evaluated
info ptr
evaluated
Haskell code GHC’s internal representation
stop the evaluation at WHNF
Examples of evaluation steps
4. Evaluation
(1) Example of GHC’s evaluation
tail (map abs [1, -2, 3])
Let’s evaluate. It’s time to magic!
4. Evaluation
* no optimizing case (without –O)
(2) How to postpone the evaluation of arguments?
tail (map abs [1, -2, 3])
function
argument
4. Evaluation
(3) GHC internally translates the expression
tail (map abs [1, -2, 3])
let thunk0 = map abs [1, -2, 3]
in tail thunk0
internal translation
4. Evaluation
(4) a let expression builds a thunk
tail (map abs [1, -2, 3])
let thunk0 = map abs [1, -2, 3]
in tail thunk0
thunk
map f xs
abs [1,-2,3]
internal translation
heap memory
build
4. Evaluation
(5) function apply to argument
tail (map abs [1, -2, 3])
let thunk0 = map abs [1, -2, 3]
in tail thunk0
internal translation
thunk
map f xs
abs [1,-2,3]
heap memory
apply
4. Evaluation
tail (map abs [1, -2, 3])
let thunk0 = map abs [1, -2, 3]
in tail thunk0
internal translation
thunk
map f xs
abs [1,-2,3]
heap memory
(6) tail function is defined here
tail (_:xs) = xs
4. Evaluation
definition
tail (map abs [1, -2, 3])
let thunk0 = map abs [1, -2, 3]
in tail thunk0
internal translation
thunk
map f xs
abs [1,-2,3]
heap memory
tail (_:xs) = xs
(7) function’s pattern is syntactic sugar
tail y = case y of
(_:xs) -> xs
syntactic
desugar
4. Evaluation
tail (map abs [1, -2, 3])
let thunk0 = map abs [1, -2, 3]
in tail thunk0
internal translation
thunk
map f xs
abs [1,-2,3]
heap memory
tail (_:xs) = xs
tail y = case y of
(_:xs) -> xs
(8) substitute the function body (beta reduction)
case thunk0 of
(_:xs) -> xs
reduction
4. Evaluation
(9) case pattern-matching drives the evaluation
tail (map abs [1, -2, 3])
let thunk0 = map abs [1, -2, 3]
in tail thunk0
internal translation
thunk
map f xs
abs [1,-2,3]
heap memory
tail (_:xs) = xs
tail y = case y of
(_:xs) -> xs
case thunk0 of
(_:xs) -> xs
evaluate
4. Evaluation
drive the evaluation
(forcing request)
tail (map abs [1, -2, 3])
let thunk0 = map abs [1, -2, 3]
in tail thunk0
internal translation
thunk
map f xs
abs [1,-2,3]
heap memory
tail (_:xs) = xs
tail y = case y of
(_:xs) -> xs
case thunk0 of
(_:xs) -> xs
(10) but, stop at WHNF
1
constructor
Cons
abs x
map f xs
abs [-2,3]
thunkthunk
stop at
WHNF
evaluate
4. Evaluation
case (abs 1) : (map abs [-2, 3]) of
(_:xs) -> xs
evaluated
(11) bind variables to a result
tail (map abs [1, -2, 3])
let thunk0 = map abs [1, -2, 3]
in tail thunk0
internal translation
thunk
map f xs
abs [1,-2,3]
heap memory
tail (_:xs) = xs
tail y = case y of
(_:xs) -> xs
case thunk0 of
(_:xs) -> xs
1
constructor
Cons
abs x
map f xs
abs [-2,3]
thunkthunk
evaluate
case (abs 1) : (map abs [-2, 3]) of
(_:xs) -> xs
4. Evaluation
(12) return the value
tail (map abs [1, -2, 3])
let thunk0 = map abs [1, -2, 3]
in tail thunk0
internal translation
thunk
map f xs
abs [1,-2,3]
heap memory
tail (_:xs) = xs
tail y = case y of
(_:xs) -> xs
case thunk0 of
(_:xs) -> xs
1
constructor
Cons
abs x
map f xs
abs [-2,3]
thunkthunk
evaluate
case (abs 1) : (map abs [-2, 3]) of
(_:xs) -> xs
map abs [-2, 3]
a result value
4. Evaluation
Key points
tail (map abs [1, -2, 3])
let thunk0 = map abs [1, -2, 3]
in tail thunk0
internal translation
thunk
map f xs
abs [1,-2,3]
heap memory
tail (_:xs) = xs
tail y = case y of
(_:xs) -> xs
case thunk0 of
(_:xs) -> xs
1
constructor
Cons
abs x
map f xs
abs [-2,3]
thunkthunk
evaluate
case (abs 1) : (map abs [-2, 3]) of
(_:xs) -> xs
map abs [-2, 3]
a result value
4. Evaluation
Examples of evaluations
4. Evaluation
* no optimizing case (without –O)
References : [D5], [D6], [D8], [D9], [D10], [H10]
Example of repeat
repeat 1
1 : repeat 1
1 : 1 : repeat 1
1 : 1 : 1 : repeat 1
4. Evaluation
References : [D5], [D6], [D8], [D9], [D10], [H10]
Example of repeat
repeat 1
1 : repeat 1
Cons 1 (repeat 1)
Cons
1
thunk
1
repeat
1 : 1 : repeat 1
Cons 1 (Cons 1 (repeat 1) )
1 : 1 : 1 : repeat 1
Cons 1 (Cons 1 (Cons 1 (repeat 1) ) )
Cons
1
Cons
1
thunk
1
repeat
Cons
1
Cons
1
thunk
1
repeat
Cons
1
1
repeat
1
repeat
4. Evaluation
References : [D5], [D6], [D8], [D9], [D10], [H10]
Example of map
map f [1, 2, 3]
f 1 : map f [2, 3]
f 1 : f 2 : map f [3]
f 1 : f 2 : f 3
...
4. Evaluation
References : [D5], [D6], [D8], [D9], [D10], [H10]
Example of map
map f [1, 2, 3]
f 1 : map f [2, 3]
f 1 : f 2 : map f [3]
f 1 : f 2 : f 3
Cons (f 1) (map f [2, 3])
Cons (f 1) (Cons (f 2) (map f [3]) )
Cons (f 1) (Cons (f 2) (Cons (f 3) Nil ) )
Cons Cons Cons Nil
f
1
f
2
f
3
Cons Cons
f
1
f
2
Cons
f
1
......
thunk
map
f [2,3]
thunk
map
f [3]
4. Evaluation
References : [D5], [D6], [D8], [D9], [D10], [H10]
Example of foldl (non-strict)
foldl (+) (0 + 1) [2 .. 100]
foldl (+) ((0 + 1) + 2) [3 .. 100]
foldl (+) (((0 + 1) + 2) + 3) [4 .. 100]
foldl (+) 0 [1 .. 100]
...
4. Evaluation
References : [D5], [D6], [D8], [D9], [D10], [H10]
Example of foldl (non-strict)
(+)
0 1
(+)
2
(+)
3
thunk1 thunk2 thunk3
(+)
0 1
(+)
2
thunk1 thunk2
(+)
0 1
thunk1
foldl (+) (0 + 1) [2 .. 100]
foldl (+) ((0 + 1) + 2) [3 .. 100]
foldl (+) (((0 + 1) + 2) + 3) [4 .. 100]
let thunk1 = (0 + 1)
in foldl (+) thunk1 [2 .. 100]
let thunk2 = (thunk1 + 2)
in foldl (+) thunk2 [3 .. 100]
let thunk3 = (thunk2 + 3)
in foldl (+) thunk3 [4 .. 100]
foldl (+) 0 [1 .. 100]
heap memory
...
*show only accumulation value
4. Evaluation
References : [D5], [D6], [D8], [D9], [D10], [H10]
Example of foldl’ (strict)
foldl’ (+) 0 [1 .. 100]
foldl’ (+) (0 + 1) [2 .. 100]
foldl’ (+) (1 + 2) [3 .. 100]
foldl’ (+) (3 + 3) [4 .. 100]
...
4. Evaluation
References : [D5], [D6], [D8], [D9], [D10], [H10]
Example of foldl’ (strict)
foldl’ (+) 0 [1 .. 100]
let thunk1 = (0 + 1)
in thunk1 `seq`
foldl’ (+) thunk1 [2 .. 100]
foldl’ (+) (0 + 1) [2 .. 100]
let thunk2 = (1 + 2)
in thunk2 `seq`
foldl’ (+) thunk2 [3 .. 100]
foldl’ (+) (1 + 2) [3 .. 100]
let thunk3 = (3 + 3)
in thunk3 `seq`
foldl’ (+) thunk3 [4 .. 100]
foldl’ (+) (3 + 3) [4 .. 100]
(+)
0 1
heap memory
thunk1
I# 1#
(+)
2
thunk2
I# 3#
I# 1#
eval
by seq
(+)
3
thunk3
I# 6#
I# 3#
...
4. Evaluation
References : [D5], [D6], [D8], [D9], [D10], [H10]
Example of foldl (non-strict) and foldl’ (strict)
foldl (+) (0 + 1) [2 .. 100]
foldl (+) ((0 + 1) + 2) [3 .. 100]
foldl (+) (((0 + 1) + 2) + 3) [4 .. 100]
foldl’ (+) (0 + 1) [2 .. 100]
foldl’ (+) (1 + 2) [3 .. 100]
foldl’ (+) (3 + 3) [4 .. 100]
4. Evaluation
(+)
References : [D5], [D6], [D8], [D9], [D10], [H10]
Example of foldl (non-strict) and foldl’ (strict)
0 1 2
(+)
3
heap memory
(+)
(+)
0 1 2
(+)
0 1
(+)
3
(+)
I# 3#
I# 6#
2
(+)
I# 1#
1
(+)
0
I# 3#
I# 1#
foldl (+) (0 + 1) [2 .. 100]
foldl (+) ((0 + 1) + 2) [3 .. 100]
foldl (+) (((0 + 1) + 2) + 3) [4 .. 100]
foldl’ (+) (0 + 1) [2 .. 100]
foldl’ (+) (1 + 2) [3 .. 100]
foldl’ (+) (3 + 3) [4 .. 100]
4. Evaluation
Controlling the evaluation
4. Evaluation
How to drive the evaluation
An expression
driving the evaluation by
and deconstructing by
pattern-
matching
primitive
operation
forcing
function
special
syntax
special
pragma
case expression
function definition
+, *, ... seq
$!
pseq
deepseq
force
$!!
rnf
,...
! Strict
StrictData
* ghc 8.0 ~
compile
option
-O
-fstrictness
-XStrict
-XStrictData
* ghc 8.0 ~
strict
function
foldl’
scanl’
,...
4. Evaluation
References : [H1] Ch.3, [D2], [D1], [H5], [W1]
(1) Evaluation by pattern-matching
case ds of
x:xs -> f x xs
[] -> False
pattern-matching in case expression
f Just _ = True
f Nothing = False
pattern-matching in function definition
forcing
(drive the evaluation of the thunk)
forcing
(drive the evaluation of the thunk)
4. Evaluation
References : [H1] Ch.3, [D2], [D1], [H5], [W1], [H8] Ch.4
(1) Evaluation by pattern-matching
Strict patterns drive the evaluation Lazy patterns postpone the evaluation.
function definition
let binding patterncase expression
irrefutable patterns
case ds of
x:xs -> f x xs
[] -> False
f Just _ = True
f Nothing = False
let (x:xs) = fun args
f ~(Just _ ) = True
f ~(Nothing) = False
There are two kinds of pattern-matching.
[H1] 3.17
4. Evaluation
References : [D3], [H5], [H12]
(2) Evaluation by primitive operation
f x y = x + y
primitive (built-in) operation
forcing x and y
(drive the evaluation of the thunks)
+, *, ...
(+) (I# a) (I# b) = I# (a+b)
pattern-matching
primitive operations are defined such as
4. Evaluation
* pseudo code
References : [B4] Ch.25, [D9], [B6] Ch.7, [B2], [S1], [S2]
(3) Evaluation by strict version function
foldl’ (+) 0 xs
strict version function
strict application of the operator
4. Evaluation
scanl’ (+) 0 xs
:
:
References : [B5] Ch.2, [B4] Ch.24, 25, [B6] Ch.7, [H1] Ch.6, [D2], [B2], [D1], [D2]. [S1], [S2]
(4) Evaluation by forcing function
seq x y
forcing functions to WHNF
forcing
(drive the evaluation of the thunk)
forcing functions to NF
f $! x
pseq x y
deepseq x y
f $!! x
force x
rnf x
4. Evaluation
References : [B5] Ch.2, [B4] Ch.24, 25, [H1] Ch.6, [D2], [B2], [D1], [D2]. [S1], [S2]
(4) Evaluation by forcing function
WHNF
NF
an expression
WHNF
NF
an expression
evaluate
seq
$!
pseq
deepseq
force
$!!
rnf
to WHNF to NF
4. Evaluation
evaluate
References : [B5] Ch.2, [B4] Ch.24, 25, [H1] Ch.6, [D2], [B2], [D1], [D2]. [S1], [S2]
(4) Evaluation by forcing function
to WHNF to NF
force
rnf
deepseq
$!!
seq
$!
pseq
two arguments
function application
one argument
sequential order
basic operation
4. Evaluation
References : [B5] Ch.2, [B4] Ch.24, 25, [H1] Ch.6, [D2], [B2], [D1], [D2]. [S1], [S2]
(4) Evaluation by forcing function
to WHNF to NF
force
rnf
deepseq
$!!
seq
$!
pseq
two expressions
function application
one expression
sequential order
basic operation
deepseq a b = rnf a `seq` b
force x = x `deepseq` x
f $!! x = x `deepseq` f x
built-in
f $! x = let !vx = x in f vx
pseq x y = x `seq` lazy y
class NFData a where
rnf :: a -> ()
instance NFData Int where rnf !_ = ()
:
instance NFData a => NFData [a] where
rnf [] = ()
rnf (x:xs) = rnf x `seq` rnf xs
definition
4. Evaluation
References : [B5] Ch.2, [B4] Ch.24, 25, [H1] Ch.6, [D2], [B2], [D1], [D10]. [S1], [S2]
(4) Evaluation by forcing function
seq a ()
deepseq a ()
length a
a = map abs [1, -2, 3, -4]
Cons Cons Cons
1 2 3
thunk
1
abs x
Cons Nil
Cons Cons Cons Cons Nil
4
thunk
-2
abs x
thunk
3
abs x
thunk
-4
abs x
thunk
1
abs x
Cons
abs
map f xs
[-2, 3, -4]
thunk
4. Evaluation
full evaluation
evaluate spine only
evaluate head only
References : [D1], [H2] Ch.7, [H1] Ch.4, [B4] Ch.25, [B2] Ch.7, [W6], [H4] Ch.22, [W4]
(5) Evaluation by special syntax
{-# LANGUAGE BangPatterns #-}
f !xs = g xs
Bang pattern
data Pair = Pair !a !b
[H2] 7.19
Strictness flag
Strictness annotation
[H1] 4.2.1
Strictness annotations assist strictness analysis.
4. Evaluation
arguments are evaluated
before function application
arguments are evaluated
before constructor application
References : [H13]
(6) Evaluation by special pragma
{-# LANGUAGE Strict #-}
let f xs = g xs in f ys
data Pair = Pair a b
Strict pragma
{-# LANGUAGE StrictData #-}
data Pair = Pair a b
Strict and StrictData pragmas are module level control.
These can use in ghc 8.0 or later.
* ghc 8.0 ~
4. Evaluation
Special pragma for strictness language extension
StrictData pragma
* ghc 8.0 ~
arguments are evaluated
before application
References : [H2], [H13]
(7) Evaluation by compile option
strictness analysis
$ ghc -O
$ ghc -fstrictness
$ ghc -XStrict
$ ghc -XStrictData
strictness language extension
* ghc 8.0 ~
4. Evaluation
apply Strict pragma
apply StrictData pragma
Turn on strictness analysis.
Implied by “-O”.
Compile option
Turn on optimization.
Imply “-fstrictness”.
5. Implementation of evaluator
Lazy graph reduction
5. Implementation of evaluator
References : [D3], [D2], [D5], [W5], [H4] Ch.12, [B8] Ch.3
Tree
An expression can be represented in the form of Abstract Syntax Tree (AST).
AST is reduced using stack (sequential access memory).
5. Implementation of evaluator
exp
exp exp
expexp exp
expexp exp
References : [D3], [D2], [D5], [W5], [H4] Ch.12, [B8] Ch.3
Graph
exp
exp exp
exp
An expression can be also represented in the form of Graph.
Graph can share subexpressions to evaluate at once.
So, graph is reduced using heap (random access memory) rather than stack.
5. Implementation of evaluator
exp
expexp exp
shared term
exp
References : [D3], [W5], [H4] Ch.11, 12, [B8] Ch.3
Graph can be reduced in some order
square (1+2)
5. Implementation of evaluator
square 1 + 2
+ 1 2
square (1+2)
square 3
+ 1 2
(1+2) * (1+2)
1 + 2
+ 1 2
3 *
top-level redex
inner level redex
which first ?
reduce top-level (outermost) firstreduce inner level first
for call-by-value for call-by-need
To select top-level redex first, the evaluation of arguments can be postponed.
References : [D3], [D2], [D5], [W5], [H4] Ch.11, 12, [B8] Ch.3
Normal order reduction is implemented by lazy graph reduction
exp
exp exp
exp expexp
Normal order (leftmost outermost) reduction is implemented by lazy graph reduction
to select top-level redex first.
5. Implementation of evaluator
exp exp
find top-level redex
and reduce it
exp exp exp exp
...
an expression
Normal order (leftmost outermost) first
Given an application of a function, the outermost redex is the function application itself.
Normal order reduction Lazy graph reduction
implemented by
STG-machine
5. Implementation of evaluator
References : [H5], [H6], [H7], [D15]
Abstract machine
Graph
(expression)
STG-machine
Evaluator
(abstract machine)
GHC uses abstract machine to reduce the expression.
It’s called “STG-machine”.
5. Implementation of evaluator
evaluate
(reduce / execute)
References : [H5], [H6], [H7], [D15]
Concept layer
Haskell code take 5 [1..10]
:
Graph
(internal representation
of the expression)
Evaluator (reducer, executer)
(abstract machine)
STG Registers Stack Heap
R1, ...
STG-machine
5. Implementation of evaluator
References : [H5], [H6], [H7], [D15]
STG-machine
STG-machine is abstraction machine
which is defined by operational semantics.
STG-machine efficiently performs lazy graph reduction.
STG Registers Stack Heap
R1, ...
STG-machine
Static
5. Implementation of evaluator
References : [H5], [H6], [H7], [D15]
STG-machine
STG Registers Stack Heap
R1, ...
STG-machine
mainly used for
nest continuation
argument passing
mainly used for
allocating objects
(thunks, datas,
functions)
Static
mainly used for
call/return convention
various control
mainly used for
code
static objects
5. Implementation of evaluator
References : [H5], [H10]
Example of mapping a code to a graph
main
print head [1..]
head [1..]
main = print (head [1..])
5. Implementation of evaluator
References : [H5], [H10]
Example of mapping a code to a graph
main
print head [1..]
head [1..]
main = print (head [1..])
5. Implementation of evaluator
References : [H5], [H10]
Example of mapping a code to a graph
code
code code
code code
main = print (head [1..])
main
print
head [1..]
head
[1..]
function
function thunk
function thunk
build
build
5. Implementation of evaluator
References : [H5], [H6], [H7], [D15]
Self-updating model
expression code
free variables
info ptr
a thunk
update code
info ptr
a data value
data components
constructor
evaluate and update
(replace myself to result value)
5. Implementation of evaluator
GHC’s internal representationExpression
References : [H5], [H6], [H4] Ch.12, [D15]
Unreferenced expressions (objects) will be removed by GC
5. Implementation of evaluator
a thunk
code
an evaluated expression
unreferenced
objects
collected by GC(Garbage Collection)
evaluate and updateevaluate and update
GHC’s internal representationExpression
collected by GC(Garbage Collection)
References : [H5], [H6], [H4] Ch.3
STG-machine associates directly ...
STG-machine associates directly lambda calculus and physical machine.
5. Implementation of evaluator
( λx . body ) arg
let x = arg
in body
case arg of
x -> body
x
x
a thunk
an evaluated value
heap memory
lazy
(non-strict)
eager
(strict)
arg
built a thunk
evaluate the arg
bind with a lazy expression
bind with an evaluated expression
arg
The STG-machine is ...
The STG-machine is the marriage of Lambda calculus and Turing machine.
5. Implementation of evaluator
λ
λ
λ λ
λ
λ λ
STG-machine
Lambda calculus Turing machine
References : [H5], [H6], [H7], [D15]
STG-dump shows which expression is built as thunks
5. Implementation of evaluator
module Example where
fun f1 n = take 1 (f1 n)
[Example.hs]
Example.fun
:: forall a_aME t_aMF. (t_aMF -> [a_aME]) -> t_aMF ->
[a_aME]
[GblId,
Arity=2,
Caf=NoCafRefs,
Str=DmdType <L,1*C1(U)><L,U>,
Unf=OtherCon []] =
﹨r srt:SRT:[] [f1_sQT n_sQU]
let {
sat_sQV [Occ=Once, Dmd=<L,1*U>] :: [a_aMH]
[LclId, Str=DmdType] =
﹨s srt:SRT:[] [] f1_sQT n_sQU;
} in GHC.List.take_unsafe_UInt 1 sat_sQV;
STG code dump
by “$ ghc -O -ddump-stg Example.hs”
thunk
f1_sQT n_sQU
f1_sQT n_sQU
heap memory
build/allocate
let expression in STG language
6. Semantics
Bottom
6. Semantics
References : [B2] Ch.2, [W4]
A well formed expression should have a value
evaluate
A value
1 + 2
An expression
3
6. Semantics
?
References : [B2] Ch.2, [H1] Ch.3, [W4], [H4] Ch.2, 22
What is a value in this case?
evaluate
A value ?
An expression
infinite loop or
partial function
a non-terminating expression
6. Semantics
References : [B2] Ch.2, [H1] Ch.3, [W4], [H4] Ch.2, 22
A value “bottom” is introduced
evaluate
A value
An expression
⊥
bottom
a non-terminating expression
6. Semantics
infinite loop or
partial function
References : [B2] Ch.2, 9, [H1] Ch.3, [W4], [H4] Ch.2, 22
Bottom
A value
⊥
Bottom (⊥) is “an undefined value”.
Bottom (⊥) is “a non-terminating value”.
6. Semantics
References : [B2] Ch.2, 9, [H1] Ch.3, [W4], [H4] Ch.2, 22
“undefined” function represents “bottom” in GHC
Haskell code GHC’s internal representation
undefined :: a
⊥
Expression
info ptr
code
6. Semantics
GHC.Err.undefined
Strict/Non-strict
6. Semantics
an expression
References : [B2] Ch.2, [W1], [W4], [H4] Ch.2, 22, [H15], [H16]
Strictness
6. Semantics
definitely evaluated?
Strictness is “evaluation demand” of the expression.
an expression
References : [B2] Ch.2, [W1], [W4], [H4] Ch.2, 22, [H15], [H16]
Strict and non-strict
6. Semantics
“Strict” means that
the expression is definitely evaluated.
“Non-strict” means that
the expression may or may not be evaluated.
an expression
References : [B2] Ch.2, [W1], [W4], [H4] Ch.2, 22, [H15], [H16]
Strict and non-strict
6. Semantics
“Strict” means that
the expression is definitely evaluated.
“Non-strict” means that
the expression may or may not be evaluated.
GHC implements non-strict semantics by lazy evaluation.
References : [H15], [H16], [B2] Ch.2, [W1], [W4], [H4] Ch.2, 22
GHC has the lattice of strictness
6. Semantics
an expression
WHNF or ⊥
NF
WHNF or ⊥
NF
an expression
NF or ⊥
an expressionan expression
a lazy demand
a head-strict demand
a hyperstrict demand
a structured strictness demand
StrictNon-strict
There are multiple levels in strict.
References : [H15], [H16], [B2] Ch.2, [W1], [W4], [H4] Ch.2, 22
Strictness of a function
6. Semantics
A function places “strictness demands” on each of its arguments.
function
argument 2
argument 1 evaluated ?
evaluated ?
Will arguments be definitely evaluated in the function?
References : [B2] Ch.2, [W1], [W4], [H4] Ch.2, 22
Strictness of a function is formally defined
6. Semantics
Strictness of a function can be defined with the association between input and output.
“given a non-terminating arguments, the function will terminate?”
⊥ f
function
input output
?
f ⊥ = ?
definition
References : [B2] Ch.2, [W1], [W4], [H4] Ch.2, 22
Definition of the strict function
⊥ f ⊥
Strict function
input output
Strict function’s output is bottom when input is bottom.
f ⊥ = ⊥
given a non-terminating arguments, strict function will not terminate.
6. Semantics
definition
Non-strict function’s output is not bottom when input is bottom.
References : [B2] Ch.2, [W1], [W4], [H4] Ch.2, 22
Definition of the non-strict function
⊥ f
≠ ⊥
Non-strict function
input output
an evaluated value or
an unevaluated expression
given a non-terminating arguments, non-strict function will terminate.
6. Semantics
f ⊥ ≠ ⊥
definition
⊥ f ⊥
Strict function
input output
Strict
⊥ f
≠ ⊥
an evaluated value or
an unevaluated expression
Non-strict function
input output
Non-strict
References : [B2] Ch.2, [W1], [W4], [H4] Ch.2, 22
Strict and Non-strict functions
6. Semantics
f
Strict function
Strict
evaluate
the argument
to WHNF
passing
the evaluated
argument
an argument
no need to evaluate the argument
f
Non-strict function
Non-strict
build a thunk
passing
the thunk
an argument
evaluate the argument if needed
References : [B2] Ch.2, [W1], [W4], [H4] Ch.2, 22
Function application and strictness
6. Semantics
Postpone or Prepay
The front stage is also important.
f $!! argf $! arg
Strict
(deepseq)(seq)
References : [B2] Ch.2, [W1], [W4], [H4] Ch.2, 22
Strict and normal form
to WHNF to NF
6. Semantics
Strict ≠ Normal form
Example of function application
Non-strict f $ arg
Lifted and boxed types
6. Semantics
References : [W4], [B2], [H14]
Lifted types
6. Semantics
Lifted types include bottom as an element.
0 1
Lifted type
2
...
lifted
⊥
References : [W4], [B2], [H14]
Lifted type’s declaration implicitly include bottom
6. Semantics
False True
0 1
Bool type
Int type
2
...
data Bool = False
| True
| ⊥
data Int = I# Int#
| ⊥
implicitly included
implicitly included
data declaration
⊥
⊥
References : [W4], [B2], [H14]
Lifted type are also implemented by uniform representation
6. Semantics
Nothing
I# 0#
Just
data Maybe a = Nothing
| Just a
| ⊥
data Int = I# Int#
| ⊥
data declaration GHC’s internal representation
⊥
⊥
x :: Maybe a
x :: Int
undefined
code
I# 1#
:
a
undefined
code
References : [W4], [B2], [H14]
Lifted and unlifted types
6. Semantics
0 1
Lifted types
2
...
lifted
0# 1#
Unlifted types
2#
...
Lifted types include bottom. Unlifted types do not include bottom.
Int type Int# type
⊥
(Bool, Int, Char, Maybe, List, ...) (Int#, Char#, Addr#, Array#, ByteArray#, ...)
⊥
References : [W4], [B2], [H14]
Example of lifted and unlifted types
6. Semantics
Lifted types Unlifted types
data1
x :: Array#
Nothing
Just
⊥
x :: Just a
code
data2
data3
I# 0#
⊥
x :: Int
code
I# 1#
:
#7
x :: Int#
no bottom
no bottom
a
References : [W4], [B2], [H14]
Boxed and unboxed types
6. Semantics
value
value
Boxed
types
Unboxed
types
pointed
Boxed types are represented as a pointer.
Unboxed types are represented other than a pointer.
- no bottom (can’t be lifted)
- no thunk (can’t be postponed)
- no polymorphism (non-uniform size)
+ low cost memory size (no pointer)
+ high performance (no wrap/unwrap)
References : [W4], [B2], [H14]
Example of boxed and unboxed types
6. Semantics
I# 0#
x :: Int
I# 1#
:
#7
x :: Int#
no bottom
Boxed
types
Unboxed
types
data1
x :: Array#
data2
data3
References : [W4], [B2], [H14]
Lifted and boxed types
6. Semantics
Lifted types Unlifted types
Boxed
types
Unboxed
types
Int
Char
Float
Maybe
:
Array#
ByteArray#
:
Int#
Char#
Float#
:
no bottom
no bottom
no packed
unboxed can’t be lifted
References : [W4], [B2], [H14]
Example of lifted and boxed types
6. Semantics
Lifted types Unlifted types
Boxed
types
Unboxed
types
I# 0#
⊥
x :: Int
code
I# 1#
:
data1
x :: Array#
data2
data3
#7
x :: Int#
include bottom
pointed
References : [B6] Ch.29, [W4], [B2], [H14]
Types and kinds
6. Semantics
Lifted types Unlifted types
Boxed
types
Unboxed
types
Int
Char
Float
Maybe
:
Array#
ByteArray#
:
Int#
Char#
Float#
:
kind ‘
*
’
kind ‘#’
Identifier’s ‘#’ customarily means “primitive” rather than “unboxed” or “unlifted”.
Kind’s ‘#’ means “unlifted”.
Note:
Strictness analysis
6. Semantics
References : [H4] Ch.22, [H8], [W6], [W3], [H15], [H16], [H13], [H2]
Strictness analysis
6. Semantics
arguments evaluated ?
function
Strictness analysis analyzes whether a function is sure to evaluate its argument.
analyzed by strictness analyser
arguments evaluated ?
function
References : [H15], [H16], [H2], [H4] Ch.22, [H8], [W6], [W3], [H13]
Strictness analysis in GHC
6. Semantics
a lazy demand
a head-strict demand
a hyperstrict demand
a structured strictness demand
a used demand
a head-used demand
unused (absence)
a structured used demand
Strictness demands Absence/usage demands
GHC’s demand analyser implements strictness analysis.
Demand analysis ( = Strictness analysis + Absence analysis + ... )
demand analyser
References : [H15], [H16], [H2], [H4] Ch.22, [H8], [W6], [W3], [H13]
Example of strictness analysis information in GHC
6. Semantics
module Example where
f1 :: Bool -> Int -> Maybe Int
f1 c n = case c of
True -> Just n
False -> Nothing
[Example.hs]
==================== Strictness signatures ====================
Example.f1: <S,1*U><L,U>
Strictness analysis dump
by “$ ghc -O -ddump-strsigs Example.hs”
L -- second argument is “Lazy”
S -- first argument is “head-Strict”
GHC shows strictness analysis information with “-ddump-strsigs” and “-ddump-stranal”.
References : [H4] Ch.22, [H8], [W6], [W3], [H15], [H17], [H13]
(1) Strictness analysis are used to avoid the thunk
If GHC knows that a function is strict, arguments is evaluated before application.
GHC finds strict functions by “strictness analysis (demand analysis)”.
heap memory
exp
non-strict function
thunk
build
non-strict function exp
apply
heap memory
exp
thunk
build
strict function exp
apply
strict function
6. Semantics
no build
no force
no update
no GC
non-strict
strict
References : [H8], [H4] Ch.22, [W6], [W3], [H15], [H17], [H13]
(1) Strictness analysis are used to avoid the thunk
6. Semantics
let x = arg
in body
case arg of
x -> body
let-to-case transformation
heap memory
arg
thunk
build
heap memory
arg
thunk
build
If GHC knows that a function is strict, GHC performs let-to-case transformation.
References : [H4] Ch.22, [H8], [W6], [W3], [H15], [H17], [H13]
(2) Strictness analysis are also used to optimize
6. Semantics
Strict function
evaluate
the argument
evaluated
argument
an argument
evaluate
the argument
evaluated
argument
an argument
f
evaluated (no thunk)
unlifted (no bottom)
if ⊥
if ≠ ⊥
⊥
or
a result
optimizing
f
f’
Strictness function can be optimized to assume no thunk, no bottom.
optimized version
References : [H4] Ch.22, [H8], [W6], [W3], [H15], [H17], [H13]
(2) Strictness analysis are also used to optimize
6. Semantics
Strict function
evaluate
the argument
evaluated
argument
an argument
evaluate
the argument
evaluated
argument
an argument
f
evaluated (no thunk)
unlifted (no bottom)
if ⊥
if ≠ ⊥
⊥
or
a result
optimizing
evaluate
the argument
evaluated
argument
an argument
wf (worker)
evaluated (no thunk)
unlifted (no bottom)
unboxed (no packed)
if ⊥
if ≠ ⊥
⊥
or
a result
unpack pack
lightly inlinable
high efficiency
f
f’
optimizing
f (wrapper)
Strictness function can be optimized to assume no thunk, no bottom, no packed.
Sequential order
6. Semantics
References : [H9], [D11], [H1] Ch.6, [S1]
“seq” doesn’t guarantee the evaluation order
specification
seq a b = ⊥, if a = ⊥
= b, otherwise
6. Semantics
seq ⊥ b = ⊥
seq a ⊥ = ⊥
// b is strict
// a is strict
“seq” function only guarantee that it is strict in both arguments.
This semantics property makes no operational guarantee about order of evaluation.
strictness for each arguments
References : [H9], [D11], [H1] Ch.6, [S1]
“seq” and “pseq”
specification
seq a b = ⊥, if a = ⊥
= b, otherwise
seq ⊥ b = ⊥
seq a ⊥ = ⊥
// b is strict
6. Semantics
// a is strict
specification
pseq a b = ⊥, if a = ⊥
= b, otherwise
pseq ⊥ b = ⊥
pseq a ⊥ = ⊥
// b is strict
// a is strict
Both of denotational semantics are the same.
But “pseq” makes operational guarantee about order of evaluation.
References : [H9], [D11], [H1] Ch.6, [S1]
Evaluation order of “seq” and “pseq”
seq a b
pseq a b
time
evaluation of a
evaluation of b
start
termination
start termination
return from b
no guarantee
no guarantee guarantee
time
evaluation of a
evaluation of b
start
termination
start termination
return from b
guarantee
6. Semantics
References : [H9], [D11], [H1] Ch.6, [H2] Ch.7, [S1]
Implementation of “seq” and “pseq”
specification
seq a b = ⊥, if a = ⊥
= b, otherwise
Haskell’s built-in
6. Semantics
specification
pseq a b = ⊥, if a = ⊥
= b, otherwise
pseq x y = x `seq` lazy y
GHC’s “lazy” function restrains
the strictness analysis.
“seq” is built-in function.
“pseq” is implemented by built-in functions (“seq” and “lazy”).
7. Appendix
References
7. Appendix
References
[H1] Haskell 2010 Language Report
https://www.haskell.org/definition/haskell2010.pdf
[H2] The Glorious Glasgow Haskell Compilation System (GHC user’s guide)
https://downloads.haskell.org/~ghc/latest/docs/users_guide.pdf
[H3] A History of Haskell: Being Lazy With Class
http://haskell.cs.yale.edu/wp-content/uploads/2011/02/history.pdf
[H4] The implementation of functional programming languages
http://research.microsoft.com/en-us/um/people/simonpj/papers/slpj-book-1987/slpj-book-1987.pdf
[H5] Implementing lazy functional languages on stock hardware: the Spineless Tagless G-machine Version 2.5
http://research.microsoft.com/en-us/um/people/simonpj/Papers/spineless-tagless-gmachine.ps.gz
[H6] Making a Fast Curry Push/Enter vs Eval/Apply for Higher-order Languages
http://research.microsoft.com/en-us/um/people/simonpj/papers/eval-apply
[H7] Faster Laziness Using Dynamic Pointer Tagging
http://research.microsoft.com/en-us/um/people/simonpj/papers/ptr-tag/ptr-tagging.pdf
[H8] Measuring the effectiveness of a simple strictness analyser
http://research.microsoft.com/~simonpj/papers/simple-strictnes-analyser.ps.gz
[H9] Runtime Support for Multicore Haskell
http://community.haskell.org/~simonmar/papers/multicore-ghc.pdf
[H10] I know kung fu: learning STG by example
https://ghc.haskell.org/trac/ghc/wiki/Commentary/Compiler/GeneratedCode
7. Appendix
References
[H11] GHC Commentary: The Layout of Heap Objects
https://ghc.haskell.org/trac/ghc/wiki/Commentary/Rts/Storage/HeapObjects
[H12] The ghc-prim package
https://hackage.haskell.org/package/ghc-prim
[H13] GHC Commentary: Strict & StrictData
https://ghc.haskell.org/trac/ghc/wiki/StrictPragma
[H14] The data type Type and its friends
https://ghc.haskell.org/trac/ghc/wiki/Commentary/Compiler/TypeType
[H15] Demand analyser in GHC
https://ghc.haskell.org/trac/ghc/wiki/Commentary/Compiler/Demand
[H16] Demand analysis
http://research.microsoft.com/en-us/um/people/simonpj/papers/demand-anal/demand.ps
[H17] Core-to-Core optimization pipeline
https://ghc.haskell.org/trac/ghc/wiki/Commentary/Compiler/Core2CorePipeline
[H18] The GHC reading list
https://ghc.haskell.org/trac/ghc/wiki/ReadingList
[H19] The GHC Commentary
https://ghc.haskell.org/trac/ghc/wiki/Commentary
7. Appendix
References
[B1] Introduction to Functional Programming using Haskell (IFPH 2nd edition)
http://www.cs.ox.ac.uk/publications/books/functional/bird-1998.jpg
http://www.pearsonhighered.com/educator/product/Introduction-Functional-Programming/9780134843469.page
[B2] Thinking Functionally with Haskell (IFPH 3rd edition)
http://www.cs.ox.ac.uk/publications/books/functional/
[B3] Programming in Haskell
https://www.cs.nott.ac.uk/~gmh/book.html
[B4] Real World Haskell
http://book.realworldhaskell.org/
[B5] Parallel and Concurrent Programming in Haskell
http://chimera.labs.oreilly.com/books/1230000000929
[B6] Types and Programming Languages (TAPL)
https://mitpress.mit.edu/books/types-and-programming-languages
[B7] Purely Functional Data Structures
http://www.cambridge.org/us/academic/subjects/computer-science/programming-languages-and-applied-logic/purely-functional-data-structures
[B8] Algorithms: A Functional Programming Approach
http://catalogue.pearsoned.co.uk/catalog/academic/product/0,1144,0201596040,00.html
7. Appendix
References
[D1] Laziness
http://dev.stephendiehl.com/hask/#laziness
[D2] Being Lazy with Class
http://www.seas.upenn.edu/~cis194/lectures/06-laziness.html
[D3] A Haskell Compiler
http://www.scs.stanford.edu/14sp-cs240h/slides/ghc-compiler-slides.html
http://www.scs.stanford.edu/11au-cs240h/notes/ghc-slides.html
[D4] Evaluation
http://dev.stephendiehl.com/fun/005_evaluation.html
[D5] Incomplete Guide to Lazy Evaluation (in Haskell)
https://hackhands.com/guide-lazy-evaluation-haskell
[D6] Laziness
https://www.fpcomplete.com/school/starting-with-haskell/introduction-to-haskell/6-laziness
[D7] Evaluation on the Haskell Heap
http://blog.ezyang.com/2011/04/evaluation-on-the-haskell-heap
[D8] Lazy Evaluation of Haskell
http://www.vex.net/~trebla/haskell/lazy.xhtml
[D9] Fixing foldl
http://www.well-typed.com/blog/2014/04/fixing-foldl
[D10] How to force a list
https://ro-che.info/articles/2015-05-28-force-list
7. Appendix
References
[D11] Evaluation order and state tokens
https://www.fpcomplete.com/user/snoyberg/general-haskell/advanced/evaluation-order-and-state-tokens
[D12] Reasoning about laziness
http://blog.johantibell.com/2011/02/slides-from-my-talk-on-reasoning-about.html
[D13] Some History of Functional Programming Languages
http://www-fp.cs.st-andrews.ac.uk/tifp/TFP2012/TFP_2012/Turner.pdf
[D14] Why Functional Programming Matters
https://www.cs.kent.ac.uk/people/staff/dat/miranda/whyfp90.pdf
[D15] GHC illustrated
http://takenobu-hs.github.io/downloads/haskell_ghc_illustrated.pdf
7. Appendix
References
[W1] Haskell/Laziness
https://en.wikibooks.org/wiki/Haskell/Laziness
[W2] Lazy evaluation
https://wiki.haskell.org/Lazy_evaluation
[W3] Lazy vs. non-strict
https://wiki.haskell.org/Lazy_vs._non-strict
[W4] Haskell/Denotational semantics
https://en.wikibooks.org/wiki/Haskell/Denotational_semantics
[W5] Haskell/Graph reduction
https://en.wikibooks.org/wiki/Haskell/Graph_reduction
[W6] Performance/Strictness
https://wiki.haskell.org/Performance/Strictness
7. Appendix
References
[S1] Hackage
https://hackage.haskell.org
[S2] Hoogle
https://www.haskell.org/hoogle
7. Appendix
Lazy,...
to be as lazy as possible...
