Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

The ASF+SDF Meta-Environment is an interactive language development environment whose main application areas are definition and implementation of domain-specific languages, generation of program analysis and transformation tools, and production of software renovation tools. It uses conditional rewrite rules to define the dynamic semantics and other tool-oriented aspects of languages, so the effectiveness of the generated tools is critically dependent on the quality of the rewrite rule implementation. The ASF+SDF rewrite rule compiler generates C code, thus taking advantage of C's portability and the sophisticated optimization capabilities of current C compilers as well as avoiding potential abstract machine interface bottlenecks. It can handle large (10,000+ rule) language definitions and uses an efficient run-time storage scheme capable of handling large (1,000,000+ node) terms. Term storage uses maximal subterm sharing (hash-consing), which turns out to be more effective in the case of ASF+SDF than in Lisp or SML. Extensive benchmarking has shown the time and space performance of the generated code to be as good as or better than that of the best current rewrite rule and functional language compilers.

REFERENCES

• 1: John Allen, Anatomy of LISP, McGraw-Hill, Inc., New York, NY, 1978
• 2: Andrew W. Appel, Compiling with continuations, Cambridge University Press, New York, NY, 1992
• 3: Appel, A. W. and Gonçalves, M. J. R. 1993. Hash-consing garbage collection. Technical report CS-TR-412-93, Princeton University,
• 4: Krzysztof R. Apt , Jacob Brunekreef , Vincent Partington , Andrea Schaerf, Alma-O: an imperative language that supports declarative programming, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.5, p.1014-1066, Sept. 1998 [doi>10.1145/293677.293679]
• 5: Dan Benanav , Deepak Kapur , Paliath Narendran, Complexity of matching problems, Proc. of the first international conference on Rewriting techniques and applications, p.417-429, December 1985, Dijon, France
• 6: J. A. Bergstra , Jan Heering , Paul Klint, Algebraic specification, ACM Press, New York, NY, 1989
• 7: J. A. Bergstra , P. Klint, The discrete time TOOLBUS—a software coordination architecture, Science of Computer Programming, v.31 n.2-3, p.205-229, July 1, 1998 [doi>10.1016/S0167-6423(97)00021-X]
• 8: Jan A. Bergstra , Mark Brand, Syntax and semantics of a high-level intermediate representation for ASF+SDF, CWI (Centre for Mathematics and Computer Science), Amsterdam, The Netherlands, 2000
• 9: Hans-Juergen Boehm, Space efficient conservative garbage collection, ACM SIGPLAN Notices, v.28 n.6, p.197-206, June 1993 [doi>10.1145/173262.155109]
• 10: Jacob Brunekreef, A Transformation Tool for Pure Prolog Programs, Proceedings of the 6th International Workshop on Logic Programming Synthesis and Transformation, p.130-145, August 28-30, 1996
• 11: Clavel, M., Durán, F., Eker, S., Lincoln, P., Marti-Oliet, N., Meseguer, J., and Quesada, J. 1999. Maude: Specification and programming in rewriting logic---Maude system documentation. Technical report, SRI International, Menlo Park, CA.
• 12: Courcelle, B. and Franchi-Zannettacci, P. 1982. Attribute grammars and recursive program schemes I and II. Theoret. Comput. Sci. 17, 163--191 and 235--257.
• 13: Nachum Dershowitz , Jean-Pierre Jouannaud, Rewrite systems, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
• 14: M. Jonge, A pretty-printer for every occasion, CWI (Centre for Mathematics and Computer Science), Amsterdam, The Netherlands, 2001
• 15: Klaus Didrich , Andreas Fett , Carola Gerke , Wolfgang Grieskamp , Peter Pepper, OPAL: design and implementation of an algebraic programming language, Proceedings of the international conference on Programming languages and system architectures, p.228-244, April 1994, Zurich, Switzerland
• 16: Dik, C. H. S. 1989. A fast implementation of the Algebraic Specification Formalism. M.S. thesis, Programming Research Group, University of Amsterdam, Amsterdam, The Netherlands.
• 17: Dinesh, T. B., Haveraaen, M., and Heering, J. 2001. An algebraic programming style for numerical software and its optimization. Sci. Program. 8, 4 (Sept./Oct.), 247--259. Special issue on Coordinate-Free Numerics.
• 18: Field, A. J. and Harrison, P. G. 1988. Functional Programming. Addison-Wesley, Reading, MA.
• 19: Field, J. 1992. A simple rewriting semantics for realistic imperative programs and its application to program analysis. In Proc. ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation (San Francisco, CA). ACM Press, New York, NY, 98--107. Also published as Technical report YALEU/DCS/RR--909, Yale University, New Haven, CT.
• 20: Wan Fokkink , Jasper Kamperman , Pum Walters, Within ARM's reach: compilation of left-linear rewrite systems via minimal rewrite systems, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.3, p.679-706, May 1998 [doi>10.1145/291889.291903]
• 21: Franz, M. 1994. Code-generation on-the-fly: A key to portable software. Ph.D. thesis, ETH Zurich, Zurich, Switzerland. Available online at ftp://ftp.inf.ethz.ch/pub/publications/dissertations/th10497.ps.
• 22: Groote, J. F., Koorn, J. W. C., and van Vlijmen, S. F. M. 1995. The safety guaranteeing system at station Hoorn-Kersenboogaard. In Proceedings of the Tenth Annual Conference on Computer Assurance (COMPASS '95). IEEE, Computer Society Press, Los Alamitos, CA, 57--68.
• 23: Hartel, P. H. et al. 1996. Benchmarking implementations of functional languages with "Pseudoknot," a float-intensive benchmark. J. Funct. Program. 6, 621--655.
• 24: J. Heering , P. R. H. Hendriks , P. Klint , J. Rekers, The syntax definition formalism SDF—reference manual—, ACM SIGPLAN Notices, v.24 n.11, p.43-75, Nov. 1989 [doi>10.1145/71605.71607]
• 25: Hendriks, P. R. H. 1991. Implementation of modular algebraic specifications. Ph.D. thesis, University of Amsterdam, Amsterdam, The Netherlands.
• 26: Hillebrand, J. A. 1996. Experiments in specification re-engineering. Ph.D. thesis, University of Amsterdam, Amsterdam, The Netherlands.
• 27: Christoph M. Hoffmann , Michael J. O'Donnell, Pattern Matching in Trees, Journal of the ACM (JACM), v.29 n.1, p.68-95, Jan. 1982 [doi>10.1145/322290.322295]
• 28: Richard Jones , Rafael Lins, Garbage collection: algorithms for automatic dynamic memory management, John Wiley & Sons, Inc., New York, NY, 1996
• 29: Kamperman, J. F. Th. 1996. Compilation of term rewriting systems. Ph.D. thesis, University of Amsterdam, Amsterdam, The Netherlands.
• 30: S. Kaplan, A compiler for conditional term rewriting systems, on Rewriting techniques and applications, p.25-41, May 1987, Bordeaux, France
• 31: Hélène Kirchner , Pierre-Etienne Moreau, Promoting rewriting to a programming language: a compiler for non-deterministic rewrite programs in associative-commutative theories, Journal of Functional Programming, v.11 n.2, p.207-251, March 2001
• 32: P. Klint, A meta-environment for generating programming environments, ACM Transactions on Software Engineering and Methodology (TOSEM), v.2 n.2, p.176-201, April 1993 [doi>10.1145/151257.151260]
• 33: J. W. Klop, Term rewriting systems, Handbook of logic in computer science (vol. 2): background: computational structures, Oxford University Press, Inc., New York, NY, 1993
• 34: Moonen, L. 1997. A generic architecture for data flow analysis to support reverse engineering. In Proceedings of the Second International Workshop on the Theory and Practice of Algebraic Specifications (ASF+SDF '97), M. P. A. Sellink, Ed. Electronic Workshops in Computing. Springer/British Computer Society, London, UK.
• 35: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 36: Nadia Nedjah , Colin D. Walter , Stephen E. Eldridge, Optimal Left-to-Right Pattern-Matching Automata, Proceedings of the 6th International Joint Conference on Algebraic and Logic Programming, p.273-286, September 03-05, 1997
• 37: Olivier, P. A. 2002. Benchmarking of functional/algebraic language implementations. Available online at http://www.cwi.nl/∼olivierp/benchmark/.
• 38: Simon L. Peyton Jones, Compiling Haskell by Program Transformation: A Report from the Trenches, Proceedings of the 6th European Symposium on Programming Languages and Systems, p.18-44, April 22-24, 1996
• 39: Peyton Jones, S. L., Hall, C. V., Hammond, K., Partain, W. D., and Wadler, P. L. 1993. The Glasgow Haskell compiler: A technical overview. In Proceedings of Joint Framework for Information Technology Technical Conference (JFIT), Keele, England). DTI/SERC, London, U.K., 249--257.
• 40: Simon L. Peyton Jones , Thomas Nordin , Dino Oliva, C-: A Portable Assembly Language, Selected Papers from the 9th International Workshop on Implementation of Functional Languages, p.1-19, September 10-12, 1997
• 41: Plasmeijer, M. J. and van Eekelen, M. C. J. D. 1994. Concurrent CLEAN---version 1.0---Language refence manual. Technical report draft, Department of Computer Science, University of Nijmegen, Nijmegen, The Netherlands.
• 42: Eric P.B.M. Rutten , Sylvie Thiebaux, Semantics of Manifold: Specification in ASF+SDF and Extension., CWI (Centre for Mathematics and Computer Science), Amsterdam, The Netherlands, 1992
• 43: Alex Sellink , Chris Verhoef, Development, Assessment, and Reengineering of Language Descriptions, Proceedings of the Conference on Software Maintenance and Reengineering, p.151, February 29-March 03, 2000
• 44: Sjaak Smetsers , Eric Nöcker , John van Groningen , Rinu Plasmeijer, Generating efficient code for lazy functional languages, Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, p.592-617, June 1991, Cambridge, Massachusetts, United States
• 45: Motoaki Terashima , Yasumasa Kanada, HLisp—its concept, implementation and applications, Journal of Information Processing, v.13 n.3, p.265-275, 1990
• 46: F. Tip , T. B. Dinesh, A slicing-based approach for locating type errors, ACM Transactions on Software Engineering and Methodology (TOSEM), v.10 n.1, p.5-55, Jan. 2001 [doi>10.1145/366378.366379]
• 47: M. G. T. Van den Brand , H. A. de Jong , P. Klint , P. A. Olivier, Efficient annotated terms, Software—Practice & Experience, v.30 n.3, p.259-291, Mar.1.2000 [doi>10.1002/(SICI)1097-024X(200003)30:3<259::AID-SPE298>3.0.CO;2-Y]
• 48: van den Brand, M. G. J., Eijkelkamp, S. M., Geluk, D. K. A., Meijer, Osborne, H. R., and Polling, M. J. F. 1995. Program transformations using ASF+SDF. In Proceedings of ASF+SDF '95. Technical Report P9504. Programming Research Group, University of Amsterdam, Amsterdam, The Netherlands, 29--52.
• 49: Mark G. J. van den Brand , Paul Klint , Pieter A. Olivier, Compilation and Memory Management for ASF+SDF, Proceedings of the 8th International Conference on Compiler Construction, Held as Part of the European Joint Conferences on the Theory and Practice of Software, ETAPS'99, p.198-213, March 22-28, 1999
• 50: Mark G. J. van den Brand , Alex Sellink , Chris Verhoef, Generation of components for software renovation factories from context-free grammars, Science of Computer Programming, v.36 n.2-3, p.209-266, March 2000 [doi>10.1016/S0167-6423(99)00037-4]
• 51: Mark G. J. van den Brand , Arie van Deursen , Jan Heering , H. A. de Jong , Merijn de Jonge , Tobias Kuipers , Paul Klint , Leon Moonen , Pieter A. Olivier , Jeroen Scheerder , Jurgen J. Vinju , Eelco Visser , Joost Visser, The ASF+SDF Meta-environment: A Component-Based Language Development Environment, Proceedings of the 10th International Conference on Compiler Construction, p.365-370, April 02-06, 2001
• 52: van der Meulen, E. A. 1996. Incremental typechecking. In Language Prototyping: An Algebraic Specification Approach, A. van Deursen, J. Heering, and P. Klint, Eds. AMAST Series in Computing, vol. 5. World Scientific, Singapore, 199--248.
• 53: van Deursen, A. 1994. Executable language definitions: Case studies and origin tracking techniques. Ph.D. thesis, University of Amsterdam, Amsterdam, The Netherlands.
• 54: van Deursen, A., Heering, J., and Klint, P., Eds. 1996. Language Prototyping. AMAST Series in Computing, vol. 5. World Scientific, Singapore.
• 55: Arie van Deursen , Paul Klint, Little languages: little maintenance, Journal of Software Maintenance: Research and Practice, v.10 n.2, p.75-92, March-Arpil 1998 [doi>10.1002/(SICI)1096-908X(199803/04)10:2<75::AID-SMR168>3.0.CO;2-5]
• 56: Arie van Deursen , Paul Klint , Chris Verhoef, Research Issues in the Renovation of Legacy Systems, Proceedings of the Second Internationsl Conference on Fundamental Approaches to Software Engineering, p.1-21, March 22-28, 1999
• 57: Arie Van Deursen , Leon Moonen, Exploring Legacy Systems Using Types, Proceedings of the Seventh Working Conference on Reverse Engineering (WCRE'00), p.32, November 23-25, 2000
• 58: van Roy, P. 1993. The wonder years of sequential Prolog implementation. J. Logic Program. 19/20, 385--441.
• 59: Vinju, J. J. 1999. Optimizations of list matching in the ASF+SDF compiler. M.S. thesis, Programming Research Group, University of Amsterdam, Amsterdam, The Netherlands. Available online at http://www.cwi.nl/∼jurgenv/.
• 60: Visser, E. 1997. Syntax definition for language prototyping. Ph.D. thesis, University of Amsterdam, Amesterdam, The Netherlands. Available online at http://www.cs.uu. nl/∼visser/publications/ftp/Vis97.thesis.ps.gz.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory
          Subjects: Semantics

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Specialized application languages
      D.3.4 Processors
          Subjects: Code generation; Compilers; Optimization

  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.2 Grammars and Other Rewriting Systems

General Terms:
Design, Languages, Performance

Keywords:
Compilation, language definition, maximal subterm sharing, term rewriting