Level 3 – Code Along 3

Code Along

gray kangaroo

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 four different Bricklayer programs, all of which implement the same geometric algorithm. The geometric algorithm we will be looking at is similar to the algorithms used to construct laces (and chess boards). The difference between between the programs we will be looking at in this code-along is the sophistication of the abstractions and language constructs used in the implementation.

Basics

The code below combines the capability of the Level 3 put2D function to create bricks having arbitrary rectangular shapes (e.g., in this case (7,7)) with overwriting to create a LEGO artifact similar to the Microsoft Window’s logo. Our goal is to a large pattern (like a quilt) in which this base pattern is repeated over and over.

open Level_3;

fun base(x,z) = version1_a
    (
        put2D (7,7) BLACK  (x,z);    
        
        put2D (2,2) BLUE   (x+1,z+1);
        put2D (2,2) YELLOW (x+4,z+1);
        put2D (2,2) GREEN  (x+4,z+4);
        put2D (2,2) RED    (x+1,z+4)
    );
    
build2D(128,128);

base(0,0);

show2D "Window";    

 

This next program shows the basic approach we will take when constructing larger patterns. Note how in the body of the function f0 there are four calls to the function base.


open Level_3;
fun base(x,z) =version1_a 
    (
        put2D (7,7) BLACK  (x,z);    
        
        put2D (2,2) BLUE   (x+1,z+1);
        put2D (2,2) YELLOW (x+4,z+1);
        put2D (2,2) GREEN  (x+4,z+4);
        put2D (2,2) RED    (x+1,z+4)
    );

fun f0(x,z) = version1_b
    (
        base(x,z);
        base(x+7,z);
        base(x+7,z+7);
        base(x,z+7)        
    );
    
build2D(128,128);

f0(0,0);

show2D "Window";    

 

From this point on, the code-along begins…

Code-along Program 1

The program shown below contains four user-defined functions: base, f0, f1, and f2. When called, the function base creates, at a given location, a LEGO artifact similar to a Window’s Logo. We will refer to this artifact as a base-artifact.

The bodies of the functions f0, f1, and f2 are similar. In particular, each function body consists of four function calls. The body of function f0 consists of four calls to the function base. When called, the function f0 creates, at a given location, a LEGO artifact consisting of four base-artifacts arranged in a square. We will refer to the artifact created by f0 as an f0-artifact.

The body of function f1 consists of four calls to the function f0. When called, the function f1 creates, at a given location, a LEGO artifact consisting of four f0-artifacts arranged in a square. We will refer to the artifact created by f1 as an f1-artifact. And similarly, when called, the function f2 creates, at a given location, a LEGO artifact consisting of four f1-artifacts.

Note the similarity between f0, f1, and f2. The only differences are: (1) the locations at which artifacts are to be created, and (2) the name of the function called within the body of the function declaration.


open Level_3;

fun base(x,z) = version1_a
    (
        put2D (7,7) BLACK  (x,z);
        put2D (2,2) BLUE   (x+1,z+1);
        put2D (2,2) YELLOW (x+4,z+1);
        put2D (2,2) GREEN  (x+4,z+4);
        put2D (2,2) RED    (x+1,z+4)
    );

fun f0(x,z) = version1_b
    (
        base(x,z);
        base(x+7,z);
        base(x+7,z+7);
        base(x,z+7)
    );

fun f1(x,z) = version1_c
    (
        f0(x,z);
        f0(x+14,z); (* 2^1 * 7 *)
        f0(x+14,z+14);
        f0(x,z+14)
    );

fun f2(x,z) = version1_d
    (
        f1(x,z);
        f1(x+28,z); (* 2^2 * 7 *)
        f1(x+28,z+28);
        f1(x,z+28)
    );

build2D(128,128);

f2(0,0);

show2D "Window";

Code-along Program 2

In this version of the program we factor out information relating to the positioning of artifacts. More specifically, we declare a new function, called offset, that calculates the appropriate shift value to properly position the artifacts created during a specific function call. The function offset makes use of three functions belonging to SML: Real.round, Real.math.pow, and Real.fromInt. These functions are used to calculate integer powers of 2 (e.g., 2^2 = 4). In this example, the bodies of f0, f1, and f2 have been translated from expression sequences to let-blocks. To each let-block a val-declaration has been added binding the variable shift to an integer value calculated by call to the function offset. The syntactic differences between f0, f1, and f2 are now as follows: (1) the name of the function that is called four times within the body of the declaration varies between f0, f1, and f2, and (2) the integer value passed to the offset function varies between f0, f1, and f2.

open Level_3;

fun base(x,z) = version1_a
    (
        put2D (7,7) BLACK  (x,z);    
        
        put2D (2,2) BLUE   (x+1,z+1);
        put2D (2,2) YELLOW (x+4,z+1);
        put2D (2,2) GREEN  (x+4,z+4);
        put2D (2,2) RED    (x+1,z+4)
    );
    
