Ballad of a Duck - Revision history

Wtd at 04:24, 9 June 2014

2014-06-09T04:24:42Z

← Older revision		Revision as of 04:24, 9 June 2014
Line 848:		Line 848:
	print_temp celsius_temp;		print_temp celsius_temp;
	print_newline ()</pre>		print_newline ()</pre>
		+
		+	==More on Recursion and First Class Functions==
		+
		+	Recursion plays an important role in the flow of evaluation of computer programs. It permits elements of a program to repeat themselves. We've already seen an example of that in the <tt>prompt_for_input</tt> function.
		+
		+	But this was just one function. A customized solution was designed. What if we could create a generic solution that would abstract out common actions, and feed it a function as a value to do a specific calculation or action. Since Ocaml functions are themselves values, and we can pass values to functions as arguments, this is possible.
		+
		+	First let's write a function which prints a number a certain number of times. Both will be provided by an argument.
		+
		+	<pre># let rec print_int_times n x =
		+	if n > 0 then
		+	(print_int x;
		+	print_newline ();
		+	print_int_times (n - 1) x);;
		+	val print_int_times : int -> int -> unit = <fun>
		+	# print_int_times 4 5;;
		+	5
		+	5
		+	5
		+	5
		+	- : unit = ()
		+	#</pre>
		+
		+	And now a function which prints a string a certain number of times.
		+
		+	<pre># let rec print_string_times n s =
		+	if n > 0 then
		+	(print_endline s;
		+	print_string_times (n - 1) s);;
		+	val print_string_times : int -> string -> unit = <fun>
		+	# print_string_times 4 "foo!";;
		+	foo!
		+	foo!
		+	foo!
		+	foo!
		+	- : unit = ()
		+	#</pre>
		+
		+	There's a common bit of logic here. Let's abstract it out into a function.
		+
		+	<pre># let rec do_times n f =
		+	if n > 0 then
		+	(f ();
		+	do_times (n - 1) f);;
		+	val do_times : int -> (unit -> 'a) -> unit = <fun>
		+	# do_times 4 (fun () -> print_endline "foo!");;
		+	foo!
		+	foo!
		+	foo!
		+	foo!
		+	- : unit = ()
		+	#</pre>

	==Answers==		==Answers==

Wtd: /* Recap */

2014-06-09T00:26:47Z

Recap

← Older revision		Revision as of 00:26, 9 June 2014
Line 775:		Line 775:
	print_float c;;		print_float c;;

-	let prompt_for_input () =	+	let rec prompt_for_input () =
	try		try
	print_string "Farenheit temperature: ";		print_string "Farenheit temperature: ";
Line 796:		Line 796:
	print_temp celsius_temp;		print_temp celsius_temp;
	print_newline ();;</pre>		print_newline ();;</pre>
		+
		+	This program is almost entirely exhaustive. Even the user inputting a bad number is handled. Unfortunately, there is absolute zero (-459.67F), so we should probably handle that as an error. We can raise an exception, then handle it appropriately.
		+
		+	<pre>type temperature = Farenheit of float \| Celsius of float
		+
		+	exception Below_absolute_zero of float
		+
		+	let absolute_zero = -459.67
		+
		+	let to_celsius temp =
		+	match temp with
		+	Farenheit f -> Celsius ((f -. 32.) /. 1.8)
		+	\| x -> x
		+
		+	let print_temp temp =
		+	match temp with
		+	Farenheit f ->
		+	print_float f
		+	\| Celsius c ->
		+	print_float c
		+
		+	let rec prompt_for_input () =
		+	try
		+	print_string "Farenheit temperature: ";
		+	let input_temp = read_float () in
		+	if input_temp < absolute_zero then
		+	raise (Below_absolute_zero input_temp)
		+	else
		+	Farenheit input_temp
		+	with
		+	Failure _ ->
		+	print_endline "Invalid input. Try again.";
		+	prompt_for_input ()
		+	\| Below_absolute_zero temp ->
		+	print_float temp;
		+	print_string "F is too cold.";
		+	print_newline ();
		+	prompt_for_input ();;
		+
		+	let input_temp = prompt_for_input () in
		+	match input_temp with
		+	Farenheit f when f < 32. ->
		+	print_endline "That's cold! I'm out of here!"
		+	\| Farenheit f when f >= 212. ->
		+	print_endline "Ouch! Hot!"
		+	\| Farenheit f when f = 80. ->
		+	print_endline "That's just right."
		+	\| Farenheit f ->
		+	let celsius_temp = to_celsius input_temp in
		+	print_string "Celsius temperature: ";
		+	print_temp celsius_temp;
		+	print_newline ()</pre>

	==Answers==		==Answers==

Wtd: /* Match */

2014-06-08T15:13:48Z

Match

← Older revision		Revision as of 15:13, 8 June 2014
Line 570:		Line 570:
	\| x -> x</pre>		\| x -> x</pre>

-	We can create a straightforward ~~rewqrite~~ of our previous program using algebraic data types and matching.	+	We can create a straightforward rewrite of our previous program using algebraic data types and matching.

	<pre>type temperature = Farenheit of float \| Celsius of float;;		<pre>type temperature = Farenheit of float \| Celsius of float;;
Line 582:		Line 582:
	print_string "Farenheit temperature: ";		print_string "Farenheit temperature: ";
	Farenheit (read_float ());;		Farenheit (read_float ());;
		+
		+	let print_temp temp =
		+	match temp with
		+	Farenheit f ->
		+	print_float f
		+	\| Celsius c ->
		+	print_float c;;

	let input_temp = prompt_for_input () in		let input_temp = prompt_for_input () in
Line 595:		Line 602:
	let celsius_temp = to_celsius input_temp in		let celsius_temp = to_celsius input_temp in
	print_string "Celsius temperature: ";		print_string "Celsius temperature: ";
-	~~print_float~~ celsius_temp;	+	print_temp celsius_temp;
	print_newline ();;</pre>		print_newline ();;</pre>

Line 610:		Line 617:
	print_string "Farenheit temperature: ";		print_string "Farenheit temperature: ";
	Farenheit (read_float ());;		Farenheit (read_float ());;
		+
		+	let print_temp temp =
		+	match temp with
		+	Farenheit f ->
		+	print_float f
		+	\| Celsius c ->
		+	print_float c;;

	let input_temp = prompt_for_input () in		let input_temp = prompt_for_input () in
Line 622:		Line 636:
	let celsius_temp = to_celsius input_temp in		let celsius_temp = to_celsius input_temp in
	print_string "Celsius temperature: ";		print_string "Celsius temperature: ";
-	~~print_float~~ celsius_temp;	+	print_temp celsius_temp;
	print_newline ();;</pre>		print_newline ();;</pre>

Wtd: /* Recursion */

2014-06-08T15:12:56Z

Recursion

← Older revision		Revision as of 15:12, 8 June 2014
Line 733:		Line 733:
	#</pre>		#</pre>

-	Now the ~~fucntion~~ call looks like the following.	+	Now the function call looks like the following.

	<pre>fact 4		<pre>fact 4
Line 742:		Line 742:
	fact' 0 24		fact' 0 24
	24</pre>		24</pre>
		+
		+	===Recap===
		+
		+	So we have if/then, matching, algebraic data types, and we know how to handle errors. Let's revisit the program written previously.
		+
		+	<pre>type temperature = Farenheit of float \| Celsius of float;;
		+
		+	let to_celsius temp =
		+	match temp with
		+	Farenheit f -> Celsius ((f -. 32.) /. 1.8)
		+	\| x -> x;;
		+
		+	let print_temp temp =
		+	match temp with
		+	Farenheit f ->
		+	print_float f
		+	\| Celsius c ->
		+	print_float c;;
		+
		+	let prompt_for_input () =
		+	try
		+	print_string "Farenheit temperature: ";
		+	Farenheit (read_float ())
		+	with Failure _ ->
		+	print_endline "Invalid input. Try again.";
		+	prompt_for_input ();;
		+
		+	let input_temp = prompt_for_input () in
		+	match input_temp with
		+	Farenheit f when f < 32. ->
		+	print_endline "That's cold! I'm out of here!"
		+	\| Farenheit f when f >= 212. ->
		+	print_endline "Ouch! Hot!"
		+	\| Farenheit f when f = 80. ->
		+	print_endline "That's just right."
		+	\| Farenheit f ->
		+	let celsius_temp = to_celsius input_temp in
		+	print_string "Celsius temperature: ";
		+	print_temp celsius_temp;
		+	print_newline ();;</pre>

	==Answers==		==Answers==

Wtd: /* Recursion */

2014-06-08T15:06:14Z

Recursion

← Older revision		Revision as of 15:06, 8 June 2014
Line 686:		Line 686:
	If this process is managed successfully, we don't have to worry about the space being finite. It's unlikely even several functions will overflow that space, causing an error. Unfortunately when a program loops many many times using recursion, it can be possible to run into this problem.		If this process is managed successfully, we don't have to worry about the space being finite. It's unlikely even several functions will overflow that space, causing an error. Unfortunately when a program loops many many times using recursion, it can be possible to run into this problem.

-	Fortunately the previous example actually demonstrates how to avoid this issue. Ocaml (and other languages) automatically optimize for recursion when the function's call of itself is the last thing it does. Since it's the last thing happening in the function, nothing in the caller function remains relevant, so it can be eliminated from the stack.	+	Fortunately the previous example actually demonstrates how to avoid this issue. Ocaml (and other languages) automatically optimize for recursion when the function's call of itself is the last thing it does. Since it's the last thing happening in the function, nothing in the caller function remains relevant, so it can be eliminated from the stack. Many recursive functions can be rewritten to take advantage of this.
		+
		+	A simple function we can look at to see this is calculating a factorial.
		+
		+	<pre># let rec fact x =
		+	if x = 0 then
		+	1
		+	else
		+	x * (x - 1);;
		+	val fact : int -> int = <fun>
		+	# fact 12;;
		+	- : int = 132
		+	#</pre>
		+
		+	For a large enough value of <tt>x</tt> this will cause problems, since the execution of this looks like:
		+
		+	<pre>fact 12
		+	12 * fact 11
		+	12 * 11 * fact 10
		+	12 * 11 * 10 * fact 9
		+	...</pre>
		+
		+	Whereas, if we use an accumulator, we can make sure the last fucntion call in the function is the recursive call.
		+
		+	<pre># let rec fact' x acc =
		+	if x = 0 then
		+	acc
		+	else
		+	fact' (x - 1) (acc * x);;
		+	val fact' : int -> int -> int = <fun>
		+	# fact' 4 1;;
		+	- : int = 24
		+	#</pre>
		+
		+	But since it's troublesome to have to remember to pass the accumulator argument, we can wrap it in another function.
		+
		+	<pre># let fact x =
		+	let rec fact' x acc =
		+	if x = 0 then acc
		+	else fact' (x - 1) (acc * x)
		+	in
		+	fact' x 1;;
		+	val fact : int -> int = <fun>
		+	# fact 4;;
		+	- : int = 24
		+	#</pre>
		+
		+	Now the fucntion call looks like the following.
		+
		+	<pre>fact 4
		+	fact' 4 1
		+	fact' 3 4
		+	fact' 2 12
		+	fact' 1 24
		+	fact' 0 24
		+	24</pre>

	==Answers==		==Answers==

Wtd: /* Recursion */

2014-06-08T14:47:52Z

Recursion

← Older revision		Revision as of 14:47, 8 June 2014
Line 675:		Line 675:

	===Recursion===		===Recursion===
		+
		+	Branching is important, but we also frequently need to repeat actions in a computer program. An important way to accomplish this is by using recursion. We know functions can call each other. Recursion involves one function calling <i>itself</i>. By doing so, the program can repeat an action.
		+
		+	In the previous example, the <tt>rec</tt> keyword denotes a recursive function that will call itself.
		+
		+	To better understand how this works, it's important to understand what happens in a computer when a function is called.
		+
		+	When a function is executed by a program, information relevant to the function is pushed onto the end of the stack. The stack is a finite area of computer memory. At the completion of a function, the information relevant to it is effectively removed from the stack.
		+
		+	If this process is managed successfully, we don't have to worry about the space being finite. It's unlikely even several functions will overflow that space, causing an error. Unfortunately when a program loops many many times using recursion, it can be possible to run into this problem.
		+
		+	Fortunately the previous example actually demonstrates how to avoid this issue. Ocaml (and other languages) automatically optimize for recursion when the function's call of itself is the last thing it does. Since it's the last thing happening in the function, nothing in the caller function remains relevant, so it can be eliminated from the stack.

	==Answers==		==Answers==

Wtd: /* Program Flow */

2014-06-08T14:28:12Z

Program Flow

← Older revision		Revision as of 14:28, 8 June 2014
Line 626:		Line 626:

	There is just one note left to make about match for now. IN this last example the match is not exhaustive. As with if/then, Ocaml does not strictly enforce exhaustive matching when the return type is <tt>unit</tt>, though it will provide a warning.		There is just one note left to make about match for now. IN this last example the match is not exhaustive. As with if/then, Ocaml does not strictly enforce exhaustive matching when the return type is <tt>unit</tt>, though it will provide a warning.
		+
		+	===Errors===
		+
		+	Ocaml does a very good job of helping programmers avoid compile-time errors, but there is another area for problems with the flow of a program: run-time errors.
		+
		+	Consider the last example program. We've accounted for everything... except what happens when the program is actually run. In this case, the wildcard is the <tt>read_input</tt> function. We assume the user will input a valid floating point number, but they don't have to. There could be a typo, or just gibberish.
		+
		+	<pre># read_float ();;
		+	foo!
		+	Exception: Failure "float_of_string".
		+	#</pre>
		+
		+	Ocaml is telling us that trying to turn the string "foo!" into a floating point number failed. Having done so, Ocaml raised an exception, disrupting the program's flow. If this happened in the middle of the program written above, nothing would happen after the input is entered.
		+
		+	Fortunately, exceptions can be handled. Handling an exception gives you the option of doing something constructive when an error occurs, rather than simply having the program give up.
		+
		+	This will look an awful lot like matching, because exception handling gives you the option to handle multiple types of exceptions.
		+
		+	<pre># try
		+	read_float ()
		+	with Failure _ -> 0.;;
		+	foo!
		+	- : float = 0.
		+	#</pre>
		+
		+	The above is very simple. When a failure occurs (and we don't care about matching the reason since we know only one option is possible) the expression simply returns a zero. But this probably isn't very useful. It keeps the program from failing, but it doesn't get us what the user wanted.
		+
		+	Let's try something that asks again.
		+
		+	<pre># let rec read_input () =
		+	try
		+	print_string "> ";
		+	read_float ()
		+	with Failure _ ->
		+	print_endline "Oops! Try again.";
		+	read_input ();;
		+	val read_input : unit -> float = <fun>
		+	# read_input ();;
		+	> foo!
		+	Oops! Try again.
		+	> t
		+	Oops! Try again.
		+	> 5
		+	- : float = 5.
		+	#</pre>
		+
		+	That does it, but there's something new, and hugely important there.
		+
		+	===Recursion===

	==Answers==		==Answers==

Wtd: /* Match */

2014-06-08T14:10:35Z

Match

← Older revision		Revision as of 14:10, 8 June 2014
Line 624:		Line 624:
	print_float celsius_temp;		print_float celsius_temp;
	print_newline ();;</pre>		print_newline ();;</pre>
		+
		+	There is just one note left to make about match for now. IN this last example the match is not exhaustive. As with if/then, Ocaml does not strictly enforce exhaustive matching when the return type is <tt>unit</tt>, though it will provide a warning.

	==Answers==		==Answers==

Wtd: /* Match */

2014-06-08T14:06:25Z

Match

← Older revision		Revision as of 14:06, 8 June 2014
Line 569:		Line 569:
	Farenheit f -> Celsius ((f -. 32.) /. 1.8)		Farenheit f -> Celsius ((f -. 32.) /. 1.8)
	\| x -> x</pre>		\| x -> x</pre>
		+
		+	We can create a straightforward rewqrite of our previous program using algebraic data types and matching.
		+
		+	<pre>type temperature = Farenheit of float \| Celsius of float;;
		+
		+	let to_celsius temp =
		+	match temp with
		+	Farenheit f -> Celsius ((f -. 32.) /. 1.8)
		+	\| x -> x;;
		+
		+	let prompt_for_input () =
		+	print_string "Farenheit temperature: ";
		+	Farenheit (read_float ());;
		+
		+	let input_temp = prompt_for_input () in
		+	match input_temp with
		+	Farenheit f ->
		+	if f < 32. then
		+	print_endline "That's cold! I'm out of here!"
		+	else if f >= 212. then
		+	print_endline "Ouch! Hot!"
		+	else if f = 80. then
		+	print_endline "That's just right."
		+	else
		+	let celsius_temp = to_celsius input_temp in
		+	print_string "Celsius temperature: ";
		+	print_float celsius_temp;
		+	print_newline ();;</pre>
		+
		+	It's very important, when dealing with control flow, to <u>keep things simple</u>. In the abhove, there are two layers of branching, with an if/then buried within a match. This kind of nesting quickly becomes unwieldy to decipher. It would be better if the two levels could become one. Fortunately, guard conditions on matching provide just this.
		+
		+	<pre>type temperature = Farenheit of float \| Celsius of float;;
		+
		+	let to_celsius temp =
		+	match temp with
		+	Farenheit f -> Celsius ((f -. 32.) /. 1.8)
		+	\| x -> x;;
		+
		+	let prompt_for_input () =
		+	print_string "Farenheit temperature: ";
		+	Farenheit (read_float ());;
		+
		+	let input_temp = prompt_for_input () in
		+	match input_temp with
		+	Farenheit f when f < 32. ->
		+	print_endline "That's cold! I'm out of here!"
		+	\| Farenheit f when f >= 212. ->
		+	print_endline "Ouch! Hot!"
		+	\| Farenheit f when f = 80. ->
		+	print_endline "That's just right."
		+	\| Farenheit f ->
		+	let celsius_temp = to_celsius input_temp in
		+	print_string "Celsius temperature: ";
		+	print_float celsius_temp;
		+	print_newline ();;</pre>

	==Answers==		==Answers==

Wtd: /* Match */

2014-06-08T13:53:43Z

Match

← Older revision		Revision as of 13:53, 8 June 2014
Line 562:		Line 562:
	Farenheit f -> Celsius ((f -. 32.) /. 1.8)		Farenheit f -> Celsius ((f -. 32.) /. 1.8)
	\| _ -> temp</pre>		\| _ -> temp</pre>
		+
		+	Or we can give the default pattern a generic name and reuse that.
		+
		+	<pre>let to_celsius temp =
		+	match temp with
		+	Farenheit f -> Celsius ((f -. 32.) /. 1.8)
		+	\| x -> x</pre>

	==Answers==		==Answers==