Understanding Stack-Based Programming in Chef

Introduction: A Different Way to Think About Code

If you’re coming from popular programming languages like JavaScript, Python, Java, or C#, you’re accustomed to working with variables, objects, and explicit control flow. You write code that looks like this:

let sum = 0;
for (let i = 1; i <= 10; i++) {
    sum = sum + i;
}
console.log(sum);

This imperative style uses named variables (sum, i) that you can read and write at any time. The flow is explicit and straightforward.

Stack-based languages like Chef, Forth, and PostScript take a fundamentally different approach. Instead of named variables, they use a stack - a last-in-first-out (LIFO) data structure where values are pushed on top and popped from the top. All operations work with values on the stack, and there are no traditional variable names in the execution model.

Think of it like a spring-loaded plate dispenser in a cafeteria: you can only add plates to the top (push) or take plates from the top (pop). You can’t reach into the middle without first removing the plates above.

This might seem limiting at first, but stack-based languages are elegantly simple and force you to think about the flow of data rather than the state of variables. This is precisely what makes Chef such a fascinating esoteric language - it wraps this low-level paradigm in the whimsical disguise of cooking recipes.

The Stack Concept in Chef: Mixing Bowls

In Chef, the stack is called a mixing bowl. Just like in real cooking, you add ingredients to a mixing bowl in a specific order, and later you might retrieve them, combine them, or pour them out.

Basic Stack Operations

Let’s compare how you’d work with values in JavaScript versus Chef:

JavaScript (imperative with variables):

let eggs = 3;
let flour = 2;
let result = eggs + flour;
console.log(result); // 5

Chef (stack-based with mixing bowl):

Ingredients.
3 eggs
2 cups flour

Method.
Put eggs into mixing bowl.
Put flour into mixing bowl.
Add eggs into mixing bowl.
Pour contents of the mixing bowl into the baking dish.

What’s happening here?

  1. Put eggs into mixing bowl - Pushes the value 3 onto the stack
    • Stack: [3]
  2. Put flour into mixing bowl - Pushes the value 2 onto the stack
    • Stack: [3, 2] (top is on the right)
  3. Add eggs into mixing bowl - Pops the top value (2), adds it to eggs (3), pushes the result (5)
    • Stack: [5]
  4. Pour contents… - Outputs the stack contents

Notice how we never explicitly say “result = eggs + flour”. Instead, we manipulate the order and contents of the stack, and the operations work with whatever is currently on top.

Understanding Stack Order: LIFO in Action

The Last-In-First-Out (LIFO) nature of stacks is crucial to understanding Chef:

Ingredients.
1 cup sugar
2 teaspoons salt
3 g butter

Method.
Put sugar into mixing bowl.
Put salt into mixing bowl.
Put butter into mixing bowl.

After these operations, your stack looks like:

[1, 2, 3]
 ↑     ↑
first  top (most recent)

If you now Fold butter into mixing bowl, it removes butter (3) from the top and discards it:

[1, 2]
 ↑  ↑
first top

If you Add salt into mixing bowl, it pops the top value (2), adds it to salt’s original value (2), giving 4, and pushes the result:

[1, 4]
 ↑  ↑
first top

This order matters immensely. In imperative languages, you can access variables in any order. In stack-based languages, you must carefully orchestrate the order of operations.

Working with the Stack: Common Patterns

Pattern 1: Simple Arithmetic

Let’s calculate (5 + 3) * 2 in Chef:

Ingredients.
5 g chocolate
3 cups sugar
2 teaspoons vanilla

Method.
Put chocolate into mixing bowl.
Put sugar into mixing bowl.
Add chocolate into mixing bowl.
Put vanilla into mixing bowl.
Combine vanilla into mixing bowl.

Step-by-step execution:

  1. Put chocolate: [5]
  2. Put sugar: [5, 3]
  3. Add chocolate: pops 3, adds to 5, pushes 8 → [8]
  4. Put vanilla: [8, 2]
  5. Combine vanilla: pops 2, pops 8, multiplies (8*2=16), pushes 16 → [16]

The stack now contains 16, which is our result.

Pattern 2: Using Fold to Remove Values

Sometimes you need to manipulate what’s on the stack without using a value:

Ingredients.
10 g ingredient-a
20 g ingredient-b
30 g ingredient-c

Method.
Put ingredient-a into mixing bowl.
Put ingredient-b into mixing bowl.
Put ingredient-c into mixing bowl.
Fold ingredient-c into mixing bowl.

Result: [10, 20] - we’ve removed the 30 from the top.

The Fold operation is like saying “take the top item off the stack and put it back into the ingredient container” - effectively a pop operation.

Pattern 3: Stack Manipulation for Complex Logic

Suppose you want to keep only the smaller of two values:

Ingredients.
15 ml milk
10 ml cream

Method.
Put milk into mixing bowl.
Put cream into mixing bowl.
Fold cream into mixing bowl.
Put cream into mixing bowl.

This creates: [15, 10]

