2: Functions and numbers

2.1: A model of computation

2.1.1: A computational model for SML programs

2.1.2: A computational model for C programs

C hello world
/* A simple C program, it prints `Hello World' */
int main( void ) {
  printf( "Hello world\n" ) ;
  return 0 ;
}
C printf hello world
printf( "Hello world\n" ) ;
C return 0
return 0 ;

2.1.3: Compiling and executing a C program

SH
cc -o monkey hello.c
SH output
Hello world

2.2: Elementary functions

SML euclid
(* euclid : int -> int -> int *)
fun euclid m n = if n > 0
                    then euclid n (m mod n)
                    else m ;
SML euclid examples
euclid 14 12   = 2 ;
euclid 14 11   = 1 ;
euclid 558 198 = 18 ;
SML function schema
(* f : t_1 -> ... t_n -> t_r *)
fun f x_1 ... x_n
    = if p
         then g
         else h ;
C function schema
t_r f( t_1 x_1, ... t_n x_n ) {
  if ( p ) {
    return g ;
  } else {
    return h ;
  }
}
C euclid
int euclid( int m, int n ) {
  if( n>0 ) {
    return euclid( n, m%n ) ;
  } else {
    return m ;
  }
}
C euclid program
#include <stdio.h>

int euclid( int m, int n ) {
  if( n>0 ) {
    return euclid( n, m%n ) ;
  } else {
    return m ;
  }
}

int main( void ) {
  printf( "%d\n", euclid( 14, 12 ) ) ;
  printf( "%d\n", euclid( 14, 11 ) ) ;
  printf( "%d\n", euclid( 558, 198 ) ) ;
  return 0 ;
}
C include stdio
#include <stdio.h>

2.2.1: The header of a C function, types and identifiers

C euclid header
int euclid( int m, int n )
C main header
int main( void )
C prototypes of main and euclid
int euclid( int m, int n ) ;
int main( void ) ;

2.2.2: The body of a C function and its behaviour

C if-statement
if( p ) {
  T
} else {
  F
}
C no else part
if( p ) {
  T
}
C euclid body
{
  if( n>0 ) {
    return euclid( n, m%n ) ;
  } else {
    return m ;
  }
}
C then statements
return euclid( n, m%n ) ;
C else statements
return m ;
C alternative body for euclid
{
  if( n>0 ) {
    return euclid( n, m%n ) ;
  }
  return m ;
}
C alternative body return-1
return euclid( n, m%n ) ;
C body of main statement 1
printf( "%d\n", euclid( 14, 12 ) ) ;

2.2.3: The execution of a C program

C euclid 14 12 2
euclid( 14, 12 )
C evaluated body of main statement 1
printf( "%d\n", 2 ) ;
C printf output
2

2.2.4: Integers

C bitwise
    (~0) == -1,
(12 & 6) == 4,
(12 | 6) == 14,
(12 ^ 6) == 10
C shift
(12 << 6)  == 768,
(400 >> 4) == 25

2.2.5: Logical operators

C logical
(0 && x) == 0,
(1 && x) == x,
(0 || x) == x,
(1 || x) == 1
C example of &&
x != 0 && y/x < 20
Pascal and
(x <> 0) AND (y/x < 20)

2.2.6: Defining a type for Booleans, typedef and enum

C how to define a boolean
typedef enum { false=0, true=1 } bool ;
C typedef
typedef T bool ;
C general form of an enumeration
enum { i_0, i_1, i_2 ... }
C combination of typedef and enum
typedef enum { i_0, i_1, i_2 ... } t ;
SML scalar datatype declaration
datatype t = i_0 | i_1 | i_2 ... ;
C other use of enumerated types
typedef  enum { Japanese, Spanish, Chinese }  language ;
SML equivalents
datatype language = Japanese | Spanish | Chinese ;

2.3: Characters, pattern matching, partial functions

