rec

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: | ||

+ | |||

+ | <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)