Parallel Concurrent ML.
John Reppy, Claudio Russo, and Yingqi Xiao.
In Proceedings of the 14th ACM SIGPLAN International Conference
on Functional Programming (ICFP 2009), September 2009.
To appear.
[ bib |
.pdf ]
Concurrent ML (CML) is a high-level message-passing language that supports the construction of first-class synchronous abstractions called events. This mechanism has proven quite effective over the years and has been incorporated in a number of other languages. While CML provides a concurrent programming model, its implementation has always been limited to uniprocessors. This limitation is exploited in the implementation of the synchronization protocol that underlies the event mechanism, but with the advent of cheap parallel processing on the desktop (and laptop), it is time for Parallel CML. Parallel implementations of CML-like primitives for Java and Haskell exist, but build on high-level synchronization constructs that are unlikely to perform well. This paper presents a novel, parallel implementation of CML that exploits a purpose-built optimistic concurrency protocol designed for both correctness and performance on shared-memory multiprocessors. This work extends and completes an earlier protocol that supported just a strict subset of CML with synchronization on input, but not output events. Our main contributions are a model-checked reference implementation of the protocol and two concrete implementations. This paper focuses on Manticore's functional, continuation-based implementation but briefly discusses an independent, thread-based implementation written in C# and running on Microsoft's stock, parallel runtime. Although very different in detail, both derive from the same design. Experimental evaluation of the Manticore implementation reveals good performance, despite the extra overhead of multiprocessor synchronization.
Regular-expression derivatives reexamined.
Scott Owens, John Reppy, and Aaron Turon.
Journal of Functional Programming, 19(2):173-190, 2009.
[ bib ]
Regular-expression derivatives are an old, but elegant, technique for compiling regular expressions to deterministic Ūnite-state machines. It easily supports extending the regular-expression operators with boolean operations, such as intersection and complement. Unfortunately, this technique has been lost in the sands of time and few computer scientists are aware of it. In this paper, we reexamine regular-expression derivatives and report on our experiences in the context of two different functional-language implementations. The basic implementation is simple and we show how to extend it to handle large character sets (e.g., Unicode). We also show that the derivatives approach leads to smaller state machines than the traditional algorithm given by McNaughton and Yamada.
Calling Variadic Functions from a Strongly-typed Language.
Matthias Blume, Mike Rainey, and John Reppy.
In Proceedings of the 2008 ACM SIGPLAN Workshop on ML, pages
47-58, September 2008.
[ bib |
.pdf ]
The importance of providing a mechanism to call C functions from high-level languages has been understood for many years and, these days, almost all statically-typed high-level-language implementations provide such a mechanism. One glaring omission, however, has been support for calling variadic C functions, such as printf. Variadic functions have been ignored because it is not obvious how to give static types to them and because it is not clear how to generate calling sequence when the arguments to the function may not be known until runtime. In this paper, we address this longstanding omission with an extension to the NLFFI foreign-interface framework used by Standard ML of New Jersey (SML/NJ) and the MLton SML compiler. We describe two different ways of typing variadic functions in NLFFI and an implementation technique based on the idea of using state machines to describe calling conventions. Our implementation is easily retargeted to new architectures and ABIs, and can also be easily added to any HOT language implementation that supports calling C functions.
Implicitly-threaded parallelism in Manticore.
Matthew Fluet, Mike Rainey, John Reppy, and Adam Shaw.
In Proceedings of the 13th ACM SIGPLAN International Conference
on Functional Programming (ICFP 2008), pages 119-130, September 2008.
[ bib |
.pdf ]
The increasing availability of commodity multicore processors is making parallel computing available to the masses. Traditional parallel languages are largely intended for large-scale scientific computing and tend not to be well-suited to programming the applications one typically finds on a desktop system. Thus we need new parallel-language designs that address a broader spectrum of applications. In this paper, we present Manticore, a language for building parallel applications on commodity multicore hardware including a diverse collection of parallel constructs for different granularities of work. We focus on the implicitly-threaded parallel constructs in our high-level functional language. We concentrate on those elements that distinguish our design from related ones, namely, a novel parallel binding form, a nondeterministic parallel case form, and exceptions in the presence of data parallelism. These features differentiate the present work from related work on functional data parallel language designs, which has focused largely on parallel problems with regular structure and the compiler transformations - most notably, flattening - that make such designs feasible. We describe our implementation strategies and present some detailed examples utilizing various mechanisms of our language.
A scheduling framework for general-purpose parallel languages.
Matthew Fluet, Mike Rainey, and John Reppy.
In Proceedings of the 13th ACM SIGPLAN International Conference
on Functional Programming (ICFP 2008), pages 241-252, September 2008.
[ bib |
.pdf ]
The trend in microprocessor design toward multicore and manycore processors means that future performance gains in software will largely come from harnessing parallelism. To realize such gains, we need languages and implementations that can enable parallelism at many different levels. For example, an application might use both explicit threads to implement course-grain parallelism for independent tasks and implicit threads for fine-grain data-parallel computation over a large array. An important aspect of this requirement is supporting a wide range of different scheduling mechanisms for parallel computation. In this paper, we describe the scheduling framework that we have designed and implemented for Manticore, a strict parallel functional language. We take a micro-kernel approach in our design: the compiler and runtime support a small collection of scheduling primitives upon which complex scheduling policies can be implemented. This framework is extremely flexible and can support a wide range of different scheduling policies. It also supports the nesting of schedulers, which is key to both supporting multiple scheduling policies in the same application and to hierarchies of speculative parallel computations. In addition to describing our framework, we also illustrate its expressiveness with several popular scheduling techniques. We present a (mostly) modular approach to extending our schedulers to support cancellation. This mechanism is essential for implementing eager and speculative parallelism. We finally evaluate our framework with a series of benchmarks and an analysis.
Toward a parallel implementation of Concurrent ML.
John Reppy and Yingqi Xiao.
In Proceedings of the Workshop on Declarative Aspects of
Multicore Programming (DAMP 2008), January 2008.
[ bib |
.pdf ]
Concurrent ML (CML) is a high-level message-passing language that supports the construction of first-class synchronous abstractions called events. This mechanism has proven quite effective over the years and has been incorporated in a number of other languages. While CML provides a concurrent programming model, its implementation has always been limited to uniprocessors. This limitation is exploited in the implementation of the synchronization protocol that underlies the event mechanism, but with the advent of cheap parallel processing on the desktop (and laptop), it is time for Parallel CML. We are pursuing such an implementation as part of the Manticore project. In this paper, we describe a parallel implementation of Asymmetric CML (ACML), which is a subset of CML that does not support output guards. We describe an optimistic concurrency protocol for implementing CML synchronization. This protocol has been implemented as part of the Manticore system.
Status Report: The Manticore Project.
Matthew Fluet, Nic Ford, Mike Rainey, John Reppy, Adam Shaw, and
Yingqi Xiao.
In Proceedings of the 2007 ACM SIGPLAN Workshop on ML, pages
15-24, October 2007.
[ bib |
.pdf ]
The Manticore project is an effort to design and implement a new functional language for parallel programming. Unlike many earlier parallel languages, Manticore is a heterogeneous language that supports parallelism at multiple levels. Specifically, we combine CML-style explicit concurrency with fine-grain, implicitly threaded, parallel constructs. We have been working on an implementation of Manticore for the past six months; this paper gives an overview of our design and a report on the status of the implementation effort.
Metaprogramming with Traits.
John Reppy and Aaron Turon.
In Proceedings of the European Conference on Object Oriented
Programming (ECOOP 2007), pages 373-398, July-August 2007.
[ bib |
.pdf ]
In many domains, classes have highly regular internal structure. For example, so-called business objects often contain boilerplate code for mapping database fields to class members. The boilerplate code must be repeated per-field for every class, because existing mechanisms for constructing classes do not provide a way to capture and reuse such member-level structure. As a result, programmers often resort to ad hoc code generation. This paper presents a lightweight mechanism for specifying and reusing member-level structure in Java programs. The proposal is based on a modest extension to traits that we have termed trait-based metaprogramming. Although the semantics of the mechanism are straightforward, its type theory is difficult to reconcile with nominal subtyping. We achieve reconciliation by introducing a hybrid structural/nominal type system that extends Java's type system. The paper includes a formal calculus defined by translation to Featherweight Generic Java.
Specialization of CML message-passing primitives.
John Reppy and Yingqi Xiao.
In Proceedings of the 34th ACM SIGPLAN-SIGACT Symposium on
Principles of Programming Languages (POPL 2007), pages 315-326, January
2007.
[ bib |
.pdf ]
Concurrent ML (CML) is a statically-typed higher-order concurrent language that is embedded in Standard ML. Its most notable feature is its support for first-class synchronous operations. This mechanism allows programmers to encapsulate complicated communication and synchronization protocols as first-class abstractions, which encourages a modular style of programming where the underlying channels used to communicate with a given thread are hidden behind data and type abstraction. While CML has been in active use for well over a decade, little attention has been paid to optimizing CML programs. In this paper, we present a new program analysis for statically-typed higher-order concurrent languages that enables the compile-time specialization of communication operations. This specialization is particularly important in a multiprocessor or multicore setting, where the synchronization overhead for general-purpose operations are high. Preliminary results from a prototype that we have built demonstrate that specialized channel operations are much faster than the general-purpose operations. Our analysis technique is modular (i.e., it analyzes and optimizes a single unit of abstraction at a time), which plays to the modular style of many CML programs. The analysis consists of three steps: the first is a type-sensitive control-flow analysis that uses the program's type-abstractions to compute more precise results. The second is the construction of an extended control-flow graph using the results of the CFA. The last step is an iterative analysis over the graph that approximates the usage patterns of known channels. Our analysis is designed to detect special patterns of use, such as one-shot channels, fan-in channels, and fan-out channels. We have proven the safety of our analysis and state those results.
Manticore: A heterogeneous parallel language.
Matthew Fluet, Mike Rainey, John Reppy, Adam Shaw, and Yingqi Xiao.
In Proceedings of the Workshop on Declarative Aspects of
Multicore Programming (DAMP 2007), pages 37-44, January 2007.
[ bib |
.pdf ]
The Manticore project is an effort to design and implement a new functional language for parallel programming. Unlike many earlier parallel languages, Manticore is a heterogeneous language that supports parallelism at multiple levels. Specifically, we combine CML-style explicit concurrency with NESL/Nepal-style data-parallelism. In this paper, we describe and motivate the design of the Manticore language. We also describe a flexible runtime model that supports multiple scheduling disciplines (e.g., for both fine-grain and course-grain parallelism) in a uniform framework. Work on a prototype implementation is ongoing and we give a status report.
Application-specific foreign-interface generation.
John Reppy and Chunyan Song.
In Proceedings of the Fifth International Conference on
Generative Programming and Component Engineering, pages 49-58, October
2006.
[ bib |
.pdf ]
A foreign interface (FI) mechanism to support interoperability with libraries written in other languages (especially C) is an important feature in most high-level language implementations. Such FI mechanisms provide a Foreign Function Interface (FFI) for the high-level language to call C functions and marshaling and unmarshaling mechanisms to support conversion between the high-level and C data representations. Often, systems provide tools to automate the generation of FIs, but these tools typically lock the user into a specific model of interoperability. It is our belief that the policy used to craft the mapping between the high-level language and C should be distinct from the underlying mechanism used to implement the mapping.In this paper, we describe a FI generation tool, called FIG (for Foreign Interface Generator) that embodies a new approach to the problem of generating foreign interfaces for high-level languages. FIG takes as input raw C header files plus a declarative script that specifies the generation of the foreign interface from the header file. The script sets the policy for the translation, which allows the user to tailor the resulting FI to his or her application. We call this approach application-specific foreign-interface generation. The scripting language uses rewriting strategies as its execution model. The other major feature of the scripting language is a novel notion of composable typemaps that describe the mapping between high-level and low-level types.
Type-sensitive control-flow analysis.
John Reppy.
In Proceedings of the 2006 ACM SIGPLAN Workshop on ML, pages
74-83, September 2006.
[ bib |
.pdf ]
Higher-order typed languages, such as ML, provide strong support for data and type abstraction. While such abstraction is often viewed as costing performance, there are situations where it may provide opportunities for more aggressive program optimization. Specifically, we can exploit the fact that type abstraction guarantees representation independence, which allows the compiler to specialize data representations. This paper describes a first step in supporting such optimizations; namely a control-flow analysis that uses the program's type information to compute more precise results. We present our algorithm as an extension of Serrano's version of 0-CFA and we show that it respects types. We also discuss applications of the analysis with examples of optimizations enabled by the analysis that would not be possible normal CFA.
A Foundation for Trait-based Metaprogramming.
John Reppy and Aaron Turon.
In 2006 International Workshop on Foundations and Developments
of Object-Oriented Languages, January 2006.
[ bib |
.pdf ]
Scharli et al. introduced traits as reusable units of behavior independent of the inheritance hierarchy. Despite their relative simplicity, traits offer a surprisingly rich calculus. Trait calculi typically include operations for resolving conflicts when composing two traits. In the existing work on traits, these operations (method exclusion and aliasing) are shallow, i.e., they have no effect on the body of the other methods in the trait. In this paper, we present a new trait system, based on the Fisher-Reppy trait calculus, that adds deep operations (method hiding and renaming) to support conflict resolution. The proposed operations are deep in the sense that they preserve any existing connections between the affected method and the other methods of the trait. Our system uses Riecke-Stone dictionaries to support these features. In addition, we define a more fine-grained mechanism for tracking trait types than in previous systems. The resulting calculus is more flexible and expressive, and can serve as the foundation for trait-based metaprogramming, an idiom we introduce. A companion technical report proves type soundness for our system; we state the key results in this paper.
The Standard ML Basis Library.
Emden R. Gansner and John H. Reppy, editors.
Cambridge University Press, 2004.
[ bib |
http ]
A Typed Calculus of Traits.
Kathleen Fisher and John Reppy.
In Proceedings of the 11th Workshop on Foundations of
Object-oriented Programming, January 2004.
[ bib |
.pdf ]
Object-oriented aspects of Moby.
Kathleen Fisher and John Reppy.
Technical Report TR-2003-10, Department of Computer Science,
University of Chicago, Chicago, IL, September 2003.
[ bib ]
Statically Typed Traits.
Kathleen Fisher and John Reppy.
Technical Report TR-2003-13, Department of Computer Science,
University of Chicago, Chicago, IL, December 2003.
[ bib ]
Optimizing Nested Loops Using Local CPS Conversion.
John Reppy.
Higher-order and Symbolic Computation, 15(2/3):161-180,
September 2002.
[ bib |
.pdf ]
Inheritance-based subtyping.
Kathleen Fisher and John Reppy.
Information and Computation, 177(1):28-55, August 2002.
[ bib |
.pdf ]
Classes play a dual role in mainstream statically-typed object-oriented languages, serving as both object generators and object types. In such languages, inheritance implies subtyping. In contrast, the theoretical language community has viewed this linkage as a mistake and has focused on subtyping relationships determined by the structure of object types, without regard to their underlying implementations. In this paper, we explore why inheritance-based subtyping relations are useful, and we describe two different approaches to extending the Moby programming language with inheritance-based subtyping relations. In addition, we present a typed object calculus that supports both structural and inheritance-based subtyping, and which provides a formal accounting of our extensions to Moby.
Compiler support for lightweight concurrency.
Kathleen Fisher and John Reppy.
Technical memorandum, Bell Labs, March 2002.
[ bib |
.pdf ]
A framework for interoperability.
Kathleen Fisher, Riccardo Pucella, and John Reppy.
In Nick Benton and Andrew Kennedy, editors, Proceedings of the
First International Workshop on Multi-Language Infrastructure and
Interoperability (BABEL'01), Volume 59 of Electronic Notes in
Theoretical Computer Science, New York, NY, September 2001. Elsevier Science
Publishers.
[ bib |
.pdf ]
Practical implementations of high-level languages must provide access to libraries and system services that have APIs specified in a low-level language (usually C). An important characteristic of such mechanisms is the foreign-interface policy that defines how to bridge the semantic gap between the high-level language and C. For example, IDL-based tools generate code to marshal data into and out of the high-level representation according to user annotations. The design space of foreign-interface policies is large and there are pros and cons to each approach. Rather than commit to a particular policy, we choose to focus on the problem of supporting a gamut of interoperability policies. In this paper, we describe a framework for language interoperability that is expressive enough to support very efficient implementations of a wide range of different foreign-interface policies. We describe two tools that implement substantially different policies on top of our framework and present benchmarks that demonstrate their efficiency.
Asynchronous exceptions in Haskell.
Simon Marlow, Simon Peyton Jones, Andrew Moran, and John Reppy.
In Proceedings of the SIGPLAN 2001 Conference on Programming
Language Design and Implementation, June 2001.
[ bib ]
Local CPS conversion in a direct-style compiler.
John Reppy.
In Proceedings of the Third ACM SIGPLAN Workshop on
Continuations (CW'01), pages 13-22, January 2001.
[ bib |
.pdf ]
Protium: An infrastructure for partitioned applications.
Cliff Young, Lakshman Y.N., Tom Szymanski, John Reppy, David
Presotto, Rob Pike, Girija Narlikar, Sape Mullender, and Eric Grosse.
In Proceedings of the Eighth Workshop on Hot Operating Systems
(HotOS-VIII), January 2001.
[ bib |
.pdf ]
Extending Moby with inheritance-based subtyping.
Kathleen Fisher and John Reppy.
In Proceedings of the European Conference on Object Oriented
Programming, Volume 1850 of Lecture Notes in Computer Science, pages
83-107, New York, NY, June 2000. Springer-Verlag.
[ bib |
.pdf ]
A Calculus for Compiling and Linking Classes.
Kathleen Fisher, John Reppy, and Jon Riecke.
In Proceedings of the European Symposium on Programming, Volume
1782 of Lecture Notes in Computer Science, pages 134-149, New York,
NY, March/April 2000. Springer-Verlag.
[ bib |
.pdf ]
Inheritance-based subtyping.
Kathleen Fisher and John Reppy.
In Proceedings of the 7th Workshop on Foundations of
Object-oriented Programming, January 2000.
[ bib |
.pdf ]
Data-level interoperability.
Kathleen Fisher, Riccardo Pucella, and John Reppy.
Technical Memorandum, Bell Labs, Lucent Technologies, April 2000.
[ bib ]
Concurrent Programming in ML.
John H. Reppy.
Cambridge University Press, Cambridge, England, 1999.
[ bib ]
The design of a class mechanism for Moby.
Kathleen Fisher and John Reppy.
In Proceedings of the SIGPLAN 1999 Conference on Programming
Language Design and Implementation, pages 37-49, New York, NY, May 1999.
ACM.
[ bib ]
Foundations for Moby classes.
Kathleen Fisher and John Reppy.
Technical Memorandum, Bell Labs, Lucent Technologies, Murray
Hill, NJ, February 1999.
[ bib ]
The Essence of Concurrent ML.
Prakash Panangaden and John Reppy.
In Flemming Nielson, editor, ML with Concurrency, Chapter 1.
Springer-Verlag, 1997.
[ bib ]
AML: Attribute Grammars in ML.
S.G. Efremidis, K.A. Mughal, L. Søraas, and John Reppy.
Nordic Journal of Computing, 4(1), 1997.
[ bib ]
Classes in Object ML via modules.
John H. Reppy and Jon G. Riecke.
In Proceedings of the Third Workshop on Foundations of
Object-oriented Programming, July 1996.
[ bib ]
Simple objects for SML.
John H. Reppy and Jon G. Riecke.
In Proceedings of the SIGPLAN 1996 Conference on Programming
Language Design and Implementation, pages 171-180, New York, NY, May 1996.
ACM.
[ bib ]
Supporting SPMD Execution for Dynamic Data Structures.
Martin Carlisle, Laurie J. Hendren, Anne Rogers, and John Reppy.
ACM Transactions on Programming Languages and Systems,
17(2):233-263, March 1995.
[ bib ]
Unrolling lists.
Zhong Shao, John Reppy, and Andrew Appel.
In ACM Conference on Lisp and Functional Programming, pages
185-195, June 1994.
[ bib ]
A portable and optimizing back end for the SML/NJ compiler.
Lal George, Florent Guillame, and John Reppy.
In Fifth International Conference on Compiler Construction,
pages 83-97, April 1994.
[ bib ]
Early experiences with Olden.
Martin Carlisle, Anne Rogers, John Reppy, and Laurie Hendren.
In 6th International Workshop on Languages and Compilers for
Parallel Computing, number 768 in Lecture Notes in Computer Science, August
1993.
[ bib ]
A Multi-threaded Higher-order User Interface Toolkit.
Emden R. Gansner and John H. Reppy.
In User Interface Software, Bass and Dewan (Eds.), Volume 1 of
Software Trends, pages 61-80. John Wiley & Sons, 1993.
[ bib ]
Concurrent ML: Design, application and semantics.
John H. Reppy.
In Peter Lauer, editor, Functional Programming, Concurrency,
Simulation and Automated Reasoning, number 693 in Lecture Notes in Computer
Science. Springer-Verlag, New York, NY, 1993.
[ bib ]
A High-performance Garbage Collector for Standard ML.
John H. Reppy.
Technical memo, AT&T Bell Laboratories, December 1993.
[ bib ]
Supporting SPMD Execution for Dynamic Data Structures.
Anne Rogers, John Reppy, and Laurie Hendren.
In 5th International Workshop on Languages and Compilers for
Parallel Computing, number 757 in Lecture Notes in Computer Science, August
1992.
[ bib ]
Abstract Value Constructors: Symbolic Constants for Standard ML.
William E. Aitken and John H. Reppy.
Technical Report TR 92-1290, Department of Computer Science, Cornell
University, June 1992.
A shorter version appears in the proceedings of the “ACM SIGPLAN
Workshop on ML and its Applications,” 1992.
[ bib |
.pdf ]
Standard ML (SML) has been used to implement a wide variety of large systems, such as compilers, theorem provers, graphics libraries, and even operating systems. While SML provides a convenient, high-level notation for programming large applications, it does have certain deficiencies. One such deficiency is the lack of a general mechanism for assigning symbolic names to constant values. In this paper, we present a simple extension of SML that corrects this deficiency in a way that fits naturally with the semantics of SML. Our proposal is a generalization of SML's datatype constructors: we introduce constants that generalize nullary datatype constructors (like nil), and templates that generalize non-nullary datatype constructors (like ::). Constants are identifiers bound to fixed values, and templates are identifiers bound to structured values with labeled holes. Templates are useful because they allow users to treat the representation of structured data abstractly without having to give up pattern matching.
Attribute grammars in ML.
S.G. Efremidis, K.A. Mughal, and John Reppy.
In ACM SIGPLAN Workshop on ML and its Aplications, June
1992.
[ bib ]
Higher-order Concurrency.
John H. Reppy.
PhD thesis, Cornell University, 1992.
Available as Computer Science Technical Report 92-1285.
[ bib ]
A Foundation for User Interface Construction.
Emden R. Gansner and John H. Reppy.
In Brad Myers, editor, Languages for Developing User
Interfaces, Chapter 14. Jones and Bartlett, 1992.
[ bib ]
CML: A higher-order concurrent language.
John H. Reppy.
In Proceedings of the SIGPLAN 1991 Conference on Programming
Language Design and Implementation, pages 293-305, New York, NY, June 1991.
ACM.
[ bib ]
eXene.
Emden R. Gansner and John H. Reppy.
In Third International Workshop on ML, September 1991.
[ bib ]
Asynchronous signals in Standard ML.
John H. Reppy.
Technical Report TR 90-1144, Department of Computer Science, Cornell
University, Ithaca, NY, August 1990.
[ bib ]
Synchronous Operations as First-class Values.
John H. Reppy.
In Proceedings of the SIGPLAN 1988 Conference on Programming
Language Design and Implementation, June 1988.
[ bib ]
Concurrent Garbage Collection on Stock Hardware.
Steven C. North and John H. Reppy.
In Third International Conference on Functional Programming
Languages and Computer Architecture, Volume 274 of Lecture Notes in
Computer Science, pages 113-133, New York, NY, September 1987.
Springer-Verlag.
[ bib ]
A foundation for programming environments.
John H. Reppy and Emden R. Gansner.
In Proceedings of the ACM SIGSOFT/SIGPLAN Software
Engineering Symposium on Practical Software Development Environments, pages
218-227, December 1986.
[ bib ]
This file was generated by bibtex2html 1.94.