Links und Funktionen
Sprachumschaltung

Navigationspfad
Sie sind hier: Startseite / Lehre / SS 2010 / Oberseminar / Ulrich Schöpp: Type Inference for Sublinear Space Functional Programming


Inhaltsbereich

Ulrich Schöpp: Type Inference for Sublinear Space Functional Programming

Fr, 23.07.2010 14:15 TCS Oberseminar
Wann 14:15 15:15 23.07.2010
von bis
Wo L109
Termin übernehmen vCal
iCal

Ulrich Schoepp,

 

Type Inference for Sublinear Space Functional Programming

(joint work with Ugo Dal Lago, Bologna)

 

We consider programming language aspects of algorithms that operate on

data too large to fit into memory. In previous work we have introduced

IntML, a functional programming language with primitives that support

the implementation of such algorithms. We have shown that IntML can

express all LOGSPACE functions but have left open the question how easy

it is in practice to program typical LOGSPACE algorithms in IntML.  

 

Here we show that useful type inference is possible for IntML. While

existing results on equational unification imply that type inference for

IntML is hard in general, we identify useful restrictions of the

language for which type inference is feasible. We show that with type

inference one can handle programs that could not be reasonably

manipulated by hand, such as a program to test undirected graphs for

acyclicity. We thus give evidence that with type inference IntML can

express typical algorithmic patterns of LOGSPACE and in a natural way.

Artikelaktionen

abgelegt unter:

Funktionsleiste