Kitten

Tutorial

Welcome to the Kitten tutorial! This is the best way to start learning Kitten, a little functional stack-based programming language. Actually, it’s pretty much the only way, because Kitten is young. But it has a lot of big ideas!

This tutorial tries not to make too many assumptions about your existing knowledge, and it has lots of links to outside learning materials so you don’t ever get lost. However, you will definitely find learning Kitten easier if you’ve programmed before.

What is Kitten?

Kitten is a statically typed stack-based functional programming language designed to be simple and fast. (That’s what the website says.) A functional language is one that speaks declaratively about the solution to a problem, with an emphasis on, you guessed it, functions. Three important properties of functional languages are:

Evaluation
Programs operate by the evaluation of expressions, rather than the execution of orders.
Immutability
Values, once created, don’t change.
Purity
If a function is called multiple times with the same parameters, it must produce the same result, just like in math.

A stack-based language is one where most operations are done on a stack of values. Functions take their inputs from the stack, do some computation, and return their results on the same stack. An important feature of stack-based languages is their notation for writing expressions. You’re probably accustomed to seeing math expressions like this:

(2 + 3) × (42 − 12)

And most programming languages have similar notation inspired by mathematics, usually with a more limited character set for convenience of entering at a keyboard.

(2 + 3) * (42 - 12)

But some programming languages use other notations; Lisp, for example, uses prefix notation, also known as Polish notation, which looks like this:

(* (+ 2 3) (- 42 12))

You can read this as “the product (*) of the sum (+) of 2 and 3, and the difference (-) of 42 and 12”. Stack languages typically use postfix notation, also called reverse Polish notation or RPN, where the operators go in the opposite order:

2 3 + 42 12 - *

You can read this as “Take 2 and 3 and add them (+). Take 42 and 12 and subtract them (-). Then take the results and multiply them (*)”. Whereas the prefix version sounds like a description of the expression, the postfix version sounds more like a description of the steps you take to compute it.

Programming languages that describe computations in terms of actions like this are called imperative languages. Do this, then do that. The majority of languages in popular use today are imperative, such as Java and C++. Though languages often include ideas from both imperative and functional programming, the two paradigms are often considered opposite in spirit and suited to solving different kinds of problems.

For the sake of familiarity, and to improve the ability to share code with other languages, Kitten uses infix for operators and postfix for function calls. However, you can use operators in the core postfix form if you choose, and we will see later how this can be very useful for manipulating code.

(2 + 3) * (42 - 12)

2 3 (+) 42 12 (-) (*)

Hold up!

I mentioned earlier that Kitten is both functional and stack-based. These two seemingly opposing features are reconciled by a simple notion: effects. The only side effect of the + operator is to pop two values from the stack and push their sum, and it always produces the same output given the same inputs—it is a pure function from one stack state to another.

So in fact, we can reason about these imperative stack procedures as pure mathematical functions, just like in a functional programming language. This combination of imperative style and functional reasoning is called concatenative programming, and is a powerful way of thinking about programs.

Enough jibber jabber! Let’s write some code!

Okay! First you need to download and install Kitten for your platform.

Note: you cannot actually download and install Kitten yet. Follow the README instructions on how to build Kitten for your platform.

Open up your terminal and type kitten. Kitten will respond with a welcome message and a prompt:

Welcome to Kitten!
Type ':help' for help or ':quit' to quit.
>>> 

Here is where you can type code and see its results. Let’s have Kitten say something.

>>> "meow" say
meow

Adorable! What happens when we enter a number?

>>> 1
1

So the result of evaluating the expression 1 is just the value 1. What happens when we enter another number?

>>> 2
1
2

Interesting. Kitten remembered the last value we entered on the stack, and is displaying the whole stack between prompts, in the same order we entered it. Let’s add these numbers together.

>>> (+)
3

The (+) function took the two integers we had placed on the stack, added them, and pushed the result. We could also have used + as an infix operator, of course, and this is what we’ll do much of the time, but it’s important to understand that the stack is available.

>>> 1 + 2
3

We can also enter multiple values at once…

>>> 4 5
3
4
5

…and perform multiple operations at once.

>>> (+) (*)  // add 4 and 5, then multiply by 3
27

The drop function lets us drop a single value from the stack. In interactive mode, you can also use the :clear command to clear the stack entirely.

Vectors and Functions

Kitten has a built-in vector datatype. Vector literals are surrounded by square brackets [] and have comma-separated elements.

>>> [1, 2, 3]
[1,2,3]

We can duplicate a value with the dup function.

>>> dup
[1,2,3]
[1,2,3]

The map function lets us apply a function to each element of a vector, returning a vector of the results. We can create a function by simply surrounding some code with curly braces {}.

>>> {2 (*)}  // multiply by two
[1,2,3]
[1,2,3]
<function>

>>> map
[1,2,3]
[2,4,6]

{2 (*)} is a function which takes an integer on the stack and multiplies it by 2. You can think of it as the * operator, with 2 pre-bound as the second argument. We can give this function a name using define, so we don’t have to repeat its implementation if we want to use it again.

>>> define twice (int -> int) { 2 (*) }

Here we see a type signature.