Article

Free access

Binding performance at language design time

Authors:

R. PaigeAuthors Info & Claims

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

Pages 85 - 97

https://doi.org/10.1145/41625.41633

Published: 01 October 1987 Publication History

Abstract

An important research goal in software engineering and programming languages is the development of principles underlying the specification of computable problems, the translation of these problems into efficient and correct programs, and the performance analysis of these programs. This paper uncovers some of these principles, which are used to design a problem specification language L₁ restricted to problems that can be compiled automatically into programs whose worst case asymptotic time and space complexities are linear in the input/output space. Any problem expressible in L₁ can be compiled into a linear cost program. A compiler for L₁ has been implemented in the RAPTS transformational programming system.

References

[1]

Aho, A., Hopcroft, 3, and Ullman, J. Demion and AnoAileis o} Computer A~Torithra,. Addison-Wesley, 1974.]]

Digital Library

[2]

Aho, A., Sethi, R., and Ullman, J., Comln~erB. Addison-Wesley, 1986.]]

[3]

Bird, R. ~The Promotion and Accumulation Strategies in Transformational Programming". A CM TOPLA$ 6, 4 (Oct. 1984), pp. 487.504.]]

Digital Library

[4]

Birkhoff, G. Lattice Theory. American Mathematical Society, Providence, 1066.]]

[5]

Cai1 J. and Paige, R. Transformational Derivation of Constant Propagation Programs. submitted.]]

[6]

Chomsky, N. "On Certain Formal Properties of Grammars". ln/o. and Control ~ (1959), 137-167.]]

[7]

Dijkstra, E. W. A Discipline o} Programm/W. Prentice-Hall, 1976.]]

[8]

Earley, J. UHigh Level lterators and a Method for Automatically Designing Data Structure Representation". Journal of Computer Lanquages i, 4 (1976), 321.342.]]

[9]

G ratzet, G. Genera/Lattice Theol. Birkhauter, 1978.]]

[10]

Gurevlch, Y. and Shelah, S. Fixed-point Extensions of First-order Logic, 26th IEEE Syrup. on FOCS, 1985,]]

[11]

Harel, D. and Kozen, D. "A Programming Language for the Inductive Sets, and Appllcationsn. l~/ornm~on and Control B& 2 (1985), 1-27.]]

[12]

Harrison, M. Set Comparison Using Hashing Techniques. Tech. Rept. .NYO-1480.155, NYU, 1970.]]

[13]

Hopcroft, J. and Ullman, J. introdue6on to Automata Thlevlt, Laa~aa~m, and Computation. Addison-Wesley, 1979.]]

Digital Library

[14]

immerman, N. Relational queries computable in polynomial time. Proc. 14th ACM Syrup. on Theory of Computing, May, 1982.]]

Digital Library

[15]

Immermsn, N. Lsngusgel Which Capture Complexity Cluses. Proc. 15th ACM Syrup. on Theory of Computing, April, }983, pp. 347-354.]]

Digital Library

[16]

Knuth, D, "Semantics of Context-free Languages". MatAsnus6~a/ Systems Theoq~ f, 2 (1968).]]

[17]

Mehlhorn, K. Data b~ructurem and Aioorlthnu. Volume l:$ort/nf and Scarchin~. Spriuger-Verlag, 1984.]]

[18]

Paige, R. Transformational Programming -- Applications to Algorithms and Systems. Proceedings Tenth ACM Symposium on Principles of Programming Languages, Jan, 1983, pp. 73-87.]]

Digital Library

[19]

Paige, R. Applications of Finite Differencing to Database Integrity Control and Query/Transaction Optimization. In AdoanceJ In DatabaJe Theorp, Volume ~, Gailaire, H., Minker, J., and Nicolas, J.-M., Ed., Plenum Press, New York, 1984, pp. 171-210.]]

[20]

