Abstract
A scheme is presented to enable the mode analysis of concurrent logic programs manipulating arrays containing both ground and non-ground elements. To do this we leverage constraint-propagation mode analysis techniques. The key ideas are to restrict multiple assignments only to variables at the leaves of paths, and to extend the language family with array comprehensions. The result is a language not significantly different than generic committed-choice languages, which can be safely mode analyzed, producing useful (not overly conservative) information, even for programs that assign to unbound array elements. An implementation of the analysis is presented.
Preview
Unable to display preview. Download preview PDF.
References
M. Bruynooghe and G. Janssens. An Instance of Abstract Interpretation Integrating Type and Mode Inference. In International Conference and Symposium on Logic Programming, pages 669–683. University of Washington, MIT Press, August 1988. Extended version in Journal of Logic Programming, 1994.
S. K. Debray. Static Inference of Modes and Data Dependencies in Logic Programs. ACM Transactions on Programming Languages and Systems, 11(3):418–450, July 1989.
S. K. Debray and D. S. Warren. Automatic Mode Inference for Prolog Programs. Journal of Logic Programming, 5(3):207–229, September 1988.
P. Hudak, S. Peyton-Jones, and P. Wadler. Report on Programming Language Haskell: A Non-Strict, Purely Functional Language, Version 1.2. ACM SIGPLAN Notices, 27(5):1–164, May 1992.
A. King and P. Soper. Schedule Analysis of Concurrent Logic Programs. In Joint International Conference and Symposium on Logic Programming, pages 478–492. Washington D.C., MIT Press, November 1992.
M. Koshimura and R. Hasegawa. A Mode Analyzer for FGHC Programs in a Model Generation Theorem Prover. In Proceedings of the 47th Annual Convention IPS Japan, 1993. In Japanese.
J. Larson, B. Massey, and E. Tick. Super Monaco: Its Portable and Efficient Parallel Runtime System. In EURO-PAR, Stockholm, August 1995.
B. C. Massey and E. Tick. Sequentialization of Parallel Logic Programs with Mode Analysis. In International Conference on Logic Programming and Automated Reasoning, number 698 in Lecture Notes in Artificial Intelligence, pages 205–216, St. Petersburg, July 1993. Springer-Verlag.
B. C. Massey and E. Tick. Demand-Driven Execution of Concurrent Logic Programs. In International Conference on Parallel Architectures and Compilation Techniques, pages 215–224, Montreal, August 1994. North-Holland.
C. S. Mellish. Some Global Optimizations for a Prolog Compiler. Journal of Logic Programming, 2(1):43–66, April 1985.
R. S. Nikhil. Id (Version 90.0) Reference Manual. Technical Report CSG Memo 284-a, MIT Laboratory for Computer Science, 545 Technology Square, Cambridge, MA 02139, USA, July 1990.
A. V. S. Sastry, W. Clinger, and Z. Ariola. Order-of-Evaluation Analysis for Destructive Updates in Strict Functional Languages with Flat Aggregates. In Conference on Functional Programming Languages and Computer Architecture, pages 266–275. Copenhagen, ACM Press, June 1993.
R. Sundararajan. Data Flow and Control Flow Analysis of Logic Programs. PhD thesis, Department of Computer Science, University of Oregon, 1994. Also available as Technical Report CIS-TR-94-08.
E. Tick. Practical Static Mode Analyses of Concurrent Logic Languages. In International Conference on Parallel Architectures and Compilation Techniques, pages 205–214, Montreal, August 1994. North-Holland.
E. Tick and C. Banerjee. Performance Evaluation of Monaco Compiler and Runtime Kernel. In International Conference on Logic Programming, pages 757–773. Budapest, MIT Press, June 1993.
E. Tick and M. Koshimura. Static Mode Analyses of Concurrent Logic Languages. Journal of Programming Language Design and Implementation, 1995. Accepted. Also available as University of Oregon Technical Report CIS-TR-94-06.
E. Tick, B. C. Massey, F. Rakoczi, and P. Tulayathun. Concurrent Logic Programsa la Mode. In E. Tick and G. Succi, editors, Implementations of Logic Programming Systems, pages 239–244. Kluwer Academic Publishers, 1994.
K. Ueda. Report on the Optimization of Concurrent Logic Language Implementations, March 1994. In Japanese.
K. Ueda and M. Morita. Message-Oriented Parallel Implementation of Moded Flat GHC. In International Conference on Fifth Generation Computer Systems, pages 799–808, Tokyo, June 1992. ICOT.
K. Ueda and M. Morita. Moded Flat GHC and Its Message-Oriented Implementation Technique. New Generation Computing, 13(1):3–43, 1994.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Massey, B.C., Tick, E. (1995). Modes of comprehension: Mode analysis of arrays and array comprehensions. In: Hermenegildo, M., Swierstra, S.D. (eds) Programming Languages: Implementations, Logics and Programs. PLILP 1995. Lecture Notes in Computer Science, vol 982. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0026822
Download citation
DOI: https://doi.org/10.1007/BFb0026822
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60359-7
Online ISBN: 978-3-540-45048-1
eBook Packages: Springer Book Archive