# Scheme代写 | CS3342 – Assignment 3 Given the lambda expression

这个Assignment是完成Lambda练习和算术运算

CS3342 – Assignment 3

due Mar. 17, 2020, (latest to submit: Mar. 20, 11:55pm)

1. (25pt) Given the lambda expression

(λfx.f (f x)) (λfx.f (f x)) f x

(i) Reduce it using applicative order (call-by-value).

(ii) Reduce it using normal order (call-by-name).

(iii) Write a Scheme program, scheme for lambda.rkt, to test the results you obtained in (i) and

(ii). Which of the results are certified to be correct by your program? Explain your answer.

You need to define what the “globals” f and x do. Use this piece of code for that:

(define f

(lambda (z)

(list ’f z)))

(define x

(lambda (z)

(list ’x z)))

2. (25pt) We have defined natural numbers using λ-expressions as follows:

0 = λf.λc.c

1 = λf.λc.(f c)

2 = λf.λc.(f (f c))

3 = λf.λc.(f (f (f c)))

· · ·

N = λf.λc.(f (f . . .(f

| {z }

N

c)). . .)

Then we introduced arithmetic operations:

addition: + = λM.λN.λa.λb.((M a)((N a) b))

multiplication: × = λM.λN.λa.(M (N a))

exponentiation: ∧ = λM.λN.(N M)

Prove the following reductions, which show that our newly defined arithmetic works correctly:

[M + N] = λa.λb.((M a) ((N a) b)) =⇒∗

β λa.λb.(a (a . . .(a

| {z }

M+N

b)). . .)

[M × N] = λa.(M (N a)) =⇒∗

β λa.λb.(a (a . . .(a

| {z }

M×N

b)). . .)

[MN ] = (N M) =⇒∗

β λa.λb.(a (a . . .(a

| {z }

MN

b)). . .)

You’ll need to use =⇒∗

β

to be able to indicate arbitrarily many reduction steps but make sure to

show all individual steps, =⇒β, that are different. That means, whenever you use =⇒∗

β

to indicate

a group of similar reductions steps, show also one such individual step.

3. (25pt) Write a Scheme program, stack.rkt, that implements a stack. You are supposed to use

imperative features (set!) of Scheme. The stack supports the following operations; assume you

have created a stack, my stack, using your program:

1

empty? : (my stack ’empty?): returns #t if my stack is empty, #f otherwise

push! : (my stack ’push! x): push x onto my stack

top : (my stack ’top): returns the top element of my stack if the stack is not empty; otherwise

gives a message: “empty stack: cannot get the top”

pop! : (my stack ’pop!): pops and returns the top element of my stack if the stack is not empty;

otherwise gives a message: “empty stack: cannot pop”

top-nth : (my stack ’top-nth n): returns the nth element from the top of my stack if the stack has

at least n elements; otherwise gives a message: “not enough elements”

unknown : for any other operation, the program says “unknown operation”.

Your code will look like this:

(define make-stack

(lambda ()

… ; your code here

and should run like this:

(define my_stack (make-stack))

(my_stack ’push! 4)

(my_stack ’push! 1)

(my_stack ’push! 5)

(my_stack ’top) => 5

(my_stack ’top-nth 2) => 1

(my_stack ’top-nth 4) => “not enough elements”

(my_stack ’pop!)

(my_stack ’pop!)

(my_stack ’empty) => “unknown operation”

(my_stack ’empty?) => #f

(my_stack ’pop!)

(my_stack ’top) => “empty stack: cannot get the top”

(my_stack ’pop!) => “empty stack: cannot pop”

4. (25pt) Write a Scheme program, quicksort.rkt, that implements the well-known quicksort algorithm. You are not allowed to use any imperative features.

Your code will look like this:

(define quicksort

(lambda (L)

… ; your code here

and should run like this:

(quicksort ’(5 3 7 2 1 6 4)) => ’(1 2 3 4 5 6 7)

READ ME! The solutions for all written questions will be submitted as single pdf file to OWL. Preferably,

the solutions should be typed, but very neat, legible, hand writing is also acceptable.1

1For those interested, the best program for scientific writing is LATEX: https://tobi.oetiker.ch/lshort/lshort.pdf

2

For all questions requiring coding, the source code files will be submitted separately, named as

indicated in their questions.

Scheme programs should run under DrRacket, version 7.5 with #lang racket at the top.

Self-reported absences can be used to extend the deadline for two days (in addition to the 3

no-penalty days: 5 no-penalty days in total). In this case, you must mark “SELF-REPORTED

ABSENCE” clearly at the top of the assignment and submit it by e-mail to cs3342@uwo.ca. If you

submit by e-mail, DO NOT submit also to OWL as the OWL submission will not be considered!

Failure to submit in OWL by “latest to submit” time or to follow the above procedure for “selfreported absences” will result in your submission not being considered. Due to the very large class,

I cannot consider special cases without good reason.

3