Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.

Dismiss

Functional Operating Systems (Summary)

21 views

Skip to first unread message

Michael David WINIKOFF

unread,

May 2, 1993, 11:45:40 PM5/2/93

Summary of responses to my question on functional operating systems and
KAOS in particular.

Thanks muchly to those who replied!

Michael

----------------------------
Collected references:

J. Cupitt
Another New Scheme for Writing Functional Operating Systems
UKC Computing Laboratory Report No. 52, University of Kent, Canterbury,
1988 (probably about KAOS again)

J. Cupitt
A Brief Walk Through KAOS
University of Kent at Canterbury Computing Laboratory Report No. 58, 1989

J. Cupitt
The Design and Implementation of an Operating System in a
Functional Language
Computing Laboratory, University of Kent Canterbury, Kent, 1990, PhD Thesis.

D. Turner
Functional Programming and Communicating Processes
Parallel Architectures and Languages Europe (PARLE), LNCS 259, Vol. 2 pp54-74

D. Turner
An Approach to Functional Operating Systems
Research Topics in Functional Programming, pp199-218, Addison Wesley,
ISBN 0-201-17236-4

Kent Karlsson
Nebula: A Functional Operating System
Programming Methodology Group Memo LPM11, Laboratory for Programming
Methodology, Chalmers University of Technology, Gteborg, 1981

Peter Henderson
Purely Functional Operating Systems
In John Darlington, Peter Henderson, Dave A. Turner, Eds.
Functional Programming and its Applications
Cambridge University Press, 1982, pp177-192

Peter Henderson, Simon B. Jones
Shells of Functional Operating Systems
University of Stirling, Dept. Comp. Sci. Report FPN--4, and in
``Distributed Computer Systems'' ed. D.A. Duce, Peter Peregrinus, 1984

Simon B. Jones
Abstract Machine Support for Purely Functional Operating Systems
Oxford University Computing Laboratory, Programming Research Group,
Monograph PRG--34, August 1983 also Stirling University CS Report 15

Simon B. Jones
A Range of Operating Systems written in a Purely Functional Style
University of Stirling, Dept. Comp. Sci. Report TR.16, 1984
--- also Oxford University Computing Laboratory, Programming Research
Group, Monograph PRG--42

S. B. Jones and A. F. Sinclair,
"Functional Programming and Operating Systems",
The Computer Journal 32(2), pp162--174, April 1989.

W.R. Stoye
A New Scheme for Writing Functional Operating Systems
Cambridge University Comp. Lab. Tech. Rep. 56

William Stoye,
"Message-based functional operating systems",
Science of Computer Programming 6(3), 291--311, 1986.

Andrew D. Gordon,
"Functional Programming and Input/Output",
PhD dissertation, University of Cambridge.
Available as Technical Report 285, University of Cambridge
Computer Laboratory, February 1993.

Andrew D. Gordon,
"An operational semantics for I/O in a lazy functional language",
To appear in the proceedings of FPCA'93, Copenhagen, June 1993.

Burstall, R.M. and Popplestone, R.J., [1968]
The POP-2 Reference Manual,
Machine Intelligence 2, pp. 205-46, eds Dale,E. and Michie,D. Oliver and Boyd,
Edinburgh, Scotland.
[This is more widely available than the 1971 publication, but says almost
nothing about the operating system issues.]

R.D.Dunn "The POP-2/4100 Users' Manual",
Edinburgh: Department of Machine Intelligence and Perception.
(An internal report, probably available from the Department of
Artificial Intelligence, Edinburgh University: I don't
have a copy).

D.J.S.Pullin "A plain man's guide to Multi-POP implementation",
Mini-MAC Report No.2 Edinburgh: Department of Machine Intelligence.
(as above)

Collins,Ambler,Burstall,Dunn,Michie,Popplestone, Pullin
"Multi-POP/67: A cheap on-line system for numerical and non-numerical computing"

-----------------------------

~From: a...@cs.st-andrews.ac.uk (Tony Davie)

In article <931182...@mulga.cs.mu.OZ.AU>, wini...@cs.mu.OZ.AU (Michael David WINIKOFF) writes:
>
> Where can I get hold of papers on KAOS?
> (Kent Applicative Operating System)
>

I have the following in my ref. list:

J. Cupitt Q A Brief Walk Through KAOS Q University of Kent at
Canterbury Computing Laboratory Report No. 58, 1989

J. Cupitt Q The Design and Implementation of an Operating System in a
Functional Language Q Computing Laboratory, University of Kent
Canterbury, Kent, 1990, PhD Thesis.

D. Turner Q Functional Programming and Communicating Processes
Q Parallel Architectures and Languages Europe (PARLE),
LNCS 259, Vol. 2 pp54-74 (The paper you already had, I think)

