More Web Proxy on the site http://driver.im/

article

Recursive modules for programming

Authors:

Jacques GarrigueAuthors Info & Claims

ACM SIGPLAN Notices, Volume 41, Issue 9

Pages 74 - 86

https://doi.org/10.1145/1160074.1159813

Published: 16 September 2006 Publication History

Abstract

TheML module system is useful for building large-scale programs. The programmer can factor programs into nested and parameterized modules, and can control abstraction with signatures. Yet ML prohibits recursion between modules. As a result of this constraint, the programmer may have to consolidate conceptually separate components into a single module, intruding on modular programming. Introducing recursive modules is a natural way out of this predicament. Existing proposals, however, vary in expressiveness and verbosity. In this paper, we propose a type system for recursive modules, which can infer their signatures. Opaque signatures can also be given explicitly, to provide type abstraction either inside or outside the recursion. The type system is decidable, and is sound for a call-by-value semantics. We also present a solution to the expression problem, in support of our design choices.

References

[1]

G. Boudol. The recursive record semantics of objects revisited. Journal of Functional Programming, 14:263--315, 2004.

Digital Library

[2]

W.R. Cook. Object-Oriented Programming Versus Abstract Data Types. In Proc. REX Workshop, volume 489 of Lecture Notes in Computer Science. Springer-Verlag, 1990.

Digital Library

[3]

K. Crary, R. Harper, and S. Puri. What is a recursive module? In Proc. PLDI'99, pages 50--63, 1999.

Digital Library

[4]

D. Dreyer. A type system for well-founded recursion. In Proc. POPL'04, 2004.

Digital Library

[5]

D. Dreyer. Recursive Type Generativity. In Proc. ICFP'05, 2005.

Digital Library

[6]

D. Dreyer. Understanding and Evolving the ML Module System. PhD thesis, Carnegie Mellon University, 2005.

Digital Library

[7]

J. Garrigue. Programming with polymorphic variants. In In Proc. ML workshop'98, 1998.

[8]

J. Garrigue. Private rows: abstracting the unnamed. http://www.math.nagoya-u.ac.jp/⊄garrigue/papers/privaterows. pdf, 2005.

Digital Library

[9]

R. Harper and M. Lillibridge. A type-theoretic approach to higherorder modules with sharing. In Proc. POPL'94, 1994.

Digital Library

[10]

R. Harper, J.C. Mitchell, and E. Moggi. Higher-order modules and the phase distinction. In Porc. of POPL'90, pages 341--354, 1990.

Digital Library

[11]

T. Hirschowitz and X. Leroy. Mixin modules in a call-by-value setting. In Proc. ESOP'02, pages 6--20, 2002.

Digital Library

[12]

X. Leroy. Manifest types, modules, and separate compilation. In Proc. POPL'94, pages 109--122. ACM Press, 1994.

Digital Library

[13]

X. Leroy. Applicative functors and fully transparent higher-order modules. In Proc. POPL'95, pages 142--153. ACM Press, 1995.

Digital Library

[14]

X. Leroy. A modular module system. Journal of Functional Programming, 10(3):269--303, 2000.

Digital Library

[15]

X. Leroy, D. Doligez, J. Garrigue, D. Rémy, and J. Vouillon. The Objective Caml system, release 3.09. Software and documentation available on the Web, http://caml.inria.fr/,2005.

[16]

D. MacQueen. Modules for Standard ML. In Proc. the 1984 ACM Conference on LISP and Functional Programming, pages 198--207. ACM Press, 1984.

Digital Library

[17]

R. Milner. Communicating and Mobile Systems: the pi-Calculus. Cambridge University Press, 1999.

Digital Library

[18]

R. Milner, M. Tofte, R. Harper, and D. MacQueen. The Definition of Standard ML (Revised). MIT Press, 1997.

Digital Library

[19]

K. Nakata and J. Garrigue. Path resolution for recursive modules. Technical Report 1545, Kyoto University Research Institute for Mathematical Sciences, 2006.

[20]

K. Nakata and J. Garrigue. Recursive modules for programming. Technical Report 1546, Kyoto University Research Institute for Mathematical Sciences, 2006.

Digital Library

[21]

D. Rémy and J. Garrigue. On the expression problem. http://pauillac.inria.fr/~remy/work/expr/,2004.

[22]

S. Romanenko, C. Russo, N. Kokholm, and P. Sestoft. Moscow ML, 2004. Software and documentation available on the Web, http://www.dina.dk/sestoft/mosml.html.

[23]

C. Russo. Recursive Structures for Standard ML. In Proc. ICFP'01, pages 50--61. ACM Press, 2001.

Digital Library

[24]

C. Stone. Type definitions. In Advanced Topics in Types and Programming Languages, chapter 9. The MIT Press, 2004.

[25]

M. Torgersen. The Expression Problem Revisited. In European Conference on Object-Oriented Programming:LN CS, volume 3086. Springer-Verlag, 2004.

[26]

P. Wadler. The expression problem. Java Genericity maling list, 1998. http://www.cse.ohio-state.edu/~gb/cis888. 07g/java-genericity/20.

[27]

M. Zenger and M. Odersky. Independently Extensible Solutions to the Expression Problem. In Proc. FOOL 12, 2005.

Cited By