SML char
type char = string ;
SML eval with pattern matching
(* eval : int -> char -> int -> char -> int -> int *)
fun eval x "+" y "+" z = (x + y) + z
  | eval x "+" y "*" z = x + (y * z)
  | eval x "*" y "+" z = (x * y) + z
  | eval x "*" y "*" z = (x * y) * z : int ;

2.3.1: Implementing pattern matching in C

SML eval with conditionals
(* eval : int -> char -> int -> char -> int -> int *)
fun eval x o1 y o2 z
    = if o1 = "+" andalso o2 = "+"
         then (x + y) + z
         else if o1 = "+" andalso o2 = "*"
                 then x + (y * z)
                 else if o1 = "*" andalso o2 = "+"
                         then (x * y) + z
                         else if o1 = "*" andalso o2 = "*"
                                 then (x * y) * z : int
                                 else raise Match ;
C eval with a cascade of conditionals
int eval( int x, char o1, int y, char o2, int z ) {
  if( o1 == '+' && o2 == '+' ) {
    return (x + y) + z ;
  } else {
    if( o1 == '+' && o2 == '*' ) {
      return x + (y * z) ;
    } else {
      if( o1 == '*' && o2 == '+' ) {
        return (x * y) + z ;
      } else {
        if( o1 == '*' && o2 == '*' ) {
          return (x * y) * z ;
        } else {
          /* raise Match */
        }
      }
    }
  }
}
C eval with else if
int eval( int x, char o1, int y, char o2, int z ) {
  if( o1 == '+' && o2 == '+' ) {
    return (x + y) + z ;
  } else if( o1 == '+' && o2 == '*' ) {
    return x + (y * z) ;
  } else if( o1 == '*' && o2 == '+' ) {
    return (x * y) + z ;
  } else if( o1 == '*' && o2 == '*' ) {
    return (x * y) * z ;
  } else {
    /* raise Match */
  }
}

Answer to exercise 2.2

SML with-line general function schema
(* f : t_1 -> ... t_n -> t_r *)
fun f x_1 ... x_n
    = if p_1
         then g_1
         else if p_2
              then g_2
                   ...
                   else if p_k
                        then g_k
                        else h ;
C general function schema
t_r f( t_1 x_1, ... t_n x_n ) {
  if( p_1 ) {
    return g_1 ;
  } else if( p_2 ) {
    return g_2 ;
    ...
  } else if( p_k ) {
    return g_k ;
  } else {
    return h ;
  }
}
C eval with chain of if statements
int eval( int x, char o1, int y, char o2, int z ) {
  if( o1 == '+' && o2 == '+' ) {
    return (x + y) + z ;
  }
  if( o1 == '+' && o2 == '*' ) {
    return x + (y * z) ;
  }
  if( o1 == '*' && o2 == '+' ) {
    return (x * y) + z ;
  }
  if( o1 == '*' && o2 == '*' ) {
    return (x * y) * z ;
  }
  /* raise Match */
}
C eval with nested if statements
int eval( int x, char o1, int y, char o2, int z ) {
  if( o1 == '+' ) {
    if( o2 == '+' ) {
      return (x + y) + z ;
    } else if( o2 == '*' ) {
      return x + (y * z) ;
    } else {
      /* raise Match */
    }
  } else if( o1 == '*' ) {
    if( o2 == '+' ) {
      return (x * y) + z ;
    } else if( o2 == '*' ) {
      return (x * y) * z ;
    } else {
      /* raise Match */
    }
  } else {
    /* raise Match */
  }
}
SML eval with optimised conditionals
(* eval : int -> char -> int -> char -> int -> int *)
fun eval x o1 y o2 z
    = if o1 = "+"
        then xyadd x y o2 z
        else if o1 = "*"
                then xymul x y o2 z : int
                else raise Match

(* xyadd : int -> int -> char -> int -> int *)
and xyadd x y o2 z
    = if o2 = "+"
         then x + y + z
         else if o2 = "*"
                 then x + y * z : int
                 else raise Match

