3: Loops

3.1: A model of the store

3.2: Local variable declarations and assignments

C local variable declaration
t x = v ;
C uninitialised local variable declaration
t x ;
C assignment statement
x = e ;
C add four numbers
int main( void ) {
  int A =   17 ;
  int B =    3 ;
  int C =    1 ;
  int D = 1000 ;
  A = A + B ;
  A = A + C ;
  A = A + D ;
  printf( "%d\n", A ) ;
  return 0 ;
}

3.3: While loops

SML leap
(* leap : int -> int *)
fun leap y = if y mod 4 <> 0
                then leap (y+1)
                else y ;
C recursive leap
int leap( int y ) {
  if( y % 4 != 0 ) {
    return leap( y+1 ) ;
  } else {
    return y ;
  }
}

Answer to exercise 3.2

SML extended leap
(* leap : int -> int *)
fun leap y = if y mod 4 <> 0 orelse
                y mod 100 = 0 andalso y mod 400 <> 0
                then leap (y+1)
                else y ;
C recursive extended leap
int leap( int y ) {
  if( (y % 4 != 0) ||
      (y % 100 == 0 && y % 400 != 0) ) {
    return leap( y+1 ) ;
  } else {
    return y ;
  }
}
C recursive leapie
int leap( int y ) {
  if( y % 4 != 0 ) {
    return leap( y+1 ) ;
  } else {
    return y ;
  }
}
SML non-tail recursion
(* fac : int -> int *)
fun fac n = if n > 1
               then n * fac (n-1)
               else 1 ;

3.3.1: Single argument tail recursion

C while statement
while( p ) {
  S
}
SML single argument tail recursion schema
(* f : t -> t_r *)
fun f x
    = if p
         then f g
         else h ;
C single argument while-schema
t_r f( t x ) {
  while( p ) {
    x = g ;
  }
  return h ;
}
C iterative leap
int leap( int y ) {
  while( y % 4 != 0 ) {
    y = y+1 ;
  }
  return y ;
}

3.3.2: Multiple argument tail recursion

SML multiple argument tail recursion schema
(* f : (t_1* ... t_n) -> t_r *)
fun f (x_1, ... x_n)
    = if p
         then f g
         else h ;
C multiple argument while-schema
t_r f( t_1 x_1, ... t_n x_n ) {
  while( p ) {
    (x_1, ... x_n) = g ;
  }
  return h ;
}
C multiple assignment
(x_1, ... x_n) = g ;  /* incorrect C */
SML modulus curried
(* modulus : int -> int -> int *)
fun modulus m n = if m >= n
                     then modulus (m - n) n
                     else m : int ;
SML modulus tupled arguments
(* modulus : int*int -> int *)
fun modulus (m,n) = if m >= n
                       then modulus (m - n,n)
                       else m : int ;
C incorrect iterative modulus
int modulus( int m, int n ) {
  while( m >= n ) {
/* ! */   (m,n) = (m - n,n) ;
  }
  return m ;
}
C incorrect multiple assignment
(m,n) = (m - n,n) ;

C two single assignments
m = m - n ;
n = n ;
C iterative modulus
int modulus( int m, int n ) {
  while( m >= n ) {
    m = m - n ;
  }
  return m ;
}
SML euclid tupled arguments
(* euclid : int*int -> int *)
fun euclid (m,n) = if n > 0
                      then euclid (n,m mod n)
                      else m ;
C incorrect iterative euclid
int euclid( int m, int n ) {
  while( n > 0 ) {
/* ! */   (m,n) = (n,m % n) ;
  }
  return m ;
}
C incorrect multiple assignment with mutual dependency
m = n ;
n = m % n ;   /* WRONG */
C incorrect multiple assignment with mutual dependency

m = n ;
n = m % n ;   /* WRONG */
C iterative euclid
int euclid( int m, int n ) {
  while( n > 0 ) {
    const int old_n = n ;
    n = m % old_n ;
    m = old_n ;
  }
  return m ;
}