> What other operating systems have been written in pure functional languages?
> References?
>

D. Turner Q An Approach to Functional Operating Systems Q
Research Topics in Functional Programming, pp199-218, Addison Wesley,
ISBN 0-201-17236-4

Kent Karlsson Q Nebula: A Functional Operating System
Q Programming Methodology Group Memo LPM11, Laboratory for Programming
Methodology, Chalmers University of Technology, Gteborg, 1981

J. Cupitt Q Another New Scheme for Writing Functional Operating Systems
Q UKC Computing Laboratory Report No. 52, University of Kent, Canterbury,
1988 (probably about KAOS again)

Peter Henderson Q Purely Functional Operating Systems Q
In John Darlington, Peter Henderson, Dave A. Turner, Eds.
Q Functional Programming and its Applications
Q Cambridge University Press, 1982, pp177-192

Peter Henderson, Simon B. Jones Q Shells of Functional Operating Systems
Q University of Stirling, Dept. Comp. Sci. Report FPN--4, and
in ``Distributed Computer Systems'' ed. D.A. Duce, Peter Peregrinus, 1984

Simon B. Jones Q Abstract Machine Support for Purely Functional Operating
Systems Q Oxford University Computing Laboratory, Programming Research Group,
Monograph PRG--34, August 1983 also Stirling University CS Report 15

Simon B. Jones Q A Range of Operating Systems written in a Purely
Functional Style Q University of Stirling, Dept. Comp. Sci. Report
TR.16, 1984 --- also Oxford University Computing Laboratory,
Programming Research Group, Monograph PRG--42

Simon B. Jones Q Functional Programming and Operating Systems
Q Computer Journal 32, 2, pp162-174 1989

W.R. Stoye Q A New Scheme for Writing Functional Operating Systems
Q Cambridge University Comp. Lab. Tech. Rep. 56

I hope these help.

Tony Davie

----------------
~From: pop%rab...@cs.umass.edu

I don't quite see how it is possible to write an operating system in a
*pure* functional language, since machine state must be affected.
Multipop-68, written by myself, Ray Dunn and others around 1968 certainly
used the functional paradigm heavily, i.e. it had a system-wide
compacting, method-driven garbage collector, closures were used as the
abstracting mechanism for presenting peripherals to the user. Initially it
was written in an intermediate dialect between POP-1 and POP-2, with
assembly-code inserts. For performance reasons, the percentage of
assembly-code rose steadily throughout the lifetime of the system. Also
some pure assembly code was inherited from the earlier Minimac project
(primarily interrupt routines).

Multipop served as a development environment for much of the work done at
Edinburgh from 1968-75, including the Boyer Moore program prover,
Burstall and Darlington's work on program transformation, and early work on
the Hope language.

Robin Popplestone.

-----------------------
~From: pop%rab...@cs.umass.edu

There is rather little documentation on the implementation details of
Multipop, although the source code still exists and is kept in Edinburgh
- I am not sure which version.

The best description of language and environment can be gained from
"Programming in POP-2" by Burstall, Collins and Popplestone [1971],
published by Edinburgh University Press. This is thus a user's description
of the operating system/language environment. The language description is
given in lower case, but the teletypes we used enforced upper case until
the mid-70's.

Thus of the parts of a conventional operating system:

What corresponds to the shell is simply the POP-2 compiler (a view that
was to be adopted by the designers of the LISP machine).

An editor, LIB POPEDIT is described. This, in the days before VDU's, is
as primitive as the standards of the day. The source code is given for
the editor. (2 pages of POP-2).

System calls were performed by a function POPMESS, which took as input a
device description and returned as result a "repeater", i.e. a procedure
which produced the characters of an input stream, or consumed the
characters of an output stream. Such a procedure (a "function" in the
language) could be converted to the referentially transparent form of a
"dynamic list", i.e. a quasi-lazy list, by the procedure FNTOLIST.

The "file store" was provided by LIB EASYFILE, a POP-2 program which
made use of disc-access primitives DISCIN and DISCOUT, which referred to
specific track and block numbers. Again, the 2 pages of program it took
to define LIB EASYFILE are given. Capabilities were limited - in effect
each disc track was assigned to one user, who used it in effect like a
small private disc.

Continuations are described in the book, under "A Language Extension:
Generalized Jumps and Backtracking". While we realised the potentiality
for process-swapping implied by continuations, we had painted ourselves
in a corner as far as an efficient implementation being possible since we
were not using lexical variable binding, partly because of the shortage
of index registers on our machine. (Closures were done by partial
application). Thus processes were a special-purpose mechanism not
available to the user: one user = one process and that is it.
Continuations were used for exploring things like backtrack search.