Modular average case analysis: Language implementation and extension


Autoria(s): Gao, Ang
Contribuinte(s)

Schellekens, Michel P.

Science Foundation Ireland

Data(s)

27/04/2013

27/04/2013

2013

2013

Resumo

Motivated by accurate average-case analysis, MOdular Quantitative Analysis (MOQA) is developed at the Centre for Efficiency Oriented Languages (CEOL). In essence, MOQA allows the programmer to determine the average running time of a broad class of programmes directly from the code in a (semi-)automated way. The MOQA approach has the property of randomness preservation which means that applying any operation to a random structure, results in an output isomorphic to one or more random structures, which is key to systematic timing. Based on original MOQA research, we discuss the design and implementation of a new domain specific scripting language based on randomness preserving operations and random structures. It is designed to facilitate compositional timing by systematically tracking the distributions of inputs and outputs. The notion of a labelled partial order (LPO) is the basic data type in the language. The programmer uses built-in MOQA operations together with restricted control flow statements to design MOQA programs. This MOQA language is formally specified both syntactically and semantically in this thesis. A practical language interpreter implementation is provided and discussed. By analysing new algorithms and data restructuring operations, we demonstrate the wide applicability of the MOQA approach. Also we extend MOQA theory to a number of other domains besides average-case analysis. We show the strong connection between MOQA and parallel computing, reversible computing and data entropy analysis.

Science Foundation Ireland (07/IN.1/I977)

Accepted Version

Not peer reviewed

Formato

application/pdf

Identificador

Gao, A. 2013. Modular average case analysis: Language implementation and extension. PhD Thesis, University College Cork.

240

http://hdl.handle.net/10468/1089

Idioma(s)

en

en

Publicador

University College Cork

Direitos

© 2013, Ang Gao

http://creativecommons.org/licenses/by-nc-nd/3.0/

Palavras-Chave #Module average case analysis #Randomness preservation #Language design #Data structures and algorithm analysis #Parallel computing #Parallel processing (Electronic computers) #Software engineering.
Tipo

Doctoral thesis

Doctoral

PhD (Science)