Abstract
Environment classifiers were proposed as a new approach to typing multi-stage languages. Safety was established in the simply-typed and let-polymorphic settings. While the motivation for classifiers was the feasibility of inference, this was in fact not established. This paper starts with the observation that inference for the full classifier-based system fails. We then identify a subset of the original system for which inference is possible. This subset, which uses implicit classifiers, retains significant expressivity (e.g. it can embed the calculi of Davies and Pfenning) and eliminates the need for classifier names in terms. Implicit classifiers were implemented in MetaOCaml, and no changes were needed to make an existing test suite acceptable by the new type checker.
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
Abadi, M., Cardelli, L., Pierce, B., Plotkin, G.: Dynamic typing in a statically typed language. ACM Transactions on Programming Languages and Systems 13(2), 237–268 (1991)
Bawden, A.: Quasiquotation in LISP. In: Danvy, O. (ed.) Proceedings of the Workshop on Partial Evaluation and Semantics-Based Program Manipulation, San Antonio, University of Aarhus, Dept. of Computer Science (1999) (invited talk)
Calcagno, C., Moggi, E., Sheard, T.: Closed types for a safe imperative MetaML. Journal of Functional Programming (2003) (to appear)
Calcagno, C., Taha, W., Huang, L., Leroy, X.: Implementing multi-stage languages using asts, gensym, and reflection. In: Pfenning, F., Smaragdakis, Y. (eds.) GPCE 2003. LNCS, vol. 2830, pp. 57–76. Springer, Heidelberg (2003)
Damas, L., Milner, R.: Principal type schemes for functional languages. In: 9th ACM Symposium on Principles of Programming Languages, August 1982. ACM, New York (1982)
Davies, R.: A temporal-logic approach to binding-time analysis. In: The Symposium on Logic in Computer Science (LICS 1996), New Brunswick, pp. 184–195. IEEE Computer Society Press, Los Alamitos (1996)
Davies, R., Pfenning, F.: A modal analysis of staged computation. In: The Symposium on Principles of Programming Languages (POPL 1996), St. Petersburg Beach, pp. 258–270 (1996)
Davies, R., Pfenning, F.: A modal analysis of staged computation. Journal of the ACM 48(3), 555–604 (2001)
Engler, D.R., Hsieh, W.C., Frans Kaashoek, M.: C: A language for high-level, efficient, and machine-independent dynaic code generation. In: Proceedings of the ACM Symposium on Principles of Programming Languages (POPL), St. Petersburg Beach, pp. 131–144 (1996)
Ganz, S., Sabry, A., Taha, W.: Macros as multi-stage computations: Type-safe, generative, binding macros in MacroML. In: The International Conference on Functional Programming (ICFP 2001), Florence, Italy, September 2001. ACM, New York (2001)
Gomard, C.K., Jones, N.D.: A partial evaluator for untyped lambda calculus. Journal of Functional Programming 1(1), 21–69 (1991)
Grant, B., Philipose, M., Mock, M., Chambers, C., Eggers, S.J.: An evaluation of staged run-time optimizations in DyC. In: Proceedings of the Conference on Programming Language Design and Implementation, pp. 293–304 (1999)
Roger Hindley, J.: Basic Simple Type Theory. Cambridge Tracts in Theoretical Computer Science, vol. 42. Cambridge University Press, Cambridge (1997)
Jim, T.: What are principal typings and what are they good for? In: Conf. Rec. POPL 1996: 23rd ACM Symp. Princ. of Prog. Langs. (1996)
Jones, N.D., Gomard, C.K., Sestoft, P.: Partial Evaluation and Automatic Program Generation. Prentice-Hall, Englewood Cliffs (1993)
Kamin, S., Callahan, M., Clausen, L.: Lightweight and generative components II: Binary-level components. In: [27], pp. 28–50 (2000)
Launchbury, J., Peyton Jones, S.L.: State in haskell. LISP and Symbolic Computation 8(4), 293–342 (1995)
Launchbury, J., Sabry, A.: Monadic state: Axiomatization and type safety. In: Proceedings of the International Conference on Functional Programming, Amsterdam (1997)
MetaOCaml: A compiled, type-safe multi-stage programming language (2001), Available online from: http://www.cs.rice.edu/taha/MetaOCaml/
The MetaML Home Page (2000), Provides source code and documentation online at: http://www.cse.ogi.edu/PacSoft/projects/metaml/index.html
Nanevski, A., Pfenning, F.: Meta-programming with names and necessity (2003) (submitted)
Nielson, F., Nielson, H.R.: Two-level semantics and code generation. Theoretical Computer Science 56(1), 59–133 (1988)
Sheard, T., Peyton-Jones, S.: Template meta-programming for haskell. In: Proc. of the workshop on Haskell, pp. 1–16. ACM, New York (2002)
Shields, M., Sheard, T., Peyton Jones, S.L.: Dynamic typing through staged type inference. In: Proceedings of the ACM Symposium on Principles of Programming Languages (POPL), pp. 289–302 (1998)
Smith, F., Grossman, D., Morrisett, G., Hornof, L., Jim, T.: Compiling for run-time code generation. Journal of Functional Programming (2003)
Taha, W.: Multi-Stage Programming: Its Theory and Applications. PhD thesis, Oregon Graduate Institute of Science and Technology (1999)
Taha, W. (ed.): SAIG 2000. LNCS, vol. 1924. Springer, Heidelberg (2000)
Taha, W.: A sound reduction semantics for untyped CBN multi-stage computation. Or, the theory of MetaML is non-trivial. In: Proceedings of the Workshop on Partial Evaluation and Semantics-Based Program Maniplation (PEPM), Boston. ACM Press, New York (2000)
Taha, W., Nielsen, M.F.: Environment classifiers. In: The Symposium on Principles of Programming Languages (POPL 2003), New Orleans (2003)
Taha, W., Sheard, T.: Multi-stage programming with explicit annotations. In: Proceedings of the Symposium on Partial Evaluation and Semantic-Based Program Manipulation (PEPM), Amsterdam, pp. 203–217. ACM Press, New York (1997)
Wells, J.B.: The essence of principal typings. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol. 2380, pp. 913–925. Springer, Heidelberg (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Calcagno, C., Moggi, E., Taha, W. (2004). ML-Like Inference for Classifiers. In: Schmidt, D. (eds) Programming Languages and Systems. ESOP 2004. Lecture Notes in Computer Science, vol 2986. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24725-8_7
Download citation
DOI: https://doi.org/10.1007/978-3-540-24725-8_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-21313-0
Online ISBN: 978-3-540-24725-8
eBook Packages: Springer Book Archive