(* xymul : int -> int -> char -> int -> int *)
and xymul x y o2 z
    = if o2 = "+"
         then x * y + z
         else if o2 = "*"
                 then x * y * z : int
                 else raise Match ;

2.3.2: Partial functions

C completing partial functions
  /* previous statements */
  if( o2 == '*' ) {
    return (x * y) * z ;
  } else {
    abort() ;
  }
} else {
  abort() ;
}
C eval
printf("Arghh, first argument of 'eval' is neither") ;
printf("a '+' nor an '*'; it is '%c'\n", o1 ) ;
abort() ;

2.3.3: Differences and similarities between characters and integers

C character equalities
'a' + 1   == 'b',
'z' - 'a' == 25,
'9' - '0' == 9
C character inequalities
'4' + '5' == 'i',
'4' + '5' != '9'
C print q
printf( "%c\n", 'q' ) ;

Exercise 2.5

C equivalence between characters and integers
int main( void ) {
  char c0 = '0' ;
  int  i0 = '0' ;
  char cq = 113 ;
  int  iq = 113 ;
  printf("'%c' = %d,  '%c' = %d\n", c0, i0, cq, iq ) ;
  return 0 ;
}

Answer to exercise 2.5

C printing characters
'0' = 48,  'q' = 113
C include ctype.h
#include <ctype.h>
SML lower case to upper case
(* makeupper : char -> char *)
fun makeupper c
    = if "a" <= c andalso c <= "z"
         then chr (ord c - ord "a" + ord "A")
         else if "A" <= c andalso c <= "Z"
                 then chr (ord c - ord "A" + ord "a")
                 else c ;
C lower case to upper case
char makeupper( char c ) {
  if( islower( c ) ) {
    return toupper( c ) ;
  } else if( isupper( c ) ) {
    return tolower( c ) ;
  } else {
    return c ;
  }
}

2.4: Real numbers

SML Indian power
(* square : real -> real *)
fun square x : real = x * x ;

(* odd : int -> bool *)
fun odd x = x mod 2 = 1 ;

(* power : real -> int -> real *)
fun power r p
    = if p = 0
         then 1.0 (* Note, this is a real! *)
         else if odd p
                 then r * power r (p-1)
                 else square (power r (p div 2)) ;
SML power table
power 3.0       0 =   1.0 ;
power 5.0       4 = 625.0 ;
power 1.037155 19 =   1.99999 ;
C power program
#include <stdio.h>

typedef enum { false=0, true=1 } bool ;

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

bool odd( int x ) {
  return x % 2 == 1 ;
}

double power( double r, int p ) {
  if( p == 0 ) {
    return 1.0 ;
  } else if( odd( p ) ) {
    return r * power( r, p-1 ) ;
  } else {
    return square( power( r, p/2 ) ) ;
  }
}

int main( void ) {
  printf( "%f\n", power( 3, 0 ) ) ;
  printf( "%f\n", power( 5, 4 ) ) ;
  printf( "%f\n", power( 1.037155, 19 ) ) ;
  return 0 ;
}

2.4.1: Coercions of integers and floating point numbers

C coercion 1
1.0 + 5.0/2.0
C coercion 2
1.0 + 5/2.0
C coercion 3
1.0 + 5/2
C coercion 4
1 + 5/2
C 1.0...02
1.000000000000000222044604925031
C 1.0...04
1.000000000000000444089209850062
C pi...5
345678912.0000000596046447753906
C pi...1
345678912.0000001192092895507812
C 0.9
0.0999999999999999916733273153113
C 1.0
0.1000000000000000055511151231257

2.5: Functions as arguments

2.5.1: Sums

SML sum of progression
(* sum : int -> int -> (int -> real) -> real *)
fun sum i n f = if i > n
                   then 0.0
                   else f i + sum (i+1) n f ;
SML terminal
(* terminal : int -> real *)
fun terminal n = let
                   fun int2real i = real i
                 in
		   sum 1 n int2real
		 end ;
