CSC 341: February 21, 2007

From CSWiki

1 Instructor's notes for the class session
2 Study questions
- 2.1 Proposed Solutions

Instructor's notes for the class session

In the functional model of computation, a step in a computation is the application of an elementary function to its arguments, yielding a value. A procedure is a plan for arranging the steps in a computation so as to specify a function, often one that is not elementary. The procedure tells how to break down the computation so that it starts with the arguments to the specified function and ends with the value of that function for those arguments, applying only elementary functions along the way.

The functions that we'll take as elementary, or (in the jargon or recursive function theorists) primitive, are:

The zero function: $\texttt{zero}() = 0$ .
The successor function: $\texttt{successor}(x) = x + 1$ .
The projection functions $\texttt{pr}^m_n$ : $\texttt{pr}^m_n(x_0, \ldots, x_{n - 1}) = x_m$ .

To build procedures from these elementary functions, we'll use two plan-constructing methods: function composition and recursion.

[edit]

Function composition

The simplest form of function composition should be familiar from the lab on higher-order procedures in CSC 151 or 153. If outer and inner are singulary (one-argument) Scheme procedures, each returning a single value, then their composition is the procedure that takes one argument, applies inner to it, applies outer to the result, and returns the result of that second application. Or, in Scheme:

(define compose
  (lambda (outer inner)
    (lambda (argument)
      (outer (inner argument)))))

For instance, (compose sqrt abs) is a procedure that takes one argument, a number, and returns the square root of the number's magnitude.

In recursive function theory, we generalize this idea, allowing outer to have any valence $m$ and the composite function to have any valence $n$ . The idea is that, instead of supplying just one "inner" function, we can supply $m$ of them. Each of those "inner" functions takes $n$ arguments and returns one value; the outer function collects the $m$ results, uses them as its arguments, and retuns one value. The composite function, then, takes $n$ arguments and returns one value; all that composition does, operationally, is set up the internal data paths (multiplexing the inputs so that they reach all of the "inner" functions, and connecting the outputs from the "inner" functions to the inputs of the outer function).

We could implement this more general idea in Scheme as follows:

(define generalized-compose
  (lambda (outer . inners)
    (lambda arguments
      (apply outer (map (lambda (inner)
                          (apply inner arguments))
                        inners)))))

