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

Article

Free access

Semantics for communication primitives in a polymorphic language

Authors:

Kazuhiko KatoAuthors Info & Claims

POPL '93: Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages

Pages 99 - 112

https://doi.org/10.1145/158511.158529

Published: 01 March 1993 Publication History

Abstract

We propose a method to extend an ML-style polymorphic language with transparent communication primitives, and give their precise operational semantics. These primitives allow any polymorphic programs definable in ML to be used remotely in a manner completely transparent to the programmer. Furthermore, communicating programs may be based on different architecture and use different data representations.

We define a polymorphic functional calculus with transparent communication primitives, which we call dML, as an extension of Damas and Milner's proof system for ML. We then develop an algorithm to translate dML to a “core” language containing only low-level communication primitives that are readily implementable in most of distributed environments. To establish the type safety of communicating programs, we define an operational semantics of the core language and prove that the polymorphic type system of dML is sound with respect to the operational semantics of the translated terms of the core language.

References

[1]

M.P. Atldnson, P.J. Bailey, K.J. Chisholm, W.P. Cockshott, and R. Morrison. An approach to persistent programming. Computer Journal, 26(4), November 1983.

[2]

M. Abadi, L. Cardelli, B. Pierce, and G. Plotldn. Dynamic typing in a statically-typed language. A CM Transcations on Programming Languages and Systems, 13(2):237-268, 1991.

Digital Library

[3]

M. Abadi, L. Cardelli, B. Pierce, and D. R~my. Dynamic typing in polymorphie languages, in A CM SIGPLAN Workshop on ML and its Applications, 1992.

[4]

D. Berry, R. Milner, and D. Turner. A semantics for ML concurrency primitives. In Proceedings of ACM Symposium on Principles of Programming Languages, pages 119-129, 1992.

Digital Library

[5]

A.D. BirreU and B. J. Nelson. Implementing remote procedure calls. A CM Transaction on Computer Systems, 2(1):39-59, 1984.

Digital Library

[6]

P. Buneman and A. Ohori. Polymoprhism and type inference in database programming. Technical report, University of Pennsylvania, 1992. To appear in A CM Transaction on Database Systems.

Digital Library

[7]

H.E. Bal, J. G. Steiner, and A. S. Tanenbaum. Programming languages for distributed computing systems. Computing Surveys, 21(3):261- 322, 1989.

Digital Library

[8]

R. Cooper and C. Krumvioda. Distributed programming with asynchronous ordered channels in distributed ML. In Proceedings of the A CM SIGPLAN Workshop on ML and its Applications, June 1992.

[9]

L. Cardelli and P. Wegner. On understanding types, data abstraction, and polymorphism. Computing Surveys, 17(4):471-522, December 1985.

Digital Library

[10]

L. Damas and R. Milner. Principal type-schemes for functional programs. In Proceedings ofA CM Symposium on Principles of Programming Languages, pages 207-212, 1982.

Digital Library

[11]

M. Hedihy and B. Liskov. A value transmission method for abstract data types. ACM Transactions on Programming Languages and Systems, 4(4):527-551, 1982.

Digital Library

[12]

R. Hayes and R. D. Schlichting. Facilitating mixed language programming in distributed systems. IEEE Transcations on Software Engineering, SE-13(12):1254--1264, December 1987.

Digital Library

[13]

M.B. Jones and R. E Rashid. Mach and Matchmaker: kernel and language support for objectoriented distributed systems. In Proceedings of A CM OOPSLA Conference, pages 67-77, 1986.

Digital Library

[14]

K. Kato and A Ohod. An approach to multilanguage persistent type system. In Proc. Hawaii International Confernece on System Science, pages 810-819, 1992.

[15]

B. Liskov, T. Bloom, D. Gifford, R. Scheifler, and W. Weihl. Communication in the Mercury system. Programming Methodology Group Memo 59, MIT, 1987.

[16]

X. Leroy. Unboxed objects and polymorphic typing. In Proceedings of ACM Symposium on Principles of Programming Languages, pages 177-188, 1992.

Digital Library

[17]

X. Leroy and M. Mauny. Dynamics in ML. In Proceedings of the A CM Conference on Functional Programming Languages and Computer Architecture, 199 I.

Digital Library

[18]

G. Lindstrom, J. Maluszytiski, and T. Ogi. Our LISP are sealed: Interfacing functional and logic programming systems. In Proceedings of Symposium on Programming Language implementation and Logic Programming, Springer Lecture Notes in Computer Science, vol. 631., pages 428-442, 1992. August.

[19]

D. MacQueen. References and weak polymorphism. Note in Standard ML of New Jersey Distribution Package, 1988.

[20]

j.C. Mitchell and R. Harper. The essence of ML. In Proceedings of A CM Symposium on Principles of Programming Languages, pages 28-46, San Diego, California, January 1988.

Digital Library

[21]

R. Milner. A theory of type polymorphism in programming. Journal of Computer and System Sciences, 17:348-375, 1978.

[22]

J.C. Mitchell and G.D. Plotldn. Abstract types have existential type. A CM Transactions on Programming Languages and Systems, 10(3):470- 502, 1988.

Digital Library

[23]

Ro Milner, M. Tofte, and R. Harper. The Definition of StandardML. The MIT Press, 1990.

Digital Library

[24]

A Ohori. A compilation method for ML-style polymorphic record calculi, in Proceedings of A CM Symposium on Principles of Programming Languages, pages 154-165, 1992.

Digital Library

[25]

J.H. Reppy. CML: A higher-order concurrent language, in Proceedings of A CM Conference on Programming Language Design and Implementation, pages 294-305, 1991.

