Code Along
A code-along is a story about coding in which you are encouraged to “code up” all the examples in the story. In a code-along you shouldnot cut-and-paste.
In this code-along we will take a look at how to create a geometric artifact in a decompositional fashion (also known as top-down development. In top-down development, a problem (e.g., the construction of a LEGO artifact) is solved by breaking the problem into smaller and smaller pieces and then combining those pieces. Up till now, we have created geometric artifacts in a compositional fashion (also know as bottom-up development). In bottom-up development a problem (e.g., building a LEGO artifact) is solved by building small pieces and then combining them to form larger and larger pieces. For example, to create an 8×8 chessboard, we start by declaring a function called (say) chessboard1 to create a 2×2 chessboard. We then declare another function called chessboard2 that calls chessboard1 four times. This results in the creation of a 4×4 chessboard. We then declare another function called chessboard3 that calls chessboard2 four times. The result is an 8×8 chessboard.
On a more abstract level, the compositional algorithms we have studied create a chessboard through successive approximation. With each new function declaration the artifact created becomes more like an 8×8 chessboard. Specifically, the artifact created by a call tochessboard2 is more similar to an 8×8 chessboard than the artifact created by a call to chessboard1. Similarly, the artifact created by a call to chessboard3 is more similar to (actually identical to) an 8×8 chessboard than the artifact created by a call to chessboard1. In this case, our sequence of approximation functions, chessboard1,chessboard2, and chessboard3 can be characterized as good, better, best.
In the code-along examples that follow, we will look at how to use a geometric algorithm to create an artifact through a sequence of decompositional approximations. The sequence of approximation functions we will create will be in the reverse order to the sequence described in the previous paragraph. Specifically, our first approximation will create part of the detail of our largest artifact (a coarse-grained approximation of our artifact). The next approximation will add some additional (e.g., medium-grained) detail to our artifact, and so on.
It should be noted that from a mathematical standpoint, constructing a LEGO artifact using a compositional geometric algorithm is exactly the same as constructing that same artifact using a decompositional geometric algorithm. The difference in the two approaches is how they help us think. They say you point from where you stand. In a compositional approach, you stand at the bottom and “point up”. That is, you strive to see “how the pieces make up the whole”. In a decompositional approach, you stand at the top and “point down”. That is, you strive to see “how the whole is made up of pieces”.
Code Along Example 1
In this example, we have a first approximation to a LEGO artifact having some similarities to a chessboard. Essentially, the artifact we want to create is a chessboard where larger squares form borders around smaller squares. We will create this artifact through a series of successive approximations in a top-down (i.e., decompositional) fashion. Each function we create will use a put2D function call to create something (e.g., leave a “bread crumb”). By analogy, our series of successive approximations will create a trail of bread crumbs of finer and finer granularity. The final result we will be artifact we had in mind.
In our first approximation, the function squares4 creates a 64×64 black square. This is accomplished in the body of squares4 by the function call put2D (side,side) b1 (x,z) (our coarse-grained bread crumb). After this function call, there are four calls to the function squares3. The function squares3 has a body consisting of the unit value (). In its current form, calling squares3 has absolute no effect.
Functions that do nothing, like squares3, are called stubs. In the design of a program, a stub serves as a placeholder for “details to be filled in later”. Another way of saying this is that a stub serves as a temporary substitute for code that has yet to be developed. It is worth noting that in the first two calls to squares3 the brick arguments are in the order b2 b1 while in the second two calls to squares3 the brick arguments are in the order b1 b2.
From the standpoint of coding, note that the arithmetic expressions side div 2 – 2 and side div 2+1 occur multiple times. This is considered to be bad form in programming. It is redundant and also inefficient since the expressions will get evaluated over and over. In a good program, every computational idea in the program (e.g., an arithmetic expression) occurs exactly once.
open Level_3;
fun squares3 b1 b2 side (x,z) = ();
fun squares4 b1 b2 side (x,z) =
(
put2D (side,side) b1 (x,z);
squares3 b2 b1 (side div 2 - 2)
(x+1,z+side div 2+1);
squares3 b2 b1 (side div 2 - 2)
(x+side div 2+1,z+1);
squares3 b1 b2 (side div 2 - 2)
(x+1,z+1);
squares3 b1 b2 (side div 2 - 2)
(x+side div 2+1,z+side div 2+1)
);
build2D(64,64);
squares4 BLACK WHITE 64 (0,0) ;
show2D "Squares";
Code Along Example 2
In this example, a let-block is used to assign the values of arithmetic expressions to variables. Technically speaking, there is still some redundancy in the code. In particular, the expressions x+1 andz+1 occur multiple times. Additional val-declarations can be introduced to remove this redundancy. However, it is not clear that this would improve the readability of the program. In general, when given a choice it is better to trade redundancy for readability, though it is not often to encounter situations where such trade-offs need to be made. Note that in a good program an adjustment to an arithmetic expression (or any other computational idea) need only be made at one location.
open Level_3;
fun squares3 b1 b2 side (x,z) = ();
fun squares4 b1 b2 side (x,z) =
let
val halfSide = side div 2
val nextSide = halfSide - 2
val offset = halfSide + 1
in
put2D (side,side) b1 (x,z);
squares3 b2 b1 nextSide (x+1 ,z+offset);
squares3 b2 b1 nextSide (x+offset,z+1 );
squares3 b1 b2 nextSide (x+1 ,z+1 );
squares3 b1 b2 nextSide (x+offset,z+offset)
end;
build2D(64,64);
squares4 BLACK WHITE 64 (0,0) ;
show2D "Squares";
Code Along Example 3
In this example, the details of body of the function squares3 is filled in. Notice that in the body of squares3 there are four calls to the function squares2 which is a stub. We leave it to the reader to rewrite the bodies of the functions squares4 and squares3 so that redundant computations are removed.
Note that in the function squares3, the function call put2D (side,side) b1 (x,z) denotes the “crumb” that is left behind. Also note that the image next to the declaration of the function squares3 does not show the artifact that squares3 creates, but rather how crumbs created by calls to squares3 affect the crumb created by squares4.
open Level_3;
fun squares2 b1 b2 side (x,z) = ();
fun squares3 b1 b2 side (x,z) =
(
put2D (side,side) b1 (x,z);
squares2 b2 b1 (side div 2 - 2)
(x+1,z+side div 2+1);
squares2 b2 b1 (side div 2 - 2)
(x+side div 2+1,z+1);
squares2 b1 b2 (side div 2 - 2)
(x+1,z+1);
squares2 b1 b2 (side div 2 - 2)
(x+side div 2+1,z+side div 2+1)
);
fun squares4 b1 b2 side (x,z) =
(
put2D (side,side) b1 (x,z);
squares3 b2 b1 (side div 2 - 2)
(x+1,z+side div 2+1);
squares3 b2 b1 (side div 2 - 2)
(x+side div 2+1,z+1);
squares3 b1 b2 (side div 2 - 2)
(x+1,z+1);
squares3 b1 b2 (side div 2 - 2)
(x+side div 2+1,z+side div 2+1)
);
build2D(64,64);
squares4 BLACK WHITE 64 (0,0) ;
show2D "Squares";
Code Along Example 4
In this example, the details of body of the function squares2 is filled in. Notice that in the body of squares2 there are four calls to the function squares1 which is a stub. We leave it to the reader to rewrite the bodies of the functions squares4, squares3, and squares2 so that redundant computations are removed.
Note that in the function squares2, the function call put2D (side,side) b1 (x,z) denotes the “crumb” that is left behind. Also note that the image next to the declaration of the function squares2 does not show the artifact that squares2 creates, but rather how crumbs created by calls to squares2 affect the crumbs created by squares3 which in turn affect the crumb created by squares4.
open Level_3;
fun squares1 b1 b2 side (x,z) = ();
fun squares2 b1 b2 side (x,z) =
(
put2D (side,side) b1 (x,z);
squares1 b2 b1 (side div 2 - 2)
(x+1,z+side div 2+1);
squares1 b2 b1 (side div 2 - 2)
(x+side div 2+1,z+1);
squares1 b1 b2 (side div 2 - 2)
(x+1,z+1);
squares1 b1 b2 (side div 2 - 2)
(x+side div 2+1,z+side div 2+1)
);
fun squares3 b1 b2 side (x,z) =
(
put2D (side,side) b1 (x,z);
squares2 b2 b1 (side div 2 - 2)
(x+1,z+side div 2+1);
squares2 b2 b1 (side div 2 - 2)
(x+side div 2+1,z+1);
squares2 b1 b2 (side div 2 - 2)
(x+1,z+1);
squares2 b1 b2 (side div 2 - 2)
(x+side div 2+1,z+side div 2+1)
);
fun squares4 b1 b2 side (x,z) =
(
put2D (side,side) b1 (x,z);
squares3 b2 b1 (side div 2 - 2)
(x+1,z+side div 2+1);
squares3 b2 b1 (side div 2 - 2)
(x+side div 2+1,z+1);
squares3 b1 b2 (side div 2 - 2)
(x+1,z+1);
squares3 b1 b2 (side div 2 - 2)
(x+side div 2+1,z+side div 2+1)
);
build2D(64,64);
squares4 BLACK WHITE 64 (0,0) ;
show2D "Squares";
Code Along Example 5
In this example, the details of body of the function squares1 is filled in. Notice that in the body of squares1 there are four calls to the function squares0 which is a stub. We leave it to the reader to rewrite the bodies of the functions squares4, squares3, squares2, and squares1 so that redundant computations are removed.
Note that in the function squares1, the function call put2D (side,side) b1 (x,z) denotes the “crumb” that is left behind. Also note that the image next to the declaration of the function squares1 does not show the artifact that squares1 creates, but rather how crumbs created by calls to squares1 affect the crumbs created by squares2 which in turn affect the crumbs created by squares3 which in turn affect the crumb created by squares4.
open Level_3;
fun squares0 b1 b2 side (x,z) = ();
fun squares1 b1 b2 side (x,z) =
(
put2D (side,side) b1 (x,z);
squares0 b2 b1 (side div 2 - 2)
(x+1,z+side div 2+1);
squares0 b2 b1 (side div 2 - 2)
(x+side div 2+1,z+1);
squares0 b1 b2 (side div 2 - 2)
(x+1,z+1);
squares0 b1 b2 (side div 2 - 2)
(x+side div 2+1,z+side div 2+1)
);
fun squares2 b1 b2 side (x,z) =
(
put2D (side,side) b1 (x,z);
squares1 b2 b1 (side div 2 - 2)
(x+1,z+side div 2+1);
squares1 b2 b1 (side div 2 - 2)
(x+side div 2+1,z+1);
squares1 b1 b2 (side div 2 - 2)
(x+1,z+1);
squares1 b1 b2 (side div 2 - 2)
(x+side div 2+1,z+side div 2+1)
);
fun squares3 b1 b2 side (x,z) =
(
put2D (side,side) b1 (x,z);
squares2 b2 b1 (side div 2 - 2)
(x+1,z+side div 2+1);
squares2 b2 b1 (side div 2 - 2)
(x+side div 2+1,z+1);
squares2 b1 b2 (side div 2 - 2)
(x+1,z+1);
squares2 b1 b2 (side div 2 - 2)
(x+side div 2+1,z+side div 2+1)
);
fun squares4 b1 b2 side (x,z) =
(
put2D (side,side) b1 (x,z);
squares3 b2 b1 (side div 2 - 2)
(x+1,z+side div 2+1);
squares3 b2 b1 (side div 2 - 2)
(x+side div 2+1,z+1);
squares3 b1 b2 (side div 2 - 2)
(x+1,z+1);
squares3 b1 b2 (side div 2 - 2)
(x+side div 2+1,z+side div 2+1)
);
build2D(64,64);
squares4 BLACK WHITE 64 (0,0) ;
show2D "Squares";
