Constraint-based type inference for the Q programming language

OData support
Dr. Szeredi Péter
Department of Computer Science and Information Theory

My thesis summarize an application of Prolog: a type checking and type

inference tool for the Q functional language. Q is a terse vector processing

language, a descendant of APL, which is getting more and more popular,

especially in financial applications. Q is a dynamically typed language, much

like Prolog. Extending Q with static typing improves both the readability of

programs and programmer productivity, as type errors are discovered by the

tool at compile time, rather than through debugging the program execution.

In this application we designed a type description syntax for Q and implemented

a parser for both the Q language and its type extension. We then implemented a

type checking algorithm using constraints. As most built-in function names of Q

are overloaded, i.e. their meaning depends on the argument types, a quite

complex system of constraints had to be implemented.

Prolog proved to be an ideal implementation language for the task at hand.

We used Definite Clause Grammars for parsing and Constraint Handling Rules

for the type checking algorithm. In my paper I describe the main problems

solved and the experiences gained in the development of the type checking


The type inference tool uses constraints that are handled by Prolog Constraint

Handling Rules. During the analysis, the application determine the possible

type values for each program expression and detect inconsistencies.


Please sign in to download the files of this thesis.