کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
422404 685082 2008 19 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Inferring Static Non-monotone Size-aware Types Through Testing
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Inferring Static Non-monotone Size-aware Types Through Testing
چکیده انگلیسی

We propose a size analysis procedure that combines testing and type checking to automatically obtain static output-on-input size dependencies for first-order functions. Attention is restricted to functions for which the size of the result is strictly polynomial, not necessarily monotone, in the sizes of the arguments.To infer a size dependency, the procedure generates hypotheses for increasing degrees of polynomials. For each degree, a polynomial is defined by a finite number of points. Based on interpolation theory, in this paper we establish an upper bound on the number of test runs and a correct choice of test data that guarantees that all polynomials representing sizes of output lists can be found. The resulting hypothesis is then checked using an existing type checking procedure.The procedure is not tied to the current size-aware type checker. The size-aware type of a function will be inferred if it exists and if it is accepted by a size-aware type checker. For terminating functions, our size-aware type inference procedure is complete with respect to type checking: if a function is well-typed, then the inference procedure terminates and produces corresponding size dependencies.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Theoretical Computer Science - Volume 216, 4 July 2008, Pages 45-63