stz

the fibonacci sequence

the fibonacci sequence
Photo by David Clode / Unsplash

This isn't entirely a post about fibonacci. But it's a good example to work off of to solve one of the more vexing and annoying aspects of manual memory management. Re-running code with state in a reusable fashion.

Let's get our baseline:

[self next-fibonacci-from: a and: b]
  [Program, UnsignedInteger, UnsignedInteger
   -> UnsignedInteger, UnsignedInteger |
    b, a + b].

This utilises tuples in a way that STZ doesn't currently support but we're not going to stay here for long so let's move on to what we really want. We really want a 'generator' pattern where we can send 'next' to the thing over and over again and get the next number in the sequence.

For that we need state. The Smalltalk way of doing this is to capture the state:

[fibonacci-sequence]
  [-> (-> Integer) |
  a := b := 1.
  [next := a. a := b. b := next + a. next]].

seq := fibonacci-sequence.
(1 to: 100) -> seq -> stdout.

But we don't have garbage collection here. Putting a and b on the stack means every time we call seq we're creating and destroying those frames. There's no magic capture copy in STZ.

The canonical way to do this is to create a structure and pass that to the method:

fib-state :: {a, b: Integer = 1}.
[self next]
  [:fib-state -> Integer |
    next := a. a := b. b := next + a. next].

fib-seq: fib-state.
(1 to: 100) -> fib-seq -> stdout.

Wait a second. That's it? that's all we needed to do? ...yep. In many ways this is more object oriented than using block variable captures. For one, there's an object. For two it solves the memory splatting problem. And for three it's still on the stack so we're not really doing anything with the heap at all.

This might seem very obvious if you've not had your head in the garbage collected world for most of your professional programming life. Sometimes it helps to go back to the simple problems and re-evaluate them.

I'm pleased with the syntax. It's succinct and clear to me what each bit is. The only magic is :fib-state which is an anonymous parameter; because we're accessing its members directly. The first parameter (and may be this will become 'the first anonymous parameter') becomes bound as the receiverless sender. Otherwise known as 'self' but that label isn't bound in this context (hence - anonymous).

Read more