User Tools

Site Tools


rec

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

rec [2015/10/08 15:20] (current)
Line 1: Line 1:
 +====== Recursive programming and pattern matching ======
  
 +
 +===== Recursive definitions =====
 +
 +Sometimes you would like to mention the name of the function you are defining, within its own body. This is not allowed by default:
 +
 +<code ocaml>
 +# let f x = f x;;
 +Unbound value f
 +</​code>​
 +
 +To define a //​recursive//​ function, you have to declare it through the keyword ''​rec''​. ​
 +For example, to define the factorial function:  ​
 +
 +<code ocaml>
 +# let rec fact x = 
 +  if x=0 then 1 
 +  else x * fact (x-1);;
 +  ​
 +val fact : int -> int = <fun>
 +
 +# fact 5;;
 +- : int = 120
 +</​code>​
 +
 +Note that integer arithmetic is subject to overflows.
 +On 32-bit machines, the values of type ''​int''​ are integer numbers from โˆ’2<​sup>​30</​sup>​ to 2<​sup>​30</​sup>​โˆ’1,​ that is โˆ’1073741824 to 1073741823.
 +Some architectures may support a wider range of integer values.
 +
 +<code ocaml>
 +# fact 12;;
 +- : int = 479001600
 +
 +# fact 13;;
 +- : int = -215430144
 +</​code>​
 +
 +However, arbitrary-precision arithmetic can be easily recovered through the OCaml libraries:
 +
 +<code ocaml>
 +#  #load "​nums.cma";;​
 +open Num;;
 +
 +#let rec fact' = fun x ->
 +      if x =/ Int 0 then Int 1 else x */ fact' (x -/ Int 1);;
 +
 +val fact' : Num.num -> Num.num = <fun>
 +
 +string_of_num (fact' (Int 13));;
 +# - : string = "​6227020800"​
 +</​code>​
 +
 +Note that our factorial function may //​diverge//,​ i.e. loop forever ​
 +What happens in practice is that the Ocaml interpreter signals a run-time error, ​
 +giving us a hint of what has gone wrong:
 +
 +<code ocaml>
 +# fact (-1);;
 +Stack overflow during evaluation (looping recursion?​).
 +</​code>​
 +
 +This is another example of a function that never terminates (without even producing a runtime error):
 +<code ocaml>
 +let rec f x = if x=0 then 1 else f x;;
 +# val f : int -> int = <fun>
 +
 +# f 2
 +(loops forever)
 +</​code>​
 +
 +Being a dialect of [[wp>​ML_(programming_language)|ML]],​ OCaml features a
 +[[wp>​Evaluation_strategy#​Call_by_value|call-by-value]] (or //eager//) evaluation strategy.
 +This means that the argument of a function will always be evaluated, even if unused in the body of the function.
 +
 +<code ocaml>
 +(fun x -> 1) (f 2);;
 +(loops forever)
 +</​code>​
 +
 +
 +Sometimes it is convenient to define functions by //mutual recursion//,​
 +that is when the definition of ''​f''​ depends on the definition of ''​g''​
 +and viceversa.
 +For example, testing whether an integer is odd or even can be implemented as follows:
 +
 +<code ocaml>
 +# let rec even n = if n=0 then true else odd (n-1)
 +  and odd n = if n=0 then false else even (n-1);;
 +
 +val even : int -> bool = <fun>
 +val odd : int -> bool = <fun>
 +</​code>​
 +
 +\\
 +
 +===== Tail recursion =====
 +
 +Consider the following recursive function:
 +<code ocaml>
 +# let rec foo x =
 +    if x=0 then 1
 +    else 1 + foo (x-1);;
 +
 +val foo : int -> int = <fun>
 +</​code>​
 +
 +Let's apply it:
 +<code ocaml>
 +# foo 10
 + - : int = 11
 +</​code>​
 +
 +Actually, ''​foo x''​ computes the successor of ''​x''​ if ''​x''​ is non-negative;​
 +otherwise, it diverges.
 +
 +Let's now try with a bigger input:
 +<code ocaml>
 +# foo 1000000
 +Stack overflow during evaluation (looping recursion?​).
 +</​code>​
 +
 +What happened ?
 +Each recursive call caused a new activation record to be pushed on the [[wp>​Call_stack|call stack]].
 +When the call stack growns too much, the computation results in a stack overflow.
 +
 +Why do we need to push a new activation record on the call stack ? 
 +Let us examine the branch of the if-then-else where the recursive call is made:
 +<code ocaml>
 +  ...
 +  else 1 + foo (x-1)
 +</​code>​
 +
 +To evaluate the expression ''​1 + foo (x-1)'',​ the interpreter:​
 +  - evaluates ''​x-1''​
 +  - pushes a new frame for ''​foo''​ on the call stack, contanining the value of ''​x-1''​ and the return point
 +  - executes ''​foo (x-1)''​
 +  - places the return value in the activation record of the caller
 +  - pops the frame from the call stack
 +  - adds 1 to the return value
 +
 +So, is it really unavoidable that recursive functions produce a stack overflow on large inputs ?
 +
 +No, there is a class of recursive functions that can crunch large inputs without making the stack overflow.
 +These are the functions where the recursive call happens as the last thing, i.e. they have the form:
 +
 +<code ocaml>
 +let rec foo x =
 +  ...
 +  foo e
 +;;
 +</​code>​
 +
 +These functions are called **tail recursive**.
 +Since the recursive call happens as the very last thing, there is no need to push a new frame on the call stack:
 +the same frame of the caller can be reused by the callee.
 +This allows the compiler to deal with the recursive call in the same way as a while loop.
 +That is, the recursive call is compiled into a jump to the start of the callee code.
 +
 +There is a standard technique to write functions in a tail-recursive manner.
 +This technique uses an additional argument to accumulate the partial results computed by 
 +the recursive function.
 +
 +Let us consider again the function ''​foo''​.
 +We write a function ''​foo2''​ which uses two arguments.
 +The first argument is the same ''​x''​ as in ''​foo''​.
 +The second argument ''​acc''​ accumulates the results.
 +
 +<code ocaml>
 +# let rec foo2 x acc =
 +  if x=0 then acc
 +  else foo2 (x-1) (acc+1);;
 + 
 +val foo2 : int -> int -> int = <fun>
 +</​code>​
 +
 +We can now rephrase ''​foo''​ in a tail-recursive manner.
 +It suffices to apply ''​foo2'',​ with the initial accumulator equal to 1 (the return value in the base case).
 +
 +<code ocaml>
 +# let foo' x = foo2 x 1;;
 +val foo' : int -> int = <fun>
 +</​code>​
 +
 +Let's try to feed ''​foo'''​ with a big input:
 +<code ocaml>
 +# foo' 1000000
 +- : int = 1000001
 +</​code>​
 +
 +Since the function ''​foo2''​ will only be used by ''​foo''',​ it is better to 
 +hide it through a nested let-definition:​
 +
 +<code ocaml>
 +# let foo' x = 
 +  let rec foo2 x acc =
 +    if x=0 then acc
 +    else foo2 (x-1) (acc+1)
 +  in foo2 x 1;;
 +
 +val foo' : int -> int = <fun>
 +</​code>​
 +
 +Let us now consider a more complex example.
 +The function ''​sumsq''​ computes the sum of the first ''​x''​ squares:
 +
 +<code ocaml>
 +# let rec sumsq x = 
 +  if x=0 then 0
 +  else x*x + sumsq (x-1);;
 +
 +val sumsq : int -> int = <fun>
 +</​code>​
 +
 +Note that ''​sumsq''​ is not tail recursive.
 +Let us feed it with a big input:
 +<code ocaml>
 +# sumsq 1000000;;
 +Stack overflow during evaluation (looping recursion?​).
 +</​code>​
 +
 +We can exploit the accumulator technique to make ''​sumsq''​ tail-recursive.
 +<code ocaml>
 +# let sumsq' x =
 +  let rec sumsq2 x acc =
 +    if x=0 then acc
 +    else sumsq2 (x-1) (acc+x*x)
 +  in sumsq2 x 0;;
 +  ​
 +val sumsq' : int -> int = <fun>
 +</​code>​
 +
 +Let us now try it (on 32-bit machines, you will obtain a negative result):
 +<code ocaml>
 +# sumsq' 1000000;;
 +- : int = 333333833333500000
 +</​code>​
 +
 +To recover a precise result, you can use arbitrary-precision arithmetic:
 +<code ocaml>
 +# let sumsq''​ = fun x ->
 +  let rec sumsq2 x acc =
 +      if x =/ Int 0 then acc 
 +      else sumsq2 (x -/ Int 1) (x */ x +/ acc)
 +  in sumsq2 x (Int 0);;
 +
 +val sumsq''​ : Num.num -> Num.num = <fun>
 +
 +# sumsq''​ (Int 1000000);;
 +- : Num.num = Int 333333833333500000
 +</​code>​
 +
 +\\
 +
 +===== Pattern matching =====
 +
 +Pattern matching is another peculiarity of functional programming.
 +We shall see in the next two lectures how it can be fully exploited to
 +define functions on lists and recursive data types.
 +Here, we mainly use pattern matching to write function definitions in a cleaner way.
 +
 +As a first example, let us consider the Fibonacci function:
 +<code ocaml>
 +# let rec fib = fun n -> 
 +    if n=0 then 0 
 +    else if n=1 then 1 
 +    else fib (n-1) + fib(n-2);;
 +    ​
 +val fib : int -> int = <fun>
 +</​code>​
 +
 +This can be made more readable with pattern matching:
 +<code ocaml>
 +# let rec fib = fun n -> match n with
 +    0 -> 0
 +  | 1 -> 1
 +  | n -> fib (n-1) + fib(n-2);;
 +</​code>​
 +
 +This is even more readable after some syntactic sugar.
 +The keyword ''​function''​ below allows us to write ''​function patterns''​ as a shorthand for ''​fun x -> match x with patterns''​):​
 +<code ocaml>
 +# let rec fib = function
 +    0 -> 0
 +  | 1 -> 1
 +  | n -> fib (n-1) + fib(n-2);;
 +</​code>​
 +
 +Writing nested if-then-else becomes quiclky unreadable as the degree of nesting increases.
 +Consider, for instance, the following (verbose) definition of the XOR function:
 +<code ocaml>
 +# let xor x y = 
 +    if x then (if y then false else true) 
 +    else (if y then true else false);;
 +val xor : bool -> bool -> bool = <fun>
 +</​code>​
 +
 +Pattern matching allows here for a cleaner definition:
 +<code ocaml>
 +# let xor = fun x -> match x with
 +  (false,​false) -> false 
 +| (false,​true) ​ -> true
 +| (true,​false) ​ -> true
 +| (true,​true) ​  -> false;;
 +
 +val xor : bool * bool -> bool = <fun>
 +</​code>​
 +
 +We can simplify definition of the xor function
 +by using //​variables//​ within patterns.
 +
 +<code ocaml>
 +# let xor = function
 +  (false,y) -> y
 +| (true,​y) ​ -> not y;;
 +
 +val xor : bool * bool -> bool = <fun>
 +</​code>​
 +
 +The wildcard ''​_''​ (underscore) matches every pattern.
 +As an example, we define a function that, given two booleans x and y, computes x => y (classical implication).
 +
 +<code ocaml>
 +# let imp = function
 +    (true,​false) -> false
 +  | _ -> true;;
 +
 +val imp : bool * bool -> bool = <fun>
 +</​code>​
 +
 +As a further example, we define the predecessor function on natural numbers:
 +
 +<code ocaml>
 +# let pred x = match x with 
 +  0 -> 0
 +| _ -> x-1;;
 +
 +val pred : int -> int = <fun>
 +</​code>​
 +
 +Patterns may have arbitrary boolean //guard expressions//​ associated with them, 
 +such that a pattern matches only when the guard expression evaluates to ''​true''​.
 +
 +Let us use guards to write a function that computes the sign of a multiplication.
 +<code ocaml>
 +# let sgn n m = match (n,m) with
 +  (x,y) when x>0 && y>0 -> "​+"​
 +| (x,y) when x<0 && y<0 -> "​+"​
 +| (0,_) -> "​0"​
 +| (_,0) -> "​0"​
 +| _ -> "​-";;​
 +
 +val sgn : int -> int -> string = <fun>
 +</​code>​
 +
 +\\
 +
 +===== Exercises =====
 +
 +[[ex-rec|LIP assignment #2]]
rec.txt ยท Last modified: 2015/10/08 15:20 (external edit)