Zhang WSun YOliveira B(2021)Compositional ProgrammingACM Transactions on Programming Languages and Systems10.1145/346022843:3(1-61)Online publication date: 3-Sep-2021
https://dl.acm.org/doi/10.1145/3460228
Rohloff JLorenzen F(2012)Call-by-Value Semantics for Mutually Recursive First-Class ModulesProceedings of the 2012 Conference on Trends in Functional Programming - Volume 782910.1007/978-3-642-40447-4_7(101-116)Online publication date: 12-Jun-2012
https://dl.acm.org/doi/10.1007/978-3-642-40447-4_7
Fan APotanin A(2022)Simple Extensible Programming through Precisely-Typed Open RecursionCompanion Proceedings of the 2022 ACM SIGPLAN International Conference on Systems, Programming, Languages, and Applications: Software for Humanity10.1145/3563768.3563951(54-56)Online publication date: 29-Nov-2022
https://dl.acm.org/doi/10.1145/3563768.3563951
Show More Cited By

Index Terms

Recursive modules for programming
1. Software and its engineering
  1. Software notations and tools
    1. Formal language definitions
    2. General programming languages
      1. Language features
        Modules / packages
        Recursion
2. Theory of computation
  1. Formal languages and automata theory

Recommendations

Recursive modules for programming
ICFP '06: Proceedings of the eleventh ACM SIGPLAN international conference on Functional programming

TheML module system is useful for building large-scale programs. The programmer can factor programs into nested and parameterized modules, and can control abstraction with signatures. Yet ML prohibits recursion between modules. As a result of this ...
Recursive type generativity
ICFP '05: Proceedings of the tenth ACM SIGPLAN international conference on Functional programming

Existential types provide a simple and elegant foundation for understanding generative abstract data types, of the kind supported by the Standard ML module system. However, in attempting to extend ML with support for recursive modules, we have found ...
Recursive type generativity
Proceedings of the tenth ACM SIGPLAN international conference on Functional programming

Existential types provide a simple and elegant foundation for understanding generative abstract data types, of the kind supported by the Standard ML module system. However, in attempting to extend ML with support for recursive modules, we have found ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 41, Issue 9

Proceedings of the 2006 ICFP conference

September 2006

296 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/1160074

Issue’s Table of Contents

ICFP '06: Proceedings of the eleventh ACM SIGPLAN international conference on Functional programming
September 2006
308 pages
ISBN:1595933093
DOI:10.1145/1159803
General Chair:
John Reppy
University of Chicago, USA
,
Program Chair:
Julia Lawall
University of Copenhagen, Denmark

Copyright © 2006 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 September 2006

Published in SIGPLAN Volume 41, Issue 9

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
311
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)0

Reflects downloads up to 31 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhang WSun YOliveira B(2021)Compositional ProgrammingACM Transactions on Programming Languages and Systems10.1145/346022843:3(1-61)Online publication date: 3-Sep-2021
https://dl.acm.org/doi/10.1145/3460228
Rohloff JLorenzen F(2012)Call-by-Value Semantics for Mutually Recursive First-Class ModulesProceedings of the 2012 Conference on Trends in Functional Programming - Volume 782910.1007/978-3-642-40447-4_7(101-116)Online publication date: 12-Jun-2012
https://dl.acm.org/doi/10.1007/978-3-642-40447-4_7
Fan APotanin A(2022)Simple Extensible Programming through Precisely-Typed Open RecursionCompanion Proceedings of the 2022 ACM SIGPLAN International Conference on Systems, Programming, Languages, and Applications: Software for Humanity10.1145/3563768.3563951(54-56)Online publication date: 29-Nov-2022
https://dl.acm.org/doi/10.1145/3563768.3563951
Rossberg ADreyer D(2013)Mixin’ Up the ML Module SystemACM Transactions on Programming Languages and Systems (TOPLAS)10.1145/2450136.245013735:1(1-84)Online publication date: 1-Apr-2013
https://dl.acm.org/doi/10.1145/2450136.2450137
Im HNakata KGarrigue JPark S(2011)A syntactic type system for recursive modulesACM SIGPLAN Notices10.1145/2076021.204814146:10(993-1012)Online publication date: 22-Oct-2011
https://dl.acm.org/doi/10.1145/2076021.2048141
Im HNakata KGarrigue JPark SLopes CFisher K(2011)A syntactic type system for recursive modulesProceedings of the 2011 ACM international conference on Object oriented programming systems languages and applications10.1145/2048066.2048141(993-1012)Online publication date: 22-Oct-2011
https://dl.acm.org/doi/10.1145/2048066.2048141
Bracha Gvon der Ahé PBykov VKashai YMaddox WMiranda E(2010)Modules as objects in newspeakProceedings of the 24th European conference on Object-oriented programming10.5555/1883978.1884007(405-428)Online publication date: 21-Jun-2010
https://dl.acm.org/doi/10.5555/1883978.1884007
Bracha Gvon der Ahé PBykov VKashai YMaddox WMiranda E(2010)Modules as Objects in NewspeakECOOP 2010 – Object-Oriented Programming10.1007/978-3-642-14107-2_20(405-428)Online publication date: 2010
https://doi.org/10.1007/978-3-642-14107-2_20
Im HPark S(2009)A module system independent of base languagesProceedings of the 1st Workshop on Modules and Libraries for Proof Assistants10.1145/1735813.1735818(24-29)Online publication date: 3-Aug-2009
https://dl.acm.org/doi/10.1145/1735813.1735818
Dreyer DRossberg AHook JThiemann P(2008)Mixin' up the ML module systemProceedings of the 13th ACM SIGPLAN international conference on Functional programming10.1145/1411204.1411248(307-320)Online publication date: 20-Sep-2008
https://dl.acm.org/doi/10.1145/1411204.1411248
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents