What is wrong?

Notice: Before sending an error with the download, please try the direct link first: Practical shortcut fusion for coinductive sequence types

Loading...

You must sign in to do that.

Forgot password?

Practical shortcut fusion for coinductive sequence types

Practical shortcut fusion for coinductive sequence types

Practical shortcut fusion for coinductive sequence types

Score: ---- | 0 votes
| Sending vote
| Voted!
|

Book Details:

pos
Global
pos
Category
Year:2010
Publisher:University of Oxford
Pages:281 pages
Language:english
Since:20/05/2014
Size:1.15 MB
License:Pending review

Content:

In functional programming it is common practice to build modular programs by composing functions where the intermediate values are data structures such as lists or arrays. A desirable optimisation for programs written in this style is to fuse the composed functions and thereby eliminate the intermediate data structures and their associated runtime costs.

Stream fusion is one such fusion optimisation that can eliminate intermediate data structures, including lists, arrays and other abstract data types that can be viewed as coinductive sequences. The fusion transformation can be applied fully automatically by a general purpose optimising compiler. The stream fusion technique itself has been presented previously and many practical implementations exist. The primary contributions of this thesis address the issues of correctness and optimisation: whether the transformation is correct and whether the transformation is an optimisation.

Proofs of shortcut fusion laws have typically relied on parametricity by making use of free theorems. Unfortunately, most functional programming languages have semantics for which classical free theorems do not hold unconditionally; additional side conditions are required. In this thesis we take an approach based not on parametricity but on data abstraction. Using this approach we prove the correctness of stream fusion for lists – encompassing the fusion system as a whole, not merely the central fusion law. We generalise this proof to give a framework for proving the correctness of stream fusion for any abstract data type that can be viewed as a coinductive sequence and give as an instance of the framework, a simple model of arrays. The framework requires that each fusible function satisfies a simple data abstraction property. We give proofs of this property for several standard list functions.

Categories:

Tags:

Loading comments...

Scanning lists...

The book in numbers

global rank

online since

20/05/2014

rate score

Nothing yet...

votes

Nothing yet...

Social likes

Nothing yet...

Views

Downloads

This may take several minutes

Interest

Countries segmentation

This may take several minutes

Source Referers

Websites segmentation

evolution

This may take several minutes

Loading...