Date: Thu, 13 Jun 91 11:21:03 MDT
From: Graham Birtwistle <graham@ca.ucalgary.cpsc>
Message-Id: <9106131721.AA14913@fsa.cpsc.ucalgary.ca>
To: info-hol@edu.uidaho.cs.ted

\documentstyle[11pt]{article}
\parskip=8pt plus2pt minus2pt
\begin{document}

\begin{center}
{\bf The Vth BANFF Higher Order Workshop}\\
{\bf Research Directions in Functional Programming}\\
{September 1-7 1991}\\
\ \ \\
\end{center}

\subsection*{Organisers}
Graham Birtwistle,
Computer Science,
University of Calgary,
Calgary, Alberta T2N 1N4, Canada.
Tel: (403) 220 6055.
Net: graham@cpsc.ucalgary.ca.

\noindent
John Hughes,
Department of Computer Science,
University of Glasgow,
Glasgow, Scotland.
Tel: (041) 339 8855.
Net: jmrh@cs.glasgow.ac.uk.


\section*{Speakers}
\begin{itemize}


\item Geoff Burn         {\sf Abstract interpretation and optimising compilers}

\item John Hughes        {\sf Programming using higher order functions}

\item John Launchbury    {\sf Partial evaluation}

\item Simon Peyton Jones {\sf Parallel architectures and programs}

\item David Turner       {\sf Constructive type theory}

\end{itemize}

\section*{Dates}

Arrive September 1; depart September 7.
Talks for the 5 days in between.

\newpage
\section{ABSTRACTS}


\begin{center}
{\sf Abstract Interpretation and Optimising Compilers\\
                Geoffrey Burn}
\end{center}

Compilers for imperative languages often make code
optimisations such as dead code elimination and constant folding,
by performing some analysis.
For logic-based languages, analyses have been defined to
determine the usage modes of predicates, to do compile-time
garbage collection, and sharing analysis.
Strictness analysis, compile-time garbage collection and binding
time analysis are all important for (lazy) functional languages.
How can we be sure that the optimisations made using the results
of these analyses are correct?

A correct analysis can be derived by formulating it as an abstract
interpretation.
The idea is that the symbols in a language are
given a different, abstract, interpretation, which captures the
property of interest.
A general correctness condition has to be established between the
abstract and standard interpretations of the language.
Given a program, a calculation is performed
using the abstract interpretation, and
the result is then interpreted as a statement about a property of the
program.
The correctness of this statement follows from the
relationship between the two interpretations.

In these talks we will describe the abstract interpretation
methodology, using examples from imperative and functional
programming languages.
Quite often the two communities know little of each others' work,
but each has some very useful insights for the other.
We will present some of our work in a novel way by using partial
equivalence relations.
Our presentation will finish by giving pointers to some of the
work currently being done in this burgeoning field.


\newpage
\begin{center}
{\sf Programming with Higher-Order Functions\\
John Hughes}
\end{center}


Functional programming is sometimes presented as programming WITHOUT
side-effects: I prefer to think of it as programming WITH higher-order
functions and lazy evaluation. These language features have a dramatic
effect on the way programs can be structured. Lazy evaluation permits
programs to be decomposed into small communicating parts, very like
pipelined processes. Higher-order functions can be used to build these
parts out of standard skeletons in a modular way. Used appropriately,
they enable us to design a relatively small collection of flexible
units from which larger programs can be quickly assembled.

Functional programmers have developed a collection of such higher-order
functions including map, filter, and foldr, which are a part of the
standard libraries of languages such as Haskell and Miranda.
But these well-known functions are by their
very nature general purpose. The idea of capturing common programming
skeletons in a library of functions can be applied equally well in the
context of particular applications.

Designing a library of functions for a specific application can be
thought of as inventing a special-purpose programming language for that
application, and giving its denotational semantics. Users of the
library can then effectively program in the special-purpose language.
I'll discuss several examples of this, including libraries for
pretty-printing, text formatting and parsing (where the special purpose
language is very close to BNF).  I'll also discuss some ideas from
category theory that can help in the design of appropriate libraries.

\newpage
\begin{center}
{\sf Partial Evaluation\\
John Launchbury}
\end{center}