Paige, R. and Henglein, F. Mechanical Translation of Set Theoretic Problem Specifications Into Efficient RAM Code - A Case Study. EUROCAL 85, 1985, pp. 5St-SeT. Lecture Notes in Computer Science 204.]]

Digital Library

[21]

Paige, R., Tarjan, R., and Bonic, R. "A Linear Time Solution to the Single Function Coarsest Partition Problem'. TCS 40, 1 (Sep 1985), 67-84.]]

[22]

Palge, R. "Programming With lnvariants~. IEEE Software $~ 1 (Jan ; 986), 56-69.]]

[23]

Paige, R. and Schonberg, E. Efficient Set Based Progre~mming. in preparation.]]

[24]

Paige, R. and Koeni8, S. "Finite Differencing of Computable Expressions~. AGM TOPLAS 4', 3 (July 1982}, 402.454.]]

Digital Library

[25]

Papadimitriou, C. "A Note On The Expressive Power of PROLOG". Btdlflin o/EATCS ~ (1985), 21-23.]]

[26]

Reif,}.H. and Lewis,H.R. Symbolic e~ahtation and the global ~ahte graph. Harvard University, Aiken Computation Laboratory, 1982.]]

[27]

Schonberg, E., Schwartz, J. T., and Sharir, M. "An Automatic Technique for Selection of Data Representations in in SI~.TL Programs~. ACM TOPLAS $, 2 (Apr 1981), 126-143.]]

Digital Library

[28]

Schwartz, J.T. On Pro~ammin#: An Interim Report on the SETL Project, in=taUment# { and IL CIMS, New York Univ., New York, 1974.]]

[29]

Schwartz, J.T. "Automatic Data Structure Choice in a Language of Very High Level". CACM 18, 12 (Dec 1975), 722.728.]]

Digital Library

[30]

Schwartz, J. T. Correct Program Technology. Tech. l~ept. Courant Computer Science Report Num. 12, CIMS, New York University, Sep, 1977.]]

[31]

Suppes, P. Aziomatic Set Theorl/. Dover, 1972.]]

[32]

Tarjan, It. Amortized computational complexity. SIAM J. A|g. Disc, Mesh. to appear.]]

[33]

Tarski, A. ~A Lattice-Theoretical Fixpoint Theorem and its Application". Pacific Jonrn~ oJ Mathematic., 5 (1955), 285-309.]]

[34]

Tenenbaum, A. Type Determination for Verll High Lens{ Langu~ge$. Ph.D. New York University, Dept. of Computer Science. Oct 1974. appears in courant Computer Science Report 3.]]

Digital Library

[35]

Vardi, M. Complexity of Relational Query Languages. Proc. 14th ACM Symp. on Theory of Computing, May, 1982, pp. 137-146.]]

Digital Library

[36]

Willard, D. Prc&cate Oeiented Dcl~zbasc Search Al~orV.hrn~. Ph.D. Th., Harvard U., 1978.]]

[37]

Willard, D. Abstract Predicate Retrieval Theory. State University of,~ew York at Albany~ Albany, New York 12222, Aug, 1983.]]

[38]

Willard, D. Efficient Processing of Relational Calculus Expressions Using Range Query Theory. Sigmod84, 1984.]]

Digital Library

Cited By

Itzhaky SGulwani SImmerman NSagiv M(2010)A simple inductive synthesis methodology and its applicationsACM SIGPLAN Notices10.1145/1932682.186946345:10(36-46)Online publication date: 17-Oct-2010
https://dl.acm.org/doi/10.1145/1932682.1869463
Itzhaky SGulwani SImmerman NSagiv MCook WClarke SRinard MSullivan KSteinberg D(2010)A simple inductive synthesis methodology and its applicationsProceedings of the ACM international conference on Object oriented programming systems languages and applications10.1145/1869459.1869463(36-46)Online publication date: 17-Oct-2010
https://dl.acm.org/doi/10.1145/1869459.1869463
Goyal D(2008)Transformational Derivation of an Improved Alias Analysis AlgorithmAutomatic Program Development10.1007/978-1-4020-6585-9_8(49-70)Online publication date: 2008
https://doi.org/10.1007/978-1-4020-6585-9_8
Show More Cited By

