Functional Programming

Contents Objectives Working Group: Implementation of Functional Languages Present Results Links to Functional Programming Haskell Page Learning Haskell and Advanced Functional Programming Type Theory

Compiler Optimisation

Since functional programming languages are based on mathematical concepts, they are amenable to formal analysis and manipulation. Especially pure functional languages, i.e. those without side effects, do not have a fixed execution model. Hence the efficiency of program execution can be considerably improved by program transformations or modifications of the execution model using information gained by static analysis of programs.

Our current main focus is on automatic transformations for optimising programs, especially with respect to time consumption. The goal is to build a large system for optimising functional programs, which consists of a variable number of arbitrarily combineable transformation modules. This system shall itself be implemented in a functional programming language.

In order to avoid building a completely new system from scratch we decided to base our work on the Glasgow Haskell Compiler. This compiler is heavily based on the ``compilation by transformation'' paradigm and it has furthermore been designed with the goal that other people can modify and extend it - especially with new optimising transformations. Since the development of the Glasgow Haskell Compiler is a long-term project undertaken by a team, the compiler is also quite well documented. Finally, it is a widely-used compiler for a standard language. Hence we can easily test our transformations with real-world programs and the transformations may even eventually become part of the Glasgow Haskell compiler and thus find their way from theory into practical use.

We study as-yet unimplemented program transformations described in the literature, discuss their implementation and the design of the whole system, and messure the effect of transformations and the interplay of several transformations.

A center of interest is the analysis of existing deforestation algorithms and development of improved new ones.

Glasgow Haskell Compiler

Language Design

See the context patterns home page.

Other FP-Software

• A Haskell parser implemented with parser combinators.
• Simulation of an STG-Machine with non-strict Cache

Promoting Functional Programming

• Members: Prof. Dr. Indermark, Volker Stolz, Michael Weber.
• References and Links
• Internal

• Thomas Böttcher
  Debugger für Concurrent Haskell
  Diplomarbeit, RWTH Aachen, Februar 2001
• Volker Stolz
  Robuste Verteilte Programmierung in Haskell
  Diplomarbeit, RWTH Aachen, Januar 2001
• Ulrich Norbisrath
  Erweiterung von Haskell um portbasierte Kommunikation zur verteilten Programmierung
  Diplomarbeit, RWTH Aachen, Juli 2000
• Axel Simon
  Typeview - Ein Typprüfungsassistent für Haskell
  Diplomarbeit, RWTH Aachen, 2000
• Ralf Welter
  Simulation einer um Caching erweiterten STG-Maschine
  Diplomarbeit, RWTH Aachen, Februar 2000.
• Claus Jürgensen
  Kategorientheoretisch fundierte Programmtransformationen für Haskell
  Diplomarbeit, RWTH Aachen, Oktober 1999.

• Olaf Chitil:
  Type-Inference Based Short Cut Deforestation (nearly) without Inlining
  Draft Proceedings of the 11th International Workshop on Implementation of Functional Languages, Lochem, Netherlands, September 7th-10th 1999, pp. 17-32.
  Abstract , DVI (24 KB) , Postscript (540 KB)

• Olaf Chitil:
  Type Inference Builds a Short Cut to Deforestation
  ACM Sigplan Notices, 34(9):249-260, 1999. Proceedings of the 1999 ACM SIGPLAN International Conference on Functional Programming (ICFP '99).
  Abstract , DVI (40 KB) , Postscript (660 KB)
  This copy is posted by permission of ACM and may not be redistributed.

• Olaf Chitil:
  Common Subexpressions are Uncommon in Lazy Functional Languages
  Chris Clack, Tony Davie and Kevin Hammond (eds.): Proceedings of the 9th International Workshop on Implementation of Functional Languages, St. Andrews, Scotland, September 10th-12th 1997, LNCS 1467, Springer, 1998, pp. 53 - 71.
  Abstract, DVI (26 KB), Postscript (150 KB).

• Christian Tüffers:
  Erweiterung des Glasgow-Haskell-Compilers um die Erkennung von Hylomorphismen
  Diplomarbeit, RWTH Aachen, 1998, 86 Seiten.

• Martin Hönings:
  Automatische Substitution der Listenimplementierung im Glasgow Haskell Compiler
  Diplomarbeit, RWTH Aachen, 1997, 115 Seiten.

• Olaf Chitil:
  Adding an Optimisation Pass to the Glasgow Haskell Compiler
  Unpublished (draft version), 1997, 15 pages.
  Abstract, DVI (16 KB), Postscript (50 KB).

• Olaf Chitil:
  Common Subexpression Elimination in a Lazy Functional Language
  Chris Clack, Tony Davie and Kevin Hammond (eds.): Proceedings of the 9th International Workshop on Implementation of Functional Languages, St. Andrews, Scotland, September 10th-12th 1997, 16 pages.
  Abstract, DVI (26 KB), Postscript (51 KB).
  Old, obsolete version: Transformation: Elimination of Common Subexpressions

• Markus Mohnen:
  Context Patterns, Part II
  1997 International Workshop on Implementation of Functional Languages
  September 10th - 12th 1997, St. Andrews, Scotland.
  Abstract, Paper

• Markus Mohnen, Stefan Tobies:
  Implementing Context Patterns in the Glasgow Haskell Compiler
  extended version is to be published as Technical Report
  Abstract, Paper

• Markus Mohnen:
  Context Patterns in Haskell
  1996 International Workshop on Implementation of Functional Languages
  September 16th - 18th 1996, Bonn/Bad Godesberg, Germany.
  Abstract, Paper

• The Haskell Homepage
• Type Theory

• Frequently Asked Questions of the newsgroup comp.lang.functional
• The newsgroup comp.lang.functional

• Phil Wadler's Guide to Functional Programming on the Web.
• Claus Reinke's Bookmarks on Functional Programming
• Jon's Functional Languages Page

Literature

• SEL-HPC Functional Programming Archive

Relevant Conferences and Workshops

• Glasgow Functional Programming Workshops
• Conference on Functional Programming Languages and Computer Architecture (FPCA)
• Static Analysis (WSA/SAS)
• Symposium on Programming Language Implementation and Logic Programming (PLILP)
• Symposium on Principles of Programming Languages (POPL)
• Symposium/Workshop on Partial Evaluation and Semantic-Based Program Manipulation (PEPM)

Some Functional Programming Research Groups

• St. Andrews
• TU Berlin
• Canterbury, England
• Chalmers
• Glasgow
• Nijmegen
• Nottingham
• Yale
• York