• Dueish:: Fri Feb 15. But because of the late posting of this assignment and the Mon Feb 18 President’s Holiday, the grace period for this assignment extends through the end of Mon Feb 18 rather than Sun Feb 17.

  • Notes:
    • You can do all problems on this pset based on material you’ve learned in lecture by Mon Feb 11.
    • This pset contains your first solo problem (Problem 1) on big-step and little-step semantics. Be sure to study the solutions on PS1 Problem 5 (which will be handed out in lecture on Mon Feb 11) as part of doing this problem.
    • You can collaborate on the non-solo problems with your classmates following the usual Gilligan’s Island and Freedom of Information rules (as explained in the Honor Code and Collaboration section of the syllabus.)
    • The problems needn’t be done in order. Feel free to jump around. Indeed, it is recommended that you do Problems 4 and 5 first.
    • This pset has 100 points, but also includes a competely optional 12-point extra credit problem. You should only attempt the extra credit problem once you have finished the required problems.

  • Times from previous recent semesters

    Times Problem 1 Problem 2 Problem 3 Problem 4 Problem 5 Total
    number of students 51 51 51 52 50 54
    average time (hours) 2.17 0.95 1.38 2.11 1.39 7.89
    50% took >= (hours) 2 0.75 1 2 1 7.31
    25% took >= (hours) 2.5 1.16 2 2.5 2 9.560
    10% took >= (hours) 3 2 2 3 2.1 11.35
  • Submission:
    • In the yourFullName CS251 Spring 2019 Folder that you created for PS1, create a Google Doc named yourFullName CS251 PS2.
    • For all problems, include all answers (including Racket code and big-step/small-step derivations) in your PS2 google doc. Please format your derivations in Problems 1 and 4 and definitions from Problem 5 so that they’re easy to read. Format all derivations and code using a fixed-width font (Courier New or Consolas). You use a small font size if that helps.
    • For Problem 5 (Racket Recursion), also drop a copy of your yourAccountName-ps2-functions.rkt in your ~/cs251/drop/ps02 drop folder on cs.wellesley.edu.

1. Conjunction Junction (Solo Problem) (29 points)

This is a solo problem. This means you must complete it entirely on your own without help from any other person and without consulting resources other than course materials or online documentation. You may ask Lyn for clarification, but not for help.

In this problem, we will consider Racket’s (and E1 E2) and (or E1 E2) logical operator constructs. (In Racket, and and or can have any number of subexpressions, but we’ll keep things simple by focusing on the common case with two subexpressions.)

1a. Big-step Semantics (6 points)

In big-step semantics, here are the evaluation rules for and and or:

| E1 ↓ #f
----------------- [and false]
(and E1 E2) ↓ #f

