Transforming the .NET intermediate language using path logic programming

ABSTRACT

Path logic programming is a modest extension of Prolog for the specification of program transformations. We give an informal introduction to this extension, and we show how it can be used in coding standard compiler optimisations, and also a number of obfuscating transformations. The object language is the Microsoft .NET intermediate language (IL).

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: Tom Archer, Inside C#, Microsoft Press, Redmond, WA, 2001
• 3: Uwe Aßmann, How to Uniformly Specify Program Analysis and Transformation with Graph Rewrite Systems, Proceedings of the 6th International Conference on Compiler Construction, p.121-135, April 24-26, 1996
• 4: Bik, A. J. C., Brinkhaus, P. J., Knijnenburg, P. M. W., and Wijshoff, H. A. G. Transformation mechanisms in MT1. Technical report, Leiden Institute of Advanced Computer Science, 1998.
• 5: Borovansky, P., Kirchner, C., Kirchner, H., and Ringeissen, C. Rewriting with strategies in ELAN: a functional semantics. International Journal of Foundations of Computer Science 12, 1 (2001), 69--98. Also available as Technical Report A01-R-388, LORIA, Nancy (France).
• 6: Peter Buneman , Mary Fernandez , Dan Suciu, UnQL: a query language and algebra for semistructured data based on structural recursion, The VLDB Journal — The International Journal on Very Large Data Bases, v.9 n.1, p.76-110, March 2000 [doi>10.1007/s007780050084]
• 7: Chou, A., Chelf, B., Hallam, S., and Engler, D. Checking system rules using system-specific, programmer-written compiler extensions. In USENIX Symposium on Operating System Design and Implementation (2000).
• 8: Collberg, C., Thomborson, C., and Low, D. A taxonomy of obfuscating transformations. Tech. Rep. 148, Department of Computer Science, University of Auckland, July 1997. Available from URL: http://www.cs.auckland.ac.nz/~collberg/Research/Publications/CollbergThomborsonLow97a/index.html.
• 9: Crew, R. F. ASTLOG: a language for examining abstract syntax trees. In Proceedings of the USENIX Conference on Domain-Specific Languages (1997), C. Ramming, Ed., pp. 229--242.
• 10: Baoqiu Cui , Yifei Dong , Xiaoqun Du , K. Narayan Kumar , C. R. Ramakrishnan , I. V. Ramakrishnan , Abhik Roychoudhury , Scott A. Smolka , David Scott Warren, Logic Programming and Model Checking, Proceedings of the 10th International Symposium on Principles of Declarative Programming, p.1-20, September 16-18, 1998
• 11: Steven Dawson , C. R. Ramakrishnan , David S. Warren, Practical program analysis using general purpose logic programming systems—a case study, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.117-126, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• 12: Oege De Moor , David Lacey , Eric Van Wyk, Universal Regular Path Queries, Higher-Order and Symbolic Computation, v.16 n.1-2, p.15-35, March-June 2003 [doi>10.1023/A:1023063919574]
• 13: de Volder, K. Type-oriented logic meta-programming. PhD dissertation, Vrije Universiteit Brussels, 1998.
• 14: Dowd, T., Henderson, F., and Ross, P. Compiling Mercury to the .NET common language runtime. In BABEL '01: First International Workshop on Multi-Language Infrastructure and Interoperability (To appear, 2002), vol. 59 of Electronic Notes in Theoretical Computer Science.
• 15: ECMA. Standard ECMA-335: Common language infrastructure (CLI). Available from http://www.ecma.ch/ecma1/STAND/ecma-335.htm.
• 16: Amy Felty, A logic programming approach to implementing higher-order term rewriting, Conference Proceedings on Extensions of logic programming, p.135-161, January 1992, Stockholm, Sweden
• 17: Eric Gunnerson, A programmer's introduction to C# (2nd ed.), Apress, Berkely, CA, 2000
• 18: Kiczales, G., Lamping, J., Menhdhekar, A., Maeda, C., Lopes, C., Loingtier, J.-M., and Irwin, J. Aspect-oriented programming. In Proceedings European Conference on Object-Oriented Programming, M. Akcsit and S. Matsuoka, Eds., vol. 1241. Springer-Verlag, Berlin, Heidelberg, and New York, 1997, pp. 220--242.
• 19: David Lacey , Oege de Moor, Imperative Program Transformation by Rewriting, Proceedings of the 10th International Conference on Compiler Construction, p.52-68, April 02-06, 2001
• 20: Yanhong A. Liu , Fuxiang Yu, Solving Regular Path Queries, Proceedings of the 6th International Conference on Mathematics of Program Construction, p.195-208, July 08-10, 2002
• 21: Masuhara, H., Kiczales, G., and Dutchyn, C. Compilation semantics of aspect-oriented programs. In Proceedings of the AOSD workshop on Foundations of Aspect-oriented Languages (2002), vol. TR-02-06 of Technical report, Department of Computer Science, Iowa State University, pp. 17--25.
• 22: Meijer, E., and Gough, J. A technical overview of the commmon language infrastructure. Available from URL: http://research.microsoft.com/~emeijer/Papers/CLR.pdf.
• 23: David Melski , Thomas Reps, Interconvertibility of a class of set constraints and context-free-language reachability, Theoretical Computer Science, v.248 n.1-2, p.29-98, October 2000 [doi>10.1016/S0304-3975(00)00049-9]
• 24: Nadathur, G., and Miller, D. Higher-order logic programming. In Handbook of logics for artificial intelligence and logic programming, D. M. Gabbay, C. Hogger, and J. A. Robinson, Eds., vol. 5. Clarendon Press, 1998, pp. 499--590.
• 25: Mehmet A. Orgun , Wanli Ma, An Overview of Temporal and Modal Logic Programming, Proceedings of the First International Conference on Temporal Logic, p.445-479, July 11-14, 1994
• 26: Robert Paige, Viewing A Program Transformation System At Work, Proceedings of the 6th International Symposium on Programming Language Implementation and Logic Programming, p.5-24, September 14-16, 1994
• 27: Somogyi, Z., Henderson, F., and Conway, T. Mercury: an efficient purely declarative logic programming language. In Proceedings of the Australian Computer Science Conference (1995), pp. 499--512.
• 28: Spivey, M. Logic Programming for Programmers. Prentice Hall, 1996.
• 29: Raja Vallée-Rai , Etienne Gagnon , Laurie J. Hendren , Patrick Lam , Patrice Pominville , Vijay Sundaresan, Optimizing Java Bytecode Using the Soot Framework: Is It Feasible?, Proceedings of the 9th International Conference on Compiler Construction, p.18-34, March 25-April 02, 2000
• 30: Raja Vallée-Rai , Phong Co , Etienne Gagnon , Laurie Hendren , Patrick Lam , Vijay Sundaresan, Soot - a Java bytecode optimization framework, Proceedings of the 1999 conference of the Centre for Advanced Studies on Collaborative research, p.13, November 08-11, 1999, Mississauga, Ontario, Canada
• 31: Eelco Visser, Stratego: A Language for Program Transformation Based on Rewriting Strategies, Proceedings of the 12th International Conference on Rewriting Techniques and Applications, p.357-362, May 22-24, 2001
• 32: Deborah L. Whitfield , Mary Lou Soffa, An approach for exploring code improving transformations, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.6, p.1053-1084, Nov. 1997 [doi>10.1145/267959.267960]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Patterns

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Constraint and logic languages

General Terms:
Languages

Keywords:
compiler optimisations, logic programming, meta programming, obfuscation, program analysis, program transformation