Index Terms

Binding performance at language design time
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
    2. System description languages
      1. Specification languages

Recommendations

The spoofax name binding language
SPLASH '12: Proceedings of the 3rd annual conference on Systems, programming, and applications: software for humanity

In textual software languages, names are used to identify program elements such as variables, methods, and classes. Name analysis algorithms resolve names in order to establish references between definitions and uses of names. In this poster, we present ...
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 ...
Layout-sensitive language extensibility with SugarHaskell
Haskell '12

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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

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

October 1987

326 pages

ISBN:0897912152

DOI:10.1145/41625

Copyright © 1987 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

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 1987

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

POPL87

Sponsor:

SIGPLAN

POPL87: Fourteenth Annual ACM SIGACT-SIGPLAN Symposium on Prnciples of Programming Languages

January 21 - 23, 1987

Munich, West Germany

Acceptance Rates

POPL '87 Paper Acceptance Rate 29 of 108 submissions, 27%;

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

22
Total Citations
View Citations
356
Total Downloads

Downloads (Last 12 months)60
Downloads (Last 6 weeks)17

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Itzhaky SGulwani SImmerman NSagiv M(2010)A simple inductive synthesis methodology and its applicationsACM SIGPLAN Notices10.1145/1932682.186946345:10(36-46)Online publication date: 17-Oct-2010
https://dl.acm.org/doi/10.1145/1932682.1869463
Itzhaky SGulwani SImmerman NSagiv MCook WClarke SRinard MSullivan KSteinberg D(2010)A simple inductive synthesis methodology and its applicationsProceedings of the ACM international conference on Object oriented programming systems languages and applications10.1145/1869459.1869463(36-46)Online publication date: 17-Oct-2010
https://dl.acm.org/doi/10.1145/1869459.1869463
Goyal D(2008)Transformational Derivation of an Improved Alias Analysis AlgorithmAutomatic Program Development10.1007/978-1-4020-6585-9_8(49-70)Online publication date: 2008
https://doi.org/10.1007/978-1-4020-6585-9_8
Paige R(2008)A National Science Foundation ProposalAutomatic Program Development10.1007/978-1-4020-6585-9_2(7-27)Online publication date: 2008
https://doi.org/10.1007/978-1-4020-6585-9_2
Paige R(2008)Research Retrospective on Transformational Development of ProgramsAutomatic Program Development10.1007/978-1-4020-6585-9_1(3-6)Online publication date: 2008
https://doi.org/10.1007/978-1-4020-6585-9_1
Whang KBrady S(2006)High-performance expert system-DBMS interface for network management and controlIEEE Journal on Selected Areas in Communications10.1109/49.168737:3(408-417)Online publication date: 1-Sep-2006
https://dl.acm.org/doi/10.1109/49.16873
Paige R(2005)An NSF ProposalHigher-Order and Symbolic Computation10.1007/s10990-005-7009-218:1-2(211-235)Online publication date: 1-Jun-2005
https://dl.acm.org/doi/10.1007/s10990-005-7009-2
Goyal D(2005)Transformational Derivation of an Improved Alias Analysis AlgorithmHigher-Order and Symbolic Computation10.1007/s10990-005-7005-618:1-2(15-49)Online publication date: 1-Jun-2005
https://dl.acm.org/doi/10.1007/s10990-005-7005-6
Paige R(2005)Viewing a program transformation system at workProgramming Language Implementation and Logic Programming10.1007/3-540-58402-1_3(5-24)Online publication date: 28-May-2005
https://doi.org/10.1007/3-540-58402-1_3
Paige R(2005)Symbolic finite differencing - Part IESOP '9010.1007/3-540-52592-0_54(36-56)Online publication date: 1-Jun-2005
https://doi.org/10.1007/3-540-52592-0_54
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