Digital Library

[26]

M. Tofte. Operational Semantics and Polymorphic Type Inference. PhD thesis, Department of Computer Science, University of Edinburgh, 1988.

Cited By

Greenman BDimoulas CFelleisen M(2023)Typed–Untyped Interactions: A Comparative AnalysisACM Transactions on Programming Languages and Systems10.1145/357983345:1(1-54)Online publication date: 5-Mar-2023
https://dl.acm.org/doi/10.1145/3579833
Buro SMastroeni I(2019)On the Multi-Language ConstructionProgramming Languages and Systems10.1007/978-3-030-17184-1_11(293-321)Online publication date: 6-Apr-2019
https://doi.org/10.1007/978-3-030-17184-1_11
Greenman BFelleisen M(2018)A spectrum of type soundness and performanceProceedings of the ACM on Programming Languages10.1145/32367662:ICFP(1-32)Online publication date: 30-Jul-2018
https://dl.acm.org/doi/10.1145/3236766
Show More Cited By

Index Terms

Semantics for communication primitives in a polymorphic language
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language features
        Abstract data types
        Data types and structures
      2. Language types
2. Theory of computation
  1. Semantics and reasoning
    1. Program constructs
      1. Type structures
    2. Program semantics
      1. Operational semantics

Recommendations

On polymorphic gradual typing

We study an extension of gradual typing—a method to integrate dynamic typing and static typing smoothly in a single language—to parametric polymorphism and its theoretical properties, including conservativity of typing and semantics over both statically ...
Structural semantics for polymorphic data types (preliminary report)
POPL '83: Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages

The semantic modeling of data types has been the subject of increased interest over the last few years, enhanced by the development of applicative languages such as Edinburgh's ML and HOPE, by the need for flexible highly structured languages that would ...
Polymorphic type inference and abstract data types

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

POPL '93: Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages

March 1993

510 pages

ISBN:0897915607

DOI:10.1145/158511

Chairmen:
Mary Van Deusen
IBM Watson Research Center
,
Bernard Lang
INRIA Rocquencourt

Copyright © 1993 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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 March 1993

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

POPL93

Sponsor:

POPL93: 20th ACM Symposium on Principles of Programming Languages

South Carolina, Charleston, USA

Acceptance Rates

POPL '93 Paper Acceptance Rate 39 of 199 submissions, 20%;

Overall Acceptance Rate 824 of 4,130 submissions, 20%

Upcoming Conference

POPL '25

Sponsor:
sigplan

The 52nd Annual ACM SIGPLAN Symposium on Principles of Programming Languages

January 19 - 25, 2025

Denver , CO , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

32
Total Citations
View Citations
441
Total Downloads

Downloads (Last 12 months)79
Downloads (Last 6 weeks)8

Reflects downloads up to 04 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Greenman BDimoulas CFelleisen M(2023)Typed–Untyped Interactions: A Comparative AnalysisACM Transactions on Programming Languages and Systems10.1145/357983345:1(1-54)Online publication date: 5-Mar-2023
https://dl.acm.org/doi/10.1145/3579833
Buro SMastroeni I(2019)On the Multi-Language ConstructionProgramming Languages and Systems10.1007/978-3-030-17184-1_11(293-321)Online publication date: 6-Apr-2019
https://doi.org/10.1007/978-3-030-17184-1_11
Greenman BFelleisen M(2018)A spectrum of type soundness and performanceProceedings of the ACM on Programming Languages10.1145/32367662:ICFP(1-32)Online publication date: 30-Jul-2018
https://dl.acm.org/doi/10.1145/3236766
Ueno KOhori A(2016)A Foreign Language Interface from ML to ShellNew Generation Computing10.1007/s00354-016-0303-134:3(239-256)Online publication date: 10-Aug-2016
https://doi.org/10.1007/s00354-016-0303-1
Fredriksson OGhica DWheen B(2014)Towards native higher-order remote procedure callsProceedings of the 26nd 2014 International Symposium on Implementation and Application of Functional Languages10.1145/2746325.2746332(1-12)Online publication date: 1-Oct-2014
https://dl.acm.org/doi/10.1145/2746325.2746332
Fredriksson OGhica D(2014)Krivine netsACM SIGPLAN Notices10.1145/2692915.262815249:9(349-361)Online publication date: 19-Aug-2014
https://dl.acm.org/doi/10.1145/2692915.2628152
Fredriksson OGhica DJeuring JChakravarty M(2014)Krivine netsProceedings of the 19th ACM SIGPLAN international conference on Functional programming10.1145/2628136.2628152(349-361)Online publication date: 19-Aug-2014
https://dl.acm.org/doi/10.1145/2628136.2628152
Cooper EWadler PPorto ALópez-Fraguas F(2009)The RPC calculusProceedings of the 11th ACM SIGPLAN conference on Principles and practice of declarative programming10.1145/1599410.1599439(231-242)Online publication date: 7-Sep-2009
https://dl.acm.org/doi/10.1145/1599410.1599439
Matthews JFindler R(2009)Operational semantics for multi-language programsACM Transactions on Programming Languages and Systems10.1145/1498926.149893031:3(1-44)Online publication date: 21-Apr-2009
https://dl.acm.org/doi/10.1145/1498926.1498930
Rossberg ATack GKornstaedt LRusso CDreyer D(2007)Status reportProceedings of the 2007 workshop on Workshop on ML10.1145/1292535.1292540(25-36)Online publication date: 2-Oct-2007
https://dl.acm.org/doi/10.1145/1292535.1292540
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