[plt-scheme] 2htdp/image

From: Stephen Bloch (sbloch at adelphi.edu)
Date: Wed Nov 18 11:15:31 EST 2009

On Nov 18, 2009, at 10:31 AM, Matthias Felleisen wrote:

> 1. Why do you think that a long list of image ops/tree nodes is  
> more expensive than a bitmap? That's minor I think. I'd measure  
> this first.

I didn't say "more expensive than a bitmap".

Suppose you've got an animation whose model is (or contains) an  
image, initially a star or a triangle or a bitmap copied from the  
Web, and which has a tick handler that rotates the image by a certain  
number of degrees.

One implementation: the tick handler adds a "rotate" node to the tree  
every time, and the redraw handler interprets the whole tree to  
flatten the image into a bitmap that can be displayed.

Another implementation: the tick handler tries to add a "rotate" node  
(a kind of matrix multiplication) to the tree, but realizes that the  
previous top node of the tree was a matrix multiplication, so it  
composes the matrix multiplications and collapses the two nodes into  
one.  The redraw handler, in flattening the image into a bitmap that  
can be displayed, only has to apply that single matrix to the  
underlying bitmap (or other primitive).

My hypothesis is that the former implementation is significantly  
slower (especially as the animation keeps running for a few minutes)  
than the latter.  Yes, that hypothesis should be tested empirically,  
but it seems very plausible.

> 2. Inexactness: Perhaps I am misunderstanding but here is what I  
> think Robby is saying and what you are saying:
> Robby: there are exact and inexact images just like their are exact  
> and inexact numbers. His operations preserve exactness as much as  
> possible, just like numeric operations. (In a sense his inexactness  
> is of course derived from the inexactness of the numbers associated  
> with images.)
> Stephen: You are saying, deal with all images as if they were  
> inexacts. That simplifies life and we don't need to worry about  
> comparisons.

Yes, I'm saying deal with all images as if they were inexacts  
(although we still need comparisons).  I certainly see the appeal in  
the notion of "exact" vs. "inexact" images, but I fear that the  
distinction might cost too much in efficiency.

>  The problem that I see is testing. For testing rendering  
> functions, I'd like to exercise all my code and get an idea that  
> they work properly. I may not test it on 10,000 shots and 3 UFOs  
> but on 2 shots and 1 UFO and that gives me some confidence that it  
> will draw things properly when I run the program (as opposed to  
> testing it).
> I don't see how I can do this without comparisons, and I really  
> dislike having to warn kids about =-comparisons for numbers on day  
> 1. Day 38 is fine. So for images I'd like some 'exact' equality and  
> perhaps we need an 'inexact' quality (=~) too.

I agree with having one equality test that compares the tree  
representations of two images, and another that compares the bitmap  
representations.  The question is whether even the former can  
reasonably be called "exact".  If some of the tree nodes contain  
matrices with inexact entries, obviously it can't.  If a user ever  
calls "rotate" with an inexact angle, then again it obviously can't  
(even under the all-trees-all-the-time implementation).

I would have check-expect, by default, compare images as bitmaps, so  
two images will compare as equal iff they would appear the same on  
the screen.  That should be easy for beginning students to understand.

> Does anyone know if others have turned images into first-class  
> values and what problems they encountered and how they solved them?

Surely somebody has.  Although the great majority of graphics  
research has been directed towards efficiently displaying things on a  
physical screen, which doesn't require exactness.

BTW, there might be something to be said for an image representation  
which is primarily a tree, but which "caches" a bitmap whenever it is  
flattened (whether for comparison-as-bitmaps or for display), so the  
next time the same image is compared or displayed, it doesn't have to  
be re-flattened.  Or to be more Schemish, the bitmap representation  
is a lazy function of the tree representation.  I would do this  
caching only at the top level of an image tree, not at every node, to  
avoid egregious memory-hogging.

Stephen Bloch
sbloch at adelphi.edu

Posted on the users mailing list.