arvb.net

Template Blending

3 min read

Template Blending

Templates are a backbone of a function based on a simple premise: before starting to code a function, what do we know about its inputs and outputs, and thereby what do we know about its structure?

In a more complex case, such as the sudoku solver, the templates we use will require several distinct steps. For example, a solve function for Sudoku will require generative recursion to create an arbitrary arity tree over which we will use backtracking search.

Thus, when writing the template for function we will start have to use elements from all three function templates.

Templating

Arbitary Arity Tree

Starting with the arbitrary arity tree, note that it’s strcture is one of elements and lists of elements to denote each node and its subnodes. Thus, begin by wrapping this in a local function:

(note that in this case the tree has Board and ListOfBoard)

(define (solve bd)
  (local [(define (solve--bd bd)
            (... (solve--lobd (bd-subs bd))))
          (define (solve--lobd lobd)
            (cond [(empty? lobd) (...)]
                  [else
                   (... (solve--bd (first lobd))
                        (solve--lobd (rest lobd)))]))]
    (solve--bd bd)))

We can see that all we’ve done here is template according to the arbitrary arity tree, with the exception that the entire tree definition is inside a local. Note that the function names and types are assumed from memory or simple checks - there is no existing definition at this point for bd-subs, so for the moment it is just a reminder of the type of data that will be passed there.

Generative Recursion

Because we know that this problem will be solved with generative recursion - that is, our functions don’t take apart an existing set of sudoku boards, but instead generate the boards at each step - we have to make an adjustment to the structure selector in the aritry tree.

In the definition of the aritry tree we start by calling (solve--lobd (bd-subs bd)): this is simply looking at the sub-elements of a given node. We must change this, like so:

(define (solve bd)
  (local [(define (solve--bd bd)
            (if (solved? bd)
	            bd
	            (solve--lobd (next-boards bd))))
          (define (solve--lobd lobd)
            (cond [(empty? lobd) (...)]
                  [else
                   (... (solve--bd (first lobd))
                        (solve--lobd (rest lobd)))]))]
    (solve--bd bd)))

Here, we renamed the data selector from the arity tree into (next-boards bd) to be suggestive of the generative nature of this section.

We then looked at the template for generative recursion and inserted it into the function. However, instead of pure templating we started making some changes as they became obvious, such as changing (trivial-answer bd) to simply bd, given the nature of the issue we are solving.

All we must do now is take the backtrack search template and insert it into the remaining parts of our template.

(define (solve bd)
  (local [(define (solve--bd bd)
            (if (solved? bd)
                bd
                (solve--lobd (next-board bd))))
                
          (define (solve--lobd lobd)
            (cond [(empty? lobd) false]
            
                  [else
                   (local [(define try (solve--bd (first lobd)))]
                     (if (not (false? try))
                         try
                         (solve--lobd (rest lobd))))]))]
    (solve--bd bd)))

Here we inserted the functionality of backtracking search into (solve--lobd) by simply following the template. By doing so, we have completed most of the logic for the sudoku solver.

Note that this still leaves a few helper functions that need writing, in particular (next-noard bd) and (solved? bd).

Graph View