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

Scalable Program Analysis and topics in Programming Language Design and Transformation

Josef Svenningsson (Institutionen för data- och informationsteknik, Datavetenskap (Chalmers))
Göteborg : Chalmers University of Technology, 2007. ISBN: 978-91-7291-899-3.- 203 s.

The thesis covers a variety of topics in programming language technology, with the main emphasis on static program analysis. A program analysis is an automatic method, a program, which anwers a specific question about programs. Examples of questions could be "Will this program crash?" and "Will a certain part of the program ever be executed?" Program analyses answering questions such as these can be used to improve the efficiency and security of programs.

A program analysis can never be exact. This means that there will always be apportunities to develop new and increasingly precise methods for program analysis. However these analyses can easily become very resource hungry, taking a lot of time and memory to compute.

This thesis develops methods for scalable program analysis. As programs grow larger and more complex program analyses should still yield precise enough answers and be feasible to compute.

Our contributions include a new constraint-based program analysis method, Constraint Abstractions, specifically targeted towards computing solutions to precise program analyses. The key technical contribution is an O(n^3) algorithm for program analyses which uses polymorphism and subtyping. A concrete case study is described: a Usage analysis which answers the question "Is a particular value used at most once?"

We also present a comprehensive experimental exploration of the vast design space for program analyses in order to determine how program analysis features interact and impact precision.

Beside program analysis this thesis covers two other topics: program transformation and programing language design. A new technique is introduced for fusing functions, thereby removing any intermediate data structure and improving the speed of programs. Last we show how regular expressions can be seamlessly added to the pattern matching facility found in functional programming languages.

Denna post skapades 2007-02-20. Senast ändrad 2013-09-25.
CPL Pubid: 26437


Institutioner (Chalmers)

Institutionen för data- och informationsteknik, Datavetenskap (Chalmers)



Chalmers infrastruktur

Relaterade publikationer

Inkluderade delarbeten:

Regular Expression Patterns

Polymorphism, Subtyping, Whole Program Analysis and Accurate Data Types in Usage Analysis

Constraint Abstractions

A usage analysis with bounded usage polymorphism and subtyping

Shortcut fusion for accumulating parameters & zip-like functions


Datum: 2007-03-23
Tid: 10.15
Lokal: 10.15 Lecture room EC, ED&IT-building, Hörsalsvägen 11, Göteborg
Opponent: Professor Jakob Rehof, Department of Computer Science, University of Dortmund, Germany

Ingår i serie

Doktorsavhandlingar vid Chalmers tekniska högskola. Ny serie 2580

Technical report D - Department of Computer Science and Engineering, Chalmers University of Technology and Göteborg University 26D