Self-Referential Data — Recursive Data

Student: Professor, I want to get the hard stuff. The real stuff about programming, the can’t-fake-it, no-nonsense big ideas. Stuff like recursion. My friends in upper division classes are always talking about that.

Prof: Good news! We’ve done recursion already.

Student: What?

Prof: We wrote our first recursive methods the last time we talked. And we’ve been making recursive data since we composed the French flag.

Student: How do you mean? Recursion is the hardest topic in CSE11. That’s what everyone says.

Prof: Then you’re doing great, as long as you understood our last conversations!

Student: Which parts?

Prof: Well, let’s bring up an example again and talk through a definition.

record ImageData(String keywords, String fileType, int width, int height, int sizeKb) {}

interface ImageQuery {
  boolean matches(ImageData img);
}

record HasKeyword(String word) implements ImageQuery { … }

record And(ImageQuery left, ImageQuery right) implements ImageQuery {
  public boolean matches(ImageData img) {
    return left.matches(img) && right.matches(img);
  }
}

record Or(ImageQuery left, ImageQuery right) implements ImageQuery {
  public boolean matches(ImageData img) {
    return left.matches(img) || right.matches(img);
  }
}

ImageData img = new ImageData("cat sleeping", "png", 640, 480, 300);
ImageQuery cat = new HasKeyword("cat");
ImageQuery png = new HasExtension("png");
ImageQuery jpg = new HasExtension("jpg");
ImageQuery light = new SmallerThanKb(500);
ImageQuery pngOrJpg = new Or(png, jpg);
ImageQuery catPic = new And(cat, pngOrJpg);
ImageQuery query = new And(catPic, light);
boolean found = query.matches(img);

Prof: So, in terms of definitions:

The And record is a recursive datatype: it both implements ImageQuery and it has a field of type ImageQuery. That means a field of an And record can itself be an instance of And.
The matches method is a recursive method: when it calls matches on its fields, it may be calling the exact method it is in. That is, two stack frames right next to each other, each for the exact same method of the exact same class, just different receivers.

These are the two important definitions of recursion in the object-oriented programs we will write.

Student: Huh. OK. So the memory trace would have multiple stack frames for the matches method on And at the same time?

Prof: Right, that’s the idea:

Names (the stack), over time →

top level

img = @1001

cat = @1002

png = @1003

jpg = @1004

light = @1005

pngOrJpg = @1006

catPic = @1007

query = @1008

found = true

query.matches(img) on @1008

img = @1001

returns true

left.matches(img) on @1007

img = @1001

returns true

left.matches(img) on @1002

img = @1001

returns true

right.matches(img) on @1006

img = @1001

returns true

left.matches(img) on @1003

img = @1001

returns true

right.matches(img) on @1005

img = @1001

returns true

Heap

@1001: ImageData[keywords=cat sleeping, fileType=png, width=640, height=480, sizeKb=300]

@1002: HasKeyword[word=cat]

@1003: HasExtension[ext=png]

@1004: HasExtension[ext=jpg]

@1005: SmallerThanKb[limitKb=500]

@1006: Or[left=@1003, right=@1004]

@1007: And[left=@1002, right=@1006]

@1008: And[left=@1007, right=@1005]

Student: Hm, ok so recursive data is when a record could have other instances of the same record in its fields? And recursive methods are when a method can call itself?

Prof: That’s right.

Practice

Beside from the Pict library is recursive data too: its left and right are Picts, and its width method calls width on both of them.

record Beside(Pict left, Pict right) implements Pict {
  public int width() { return left.width() + right.width(); }
  // ...
}

Pict dot = new Circle(10, "red");
Pict box = new Rect(30, 20, "blue");
Pict pair = new Beside(dot, box);
Pict row = new Beside(pair, dot);
int w = row.width();

These are the calls of row.width() over time, with the receivers left out.

Names (the stack), over time →

top level

dot = @1001

box = @1002

pair = @1003

row = @1004

w = 70

row.width() on @1004

returns 70

left.width() on ???

returns 50

left.width() on ???

returns 20

right.width() on ???

returns 30

right.width() on ???

returns 20

Heap

@1001: Circle[radius=10, color=red]

@1002: Rect[width=30, height=20, color=blue]

@1003: Beside[left=@1001, right=@1002]

@1004: Beside[left=@1003, right=@1001]

Fill in the receiver of each call.

The call that returns 50 runs on .
The call that returns 30 runs on .
Both calls that return 20 run on .

Which two calls are next to each other on the stack, running the same method of the same record?

row.width() and the this.left.width() that returns 50
Both run width from Beside: one on @1004, and the one it calls on @1003.
the this.left.width() that returns 20 and the this.right.width() that returns 30
@1001 is a Circle and @1002 is a Rect, so these are two different width methods, and neither one called the other.
the two calls that return 20
These run on the same object, @1001, but neither one called the other. They are never on the stack at the same time.