Polynomial Size Analysis of First-Order Shapely Functions

Details Polynomial Size Analysis of First-Order Shapely Functions Polynomial Size Analysis of First-Order Shapely Functions

2009-02-12

arxiv.org/abs/0902.2073v2

LMCS 5 (2:10) 2009

Computer Science

Logic in Computer Science

35 pages, 1 figure

Scientific paper

10.2168/LMCS-5(2:10)2009

We present a size-aware type system for first-order shapely function definitions. Here, a function definition is called shapely when the size of the result is determined exactly by a polynomial in the sizes of the arguments. Examples of shapely function definitions may be implementations of matrix multiplication and the Cartesian product of two lists. The type system is proved to be sound w.r.t. the operational semantics of the language. The type checking problem is shown to be undecidable in general. We define a natural syntactic restriction such that the type checking becomes decidable, even though size polynomials are not necessarily linear or monotonic. Furthermore, we have shown that the type-inference problem is at least semi-decidable (under this restriction). We have implemented a procedure that combines run-time testing and type-checking to automatically obtain size dependencies. It terminates on total typable function definitions.

Affiliated with

Also associated with

No associations

Rating

Polynomial Size Analysis of First-Order Shapely Functions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Polynomial Size Analysis of First-Order Shapely Functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Polynomial Size Analysis of First-Order Shapely Functions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-556246