Hostname: page-component-cd9895bd7-dk4vv Total loading time: 0 Render date: 2024-12-19T02:44:55.076Z Has data issue: false hasContentIssue false
  • English
  • Français

Practical run-time checking via unobtrusive property caching

Published online by Cambridge University Press:  03 September 2015

NATALIIA STULOVA ,
JOSÉ F. MORALES  and
MANUEL V. HERMENEGILDO
NATALIIA STULOVA
Affiliation:
IMDEA Software Institute, (e-mail: [email protected], [email protected], [email protected])
JOSÉ F. MORALES
Affiliation:
IMDEA Software Institute, (e-mail: [email protected], [email protected], [email protected])
MANUEL V. HERMENEGILDO
Affiliation:
IMDEA Software Institute, (e-mail: [email protected], [email protected], [email protected]) School of Computer Science, Technical University of Madrid (UPM) (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

The use of annotations, referred to as assertions or contracts, to describe program properties for which run-time tests are to be generated, has become frequent in dynamic programing languages. However, the frameworks proposed to support such run-time testing generally incur high time and/or space overheads over standard program execution. We present an approach for reducing this overhead that is based on the use of memoization to cache intermediate results of check evaluation, avoiding repeated checking of previously verified properties. Compared to approaches that reduce checking frequency, our proposal has the advantage of being exhaustive (i.e., all tests are checked at all points) while still being much more efficient than standard run-time checking. Compared to the limited previous work on memoization, it performs the task without requiring modifications to data structure representation or checking code. While the approach is general and system-independent, we present it for concreteness in the context of the Ciao run-time checking framework, which allows us to provide an operational semantics with checks and caching. We also report on a prototype implementation and provide some experimental results that support that using a relatively small cache leads to significant decreases in run-time checking overhead.

Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 15 , Special Issue 4-5: 31st International Conference on Logic Programming , July 2015 , pp. 726 - 741
Copyright
Copyright © Cambridge University Press 2015 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Boye, J., Drabent, W. and Małuszyński, J. 1997. Declarative Diagnosis of Constraint Programs: an assertion-based approach. In Proc. of the 3rd. Int'l Workshop on Automated Debugging–AADEBUG'97. U. of Linköping Press, Linköping, Sweden, 123–141.Google Scholar
Bueno, F., Deransart, P., Drabent, W., Ferrand, G., Hermenegildo, M., Maluszynski, J. and Puebla, G. 1997. On the Role of Semantic Approximations in Validation and Diagnosis of Constraint Logic Programs. In Proc. of the 3rd. Int'l WS on Automated Debugging–AADEBUG. U. Linköping Press, 155–170.Google Scholar
Cartwright, R. and Fagan, M. 1991. Soft Typing. In PLDI'91. SIGPLAN, ACM, 278–292.Google Scholar
Dart, P. and Zobel, J. 1992. A Regular Type Language for Logic Programs. In Types in Logic Programming. MIT Press, 157–187.Google Scholar
Dietrich, S. 1987. Extension Tables for Recursive Query Evaluation. Ph.D. thesis, Departament of Computer Science, State University of New York.Google Scholar
Dimoulas, C. and Felleisen, M. 2011. On contract satisfaction in a higher-order world. ACM Trans. Program. Lang. Syst. 33, 5, 16.Google Scholar
Fähndrich, M. and Logozzo, F. 2011. Static contract checking with abstract interpretation. In Proceedings of the 2010 International Conference on Formal Verification of Object-oriented Software. FoVeOOS'10. Springer-Verlag, Berlin, Heidelberg, 10–30.Google Scholar
Findler, R. B. and Felleisen, M. 2002. Contracts for higher-order functions. In ICFP, Wand, M. and Jones, S. L. P., Eds. ACM, 48–59.Google Scholar
Hermenegildo, M., Puebla, G. and Bueno, F. 1999. Using Global Analysis, Partial Specifications, and an Extensible Assertion Language for Program Validation and Debugging. In The Logic Programming Paradigm: a 25–Year Perspective, Apt, K. R., Marek, V., Truszczynski, M., and Warren, D. S., Eds. Springer-Verlag, 161–192.CrossRefGoogle Scholar
Hermenegildo, M., Puebla, G., Bueno, F. and García, P. L. 2005. Integrated Program Debugging, Verification, and Optimization Using Abstract Interpretation (and The Ciao System Preprocessor). Science of Computer Programming 58, 1–2.CrossRefGoogle Scholar
Hermenegildo, M. V., Bueno, F., Carro, M., López, P., Mera, E., Morales, J. and Puebla, G. 2012. An Overview of Ciao and its Design Philosophy. Theory and Practice of Logic Programming 12, 1–2 (January), 219–252. http://arxiv.org/abs/1102.5497.Google Scholar
Koukoutos, E. and Kuncak, V. 2014. Checking Data Structure Properties Orders of Magnitude Faster. In Runtime Verification, Bonakdarpour, B. and Smolka, S. A., Eds. Lecture Notes in Computer Science, vol. 8734. Springer International Publishing, 263–268.CrossRefGoogle Scholar
Laï, C. 2000. Assertions with Constraints for CLP Debugging. In Analysis and Visualization Tools for Constraint Programming, Deransart, P., Hermenegildo, M. V., and Maluszynski, J., Eds. Lecture Notes in Computer Science, vol. 1870. Springer, 109–120.Google Scholar
Lamport, L. and Paulson, L. C. 1999. Should your specification language be typed? ACM Transactions on Programming Languages and Systems 21, 3 (May), 502–526.CrossRefGoogle Scholar
Leavens, G. T., Leino, K. R. M. and Müller, P. 2007. Specification and verification challenges for sequential object-oriented programs. Formal Asp. Comput. 19, 2, 159–189.Google Scholar
Mera, E., López-García, P. and Hermenegildo, M. 2009. Integrating Software Testing and Run-Time Checking in an Assertion Verification Framework. In 25th International Conference on Logic Programming (ICLP'09). Number 5649 in LNCS. Springer-Verlag, 281–295.Google Scholar
Mera, E., Trigo, T., López-García, P. and Hermenegildo, M. 2011. Profiling for Run-Time Checking of Computational Properties and Performance Debugging. In Practical Aspects of Declarative Languages (PADL'11). LNCS, vol. 6539. Springer-Verlag, 38–53.Google Scholar
Mera, E. and Wielemaker, J. 2013. Porting and refactoring Prolog programs: the PROSYN case study. TPLP 13, 4–5-Online-Supplement.Google Scholar
Muthukumar, K. and Hermenegildo, M. 1992. Compile-time Derivation of Variable Dependency Using Abstract Interpretation. Journal of Logic Programming 13, 2/3 (July), 315–347.Google Scholar
Puebla, G., Bueno, F. and Hermenegildo, M. 1997. An Assertion Language for Debugging of Constraint Logic Programs. In Proceedings of the ILPS'97 Workshop on Tools and Environments for (Constraint) Logic Programming. Available from ftp://clip.dia.fi.upm.es/pub/papers/assert_lang_tr_discipldeliv.ps.gz as technical report CLIP2/97.1.Google Scholar
Puebla, G., Bueno, F. and Hermenegildo, M. 2000a. An Assertion Language for Constraint Logic Programs. In Analysis and Visualization Tools for Constraint Programming. Number 1870 in LNCS. Springer-Verlag, 23–61.Google Scholar
Puebla, G., Bueno, F. and Hermenegildo, M. 2000b. Combined Static and Dynamic Assertion-Based Debugging of Constraint Logic Programs. In Logic-based Program Synthesis and Transformation (LOPSTR'99). Number 1817 in LNCS. Springer-Verlag, 273–292.CrossRefGoogle Scholar
Stulova, N., Morales, J. F. and Hermenegildo, M. V. 2014. Assertion-based Debugging of Higher-Order (C)LP Programs. In 16th Int'l. ACM SIGPLAN Symposium on Principles and Practice of Declarative Programming (PPDP'14). ACM Press.Google Scholar
Swift, T. and Warren, D. S. 2012. XSB: Extending Prolog with Tabled Logic Programming. TPLP 12, 1–2, 157–187.Google Scholar
Tamaki, H. and Sato, M. 1986. OLD Resol. with Tabulation. In ICLP. LNCS, 84–98.Google Scholar
Tobin-Hochstadt, S. and Felleisen, M. 2008. The Design and Implementation of Typed Scheme. In POPL. ACM, 395–406.Google Scholar
Warren, D. S. 1992. Memoing for Logic Programs. CACM 35, 3, 93–111.Google Scholar
Warren, R., Hermenegildo, M. and Debray, S. K. 1988. On the Practicality of Global Flow Analysis of Logic Programs. In Fifth International Conference and Symposium on Logic Programming. MIT Press, 684–699.Google Scholar
Zhou, N.-F. and Have, C. T. 2012. Efficient Tabling of Structured Data with Enhanced Hash-Consing. Theory and Practice of Logic Programming 12, 547–563.Google Scholar
Supplementary material: PDF

Stulova supplementary material

Online Appendix

Download Stulova supplementary material(PDF)
PDF 2.8 MB