Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

In this article, we discuss two programming language features that have value for expressibility and efficiency: nonstrictness and nondeterminism. Our work arose while assessing ways to enhance a currently successful language, SISAL [McGraw et al. 1985]. The questions of how best to include these features, if at all, has led not to conclusions but to an impetus to explore the answers in an objective way. We will retain strictness for efficiency reasons and explore the limits it may impose, and we will experiment with a carefully controlled form of nondeterminism to assess its expressive power.

REFERENCES

• 1: D. A. Abramson , G. K. Egan, An overview of the RMIT/CSIRO parallel systems architecture project, Australian Computer Journal, v.20 n.3, p.113-121, August 1988
• 2: A. P. Willem Böhm , Robert E. Hiromoto, The dataflow time and space complexity of FFTs, Journal of Parallel and Distributed Computing, v.18 n.3, p.301-313, July 1993 [doi>10.1006/jpdc.1993.1066]
• 3: A. P. Wim Böhm , J. Sargeant, Code Optimization for Tagged-Token Dataflow Machines, IEEE Transactions on Computers, v.38 n.1, p.4-14, January 1989 [doi>10.1109/12.8726]
• 4: BOHM, A P. W. CANN. D. C., FEO. J T, AND OLDEHOEFT, R.R. t991. SISAL 2 0 reference manual. Tech Rep. CS-91-118, Computer Science Dept, Colorado State Univ., Fort Colhns, Nov.
• 5: BOHM, A. P. W, GURD, J. R, AND KIRKHAM, C.C. 1987. The Manchester Dataflow Computing System. In Experimental Parallel Computing Archttectures. North-Holland, Amsterdam, 177-219.
• 6: David Cann, Retire Fortran?: a debate rekindled, Communications of the ACM, v.35 n.8, p.81-89, Aug. 1992 [doi>10.1145/135226.135231]
• 7: CANN, D. C. 1991. Vectorization of an applicative language: Current results and future directions. In Compcon 91. (Feb), 396-402.
• 8: CANN, D. C., AND OLDEHOEFT, R.R. 1989. High performance parallel applicative computing. Tech. Rep CS-89-104, Computer Science Dept., Colorado State Univ., Fort Collins, Feb.
• 9: CANN, D. C., AND OLDEHOEFT, R.R. 1988. Reference count and copy elimination for parallel applicative computing. Tech. Rep. CS-88-129, Computer Science Dept., Colorado State Univ., Fort Collins, Nov.
• 10: John T. Feo , David C. Cann , Rodney R. Oldehoeft, A report on the Sisal language project, Journal of Parallel and Distributed Computing, v.10 n.4, p.349-366, Dec. 1990 [doi>10.1016/0743-7315(90)90035-N]
• 11: Matthias Felleisen, On the expressive power of programming languages, Science of Computer Programming, v.17 n.1-3, p.35-75, Dec. 1991 [doi>10.1016/0167-6423(91)90036-W]
• 12: GAO, G. R., YATES, R. K., DENNIS, J. B., AND MULLIN, L.R. 1990. An efficient monolithic array constructor. Tech. Rep. ACAPS-TM-19, Dept. of Computer Science, McGill Univ.
• 13: HAINES, M. AND B6HM, A. P. W. 1992. Towards a distributed memory implementation of SISAL. in Proceedtngs of the Scalable High Performance Computing Conference. IEEE, New York, 385- 392.
• 14: MCGRAW, J. R., SKEDZIELEWSKI, S. K., ALLAN, S. J., OLDEHOEFT, R. R., GLAUERT, J., KIRKHAM, C., NOYCE. W., AND THOMAS, R. 1985. SISAL: Streams and iteration in a single assignment language: Reference manual version 1.2. Manual M-146, Lawrence Livermore National Laboratory, Livermore, Calif.
• 15: Rodney R. Oldehoeft , David C. Cann, Applicative Parallelism on a Shared-Memory Multiprocessor, IEEE Software, v.5 n.1, p.62-70, January 1988 [doi>10.1109/52.1995]
• 16: John Elvin Ranelletti , James Mcgraw, Graph transformation algorithms for array memory optimization in applicative languages, 1987
• 17: RICHERT, T. R. 1989. Efficient task management for SISAL. Tech. Rep. 89-111, Computer Science Dept, Colorado State Univ., Fort Collins.
• 18: Balaram Sinharoy , Bruce McKenney , Boleslaw K. Szymanski, Scheduling EPL programs for parallel processing, Languages, compilers and run-time environments for distributed memory machines, Elsevier Science Publishers B. V., Amsterdam, The Netherlands, 1992
• 19: SKEDZIELEWSKI, S. K. AND GLAUERT, J. 1985. IFl--an intermediate form for applicative lan- guages. Manual M-170, Lawrence Livermore National Laboratory, Livermore, Calif.
• 20: S. K. Skedzielewski , M. L. Welcome, Data flow graph optimization in ifi, Proc. of a conference on Functional programming languages and computer architecture, p.17-34, January 1985, Nancy, France
• 21: Peter Wegner, Concepts and paradigms of object-oriented programming, ACM SIGPLAN OOPS Messenger, v.1 n.1, p.7-87, Aug. 1990 [doi>10.1145/382192.383004]
• 22: WELCOME, M. L., SKEDZIELEWSKI~ S. K., YATES, R. K., AND RANELLETTI J.E. 1986. IF2: An applicative language intermediate form with explicit memory management. Manual M-195, Lawrence Livermore National Laboratory, Livermore, Calif.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: SISAL

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Concurrent, distributed, and parallel languages
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures

General Terms:
Design, Languages

Keywords:
SISAL, nondeterminism, nonstrictness