Skip to main content Accessibility help

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.

Close cookie message
×
Hostname: page-component-66644f4456-vbzrr Total loading time: 0 Render date: 2025-02-13T03:04:02.263Z Has data issue: true hasContentIssue false

5 - Kahn networks at the dawn of functional programming

Published online by Cambridge University Press:  06 August 2010

By
David B. MacQueen
Edited by
Yves Bertot ,
Gérard Huet ,
Jean-Jacques Lévy  and
Gordon Plotkin
David B. MacQueen
Affiliation:
University of Chicago
Yves Bertot
Affiliation:
INRIA-Sophia Antipolis, France
Gérard Huet
Affiliation:
Institut National de Recherche en Informatique et en Automatique (INRIA), Rocquencourt
Jean-Jacques Lévy
Affiliation:
Institut National de Recherche en Informatique et en Automatique (INRIA), Rocquencourt
Gordon Plotkin
Affiliation:
University of Edinburgh
Get access

Summary

Introduction

The evolution of programming languages involves isolating and describing abstractions that allow us to solve problems more elegantly, efficiently, and reliably, and then providing appropriate linguistic support for these abstractions. Ideally, a new abstraction can be described precisely with a mathematical semantics, and the semantics leads to logical techniques for reasoning about programs that use the abstraction. Gilles Kahn's early work on stream processing networks is a beautiful example of this process at work.

Gilles began thinking about parallel graph programs at Stanford, and he developed his ideas in a series of papers starting in 1971: and. Gilles' original motivation was to provide a formal model for reasoning about aspects of operating systems programming, based on early data flow models of computation. But the model he developed turned out to be of much more general interest, both in terms of program architecture and in terms of semantics. During his Edinburgh visit in 1975–76, Gilles and I collaborated on a prototype implementation of the model that allowed further development and experimentation, reported in. By 1976 it was clear that his model, while inspired by early data flow research, was also closely connected to several other developments, including coroutines, Landin's notion of streams, and the then emerging lazy functional languages.

Type
Chapter
Information
From Semantics to Computer Science
Essays in Honour of Gilles Kahn
 , pp. 95 - 138
