Transcript Closure Representations in Higher-Order

Closure Representations in HigherOrder Programming Languages
Vijay Kumar Gurramkonda
Ball State University
Computer Science
Department
11/22/00
CS 689
Introduction
Higher Order Functions
Functions that take functional arguments.
Higher Order Functional Programming
Languages.
A higher-order functional language is one with
nested scope and higher-order functions.
Closures
It is a record that contains the machine-code
pointer and a way to access the necessary
nonlocal variables. One simple kind of closure is
just a pair of code pointer and static link.
Closures need not be based on static links, any
other data structure that gives access to
nonlocal variables will do.
Heap-Allocated Activation
Records
Activation record for a function say “add” must
not be destroyed when “add” returns, because it
may still serve as an environment to another
function say “U”. To solve this problem, we could
create activation records on the heap instead of
on the stack. Instead of explicitly destroying
add’s frame when add returns, we would wait
until the garbage collector determines that it is
safe to reclaim the frame, this would happen
when all the pointers to “U” disappear.
Problem Description
Compilers implement function calls in two
steps:
First, a closure environment is installed to
provide an access for free variables in the
target program fragment.
Second, the control is transferred to the
target by a jump with arguments.
Contd…
Closure conversion, which decides where and
how to represent closures at runtime is a crucial
step in the compilation of functional languages.
Depending on the runtime behavior of each
function, closures can be represented as data
structures of virtually any shape, allocated in the
heap, on the stack or in the registers. The
decisions of where and how to represent
closures at runtime greatly affect the quality of
the code generated. Thus, a good closureallocation scheme is required to optimize
function calls.
Research Objectives

Make best
techniques.
use
of
closure
representation
 Test and use a closure-allocation scheme that
integrates and improves previous closure
analysis techniques and construct safely
linked closures.
 Decide where and how to represent closures at
runtime
Literature Review
Comparison of Stack and Heap
Costs involved in creating, accessing
and destroying activation records
whether they are on heap or on stack.
Comparison of Stack and Heap
Component
Heap
Stack
Copying and sharing
0.0
3.4
Frames pointers
2.0
0.0
Creation
3.1
1.0
Cache write misses
0.0 or 5.3
0.0
Disposal (pop)
1.4
1.0
Cache read misses
1.0
0.0
Total Cost
7.5 or 12.8
5.4
Call/cc
O(1)
O(N)
-----------------------------------------------------------------------Implementation
easy
hard
Comparison Results
The write-miss policy of the machine’s primary cache.
On machines with fetch-on-write or write-around writemiss policies, heap-allocated frames are significantly
more expensive
Stacks are harder to implement without space leaks as
explained later
If programming language supports call-with-currentcontinuation (call/cc), stacks have a much higher cost.
Implementation
Implementation of Heap frames
 To achieve a good performance with heap
frames, it is necessary to have a sophisticated
algorithm to choose closure representations.
Implementation of Stacks
 A good closure analysis algorithm must be used
to preserve space complexity while still trying to
avoid too much copying
 If call/cc is to be supported, then stack copying
or some more complicated technique must be
implemented
Contd….
In a system with multiple threads, each thread
must have its own stack. A large contiguous
region of virtual memory must be reserved.
Stack overflow detection must be implemented.
In most cases this is handled automatically by
the operating system using virtual- memory page
faults.
Research Design
I would like to adopt a new closure allocation
scheme that does not use any runtime stack.
Instead, all closure environments are either
allocated in the heap or in registers.
Efficiency and Space Safety
•
•
•
Flat Closures
Linked Closures
Safely Linked closure
An Example in ML
fun f (v, w, x, y, z) =
let fun g () =
let val u = hd (v)
fun h () =
let fun i() = w+x+y+z+3
in (i,u)
end
in h
end
Contd…
fun big n = if n<1 then nil else n :: big(n-1)
fun loop (n, res) =
if n<1 then res
else let val s = f(big(N),0,0,0,0) ()
in loop(n-1,s::res)
end
val result = loop(N,nil)
Flat Closures
Linked Closures
Comparison of various
Closures

Flat Closures – The final result (I.e result)
contains ‘N’ copies for h, thus it uses at most
O(N) space.

Linked Closures – Each closure for ‘h’ contains a
pointer to the closure for ‘g’, which contains a
list ‘v’ of size ‘N’. Since the final result keeps ‘N’
closures for ‘h’ simultaneously, it uses O(N^2)
space. This space leak is caused by
inappropriate retaining of some dead objects (‘v’)
that should be reclaimed by the garbage
collection.
SSC Rule
Garbage - collected languages should
satisfy the safe for space complexity
rule. Each local variable should be
considered “dead” after its last use in
the current function body. This rule is
not important for C-like languages
because we can manually deallocate
intermediate data structures in the
program source.
Drawbacks of Flat and
Linked Closures

Linked Closures – they violate the SSC
rule because local variable bindings will
stay on the stack until they exit their
scope, so they may remain live even after
their last use.

Flat Closures – they satisfy the SSC rule,
but require that variables be copied many
times from one closure to another.
Safely Linked Closures
Safely Linked Closures
These closures contain only variables
actually needed in the function but avoid
closure copying by grouping variables with
the same life time into a sharable record.
In linked closures accessing variables is
quite expensive because at least two links
need to be traversed. But the nesting level
of safely linked closures never exceeds two.
So they still enjoy very fast variable access
time.
Closure Conversion
Algorithm



I have chosen an algorithm proposed by A.Shao and
A.Appel for closure conversion with the following
properties:
Activation records are allocated in the heap, hence they
can be shared with other heap-allocated closures.
Once a closure is created, no later writes are made to it;
this makes generational garbage collection and call/cc
efficient.
It makes programs smaller and faster. It decreases the rate
of heap allocation by 32% and reduces the amount of live
data preserved by garbage collection.
Conclusions
Thus by using safely linked closures
and allocating closures in the heap
and using the algorithm proposed by
A.Shao and A.Appel for closure
conversion we can improve the
design of the compilers for higherorder
functional
programming
languages such as ML, Scheme and
Small Talk.
Questions
Questions