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

Article

Free access

Implementing RUSSELL

Authors:

Hans-Juergen Boehm,

Alan DemersAuthors Info & Claims

SIGPLAN '86: Proceedings of the 1986 SIGPLAN symposium on Compiler construction

Pages 186 - 195

https://doi.org/10.1145/12276.13330

Published: 01 July 1986 Publication History

Abstract

We have completed an implementation of the Russell programming language [Don 85]. This effort has been very helpful in the evaluation of the original language design. It has also served to pinpoint the difficulties in implementing languages with type systems as general as that of Russell.

Russell treats both functions and types as data objects which can be freely manipulated by the program. Most operators present in conventional programming languages are viewed as function calls. In spite of this, our compiler produces surprisingly efficient machine code, even with minimal effort invested in the code generator.

The generality of the language served to simplify some aspects of the compiler. We focus on the separate compilation mechanism.

The most difficult implementation problem is that of inferring typing information omitted by the programmer. We argue that this is an essential part of type checking a language such as Russell. Our current solution is only partially satisfactory.

References

[1]

Aho, Alfred V, John E. Hopcroft, Jeffrey D. UIP man, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974, p.55.

Digital Library

[2]

Backus, J., "Can Programming Be Liberated from the yon Neumann Style? A Functional Style and Its Algebra of Programs", Communications of the ACM 21, 8 (August 1978), pp. 613-641.

Digital Library

[3]

Baker, T. P., "A Single-Pass Syntax-Directed Front End for Ada", Proceedings of the SIG- PLAN '82 Symposium on Compiler Construction, SIGPLAN Notices 17, 6 (June 1982), pp, 318-326.

Digital Library

[4]

Boehm, Hans, Alan J. Demers, and James E~ Donahue, "An Informal Description of Russell", Technical Report 80-430, Department of Computer Science, Cornell University, 1980.

Digital Library

[5]

Boehm, Hans, Alan J. Demers, and James E. Donahue, "A Programmer's Introduction to Russell", Technical Report 85-16, Computer Science, Rice University, 1985.

[6]

Boehm, Hans, "Partial Polymorphic Type Inference is Undecidable", Proceedings of the 26th Annual Symposium on Foundations of Computer Science, pp. 339-345.

Digital Library

[7]

Brooks, Rodney A., Richard P. Gabriel, Guy L. Steele Jr, "An Optimizing Compiler for Lexically Scoped LISP", Proceedings of the SIG- PLAN '82 Symposium on Compiler Construction, SIGPLAN Notices 17, 6 (June 1982), pp. 261-273.

Digital Library

[8]

Cardelli, Luca, "Compiling a Functional Language", Conference Record of the 1984 Symposium on LISP and Functional Programming, pp. 208-217.

Digital Library

[9]

Demers, Alan J., and James E. Donahue, "Data Types are Values", Department of Computer Science, Comell University, Technical Report TR79-393.

[10]

Demers, Alan J., and James E. Donahue, "Data Types, Parametem, and Type Checking", Proceedings, 7th Annual ACM Symposium on PrincipLes of Programming; Languages, 1980, pp. 12 -23.

Digital Library

[11]

Demers, Alan J., and James E. Donahue, "Type-completeness as a Language Principle", Proceedings, 7th Annual ACM Symposium on Principles of Programming Languages, 1980, pp. 234-244.

Digital Library

[12]

Deutsch, Peter L., and Allan M. Schiffman, "Efficient Implementation of the Smallt, alk-80 System", Proceedings, l lth Annual ACM Symposium on Principles of Programming Languages, 1984, pp.297-302.

Digital Library

[13]

Dijkstra, Edsger W., A Discipline of Programming, Prentice Hall, Englewood Cliffs, NJ, 1976.

Digital Library

[14]

Donahue, J., and A. Demem, "Data Types are Values", ACM Transactions on Programming Lang;uuges ~nd Systems 7, :3 (July 1985), pp. 426-445.

Digital Library

[15]

Gordon, M. J., R. Milner, and C. P. Wadsworth, Lecture Note8 in Computer Science, Vol. 78: Edinburgh LCF, Springer Verlag, 1979.

[16]

Ichbiah, J. D., J. G. P. Barnes, J. C. Heliurd, B. Krieg-Brueckner, O. Roubine, and B. A. Wichmann, "Rationale for the Design of the ADA Programming Language", SIGPLAN Notices 14, 6B (June 1979). See especially chapter 13 and pages 4-17.

Digital Library

[17]

Jenks, Richard D., "A Primer: 11 Keys to the new Scratchpad", Proceeding of EUROSAM '84, Springer Lecture Notes in Computer Science # 174, pp. 12;3-147.

Digital Library

[18]

Lampson, Butler W., and Eric E. Schmidt, "Practical Use of a Polymorphic Applicative Language", Conference Record of the Tenth Annual ACM Symposium on Principles of Programming Languages, 1983, pp. 237-255.

Digital Library

[19]

Liskov, B.H., A. Snyder, R. Atkinson, and C. Schaffert, "Abstraction Mechanisms in CLU", Communications of the ACM 20, 8 (August 1977), pp. 564-576.

Digital Library

[20]

MacQueen, David, Gordon Plotkin, and Ravi Sethi, "An Ideal Model for Recursive Polymorphic types", Conference Record of the Eleventh Annual ACM Symposium On Principles of Programming Languages, 1984.

Digital Library

[21]

Matthews, D.C.J., "Poly Report", University of Cambridge Computer Laboratory, Technical Report No. 28, 1982.

[22]

