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: Longer programs work the same way. Consider 2 3 + 5 *: 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·V0.16 + 0.4275·T·V0.16
This program expects to find T and V on top of the stack:
    T V
The program 0.16 pow computes x0.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. -----