(Note, however, that this code doesn't enforce the valence requirements.)

So, for example, (generalized-compose + sqrt abs /) is a procedure that takes one argument, a number, and returns the sum of its square root, magnitude, and reciprocal. (Here $m$ is 3 and $n$ is 1.)

In mathematical notation, this general form of definition by function composition is written this way:

$h(x_0, \ldots, x_{n - 1}) = f(g_0(x_0, \ldots, x_{n - 1}), \ldots, g_{m - 1}(x_0, \ldots, x_{n - 1}))$

Here $h$ is the function being defined, $f$ is the ``outer function, and $g_0, \ldots, g_{m - 1}$ are the ``inner functions. The $n$ arguments to $h$ are multiplexed out to all of the inner functions, and their results are collected and submitted as arguments to $f$ . The value of $f$ at those (intermediate) arguments is the value of $h$ at the original arguments.

Because this notation is cumbersome, we'll use the more concise form $\texttt{[}\texttt{o}^m_n\texttt{\ }f\texttt{\ }g_0\texttt{\ }\dots\texttt{\ }g_{m - 1}\texttt{]}$ for the procedure of composing the $m$ -ary function $f$ with the $n$ -ary functions $g_0, \ldots, g_{m - 1}$ in this way.

[edit]

Recursion

Our other plan-building operation is recursion, specifically zero-based recursion over natural numbers. To simplify some of the proofs later on, we'll assume that the variable of recursion is always the last of the arguments to the function that we're trying to define; for generality, however, we'll assume that that function can have any positive valence, with all but the last of the arguments being, in effect, fixed and constant values as far as the recursion is concerned.

In mathematical notation, then, a recursive definition of a function $h$ generally takes the form of a pair of "recursion equations," one specifying the value of the function in the base case, when the value of the variable of recursion is 0, and the other describing how to compute the value of the function being defined when the value of the variable of recursion is a successor, say $t + 1$ :

$h(x_0, \ldots, x_{n - 1}, 0) = f(x_0, \ldots, x_{n - 1}) h(x_0, \ldots, x_{n - 1}, t + 1) = g(t, h(x_0, \ldots, x_{n - 1}, t), x_0, \ldots, x_{n - 1})$

Note the resources that we have available to help us with the computation in the second equation:

$t$ itself,
the value $h(x_0, \ldots, x_{n - 1}, t)$ of the recursively defined function when the value of the variable of recursion is $t$ , and
all of the other (fixed) arguments to the function being defined.

These resources are supplied as arguments to a function $g$ , which effectively performs the induction step that computes the new value of $h$ from the "preceding" one.

This pattern could be rendered in Scheme, again without the valence restrictions, as follows:

(define generalized-recursion
  (lambda (base induction)
    (lambda arguments
      (call-with-values
        (lambda () (detach arguments))
        (lambda (last all-but-last)
          (letrec ((recurser (lambda (vor) ; "variable of recursion"
                               (if (zero? vor)
                                   (apply base all-but-last)
                                   (apply induction (- vor 1)
                                                    (recurser (- vor 1))
                                                    all-but-last)))))
            (recurser last)))))))

(define detach
  (lambda (ls)
    (if (null? (cdr ls))
        (values (car ls) '())
        (call-with-values
          (lambda () (detach (cdr ls)))
          (lambda (last all-but-last-of-cdr)
            (values last (cons (car ls) all-but-last-of-cdr)))))))

The Scheme analogue of the recursive definition of add in Theorem 3.1 on the handout would be

(define add (generalized-recursion (lambda (x) x)
                                   (lambda (x y z) (+ y 1))))

Again, for concision, we'll write the procedure for defining an $(n + 1)$ -ary function $h$ from an $n$ -ary base function $f$ and an $(n + 2)$ -ary inductive-step function $g$ as $\texttt{[}\texttt{v}_n\texttt{\ }f\texttt{\ }g\texttt{]}$ .

[edit]

Constructing primitive recursive functions

A function is primitive recursive if, and only if,

it is a primitive function, or
it can be defined by (generalized) composition of primitive recursive functions, or
it can be defined by (generalized) recursion from primitive recursive functions.

At first glance, it might seem that the class of primitive recursive functions is quite limited, but it actually includes a large variety of familiar functions, as section 3 in the handout and the sections that follow it will reveal.

[edit]

Encoding

In trying to compare primitive recursive functions, as a model of computation, with (say) finite automata, there is initially a kind of mismatch, since a finite automaton takes a string as input and delivers a Boolean value as output, whereas a primitive recursive function takes non-negative integers as inputs and delivers a non-negative integer as output. However, we can use the idea of encoding to patch over the connection. In section 4 of the handout, we see how to encode Boolean values as non-negative integers (and decode non-negative integers, uniquely, as Boolean values, if necessary). So functions with Boolean inputs or outputs can be modelled by, or even identified with, functions with numeric inputs or outputs.

In section 7, we'll see that strings (of any specified alphabet) can also be encoded into non-negative integers, and non-negative integers can be decoded into strings. So the kinds of "functions" that are computed by finite automata -- singulary functions taking strings as arguments and returning Boolean values -- can likewise be modelled by singulary functions taking non-negative integers as arguments and returning non-negative integers as values.

[edit]

Study questions

Find functions $f$ and $g$ such that double is $\texttt{[}\texttt{v}_0\texttt{\ }f\texttt{\ }g\texttt{]}$ .
Find functions $f$ and $g$ such that square, the function that outputs the square of its input, is $\texttt{[}\texttt{v}_0\texttt{\ }f\texttt{\ }g\texttt{]}$ .
Prove that the function $f : N^2 \rightarrow N$ defined by $f (x, y) = x 2 - 2 x y + y 2$ is primitive recursive.
Prove that the factorial function is primitive recursive.
Prove that the binary xor ("exclusive or") function, which returns 1 when its arguments are both zero or both truish, 0 when one of its arguments is zero and the other truish, is primitive recursive.

[edit]

Proposed Solutions

Since $x^2 - 2xy + y^2 = (x - y)^2 = \texttt{square}(\texttt{disparity}(x,y))$ , we have $f \equiv \texttt{[}\circ_2^1 \ \texttt{square} \ \texttt{disparity} \texttt{]}.$