Code Along

gray kangaroo

A code-along is a story about coding in which you are encouraged to “code up” all the examples gray kangarooin the story. In a code-along you should not cut-and-paste.

In this code along, we will explore val-declarations and let-blocks. These are language constructs that can be used to help us organize and improve the structure of Bricklayer programs.

Bricklayer programs are written in the functional programming language SML. The primary elements used in SML programs are declarations and expressions.

Bricklayer programs begin with a bricklayer-doc comment followed by a sequence of declarations which is followed by a sequence of expressions. SML comments can occur anywhere within a Bricklayer program.

So far we have learned about the the following kinds of declarations and expressions.

  • declarations
    • open id
    • fun id args = expression
  • expressions
    • values
      • integer
      • string
      • tuple
    • variables
    • arithmetic expressions – expressions containing arithmetic operators
    • string expressions – expressions containing the string concatenation operator
    • function calls
    • expression sequences

Val-declarations

The val-declaration is a construct provided by the language SML as a mechanism for binding variables (i.e., identifiers) to values. Syntactically, a val-declaration consists of the keyword val followed by a special kind of equation. In general, this equation has a pattern as its left-hand side and an expression as its right-hand side.

val pattern = expression;

 

Here, we will restrict our attention to a special kind of pattern consisting of a single identifier (other kinds of patterns will be discussed in higher Bricklayer levels). We will use the term “restricted val-declaration” when referring to a val-declaration whose equation has a left-hand side that is an identifier.

val id = expression;

 

The execution of a restricted val-declaration involves the following steps:

  1. The expression on the right-hand side of the equation is reduced (through computation) to a value.
  2. The variable (i.e., id) on the left-hand side of the val-declaration’s equation is bound to the value produced in step 1.

All references to a variable bound by a val-declaration denote the value to which it is bound.

Example 1

val x = 5 + 6;
x + x;

 

Example 2


val x = 5 + 6;
val z = 2 * x;
x + z;

 

Observation

From a syntactic perspective, restricted val-declarations are similar to function declarations.

val id = expression;

fun id args = expression;

 

Summary

We now have learned about three kinds of declarations. The keywords used by each kind of declaration is listed below.

  • open
  • fun
  • val

Let-blocks – a new kind of expression

The let-block is a very useful programming language construct. A let-block is an expression that can contain declarations which are only visible within the let-block. This is a nice way to manage/organize the variables/names that can be referenced at a given point in a program.

Syntactically, a let-block consists of the keyword “let” followed by a list of zero or more declarations, followed by the keyword “in”, followed by a semicolon-separated sequence of expressions, followed by the keyword “end”. We will refer to the semicolon-separated sequence of expressions (between the keyword in and the keyword end) as the body of the let-block.

let 
    declaration list
in 
    expression sequence (* aka the body of the let-block *)
end

 

A let-block is executed by first evaluating the declaration list in lexical order. This will create a set of variable bindings. Next, the expressions in the body of the let-block are evaluated in lexical order (meaning from top to bottom and from left to right).

Computationally speaking, a let-block reduces to the value of the last expression in its body.

Example 1

The let-block below reduces to the value 33.

let 
    val x = 5 + 6;
    val z = 2 * x;
in 
    x + z
end

 

Example 2

The let-block below reduces to the value 242.

let 
    val x = 5 + 6;
    val z = 2 * x;
in 
    x + z;
    x * z
end

 

Initial Program

The code examples that follow show how let-blocks can be introduced into Bricklayer programs in order to make programs more readable, organized, and to eliminate redundant computations.

We begin with a program that uses a geometric algorithm to construct a grid whose “squares” contain a cross artifact. Notice that the cross artifact is created by a function called, seed. The cross fits into a 3×3 box (its true bounding box).

The function cross1 is simply a renaming of the seed function. This renaming is done to help the reader understand the difference between the seed pattern and its geometric repetition. The coordinates in the geometric repetitions are related. However, the coordinates in the seed pattern have no relation to the coordinates in the geometric repetition.

A 4-cross pattern can be created by placing four individual crosses, and a 16-cross pattern can be created by placing four 4-cross patterns.

The positioning of the crosses in the geometric pattern is such that the individual crosses are separated by a single space. This is accomplished by code that (in effect) assumes the bounding box for the cross is a 4×4 box.

open Level_3; 

fun seed (x,z) = 
    (
cross1
        put2D (3,1) BLUE (x    ,z + 1);
        put2D (1,3) BLUE (x + 1,z    )
    );

fun cross1 (x,z) = seed (x,z);
  
fun cross4 (x,z) = 
    (
cross4
        cross1 (x      ,z      );
        cross1 (x + 2*2,z      );
        cross1 (x + 2*2,z + 2*2);
        cross1 (x      ,z + 2*2)
    );

fun cross16 (x,z) = 
    (
cross16
        cross4 (x        ,z        );
        cross4 (x + 2*2*2,z        );
        cross4 (x + 2*2*2,z + 2*2*2);
        cross4 (x        ,z + 2*2*2)
    );
    
build2D (64,64);

cross16 (0,0);

show2D "grid";

 

Transforming Expression Sequences into (Empty) Let-blocks

In this version of the program, the expression sequences that formed the bodies of the cross4 and cross16 function declarations are transformed into equivalent let-block expressions.

It is worth noting that the body of the cross4 function contains four occurrences of the expression “2*2”. Technically speaking, this expression could be evaluated statically (e.g., by the programmer). However, in its current form, the expression reveals how coordinates change over the course of the geometric algorithm.

