Level 5 – Document

Level_5 is a Bricklayer interface (technically speaking an SML structure) that extends the Level_4 interface with a set of functions for traversing regions within Bricklayer’s virtual space. An access function is provided for obtaining the contents of a cell, and an update function is provided as a conceptual counterpart to the access function.

See Vitruvia Concepts 20-23 for exercises relating to Level_5 functions.

To get (direct) access to all the functions in Level_5, place the following command at the beginning of your bricklayer program:

Bounding Box

A key concept used by Bricklayer’s traversal functions is the bounding box which is defined as the smallest rectangular prism enclosing a region in the virtual space.

When specifying a bounding box, the goal is to provide enough information that the coordinates of all 8 corners of the rectangular prism can be determined. The most direct way of doing this would be to simply list the coordinates of all 8 corners. However, there are shorter ways of doing this.

Standard Specification Format

A standard way of specifying a bounding box is by identifying the coordinates of the left-lower-front corner of the box and the right-upper-back corner of the box. For example, the coordinates (0,0,0) and (10,10,10) define a bounding box whose cells range from (0,0,0) to (10,10,10). Using these two coordinates, the coordinates of all the other corners of the rectangular prism can be determined: (0,0,0), (0,0,10), (0,10,0), (0,10,10), (10,0,0) (10,0,10), (10,10,0), and (10,10,10).

Let (xLo,yLo,zLo) and (xHi,yHi,zHi) denote a pair of coordinates. In order for these two coordinates to meet the conditions associated with the standard definition of a bounding box, the following properties must hold.

• xLo ≤ xHi
• yLo ≤ yHi
• zLo ≤ zHi

Alternate Specification Format

Another way a bounding box could be specified is to identify the coordinates of the left-upper-front and right-lower-back corner of the box. Reasoning similar to that discussed in the Standard Format section can be used to determine the coordinates of all the corners of the bounding box.

Level_5 Functions

Level_5 includes all functions found in Level_4 plus the functions described below.

traverseWithin : point → point → brick_function → unit

The traverseWithin function takes three inputs in curried form. The first two inputs define the bounding box of the region over which the traversal is to occur. The third input is a function whose signature is

point → brick_type

When applied to a coordinate, a function having the above signature will return a brick as its result. We refer to such a function  as a brick function.

When called, the traverseWithin function will visit every cell its bounding box and apply the brick function to the coordinate of that cell. The contents of the cell will be updated with the result produced by the brick function.

IMPORTANT: No assumptions should be made about the order in which cells in the bounding box are visited.

applyWithin : point → point → ‘a point_function → unit

The applyWithin function takes three inputs in curried form. The first two inputs define the bounding box of the region over which the traversal is to occur. The third input is a function whose signature is

point → ‘a

The ‘a is a type variable which stands for any type. Thus, when applied to a coordinate, a function having the above signature may return a value of any type as its result. We refer to such a function  as a point function.

When called, the applyWithin function will visit every cell its bounding box and apply the point function to the coordinate of that cell.

IMPORTANT: No assumptions should be made about the order in which cells in the bounding box are visited.

access : point → brick_type 

The access function takes as input a coordinate in the virtual space and returns the contents of the cell at that coordinate.  The contents of a cell can be a LEGO brick, a Minecraft block, or the EMPTY piece.

update : brick_type → point → unit

The update function takes a brick_type and coordinate as its input and “puts” a 1-bit brick at the coordinate in the virtual space. As shown below, the update function is a special case of the put function.

The primary reason for including the update function in Level_5 is as a conceptual counterpart for the access function. Specifically, in computer science algorithms involving structures that hold data are described using the terms access and update.

iterateZX : int → point2D → point2D → brick_function → unit

The iterateZX function can be used to traverse over a region in the virtual space in a controlled manner. Specifically, the caller has control over the order in which cells are visited during a traversal. This control allows structures to be created using algorithms that query (using the access function) previously visited cells. Elementary cellular automata are an example the kinds of structures that can be created using the iterateZX function.

The iterateZX function takes 4 arguments as input. The first is the y-value of the xz-plane over which the iteration will occur. The second two inputs specify the 2-dimensional bounding box of the region in the xz-plane over which the iteration will occur. To provide greater control over the order in which cells are visited, the 2-dimensional bounding box can be specified in one of the following ways:

1. The 2D bounding box can be specified in a left-front…right-back fashion. This format is a special case of the standard specification format described in the beginning of this document. Specifically, the 2D bounding box is obtained from the 3D bounding box by simply removing the y-value from the coordinates.
2. The 2D bounding box can be specified in a right-back…left-front fashion. This format is equivalent to the previous format with the coordinates reversed.
3. The 2D bounding box can be specified in a left-upper…right-lower fashion. This format is a special case of the alternate specification format described in the beginning of this document. Specifically, the 2D bounding box is obtained from the 3D bounding box by simply removing the y-value from the coordinates.
4. The 2D bounding box can be specified in a right-lower…left-upper fashion. This format is equivalent to the previous format with the coordinates reversed.

