Christopher Diggins. “Typing functional stack-based languages”. Unpublished technical report. May 2008.

Remarkable PDF

Original PDF



Stack-based languages (e.g. Forth (Moore 1974), Postscript (Inc. 1999)) have been around for nearly four decades. They are par-ticularly 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 perfor-mance 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 instruc-tions 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 im-perative stack-based languages and untyped functional stack-based languages by defining a type-system for a point-free functional stack-based language.


Mentions several other papers that “formally describe the type system for non-functional stack-based languages”: Raffali1993, Stata1998, O'Callahan1988, Poial2006.