Matthews, D.C.J., "Introduction to Poly", University of Cambridge Computer Laboratory, Technical Report No. 29, 1982. Both this and the preceding reference are reprinted in the April 1983 issue of the Polymorphism newsletter (edited by Cardelli and MacQueen, Bell Laboratories, Murray Hill).

[23]

Matthews, D.C.J., "Poly Manual", SIGPLAN Notices 20, 9 (Sept. 85), pp. 52-76.

Digital Library

[24]

Milner, R. "A Theory of Type Polymorphism in Prog;ramming", Journal of Computer and System Sciences 17 (1978), pp. 348-375.

[25]

Mitchell, J., W. Maybury, and R. Sweet, "Mesa Language Manual, Version 5.0", April 1979, Xerox PARC report CSL-79-3.

[26]

Stoy, Joseph E., Denotational Semantics: The Scott-Strachey approach to Programming Language Theory, MIT Press, 1977.

Digital Library

Cited By

Shao ZAppel AVan Deusen MLang B(1993)Smartest recompilationProceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages10.1145/158511.158702(439-450)Online publication date: 1-Mar-1993
https://dl.acm.org/doi/10.1145/158511.158702
Sabry AFelleisen M(1993)Reasoning about programs in continuation-passing styleLISP and Symbolic Computation10.1007/BF010194626:3-4(289-360)Online publication date: Nov-1993
https://doi.org/10.1007/BF01019462
Soliman HJohnston J(1992)Dynamic genericity in imperative languages: example in CMLProceedings ICCI `92: Fourth International Conference on Computing and Information10.1109/ICCI.1992.227696(96-99)Online publication date: 1992
https://doi.org/10.1109/ICCI.1992.227696
Show More Cited By

Index Terms

Implementing RUSSELL

Recommendations

Implementing RUSSELL

We have completed an implementation of the Russell programming language [Don 85]. This effort has been very helpful in the evaluation of the original language design. It has also served to pinpoint the difficulties in implementing languages with type ...
Implementing typed intermediate languages

Recent advances in compiler technology have demonstrated the benefits of using strongly typed intermediate languages to compile richly typed source languages (e.g., ML). A type-preserving compiler can use types to guide advanced optimizations and to ...
Implementing Domain Specific Languages with Xtext and Xtend - Second Edition

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGPLAN '86: Proceedings of the 1986 SIGPLAN symposium on Compiler construction

July 1986

275 pages

ISBN:0897911970

DOI:10.1145/12276

Editor:
Richard L Wexelblat
Philips Laboratories, Briarcliff Manor, NY

ACM SIGPLAN Notices Volume 21, Issue 7
July 1986
275 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/13310
Editor:
Richard L. Wexelblat
Philips Laboratories, Briarcliff Manor, NY
Issue’s Table of Contents

Copyright © 1986 Authors.

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1986

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SCC86

Sponsor:

SIGPLAN

SCC86: SIGPLAN Symposium on Compiler Construction

June 25 - 27, 1986

California, Palo Alto, USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

23
Total Citations
View Citations
492
Total Downloads

Downloads (Last 12 months)89
Downloads (Last 6 weeks)7

Reflects downloads up to 20 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Shao ZAppel AVan Deusen MLang B(1993)Smartest recompilationProceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages10.1145/158511.158702(439-450)Online publication date: 1-Mar-1993
https://dl.acm.org/doi/10.1145/158511.158702
Sabry AFelleisen M(1993)Reasoning about programs in continuation-passing styleLISP and Symbolic Computation10.1007/BF010194626:3-4(289-360)Online publication date: Nov-1993
https://doi.org/10.1007/BF01019462
Soliman HJohnston J(1992)Dynamic genericity in imperative languages: example in CMLProceedings ICCI `92: Fourth International Conference on Computing and Information10.1109/ICCI.1992.227696(96-99)Online publication date: 1992
https://doi.org/10.1109/ICCI.1992.227696
Sheldon MGifford DKahn G(1990)Static dependent types for first class modulesProceedings of the 1990 ACM conference on LISP and functional programming10.1145/91556.91577(20-29)Online publication date: 1-May-1990
https://dl.acm.org/doi/10.1145/91556.91577
Stansifer RFerrante JMager P(1988)Type inference with subtypesProceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages10.1145/73560.73568(88-97)Online publication date: 13-Jan-1988
https://dl.acm.org/doi/10.1145/73560.73568
MacQueen DChailloux J(1988)An implementation of standard ML modulesProceedings of the 1988 ACM conference on LISP and functional programming10.1145/62678.62704(212-223)Online publication date: 1-Jan-1988
https://dl.acm.org/doi/10.1145/62678.62704
Boehm HWeiser M(1988)Garbage collection in an uncooperative environmentSoftware—Practice & Experience10.1002/spe.438018090218:9(807-820)Online publication date: 1-Sep-1988
https://dl.acm.org/doi/10.1002/spe.4380180902
Boehm H(1987)Constructive real interpretation of numerical programsACM SIGPLAN Notices10.1145/960114.2967322:7(214-221)Online publication date: 1-Jul-1987
https://dl.acm.org/doi/10.1145/960114.29673
Boehm H(1987)Constructive real interpretation of numerical programsPapers of the Symposium on Interpreters and interpretive techniques10.1145/29650.29673(214-221)Online publication date: 1-Jul-1987
https://dl.acm.org/doi/10.1145/29650.29673
Boehm HCartwright RRiggle MO'Donnell MScherlis WWilliams JGabriel R(1986)Exact real arithmetic: a case study in higher order programmingProceedings of the 1986 ACM conference on LISP and functional programming10.1145/319838.319860(162-173)Online publication date: 8-Aug-1986
https://dl.acm.org/doi/10.1145/319838.319860
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Media

Figures

Other

Tables

View Table of Contents