Article

Free access

"Type-completeness" as a language principle

Authors:

Alan Demers,

James DonahueAuthors Info & Claims

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

Pages 234 - 244

https://doi.org/10.1145/567446.567469

Published: 28 January 1980 Publication History

PDF eReader

Abstract

In his recent Turing Lecture, John Backus delivered a trenchant argument for the proposition that "programming languages are in trouble." Backus claims this to be inevitable: the development of Algol-like languages must lead to this sorry state because it begins from faulty assumptions.A less radical interpretation of the difficulties of language design is that we still do not understand the fundamental principles that should guide our design efforts; the machines we use may limit our results, but our ignorance has far greater effect. As evidence to support this position, we can cite the difficulties of building successors to Algol 60 and Pascal. Both languages have been acclaimed as well-designed, but it has proved extremely difficult to capture just what they "got right." Thus, Hoare has claimed that "Algol 60 was not only a great improvement on its predecessors, but also on nearly all of its successors." [73a] The recent Ada design suggests that the same fate may befall Pascal.In this paper, we expand on an idea of Landin [66] to develop an important principle of programming languages: type-completeness. We argue that application of this principle is an effective tool in understanding problems of programming language design. In particular, type-completeness1. allows us to point out many of the flaws and inconsistencies in existing languages (so we can know what mistakes not to repeat) and2. provides a framework for the design of languages (or language families) that have wide variation in their changeable parts.Below, we present the principle of type-completeness and its ramifications for language design. We then discuss some common examples of incompleteness found in existing Algol-like languages. And we end by presenting the type structure of the type-complete programming language Russell, which has been designed by the authors. As we show, the flexibility provided in Russell by the combination of a small, rich type structure and type-completeness belie Backus's assertion of inherent weakness of vonNeumann languages.

References

[1]

{Backus78} Backus, J. Can Programming Be Liberated From the vonNeumann Style? A Functional Style and its Algebra of Programs. CACM 21(1978), pp. 613-641.

Digital Library

Google Scholar

[2]

{Demers79} Demers, A. and J. Donahue. Revised Report on Russell. Report TR79-389, Computer Science Department, Cornell University (1979).

Google Scholar

[3]

{Hoare73a} Hoare, C. A. R. Hints on Programming Language Design. ACM Symposium on Principles of Programming Languages (1973), pp. 1-30.

Google Scholar

[4]

{Hoare73b} Hoare, C. A. R. Recursive Data Structures. Report STAN-CS-73-400, Department of Computer Science, Stanford University (1973).

Google Scholar

[5]

{Lampson77} Lampson, Butler, James Horning, Ralph London, James Mitchell and G. Popek. Report on the Programming Language Euclid. SIGPLAN Notices 12:3 (1977).

Digital Library

Google Scholar

[6]

{Landin65} Landin, P. J. A Correspondence between Algol 60 and Church's Lambda Notation. CACM 8(1965), pp. 89-101, 158-165.

Digital Library

Google Scholar

[7]

{Landin66} Landin, P. J. The Next 700 Programming Languages. CACM 9(1966), pp. 157-164.

Digital Library

Google Scholar

[8]

{Liskov77} Liskov, B., A. Snyder, R. Atkinson and C. Schaffert. Abstraction Mechanisms in CLU. CACM 20(1977), pp. 564-576.

Digital Library

Google Scholar

[9]

{Reynolds70} Reynolds, J. GEDANKEN -- A Simple Typeless Language Based on the Principle of Completeness and the Reference Concept. CACM 13(1970), pp. 308-318.

Digital Library

Google Scholar

[10]

{vanWijngaarden77} vanWijngaarden, A., et al. Revised Report on the Algorithmic Language Algol68. SIGPLAN Notices 12:5(1977), pp. 1-70.

Google Scholar

[11]

{Wulf78} Wulf, W., et al. (Preliminary) An Informal Definition of Alphard, CMU-CS-78-105, Department of Computer Science, Carnegie-Mellon University, 1978.

Google Scholar

Cited By

View all

Zamulin AKositov VKucherov GPak ERyshkov V(2005)The database programming language Atlant: Principal features and implementation techniquesNext Generation Information System Technology10.1007/3-540-54141-1_21(385-402)Online publication date: 8-Jun-2005
https://doi.org/10.1007/3-540-54141-1_21
Agnarsson SKrishnamoorthy MSaunders B(2005)An algebraic implementation of packagesEUROCAL '8510.1007/3-540-15984-3_280(291-302)Online publication date: 8-Jun-2005
https://doi.org/10.1007/3-540-15984-3_280
Boehm HDemers A(1986)Implementing RUSSELLACM SIGPLAN Notices10.1145/13310.1333021:7(186-195)Online publication date: 1-Jul-1986
https://dl.acm.org/doi/10.1145/13310.13330
Show More Cited By

