Lazy list s-expression matrix in smalltalk

Question

So I have a class to create in smalltalk called LazyMatrix. The class only has 1 instance variable and cannot be a subclass of anything but Object. The instance variable of LazyMatrix is called block and must be a back. I initialize LazyMatrix like this:

initialize
block:=[nil]

There will be a method for setting values

setRow:column:value:

This method will redefine the block by setting the new block as [#(i j value).[nil]]. Each subsequent call adds an array of 3 to the block, so it expands like [#(i j value).[#(i j value).[nil]]] much like an s-expression or "lazy list".

So I need to access the head of this block (i.e. [#(i j value) ) as well as the tail of this bock (i.e. [#(i j value).[nil]] ). How do I do this in smalltalk? I know calling value on the block will return the tail... now I need to return the head.

Answer 1

Adding an array to your block doesn't get you anywhere. Think in terms of behavior, not about data structures.

I guess your teacher did provide you with the overall idea: given a row and column, answer the associated value; otherwise ask the "tail" for the answer.

That is literally how you would implement it in Smalltalk using a block closure (where the "tail" is the previously set block). Inside the block, put code that does the testing and answering and tail recursion. Do not make a data structure, tail and head are just metaphors to reason about this style of coding.

I just implemented your LazyMatrix in Squeak, it is just a few lines of code. Cute example, indeed. And no arrays or collections involved, at all.

Hint: The key to this puzzle is realizing that every call to setRow:column:value: can create a new block, which is independent of all the previously created blocks.

Answer 2

I think you can go in two ways here. The first one (which I wouldn't recommend) is to model your s-expressions as lists in lambda calculus. You basically use blocks as functions and you are done. Here you can fond an explanation of writing lists using lambda calculus. As an example, in Smalltalk you would write

empty = λfx.x

as

empty := [:f :x | x].

Now, going that road would be basically writing a functional program in an OO language, which I wouldn't do. If you want to use the symbolic approach for lists then you should model it with objects. Have a EmptyList class and a Cons class (Cons would have an element and a list inst var), so that you create a list by doing:

listWithOne := Cons element: 1 list: EmptyList new.

The head and tail methods can be trivially written in the Cons class by just returning the inst var values. You can also define head and tail methods in the EmptyList class, so that now EmptyList and Cons are polymorphic.

Added: Ok, just for fun, an implementation that uses blocks and arrays, functional style:

| empty cons head tail test |
empty := [nil].
cons := [:i :j :value :old | [Array with:i with:j with:value with:old]].
head := [:list | list value ifNotNil: [:v | v copyFrom:1 to:3]].
tail := [:list | list value at: 4].

test := cons value: 1 value: 1 value: 'Hi' value: (cons value: 1 value: 2 value: 'Ho' value: empty).
"Print each one"
head value: test.
head value: (tail value: test).
head value: (tail value: (tail value: test)).

HTH