Code Along – Traversals

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 explore how basic ideas from modular arithmetic can be used to create LEGO artifacts consisting of repeating patterns. More specifically, we will define brick functions whose outputs are controlled by predicates that evaluate to true for all points having attributes satisfying a particular congruence relation.

Consider the program shown below. The function isEven is a predicate that evaluates to true for all (x,z) values whose sum is congruent modulo 2 to 0; otherwise isEven evaluates to false. The function blackWhite is a brick function whose body consists of a conditional expression that evaluates to (i.e., returns) a BLACK brick in cases where isEven(x,z) is true and evaluates to a WHITE brick otherwise. The body of the function chessboard consists of a call to the traverseWithin function which iterates over the points in the set { (0,0,0), …, (8,0,8) } putting BLACK bricks at some points and WHITE bricks at others. The results is a chessboard pattern.

open Level_5;

fun isEven (x,z) = (x+z) mod 2 = 0;

fun blackWhite (x,y,z) = if isEven(x,z) then BLACK 
                         else WHITE;

fun chessboard () = traverseWithin (0,0,0) 
                                   (7,0,7) 
                                   blackWhite; 

build (8,1,8); 

chessboard();

show "chessboard";

Code-along Program 1

The program below, is similar to the previous program which was used to create a chessboard. One difference is that congruence relation has changed slightly. However, the main difference is that the predicate for determining whether a point has attributes satisfying our congruence relation involves only the x value of the point. Let x1 denote a value for which property x1 evaluates to true. This implies that among the points traversed, all points whose x value is x1 will have attributes satisfying our congruence relation (e.g., (x1,0,0), (x1,0,1), (x1,0,2), and so on).

open Level_5;

fun bars () =
    let
        fun property x  = x mod 3 = 0;  
        
        fun buildBars(x,y,z) = 
            if property x then BLACK 
            else EMPTY;
    in
        traverseWithin (0,0,0) (6,0,6) buildBars
    end;

build(7,1,7);

bars();

show "bars";

Code-along Program 2

In this program the predicate for determining whether a point has attributes satisfying our congruence relation is involves the x and z values of the point. However, note that the predicate property has a body consisting of a Boolean expression involving the orelse operator. This means that the expression is less restrictive (more often true) than the expression in property of the previous program.

open Level_5;

fun bars () =
    let
        fun property (x,z)  = x mod 3 = 0 
                              orelse 
                              z mod 3 = 0;
      
        fun buildBars(x,y,z) = 
            if property (x,z) then BLACK 
            else EMPTY;
    in
        traverseWithin (0,0,0) (6,0,6) buildBars
    end;

build(7,1,7);

bars();

show "bars";

Code-along Program 3

In this program the predicate for determining whether a point has attributes satisfying our congruence relation is involves the x and z values of the point. However, note that the predicate property has a body consisting of a Boolean expression involving the andalso operator. This means that the expression is more restrictive (less often true) than the expression in properties of both the previous programs.

open Level_5;

fun grid () =
    let
        fun property (x,z) = x mod 3 = 0 
                             andalso 
                             z mod 3 = 0;  
           
        fun buildGrid(x,y,z) = 
            if property (x,z) then BLACK 
            else EMPTY;
    in
        traverseWithin (0,0,0) (18,0,18) buildGrid
    end;

build(19,1,19);

grid();

show "grid";

Code-along Program 4

This program involves a much more complex predicate. Placing blue bricks at points that satisfy the function property will result in the construction of a grid of 3D crosses. Note that the function property contains numerous redundant computations (we leave it to the reader to improve the code).

One thing that stands out in this example is the complexity of the property needed to create a single cross. Perhaps there is a better way.

open Level_5;

fun crossField () =
    let
        fun property (x,y,z) =
            let
                val up       = x mod 5 = 1 
                               andalso 
                               z mod 5 = 1;

                val sideways = x mod 5 < 3  
                               andalso 
                               y = 1 
                               andalso 
                               z mod 5 = 1;

                val back     = x mod 5 = 1 
                               andalso 
                               y = 1 
                               andalso 
                               z mod 5 < 3;

            in
                up orelse sideways orelse back  
            end;
        
        fun buildCross(x,y,z) = 
            if property (x,y,z) then BLUE
            else EMPTY
    in
        traverseWithin (0,0,0) (32,2,32) buildCross
    end;

build(33,3,33);

crossField();

show "crossField";

Code-along Program 5

In this example, the function cross builds a 3-dimensional cross-shaped artifact using calls to Level_4 put functions. Note that Level_5 is defined in such a way that it contains all of the Level_4 functions. Therefore, having a declaration that explicitly opens Level_4 is unnecessary.

In this program, a predicate called buildHere is declared which evaluates to true for points corresponding to the lower-left corner of a 3x3x3 cube in which a 3D cross can be constructed. If we wanted a field of crosses without spaces between them, the buildHere function would have needed to perform mod 3 operations. However, we want crosses to be separated from each other by a distance of 2 cells so we perform mod 5 operations.

It should be noted that the function cross is not a brick function (i.e., it does not return a brick value as its result). For this reason, cross is unsuitable for use with traverseWithin. However, in Level_5 there is another traversal function called applyWithin for which our cross is a suitable argument. Specifically, applyWithin is a traversal that applies a point_function to every point it traverses. Bricklayer defines a point_function to be a specific function type. A function that takes a 3D point as input and returns the unit value as output is of the type point_function. Using this definition, we see that cross is a function whose type is point_function.

Below is the actual definition of the point_function type and the signature of the function applyWithin used in Bricklayer.

A strong argument can be made that for certain kinds of patterns, combining Level_4 and Level_5 construction techniques is better than trying to express the pattern exclusively using Level_4/Level_5 functions.

open Level_5;

fun crossField () =
    let
        fun cross (x,y,z) =
            (
                put (3,1,1) BLUE (x,y+1,z+1);
                put (1,3,1) BLUE (x+1,y,z+1);
                put (1,1,3) BLUE (x+1,y+1,z)
            );
        
        fun buildHere (x,y,z) = x mod 5 = 0 
                                andalso 
                                y = 0 
                                andalso 
                                z mod 5 = 0;
        
        fun buildCross(x,y,z) = 
           if buildHere (x,y,z) then cross(x,y,z) 
           else ();
    in
        applyWithin (0,0,0) (32,2,32) buildCross
    end;

build(33,3,33);

crossField();

show "crossField";