3.3.3: Non-tail recursion: factorial

SML factorial
(* fac : int -> int *)
fun fac n = if n > 1
               then n * fac (n-1)
               else 1 ;
C recursive factorial
int fac( int n ) {
  if( n > 1 ) {
    return n * fac (n-1) ;
  } else {
    return 1 ;
  }
}
SML factorial with accumulator
(* fac_accu : int -> int -> int *)
fun fac_accu n b = if n > 1
                      then fac_accu (n-1) (n*b)
                      else b ;
C incorrect iterative factorial
int fac_accu( int n, int b ) {
  while( n > 1 ) {
/* ! */   (n,b) = (n-1,n*b) ;
  }
  return b ;
}
C iterative factorial
int fac_accu( int n, int b ) {
  while( n > 1 ) {
    b = n*b ;
    n = n-1 ;
  }
  return b ;
}
C abstraction on top of fac_accu
int fac( int n ) {
  return fac_accu( n, 1 ) ;
}
C fac after inlining
int fac( int n ) {
  int b = 1 ;
  while( n > 1 ) {
    b = n*b ;
    n = n-1 ;
  }
  return b ;
}

3.3.4: More on assignments

C body of fac
b = n*b ;
n = n-1 ;
C fac after extensive inlining
int absurd_fac( int n ) {
  int b = n ;
  while( --n ) {
    b = n*b ;
  }
  return b ;
}

3.3.5: Breaking out of while-loops

SML bisection
(* bisection : (real->real) -> real -> real -> real *)
fun bisection f l h
    = let
         val m = (l + h) / 2.0
         val f_m = f m
      in
         if absolute f_m < eps
(* 1 *)     then m
            else if absolute (h-l) < delta
(* 2 *)             then m
                    else if f_m < 0.0
(* 3 *)                  then bisection f m h
(* 4 *)                  else bisection f l m
      end ;
SML general tail recursion schema
(* f : (t_1* ... t_n) -> t_r *)
fun f (x_1, ... x_n)
    = let
         val y_1 = z_1 (* y_1 : t_y_1 *)
         ...
         val y_j = z_j (* y_j : t_y_j *)
      in
         if p_1
            then q_1
            else
                 ...
                 if p_k
                    then q_k
                    else q_k+1
      end ;
C general while-schema
t_r f( t_1 x_1, ... t_n x_n ) {
  t_y_1 y_1 ;
  ...
  t_y_j y_j ;
  while( true ) {
    y_1 = z_1 ;
    ...
    y_j = z_j ;
    if( p_1 ) q_1 ;
    else if( p_2 ) q_2 ;
    ...
    else if( p_k ) q_k ;
    else q_k+1 ;
  }
}
SML bisection tupled arguments
(* bisection : (real->real)*real*real -> real *)
fun bisection(f,l,h)
    = let
         val m = (l + h) / 2.0  (* m   : real *)
         val f_m = f m          (* f_m : real *)
      in
         if absolute f_m < eps
(* 1 *)     then m
            else if absolute (h-l) < delta
(* 2 *)             then m
                    else if f_m < 0.0
(* 3 *)                     then bisection(f,m,h)
(* 4 *)                     else bisection(f,l,m)
      end ;
C iterative bisection
double bisection( double(*f)( double ),
                  double l, double h ) {
  double m ;
  double f_m ;
  while( true ) {
    m = (l+h)/2.0 ;
    f_m = f(m) ;
    if( absolute( f_m ) < eps ) {
      return m ;
    } else if( absolute( h-l ) < delta ) {
      return m ;
    } else if( f_m < 0.0 ) {
      l = m ;
    } else {
      h = m ;
    }
  }
}

Exercise 3.10

C alternative bisection
double bisection( double(*f)( double ),
		  double l, double h ) {
  double m = (l+h)/2.0 ;
  double f_m = f(m) ;
  while( ! ( absolute( f_m ) < eps ||
	     absolute( h-l ) < delta) ) {
    /*  body of the while-loop */
  }
  return m ;
}

Answer to exercise 3.10

C body of the while-loop
if( f_m < 0.0 ) {
  l = m ;
} else {
  h = m ;
}
m = (l+h)/2.0 ;
f_m = f(m) ;

Exercise 3.11

C main program for bisection
int main( void ) {
  double x = bisection( parabola, 0.0, 2.0 ) ;
  printf("The answer is %f\n", x ) ;
  return 0 ;
}

Answer to exercise 3.11

C inlined iterative bisection
int main( void ) {
  double x ;
  double l = 0.0 ;
  double h = 2.0 ;
  double m ;
  double f_m ;
  while( true ) {
    m = (l+h)/2.0 ;
    f_m = parabola(m) ;
    if( absolute( f_m ) < eps ) {
      x = m ;
      break ;
    } else if( absolute( h-l ) < delta ) {
      x = m ;
      break ;
    } else if( f_m < 0.0 ) {
      l = m ;
    } else {
      h = m ;
    }
  }
  printf("The answer is %f\n", x ) ;
  return 0 ;
}

3.4: For loops

SML arithmetic sequence
(* -- : int*int -> int list *)
infixr 5 -- ;
fun (m -- n)
    = let
         fun up   i = if i > n
                         then []
                         else i :: up (i+1)
         fun down i = if i < n
                         then []
                         else i :: down (i-1)
      in
         if m <= n
            then up   m
            else down m
      end ;
