Static type inference for a first-order declarative visual programming language with inheritance

The early detection of type errors is a well-known benefit of static typing , but until recent years, this benefit usually has come at the cost of requ iring the programmer to explicitly declare the type of every object in a pr ogram. Since many visual programming languages (VPLs), especially those VPL s intended for end users, are designed to eliminate such programming mechan isms, most VPLs have been implemented with dynamic typing, thereby sacrific ing early type error feedback and other benefits of static typing. One pote ntial solution for this dilemma is static type inference, but unfortunately , the types inferred under previous approaches have been notoriously diffic ult to understand, even for professional programmers. Compounding this prob lem is the fact that when support for inheritance is added to such type inf erence systems, explicit type declarations have re-emerged. In this paper, we present a model of types that supports static type infere nce for a declarative VPL that includes inheritance. Our model addresses th e problems presented in the previous paragraph. We present the formal model of our type system, and show that the model is not only sound with respect to type safety, but that it also has sufficient power to support tradition al and non-traditional forms of inheritance, and further that it requires t he user to understand only a small vocabulary of types, a feature important in addressing the understandability problem in end-user VPLs. (C) 2000 Aca demic Press.