Publisher: Cambridge University Press
Print publication year: 2009

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]H., Abelson, G. J., Sussman, and J., Sussman. Structure and Interpretation of Computer Programs. McGraw-Hill, New York, 1985.Google Scholar
[2]S., Abramsky. A generalized Kahn principle for abstract asynchronous networks. In Mathematical Foundations of Programming Semantics, 5th International Conference, pp. 1–21. Springer-Verlag, 1989.Google Scholar
[3]D. A., Adams. A Computation Model with Data Flow Sequencing. PhD thesis, Computer Science Dept, Stanford University, December 1968. Technical Report CS-117.
[4]A., Appel and D. B., MacQueen. Standard ml of new jersey. In J., Maluszynski and M., Wirsing (eds) Programming Language Implementation and Logic Programming, Proceedings of the 3rd International Symposium, volume 528 Lecture Notes in Computer Science, pp. 1–13. Springer Verlag, 1991.Google Scholar
[5]A. E., Ashcroft. Program proving without tears. In G., Huet and G., Kahn (eds) Symposium on Proving and Improving Programs, pp. 99–111. INRIA Rocquencourt, July 1975.Google Scholar
[6]A. E., Ashcroft and W. W., Wadge. Lucid – a formal system for writing and proving programs. SIAM J. Comput., 5:519–526, 1976.Google Scholar
[7]A. E., Ashcroft and W. W., Wadge. Lucid: Scope Structures and Defined Functions. Technical Report Rep. CS-76-22, Computer Science Dept., University of Waterloo, 1976.Google Scholar
[8]A. E., Ashcroft and W. W., Wadge. Lucid, a nonprocedural language with iteration. Commun. ACM, 20(7):519–526, 1977.Google Scholar
[9]A. E., Ashcroft and W. W., Wadge. Structured Lucid. Technical Report CS-79-21, Computer Science Department, University of Waterloo, 1979.Google Scholar
[10]A. E., Ashcroft and W. W., Wadge. Lucid, the Dataflow Programming Language. Number 22 in APIC Studies in Data Processing. Academic Press, 1985.Google Scholar
[11]J. L., Baer. A survey of some theoretical aspects of multiprocessing. ACM Comput. Surv., 5(1):31–80, 1973.Google Scholar
[12]G., Berry and P.-L., Currien. Sequential algorithms on concrete data structures. Theoret. Comput. Sci., 20:265–322, 1982.Google Scholar
[13]G., Berry and P.-L., Currien. The kernel of the applicative language cds: theory and practice. In Proc. French-US Seminar on the Applications of Algebra to Language Definition and Compilation, pp. 35–87. Cambridge University Press, 1985.Google Scholar
[14]S., Brookes and S., Geva. Continuous functions and parallel algorithms on concrete data structures. In Proc. 7th International Conf. on Mathematical Foundations of Programming Semantics, volume 598 in Lecture Notes in Computer Science, 1991.Google Scholar
[15]S., Brookes. Historical introduction to “concrete domains” by G. Kahn and G. D. Plotkin. Theoret. Comput. Sci., 121(1–2):179–186, 1993.Google Scholar
[16]W. H., Burge. Recursive Programming Techniques. Addison Wesley, 1975.Google Scholar
[17]W. H., Burge. Stream processing functions. IBM J. Res. Develop., pp. 12–25, 1975.Google Scholar
[18]R. M., Burstall. Design considerations for a functional programming language. In Infotech State of the Art Conference: The Software Revolution, Copenhagen, October 1977.Google Scholar
[19]R. M., Burstall, J. S., Collins, and R. J., Popplestone. Programming in POP-2. Edinburgh University Press, 1977.Google Scholar
[20]R. M., Burstall and J., Darlington. A tranformation system for developing recursive programs. J. ACM, 24(1), 1977.Google Scholar
[21]R. M., Burstall, D. B., MacQueen, and D., Sannella. Hope: An experimental applicative language. In Conference Record of the 1980 Lisp Conference, pp. 136–143, August 1980. Stanford.Google Scholar
[22]P., Caspi, D., Pilaud, N., Halbwachs and J. A., Plaice. LUSTRE: a declarative language for real-time programming. In POPL '87: Proceedings of the 14th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, pp. 178–188, New York, NY, USA, 1987. ACM Press.Google Scholar
[23]P., Caspi and M., Pouzet. Synchronous Kahn networks. In ICFP '96: Proceedings of the first ACM SIGPLAN International Conference on Functional Programming, pp. 226–238, New York, NY, USA, 1996. ACM Press.Google Scholar
[24]A., Cohen, M., Duranton, C., Eisenbeis, C., Pagetti, F., Plateau and M., Pouzet. N-synchronous Kahn networks: a relaxed model of synchrony for real-time systems. In POPL '06: Conference Record of the 33rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pp. 180–193, New York, NY, USA, 2006. ACM Press.Google Scholar
[25]M. E., Conway. Design of a separable transition-diagram compiler. Commun. ACM, 6(7):396–408, 1963.Google Scholar
[26]B., Courcelle, G., Kahn and J., Vuillemin. Algorithmes d'equivalence et de reduction a des expressions minimales dans une classe d'equations recursives simples. In Proceedings of the 2nd Colloquium on Automata, Languages and Programming, pp. 200–213, London, UK. Springer-Verlag, 1974.Google Scholar
[27]J., Darlington and M., Reeve. Alice a multi-processor reduction machine for the parallel evaluation cf applicative languages. In FPCA '81: Proceedings of the 1981 Conference on Functional Programming Languages and Computer Architecture, pp. 65–76, New York, NY, USA, 1981. ACM Press.Google Scholar
[28]J., Davies. POP-10 User's Manual. Technical Report CS R25, University of Western Ontario Computer Science Dept., 1976.Google Scholar
[29]J. B., Dennis. Programming generality, parallelism, and computer architecture. In Information Processing 68, pp. 484–492. North Holland, 1969.Google Scholar
[30]J. B., Dennis. First version of a data flow procedure language. In Programming Symposium, Proceedings Colloque sur la Programmation, volume 19 of Lecture Notes in Computer Science, pp. 362–376, Springer-Verlag, 1974.Google Scholar
[31]J. B., Dennis, J. B., Fosseen and J. P., Linderman. Data flow schemas. In G., Goos and J., Hartmanis (eds), International Symposium on Theoretical Programming, volume 5, Lecture Notes in Computer Science, pp. 187–216, Springer-Verlag, 1974.Google Scholar
[32]J. B., Dennis. A language design for structured concurrency. In J. H., Williams and D. A., Fisher (eds), Proceedings of the DoD Sponsored Workshop on Design and Implementation of Programming Languages, volume 54, Lecture Notes in Computer Science, pp. 231–242. Springer-Verlag, 1977.Google Scholar
[33]J. B., Dennis. Stream Data Types for Signal Processing. Computation Structures Group Memo 36, MIT LCS, October 1994.Google Scholar
[34]J. B., Dennis and D. P., Misunas. A preliminary architecture for a basic data-flow processor. In ISCA '75: Proceedings of the 2nd Annual Symposium on Computer Architecture, pp. 126–132, New York, NY, USA, 1975. ACM Press.Google Scholar
[35]D. P., Friedman and D. S., Wise. Cons should not evaluate its arguments. In S., Michaelson and R., Milner (eds), Automata, Languages and Programming, pp. 257–284. Edinburgh University Press, 1976.Google Scholar
[36]M. J. C., Gordon, A. J. R. G., Milner, L., Morris, M. C., Newey and C. P., Wadsworth. A metalanguage for interactive proof in LCF. In Fifth ACM Symposium on Principles of Programming Languages, New York, 1978. ACM Press.Google Scholar
[37]J. R., Gurd, C. C., Kirkham and I., Watson. The Manchester prototype dataflow computer. Commun. ACM, 28(1):34–52, 1985.Google Scholar
[38]N., Halbwachs, P., Caspi, P., Raymond and D., Pilaud. The synchronous dataflow programming language LUSTRE. Proceedings of the IEEE, 79(9):1305–1320, Sept. 1991.Google Scholar
[39]E., Harold. Java I/O, 2nd Edition. O'Reilly Media, 2006.Google Scholar
[40]P., Henderson and J. H., Morris. A lazy evaluator. In Third ACM Symposium on Principles of Programming Languages, pp. 123–42, New York, 1976. ACM Press.Google Scholar
[41]C., Hewitt, P., Bishop, R., Steiger, I., Greif, B., Smith, T., Matson and R., Hale. Behavioral semantics of nonrecursive control structures. In Programming Symposium, Proceedings Colloque sur la Programmation, volume 19, Lecture Notes in Computer Science, pp. 385–407. Springer-Verlag, 1974.Google Scholar
[42]G., Kahn and G. D., Plotkin. Domaines concrets. INRIA Rapport 336, INRIA, 1978.Google Scholar
[43]G., Kahn and G. D., Plotkin. Concrete domains. Theoret. Comput. Sci., 121(1–2):187–277, 1993.Google Scholar
[44]G., Kahn. An approach to systems correctness. In SOSP '71: Proceedings of the Third ACM Symposium on Operating Systems Principles, pp. 86–94, New York, NY, USA, 1971. ACM Press.Google Scholar
[45]G., Kahn. A Preliminary Theory for Parallel Programs. Technical Report Rapport Laboria no. 6, IRIA Rocquencourt, January 1973.Google Scholar
[46]G., Kahn. The semantics of a simple language for parallel programming. In Information Processing 74, Proceedings of the IFIP Congress 74, pp. 471–475. ElsevierNorth Holland, 1974.Google Scholar
[47]G., Kahn and D. B., MacQueen. Coroutines and networks of parallel processes. In B., Gilchrist (ed.), Information Processing 77, pp. 993–998. North Holland, 1977.Google Scholar
[48]G., Kahn and G., Plotkin. Concrete Data-types. first draft manuscript, December 1975.Google Scholar
[49]R. M., Karp and R. E., Miller. Properties of a model for parallel computations: Determinacy, termination, queueing. SIAM J. Appl. Maths, 14(6):1390–1411, 1966.Google Scholar
[50]J., Kelly, C., Lochbaum and V., Vyssotsky. A block diagram compiler. Bell System Tech. J., 40(3):669–676, May 1961.Google Scholar
[51]S., Kleene. Introduction to Metamathematics. Van Nostrand, 1952.Google Scholar
[52]G., Kopec. A high-level block-diagram signal processing language. In IEEE International Conference on Acoustics, Speech, and Signal Processing, pp. 684–687, 1979.Google Scholar
[53]P. J., Landin. A correspondence between ALGOL 60 and Church's lambda-notation: Part I. Commun. ACM, 8(2):89–101, 1965.Google Scholar
[54]D. C., Luckham, D. M. R., Park and M. S., Paterson. On formalized computer programs. J. System Sci., 4(3):220–249, 1970.Google Scholar
[55]D. B., MacQueen, P., Wadler and W., Taha. How to add laziness to a strict language without even being odd. In Proceedings of the 1998 ACM Workshop on ML, pp. 24–30, September 1998. Baltimore, MD.Google Scholar
[56]J., McCarthy, P. W., Abrahams, D. J., Edwards, T. P., Hart and M. E., Levin. LISP 1.5 Programmer's Manual. MIT Press, 1962.Google Scholar
[57]J., McCarthy. Towards a mathematical science of computation. In Proceedings of the IFIP Congress 1962, pp. 21–28. North-Holland, 1962.Google Scholar
[58]J., McCarthy. A basis of a mathematical theory of computation. In P., Braffort and D., Hirshberg (eds), Computer Programming and Formal Systems, pp. 33–70. North-Holland, 1963.Google Scholar
[59]M. D., McIlroy. Coroutines. unpublished note, May 1968.
[60]M. D., McIlroy. Squinting at power series. Software Pract. Exper., 20:661–683, 1990.Google Scholar
[61]M. D., McIlroy. Power Series as Lazy Streams. Technical Report BL011276-970313-02TMS, Bell Laboratories, Lucent Technologies, 1997.Google Scholar
[62]M. D., McIlroy. Power series, power serious. J. Funct. Program., 9(3):325–337, May 1999.Google Scholar
[63]R., Milner. Implementation and applications of Scott's logic for computable functions. In Proceedings of ACM Conference on Proving Assertions About Programs, pp. 1–6, New York, NY, USA, 1972. ACM.Google Scholar
[64]R., Milner. Processes: A mathematical model of computing agents. In Proceedings of the Colloquium in Mathematical Logic, pp. 157–173. North-Holland, 1973.Google Scholar
[65]R., Milner and R., Weyrauch. Proving compiler correctness in a mechanized logic. In Machine Intelligence 7. Edinburgh University Press, 1972.Google Scholar
[66]S., Peyton-Jones (ed.) Haskell98, Languages and Libraries, The Revised Report. Cambridge University Press, 2003.Google Scholar
[67]E. D., Reilly. Milestones in Computer Science and Information Technology. Greenwood Press, 2003.Google Scholar
[68]J., Reppy and E., Gansner. The Standard ML Basis Library. Cambridge University Press, 2006.Google Scholar
[69]D. M., Ritchie. A stream input-output system. AT&T Bell Laboratories Tech. J., 63(8):1897–1910, 1984.Google Scholar
[70]D. M., Ritchie and K., Thompson. The UNIX time-sharing system. Commun. ACM, 17(7):365–375, 1974.Google Scholar
[71]J. E., Rodriguez. A Graph Model for Parallel Computations. Technical Report TR-64, MIT Project MAC, September 1969.Google Scholar
[72]D., Scott. Outline of a Mathematical Theory of Computation. Technical Report Technical Monograph PRG-2, Programming Research Group, Oxford University, November 1970.Google Scholar
[73]D., Scott. Continuous Lattices. Technical Report Technical Monograph PRG-7, Programming Research Group, Oxford University, August 1971.Google Scholar
[74]D., Scott. Data types as lattices. SIAM J. Comput., 5:522–587, 1976.Google Scholar
[75]D., Seror. D. C. P. L: A Distributed Control Programming Language. PhD thesis, University of Utah, 1970.
[76]S. F., Smith. A computational induction principle. unpublished note, July 1991.
[77]D. A., Turner. An overview of Miranda. SIGPLAN Notices, 21, 1986.Google Scholar
[78]D. A., Turner. SASL Language Manual. Technical report, St. Andrews University, Department of Computational Science, December 1976.Google Scholar
[79]D. A., Turner. The semantic elegance of applicative languages. In Proceedings of the 1981 Conf. on Functional Programming and Computer Architecture, 1981.Google Scholar
[80]J., Vuillemin. Correct and optimal implementations of recursion in a simple programming language. In STOC '73: Proceedings of the Fifth Annual ACM Symposium on Theory of Computing, pp. 224–239, New York, NY, USA, 1973. ACM Press.Google Scholar
[81]J., Vuillemin. Correct and optimal implementations of recursion in a simple programming language. J. Comput. System Sci., 9(3):332–354, December 1974.Google Scholar
[82]C. P., Wadsworth. Semantics and Pragmatics of the Lambda-calculus. PhD thesis, Oxford University, 1971.
[83]Z., Wan and P., Hudak. Functional Reactive Programming from first principles. In Proceedings of the ACM SIGPLAN'00 Conference on Programming Language Design and Implementation (PLDI'00), 2000.Google Scholar
[84]E., Wiedmer. Exaktes rechnen mit reellen zahlen. Technical Report Bericht no. 20, Eidgenössische Technische Hocchschule, Zurich, July 1976.Google Scholar
[85]G., Winskel. Events in Computation. PhD thesis, Edinburgh University, 1981.

Save book to Kindle

To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.

Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

Find out more about the Kindle Personal Document Service.

Available formats
×

Save book to Dropbox

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.

Available formats
×

Save book to Google Drive

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.

Available formats
×