The goal of this lecture note is to put polymorphic unparsing to work by tracing function calls and returns.
Say we are given the following definitions:
let add_1 a =
1 + a;;
let add_11 b =
10 + add_1 b;;
let add_111 c =
100 + add_11 c;;
let add_1111 d =
1000 + add_111 d;;
Warning
Make sure you have first read the Mini-interlude about Exercise 0.2 approved by Magritte.
Let us enumerate the computational steps involved in evaluating, e.g., add_1111 0 in the global environment where add_1, add_11, add_111, add_1111 are defined:
Enseigner, c’est répéter.(To teach is to repeat.)—French proverb
Quite a mouthful, isn’t it?
Let’s try again, trimming the text and indenting it to reflect the nesting of sub-problems. We want to evaluate add_1111 0 in the global environment where add_1, add_11, add_111, add_1111 are defined:
each of add_1111 and 0 is evaluated: one, to the function denoted by add_1111, and the other, to the number 0; and the function denoted by add_1111 is applied to 0;
1000 + add_111 d is evaluated in an environment where d denotes 0; each of 1000 and add_111 d is evaluated: 1000 evaluates to the number 1000; to evaluate add_111 d, each of add_111 and d is evaluated: one, to the function denoted by add_111 and the other, to the number 0; and the function denoted by add_111 is applied to 0, a computation that needs to complete before the addition can take place;
100 + add_11 c is evaluated in an environment where c denotes 0; each of 100 and add_11 c is evaluated: 100 evaluates to the number 100; to evaluate add_11 c, each of add_11 and c is evaluated: one, to the function denoted by add_11, and the other, to the number 0; and the function denoted by add_11 is applied to 0, a computation that needs to complete before the addition can take place;
10 + add_1 b is evaluated in an environment where b denotes 0; each of 10 and add_1 b is evaluated: 10 evaluates to the number 10; to evaluate add_1 b, each of add_1 and b is evaluated: one, to the function denoted by add_1, and the other, to the number 0; and the function denoted by add_1 is applied to 0, a computation that needs to complete before the addition can take place;
1 + a is evaluated in an environment where a denotes 0; each of 1 and a are evaluated: 1 evaluates to the number 1, and a evaluates to the number 0; the addition of 1 and 0 takes place, yielding 1, and 1 is returned as the result of calling the function denoted by add_1 to 0;(continued) so the result of evaluating add_1 b is 1; the addition of 10 and 1 takes place, yielding 11, and 11 is returned as the result of calling the function denoted by add_11 to 0;
(continued) so the result of evaluating add_11 c is 11; the addition of 100 and 11 takes place, yielding 111, and 111 is returned as the result of calling the function denoted by add_111 to 0;
(continued) so the result of evaluating add_111 d is 111; the addition of 1000 and 111 takes place, yielding 1111, and 1111 is returned as the result of calling the function denoted by add_1111 to 0;
(ended) so the result of evaluating add_1111 0 is 1111.
To visualize these successive computational steps, the accompanying resource file contains traced versions of add_1, add_11, add_111, add_1111.
The versions of add_1, add_11, add_111, and add_1111 where the calls are traced are named add_1_with_calls_traced, add_11_with_calls_traced, add_111_with_calls_traced, and add_1111_with_calls_traced. Here they are in action:
# add_1111_with_calls_traced 0;;
add_1111 0 ->
add_111 0 ->
add_11 0 ->
add_1 0 ->
- : int = 1111
#
Each time a function is called, its original name is printed out, followed by the value of its argument, followed by a right arrow, and a new line.
The versions of add_1, add_11, add_111, and add_1111 where the calls and the returns are traced are named add_1_with_calls_and_returns_traced, add_11_with_calls_and_returns_traced, add_111_with_calls_and_returns_traced, and add_1111_with_calls_and_returns_traced. Here they are in action:
# add_1111_with_calls_and_returns_traced 0;;
add_1111 0 ->
add_111 0 ->
add_11 0 ->
add_1 0 ->
add_1 0 <- 1
add_11 0 <- 11
add_111 0 <- 111
add_1111 0 <- 1111
- : int = 1111
#
Each time a function is called, its original name is printed out, followed by the value of its argument, followed by a right arrow, and a new line. And each time a function returns, its original name is printed out, followed by the value of its argument, followed by a left arrow, followed by the result that is returned, and a new line.
The versions of add_1, add_11, add_111, and add_1111 where the calls and the returns are traced and indented are named add_1_with_calls_and_returns_traced_and_indented, add_11_with_calls_and_returns_traced_and_indented, add_111_with_calls_and_returns_traced_and_indented, and add_1111_with_calls_and_returns_traced_and_indented. Here they are in action:
# add_1111_with_calls_and_returns_traced_and_indented 0;;
add_1111 0 ->
add_111 0 ->
add_11 0 ->
add_1 0 ->
add_1 0 <- 1
add_11 0 <- 11
add_111 0 <- 111
add_1111 0 <- 1111
- : int = 1111
#
Each time a function is called, its original name is printed out, followed by the value of its argument, followed by a right arrow, and a new line, after some white space that reflects the nesting of the calls: the more nested, the more space. And each time a function returns, its original name is printed out, followed by the value of its argument, followed by a left arrow, followed by the result that is returned, and a new line.
The indentation makes it clear how the calls and the corresponding returns are related: they are vertically aligned.
Added the definition of show_int in the resource file to make it stand alone, thanks to Stinson’s eagle eye [17 Feb 2020]
Added the warning and the indented description [15 Feb 2020]
Created [14 Feb 2020]