TITLE: Getting a Sense of Joy Style Through the Stack
AUTHOR: Eugene Wallingford
DATE: July 18, 2016 12:47 PM
DESC:
-----
BODY:
Last time,
I wrote about returning to the programming language Joy,
without giving too many details of the language or its
style. Today, I'll talk a bit more what it means to say
that Joy is a "stack language" and show how I sometimes
think about the stack as I am writing a simple program.
The evolution of the stack is helping me to think about
how data types work in this language and to get a sense
of why languages such as Joy are called
concatenative.
Racket and other Lisp-like languages use prefix notation,
unlike the more common infix notation we use in C, Java,
and most mainstream languages. A third alternative is
postfix notation, in which operators follow their
operands. For example, this postfix expression is a
valid Joy program:
2 3 +
computes 2 + 3.
Postfix expressions are programs in a stack-based language.
They correspond to a postfix traversal of a program tree.
Where is the stack? It is used to interpret the program:
- 2 is pushed onto the stack.
- 3 is pushed onto the stack.
- + is an operator. An operator pops its
arguments from the stack, computes a result, and
pushes the result on to the stack. + is a
two-argument function, so it pops two arguments from
the stack, computes their sum, and pushes the 5
back onto the stack.
Longer programs work the same way. Consider 2 3 +
5 *:
- 2 is pushed onto the stack.
- 3 is pushed onto the stack.
- + pops the 2 and the 3, computes a 5, and
pushes it on to the stack.
- 5 is pushed onto the stack.
- * pops the two 5s, computes a 25, and
pushes it on to the stack.
This program is equivalent to 2 + 3 - 5,
er, make that (2 + 3) * 5. As long as we
know the arity of each procedure, postfix notation requires
no rules for the precedence of operators.
The result of the program can be the entire stack or the top
value on the stack. At the end of a program, the stack
could finish with more than one value on it:
2 3 + 5 * 6 3 /
leaves a stack consisting of 25 2.
Adding an operator to the end of that program can return us
to a single-value stack:
2 3 + 5 * 6 3 / -
leaves a stack of one value, 23.
This points out an interesting feature of this style of
programming: we can compose programs simply by
concatenating their source code.
2 * is a program: "double my argument", where
all arguments are read from the stack. If we place it at the
end of 2 3 + 5 * 6 3 / -, we get a new program,
one that computes the value 46.
This gives us our first hint as to why this style is called
concatenative programming.
As I am re-learning Joy's style, I think a lot about the
stack, which holds the partial results of the computation
I am trying to program. I often find myself simulating the
state of stack to help me keep track of what to do next,
whether on paper or in a comment on my code.
As an example, think back to the wind chill problem I discussed
last time:
given the the air temperature T and the wind speed V, compute
the wind chill index
T'.
T' = 35.74 + 0.6215·T - 35.75·V^{0.16} + 0.4275·T·V^{0.16}
This program expects to find T and V on top of the stack:
T V
The program 0.16 pow computes x^{0.16}
for the 'x' on top of the stack, so it leaves the stack in
this state:
T V'
In Joy documentation, the type of a program is often described
with a before/after picture of the stack. The dup2
operator we saw last time is described as:
dup2 :: a b -> a b a b
because it assumes two arbitrary values on top of the stack
and leaves the stack with those values duplicated. In this
fashion, we could describe the program 0.16 pow
using
0.16 pow :: N -> N
It expects a number N to be on top of the stack and leaves
the stack with another number on top.
When I'm using these expressions to help me follow the state
of my program, I sometimes use problem-specific names or
simple modifiers to indicate changes in value or type. For
the wind-chill program, I thought of the type of
0.16 pow as
T V -> T V'
,
because the values on the stack were a temperature and a
velocity-based number.
Applied to this stack, dup2 converts the
stack as
T V' -> T V' T V'
,
because the values on the stack were a temperature and a
velocity-based number.
If we concatenate these two programs and evaluate them
against the original stack, we get:
[ initial stack] T V
0.16 pow -> T V'
dup2 -> T V' T V'
I've been preserving these stack traces in my documentation,
for me and any students who might end up reading my code.
Here is the definition of wind-chill, taken
directly from the source file:
DEFINE wind-chill == 0.16 pow (* -> T V' *)
dup2 (* -> T V' T V' *)
* 0.4275 * (* -> T V' t3 *)
rollup (* -> t3 T V' *)
35.75 * (* -> t3 T t2 *)
swap (* -> t3 t2 T *)
0.6215 * (* -> t3 t2 t1 *)
35.74 (* -> t3 t2 t1 t0 *)
+ swap - +. (* -> T' *)
After the dup2 step, the code alternates
between computing a term of the formula and rearranging
the stack for the next computation.
Notice the role concatenation plays. I can solve each
substep in almost any order, paste the resulting little
programs together, and boom! I have the final solution.
I don't know if this kind of documentation helps anyone
but me, or if I will think it is as useful after I feel
more comfortable in the style. But for now, I find it
quite helpful. I do wonder whether thinking in terms of
stack transformation may be helpful as I prepare to look
into what type theory means for a language like Joy.
We'll see.
I am under no pretense that this is a great Joy program,
even in the context of a relative novice figuring things
out. I'm simply learning, and having fun doing it.
-----