research-article

Open access

Normalize, transpose, and distribute: An automatic approach for handling nonscalars

Authors:

Daniel E. Cooke,

J. Nelson Rushton,

Robert G. Watson,

Per AndersenAuthors Info & Claims

ACM Transactions on Programming Languages and Systems (TOPLAS), Volume 30, Issue 2

Article No.: 9, Pages 1 - 49

https://doi.org/10.1145/1330017.1330020

Published: 14 March 2008 Publication History

Abstract

SequenceL is a concise, high-level language with a simple semantics that provides for the automatic derivation of many iterative and parallel control structures. The semantics repeatedly applies a “Normalize-Transpose-Distribute” operation to functions and operators until base cases are discovered. Base cases include the grounding of variables and the application of built-in operators to operands of appropriate types. This article introduces the results of a 24-month effort to reduce the language to a very small set of primitives. Included are comparisons with other languages, the formal syntax and semantics, and the traces of several example problems run with a prototype interpreter developed in 2006.

References

[1]

Backus, J. 1978. Can programming be liberated from the von neumann style&quest; Comm. ACM 21. 8 (Aug.), 613--641.

Digital Library

[2]

Banatre, J. and Le Metayer, D. 1993. Programming by multiset transformation. Comm. ACM 36. 1, (Jan.), 98--111.

Digital Library

[3]

Bishop, J. 1990. The effect of data abstraction on loop programming techniques. IEEE Trans. Soft. Eng. 16, 4 (Apr.), 389--402.

Digital Library

[4]

Blelloch, G. 1996. Programming parallel algorithms. Comm. ACM 39, 3 (Mar.) 98--111.

Digital Library

[5]

Cohen, P. 1966. Set Theory and the Continuum Hypothesis. WH Benjamin, New York.

[6]

Cooke, D. 1996. An introduction to SEQUENCEL: A language to experiment with nonscalar constructs. Softw. Pract. Exper. 26, 11 (Nov.), 1205--1246.

Digital Library

[7]

Cooke, D. 1998. SequenceL provides a different way to view programming. Comp. Lang. 24, 1--32.

Digital Library

[8]

Cooke, D. and Andersen, P. 2000. Automatic parallel control structures in SequenceL. Softw. Prac. Expe. 30, 14 (Nov.), 1541--1570.

Digital Library

[9]

Cooke, D., Barry, M., Lowry, M., and Green, C. 2006. NASA's exploration agenda and capability engineering. Computer 39, 1 (Jan.), 63--73.

Digital Library

[10]

Cooke, D. and Gates, A. 1991. On the development of a method to synthesize programs from requirement specifications. Int. J. Softw. Eng. Knowl. Eng. 1, 1 (Mar.), 21--38.

[11]

Cooke, D., Gelfond, M., Rushton, N., and Hu, H. 2005. Application of model-based technology systems for autonomous systems. In American Institute of Aeronautics and Astronautics Infotech&commat;Aerospace Conference. AIAA Press, Reston, VA. 8 pages.

[12]

Cooke, D. and Rushton, N. 2005. Iterative and parallel algorithm design from high level language traces. Lecture Notes in Computer Science, vol. 3516. Springer-Verlag, New York. 891--894.

Digital Library

[13]

Gelfond, M. and Lifschitz, V. 1998. The stable model semantics for logic programming. In Proceedings of the 5th International Conference on Logic Programming. Seattle, WA, Aug. MIT Press, Cambridge, MA, 1070--1080.

[14]

Gelfond, M. and Lifschitz, V. 1991. Classical negation in logic programs and disjunctive databases. New Generation Comp. 9, 365--385.

[15]

Iverson, K. 1962. A Programming Language. Wiley, New York.

Digital Library

[16]

Lämmel, R. and Peyton-Jones, S. 2003. Scrap your boilerplate: A practical design patterns for generic programming. ACM SIGPLAN Notices 38, 3, 26--37.

Digital Library

[17]

Lämmel, R. and Peyton-Jones, S. 2004. Scrap more boilerplate: Reflection, zips, and generalised cates. ACM SIGPLAN Notices 39, 9, 244--255.

Digital Library

[18]

Lin, F. and Zhao, Y. 2004. Assat: Computing answer sets of a logic program by sat solvers. Artificial Intelligence 157, 1--2 (Aug.), 115--137.

Digital Library

