An assessment of multilisp: Lessons from experience | International Journal of Parallel Programming Skip to main content
Springer Nature Link
Log in

An assessment of multilisp: Lessons from experience

  • Published:
International Journal of Parallel Programming Aims and scope Submit manuscript

Abstract

Multilisp is a parallel programming language derived from the Scheme dialect of Lisp by addition of thefuture construct. It has been implemented on Concert, a 32-processor shared-memory multiprocessor. A statistics-gathering feature of Concert Multilisp producesparallelism profiles showing the number of processors busy with computing or overhead, as a function of time. Experience gained using parallelism profiles and other measurement tools on several application programs has revealed three basic ways in whichfuture generates concurrency. These ways are illustrated on two example programs: the Lisp mapping functionmapcar and the partitioning routine from Quicksort. Experience with Multilisp programming exposes issues relating to side effects, error and exception handling, low-level operations for explicit manipulation of futures and tasks, and speculative computing, which are also discussed. The basic outlines of Multilisp are now fairly clear and have stood the test of being used for several applications, but further language design work is especially needed in the areas of speculative computing and exception handling.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. H. Abelson, and G. Sussman,Structure and Interpretation of Computer Programs, M.I.T. Press, Cambridge, Mass., (1984).

    Google Scholar 

  2. J. Rees, and W. Clinger, (eds.), “Revised3 Report on the Algorithmic Language Scheme,”ACM SIGPLAN Notices 21(12): 37–79, (December 1986).

  3. T. Anderson,The Design of a Multiprocessor Development System, M.I.T. Laboratory for Computer Science Technical Report TR-279, Cambridge, Mass., (September 1982).

  4. R. Halstead, T. Anderson, R. Osborne, and T. Sterling, Concert: Design of a Multiprocessor Development System,13th Annual Symp. on Computer Architecture, Tokyo, pp. 40–48 June 1986.

  5. R. Halstead, Multilisp: A Language for Concurrent Symbolic Computation,ACM Trans. on Prog. Languages and Systems 7(4):501–538, (October 1985).

    Google Scholar 

  6. R. Osborne,Modeling the Performance of the Concert Multiprocessor, S.M. thesis, M.I.T. E.E.C.S. Dept., Cambridge, Mass., (June 1986).

    Google Scholar 

  7. R. Halstead, Concurrent Lisp Machines, to appear inSupercomputers and AI Machines, K. Hwang and D. DeGroot, (eds.), McGraw-Hill, New York, (1988).

    Google Scholar 

  8. R. Halstead, Parallel Symbolic Computing,IEEE Computer 19(8): 35–43 August 1986.

    Google Scholar 

  9. R. Halstead, Parallel Computing Using Multilisp, to appear inParallel Computation and Computers for Artificial Intelligence, J. Kowalik, (ed.), Kluwer Academic Publishers, (1987).

  10. E. Bradley,Logic Simulation on a Multiprocessor, Technical Report TR-380, M.I.T. Laboratory for Computer Science, Cambridge, Mass., (November 1986).

    Google Scholar 

  11. M. Ma,Efficient Message-Based System for Concurrent Simulation, Ph.D. thesis, M.I.T. E.E.C.S. Dept., Cambridge, Mass., (in preparation).

  12. W. Lau,Lexical Analysis of Noisy Phonetic Transcriptions, S.M. thesis, M.I.T. E.E.C.S. Dept., Cambridge, Mass., (February 1986).

    Google Scholar 

  13. H. J. Baek,Parallel Retrieval Algorithms for Semantic Nets, S.B. thesis, M.I.T. E.E.C.S. Dept., Cambridge, Mass., (June 1986).

    Google Scholar 

  14. S. Solomon,A Query Language on a Parallel Machine Operating System, S.B. thesis, M.I.T. E.E.C.S. Dept., Cambridge, Mass. (May 1985).

    Google Scholar 

  15. R. Gabriel,Performance and Evaluation of Lisp Systems, M.I.T. Press, Cambridge, Mass., (1985).

    Google Scholar 

  16. E. Krall and P. McGehearty, A Case Study of Parallel Execution of a Rule-Based Expert System,Int'l. J. of Parallel Programming 15(1): 5–32 (February 1986).

    Google Scholar 

  17. G. Steele, S. Fahlman, R. Gabriel, D. Moon, and D. Weinreb,Common Lisp Reference Manual, Digital Press, Burlington, Mass., (1984).

    Google Scholar 

  18. S. Gray,Using Futures to Exploit Parallelism in Lisp, S.M. thesis, M.I.T. E.E.C.S. Dept., Cambridge, Mass. (January 1986).

    Google Scholar 

  19. G. L. Steele and W. D. Hillis, Connection Machine Lisp: Fine-Grained Parallel Symbolic Processing,1986 ACM Conf. on Lisp and Functional Programming, Cambridge, Mass., pp. 279–297 (August 1986).

  20. Arvind and D. Culler, “Dataflow Architectures,”,Annual Reviews in Computer Science, Annual Reviews, Inc., Palo Alto, Ca., pp. 225–253 (1986).

    Google Scholar 

  21. Arvind, R. S. Nikhil, and K. K. Pingali, “I-Structures: Data Structures for Parallel Computing,”Proc. Workshop on Graph Reduction, Los Alamos, N.M. (September 1986); also Computation Structures Group Memo 269, M.I.T. Laboratory for Computer Science, Cambridge, Mass., (February 1987).

  22. R. Halstead, Architecture of a Myriaprocessor,IEEE COMPCON Spring 81, San Francisco, pp. 299–302 (February 1981).

  23. Arvind and K. Gostelow, The U-Interpreter,IEEE Computer 15(2): 42–49 (February 1982).

    Google Scholar 

  24. A. Davis and R. Keller, Data Flow Program Graphs,IEEE Computer 15(2):26–41 (February 1982).

    Google Scholar 

  25. J. B. Dennis, Data Flow Supercomputers,IEEE Computer 13(11):48–56 (November 1980).

    Google Scholar 

  26. A. Wang,Exploiting Parallelism in Lisp Programs with Side Effects, S.B. thesis, M.I.T. E.E.C.S. Dept., Cambridge, Mass., (May 1986).

    Google Scholar 

  27. R. Halstead, Architecture of a Myriaprocessor, inAdvanced Computer Concepts, (ed.) J. Solinsky, La Jolla Institute, La Jolla, California, (1981).

    Google Scholar 

  28. J. B. Goodenough, Exception Handling: Issues and a Proposed Notation,Comm. ACM 18(12): 683–696 (December 1975).

    Google Scholar 

  29. J. D. Ichbiah,et al., Preliminary ADA Reference Manual,SIGPLAN Notices 14(6) Part A, (June 1979).

  30. B. H. Liskov and A. Snyder, Exception Handling in CLU,IEEE Trans. Softw. Eng. SE-5:6: 546–558 (November 1979).

    Google Scholar 

  31. Symbolics Corp.,Symbolics Common Lisp: Language Concepts, Symbolics Corp., Cambridge, Mass., (August 1986).

    Google Scholar 

  32. R. Halstead and J. Loaiza, “Exception Handling in Multilisp,”1985 Int'l. Conf. on Parallel Processing, St. Charles, Ill., pp. 822–830 (August 1985).

  33. C. Wetherell, Error Data Values in the Data-Flow Language VAL,ACM Trans. on Prog. Languages and Systems 4(2): 226–238 (April 1983).

    Google Scholar 

  34. J. Miller, MultiScheme: A Parallel Processing System Based on MIT Scheme, Ph.D. thesis, M.I.T. E.E.C.S. Dept., Cambridge, Mass., (September 1987).

    Google Scholar 

  35. E. Shapiro, Concurrent Prolog: A Progress Report,IEEE Computer 19(8): 44–58 (August 1986).

    Google Scholar 

  36. F. W. Burton, Controlling Speculative Computation in a Parallel Functional Programming Language, Dept. of E.E. and Computer Sci., U. of Colorado, Denver, Co. (August 1984).

    Google Scholar 

  37. R. P. Gabriel and J. McCarthy, Queue-based Multi-processing Lisp,1984 ACM Symp. on Lisp and Functional Programming, Austin, Tex., pp. 25–44 (August 1984).

Download references

Author information

Authors and Affiliations

  1. Massachusetts Institute of Technology Laboratory for Computer Science, 545 Technology Square, 02139, Cambridge, Massachusetts

    Robert H. Halstead Jr.

Authors
  1. Robert H. Halstead Jr.
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

This research was supported in part by the Defense Advanced Research Projects Agency and was monitored by the Office of Naval Research under contract numbers N00014-83-K-0125 and N00014-84-K-0099.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Halstead, R.H. An assessment of multilisp: Lessons from experience. Int J Parallel Prog 15, 459–501 (1986). https://doi.org/10.1007/BF01407410

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01407410

Key Words

Search

Navigation