In programming, it is common to see a tradeoff between the conflicting
requirements of clarity and efficiency. Programs destined for serious
use have to perform efficiently, and their coding reflects this fact.
Opportunities for modularisation may be resisted because of the
run-time cost, but this then reflects seriously both on the ease of
verification of correctness and on the ease of maintainance in the light
of changing requirements---to say nothing of reducing the opportunities
of software reuse.

An extreme form of modularisation is to write programs in an
interpretive style, where flow of control is determined from stored
data. Programs written in this style are comparatively easy to prove
correct, and to modify when requirements change.
Unfortunately, they have extremely poor run-time behaviour,
often an order of magnitude slower than their non-interpretive counterparts.
Thus, the interpretive style tends to be used infrequently, and only in non
time-critical contexts. Instead, flow of control is determined deep
within the program where a reasonable level of efficiency may be
obtained.

Partial evaluation is a serious attempt to tackle this issue. In
principle it allows the programmer to write in a heavily interpretive
style without paying the corresponding price in efficiency. During
partial evaluation, many of the interpretive computations are performed
once and for all, and a more efficient version of the program is
produced. Flow of control decisions are moved from stored data into the
structure of the new program. The ability to program freely in an
interpretive style should have significant implications in areas as
disparate as expert systems, ray-tracing and programming language
extensions, to name but a few.

The talks will begin with an introduction to partial evaluation,
showing something of its powers and limitations. We will go on to study
binding-time analysis, demonstrating its importance in enabling
successful self-application of a partial evaluator to itself---a
technique allowing compilers to be produced from interpreters. Finally
we shall spend some time considering more advanced issues such as
partially evaluating higher-order functions, improving binding
times, and type specialisation.

\newpage
\begin{center}
{\sf Parallelism in functional programming\\
Simon L Peyton Jones}
\end{center}

Parallelism is all the rage these days: parallel computers are easy to
build, readily avaialable, and offer outstanding raw cost/performance.
The fly in the ointment is of course the word ``raw''.  The trick is to
harness this raw power to do something useful.
The most common approach to this opportunity is bottom-up.  A conventional
imperative language is extended with extra constructs to support the creation
of concurrent threads, and their communication and synchronisation.  This works
well for algorithms where the structure of the parallelism is fairly
straightforward.
Another approach works top-down, by using a high-level language in which
the parallelism is implicit.  Functional languages are of this kind.
So are functional languages any good for programming parallel computers?
This series of lectures will address this question. The main topics will be
these:


\noindent
Basic technology and architectural issues.\\
There are currently two very active strands of research in parallel
functional-language implementation, namely lazy graph reduction and
dataflow.  I will sketch how each technique works, what the recent
advances have
been, and survey the currently-active research areas.

\noindent
Resource management issues.\\
A vital question is how efficiently the system can map a functional
program onto parallel hardware.  There is a big rats-nest of issues here:
when to create a thread, when to run it, which processor to run it on,
where to store data, whether to duplicate data or to share it, and so on.
Bad decisions about these questions can lead to a huge performance penalty.
I will sketch the issues, and outline the approaches which are being
studied, especially granularity and placement annotations, and K-bounded loops.

\noindent
Are functional languages expressive enough?\\
Pure functional languages can express a variety of parallel programming
paradigms (eg pipelining, divide and conquer), but there are others which
seem beyond its reach (eg branch and bound).  I will discuss what the problem
is, and a variety of ways in which researchers have suggested relaxing the
``rules'' in order to gain concurrency; for example, I-structures, bags,
improving values, non-determinism, M-structures.

\newpage

\begin{center}
{\sf Constructive type theory \\
David Turner}
\end{center}


\newpage
\begin{center}
{\bf Subject: Banff V.  \\
Banff, Alberta September 1--7 1991, \\
Address: The  Banff  Centre, Box 1020, Banff, Alberta T0L 0C0 \\
Telephone: (403) 762-6202}
\end{center}

The workshop will have around 30 participants including speakers---to avoid
disappointment, register your interest with Graham Birtwistle as soon as you can.
The theme of the workshop is functional programming research---your
chance to hear from some of the leading European researchers.
The workshop is intended for graduate students and researchers
already working in functional programming who want a kick start into
selected central themes.

