An investigation of nondeterminism in functional programming languages
- Authors: Graham, Gwyneth Clare
- Date: 1997
- Subjects: Functional programming languages
- Language: English
- Type: Thesis , Masters , MSc
- Identifier: vital:4658 , http://hdl.handle.net/10962/d1006658 , Functional programming languages
- Description: This thesis investigates nondeterminism in functional programming languages. To establish a precise understanding of nondeterministic language properties, Sondergaard and Sestoft's analysis and definitions of functional language properties are adopted as are the characterizations of weak and strong nondeterminism. This groundwork is followed by a denotational semantic description of a nondeterministic language (suggested by Sondergaard and Sestoft). In this manner, a precise characterization of the effects of strong nondeterminism is developed. Methods used to hide nondeterminism to in order to overcome or sidestep the problem of strong nondeterminism in pure functional languages are defined. These different techniques ensure that functional languages remain pure but also include some of the advantages of nondeterminism. Lastly, this discussion of nondeterminism is applied to the area of functional parallel language implementation to indicate that the related problem and the possible solutions are not purely academic. This application gives rise to an interesting discussion on optimization of list parallelism. This technique relies on the ability to decide when a bag may be used instead of a list.
- Full Text:
- Date Issued: 1997
Static analysis of functional languages
- Authors: Mountjoy, Jon-Dean
- Date: 1994 , 2012-10-10
- Subjects: Functional programming languages
- Language: English
- Type: Thesis , Masters , MSc
- Identifier: vital:4669 , http://hdl.handle.net/10962/d1006690 , Functional programming languages
- Description: Static analysis is the name given to a number of compile time analysis techniques used to automatically generate information which can lead to improvements in the execution performance of function languages. This thesis provides an introduction to these techniques and their implementation. The abstract interpretation framework is an example of a technique used to extract information from a program by providing the program with an alternate semantics and evaluating this program over a non-standard domain. The elements of this domain represent certain properties of interest. This framework is examined in detail, as well as various extensions and variants of it. The use of binary logical relations and program logics as alternative formulations of the framework , and partial equivalence relations as an extension to it, are also looked at. The projection analysis framework determines how much of a sub-expression can be evaluated by examining the context in which the expression is to be evaluated, and provides an elegant method for finding particular types of information from data structures. This is also examined. The most costly operation in implementing an analysis is the computation of fixed points. Methods developed to make this process more efficient are looked at. This leads to the final chapter which highlights the dependencies and relationships between the different frameworks and their mathematical disciplines. , KMBT_223
- Full Text:
- Date Issued: 1994