Smith, Alexander Ian (2015). On the design of finite-state type systems. University of Birmingham. Ph.D.
|
Smith15PhD.pdf
PDF - Accepted Version Download (846kB) |
Abstract
Practical computers have only finite amounts of memory. However, the programs that run on them are often written in languages that effectively assume (via providing constructs such as general recursion) that infinite memory is available, meaning that an implementation of those programs is necessarily an approximation.
The main focus of this thesis is on the use of contraction: the ability to use a function parameter more than once in the body of that function (or more generally, to mention a free variable more than once in a term). Unrestricted contraction is a common reason for a language to require unbounded amounts of memory to implement.
This thesis looks at a range of type systems, both existing and new, that restrict the use of contraction so that they can be implemented with finite amounts of state, identifying common themes, and explaining and suggesting solutions for common deficiencies. In particular, different restrictions on contraction are seen to correspond to different features of the language’s implementation.
Type of Work: | Thesis (Doctorates > Ph.D.) | ||||||
---|---|---|---|---|---|---|---|
Award Type: | Doctorates > Ph.D. | ||||||
Supervisor(s): |
|
||||||
Licence: | |||||||
College/Faculty: | Colleges (2008 onwards) > College of Engineering & Physical Sciences | ||||||
School or Department: | School of Computer Science | ||||||
Funders: | None/not applicable | ||||||
Subjects: | Q Science > QA Mathematics > QA75 Electronic computers. Computer science | ||||||
URI: | http://etheses.bham.ac.uk/id/eprint/6120 |
Actions
Request a Correction | |
View Item |
Downloads
Downloads per month over past year