\begin{quote}
The cost for non-speakers is \$CAN 850 which includes
GST, full accommodation and food for the week at the Banff Centre,
xeroxing charges, and a nominal contribution towards
getting the speakers there.
Any speaker/participant bringing family will only be charged for
accommodation and food.

{\bf When  registered, make cheques out to {\it Banff V HOW Workshop}
and send them to the organiser at the Calgary end (Graham Birtwistle).}
\end{quote}

{\it Due to space restrictions, some of us will have to share rooms.}
Let me know if there is anyone you would like to share with.
If you can't hack sharing, we will do our best.

This year we have scheduled breakfast at 7.00-8.00,
two talks per morning between 8.00 and say 11.00,
an evening meal at 18.30, and an evening lecture at 19.30.
The idea, adopted from previous workshops held in Banff
is that with everyone together in `seclusion' you can talk to your favourite
lecturer at breakfast, go walkies with them in the afternoon, have
supper with him/her in the evening, and then repair to wherever with him/her in the evening.
I.e. you have the chance to make or re-inforce
varied personal contacts in the field
and learn current research thrusts.

\subsection*{General items}

\begin{itemize}

\item Location: The  Banff  Centre, Box 1020, Banff, Alberta T0L 0C0.
Tel: (403) 762-6202.
The Banff Centre is a residential
continuing education school which sits
a few minutes walk from the centre of Banff (125 kilometres
west of Calgary). Head for Banff (population 7,000) and ask.
The Centre is equipped with excellent conference services
and other such goodies as a swimming pool,
tennis courts, running track, gymnasium, and squash courts.

\item Registration: will take place in the Bourgeau Room at the Banff Centre between
20.00 and 22.00 Sunday September 1st 1991.
This is where you pick up workshop handouts.
You are asked to vacate your room by 11.00 Saturday, September 7 1991.
{\it Let me know if you will not be there for the full period.}

\item Meals: three meals are provided each day.
They are all paid for in your workshop fee.
Breakfast at 7.00 in the canteen;
packed lunch for you to take out at 11.00;
and supper in the canteen at 18.30.
You also get supper on September 1st and breakfast on September 7th.
{\it Let me know if you have special requirements,
e.g. vegetarian or kosher}.

\item Airport transportation: Fly to Calgary. You then have 3 options:
\begin{enumerate}
\item Rent a car (book in advance) and drive along the Trans Canada
Highway West to Banff.
Route finding is easy. Drive out from the Airport South along Barlow Trail
(the only road) for about 10 kilometers; turn right onto the Trans Canada Highway
(Highway 1) going West. Banff is now about 120 km away,
20 km after entering the National Park.
You will need a Park permit (\$CAN 10) or so for the week -- sorry about that,
it is NOT part of the fee.

\item Take a bus to Banff and a short taxi ride from there.
There are two bus lines.
Brewsters (403 762 2286) which
leaves Calgary at 12.20 and 17.15 daily, and Pacific Western Transport
(403 762 4458) which leaves at 12.00, 15.00, and 19.00.
The fare is \$CAN 20 each way and no reservations are necessary.
You will need to take a cab or a bus from the airport to the bus depot.
Enquire at the Airport.

\item You are hopelessly poor.
Let me know and we will do our best to get you a lift out.
In this case remember that the workshop starts with a
get together on Sunday evening
and the guy giving you a lift will want to be in Banff Sunday afternoon.
\end{enumerate}

\item The weather in Alberta varies enormously, from day to day even.
We expect the temperature to be around 20 Celcius,
but it will be cool at night (0 Celcius) -- it might even be 15 below.
It always snows in September, so bring some warm gear.
\end{itemize}

\begin{verbatim}


                  REGISTRATION FORM
                     BANFF V 1991

Email to graham@cpsc.ucalgary.ca,       or
Fax to Graham Birtwistle at (403) 284 4707.


I would like to attend this workshop:

Name:
Affiliation:
Address:


Telephone:
Fax:
Net address:

Dietary restrictions:
  None
  Vegetarian
  Milk free
  Kosher

\end{verbatim}
\end{document}