[Prev][Next][Index][Thread]
[menke@harvard.harvard.edu: Colloquium Announcements]
Date: Thu, 17 Mar 88 09:24:53 EST
From: menke@harvard.harvard.edu (Baiba Menke)
To: colloquium@harvard.harvard.edu
Subject: Colloquium Announcements
HARVARD
Colloquiua are held at 4pm with tea preceeding at 3:30 in the
Aiken Main Lobby
...
Friday, March 25, 1988
The Efficient Implementation of Functional Languages
Jonathan Young
Computer Science Department
Yale University
Abstract
While much has been made of the beauty of functional languages,
in which a few orthogonal primitives promote an equational style of
programming and it is easy to prove the correctness of programs
(and program transformations), implementations of such languages have
traditionally been very inefficient. In fact, much of this cost is
a direct consequence of the normal-order ("call-by-need" or "lazy")
evaluation semantics of such languages. It is possible to give a
precise semantic characterization of when it is safe to transform
"call-by-need" evaluation into "call-by-value", but this
characterization ({\it strictness analysis}) is in general undecidable.
Using a technique called {\it abstract interpretation}, we
approximate the strictness properties of a program by a decidable
(although exponential) semantic predicate; we use other general
techniques, including {\it depth bounding} and {\it pending analysis},
to compute the semantic predicate efficiently. If time permits, we
will also explore some of the extensions to strictness analysis we
have been developing.
Host: Prof. T. E. Cheatham
....