• Dueish: Tue Nov 10

  • Notes:

    • This is your first solo assignment. You must complete all parts of this assignment entirely on your own without help from any other person and without consulting any resources other than course materials or Racket documentation. You may ask Lyn for clarification, but not for help.

    • You can do all problems on this assignment based on material you learned for PS1. Be sure to study the solutions to PS1 before doing this assignment.

    • This assignment has 38 solo points.

  • How to Start Solo Assignment A

    Follow the instructions in the GDoc CS251-F20-T2 Pset Submission Instructions for creating your SOLO-A Google Doc. Put all written answers and a copy of all code into this SOLO-A GDoc.

  • Submission:

    • For all parts of all problems, include all answers (including Racket code and big/small-step derivations) in your SOLO-A GDoc. Please format your big/small-step derivation in Problem 1 and your Racket function definitions in Problem 2 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 1 (Conjunction Junction), include your big/small-step derivations and answers to all questions in your SOLO-A doc.
    • For Problem 2 (Numeric Recursion):
      • Be sure that all function definitions in yourAccountName-solo-a.rkt also appear in your SOLO-A GDoc (so that I can comment on them).
      • When you are finished with Problem 2, drop a copy of your yourAccountName-solo-a.rkt in your ~/cs251/drop/solo-a drop folder on cs.wellesley.edu.

1. Conjunction Junction (26 points)

1a. Big-step Semantics (7 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.

(and (or (= 16 15) (> 14 13)) 
     (or (< 11 12) (+ 10 #t)))

(or (and (or #f (- 9 9)) 
         (and (< 5 4) (/ 8 0)))
    (* 7 6))

Notes:

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

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

  • Be sure to label each rule application with the rule name in square brackets. Points will be deducted for missing rule names.

  • Be sure that all conclusions are justified exactly by the rules. Points will be deducted for incorrect application of the rules (e.g., deriving conclusions that aren’t really justified by the rules).

  • Because solo problem points count more than regular pset problem points, it’s in your best interest to double check all your answers before you submit them.

1b. Small-step Semantics (6 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 Part 1a.

Notes:

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

  • Be sure to indicate the redex in each step with curly braces. Points will be deducted for missing curly braces.

  • Be sure to label each rule application with the rule name in square brackets. Points will be deducted for missing rule names.

  • Be sure that all steps are justified exactly by the rules. Points will be deducted for incorrect application of the rules (e.g., deriving steps that aren’t really justified by the rules).

1c. Desugaring (4 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 examples of ⇒*, see the abbreviated small-step derivations for recursion examples in Lec 06 and in PS2 Problem 1).

For example, assume that E1 ⇒* #f. Here are small-step derivations showing that (and E1 E2) ⇒* #f and (if E1 E2 #f) ⇒* #f, from which we can conclude 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 below.

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

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

iii. Assume that E1 ⇒* V1, where V1 is not #f. Write small-step derivations showing that (1) (or E1 E2) ⇒* V1 and (2) that (if E1 E1 E2) ⇒* V1, indicating 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 (4 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 variants of the examples from parts 1a and 1b:

(conj (disj (= 16 15) (> 14 13)) 
      (disj (< 11 12) (+ 10 #t)))

(disj (conj (disj #f (- 9 9)) 
            (conj (< 5 4) (/ 8 0)))
      (* 7 6))

1e. Comparisons to logical operators in other languages (5 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. For the answer you choose, also describe any differences in behavior between your chosen operators and Python’s and/or infix operators.

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

2. Numeric Recursion (12 points)

In this problem you will define two recursive functions. To start this problem, use Dr. Racket to create a single file named yourAccountName-solo-a.rkt that will contain the two functions that you define for this problem.

  1. (5 points) Define a recursive function sum-halves that takes one argument n, which you may assume is a floating point real number (i.e., a number written with an explicit decimal point, like 16.0 or 3.141). sum-halves returns the sum of all numbers that are ≥ 1.0 in the sequence of numbers n, n/2, n/4, n/8, … If no numbers in this sequence are ≥ 1.0, sum-halves returns 0.0.

     > (sum-halves 16.0)
 31.0 ; = 16.0 + 8.0 + 4.0 + 2.0 + 1.0
 > (sum-halves 10.0)
 18.75 ; = 10.0 + 5.0 + 2.5 + 1.25
 > (sum-halves 3.141)
 4.7115 ; = 3.141 + 1.5705
 > (sum-halves 100.0)
 198.4375 ; = 100.0 + 50.0 + 25.0 + 12.5 + 6.25 + 3.125 + 1.5625
 > (sum-halves 0.99)
 0.0 ; 0.99 is < 1.0, so all its successive halves will be < 1.0, too
 > (sum-halves -10.0)
 0.0 ; -10.0 is < 1.0, so all its successive halves will be < 1.0, too

  2. (7 points) Define a recursive function product-of-digits that takes one argument x. If x is a positive integer (i.e., it’s an integer > 0), product-of-digits returns the product of the digits in the integer (see examples below). Otherwise (i.e., if x is not an integer or is <= 0), product-of-digits returns 0.

     > (product-of-digits 372)
 42 ; = 3 * 7 * 2
 > (product-of-digits 251)
 10 ; = 2 * 5 * 1
 > (product-of-digits 22533)
 180 ; = 2 * 2 * 5 * 3 * 3
 > (product-of-digits 225033)
 0 ; = 2 * 2 * 5 * 0 * 3 * 3
 > (product-of-digits 123456789)
 362880 ; = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9
 > (product-of-digits 7)
 7 ; the product of one digit is that digit
 > (product-of-digits 0)
 0 ; 0 is <= 0
 > (product-of-digits -7)
 0 ; -7 is <= 0
 > (product-of-digits -251)
 0 ; -251 is <= 0
 >  (product-of-digits (/ 468 2))
 24 ; = 2 * 3 * 4
 > (product-of-digits (/ 22 7))
 0 ; 22/7 is not an integer
 > (product-of-digits 3.141)
 0 ; 3.141 is not an integer
 > (product-of-digits #t)
 0 ; #t is not an integer
 > (product-of-digits "Wow")
 0 ; "Wow" is not an integer

    Notes:

    • Use integer? to test if a value is an integer. Note that integer returns #f for any value that’s not an integer, including rational numbers, booleans, strings, etc.
    • Use (remainder x 10) to extract the last digit of a positive integer.
    • Use (quotient x 10) to extract all but the last digit of a positive integer.
    • Do not attempt to convert x to a string (e.g., do not use number->string) or use any string operations.