"Type-completeness" as a language principle
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages

Recommendations

GEDANKEN—a simple typeless language based on the principle of completeness and the reference concept

GEDANKEN is an experimental programming language with the following characteristics. (1) Any value which is permitted in some context of the language is permissible in any other meaningful context. In particular, functions and labels are permissible ...
Layout-sensitive language extensibility with SugarHaskell
Haskell '12: Proceedings of the 2012 Haskell Symposium

Programmers need convenient syntax to write elegant and concise programs. Consequently, the Haskell standard provides syntactic sugar for some scenarios (e.g., do notation for monadic code), authors of Haskell compilers provide syntactic sugar for more ...
Type-directed language extension for effectful computations
SCALA '14: Proceedings of the Fifth Annual Scala Workshop

Computation types such as functors, applicative functors and monads have become common abstractions for modeling effectful computations in functional programming languages. They are often used together with special language extensions intended to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

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

January 1980

261 pages

ISBN:0897910117

DOI:10.1145/567446

Conference Chairs:
Paul Abrahams
Courant Institute, New York, NY
,
Richard Lipton
University of California at Berkeley, Berkeley, CA
,
Program Chair:
Stephen Bourne
Bell Laboratories, Murray Hill, NJ

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: 28 January 1980

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

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

11
Total Citations
View Citations
561
Total Downloads

Downloads (Last 12 months)59
Downloads (Last 6 weeks)10

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Zamulin AKositov VKucherov GPak ERyshkov V(2005)The database programming language Atlant: Principal features and implementation techniquesNext Generation Information System Technology10.1007/3-540-54141-1_21(385-402)Online publication date: 8-Jun-2005
https://doi.org/10.1007/3-540-54141-1_21
Agnarsson SKrishnamoorthy MSaunders B(2005)An algebraic implementation of packagesEUROCAL '8510.1007/3-540-15984-3_280(291-302)Online publication date: 8-Jun-2005
https://doi.org/10.1007/3-540-15984-3_280
Boehm HDemers A(1986)Implementing RUSSELLACM SIGPLAN Notices10.1145/13310.1333021:7(186-195)Online publication date: 1-Jul-1986
https://dl.acm.org/doi/10.1145/13310.13330
Boehm HDemers A(1986)Implementing RUSSELLProceedings of the 1986 SIGPLAN symposium on Compiler construction10.1145/12276.13330(186-195)Online publication date: 1-Jul-1986
https://dl.acm.org/doi/10.1145/12276.13330
Agnarsson SKrishnamoorthy MPayton TDeutsch L(1985)Towards a theory of packagesProceedings of the ACM SIGPLAN 85 symposium on Language issues in programming environments10.1145/800225.806833(117-130)Online publication date: 25-Jun-1985
https://dl.acm.org/doi/10.1145/800225.806833
Donahue JDemers A(1985)Data types are valuesACM Transactions on Programming Languages and Systems10.1145/3916.39877:3(426-445)Online publication date: 1-Jul-1985
https://dl.acm.org/doi/10.1145/3916.3987
Mitchell JPlotkin GVan Deusen MGalil ZReid B(1985)Abstract types have existential typesProceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages10.1145/318593.318606(37-51)Online publication date: 1-Jan-1985
https://dl.acm.org/doi/10.1145/318593.318606
Agnarsson SKrishnamoorthy M(1985)Towards a theory of packagesACM SIGPLAN Notices10.1145/17919.80683320:7(117-130)Online publication date: 25-Jun-1985
https://dl.acm.org/doi/10.1145/17919.806833
Wegner PWhite JLandweber LDemers ATeitelbaum T(1983)On the unification of data and program abstraction in AdaProceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages10.1145/567067.567091(256-264)Online publication date: 24-Jan-1983
https://dl.acm.org/doi/10.1145/567067.567091
Demers ADonahue JWhite JLandweber LDemers ATeitelbaum T(1983)Making variables abstractProceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages10.1145/567067.567075(59-72)Online publication date: 24-Jan-1983
https://dl.acm.org/doi/10.1145/567067.567075
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Cited By

Recommendations

GEDANKEN—a simple typeless language based on the principle of completeness and the reference concept

Layout-sensitive language extensibility with SugarHaskell

Type-directed language extension for effectful computations