Similarly, the body of the cross16 function contains four occurrences of the expression “2*2*2”.

open Level_3; 

fun seed (x,z) = 
    (
        put2D (3,1) BLUE (x    ,z + 1);
        put2D (1,3) BLUE (x + 1,z    )
    );

fun cross1 (x,z) = seed (x,z);
  
fun cross4 (x,z) = 
    let
    in
        cross1 (x      ,z      );
        cross1 (x + 2*2,z      );
        cross1 (x + 2*2,z + 2*2);
        cross1 (x      ,z + 2*2)
    end;

fun cross16 (x,z) = 
    let
    in
        cross4 (x        ,z        );
        cross4 (x + 2*2*2,z        );
        cross4 (x + 2*2*2,z + 2*2*2);
        cross4 (x        ,z + 2*2*2)
    end;
    
build2D (64,64);

cross16 (0,0);

show2D "grid";

 

Factoring out Repeated Computations from Let-block Bodies

In this version of the program, redundant computations are factored out of the bodies of the cross4 and cross16 functions. This is done by introducing a restricted val-declaration in which the variable named offsest is bound to the expression 2*2 in the function cross4 and 2*2*2 in the function cross16.

In cross4, the introduction of the variable offset is accompanied by a replacement of all occurrences of 2*2 in the body of the let-block by the variable offset. This completes the factoring for the function cross4.

A similar refactoring is applied to the body of the function cross16.

Note that in the bodies of cross4 and cross16  the variable introduced is named offset. The reason for using this same name in both functions is because, conceptually speaking, it serves the same purpose in both functions.

open Level_3; 

fun seed (x,z) = 
    (
        put2D (3,1) BLUE (x    ,z + 1);
        put2D (1,3) BLUE (x + 1,z    )
    );

fun cross1 (x,z) = seed (x,z);
  
fun cross4 (x,z) = 
    let
        val offset = 2*2;
    in
        cross1 (x         ,z         );
        cross1 (x + offset,z         );
        cross1 (x + offset,z + offset);
        cross1 (x         ,z + offset)
    end;

fun cross16 (x,z) = 
    let
        val offset = 2*2*2;
    in
        cross4 (x         ,z         );
        cross4 (x + offset,z         );
        cross4 (x + offset,z + offset);
        cross4 (x         ,z + offset)
    end;
    
build2D (64,64);

cross16 (0,0);

show2D "grid";

 

Normalizing Repeated Function Calls

This next transformation involves renaming the functions called in the body of the cross4 and cross16 functions. Specifically, the body of the let-block in cross4 consists of four calls to the function cross1. Similarly, the body of the let-block in cross16 consists of four calls to the function cross4.

A val declaration can be used to essentially rename a function. For example, the declaration

val f = cross1;

binds the variable f to the function cross1. Technically speaking, the variable f is bound to the function value to which cross1 is bound. However, at this point it sufficies to simply think of f as another name for the function cross1. The val-declaration above has the same effect as the following fun declaration.

fun f (x,z) = cross1 (x,z);

As was the case with the choice of offset as our variable name, we will use the same name to rename our functions in both function bodies. We do this because the renamed functions are serving conceptually equivalent purposes. Specifically, in the body of cross4, the function cross1 will be renamed to f. In the body of cross16, the function cross4 will be renamed to f as well.

To complete the renaming normalization, all occurrences of cross1 in the the body of the let-block associated with the function cross4 must be renamed to f. Similarly, all occurrences of cross4 in the the body of the let-block associated with the function cross16 must be renamed to f.

Notice the syntactic similarity of the bodies of cross4 and cross16. We are precisely trying to achieve such similarity. Furthermore, this similarity is no accident.

open Level_3; 

fun seed (x,z) = 
    (
        put2D (3,1) BLUE (x    ,z + 1);
        put2D (1,3) BLUE (x + 1,z    )
    );

fun cross1 (x,z) = seed (x,z);
  
fun cross4 (x,z) = 
    let
        val offset = 2*2;
        val f      = cross1;
    in
        f (x         ,z         );
        f (x + offset,z         );
        f (x + offset,z + offset);
        f (x         ,z + offset)
    end;

fun cross16 (x,z) = 
    let
        val offset = 2*2*2;
        val f      = cross4;
    in
        f (x         ,z         );
        f (x + offset,z         );
        f (x + offset,z + offset);
        f (x         ,z + offset)
    end;
    
build2D (64,64);

cross16 (0,0);

show2D "grid";

 

Moving a Top-Level Declaration into a Let-block

This last version of the program is mainly to show that declarations in a let-block can also be function declarations. In this version, the declaration of the function cross4 is moved into the declaration list of the let-block which forms the body of the cross16 function declaration. Note that, as a result, the function cross4 is not visible (i.e., is not defined) outside of the body of the cross16 function declaration.

open Level_3; 

fun seed (x,z) = 
    (
        put2D (3,1) BLUE (x    ,z + 1);
        put2D (1,3) BLUE (x + 1,z    )
    );

fun cross1 (x,z) = seed (x,z);
  
fun cross16 (x,z) = 
    let
        fun cross4 (x,z) = 
            let
                val offset = 2*2;
                val f      = cross1;
            in
                f (x         ,z         );
                f (x + offset,z         );
                f (x + offset,z + offset);
                f (x         ,z + offset)
            end;

        val offset = 2*2*2;
        val f      = cross4;
    in
        f (x         ,z         );
        f (x + offset,z         );
        f (x + offset,z + offset);
        f (x         ,z + offset)
    end;
    
build2D (64,64);

cross16 (0,0);

show2D "grid";