SICP series - Procedural Abstraction

14 November 2019
Tags: fundamentals SICP functional programming

The previous article Introductory Concepts exposed procedures as basic components to capture processes. Scheme provides one mechanism to define procedures: the lambda expression. The purpose of this element is to capture common patterns of computation into the body of the procedure. For example in order to group any pattern of the form

(* 3 3)
(* 5 5)

the following lambda expression can be used

(lambda (x) (* x x))

to capture the double an element process. It consists of two components, namely the parameters and the body which is evaluated to a value. The lambda expression can be combined with the naming abstraction of the previous article to provide a name to the procedure. The previous expression can then be rewritten in the following manner

(define square (lambda (x) (* x x)))

It is thus possible to use the procedure by simply calling it by its name, like (square 5), which gives the result 25.

The following steps provide an overview of the steps to abstract processes:

  • identify modules or stages of a process

  • capture each module within a procedural abstraction

  • construct a procedure to control the interactions between the modules

  • repeat the process within each module as necessary

Abstraction and Modularity

By means of the procedure, we can treat processes as black boxes in which the implementation details are hidden and detached from the use of the procedure, which can simply be referred by its name or lambda expression. The procedure also exposes a contract, according to which for given inputs of the provided type an output of the specified type will be given. So the black box abstraction hides the details of this contract for converting input to output.

Another important concept which allow to create modular systems is that of block structures. It consists in defining procedures inside the body of the lambda expression of a given procedure; by doing so, the internal procedures are accessible only to other expressions within the body of the lambda, but inaccessible outside the scope ofthe procedure. This is important, because internal procedures become part of the implementation details of procedures giving them a higher abstraction power. A trivial example to illustrate the concept can be the following one hiding the square lambda inside the sum of squares procedure. Note that normally it would be arguable whether the square procedure should be made private as it can be useful anywhere in the system, but I will stick to this example for simplicity sake.

(define (sum-of-squares a b)
  (define (square x)
    (* x x))
  (+ (square a) (square b))
)

Higher-order Functions

Higher-order procedures bring the concept of procedure abstraction to the next level by capturing common procedural patterns. They take other procedures as arguments or return one as value. This allows to further increase the modularity of the system. As an example let’s consider different patterns of sum such as the following ones

(define (sum-integers a b)
  (if (> a b)
    0
    (+ a (sum-integers (+ 1 a) b))))
(define (sum-squares a b)
  (if (> a b)
    0
    (+ (square a) (sum-squares (+ 1 a) b))))

It is clear both procedures share the same form, so they can be distilled into the following higher-order procedure

(define (sum term a next b)
  (if (> a b)
    0
    (+ (term a) (sum term (next a) next b))))

Both term and next are procedures and are passed as arguments to sum.

Recursive and iterative processes

The last topic of this post regards the shape a process can assume, which could either be recursive or iterative. The shape of the process determines some of its characteristics such as the space and time complexity. The following two paragraphs are going to go more in detail on each approach.

Recursive Processes

A recursive process is characterized by a set of deferred operations as long as the computation does not reach the base case; once that point is reached, the stacked up operations are accumulated to give the final result. For example consider the shape for the factorial operation

(fact 3)
(* 3 (fact 2))
(* 3 (* 2 (fact 1)))
(* 3 (* 2 (* 1)))
(* 3 (* 2))
6

The implementation of the factorial procedure is

(define fact
  (lambda (n)
    (if (= n 1)                 # test base case
      1                         # base case
      (* n (fact (- n 1))))))   # recursive case

It is clear that the algorithm grows linearly with the size of the argument in both space and time.

The steps to design recursive algorithms are the following ones:

  1. wishful thinking - assume you have avilable a procedure that solves the problem for smaller versions of it

  2. decompose the problem - use the solution to smaller sized problems with some operations to get the solution to the larger sized problem

  3. identify non-decomposable problems - identify the smallest problem, i.e. base case

Iterative Processes

Contrary to the recursive process, iterative processes do not require to keep track of deferred operations, but perform the computations without using any additional memory. For this reason additional parameters are needed to store the current state of the computation such as counters and temporary values. A possible shape for the iterative factorial algorithm is the following one

(ifact 3)
(if (> 1 3) 1 (ifact-helper (* 1 1) (+ 1 1) 3))
(if (> 2 3) 1 (ifact-helper (* 1 2) (+ 2 1) 3))
(if (> 3 3) 2 (ifact-helper (* 2 3) (+ 3 1) 3))
(if (> 4 3) 6 (ifact-helper (* 6 4) (+ 4 1) 3))
6

for the procedure

(define ifact-helper
  (lambda (product counter n)
    (if (> counter n)
      product
      (ifact-helper (* product counter)
                    (+ counter 1)
                    n))))
(define ifact (lambda (n) (ifact-helper 1 1 n)))

The algorithm grows constantly in space and linearly with the size of the argument in time.

To develop an iterative algorithm the following recipe can be followed:

  • determine a way to accumulate partial answers

  • write a table to analyze

    • initialization of first row

    • update rules for other rows

    • how to know when to stop

  • translate rules in Scheme