SML terminal with expanded sum
(* terminal : int -> real *)
fun terminal n
    = let
	 fun int2real i = real i
         fun sum' i n = if i > n
                          then 0.0
                          else int2real i + sum' (i+1) n
      in
         sum' 1 n
      end ;
C sum of progression
double sum( int i, int n, double (*f) ( int ) ) {
  if( i > n ) {
    return 0.0 ;
  } else {
    return f( i ) + sum( i+1, n, f ) ;
  }
}
C functional argument declaration
double (*f)( int )
C general functional argument declaration
t_r (*f)( t_1, ... t_n )
SML higher order function type
(t_1 -> ... t_n -> t_r)
C convert int to double
typedef double (*int_to_double_funcs)( int ) ;
SML convert into to real
type int_to_real_funcs = int -> real ;
C terminal
double int2real( int i ) {
  return (double) i ;	/* return i would suffice */
}

double terminal( int n ) {
  return sum( 1, n, int2real ) ;
}

2.5.2: Products

SML product
(* product : int -> int -> (int -> real) -> real *)
fun product i n f = if i > n
                       then 1.0
                       else f i * product (i+1) n f ;
SML factorial
(* factorial : int -> real *)
fun factorial n = let
		    fun int2real i = real i
		  in
		    product 1 n int2real
		  end ;
SML repeat
(* repeat : 'a -> ('b -> 'a -> 'a) ->
            int -> int -> (int -> 'b) -> 'a *)
fun repeat base combine i n f
    = if i > n
         then base
         else combine (f i) (repeat base combine (i+1) n f) ;
SML sum in terms of repeat
(* sum : int -> int -> (int -> real) -> real *)
fun sum i n f
    = let
         fun add x y = x + y
      in
         repeat 0.0 add i n f
      end ;
SML sum equiv
sum = repeat 0.0 add

Answer to exercise 2.15

C repeat
double repeat( double base,
               double (*combine) (double, double),
               int i, int n, double (*f) (int) ) {
  if( i > n ) {
    return base ;
  } else {
    return combine( f( i ),
                    repeat( base, combine, i+1, n, f) ) ;
  }
}
C sum in terms of repeat
double double_add( double x, double y ) {
  return x+y ;
}

double sum( int i, int n, double (*f) (int) ) {
  return repeat( 0.0, double_add, i, n, f ) ;
}

Answer to exercise 2.16

SML nearly phi
(* nearly_phi : int -> real *)
fun nearly_phi n
    = let
         fun constant_one i = 1.0
         fun divide x y = x / (1.0 + y)
       in
         1.0 + repeat 1.0 divide 1 n constant_one
      end ;
C nearly phi
double constant_one( int i ) {
  return 1.0 ;
}

double divide( double x, double y ) {
  return x / (1.0 + y) ;
}

double nearly_phi( int n ) {
  return 1.0 + repeat( 1.0, divide, 1, n, constant_one ) ;
}

2.5.3: An extended example of higher order functions: bisection

SML epsilon and delta
(* eps,delta : real *)
val eps = 0.001 ;
val delta = 0.0001 ;
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
            then m
            else if absolute(h-l) < delta
                    then m
                    else if f_m < 0.0
                            then bisection f m h
                            else bisection f l m
      end ;
SML absolute
(* absolute : real -> real *)
fun absolute x = if x >= 0.0
                    then x
                    else ~x ;
SML parabola
(* parabola : real -> real *)
fun parabola x = x * x - 2.0 ;
SML bisection of parabola
bisection parabola 1.0   2.0 = 1.41406 ;
bisection parabola 0.0 200.0 = 1.41449 ;
bisection parabola 1.2   1.5 = 1.41445 ;
C bisection program
#include <stdio.h>

double absolute( double x ) {
  if( x >= 0 ) {
    return x ;
  } else {
    return -x ;
  }
}

const double eps=0.001, delta=0.0001 ;

