code Formal semantics and basic Racket programming

Assign: Tuesday, 28 January
Due: 11:59pm Tuesday, 4 February
Policy: Individual graded synthesis assignment
Code: cs251 start semantics --solo
Submit: git commit, cs251 sign, and git push your completed code.
Reference:

Assignment Manifest

Each CS 251 assignment starts with an assignment manifest describing due dates, the honor code policy for collaboration and submissions, how to find starter code (if any), how to submit your work, and a list of topics that are good reference.

(Boxes this color mark key information or warnings.)

The corner of each CS 251 page contains buttons that jump to:

the ▲ top of the page
the ☰ table of contents, if any
the ▼ bottom of the page

(Blue boxes mark optional asides.)

Time Info
Tool Setup
Formal Notations in Plain Text
Tasks
Submission

Time Info

In Spring 2020, students self-reported spending a median of 7.5 hours on this assignment.

Tool Setup

Programming work in CS 251 will be supported primarily by the CS GNU/Linux machines in the SCI L037 CS Systems Lab space. Even though some tools are easily installed elsewhere, you are required to use the lab machines for this assignment to make sure you get familiar with that environment.

To acquire starter code and submit assignment work in CS 251, you will use the Git version control system, paired with a local Git hosting service.

The first task for this assignment is to follow the First-Time Setup instructions on the Tools page to set up your CS account to use the course tools and learn to use them. This includes a tutorial on using Git for CS 251. Even if you are familiar with Git, please skim through this tutorial, as it also includes info about particulars of the CS 251 hosting service (which is accessed purely on the command line).

To get the starter code for this assignment:

$ cs251 start semantics --solo

Formal Notations in Plain Text

Environment $E = x \mapsto 4, y \mapsto 8, x \mapsto 16, \cdot$ can be written as E = x --> 4, y --> 8, x --> 16, ..

Function closure value $\langle E, \texttt{(lambda (x) (+ x x))}\rangle$ can be written <E, (lambda (x) (+ x x))>.

For inference rules and evaluation derivations:

Use conclusion-below-subderivations form in plain text.
Align the start of horizontal bars with the left end of the conclusion underneath.
Indent premises relative to the horizontal bar below them.
List bracketed rule names to the write of their applications (or definitions).
Feel free to use “!” in place of “↓” and “|-” in place of “$\vdash$”.
Use only spaces for indentation (no tabs) to ensure we all see the same indentation.

Here is a plain text formatting example for the addition evaluation rule:

  E |- e1 ! n1
  E |- e2 ! n2
  n = n1 + n2
-------------------- [add]
E |- (+ e1 e2) ! n

Here is a plain text formatting example for the evaluation derivation of expression (+ 290 (- 240 251)):

  E |- 290 ! 290          [value]
    E |- 251 ! 251    [value]
    E |- 240 ! 240    [value]
    11 = 251 - 240
  ----------------------- [sub]
  E |- (- 251 240) ! 11
  301 = 11 + 290
-------------------------------- [add]
E |- (+ 290 (- 251 240)) ! 301

If you prefer, you can use the vertical bars to help show nesting:

| E |- 290 ! 290          [value]
| | E |- 251 ! 251    [value]
| | E |- 240 ! 240    [value]
| | 11 = 251 - 240
| ----------------------- [sub]
| E |- (- 251 240) ! 11
| 301 = 11 + 290
-------------------------------- [add]
E |- (+ 290 (- 251 240)) ! 301

Tasks

To get the starter code for this assignment:

$ cs251 start semantics --solo

0. Course In{f,tr}o (5 points)

Policies (5 points)

Please read the Syllabus and other course info, then answer the following questions in the file course.txt, with a couple phrases or one sentence.

What should I do if I can’t finish an assignment before the deadline?
When is the scheduled in-class exam?
When should I talk to Ben about any necessary accommodations or alternative arrangements for the in-class exam?
What are some good reasons to use the lab machines?
Is it ever acceptable to view another student’s code? If so, under what circumstances?
Is it acceptable for two individuals to write a full code solution together on a whiteboard, then immediately type it up in their individual assignment submissions?
Is it acceptable for one individual student to offer another individual student help understanding an error message?

Meeting (required, ungraded)

Come visit Ben’s drop-in hours (or an appointment) before this assignment is due. There are no points associated with this part, but you must complete it to get any of the points on the rest of this assignment.

Let’s be sure to talk about:

Your name and pronouns.
CS courses you have taken, are taking, or hope to take in the future.
Excitement, concerns, or questions about this course or accommodations.
A place you have never visited but want to visit.

1. Environments (15 points)

For each of the following Racket definitions, write the value to which the variable will be bound. If evaluating the expression in the definition would give rise to an error, write “error”, along with a brief explanation of why the error occurs.

Write your answers as comments in the file definitions.rkt, with one line per definition, in order, as comments after each definition, in the form:

(define x 7)
; x --> 7
(define y 3)
; y --> 3
(define z (quotient 3 0))
; z: error -- attempt to divide a number by 0.

meaning that variable x is bound to value 7, variable y is bound to value 3, and evaluating the binding for z results in a divide-by-zero error.

You do not need to write the entire environment after each definition.

If you encounter an error in one definition, continue to the next definition after notating the error. When using the environment in later definitions, pretend that the erroneous definition was never there.

Predict the answers without running the code. You may find it useful to write evaluation derivations, leaving blanks for the result values as you build the derivation, and then filling in the results once you begin to reach values, but you do not need to submit any derivations in this problem. You may also check your manually evaluated answers by running each binding in order in the DrRacket REPL.

#lang racket
(define a 5)

(define b (* a a))

(define c (+ (* 2 a) (- b a)))

(define d (+ a b c))

(define e (+ a))

(define f (+))

(define g (*))

(define h b)

(define i (if (< a 0) 7 (quotient 43 a)))

(define j (if (= a 0) 11 (remainder 43 a)))

(define k (/ i j))

(define l (< a b))

(define m (= b c))

(define n (< b c d))

(define o (+ a m))

(define p (< a m) )

(define q (if a b c))

(define r (if l m n))

(define s (if (if (< i j) m l)
              (if (> a c) (+ a c) (* a c))
              (if (< a b) (+ a b) (* a b))))            

(define t (= (if (< b c)
                 (* (remainder (- (* a b) (* 2 a)) c) (- (quotient d b)))
                 (* (- (+ d (* (* a b) (quotient d a))))))
             (- (* (/ (- c a) (- a 1)) (quotient b (if (> a c) i j))))))

(define u (if (> i j) (< a 0) (< (< b c) a)))

(define v (if (<= i j) (< a 0) (< (< b c) a)))

2. Derivations (5 points)

In the file derivation.txt, write a plain text evaluation derivation for the following expression under dynamic environment E = a -->3, b --> 6, c --> 4, .:

(+ (if (< a b) (* a (+ b c)) (+ b #t))
   (if (if (> a c) (< c b) (- c 4)) (* 2 b) a))

3. Evaluation Rules for `or` (15 points)

Write your answers for this problem in the file or.txt.

Write one or more evaluation rules for short-circuited Boolean OR expressions of the form: (or e1 e2) using the plain text format described above. If you do not recall the term “short-circuited” review the How to Program (Racket) notes about and or look up documentation of the Boolean OR operator in your favorite programming language.
Could the or expression actually be implemented as a function instead of a special form with its own evaluation rule? If yes, give a function definition for or with comments and an example call (application) of that function explaining how it works and why it is equivalent to your evaluation rule. If no, explain why or must be a special form with its own evaluation rule instead of a call to a function.
Consider this Racket program:
```
#lang racket
(define (diverge x) (diverge x)) ; infinitely recursive function
; Show environment in effect here. E =
(or (< 240 251) (diverge 235)) ; Show evaluation derivation for this expresion.
```
Using our Racket semantics so far, extended with your or evaluation rule:
- Show the environment, E, that is in place when evaluating the or expression. E = ....
- Write an evaluation derivation for the or expression, using E to stand for the environment you just showed.
Use the plain text format described above.

4. Recursive Racket Programming (50 points)

This part gives you practice writing simple recursive functions in Racket.

You may (and in some cases, must) define helper functions to solve well-selected sub-problems.
You may not use Racket lists or cons-related features.
In general you should be using only features we have seen so far, with the exception of some other simple built-in functions.
You must use recursion (and no other iterative mechanisms).
If you find something else in Racket documentation that seems highly relevant, ask before using it.

Write your answers to this part in the file recursion.rkt using DrRacket.

(10 points) Write a recursive Racket function sum-digits that takes any non-negative integer as an argument and returns the sum of its digits. It does not matter how your function behaves when applied to any value that is not a non-negative integer.
```
> (sum-digits 0)
0
> (sum-digits 2)
2
> (sum-digits 25)
7
> (sum-digits 251)
8
```
(10 points) Write a recursive Racket function nondecreasing-digits?-if that takes any non-negative integer and returns #t if its digits, from most significant place to least significant place, are nondecreasing (i.e., monotonically increasing): each digit is at least as large as the last. It does not matter how your function behaves when applied to any value that is not a non-negative integer. Do not worry about repeating simply arithmetic expressions multiple times in your function. Use if at least once.
```
> (nondecreasing-digits?-if 2)
#t
> (nondecreasing-digits?-if 25)
#t
> (nondecreasing-digits?-if 251)
#f
> (nondecreasing-digits?-if 037)
#t
> (nondecreasing-digits?-if 111)
#t
```

(5 points) Write a recursive Racket function nondecreasing-digits? that acts just like nondecreasing-digits?-if except that it must not use if at all.

> (nondecreasing-digits? 2)
#t
> (nondecreasing-digits? 25)
#t
> (nondecreasing-digits? 251)
#f
> (nondecreasing-digits? 037)
#t
> (nondecreasing-digits? 111)
#t

(10 points) Write a recursive Racket function count-one-bits that takes any non-negative integer and returns the number of 1 bits required to represent that integer as an unsigned binary number.

> (count-one-bits 0) ; 0
0
> (count-one-bits 1) ; 1
1
> (count-one-bits 2) ; 10
1
> (count-one-bits 3) ; 11
2
> (count-one-bits 6) ; 110
2
> (count-one-bits 13) ; 1101
3

(10 points) Write a recursive Racket function count-occurrences that takes two strings and counts how many times the second string (the “needle”) appears as a contiguous substring of the first string (the “haystack”). You may use the standard string-length, substring, and string=? functions.
```
> (count-occurrences "haystack" "needle")
0
> (count-occurrences "haystack" "a")
2
> (count-occurrences "aaaa" "aa")
3
> (count-occurrences "aa" "aaaa")
0
```
Challenge (5 points): Write a recursive Racket function palindrome? that takes any string and returns #t if it is a palindrome (same forwards or backwards) and #f otherwise. You will find the following string functions useful: non-empty-string?, string-length, string-ci=?, substring, string-replace. If there are other string functions you wish to use, ask first. Your palindrome checker should be case-insensitive (“aA” is a palindrome) and should ignore spaces, treating them as if they are not there, but all other characters can be treated as meaningful. (You do not need to filter out punctuation.) You may or may not solve this one, which is OK, but you must try.
```
> (palindrome? "was it a car or a cat I saw")
#t
> (palindrome? "programming language")
#f
> (palindrome? "never odd or even")
#t
> (palindrome? "Semordnilap Palindrome")
#f
> (palindrome? "")
#t
> (palindrome? "a")
#t
> (palindrome? "aa")
#t
> (palindrome? "aba")
#t
```

Submission

Submit: The course staff will collect your work directly from your hosted repository. To submit your work:

Test your source code files one last time. Make sure that, at a minimum, submitted source code is free of syntax errors and any other static errors (such as static type errors or name/scope errors). In other words: the code does not need to complete the correct computation when invoked, but it must be a valid program. We will not grade files that do not pass this bar.
Make sure you have committed your latest changes.
```
$ git add ...
$ git commit ...
```
Run the command cs251 sign to sign your work and respond to any assignment survey questions.
```
$ cs251 sign
```
Push your signature and your latest local commits to the hosted repository.
```
$ git push
```

Confirm: All local changes have been submitted if the output of git status shows both:

Your branch is up to date with 'origin/master', meaning all local commits have been pushed
nothing to commit, meaning all local changes have been committed

Resubmit: If you realize you need to change something later, just repeat this process.

Some Antics with Semantics

Contents

Time Info

Tool Setup

Formal Notations in Plain Text

Tasks

0. Course In{f,tr}o (5 points)

Policies (5 points)

Meeting (required, ungraded)

1. Environments (15 points)

2. Derivations (5 points)

3. Evaluation Rules for `or` (15 points)

4. Recursive Racket Programming (50 points)

Submission

Contents

Time Info

Tool Setup

Formal Notations in Plain Text

Tasks

0. Course In{f,tr}o (5 points)

Policies (5 points)

Meeting (required, ungraded)

1. Environments (15 points)

2. Derivations (5 points)

3. Evaluation Rules for or (15 points)

4. Recursive Racket Programming (50 points)

Submission

3. Evaluation Rules for `or` (15 points)