Locals

Code refactoring and locals

One of the things that separates good programmers from the others is the process of refactoring.

One way to do this is to use local expressions. These allow us to write definitions - such as constants, functions, and structures - that are only visible within the local expression. We can then use these locals to create “private” helper functions and to avoid redundant computation.

Local Intuition

(local [(define a 1)   ; local definitions
		(define b 2)]
	(+ a b))           ; local body

What the local definition does is create variables that only exist within the local expression. That is to in, within the function above we defined a and b, but those variables will not exist once the expression is completed.

Note that the local definitions can be anything, from constants to type structures and functions.

To create local expressions in Racket:

(local [<definition> ...]
	<expression>)

Note that we could have a local expression without definitions, but that would probably be a waste of time anyway.

Lexical Scoping

In a program, there is a “top-level” or “global” scope. A way to think about this is to imagine there is a box that surrounds our code where we can make definitions, etc.

If, inside that box, we encounter a local expression, we can create another box (a box inside the larger box) that itself allows definitions to exist only inside said box.

As we add more and more of these, what we get is a lexical contour.

If we were to encounter a reference to the same namespace in box the local and the global scopes we can resolve any ambiguity by always referring first to the inner most (the most local) attribution.

(define p "incendio ")
 
(local [(define p "accio ")]
	(define (fetch n) (string-append p n))    ; Most local p
		fetch "portkey")                      ; If p not local, global p used

Another example:

(define a 1)
(define b 2)
 
(+ a                     ; global b
	(local [(define b3)] ; local b
	 (+ a b))            ; global a
	 b)                  ; global b
 
;; returns 7

Evaluation rules

(define b 1)
 
(+ b
	(local [(define b 2)]
	 (* b b))
   b)

When evaluating a local, three things happen at once:

1. Renaming
   1. Take every definition in local and create a new global name for each instance

local [(define b_0 2)]
	(* b_0 b_0)

2. Lifting
   1. Once the local definitions have been renamed, lift the definition from local scope into global scope
3. Replace entire local with renamed body

The end result, then, is to completely remove locals at runtime. In essence, the program becomes as follows:

(define b 1)
(define b_0 2)    ; renamed local b
 
(+ 1              ; global b
	(* b_0 b_0)   ; lifted local body
	b)            ; global b

Encapsulation

Encapsulation allows us to take larger programs and break each module of the program into smaller containers, where each of those continers (or capsules) have all the references they need without making calls to top level or global definitions.

This is particularly useful because it allows us to avoid the issue of having multiple definitinos with the same name, especially on larger teams.

It is also useful when writing complex functions. Consider a function that sums al the data in a data tree. It is likely that the functio wil have 2 mutualy referencial functions:

(define (sum-data--element e) empty)
(define (sum-data--loe) loe)

Here we are assuming a type-struct Element and a ListOfElement, both of which call each other to traverse the tree. However, someone using this program isn’t likely to care about the specific, local functions; the important part is the result of the entire operation.

Thus, we use locals and encapsulation to hide the inner workings of sum-data. In other words, we make the --element and --loe parts “private”:

(define (sum-data e)
  (local [(define (sum-data--element e)
            (if (zero? (elt-data e))
                (sum-data--loe (elt-subs e))
                (elt-data e))) 
 
          (define (sum-data--loe loe)
            (cond [(empty? loe) 0]
                  [else
                   (+ (sum-data--element (first loe))
                      (sum-data--loe (rest loe)))]))]
    (sum-data--element e)))

In general, good candidates for encapsulation are functions that “work well” together, mutually recursive functions, for example, or helper functions. Additionally, we want to ensure that the rest of the program only really cares about a spcific function, and has no need for calling its helpers.

As part of the process of encapsulation, we want to define a namefor our new global function, encapsulate the new local functions, ensure we call the “trampoline”, adjust the signatures (only the input and outputs of the global function need to be written), and adjust any unit tests as required.

The process of encapsulating, then, follows a refactoring methodology: change a program’s code/structure without changing its behaviour. Thus, when we are done encapsulating we want to run the program as soon as possible to ensure no mistakes were made.

Because the process of encapsulating mutually recursive functions is always the same, we can also modify our templates to include the encapsulation from the beginning. The result of this is that we also don’t need to rename the fn-for-x calls inside our template, since they are effectively private:

(define (fn-for-element e)
    (local [(define (fn-for-element e)
                (...(elt-name e) 
                    (elt-data e)
                    (fn-for-loe (elt-subs e))))
 
            (define (fn-for-loe e)
               (cond [(empty? loe) (...)]
                     [else
                        (... (fn-for-element (first loe))
                             (fn-for-loe (rest loe)))])))
    (fn-for-element e))

Avoiding recomputation

It is better to design a program that is simple to design and change, and only then worry about efficiency. This way, we can use benchmarks to find the actual bottlenecks - often times unexpectedly.

Nontheless, it is still impotant to avoid writing functions tht sufer from exponential growth. Consider, for example, this snippet:

[else
    (if (not (false? (find--element n (first lon))))
        (find--element n (first lon))
        (find--loe n (rest loe)))]

If we are using the above to search through an arbitrary arity tree, we will find that as the tree grows, the computation time will grow exponentially. This is because this design will traverse the tree twice as many times per level - ones to evaluate the if, and if true, then to produce an answer.

The solution is to ensure we only traverse the tree once. We can us local functions to achieve this. To do this, simply find the closest enclosing expression that call the bottleneck function twice and wrap it in a local:

[else
    (local [(define try (find--element n (first loe)))]
    (if (not (false? try))
    try
    (find--loe n (rest loe))))]

The procedure is to create a local variable to hold the result, and then replace every recursive call with the variable.