double bisection( double (*f)( double ),
                  double l, double h  ) {
  const double m = (l + h ) / 2.0 ;
  const double 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 ) {
    return bisection( f, m, h ) ;
  } else {
    return bisection( f, l, m ) ;
  }
}

double parabola( double x ) {
  return x * x - 2.0 ;
}

int main( void ) {
  printf( "%f\n", bisection( parabola, 1.0,   2.0 ) ) ;
  printf( "%f\n", bisection( parabola, 0.0, 200.0 ) ) ;
  printf( "%f\n", bisection( parabola, 1.2,   1.5 ) ) ;
  return 0 ;
}
C epsilon and delta
const double eps=0.001, delta=0.0001 ;
C dependent constants
const double m = (l + h ) / 2.0 ;
const double f_m = f( m ) ;

Answer to exercise 2.17

SML with-line general function schema with locals
(* 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 g_1
            else if p_2
                    then g_2
                         ...
                         else if p_k
                                 then g_k
                                 else h
      end ;
C general function schema with locals
t_r f( t_1 x_1, ... t_n x_n ) {
  const t_y_1 y_1 = z_1 ;
  ...
  const t_y_j y_j = z_j ;
  if ( p_1 ) {
    return g_1 ;
  } else if ( p_2 ) {
    return g_2 ;
    ...
  } else if ( p_k ) {
    return g_k ;
  } else {
    return h ;
  }
}

Summary

C general form of a function declaration
t_r f( t_1 v_1, ... t_n v_n ) {
  /* constant declarations */
  /* statements */
}
C general form of a constant declaration
const t c = e ;
C general form of a return statement
return e ;
C general form of an if then else statement
if( p ) {
  T
} else {
  F
}
C general form of an if then statement
if( p ) {
  T
}


C general form of a typedef
typedef t i ;
C general form of a typedef for a function
typedef t_r (*i)(t_1, ... t_n) ;
SML general form of an SML function type declaration
type i = t_1 -> ... t_n -> t_r ;
C general form of an enum declaration
typedef enum { i_0, i_1 ... } t ;

Further exercises

Exercise 2.26

C trace Newton Raphson
newton_raphson( parabola, parabola_, 0.001, 1.5 )

Answer to exercise 2.26

SML Newton Raphson
(* newton_raphson : (real->real) -> (real->real) ->
                     real -> real *)
fun newton_raphson f f' eps x
    = let
         val fx = f(x) (* fx : real *)
      in
         if absolute(fx) < eps
            then x
            else newton_raphson f f' eps (x-fx/f'(x))
      end ;
SML parabola and its derivative
(* parabola : real -> real *)
fun parabola  x = x * x - 2.0 ;

(* parabola' : real -> real *)
fun parabola' x = 2.0 * x ;
SML Newton Raphson parabola
newton_raphson parabola parabola' 0.001 1.5 = 1.41421;
newton_raphson parabola parabola' 0.1 200.0 = 1.41624;
C Newton Raphson program
#include <stdio.h>

double absolute( double x ) {
  if( x >= 0 ) {
    return x ;
  } else {
    return -x ;
  }
}

double newton_raphson( double (*f)( double ),
                       double (*f_)( double ),
                       double eps, double x ) {
  const double fx = f( x ) ;
  if( absolute( fx ) < eps ) {
    return x ;
  } else {
    return newton_raphson( f, f_, eps, x - fx/f_(x) ) ;
  }
}

double parabola( double x ) {
  return x * x - 2.0 ;
}

double parabola_( double x ) {
  return 2 * x ;
}

int main( void ) {
  printf( "%f\n", newton_raphson( parabola, parabola_,
                                  0.001, 1.5 ) ) ;
  printf( "%f\n", newton_raphson( parabola, parabola_,
                                  0.1, 200.0 ) ) ;
  return 0 ;
}
C double fx
const double fx = f( x ) ;
C parabola 1.5
const double fx = parabola( 1.5 ) ;