rec

# Differences

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

 — 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: + + + # let f x = f x;; + Unbound value f + ​ + + To define a //​recursive//​ function, you have to declare it through the keyword ''​rec''​. ​ + For example, to define the factorial function:  ​ + + + # let rec fact x = + if x=0 then 1 + else x * fact (x-1);; + ​ + val fact : int -> int = + + # fact 5;; + - : int = 120 + ​ + + Note that integer arithmetic is subject to overflows. + On 32-bit machines, the values of type ''​int''​ are integer numbers from โ2<​sup>​30​ to 2<​sup>​30​โ1,​ that is โ1073741824 to 1073741823. + Some architectures may support a wider range of integer values. + + + # fact 12;; + - : int = 479001600 + + # fact 13;; + - : int = -215430144 + ​ + + However, arbitrary-precision arithmetic can be easily recovered through the OCaml libraries: + + + #  #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 = + + string_of_num (fact' (Int 13));; + # - : string = "​6227020800"​ + ​ + + 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: + + + # fact (-1);; + Stack overflow during evaluation (looping recursion?​). + ​ + + This is another example of a function that never terminates (without even producing a runtime error): + + let rec f x = if x=0 then 1 else f x;; + # val f : int -> int = + + # f 2 + (loops forever) + ​ + + 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. + + + (fun x -> 1) (f 2);; + (loops forever) + ​ + + + 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: + + + # 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 = + val odd : int -> bool = + ​ + + \\ + + ===== Tail recursion ===== + + Consider the following recursive function: + + # let rec foo x = + if x=0 then 1 + else 1 + foo (x-1);; + + val foo : int -> int = + ​ + + Let's apply it: + + # foo 10 + - : int = 11 + ​ + + Actually, ''​foo x''​ computes the successor of ''​x''​ if ''​x''​ is non-negative;​ + otherwise, it diverges. + + Let's now try with a bigger input: + + # foo 1000000 + Stack overflow during evaluation (looping recursion?​). + ​ + + 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: + + ... + else 1 + foo (x-1) + ​ + + 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: + + + let rec foo x = + ... + foo e + ;; + ​ + + 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. + + + # let rec foo2 x acc = + if x=0 then acc + else foo2 (x-1) (acc+1);; + + val foo2 : int -> int -> int = + ​ + + 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). + + + # let foo' x = foo2 x 1;; + val foo' : int -> int = + ​ + + Let's try to feed ''​foo'''​ with a big input: + + # foo' 1000000 + - : int = 1000001 + ​ + + Since the function ''​foo2''​ will only be used by ''​foo''',​ it is better to + hide it through a nested let-definition:​ + + + # 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 = + ​ + + Let us now consider a more complex example. + The function ''​sumsq''​ computes the sum of the first ''​x''​ squares: + + + # let rec sumsq x = + if x=0 then 0 + else x*x + sumsq (x-1);; + + val sumsq : int -> int = + ​ + + Note that ''​sumsq''​ is not tail recursive. + Let us feed it with a big input: + + # sumsq 1000000;; + Stack overflow during evaluation (looping recursion?​). + ​ + + We can exploit the accumulator technique to make ''​sumsq''​ tail-recursive. + + # 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 = + ​ + + Let us now try it (on 32-bit machines, you will obtain a negative result): + + # sumsq' 1000000;; + - : int = 333333833333500000 + ​ + + To recover a precise result, you can use arbitrary-precision arithmetic: + + # 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 = + + # sumsq''​ (Int 1000000);; + - : Num.num = Int 333333833333500000 + ​ + + \\ + + ===== 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: + + # 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 = + ​ + + This can be made more readable with pattern matching: + + # let rec fib = fun n -> match n with + 0 -> 0 + | 1 -> 1 + | n -> fib (n-1) + fib(n-2);; + ​ + + 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''​):​ + + # let rec fib = function + 0 -> 0 + | 1 -> 1 + | n -> fib (n-1) + fib(n-2);; + ​ + + 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: + + # 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 = + ​ + + Pattern matching allows here for a cleaner definition: + + # let xor = fun x -> match x with + (false,​false) -> false + | (false,​true) ​ -> true + | (true,​false) ​ -> true + | (true,​true) ​  -> false;; + + val xor : bool * bool -> bool = + ​ + + We can simplify definition of the xor function + by using //​variables//​ within patterns. + + + # let xor = function + (false,y) -> y + | (true,​y) ​ -> not y;; + + val xor : bool * bool -> bool = + ​ + + 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). + + + # let imp = function + (true,​false) -> false + | _ -> true;; + + val imp : bool * bool -> bool = + ​ + + As a further example, we define the predecessor function on natural numbers: + + + # let pred x = match x with + 0 -> 0 + | _ -> x-1;; + + val pred : int -> int = + ​ + + 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. + + # 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 = + ​ + + \\ + + ===== Exercises ===== + + [[ex-rec|LIP assignment #2]]