¿Qué está mal?

Aviso: Antes de informar sobre un error con la descarga, por favor, prueba el enlace directo: Practical shortcut fusion for coinductive sequence types


Debes iniciar sesión para hacer esto.

Practical shortcut fusion for coinductive sequence types

Practical shortcut fusion for coinductive sequence types

Practical shortcut fusion for coinductive sequence types

Puntuación: ---- | 0 votos
| Enviando voto
| ¡Votado!

Detalles del libro:

Editor:University of Oxford
Páginas:281 páginas
Tamaño:1.15 MB
Licencia:Pendiente de revisión


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.



Cargando comentarios...

Escaneando listas...

El libro en números

Posición global

posición en categorías

en catálogo desde



Nothing yet...


Nothing yet...

'LIKES' sociales

Nothing yet...



Esto puede tardar un momento


Segmentación por países

Esto puede tardar un momento

Páginas de entrada

Segmentación por sitios web


Esto puede tardar un momento