Abstract
Can formal specification techniques be scaled-up to industrial problems such as the development of domain-specific languages and the renovation of large COBOL systems?
We have developed a compiler for the specification formalism ASF+SDF that has been used successfully to meet such industrial challenges. This result is achieved in two ways: the compiler performs a variety of optimizations and generates efficient C code, and the compiled code uses a run-time memory management system based on maximal subterm sharing and mark-and-sweep garbage collection.
We present an overview of these techniques and evaluate their effectiveness in several benchmarks. It turns out that execution speed of compiled ASF+SDF specifications is at least as good as that of comparable systems, while memory usage is in many cases an order of magnitude smaller.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Allen, J.R.: Anatomy of LISP. McGraw-Hill, New York (1978)
Appel, A.W., Goncalves, M.J.R.: Hash-consing garbage collection. Technical Report CS-TR-412-93, Princeton University (1993)
Appel, A.W., MacQueen, D.: A standard ML compiler. In: Kahn, G. (ed.) FPCA 1987. LNCS, vol. 274, pp. 301–324. Springer, Heidelberg (1987)
Arnold, B.R.T., van Deursen, A., Res, M.: An algebraic specification of a language for describing financial products. In: Wirsing, M. (ed.) ICSE-17 Workshop on Formal Methods Application in Software Engineering, pp. 6–13. IEEE, Los Alamitos (1995)
Bergstra, J.A., Heering, J., Klint, P. (eds.): Algebraic Specification. ACM Press/Addison-Wesley (1989)
Boehm, H.: Space efficient conservative garbage collection. In: Proceedings of the ACM SIGPLAN 1991 Conference on Programming Language Design and Implementation, SIGPLAN Notices, June 1993, vol. 28, pp. 197–206 (1993)
Boehm, H., Weiser, M.: Garbage collection in an uncooperative environment. Software - Practice and Experience (SPE) 18(9), 807–820 (1988)
Borovanský, P., Kirchner, C., Kirchner, H., Moreau, P.-E., Vittek, M.: ELAN: A logical framework based on computational systems. In: Meseguer, J. (ed.) Proceedings of the First International Workshop on Rewriting Logic. Electronic Notes in Theoretical Computer Science, vol. 4. Elsevier Science, Amsterdam (1996)
van den Brand, M.G.J., van Deursen, A., Klint, P., Klusener, S., van der Meulen, A.E.: Industrial applications of ASF+SDF. In: Wirsing, M., Nivat, M. (eds.) AMAST 1996. LNCS, vol. 1101. Springer, Heidelberg (1996)
van den Brand, M.G.J., Heering, J., Klint, P., Olivier, P.A.: Compiling rewrite systems: The asf+sdf compiler. Technical report, Centrum voor Wiskunde en Informatica (CWI) (1999) (in preparation)
van den Brand, M.G.J., Klint, P., Verhoef, C.: Term rewriting for sale. In: Kirchner, C., Kirchner, H. (eds.) Proceedings of the First International Workshop on Rewriting Logic and its Applications. Electronic Notes in Theoretical Computer Science, vol. 15, pp. 139–161. Elsevier Science, Amsterdam (1998)
van den Brand, M.G.J., Sellink, M.P.A., Verhoef, C.: Generation of components for software renovation factories from context-free grammars. In: Baxter, I.D., Quilici, A., Verhoef, C. (eds.) Proceedings of the Fourth Working Conference on Reverse Engineering, pp. 144–153 (1997)
van den Brand, M.G.J., Visser, E.: Generation of formatters for context-free languages. ACM Transactions on Software Engineering and Methodology 5, 1–41 (1996)
Brunekreef, J.J.: A transformation tool for pure Prolog programs. In: Gallagher, J.P. (ed.) LOPSTR 1996. LNCS, vol. 1207, pp. 130–145. Springer, Heidelberg (1997)
van Deursen, A., Heering, J., Klint, P. (eds.): Language Prototyping: An Algebraic Specification Approach. AMAST Series in Computing, vol. 5. World Scientific, Singapore (1996)
Didrich, K., Fett, A., Gerke, C., Grieskamp, W., Pepper, P.: OPAL: Design and implementation of an algebraic programming language. In: Gutknecht, J. (ed.) Programming Languages and System Architectures. LNCS, vol. 782, pp. 228–244. Springer, Heidelberg (1994)
Dik, C.H.S.: A fast implementation of the Algebraic Specification Formalism. Master’s thesis, University of Amsterdam, Programming Research Group (1989)
Hartel, P.H., et al.: Benchmarking implementations of functional languages with ’pseudoknot’, a float-intensive benchmark. Journal of Functional Programming 6, 621–655 (1996)
Heering, J., Hendriks, P.R.H., Klint, P., Rekers, J.: The syntax definition formalism DF — Reference manual. In: SIGPLAN Notices, vol. 24(11), pp. 43–75 (1989), Most recent version available at http://www.cwi.nl/~gipe/
Jones, R., Lins, R.: Garbage Collection: Algorithms for Automatic Dynamic Memory Management. Wiley, Chichester (1996)
Peyton Jones, S.L., Hall, C.V., Hammond, K., Partain, W.D., Wadler, P.L.: The lasgow haskell compiler: a technical overview. In: Proc. Joint Framework for Information Technology (JFIT) Technical Conference, pp. 249–257 (1993)
Kaplan, S.: A compiler for conditional term rewriting systems. In: Lescanne, P. (ed.) RTA 1987. LNCS, vol. 256. Springer, Heidelberg (1987)
Klint, P.: A meta-environment for generating programming environments. ACM transactions on Software Engineering and Methodology 2, 176–201 (1993)
Plasmeijer, M.J., van Eekelen, M.C.J.D.: Concurrent Clean - version 1.0 - Language Reference Manual, draft version. Department of Computer Science, University of Nijmegen, Nijmegen, The Netherlands (1994)
Terashima, M., Kanada, Y.: HLisp—its concept, implementation and applications. Journal of Information Processing 13(3), 265–275 (1990)
Visser, E.: Syntax Definition for Language Prototyping. PhD thesis, University of Amsterdam (1997)
Wadler, P.: Deforestation: Transforming programs to eliminate trees. Theoretical Computer Science 73(2), 231–248 (1990)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
van den Brand, M., Klint, P., Olivier, P. (1999). Compilation and Memory Management for ASF+SDF. In: Jähnichen, S. (eds) Compiler Construction. CC 1999. Lecture Notes in Computer Science, vol 1575. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-49051-7_14
Download citation
DOI: https://doi.org/10.1007/978-3-540-49051-7_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-65717-0
Online ISBN: 978-3-540-49051-7
eBook Packages: Springer Book Archive