MP 2 – Higher-order Functions

MP 2 – Higher-order Functions and
Continuation-Passing Style
CS 421 
Revision 1.3

1 Change Log
1.3 Fixed the base case for the extra credit, saying list compose returns 0 when applied to the empty list.
1.2 Changed ## to -- in in shiftk to stop it disappearing from the grader. Tried to revise function argument names
to make them more helpful.
1.1 All the functions in Section 5 (CPS) have been redone to start with non-CPS functions that are uncurried.
1.0 Initial Release.
2 Objectives and Background
The purpose of this MP is to:
• Help student master higher-order functions.
• Help the student learn the basics of continuation-passing style, or CPS, and CPS transformation. Next week, you
will be using your knowledge learned from this MP to construct a general-purpose algorithm for transforming
code in direct style into continuation-passing style.
3 Instructions
Instructions for solving the problems related to higher-order functions are the same as instruction for ML2.
The problems related to CPS transformation are all similar to the problems in MP1 and ML2. The difference is that
you must implement each of these function in continuation-passing style. In some cases, you must first write a function
in direct style (according to the problem specification), then transform the function definition into continuation-passing
style.
The problems below have sample executions that suggest how to write answers. Students have to use the same
function name, but the name of the parameters that follow the function name need not be duplicated. That is, the
students are free to choose different names for the arguments to the functions from the ones given in the example
execution. We also will use let rec to begin the definition of some of the functions that are allowed to use recursion.
You are not required to start your code with let rec. Similarly, if you are not prohibited from using explicit
recursion in a given problem, you may change any function definition from starting with just let to starting with let
rec.
For all these problems, you are allowed to write your own auxiliary functions, either internally to the function
being defined or externally as separate functions. All such helper functions must satisfy any coding restrictions (such
as not using explicit recursion) as the main function being defined for the problem must satisfy.
1
Here is a list of the strict requirements for the assignment.
• The function name must be the same as the one provided.
• The type of parameters must be the same as the parameters shown in sample execution.
• Students must comply with any special restrictions for each problem. For several of the problems, you will be
required to write a function in direct style, possibly with some restrictions, as you would have in MP1 or ML2,
and then transform the code you wrote in continuation-passing style.
4 Problems
4.1 Higher Order Functions
For problems 1 through 6, you will be supplying arguments to the higher-order functions List.map, List.fold right,
and List.fold left. You should not need to use explicit recursion for any of these problems. For the problems
in this section, you must not use recursion.
1. (3 pts) Write a value even count fr base : int and a function
even count fr step : int - int - int such that
(fun l - List.fold right even count fr step l even count fr base) returns the number
of even integers found in the input list. There should be no use of recursion in the solution to this problem.
# let even_count_fr_base = ... ;;
val even_count_fr_base : int = ...
# let even_count_fr_step x rec_val = ... ;;
val even_count_fr_step : int - int - int = <fun
# (fun l - List.fold_right even_count_fr_step l even_count_fr_base)
[1; 2; 3];;
- : int = 1
2. (3 pts) Write a function pair sums map arg : (int * int) - int such that
List.map pair sums map arg takes a list of pairs of integers and returns a list of the sums of those pairs in
the same order. There should be no use of recursion in the solution to this problem.
let pair_sums_map_arg p = ...;
val pair_sums_map_arg : int * int - int = <fun
# List.map pair_sums_map_arg [(1,6);(3,1);(3,2)];;
- : int list = [7;4;5]
3. (3 pts) Write a value even count tr start : int and a function
even count tr step : int - int - int such that
(List.fold left even count tr step even count tr start) returns the number of even integers
found in the input list. There should be no use of recursion in the solution to this problem.
# let even_count_tr_start = ... ;;
val even_count_tr_start : int = ...
# let even_count_tr_step acc_value x = ... ;;
val even_count_tr_step : int - int - int = <fun
# List.fold_left even_count_tr_step even_count_tr_start [1; 2; 3];;
- : int = 1
2
4. (3 pts) Write a value count element start : int and function
count element step : ’a - int - ’a - int such that
(fun l - fun m - List.fold left (count element step m) count element start l)
l m returns the number of elements in the input list l that are equal to m. There should be no use of recursion or
library functions in the solution to this problem.
# let count_element_start = ...;;
val count_element_start : int = ...
# let count_element_step m acc_value x = ...;;
val count_element_step : ’a - int - ’a - int = <fun
# (fun l - fun m - List.fold_left
(count_element_step m)
count_element_start l)
[0;1;2;4;2;5;4;2] 2;;
- : int = 3
5. (5 pts) Write a function app all with : (’a - ’b - ’c) list - ’a - ’b list - ’c
list list that takes a list of functions, a single first argument, and a list of second arguments and returns a list
of list of results from consecutively applying the functions to all arguments after applying the single argument to
each function first. The functions should be applied in the order they appear in the list and in the order in which
the arguments appear in the second list. Each list in the result corresponds to a list of applications of a function
on the single argument and then the given argument from the second list. There should be no use of recursion or
library functions except List.map in the solution to this problem.
let app_all_with fs b l = ...;
val app_all_with : (’a - ’b - ’c) list - ’a - ’b list - ’c list list = <fun
# app_all_with [(fun x y - x*y); (fun x y - x+y)] 10 [-1;0;1];;
- : int list list = [[-10; 0; 10]; [9; 10; 11]]
6. (5 pts) Write a value exists between start : bool and a function exists between step: int
- int - bool - int - bool such that (fun m - fun n - fun l - List.fold left
(exists between step m n) exists between start l) m n l returns true if there is an element
x of l such the m ≤ x ≤ n. There should be no use of recursion or library functions in the solution to this problem.
# let exists_between_start = ...;;
val exists_between_start : bool = ...
# let exists_between_step m n acc_value x = ...;;
val exists_between_step : ’a - ’a - bool - ’a - bool = <fun
# (fun m - fun n - fun l - List.fold_left
(exists_between_step m n) exists_between_start l)
5 10 [1; 20; 7; 9];;
- : bool = true
5 Continuation Passing Style
These exercises are designed to give you a feel for continuation-passing style. A function that is written in continuationpassing style does not return once it has finished computing. Instead, it calls another function (the continuation) with
the result of the computation. Here is a small example:
3
# let report_int x =
print_string "Result: ";
print_int x;
print_newline();;
val report_int : int - unit = <fun
# let inck i k = k (i+1);;
val inck : int - (int - ’a) - ’a = <fun
The inck function takes an integer and a continuation. After adding 1 to the integer, it passes the result to its
continuation.
# inck 3 report_int;;
Result: 4
- : unit = ()
# inck 3 inck report_int;;
Result: 5
- : unit = ()
In the first example, inck increments 3 to be 4, and then passes the 4 to report int. In the second example,
the first inck adds 1 to 3, and passes the resulting 4 to the second inck, which then adds 1 to 4, and passes the
resulting 5 to report int.
5.1 Transforming Primitive Operations
Primitive operations are “transformed” into functions that take the arguments of the original operation and a continuation, and apply the continuation to the result of applying the primitive operation on its arguments.
In the helper module Mp2common, we have given you a testing continuation and a few low-level functions in
continuation-passing style. These are as follows:
val report_int : int - unit = <fun
val report_float : float - unit = <fun
val addk : int * int - (int - ’a) - ’a = <fun
val subk : int * int - (int - ’a) - ’a = <fun
val mulk : int * int - (int - ’a) - ’a = <fun
val modk : int * int - (int - ’a) - ’a = <fun
val float_addk : float * float - (float - ’a) - ’a = <fun
val float_subk : float * float - (float - ’a) - ’a = <fun
val float_mulk : float * float - (float - ’a) - ’a = <fun
val geqk : ’a * ’a - (bool - ’b) - ’b = <fun
val eqk : ’a * ’a - (bool - ’b) - ’b = <fun
val notk : bool - (bool - ’a) - ’a = <fun
You are being asked first to extend that set of functions in continuation-passing style.
7. (0 pts) Write the following low-level functions in continuation-passing style. A description of what each function
should do follows:
• consk creates a new list by adding an element to the front of a list.
• concatk concatenates two strings in the order they are provided.
• string of intk takes an integer and converts it into a string.
4
• truncatek takes a float n and truncates it in the same way as the truncate function which can be found
in the pervasives module.
# let consk (x, l) k = ... ;;
val consk : ’a * ’a list - (’a list - ’b) - ’b = <fun
# let concatk (s1, s2) k = ... ;;
val concatk : string * string - (string - ’a) - ’a = <fun
# let string_of_intk n k = ... ;;
val string_of_intk : int - (string - ’a) - ’a = <fun
# let truncatek x k = ... ;;
val truncatek : float - (int - ’a) - ’a = <fun
# consk (1, []) (List.map string_of_int);;
- : string list = ["1"]
# concatk ("hello", "world") (fun s - (s, String.length s));;
- : string * int = ("helloworld", 10)
# string_of_intk 0 (fun s - (s, String.length s));;
- : string * int = ("0", 1)
# truncatek 3.14 string_of_int;;
- : string = "3"
8. (5 pts) Using subk and mulk defined in Mp2common, write a function diff flipk that takes one integer
argument p and “returns” the expression 2 ∗ ((1 −p) ∗ p). You may only use subk and mulk to do the arithmetic.
# let diff_flipk p k = ... ;;
val diff_flipk : int - (int - ’a) - ’a = <fun
# diff_flipk 1 report_int;;
Result: 0
- : unit = ()
9. (5 pts) Write a function quadk that takes three integer arguments, a, b, and c, and “returns” the result of the
expression (2 ∗ (a
2
) + 4 ∗ b) + c. Again you may only use functions from Mp2common to perform the arithmetic.
# let quadk (a, b, c) k = ... ;;
val quadk : int * int * int - (int - ’a) - ’a = <fun
# quadk (1, 1, 1) report_int;;
Result: 7
- : unit = ()
10. (5 pts) Write a function three freezek that takes two string arguments s and p and calculates the string
formed by concatenating them as sp. The function will then “return” this string repeated three times in a row,
however you should only need to calculate sp once.
# let three_freezek (s, p) k = ... ;;
val three_freezek : string * string - (string - ’a) - ’a = <fun
# three_freezek ("muda", "plop") (fun s - (s , String.length s));;
- : string * int = ("mudaplopmudaplopmudaplop", 24)
5
11. (5 pts) Write a function shiftk that takes a string argument s and a float argument q. This function will calculate
(q + 1.57)2 using only arithmetic functions from Mp2common. After calculating this value, it should truncate the
result, turn it into a string, and then concatenate the string s to the beginning and end of the resulting string. This
string is then “returned”.
# let shiftk (s, q) k = ... ;;
val shiftk : string * float - (string - ’a) - ’a = <fun
# shiftk ("--", 3.14) (fun s - s);;
- : string = "--22--"
5.2 Transforming Recursive Functions
How do we write recursive programs in CPS? Consider the following recursive function:
# let rec factorial n =
if n = 0 then 1 else n * factorial (n - 1);;
val factorial : int * int = <fun
# factorial 5;;
- : int = 120
We can rewrite this making each step of computation explicit as follows:
# let rec factoriale n =
let b = n = 0 in
if b then 1
else let s = n - 1 in
let m = factoriale s in
n * m;;
val factoriale : int - int = <fun
# factoriale 5;;
- : int = 120
Now, to put the function into full CPS, we must make factorial take an additional argument, a continuation, to
which the result of the factorial function should be passed. When the recursive call is made to factorial, instead of it
returning a result to build the next higher factorial, it needs to take a continuation for building that next value from
its result. In addition, each intermediate computation must be converted so that it also takes a continuation. Thus the
code becomes:
# let rec factorialk n k =
eqk (n, 0)
(fun b - if b then k 1
else subk (n, 1)
(fun s - factorialk s
(fun m - timesk (n, m) k)));;
# factorialk 5 report;;
Result: 120
- : unit = ()
Notice that to make a recursive call, we needed to build an intermediate continuation capturing all the work that must
be done after the recursive call returns and before we can return the final result. If m is the result of the recursive call
in direct style (without continuations), then we need to build a continuation to:
6
• take the recursive value: m
• build it to the final result: n * m
• pass it to the final continuation k
Notice that this is an extension of the ”nested continuation” method.
In Problems 12 through 15 you are asked to first write a function in direct style and then transform the code into
continuation-passing style. When writing functions in continuation-passing style, all uses of functions need to take a
continuation as an argument. For example, if a problem asks you to write a function partition, then you should
define partition in direct style and partitionk in continuation-passing style. All uses of primitive operations
(e.g. +, -, *, <=, <) should use the corresponding functions defined in Problem 7 or in the lecture notes. If you need
to make use of primitive operations not covered in Problem 7, you should include a definition of the corresponding
version that takes a continuation as an additional argument, as in Problem 7. In all problems there must be no use of
list library functions.
12. (7 pts total)
a. (2 pts) Write a function list prod : int list - int that returns the product of all the elements
in an input list, if the list is non-empty and 1 if the list is empty. The function is required to use (only) forward
recursion (no other form of recursion). You may not use any library functions.
b. (5 pts) Write the function list prodk : int list - (int - ’a) - ’a that is the CPS
transformation of the function you gave in part a.
# let rec list_prod l = ...
val list_prod : int list - int = <fun
# list_prod [1;2;3];;
- : int = 6
let rec list_prodk l k = ...
val list_prodk : int list - (int - ’a) - ’a = <fun
# list_prodk [1;2;3] report_int;;
Result: 6
- : unit = ()
13. (7 pts total)
a. (2 pts) Write a function all positive : int list - bool that returns true if all the elements
in the list are positive, and false otherwise. The function is required to use (only) tail recursion (no other
form of recursion). You may not use any library functions. This problem does not require an auxiliary
function. Note that geqk was one of the functions given in Problem 7.
b. (5 pts) Write the function all positivek : int list - (bool - ’a) - ’a that is the
CPS transformation of the function you gave in part a.
# let rec all_positive l = ...
val all_positive : int list - bool = <fun
all_positive [5;3;6;(-1);7];;
- : bool = false
# let rec all_positivek l k = ...
val all_positivek : int list - (bool - ’a) - ’a = <fun
# all_positivek [5;3;6;(-1);7] (fun b - if b then "true" else "false");;
- : string = "false"
7
14. (8 pts total)
a. (2 pts) Write a function even count that takes a list of integers and computes the number of even integers
found in the input list as in ML2. The only form of recursion you may use for this problem is forward
recursion. You may not use library functions in this part.
b. (6 pts) Write the function even countk that is the CPS transformation of the code you wrote for Part (a).
# let rec even_count l = ... ;;
val even_count : int list - int = <fun
# even_count [1;2;3];;
- : int = 1
# let rec even_countk l k = ... ;;
val even_countk : int list - (int - ’a) - ’a = <fun
# even_countk [1;2;3] report_int;;
Result: 1
- : unit = ()
5.3 CPS - Extra Credit
15. (6 pts total)
a. (2 pts) Write a function list compose : (int - int) list - int that takes a list of functions l = [f0; f1; ...; fn], an from right to left applied fn to 0, and then fn−1 is applied to the output of fn,
etc down to f0 is applied to the output of f1. The result is the composition f0(f1(. . .(fn0). . .)). If the list
of functions is empty, list compose should return 0.
b. (4 pts) Write the function list composek that is the CPS transformation of the code you wrote for Part
(a). In the CPS version, you need to assume that the list of functions to which list composek might be
applied has already been put in CPS.
# let rec list_compose fs = ...
val list_compose : (int - int) list - int = <fun
# list_compose [(fun x - x * x) ; (fun x - x + 2)];;
- : int = 4
# list_composek [(fun x - mulk (x, x)) ; (fun x - addk (x, 2))] report_int;;
Result: 4
- : unit = ()
8