fun offset n =
    let
        val power = Real.round( Real.Math.pow(2.0, 
                                Real.fromInt n) );
    in
        power * 7
    end;
    
fun f0(x,z) = version1_b
    let
        val shift = offset 0;
    in
        base(x,z);
        base(x+shift,z);
        base(x+shift,z+shift);
        base(x,z+shift)
    end;
    

fun f1(x,z) = version1_c
    let
        val shift = offset 1;
    in
        f0(x,z);
        f0(x+shift,z);  
        f0(x+shift,z+shift);
        f0(x,z+shift)
    end;
    
fun f2(x,z) = version1_d
    let
        val shift = offset 2;
    in
        f1(x,z);
        f1(x+shift,z); 
        f1(x+shift,z+shift);
        f1(x,z+shift)
    end;
            
build2D(128,128);

f2(0,0);

show2D "Window";   

Code-along Program 3

In this version of the program we factor out information relating to the differences in the name of the function that is called four times within the body of the declaration f0, f1, and f2. Specifically, a val-declaration is introduced in which the variable f is bound to the appropriate function to be called. For example, in the case of f0, the variable f is bound to base, and so on.

The idea that functions themselves can be treated as values which can be bound to variables through constructs like val-declarations is one of the hallmarks of functional programming languages.

The syntactic differences between f0, f1, and f2 are now as follows: (1) the integer value passed to the offset function varies between f0, f1, and f2, and (2) the function value bound to f in the val-declaration varies between f0, f1, and f2. Other than that, the bodies of f0, f1, and f2 are identical!

open Level_3;

fun base(x,z) = version1_a
    (
        put2D (7,7) BLACK  (x,z);    
        
        put2D (2,2) BLUE   (x+1,z+1);
        put2D (2,2) YELLOW (x+4,z+1);
        put2D (2,2) GREEN  (x+4,z+4);
        put2D (2,2) RED    (x+1,z+4)
    );
    
fun offset n =
    let
        val power = Real.round( Real.Math.pow(2.0, 
                                Real.fromInt n) );
    in
        power * 7
    end;
    
fun f0(x,z) = version1_b
    let
        val shift = offset 0;
        val f     = base;
    in
        f(x,z);
        f(x+shift,z);
        f(x+shift,z+shift);
        f(x,z+shift)
    end;
    

fun f1(x,z) = version1_c
    let
        val shift = offset 1;
        val f     = f0;      
    in
        f(x,z);
        f(x+shift,z);  
        f(x+shift,z+shift);
        f(x,z+shift)
    end;
    
fun f2(x,z) = version1_d
    let
        val shift = offset 2;
        val f     = f1;      
    in
        f(x,z);
        f(x+shift,z); 
        f(x+shift,z+shift);
        f(x,z+shift)
    end;
            
build2D(128,128);

f2(0,0);

show2D "Window";   

Code-along Program 4

In this version of the program we lift the syntactic differences between f0, f1, and f2 in the previous program and make them parameters to a new function which we will call apply. The functionapply takes as input a function f, an integer n, and a location. Within the body of apply, the value n is used to calculate a shift amount, which is then used to calculate four different locations all of which are passed as parameters to the function f.

The function apply is a curried function – meaning that it takes multiple arguments as input in a curried fashion. This is not new, many Bricklayer functions such as ringXZ and circleXZ are curried functions. What is new in this example is that the argument (i.e., formal parameter) f represents a function! This ability to pass functions as arguments to other functions is a hallmark of functional programming languages.

Notice how the declarations of f0, f1, and f2 have now changed. Notice that if, in the body of apply, the value base is substituted for f and the value 0 is substituted for n, then the body of apply is syntactically identical to the body of the definition of f0 in code-along program 2. Similar equivalences hold for f1, and f2.

open Level_3;

fun base(x,z) = 
    (
        put2D (7,7) BLACK  (x,z);    
        
        put2D (2,2) BLUE   (x+1,z+1);
        put2D (2,2) YELLOW (x+4,z+1);
        put2D (2,2) GREEN  (x+4,z+4);
        put2D (2,2) RED    (x+1,z+4)
    );
    
fun offset n =
    let
        val power = Real.round( Real.Math.pow(2.0, 
                                Real.fromInt n) );
    in
        power * 7
    end;
    
fun apply f n (x,z) = 
    let
        val shift = offset n;
    in
        f(x,z);
        f(x+shift,z);
        f(x+shift,z+shift);
        f(x,z+shift)
    end;
    
fun f0(x,z) = apply base 0 (x,z);
fun f1(x,z) = apply f0   1 (x,z);   
fun f2(x,z) = apply f1   2 (x,z);
    version1_d        
build2D(128,128);

f2(0,0);

show2D "Window";