Lecture 6: Inductive Definitions: BNF

Inductively-Defined Data

A data type is

• a set of values and
• a set of operations on those values.

If the number of possible values is finite, they can be enumerated.  But in many cases, the data we care about might have an infinite number of possibilities which obviously can't be enumerated.  (Quick: how many syntactically valid C++ programs are there?)  We need a method of specifying these values so that we can define operations on them.

Review: Inductive Specification

Suppose that we want to specify the set of natural numbers:

1. The number 0 is in the set
2. The number 1 is in the set
3. The number 2 is in the set
4. and so on.

This specification relies on the user to determine the pattern and continue it.  What if the user is a computer?

We can be more specific about the pattern by writing it this way:

1. The number 0 is in the set.
2. If n is in the set, then n + 1 is in the set.

Using this definition, we can generate all of the natural numbers.

Questions

1. Using this inductive definition of natural numbers, convince me that 4 is a natural number.
2. Give the inductive definition for a list of numbers (its in the book, but don't peek).  Show me that (4 3 2 1) is a list using your definition.

Backus-Naur Form

Inductive specifications are so plentiful that computer scientists have developed a specialized notation for describing them (In case it hasn't occurred to you yet, most of computer science is about notation in one form or another).  The notation is called Backus-Naur Form or BNF.  You'll see BNF discussed in a number of forums and people will just expect that you know what BNF is.  You've probably seen and used BNF notation in CS 236, but perhaps without calling it such.

BNF has three major parts:

1. terminals, which require no further definition,
2. non-terminals which are defined in terms of other non-terminals and terminals, and
3. productions which, for each non-terminal, precisely state how it is constructed.

You will sometimes see terminals ignored altogether.  Non-terminals are sometimes called syntactic categories.  Productions are sometimes called rules.

Here is the BNF for a list of numbers:

   <list-of-numbers> ::= ()   
   <list-of-numbers> ::= (<number> . <list-of-numbers>)   
 

A few things to note about this definition:

• (, ), and . are the terminals used in this definition.
• <list-of-numbers> is a non-terminal.  We denote non-terminals by surrounding them with angle brackets.
• ::= is the symbol denoting definition and is read "...is defined to be..."

As you can see from the above definition, there can be more than one rule for any non-terminal.  This happens so often that there is a special notation for it:

   <list-of-numbers> ::= ()   
                       | (<number> . <list-of-numbers>)   
 

The vertical bar, | is read "...or...".

One final piece of notation is called the Kleene star (sometimes called star closure), denoted by {...}*.  This notation says to repeat whatever is in the brackets zero or more times.  Using the star closure, we can define a list of numbers simply as:

   <list-of-numbers> ::= ( {<number>}* )   
 

Note that this version of the BNF does not use the dot-paren notation for lists like the other versions.  In this course, either form will be acceptable.

A variation of star closure is the Kleene plus, denoted by {...}+.  Plus closure differs from star closure because the structure in the brackets must appear at last once.

Questions

1. What would we get if we substituted plus closure for star closure in the last definition of lists?

Syntactic Derivation

We can use our inductive definitions to prove that a given element is (or is not) a member of a particular data type.  For example, consider the list (4 . (3 . ())).  We can use syntactic derivation prove it is a member of the data type <list-of-numbers>:

    <list-of-numbers>
    (<number> . <list-of-numbers>)
    (4 . <list-of-numbers>)
    (4 . (3 . <list-of-numbers>))
    (4 . (3 . ()))

If more than one subtitution can be made at a time, the order in which we make them is not important.

Using BNF to Specify Data

We have seen how one can specify a list of numbers.  BNF can be used to specify other things as well.  For example, we can specify a binary tree with numeric leaves and symbols at the nodes as:

   <tree> ::= <number>   
            | (<symbol> <tree> <tree>)   
 

This BNF specification describes trees that look like the following:

    1
    (foo 1 2)
    (bar (foo 1 2) (fuz 3 4))
    (baz 1 (foo (buz 3 4) 5))

We will see many more examples of BNF throughout the course.  One important use is specifying the syntax of programming languages.  It may seem odd that a method we just described as being useful for specifying data types would be useful for specifying programming language syntax, but remember: a compiler is a program that treats other programs as data.  In other words, programming language syntax is just another data type.

For example, here is the syntax for Java. (This example is written in a modified form of BNF where nonterminals are written without < or > and terminals are denoted with quotation marks.

Recursive Programming and Inductive Types

When data types are defined inductively, the most natural programming structure for processing them is recursion.  Presumably, you've talked about recursion in earlier courses such as CS 235 and 236.

Example: Finding powers of numbers

Suppose that we have a series of functions for finding the power of a number x.

    pow0(x) = 1
    pow1(x) = x         = x * pow0(x)
    pow2(x) = x * x     = x * pow1(x)
    pow3(x) = x * x * x = x * pow2(x)
    ...

We can turn this into something more usable by creating a variable for the power and making the pattern explicit:

    pow(0,x) = 1
    pow(n,x) = x * pow(n-1,x)

In fact, there are programming languages that let you write the recursive equation exactly like this!

In Scheme, we would write:

(define pow
  (lambda (n x)
    (if (zero? n)
        1
        (* x (pow (- n 1) x)))))

Remember, the fundamental idea behind recursion is that if a problem can be defined in terms of a similar, yet smaller problem, recursion is a good tool for solving it.

Question

Here is a question to think about:

1. Show how to write a curried version of pow.  Can you use thecurried version of pow to write procedures for squaring and cubing a number?

Structure of Recursive Programs

Every recursive program consists of:

1. one or more base cases, and
2. one or more recursive cases.

Each recursive case consists of:

1. splitting the data into smaller pieces, for example, with car and cdr,
2. handling the pieces, often with recursive calls, and
3. combining the results into a single result.

Deriving Programs from BNF Specifications

BNF can serve as a guide for defining programs that process data types.

Example: Lists of Numbers

Recall our earlier definition of <list-of-numbers>:

   <list-of-numbers> ::= ()   
                       | (<number> . <list-of-numbers>)   
 

This BNF definition can serve as a pattern for defining programs that operate on lists of numbers.

For example, suppose we wish to define a program for determining the length of a list of numbers.  The pattern for a simple function is:

(define list-length
  (lambda (lon)
    ...
  ))

The first step is to fill in this framework with the behavior to take when the list is empty (the first alternate in the BNF specification):

(define list-length
  (lambda (lon)
    (if (null? lon)
        0
        ...
    )))

The length of the empty list is 0.

Next, we start on the remaining arm. Since that arm is defined in terms of <list-of-numbers>, we know that there will be a recursive call.  The BNF for this arm states the data must in this case be a pair, so we know how to take it apart: with car and cdr.  The car of the pair is a single number, which obviously has length 1. The cdr of the pair is itself a <list-of-numbers>, which tells us that we need to recurse on that part.  Adding the length of the car (1) and the length of the cdr (what we get back from a recursive call to list-length) gives us the length of the data:

(define list-length
  (lambda (lon)
    (if (null? lon)
        0
        (+ 1 (list-length (cdr lon)))
    )))

This completes the definition of list-length.

Make sure you understand the other examples in the book (Section 1.2.1).

Examples: Lists of Symbols

There are three important examples in the book which we will go over here, the definitions of remove-first, remove, and subst (next lecture).  These are important for two reasons: (1) they illustrate some important points about recursive programming, and (2) they will be used later in the book and in the homework.

The first step is to write down the BNF for a list of symbols.  Not surprisingly, it is very similar to the BNF for a list of numbers:

   <list-of-symbols> ::= ()   
                       | (<symbol> . <list-of-symbols>)   
 

The remove-first Function

The remove-first procedure removes the first occurrence of a particular symbol from a list of symbols.  We start with the familiar pattern:

(define remove-first
  (lambda (s los)
    ...
  )))

The function remove-first takes two arguments, a symbol to remove and a list of symbols.  If the list is empty, the list with the symbol removed is still empty!

(define remove-first
  (lambda (s los)
    (if (null? los)
        '()
        ...
    )))

What if los is not empty?  There are two cases, either the first element in los is the symbol we want to remove, or it is not.  If it's the one we want to remove, we simply return the tail of the list:

(define remove-first
  (lambda (s los)
    (if (null? los)
        '()
        (if (eq? (car los) s)
            (cdr los)
            ...
        ))))

If the first element of los is not the symbol we want to remove, then we want to return a list that has that first element at the front of what we get when we remove the symbol from the tail of los.  Scheme's function cons does exactly that.  It inserts a single item (parameter 1) at the head of a list (parameter 2):

(define remove-first
  (lambda (s los)
    (if (null? los)
        '()
        (if (eq? (car los) s)
            (cdr los)
            (cons (car los)
                  (remove-first s (cdr los)))
        ))))

The remove Function

The function remove also takes two arguments: a symbol to remove and a list of symbols.  However, remove removes all occurrences of the symbol, not just the first.  The structure of remove-first and remove are similar, in fact we recognize that if the list is empty, we still return the empty list.  There are still two cases to consider when the list isn't empty.  When the symbol isn't the first member of the list, we certainly want to do the same thing, keep the symbol and recurse.  This is done most easily with cons:

(define remove
  (lambda (s los)
    (if (null? los)
        '()
        (if (eq? (car los) s)
            ...
            (cons (car los)
                  (remove s (cdr los)))
        ))))

When the symbol to remove is the same, we still want to throw it away, but we must continue removing the symbol from the result, so we recurse:

(define remove
  (lambda (s los)
    (if (null? los)
        '()
        (if (eq? (car los) s)
            (remove s (cdr los))
            (cons (car los)
                  (remove s (cdr los)))
        ))))

Review

This page is a shortened outline of how to write recursive code from a BNF

Last updated at 11:25 am on Tuesday, August 21, 2007.