CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Constraint Abstractions

Jörgen Gustavsson (Institutionen för datavetenskap, Funktionell programmering) ; Josef Svenningsson (Institutionen för datavetenskap, Funktionell programmering)
Lecture Notes in Computer Science - Second Symposium on Programs as Data Objects (0302-9743). Vol. LNCS (2001), 2053, p. 63-83.
[Konferensbidrag, refereegranskat]

Many type based program analyses with subtyping, such as flow analysis, are based on inequality constraints over a lattice. When inequality constraints are combined with polymorphism it is often hard to scale the analysis up to large programs. A major source of inefficiency in conventional implementations stems from computing substitution instances of constraints. In this paper we extend the constraint language with constraint abstractions so that instantiation can be expressed directly in the constraint language and we give a cubic-time algorithm for constraint solving. As an application, we illustrate how a flow analysis with flow subtyping, flow polymorphism and flow-polymorphic recursion can be implemented in time where is the size of the explicitly typed program.



Denna post skapades 2007-02-20. Senast ändrad 2013-06-10.
CPL Pubid: 26434

 

Läs direkt!


Länk till annan sajt (kan kräva inloggning)


Institutioner (Chalmers)

Institutionen för datavetenskap, Funktionell programmering (2002-2004)

Ämnesområden

Datalogi

Chalmers infrastruktur

Relaterade publikationer

Denna publikation ingår i:


Scalable Program Analysis and topics in Programming Language Design and Transformation