[19]

Loidl, H. and Trinder, P. 2006. A Gentle introduction to GPH. http://www.macs.hw.ac.uk/~dsg/gph/docs/Gentle-GPH/gph-gentle-intro.html.

[20]

Meijer, E. and Fokkinga, M., and Paterson, R. 1991. Functional programming with bananas, lenses, envelopes and barbed wire. Lecture Notes in Computer Science, vol. 523. Springer-Verlag, New York. 124--144.

Digital Library

[21]

Mills, H. and Linger, R. 1986. Data structured programming: Programming without arrays and pointers. IEEE Trans. Soft. Eng. 12, 2 (Feb.), 192--197.

Digital Library

[22]

Nikhil, R. and Arvind. 2001. Implicit Parallel Programming in pH. Morgan Kaufmann, San Francisco.

Digital Library

[23]

Pancake, C. 1999. Those who live by the flop may die by the flop. Keynote Address, 41st International Cray User Group Conference, Minneapolis, MN.

[24]

Sipelstein, J. and Blelloch, G. E. 1991. Collection-oriented languages. Proc. IEEE, 79, 4.

Cited By

Başağaoğlu HBlount JBlount JNelson BSucci SWesthart PHarwell J(2017)Computational performance of SequenceL coding of the lattice Boltzmann method for multi-particle flow simulationsComputer Physics Communications10.1016/j.cpc.2016.12.012213(92-99)Online publication date: Apr-2017
https://doi.org/10.1016/j.cpc.2016.12.012
Nemanich BCooke DRushtom JPetersen LPontelli E(2010)SequenceLProceedings of the 5th ACM SIGPLAN workshop on Declarative aspects of multicore programming10.1145/1708046.1708057(45-52)Online publication date: 19-Jan-2010
https://dl.acm.org/doi/10.1145/1708046.1708057
Cooke DRushton J(2009)Taking Parnas's Principles to the Next LevelComputer10.1109/MC.2009.30142:9(56-63)Online publication date: 1-Sep-2009
https://dl.acm.org/doi/10.1109/MC.2009.301
Show More Cited By

Index Terms

Normalize, transpose, and distribute: An automatic approach for handling nonscalars
1. Computing methodologies
  1. Concurrent computing methodologies
    1. Concurrent programming languages
2. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language features
      2. Language types
        Concurrent programming languages
        Functional languages

Recommendations

Automatic parallel control structures in SequenceL
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

Information & Contributors

Information

Published In

cover image ACM Transactions on Programming Languages and Systems

ACM Transactions on Programming Languages and Systems Volume 30, Issue 2

March 2008

217 pages

ISSN:0164-0925

EISSN:1558-4593

DOI:10.1145/1330017

Issue’s Table of Contents

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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 March 2008

Accepted: 01 June 2007

Revised: 01 November 2006

Received: 01 July 2005

Published in TOPLAS Volume 30, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Abilene Community/Sheldon Fund
National Aeronautics and Space Administration

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
619
Total Downloads

Downloads (Last 12 months)91
Downloads (Last 6 weeks)9

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Başağaoğlu HBlount JBlount JNelson BSucci SWesthart PHarwell J(2017)Computational performance of SequenceL coding of the lattice Boltzmann method for multi-particle flow simulationsComputer Physics Communications10.1016/j.cpc.2016.12.012213(92-99)Online publication date: Apr-2017
https://doi.org/10.1016/j.cpc.2016.12.012
Nemanich BCooke DRushtom JPetersen LPontelli E(2010)SequenceLProceedings of the 5th ACM SIGPLAN workshop on Declarative aspects of multicore programming10.1145/1708046.1708057(45-52)Online publication date: 19-Jan-2010
https://dl.acm.org/doi/10.1145/1708046.1708057
Cooke DRushton J(2009)Taking Parnas's Principles to the Next LevelComputer10.1109/MC.2009.30142:9(56-63)Online publication date: 1-Sep-2009
https://dl.acm.org/doi/10.1109/MC.2009.301
Cooke DBarry MLowry MGreen C(2006)NASA's Exploration Agenda and Capability EngineeringComputer10.1109/MC.2006.2739:1(63-73)Online publication date: 1-Jan-2006
https://dl.acm.org/doi/10.1109/MC.2006.27

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 Article

Figures

Tables

Media

View Issue’s Table of Contents