Use of a functional language in OS development
Levi
enjoyment and have a few questions regarding functional languages. One
of my project goals is to break new ground by foregoing almost all
backwards compatibility; on that front I decided to create a new
programming language in which to develop my OS.
While searching for inspiration, I've heard (well, read actually) good
things about functional programming. I rediscovered Forth (it always has
interested me), which is very easy to compile, but soon began to worry
that it decays into gibberish quite easily. I like the syntax and
semantics of Haskell (at first glance anyway), but it seems to be quite
a large system.
I've developed some toy imperative languages, and haven't found it very
difficult. I was wondering if developing a functional language is
signifigently more difficult. Can anyone offer me advice on this front?
Pointers to small functional languages or info on functional language
implimentation whould be much appreciated.
Another thing I've been wondering about is the suitability of the
functional paradime to OS development. When I begin to think about it,
an OS's job is almost all side effect oriented. Is this veiw correct, or
can the OS's functionality be veiwed otherwise? Are fuctional languages
suitable to event driven tasks like operating systems and interactive
userland applications?
-Levi
Joachim Durchholz
> I've developed some toy imperative languages, and haven't found it very
> difficult. I was wondering if developing a functional language is
> signifigently more difficult.
There's a paper somewhere floating in the net describing the
implementation of a full functional language. Simon Peyton-Jones, I
think, with "tutorial" somewhere in the title (sorry I don't have the
paper handy).
> Another thing I've been wondering about is the suitability of the
> functional paradime to OS development. When I begin to think about it,
> an OS's job is almost all side effect oriented. Is this veiw correct,
Yes. A lot of the OS is dedicated to changing the state of the world
(especially in the device drivers).
FPLs are not about eliminating side effects. They are about avoiding
them as far as possible, and about pushing the unavoidable side effects
as far to the top level as possible.
> Are fuctional languages suitable to event driven tasks like
> operating systems and interactive userland applications?
I wouldn't want to program a state machine in an FPL (unless the FPL
comes with libraries that give me thinly disgused imperative programming
back).
But there's a whole host of things that can be specified in a functional
way. The menu structure is static, the links from menu items to actions
to be executed is static, the constraints on input fields are static.
Anything that you can find a static description for can be factored out
and made functional. (This essentially applies to all programming; the
natural limit for this technique is where the static description start
to become as unwieldy as the dynamic/imperative ones.)
Just my 2c.
Regards,
Joachim
--
This is not an official statement from my employer.
Peter G. Hancock
I suppose it might be possible actually to write an OS kernel
_in_ a lazy FPL. It has been done in the past, in the Lispkit system,
before monadic IO.
One would like to be sure it ran in constant space and bounded time,
whatever the system call. It would certainly need some fairly
substantial "jacket", for the FPL's own GC, but also to marshall
arguments of system calls, deliver results to waiting processes,
and do something about interrupts.
Very speculatable-aboutable.
Peter Hancock
Benjamin Ylvisaker
There are two projects that I know of that attempted to combine ML and
operating systems:
http://www.ai.mit.edu/projects/express/
http://www2.ics.hawaii.edu/~esb/prof/proj/hello/index.html
There is a good paper about purely functional GUIs:
http://www.cs.uu.nl/people/ralf/hw2001/3.html
Good luck.
Benjamin
p.s. I have been thinking that it would be great to build an operating
system with provably correct languages and proof carrying code: Prove
that your OS can never crash! (modulo hardware failures)
Claus Reinke
> I'm working on a small operating system project for my own personal
> enjoyment and have a few questions regarding functional languages. One
> of my project goals is to break new ground by foregoing almost all
> backwards compatibility; on that front I decided to create a new
> programming language in which to develop my OS.
If the keywords a "small" and "for your own personal enjoyment", sure, why not?
Otherwise, there might still be some research to be done - perhaps Clean with
its new support for type Dynamic might be a possible vehicle (there used to be
plans for investigating building some kind of OS on top of that, but that seems
to
have disappeared - lack of resources, I guess).
> Another thing I've been wondering about is the suitability of the
> functional paradime to OS development. When I begin to think about it,
> an OS's job is almost all side effect oriented. Is this veiw correct, or
> can the OS's functionality be veiwed otherwise? Are fuctional languages
> suitable to event driven tasks like operating systems and interactive
> userland applications?
The basics are not new ground at all.. Getting all the details right for
practical
use would be another matter. I think the answer was something like: you'd like
a non-deterministic merge (well, actually fair selection of available inputs
from
a set of potential inputs), but everything else could be programmed functionally
(setting resource usage and type system questions to the side for now:).
In fact, one needs at most one instance of such a merge (Stoye's "sorting
office"), so careful design can limit the effects of non-determinism on
functional reasoning. Lots has been written about this and related issues,
but here are a few example references.
Claus
@article{JonesSinclair89,
author = {S.B. Jones and A.F. Sinclair},
title = {{Functional Programs and Operating Systems}},
journal = {The Computer Journal},
year = 1989,
volume = {32},
number = {2},
pages = {162-174},
topics = {FP - Input/Output}
}
@incollection{Henderson82,
crossref = {DarlingtonHendersonTurner82},
author = {Peter Henderson},
title = {{Purely Functional Operating Systems}},
year = 1980,
pages = {177-192},
topics = {FP - General,FP - Input/Output,FP - Nonsequential Execution}
}
@book{DarlingtonHendersonTurner82,
editor = {J. Darlington and P. Henderson and D.A. Turner},
booktitle = {{Functional programming and its applications}},
publisher = {Cambridge University Press},
year = 1982,
topics = {FP - General}
}
@article{Stoye86,
author = {William Stoye},
title = {{Message-Based Functional Operating Systems}},
journal = {Science of Computer Programming},
year = 1986,
volume = {6},
pages = {291-311},
topics = {FP - Nonsequential Execution}
}
Arjen
On Tue, 26 Mar 2002, Claus Reinke wrote:
> "Levi" <le...@gis.net> schrieb im Newsbeitrag news:3CA058B0...@gis.net...
> > I'm working on a small operating system project for my own personal
> > enjoyment and have a few questions regarding functional languages. One
> > of my project goals is to break new ground by foregoing almost all
> > backwards compatibility; on that front I decided to create a new
> > programming language in which to develop my OS.
>
> If the keywords a "small" and "for your own personal enjoyment", sure, why not?
> Otherwise, there might still be some research to be done - perhaps Clean with
> its new support for type Dynamic might be a possible vehicle (there used to be
> plans for investigating building some kind of OS on top of that, but that seems
> to
> have disappeared - lack of resources, I guess).
We are still investigating a functional operating system, written in
Clean with type safe communications using dynamics.
I've made a micro-kernel on top of Windows (the current dynamics
run-time linker requires it) and process manager, and I'm working on a
shell (with a functional syntax), a device manager and a typed file
system (containing dynamics). The basic idea is that any dynamic that
contains a function can be regarded as an executable, which can be
dynamically loaded and executed as a concurrent functional process.
> > Another thing I've been wondering about is the suitability of the
> > functional paradime to OS development. When I begin to think about it,
> > an OS's job is almost all side effect oriented. Is this veiw correct, or
> > can the OS's functionality be veiwed otherwise? Are fuctional languages
> > suitable to event driven tasks like operating systems and interactive
> > userland applications?
>
> The basics are not new ground at all.. Getting all the details right for
> practical
> use would be another matter. I think the answer was something like: you'd like
> a non-deterministic merge (well, actually fair selection of available inputs
> from
> a set of potential inputs), but everything else could be programmed functionally
> (setting resource usage and type system questions to the side for now:).
> In fact, one needs at most one instance of such a merge (Stoye's "sorting
> office"), so careful design can limit the effects of non-determinism on
> functional reasoning. Lots has been written about this and related issues,
> but here are a few example references.
Personally, I think that functional languages are very suitable for event
driver tasks. Higher-order functions can easily be used to setup 'callbacks',
as done in the Clean Object I/O library. Hiding the event loop
alltogether, and eliminating the need to write functional process as
stream processors.
regards,
Arjen van Weelden
Martin Young
> p.s. I have been thinking that it would be great to build an operating
> system with provably correct languages and proof carrying code: Prove
> that your OS can never crash! (modulo hardware failures)
Depends how you define crash, I suppose.
You might be interested in VFiasco - a project to produce a formally
verifyable L4 microkernel. AFAIK they haven't published a hugh amount
of detailed information but they do have a web page here
http://os.inf.tu-dresden.de/vfiasco/
--
Martin Young, at work.