Published Papers

Cat: A Functional Stack-Based Little Language

Doctor Dobbs Journal, April 15th, 2008

Abstract
My interest in Joy was primarily motivated by my search for an intermediate language that could be easily targeted by imperative and functional languages, could be easily optimized, and could be statically verified. Joy relies heavily on dynamic checking, so I created a more restricted, statically typed language based on Joy and called it "Cat."

Technical Reports

Simple Type Inference for Higher-Order Stack-Oriented Languages

Technical Report Cat-TR-2008-001, Draft April 20, 2008

Abstract
Stack based languages are widely used as byte-codes, as intermediate languages, and as programming languages for embedded devices. It is well-known how to check the types of simple stack-based languages such as for the Java virtual machine language, using Hindley- Milner type inference, or using Hoare logic. The simple Hindley-Milner type inference algorithm is insufficient to type-check higher order instructions, such as abstraction operators, in a stack-based language without annotations. This limitation occurs because we require first-class polymorphism. Our contribution is to describe a simple type-system and type-inference algorithm for higher-order instructions in a single stack stack-based language.

Retired Papers

Typing Functional Stack-Based Languages

Christopher Diggins, April 6th, 2007

Abstract

Stack-based languages (e.g. Forth (Moore 1974)) have been around for nearly four decades. They are particularly popular today for use as intermediate languages (e.g. CIL (ECMA 2002), JVML (Lindholm and Yellin 1999), (Morrisett et al. 1998)). This is for several reasons: they have good run-time performance characteristics, they resemble the machine level instructions on many computers, they are easy to implement, and they have compact representations. In these stack-based languages instructions are not first-class values.

The Joy programming language (von Thun 2001) and the Factor programming language (Pestov 2003) are examples of functional stack-based languages: they allow instructions to be treated as data and placed on the stack. These languages however are lacking a static type system.

This paper aims to bridge the gap between statically typed imperative stack-based languages and untyped functional stack-based languages by defining a type-system for a point-free functional stack-based language.

This paper has been superceded by the latest technical report and is longer available for download. Please contact me if you would like a copy.

Comments are warmly invited either privately at cdiggins@gmail.com, or publicly at the Cat language discussion group at Google ( http://groups.google.com/group/catlanguage ).

The Cat Programming Language by Christopher Diggins