While Chef doesn’t have explicit conditionals like if (a < b), you can use auxiliary recipes (subroutines) and loops to build complex logic through stack manipulation.

Looping in Chef: The “Verb until Verbed” Pattern

Loops in Chef are unique and creative. Instead of for or while, Chef uses cooking metaphors:

Method.
Stir the mixture for 5 minutes.
Fold in the chocolate.
Mix until mixed.

The pattern “Verb until verbed” creates a loop. Chef decrements an ingredient and repeats instructions until that ingredient reaches zero.

Example: Countdown from 5

Ingredients.
5 potatoes

Method.
Put potatoes into mixing bowl.
Chop potatoes.
Serve with countdown.

Countdown.
Verb the potatoes until chopped.
Fold potatoes into mixing bowl.
Put potatoes into mixing bowl.
Chop potatoes.

How it works:

  1. Verb the potatoes until chopped - Marks the start of the loop. The loop will decrement potatoes and repeat until it reaches 0.
  2. Inside the loop:
    • Fold potatoes (remove from stack)
    • Put potatoes back (add current value to stack)
    • Chop potatoes (decrement the ingredient)

Each iteration puts the current value of potatoes onto the stack, so you end up with:

[5, 4, 3, 2, 1]

This is how you generate sequences or repeat operations a specific number of times.

The Power of Loop Ingredients

The loop construct uses an ingredient as a counter. This is different from languages with explicit loop counters:

JavaScript:

for (let i = 5; i > 0; i--) {
    console.log(i);
}

Chef:

Ingredients.
5 counter

Method.
Loop the counter until looped.
Put counter into mixing bowl.
Break the counter.

Serves 1.

The “Loop… until looped” pattern decrements counter automatically. You don’t explicitly write counter--; the loop mechanism handles it.

Practical Example: Computing Fibonacci Numbers

Let’s see a more complex example that uses stack manipulation and loops to compute Fibonacci numbers:

Fibonacci Numbers with Caramel Sauce.

Ingredients.
100 g butter
1 cup sugar

Method.
Put butter into mixing bowl.
Put sugar into mixing bowl.
Verb the sugar until verbed.
Fold sugar into mixing bowl.
Put sugar into mixing bowl.
Put butter into mixing bowl.
Fold butter into mixing bowl.
Combine sugar into mixing bowl.
Put sugar into mixing bowl.
Verb the sugar.

Serves 1.

This code:

  1. Initializes the stack with starting Fibonacci values (0 and 1)
  2. Loops based on the sugar counter
  3. In each iteration:
    • Duplicates and combines values on the stack
    • Generates the next Fibonacci number
    • Decrements the counter

The stack manipulation here is intricate - you’re swapping, duplicating, and combining values to maintain state across loop iterations without named variables.

Multiple Mixing Bowls: Working with Multiple Stacks

Chef supports multiple mixing bowls (stacks), which you can think of as separate data structures:

Ingredients.
5 eggs
3 cups flour

Method.
Put eggs into 1st mixing bowl.
Put flour into 2nd mixing bowl.

Now you have:

You can transfer values between bowls, use one for temporary storage, or organize different parts of your computation. This is similar to having multiple stacks in Forth or using different registers in assembly language.

Why Learn Stack-Based Programming?

Understanding stack-based languages like Chef teaches you:

  1. Data flow thinking - You learn to think about how data moves through your program, not just what state it’s in.

  2. Low-level concepts - Stacks are fundamental to computing. Understanding them helps you grasp how function calls work, how assembly language operates, and how compilers generate code.

  3. Problem decomposition - Without named variables, you must carefully plan the order of operations, leading to deeper algorithmic thinking.

  4. Historical context - Stack machines influenced early computing and continue to power technologies like the Java Virtual Machine (JVM) and PostScript.

  5. Creativity in constraints - Chef forces you to express complex ideas within strict syntactic and semantic constraints, making you a more versatile programmer.

Conclusion: Give Chef a Try

Stack-based programming might feel awkward at first, especially when disguised as cooking recipes. But that’s precisely what makes Chef such a rewarding challenge. It’s an esoteric language that combines the playfulness of recipe-writing with the rigor of stack manipulation.

As you experiment with Chef, you’ll find yourself thinking differently about program flow. You’ll appreciate the elegance of PostScript, understand why Forth developers love their language, and gain insight into how CPUs execute instructions at the hardware level.

Ready to start cooking? Here’s how:

# Install the interpreter
cargo install --git https://github.com/y-a-v-a/cheffers

# Write a simple recipe (hello.chef)
# Then run it:
cheffers hello.chef

Start simple:

  1. Try pushing and popping values from the mixing bowl
  2. Experiment with arithmetic operations
  3. Build a simple loop
  4. Gradually work up to more complex recipes

Remember: in Chef, you’re not just writing code - you’re crafting a culinary masterpiece that happens to compute. Every “Put,” “Fold,” and “Combine” is a carefully choreographed step in your algorithmic recipe.

Happy cooking, and may your mixing bowls always be properly stacked!

Further Resources