Newsgroups: comp.lang.functional
Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!think.com!linus!linus!linus!swarup
From: swarup@mitre.org (Vipin Swarup)
Subject: Re: Summary: functional programming of graph algorithms (long)
In-Reply-To: barth@au-bon-pain.lcs.mit.edu's message of 21 Jun 91 10:54:56
Message-ID: <SWARUP.91Jun25162916@hrothgar.mitre.org>
Sender: news@linus.mitre.org (News Service)
Nntp-Posting-Host: hrothgar.mitre.org
Reply-To: swarup@mitre.org
Organization: Mitre Corporation, Bedford, MA.
References: <5495@ztivax.UUCP> <1865@harl86.harl.hitachi.co.jp>
	<BARTH.91Jun21105456@au-bon-pain.lcs.mit.edu>
Date: 25 Jun 91 16:29:16
Lines: 45



You might also look at the following paper:

  @InProceedings(Imperative-lambda-calculus,
	Author = "Swarup, V. and Reddy, U.S. and Ireland, E.",
	Title = "Assignments for applicative languages",
	BookTitle = "Proc. Conf. on Functional Programming Languages and Computer Architecture",
	Note = "(To appear)",
	Month = "August",
	Year = "1991"
	)

The paper proposes a framework for adding references and assignments
to pure, strongly-typed functional languages without violating the
semantic properties of the languages.  Expressions do not have
side-effects, and the extended languages are proper extensions of the
assignment-free languages.  That is, the denotational and operational
semantics of lambda-abstraction/application and pairing/projection are
exactly the same before and after the extension.

References may be used to construct arbitrary data structures
(including graphs). Shared data may be destructively modified, and the
modifications are visible to other parts of the program without having
to explicitly pass the new values to those program points. This is
demonstrated by a program for unification.

The formal language considered in the paper is called "Imperative
Lambda Calculus" (ILC for short).  The type system of ILC ensures that
state-oriented computation is combined linearly, allowing an
implementation in terms of a global store.  Evaluation of well-typed
programs is Church-Rosser.  Thus, programs produce the same results
whether an eager or lazy evaluation order is used (assuming
termination).  The benefits of this work include greater expressive
power and efficiency (compared to applicative languages), while
retaining simplicity of reasoning.

==========================================================================
Vipin Swarup, MS A156
The MITRE Corporation
Burlington Road
Bedford, MA 01730.

E-mail :   swarup@mitre.org
==========================================================================