SML arithmetic sequence examples
(1--3) = [1,2,3] ;
(0--0) = [0] ;
(1--0) = [1,0] ;
SML factorial with arithmetic sequence
(* fac : int -> int *)
fun fac n = prod (1--n) ;
SML foldl
(* foldl : ('a->'b->'a) -> 'a -> 'b list -> 'a *)
fun foldl f r []      = r
  | foldl f r (x::xs) = foldl f (f r x) xs ;
SML prod
(* prod : int list -> int *)
fun prod xs = foldl mul 1 xs ;
SML mul
(* mul : int -> int -> int *)
fun mul x y = x * y : int ;
SML foldl schema
(* f : t_1 -> ... -> t_j -> t_r *)
fun f x_1 ... x_j
    = foldl g b (m -- n) ;
C increasing for schema
t_r f( t_1 x_1, ... t_j x_j ) {
  int i ;
  t_r a = b ;
  for( i = m; i <= n; i++ ) {
    a = g( a, i ) ;
  }
  return a ;
}
C decreasing for schema
t_r f( t_1 x_1, ... t_j x_j ) {
  int i ;
  t_r a = b ;
  for( i = m; i >= n; i-- ) {
    a = g( a, i ) ;
  }
  return a ;
}

3.4.1: Factorial using a for-loop

SML explicitly folding factorial
(* fac : int -> int *)
fun fac n = foldl mul 1 (1--n) ;
C iterative factorial with for statement
int fac( int n ) {
  int i ;
  int accu = 1 ;
  for( i = 1; i <= n; i++ ) {
    accu = accu * i ;
  }
  return accu ;
}

3.4.2: Folding from the right

SML foldr
(* foldr : ('a->'b->'b) -> 'b -> 'a list -> 'b *)
fun foldr f r []      = r
  | foldr f r (x::xs) = f x (foldr f r xs) ;
SML foldr schema
(* f : t_1 -> ... -> t_j -> t_r *)
fun f x_1 ... x_j
    = foldr g b (m -- n) ;
C increasing right folding for schema
t_r f( t_1 x_1, ... t_j x_j ) {
  int i ;
  t_r a = b ;
  for( i = n; i <= m; i ++ ) {
    a = g( i, a ) ;
  }
  return a ;
}

3.5: Generalizing loops and control structures

3.5.1: Combining foldl with map: sum of squares

SML square
(* square : int -> int *)
fun square x = x * x : int ;
SML sum
(* sum : int list -> int *)
fun sum xs = foldl add 0 xs ;
SML add
(* add : int -> int -> int *)
fun add x y = x + y : int ;
SML map
(* map : ('a->'b) -> 'a list -> 'b list *)
fun map h []      = []
  | map h (x::xs) = h x :: map h xs ;
SML sum of squares
(* sum_of_squares : int -> int *)
fun sum_of_squares n
    = sum (map square (1 -- n)) ;
SML sum of squares with foldl exposed
(* sum_of_squares : int -> int *)
fun sum_of_squares n
    = foldl add 0 (map square (1 -- n)) ;
SML sum of squares with map removed
(* add_square : int -> int -> int *)
fun add_square b x = add b (square x) ;

(* sum_of_squares : int -> int *)
fun sum_of_squares n
    = foldl add_square 0 (1 -- n) ;
C sum of squares
int add( int x, int y ) {
  return x + y ;
}

int square( int x ) {
  return x * x ;
}

int add_square( int b, int x ) {
  return add( b, square( x ) ) ;
}

int sum_of_squares( int n ) {
  int i ;
  int accu = 0 ;
  for( i = 1; i <= n; i++ ) {
    accu = add_square( accu , i ) ;
  }
  return accu ;
}
C final sum of squares
int sum_of_squares( int n ) {
  int i ;
  int accu = 0 ;
  for( i = 1; i <= n-1; i++ ) {
    accu = accu + (i * i) ;
  }
  return accu ;
}

3.5.2: Combining foldl with filter: perfect numbers

SML perfect
(* perfect : int -> bool *)
fun perfect n = n = sum_of_factors n ;
SML sum of factors predicate
(* rel_prime : int -> int -> bool *)
fun rel_prime n i = n mod i = 0 ;
SML sum of factors
(* sum_of_factors : int -> int *)
fun sum_of_factors n
    = sum (filter (rel_prime n) (1 -- n-1)) ;
SML filter
(* filter : ('a->bool) -> 'a list -> 'a list *)
fun filter p []      = []
  | filter p (x::xs) = if p x
                          then x :: filter p xs
                          else filter p xs ;
SML sum of factors with foldl exposed
(* sum_of_factors : int -> int *)
fun sum_of_factors n
    = foldl add 0 (filter (rel_prime n) (1 -- n-1)) ;
SML incorrect add relative prime
(* add_rel_prime : int -> int -> int *)
fun add_rel_prime b x
    = if (rel_prime n) x
         then add b x
         else b ;
SML sum of factors with filter removed
(* add_rel_prime : int -> int -> int -> int *)
fun add_rel_prime n b x
    = if (rel_prime n) x
         then add b x
         else b ;

(* sum_of_factors : int -> int *)
fun sum_of_factors n
    = foldl (add_rel_prime n) 0 (1 -- n-1) ;
C perfect
bool rel_prime( int n, int i ) {
  return n % i == 0 ;
}

int add_rel_prime( int n, int b, int x ) {
  if( rel_prime( n, x ) ) {
    return add( b, x ) ;
  } else {
    return b ;
  }
}

int sum_of_factors( int n ) {
  int i ;
  int accu = 0 ;
  for( i = 1; i <= n-1; i++ ) {
    accu = add_rel_prime( n, accu, i ) ;
  }
  return accu ;
}

bool perfect( int n ) {
  return sum_of_factors( n ) == n ;
}
C inlining of add_rel_prime in sum_of_factors
int sum_of_factors( int n ) {
  int i ;
  int accu = 0 ;
  for( i = 1; i <= n-1; i++ ) {
    if( rel_prime( n, i ) ) {
      accu = add( accu, i ) ;
    } else {
      accu = accu ;
    }
  }
  return accu ;
}
C final perfect
bool perfect( int n ) {
  int i ;
  int accu = 0 ;
  for( i = 1; i <= n-1; i++ ) {
    if( n % i == 0 ) {
      accu = accu + i ;
    }
  }
  return accu == n ;
}

3.5.3: Nested for statements

SML sum of powers
(* sum_of_powers : int -> int -> int *)
fun sum_of_powers m i
    = sum (map (power i) (0--m)) ;
C sum of powers
int sum_of_powers( int m, int i ) {
  int k ;
  int accu = 0 ;
  for( k = 0; k <= m; k++ ) {
    accu = accu + power( i, k ) ;
  }
  return accu ;
}
SML sum of sum of powers
(* sum_of_sum_of_powers : int -> int -> int *)
fun sum_of_sum_of_powers m n
    = sum (map (sum_of_powers m) (0--n)) ;
C sum of sum of powers
int sum_of_sum_of_powers( int m, int n ) {
  int i ;
  int accu = 0 ;
  for( i = 0; i <= n; i++ ) {
    accu = accu + sum_of_powers( m, i ) ;
  }
  return accu ;
}
C nested sum of sum of powers
int sum_of_sum_of_powers( int m, int n ) {
  int i,k ;
  int accu = 0 ;
  for( i = 0; i <= n; i++ ) {
    for( k = 0; k <= m; k++ ) {
      accu = accu + power( i, k ) ;
    }
  }
  return accu ;
}

Summary

C assignment
x = e
C while
while( p ) {
  S
}
C general form of the for statement
for( I ; p ; N ) {
  S
}
C general form of the most common ascending for loop
for( i=0 ; i<n ; i++ ) {
  S
}
C general form of the most common descending for loop
for( i=n-1 ; i>=0 ; i-- ) {
  S
}

Further exercises

Answer to exercise 3.16

C population count with loop
int pop_count( int n ) {
  int accu = 0 ;
  while( n != 0 ) {
    accu = accu + (n&1) ;
    n = n >> 1 ;
  }
  return accu ;
}

int main( void ) {
  printf( "population count\n");
  printf( "of     0 is %d\n", pop_count( 0 ) ) ;
  printf( "of     9 is %d\n", pop_count( 9 ) ) ;
  printf( "of 65535 is %d\n", pop_count( 65535 ) ) ;
  return 0 ;
}

Answer to exercise 3.17

C power of power program
#include <stdio.h>

int power( int r, int p ) {
  int accu = 1 ;
  while( p != 0 ) {
    accu = accu * r ;
    p = p - 1 ;
  }
  return accu ;
}

int power_of_power( int m, int n ) {
  int accu = 1 ;
  while( n != 0 ) {
    accu = power( m, accu ) ;
    n = n - 1 ;
  }
  return accu ;
}

int main( void ) {
  printf( "power of power\n");
  printf( "0 17: %d\n", power_of_power( 0, 17 ) ) ;
  printf( "1 17: %d\n", power_of_power( 1, 17 ) ) ;
  printf( "2  0: %d\n", power_of_power( 2,  0 ) ) ;
  printf( "2  1: %d\n", power_of_power( 2,  1 ) ) ;
  printf( "2  2: %d\n", power_of_power( 2,  2 ) ) ;
  printf( "2  3: %d\n", power_of_power( 2,  3 ) ) ;
  printf( "2  4: %d\n", power_of_power( 2,  4 ) ) ;
  return 0 ;
}
C inlined power of power function
int power_of_power( int m, int n ) {
  int accu = 1 ;
  while( n != 0 ) {
    int p = accu ;
    int power = 1 ;
    while( p != 0 ) {
      power = power * m ;
      p = p - 1 ;
    }
    accu = power ;
    n = n - 1 ;
  }
  return accu ;
}

Exercise 3.18

C chess output
---------
| |X| |X|
---------
|X| |X| |
---------