## 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 should**not** 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 to*chessboard2* 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* and*z+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";
```