The iterateZX function creates a counter using the bounding box information provided. Conceptually, this counter is like a 2-place odometer with the z-value occupying the first (i.e., left) position and the x value occupying the second (i.e., right) position. Let (x1,z1) and (x2,z2) denote the coordinates of the 2D bounding box. The counter created by iterateZX will visit the coordinates in the range (x1,z1)…(x2,z1) first. Then a similar range of coordinates will be visited for the next value of z: (x1,next(z1))…(x2,next(z1)). This continues until all coordinates in the bounding box have been processed.

To each coordinate visited, the brick function (i.e., the 4th input to iterateZX) is applied in a manner similar to that used by the traverseWithin function.

Example 1

open Level_5;

val dim = 10;
val max = dim - 1;

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

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

build (dim,dim,dim);

traverseWithin (0,0,0) (max,max,max) brickFn;

show "checkered cube";

Example 2

open Level_5;

val dim = 10;
val max = dim - 1;

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

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

build (dim,dim,dim);

traverseWithin (0,0,0) (max,0,max) brickFn;

show "checkered board";

Example 3

open Level_5;

val dim = 64;
val max = dim - 1;

fun multipleOf u v = u mod v = 0;

fun square side brick (x,y,z) =
    (
        line (x     ,y,z  )    (x+side,y,z     ) brick;
        line (x     ,y,z+side) (x+side,y,z+side) brick;
        line (x     ,y,z  )    (x     ,y,z+side) brick;
        line (x+side,y,z  )    (x+side,y,z+side) brick
    );

fun someFn1 (x,y,z) = 
     if multipleOf x 16 andalso multipleOf z 16  
     then square 12 BLACK (x,y,z) else ();

fun someFn2 (x,y,z) = 
     if multipleOf (x-8) 16 andalso multipleOf (z-8) 16
     then square 12 RED (x,y,z) else ();

build (dim,1,dim);

applyWithin (0,0,0) (max,0,max) someFn1;
applyWithin (0,0,0) (max-8,0,max-8) someFn2;

show "squares";

Example 4

open Level_5;

val dim = 10;
val max = dim - 1;

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

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

fun brickFn2 (x,y,z) = 
     if access(x,y,z) = BLACK andalso x+y+z < 10 
     then BLUE 
     else IDENTITY;

build (dim,dim,dim);

traverseWithin (0,0,0) (max,0,max) brickFn1;
traverseWithin (0,0,0) (max,0,max) brickFn2;

show "checkered board";

Example 5

open Level_5;

val dim = 10;
val max = dim - 1;

fun isEven v = v mod 2 = 0;

fun brickFn (x,y,z) = 
     if access(x,y,z) = BLACK andalso isEven x 
     then RED 
     else IDENTITY;

build (dim,dim,dim);

line (0,0,0) (max,0,max) BLACK;
traverseWithin (0,0,0) (max,0,max) brickFn;

show "checkered line";

Example 6

This example shows the various ways the iterateZX function can be used to traverse a bounding box. The order in which cells are visited is shown in the command prompt window.

open Level_5;

val dim = 10;
val max = dim - 1;

fun toString (x,y,z) = 
    let
        val xStr = Int.toString x;
        val yStr = Int.toString y;
        val zStr = Int.toString z;
    in
        "(" ^ xStr ^ "," ^ yStr ^ "," ^ zStr ^ ")" 
    end;
    
fun brickFn (x,y,z) = 
    (
        print("(x,y,z) = " ^ toString (x,y,z) ^ "\n");
        IDENTITY
    );

build (dim,dim,dim);

(* bounding box = upper-right...lower-left *)
iterateZX 0 (max,max) (0,0) brickFn;

(* bounding box = lower-left...upper-right *)
iterateZX 0 (0,0) (max,max)  brickFn;

(* bounding box = upper-left...lower-right *)
iterateZX 0 (0,max) (max,0)  brickFn;

(* bounding box = lower-right...upper-left *)
iterateZX 0 (max,0) (0,max)  brickFn;

(* other examples *)
iterateZX 0 (2,4) (7,2)  brickFn;
iterateZX 0 (7,2) (2,4)  brickFn;

show "counters";

Example 7

open Level_5;

val dim = 40;
val max = dim - 1;

fun brickFn (x,y,z) = 
     if access(x,y,z+1) = BLACK then WHITE else BLACK;

build (dim,dim,dim);

putMultibrick (dim,1,1) [BLACK,WHITE] (0,0,max);

iterateZX 0 (max,max-1) (0,0) brickFn;

show "random checkered board";