SYNTHESISING INCREMENTAL PARSING AND INCREMENTAL TYPE INFERENCING

Abstract

Incremental computation takes advantage of repeated computation on inputs that differ slightly from one another, computing each new output incrementally by making use of the previous output rather than from scratch. Incremental parser is commonly used in a syntax-directed programming environment to handle parsing of expressions containing infix operators [Hee90]. Its ability to detect program errors as early as when the user is entering the expression makes such a programming environment appealing. Providing type information of the program under development to the incremental parser not only enables checking of both syntax and type errors at very early stage of program development, but also assists in the making of parsing decision. In other words, it enables more intelligent incremental parsing than conventional incremental parsers. So, we name this new parser type-sensitive incremental parser. In this thesis, we investigate the design of a type-sensitive incremental parsing for functional programs. In other words, we attempt to formulate a infer-&-check-as-you-parse approach to writing ML-like functional programs. The problems we tackle are: (1) incremental computation of ML-like type system in the syntax-directed environment: and (2) synthesis of incremental parsing and incremental type inference. We extend Heeman's incremental parsing approach [Hee90] with checking and guidance from type information obtained via an incremental type checker which has several similarities with that devised by Aditya and Nikhil [AN91], but handles type checking of program containing multiple holes.