COMP 3007 A/B (Winter 2023) − "Programming Paradigms"
Specification for Assignment 2
Your submission for this assignment must be commented and must include both your name and your
student number as a comment at the top of every source file you submit. Each of your submitted files must
use a file name beginning 'comp3007_w23_#########_assignment_02' (replacing the number signs with
your own student number) and any submissions that crash (i.e., terminate with an error) on execution will
automatically receive a mark of 0.
Officially, the Due Date for this Assignment is:
Friday, February 3rd, 2023, at 11:59pm EST.
Late Submissions are Accepted Without Penalty Until Sunday, February 5th, by 11:59pm EST.
Submissions received after that will not be accepted and will receive a mark of 0.
The objective of this assignment is to have you review some of the basics of -calculus by completing two
simple exercises. As the purpose of the -calculus module was to develop a foundation of understanding
about the system from which the Haskell programming language was derived, you must show all your work
to receive full credit. You are not permitted to "skip" any operations when performing these reductions.
For the first exercise, you must perform a β-reduction on the expression below that corresponds to *your*
unique student identification number.
If the LAST TWO DIGITS of your student number is in the range from 00 to 24 inclusive, then you must reduce:
(𝜆𝑔. (𝜆𝑗. 𝑔)) (𝜆ℎ. (𝜆𝑘. 𝑘)) (𝜆𝑖. (𝜆𝑚. 𝑖))
If the LAST TWO DIGITS of your student number is in the range from 25 to 49 inclusive, then you must reduce:
(𝜆𝑛. (𝜆𝑞. 𝑞)) (𝜆𝑜. (𝜆𝑟. 𝑜)) (𝜆𝑝. (𝜆𝑠. 𝑠))
If the LAST TWO DIGITS of your student number is in the range from 50 to 74 inclusive, then you must reduce:
(𝜆𝑡. (𝜆𝑤. 𝑤)) (𝜆𝑢. (𝜆𝑦. 𝑦)) (𝜆𝑣. (𝜆𝑧. 𝑣))
If the LAST TWO DIGITS of your student number is in the range from 75 to 99 inclusive, then you must reduce:
(𝜆𝑎. (𝜆𝑑. 𝑎)) (𝜆𝑏. (𝜆𝑒. 𝑏)) (𝜆𝑐. (𝜆𝑓. 𝑓))
For the second exercise, you must first write the -calculus expression corresponding to the Church encoding
of the LARGEST digit in your student number. You must then perform a β-reduction on the expression below,
eventually replacing both zero and yourdigit with their corresponding Church encodings.
𝜆𝑎. (𝜆𝑏. (𝜆𝑐. (𝜆𝑑. ((𝑎 𝑐)((𝑏 𝑐) 𝑑))))) 𝑦𝑜𝑢𝑟𝑑𝑖𝑔𝑖𝑡 𝑧𝑒𝑟𝑜
For this assignment:
• your submission must be a single pdf document that you created electronically (using a word
processor like Microsoft Word or Google Docs), and please note that scans or digital photographs of
handwritten submissions will not be accepted and will receive a mark of zero
• you must include your full name and student number at the top of your submission
• you must show *all* your work and perform no more than one operation per line when reducing