Please use this identifier to cite or link to this item: https://doi.org/10.1023/A:1012996816178
Title: Calculating sized types
Authors: Chin, W.-N. 
Khoo, S.-C. 
Keywords: Presburger formulae
Program analysis and optimization
Type inference
Issue Date: 2001
Source: Chin, W.-N.,Khoo, S.-C. (2001). Calculating sized types. Higher-Order and Symbolic Computation 14 (2-3) : 261-300. ScholarBank@NUS Repository. https://doi.org/10.1023/A:1012996816178
Abstract: Many program optimizations and analyses, such as array-bounds checking, termination analysis, etc., depend on knowing the size of a function's input and output. However, size information can be difficult to compute. Firstly, accurate size computation requires detecting a size relation between different inputs of a function. Secondly, different optimizations and analyses may require slightly different size information, and thus slightly different computation. Literature in size computation has mainly concentrated on size checking, instead of size inference. In this paper, we provide a generic framework on which different size variants can be expressed and computed. We also describe an effective algorithm for inferring, instead of checking, size information. Size information are expressed in terms of Presburger formulae, and our algorithm utilizes the Omega Calculator to compute as exact a size information as possible, within the linear arithmetic capability.
Source Title: Higher-Order and Symbolic Computation
URI: http://scholarbank.nus.edu.sg/handle/10635/39324
ISSN: 13883690
DOI: 10.1023/A:1012996816178
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

46
checked on Dec 5, 2017

Page view(s)

62
checked on Dec 8, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.