| E1 ↓ V1
| E2 ↓ V2
----------------- [and nonfalse] (where V1 is not #f)
(and E1 E2) ↓ V2

| E1 ↓ #f
| E2 ↓ V2
----------------- [or false] 
(or E1 E2) ↓ V2

| E1 ↓ V1
----------------- [or nonfalse] (where V1 is not #f)
(or E1 E2) ↓ V1

Note that there are situations where and and or can return a value based solely on the value of the expression E1 without evaluating the expression E2. Because of this, they are called short-circuit operators.

Using the above rules together with the other big-step rules you know, give complete big-step evaluation derivations for the following two expressions.

(or (and (< 1 2) (> 3 4)) (and (= 5 6) (/ 7 0)))

(and (or (* 8 9) (= 10 11)) (or (+ 12 13) (- 14 #f)))

Notes:

  • Study the solutions to PS1 Problem 5a before starting this problem.

  • You may use either the conclusion-above-subderivation format or conclusion-below-subderivation format, as described in PS1 Problem 5.

  • Be sure to label each rule application with the rule name in square brackets.

  • Be sure that all conclusions are justified exactly by the rules. In the past, points have been deducted for careless application of the rules (e.g., deriving conclusions that aren’t really justified by the rules).

  • In general, solo problems are worth more than regular problems, so you should be more careful to avoid in these problems.

1b. Small-step Semantics (5 points)

In small-step semantics, here are the reduction rules for and and or:

(and #f E2) ⇒ #f [and false]

(and V1 E2) ⇒ E2 [and nonfalse] (where V1 is not #f)

(or #f E2) ⇒ E2 [or false]

(or V1 E2) ⇒ V1 [or nonfalse] (where V1 is not #f)

In all four of these rules, note that the presence of #f and V1 in the first operand position indicated that the first operand must be evaluated to a value before any reduction step can take place. However, the presence of E2 in the second operand position means that no evaluation should take place on the second operand before the reduction takes place. (Recall that, in general, metavariables beginning with V match only values, but E matches any expression.)

Using these small-step reduction rules with other small-step rules you know, give complete small-step evaluation derivations for the same two expressions evaluated in 1a.

Notes:

  • Study the solutions to PS1 Problem 5b before starting this problem.

  • Be sure to indicate the redex in each step with curly braces.

  • Be sure to label each rule application with the rule name in square brackets.

  • Be sure that all steps are justified exactly by the rules. In the past, points have been deducted for careless application of the rules (e.g., deriving steps that aren’t really justified by the rules).

1c. Desugaring (5 points)

Rather than giving big-step or small-step reduction rules to define the semantics of and and or, we can instead provide a way to translate these constructs to the if expression we already know. This approach is known as desuguaring. In this case, (and E1 E2) desugars to (i.e., translates to) (if E1 E2 #f) and (or E1 E2) desugars to (if E1 E1 E2). The key advantage of desugaring is that new constructs can be explained in terms of old ones rather than requiring new rules.

In this problem, we use small-steps semantics to formally show that these desugarings have exactly the same meaning as the original and and or constructs. We use the notation E1 ⇒* E2 to mean that E1 rewrites to E2 by zero or more ⇒ rewrite steps (for an example, see Problem 4 below).

For example, assume that E1 ⇒* #f. We will write small-step derivations showing that (and E1 E2) ⇒* #f and (if E1 E2 #f) ⇒* #f so that (if E1 E2 #f) acts exactly like (and E1 E2) in this case:

(and {E1} E2 )
⇒* {(and #f E2)} [assumption]
⇒ #f [and false]
(if {E1} E2 #f)
⇒* {(if #f E2 #f)} [assumption]
⇒ #f [if false]

Note that in this derivation, we use the justification [by assumption] to justify the ⇒* step that uses the fact E1 ⇒* #f. This is not justified by the [varref] rule, because it is using information about the metavariable E1, which is not a variable within Racket. You should use [by assumption] in a similar way vbelow.

i. Assume that E1 ⇒* V1, where V1 is not false. Write small-step derivations showing that (and E1 E2) ⇒* E2 and (if E1 E2 #f) ⇒* E2 so that (if E1 E2 #f) acts exactly like (and E1 E2) in this case.

ii. Assume that E1 ⇒* #f. Write small-step derivations showing that (or E1 E2) ⇒* E2 and (if E1 E1 E2) ⇒* E2, and so (if E1 E1 E2) acts like (or E1 E2) in this case.

iii. Assume that E1 ⇒* V1, where V1 is not false. Write small-step derivations showing that (or E1 E2) ⇒* V1 and (if E1 E1 E2) ⇒* V1 so that (if E1 E1 E2) acts exactly like (or E1 E2) in this case.

iv. The desugaring of (or E1 E2) to (if E1 E1 E2) has a downside. What is it? (Later We will see how to fix this downside).

1d. Alternative logical operators (5 points)

We can imagine alternative logical operators conj and disj that are similar to and and or respectively, but have different small-step semantics rules:

(conj #f V2) ⇒ #f [conj false]

(conj #t V2) ⇒ V2 [conj true] 

(disj #f V2) ⇒ V2 [disj false]

(disj #t V2) ⇒ #t [disj true]

Note that in all four rules, the presence of #f or #t in the first operand position and V2 in the second operand position means that both the first and second operands must be values in order for the reduction to take place. So in the expressions (conj E1 E2) and (disj E1 E2), both E1 and E2 must be evaluated to values before the above rules can be applied. You should assume left-to-right evaluation of operands — i.e., E1 must be completely evaluated to a value V1 before evaluation of E2 begins.

Pay attention to the same bulleted notes as in Problem 1b.

Using these alternative small-step reduction rules with other small-step rules you know, give complete small-step evaluation derivations for the following variant of the examples from parts 1a and 1b:

(disj (conj (< 1 2) (> 3 4)) (conj (= 5 6) (/ 7 0)))

(conj (disj (* 8 9) (= 10 11)) (disj (+ 12 13) (- 14 #f)))

1e. Comparisons to logical operators in other languages (8 points)

In the following parts, you are asked to compare the above operators to similar operators in Python and Java. In each part, you should discuss both of the following:

  1. short-circuiting behavior

  2. handling of non-boolean operands

In each part, you should refer to appropriate Python/Java documentation and give relevant examples from Racket/Python/Java to justify your answers. Points will be deducted for answers that are vague, do not include relevant examples, or do not cover all relevant issues.

i. [3 points] Which of Racket’s and/or or the alternative disj/conj operators behaves more like Python’s and/or infix operators? Carefully justify your answer.

ii. [2.5 points] In what way(s) are Racket’s and/or like Java’s &&/||? In what way(s) are they different?

iii. [2.5 points] In what way(s) are the alternative disj/conj like Java’s &&/||? In what way(s) are they different?

2. The Evils of Two Lesses (14 points)

Consider the exact expression (3 < 4 < 2). (Do not remove the parens or any spaces, add any extra parens, or move around any symbols.) This expression is handled differently in different programming languages. For each of the following four programming languages, explain how this expression is handled in that language.

  • If the expression returns a value, specify that value and explain why that value is returned and how you know this fact. Give evidence from a sample program in that language that is has the value you claim.

  • If the expression causes an error, explain the nature of the error (is it a syntax error? static type error? dynamic type error? something else?) and how you know this fact. Again, give evidence from a sample program in that language that is has the error you claim.

  1. Java (3 points)
  2. JavaScript (4 points)
  3. Python (4 points)
  4. Racket (3 points)

Note: If the answer depends on special features of the language, you should cite a source for the documentation explaining those features.

3. Truthiness (16 points)

truthiness image)

In the context of a conditional test, a value that chooses the then arm of the conditional is called truthy and a value that chooses the else arm of the conditional is called falsey (sometimes spelled falsy). We will use the term neither to refer to a value that cannot be used as a conditional test (causing a compile-time or run-time error).

We have seen that in Racket, the #f value is falsey and every value that is not #f is truthy; Racket has no neither values. This problem asks you to explore truthiness in other languages.

Below are five programming languages and links to their language specification documents. Based on information in the documents, determine which values are truthy, which are falsey, and which (if any) are neither. In your answers, explicitly cite all the sections of the reference manuals that you use to justify ine your answer. Points will be deducted if appopriate citations are missing.

Notes:

  • Hint: begin by searching for the terms if statement or conditional in the documents.

  • One of the purposes of this problem is to introduce you to language specification documents. These are the authoritative sources for answering any questions about the languages, even nit-picky ones. Although they can be somewhat dense, you should get into the habit of consulting them. For reasons you will understand after doing this problem, people who write/consult/cite such language specifications are sometimes called language lawyers.

  • In the EcmaScript specification, notions like ReturnIfAbrupt and CompletionRecord are used to model the dynamic semantics of exceptions and can be ignored for the purposes of this problem.

  • The C specification for the semantics of if statments uses the terminolgy “compares equal to 0”. Although it’s not obvious, this terminology is defined in Section 6.5.9 Equality operators on p. 96.

  • The correct answer for C is particularly challenging to track down. Consider the following in your answer:

    • How are pointers treated by C? Are there any pointers treated as falsey?
    • How are arrays treated by C?

  • Compare the length of the Scheme reference document (only 50 pages) to the others. When people say that Scheme/Racket are simpler than other languages, this is one piece of evidence that they give.

4. Sum Fun (25 points)

In the Mon Feb 11 class, the following recursive factorial function is covered:

(define fact
  (lambda (n)
    (if (= n 0)
        1
        (* n (fact (- n 1))))))

We used the small-step semantics introduced in lecture on Wed Sep 12 to explain the evaluation of (fact 4). To simplify things, let’s introduce the abbreviation λ_fact for the follow lambda expression:

(lambda (n) (if (= n 0) 1 (* n (fact (- n 1)))))

Then here is the small-step evaluation derivation for (fact 4) relative to an implicit environment that binds the name fact to the expression λ_fact:

({fact} 4)
⇒ {(λ_fact 4)} [varref]
⇒ (if {(= 4 0)} 1 (* 4 (fact (- 4 1)))) [function call]]
⇒ {(if #f 1 (* 4 (fact (- 4 1))))} [equality]
⇒ (* 4 ({fact} (- 4 1))) [if false]
⇒ (* 4 (λ_fact {(- 4 1)})) [varref]
⇒ (* 4 {(λ_fact 3)}) [subtraction]
⇒ (* 4 (if {(= 3 0)} 1 (* 3 (fact (- 3 1))))) [function call]
⇒ (* 4 {(if #f 1 (* 3 (fact (- 3 1))))}) [equality]
⇒ (* 4 (* 3 ({fact} (- 3 1)))) [if false]
⇒ (* 4 (* 3 (λ_fact {(- 3 1)}))) [varref]
⇒ (* 4 (* 3 {(λ_fact 2)})) [subtraction]
⇒ (* 4 (* 3 (if {(= 2 0)} 1 (* 2 (fact (- 2 1)))))) [function call]
⇒ (* 4 (* 3 {(if #f 1 (* 2 (fact (- 2 1))))})) [equality]
⇒ (* 4 (* 3 (* 2 ({fact} (- 2 1))))) [if false]
⇒ (* 4 (* 3 (* 2 (λ_fact {(- 2 1)})))) [varref]
⇒ (* 4 (* 3 (* 2 {(λ_fact 1)}))) [subtraction]
⇒ (* 4 (* 3 (* 2 (if {(= 1 0)} 1 (* 1 (fact (- 1 1))))))) [function call]
⇒ (* 4 (* 3 (* 2 {(if #f 1 (* 1 (fact (- 1 1))))}))) [equality]
⇒ (* 4 (* 3 (* 2 (* 1 ({fact} (- 1 1)))))) [if false]
⇒ (* 4 (* 3 (* 2 (* 1 (λ_fact {(- 1 1)}))))) [varref]
⇒ (* 4 (* 3 (* 2 (* 1 {(λ_fact 0)})))) [subtraction]
⇒ (* 4 (* 3 (* 2 (* 1 (if {(= 0 0)} 1 (* 0 (fact (- 0 1)))))))) [function call]
⇒ (* 4 (* 3 (* 2 (* 1 {(if #t 1 (* 0 (fact (- 0 1))))})))) [equality]
⇒ (* 4 (* 3 (* 2 {(* 1 1)}))) [if nonfalse]
⇒ (* 4 (* 3 {(* 2 1)})) [multiplication]
⇒ (* 4 {(* 3 2)}) [multiplication]
⇒ {(* 4 6)} [multiplication]
⇒ 24 [multiplication]

To highlight the essential steps of such an evaluation, we will often use the notation E1 ⇒* E2 to mean that expression E1 rewrites to expression E2 by some number (possibly zero) of ⇒ steps. Below, we use this notation to omit all lines except for the ones involving (1) calls to λ_fact on argument values or (2) calculation of the final result. Below is an example of an abbreviated evaluation derivation for the above example. Note that lines involving ⇒* do not have an explicit justification in square brackets (though the could be justified by all of the rules applied in ⇒*).

({fact} 4)
⇒ {(λ_fact 4)} [varref]
⇒* (* 4 {(λ_fact 3)})
⇒* (* 4 (* 3 {(λ_fact 2)}))
⇒* (* 4 (* 3 (* 2 {(λ_fact 1)})))
⇒* (* 4 (* 3 (* 2 (* 1 {(λ_fact 0)}))))
⇒* (* 4 (* 3 (* 2 {(* 1 1)})))
⇒ (* 4 (* 3 {(* 2 1)})) [multiplication]
⇒ (* 4 {(* 3 2)}) [multiplication]
⇒ {(* 4 6)} [multiplication]
⇒ 24 [multiplication]

As another example, consider a recursive definition of a function for calculating the nth Fibonacci number, which we saw in class on Tue Sep 18:

(define fib
  (lambda (n)
    (if (<= n 1)
        n
        (+ (fib (- n 1)) (fib (- n 2))))))

Suppose λ_fib is an abbreviation for the following lambda expression:

(lambda (n)
  (if (<= n 1)
      n
      (+ (fib (- n 1)) (fib (- n 2))))))

Then here is an abbreviated evaluation derivation for (fib 4) relative to an implicit environment that binds the name fib to the expression λ_fib:

({fib} 4) 
⇒  {(λ_fib 4)} [varref]
⇒* (+ {(λ_fib 3)} (fib (- 4 2)))
⇒* (+ (+ {(λ_fib 2)} (fib (- 3 2))) (fib (- 4 2)))
⇒* (+ (+ (+ {(λ_fib 1)} (fib (- 2 2))) (fib (- 3 2))) (fib (- 4 2)))
⇒* (+ (+ (+ 1 {(λ_fib 0)}) (fib (- 3 2))) (fib (- 4 2)))
⇒* (+ (+ {(+ 1 0)} (fib (- 3 2))) (fib (- 4 2)))
⇒* (+ (+ 1 {(λ_fib 1)}) (fib (- 4 2)))
⇒* (+ {(+ 1 1)} (fib (- 4 2)))
⇒* (+ 2 {(λ_fib 2)})
⇒* (+ 2 (+ {(λ_fib 1)} (fib (- 2 2))))
⇒* (+ 2 (+ 1 {(λ_fib 0)}))
⇒* (+ 2 {(+ 1 0)})
⇒ {(+ 2 1)} [addition]
⇒ 3 [addition]

Note that (λ_fib 4) ⇒* (+ (λ_fib 3) (fib (- 4 2))) and not (λ_fib 4) ⇒* (+ (λ_fib 3) (λ_fib 2)). Why? Because the small-step evaluation of (+ E1 E2) must fully evaluate E1 to a value V1 before any evaluation is performed on E2. So the expression (fib (- 4 2)) is not simplified in any way until (λ_fib 3) evaluates to 2.

Also note that ⇒* (+ (+ 1 0) (fib (- 3 2))) ⇒ (+ 1 (fib (- 3 2))) and not (+ (+ 1 0) (fib (- 3 2))) ⇒ (+ (+ 1 0) (λ_fib 1)). The addition redex (+ 1 0) must be evaluated to 1 before any work is done reducing (fib (- 3 2)).

In this problem you are asked to reason about and create such abbreviated derivations.

a. sum-between (5 points)

Here is a definition of a sum-between function that returns the sum of all the integers between its two integer arguments (inclusive):

(define sum-between
  (lambda (lo hi)
    (if (> lo hi)
        0
        (+ lo (sum-between (+ lo 1) hi)))))

Using the abbreviated small-step derivation notation shown above for (fact 4), show an abbreviated evaluation derivation for (sum-between 3 7) that shows the key steps in this derivation. Use the notation λ_sb as an abbreviation for the lambda expression

(lambda (lo hi)
  (if (> lo hi)
      0
      (+ lo (sum-between (+ lo 1) hi))))

Your derivation should only show lines in which λ_sb is called on values and lines involving the calculation of + in (+ lo ...), but not any lines that involve if, >, or the calculation of + in (+ lo 1).

b. Stack depth for sum-between (3 points)

Although the small-step evaluation model does not have any explicit notion of stack frames, operations like * in the recursive fact definition and + in the recursive sum-between definition correspond to pending operations that are remembered to be performed when control returns from the stack frame for a particular function invocation in a model based on stack frames. In the (fact 4) example, the fact that the maximal sequence of nested multiplications, (* 4 (* 3 (* 2 (* 1 1)))), has four multiplications corresponds to a nesting of five stack frames (one for each call of fact on arguments 4 down to 0).

In the case of fact, we will call the maximal number of pending multiplications the stack depth. So (fact 4) has a stack depth of 4, and (fact 100) would have a stack depth of 100. So the stack depth of (fact n) grows linearly in n.

Let’s define the stack depth for sum-between to be the maximal number of nested pending addition operations in the small-step evaluation derivation.

  1. What is the stack depth for (sum-between 3 7)?

  2. What is the stack depth for (sum-between 1 128)?

  3. How does the stack depth for (sum-between 1 n) grow with n?

c. sum-between-halves (8 points)

Here is a definition of a sum-between-halves function that also returns the sum of all the integers between its two integer arguments (inclusive), but does so in a different way from sum-between:

(define sum-between-halves
  (lambda (lo hi)
    (if (> lo hi)
        0
        (if (= lo hi)
            lo
            (+ (sum-between-halves lo (quotient (+ lo hi) 2))
               (sum-between-halves (+ 1 (quotient (+ lo hi) 2)) hi))))))

Show an abbreviated evaluation derivation for (sum-between-halves 3 7) that shows the key steps in this derivation. Use the notation λ_sbh as an abbreviation for the lambda expression

(lambda (lo hi)
  (if (> lo hi)
      0
      (if (= lo hi)
          lo
          (+ (sum-between-halves lo (quotient (+ lo hi) 2))
             (sum-between-halves (+ 1 (quotient (+ lo hi) 2)) hi))))))

Your derivation should be similar to the (fib 4) example given above. Note that somes lines will have a mixture of calls to λ_sbh on values and calls to sum-between-halves on unevaluated expressions. See the (fib 4) example for an explanation of this. For example, your derivation should begin like this:

(λ_sbh 3 7)
⇒* (+ (λ_sbh 3 5) 
      (sum-between-halves (+ 1 (quotient (+ 3 7) 2)) 7))
⇒* (+ (+ (λ_sbh 3 4) 
         (sum-between-halves (+ 1 (quotient (+ 3 5) 2)) 5))
      (sum-between-halves (+ 1 (quotient (+ 3 7) 2)) 7))

d. Stack depth for sum-between-halves (4 points)

Define the stack depth for a call to sum-between-halves as the maximal number of nested pending + operations from (+ (sum-between-halves ...) (sum-between-halves ...)).

  1. What is the stack depth for (sum-between-halves 3 7)?

  2. What is the stack depth for (sum-between-halves 1 128)?

  3. How does the stack depth for (sum-between-halves 1 n) grow with n?

  4. Does sum-between-halves offer any benefit over sum-between as a way to calculate the sum of integers in a range?

e. sum-between-iter (3 points)

Now we consider one more way to calculate the sum of integers in a given range. The function sum-between-iter defined below also sums numbers in a given range using the helper function sum-between-tail.

(define sum-between-iter
  (lambda (lo hi)
    (sum-between-tail lo hi 0)))

(define sum-between-tail
  (lambda (lo hi sum-so-far)
    (if (> lo hi)
        sum-so-far
        (sum-between-tail (+ lo 1) hi (+ lo sum-so-far)))))

Show an abbreviated evaluation derivation for (sum-between-iter 3 7) that shows the key steps in this derivation. Use the notation λ_sbi as an abbreviation for the lambda expression

(lambda (lo hi)
  (sum-between-tail lo hi 0)))

and the notation λ_sbt as an abbreviation for the lambda expression

(lambda (lo hi sum-so-far)
  (if (> lo hi)
      sum-so-far
      (sum-between-tail (+ lo 1) hi (+ lo sum-so-far)))))

In your derivation, show only lines in which λ_sbi or λ_sbt are called on values.

f. Benefits of sum-between-iter/sum-between-tail (2 points)

Do sum-between-iter/sum-between-tail offer any benefit(s) over sum-between and sum-between-halves? Explain.

Note: sum-between-tail is an example of a so-called tail-recursive function, which we will study in a few weeks. Racket has no loop constructs, but they are not necessary because it is is possible to write all iterations (loops) in Racket using tail recursion.

5. Racket Recursion (16 points)

Although you’ve written recursive function definitions before in other courses, recursion is particularly important in CS251 for three reasons:

  • The list data structures in Racket and Standard ML are recursively defined, and so are naturally processed with recursion. (You will get lots of practice with these starting later in the week of Sep 17.)

  • Neither Racket nor Standard ML has looping constructs, so what you would express via loops in other languages must be expressed via recursion in these languages. (As suggested in Problem 4e above, a particular kind of recursion known as tail recursion can express anything expressible with loops in other languages and then some.)

  • Later in the semester we will study metaprograms – i.s., programs that manipulate other programs. Metaprograms typically process the abstract syntax tree (AST) structure of the program being manipulated. Such tree processing is most naturally expressed using recursion. Indeed, you’ve already seen that big-step evaluation semantics is tree-recursive in nature.

For each of the following two Racket function specifications, write and test a recursive function that satisfies that specification. In all of your definitions, you should use the following recursive problem solving strategy:

  • For which argument(s) is the function so simple that the answer can be returned immediately? This is the base case.

  • For the other case(s) (known as the recursive case(s)), use divide/conquer/glue:

    • divide: make one or more subproblems that are smaller instances of the given problem;

    • conquer: assume that the recursive function you’re defining simply works and returns the correct answer on all of the smaller problems.

    • glue: combine the result(s) of the recursive function call(s) with information in the original problem to create the correct result for the whole problem.

The fact, fib, sum-between and sum-between-halves functions shown above are all instances of this strategy, and we will see many examples of recursion with list arguments in the coming week. (The sum-between-iter function is not an instance of this strategy because it introduces a helper function that changes the structure of the problem into an iteration.)

Notes:

  • For this problem, you should use Dr. Racket to create a single file named yourAccountName-ps2-functions.rkt that contains all the functions (including helper functions) that you define for this problem.

  • In your definitions, unless otherwise instructed, you should not introduce any recursive helper functions. (But you can define nonrecursive helper functions).
  • If the following error message pops up during the testing of one of your functions, it mostly likely means that you have an infinite recursion that doesn’t reach its base case and runs out of memory due to a stack depth that cannot fit into available memory.

box-and-pointer-diagram

  1. (8 points) Define a function sum-squares-of-ints-divisible-by that takes three integer arguments (divisor, lo, and hi) and returns the sum of the squares of all the integers between lo and hi (inclusive) that are evenly divisible by divisor.

     > (sum-squares-of-ints-divisible-by 2 1 8)
 120 ; =  2^2 + 4^2 + 6^2 + 8^2
 > (sum-squares-of-ints-divisible-by 3 1 10)
 126 ; =  3^2 + 6^2 + 9^2
 > (sum-squares-of-ints-divisible-by 5 1 10)
 125 ; =  5^2 + 10^2 
 > (sum-squares-of-ints-divisible-by 7 1 10)
 49 ; =  7^2 
 > (sum-squares-of-ints-divisible-by 11 1 10)
 0 ; no multiples of 11 between 1 and 10
 > (sum-squares-of-ints-divisible-by 11 7 15)
 121 ; = 11^2
 > (sum-squares-of-ints-divisible-by 2 10 8)
 0 ; the range "from 10 up to 8" is empty

    Use the following helper function in this problem:

    (define divisible-by?
  (lambda (num divisor)
    (= (remainder num divisor) 0)))

  2. (8 points) A Hamming number is any positive integer expressible as 2i⋅3j⋅5k. E.g., the Hamming numbers between 1 and 100 are:

    1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36 40 45 48 50 54 60 64 72 75 80 81 90 96 100

    Define a function hamming? that takes a single numeric argument (including 0, negatives, and nonintegers), and returns #t if the argument is a Hamming number and #f if it is not. Your function need not work on arguments that are not numbers.

     > (hamming? 30)
 #t
 > (hamming? 31)
 #f
 > (hamming? -31)
 #f
 > (hamming? 3.141)
 #f
 > (hamming? 0)
 #f
 > (filter hamming? (range -100 101)) ; list all integers from -100 up to
                                      ; (but not including) 101 
                                      ; for which hamming? is true
 '(1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36 40 45 48 50 54 60 64 72 75 80 81 90 96 100)

    Notes:

    • Use integer? to test if a value is an integer.
    • Use (and E1 E2 ... En) to determine if all of the expressions E1, E2, …, En are true.
    • Use (or E1 E2 ... En) to determine if at least one the expressions E1, E2, …, En is true.
    • You needn’t use any if expressions in your definition. All you need are and and or. (But you can use if if you want to.)
    • The divisible-by? helper function from Problem 5a is useful here as well.

Extra Credit: Distinguishing Languages with One Expression (10 points)

This problem is optional. You should only attempt it after completing all the other problems.

In Problem 3, you saw that Racket, Python, JavaScript, and C all have slightly different notions of truthy and falsey. In this problem, the goal is to use this fact to design a single expression that denotes a string, and the string it denotes names the language in which the string is evaluated.

Of course, each of these four languages has a different syntax, so the “single expression” can’t be exactly the same in all the languages. Rather, it should have the same abstract syntax in all the languages but the concrete syntax can differ.

For example, consider these two conditional expressions:

  • JavaScript: ((3 < 4 < 2) ? "javascript" : "python")
  • Python: "javascript" if 3 < 4 < 2 else "python"

They have different concrete syntax but the same abstract syntax. (Actually, (3 < 4 < 2) is treated slightly differently in terms of abstract syntax trees in JavaScript and Pyton, but let’s ignore this detail for now.) But because of the difference in senantics between the languages, the JavScript expression evaluates to "javascript" and the Python expression evaluates to "python".

Your goal is to write a single (abstract syntax) expression that can return one of the four strings "javascript", "python", "racket" or "c", and when the (concrete syntax) of this expression is evaluated in JavaScript, Python, Racket, or C, it returns the name of the language in which it was evaluated. So effectively this expression is a test that answers the question “Which language I am in?”.

Notes:

  • You should give the concrete syntax of the same abstract expression in all four languages, and show a transcript from all four languages that it has the desired behavior.

  • You are allowed to use the following syntactic elements in your expression: numbers, strings, lists/arrays, and conditional expressions. You are not allowed to use operators (such as +, <, etc.) or built-in functions. Because of the restriction on <, you cannot use the example above to distinguish JavaScript and Python.

  • For the purposes of this problem, Racket’s immutable lists, Python’s & JavaScript’s mutable lists, and C’s arrays will be considered “equivalent”. E.g. Racket’s list '(1 2 3), Python’s & JavaScript’s list [1, 2, 3], and C’s array {1, 2, 3} will be considered “the same”.

  • For the C expression, you may (1) declare arrays outside of the expression that are used inside the expression and (2) may use explicit type casts to cast arrays to a type suitable for truthy/falsey.

  • You can get partial credit for distinquishing a subset of the languages: 2 points for distinquishing two languages, 5 points for distinguishin three languages, and 10 points for distinguishing all four.