Cat: A Functional Stack-Based Little Language
Doctor Dobbs Journal, April 15th, 2008
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."
Simple Type Inference for Higher-Order Stack-Oriented Languages
Technical Report Cat-TR-2008-001, Draft April 20, 2008
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.
Typing Functional Stack-Based Languages
Christopher Diggins, April 6th, 2007
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
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 firstname.lastname@example.org, or
publicly at the Cat language discussion group at Google ( http://groups.google.com/group/catlanguage ).
The Cat Programming Language by