Homework 7: Scheme Data Abstractions, Programs as Data

• hw07.zip

Due by 11:59pm on Wednesday, August 10

Instructions

This lab has a several files. Remember to write in hw07.scm for the Scheme questions, hw07.py for the Regex question, hw07.sql for the SQL questions.

Submission: When you are done, submit with python3 ok --submit. You may submit more than once before the deadline; only the final submission will be scored. Check that you have successfully submitted your code on okpy.org. See Lab 0 for more instructions on submitting assignments.

Using Ok: If you have any questions about using Ok, please refer to this guide.

Readings: You might find the following references useful:

• Scheme Specification
• Scheme Built-in Procedure Reference

Grading: Homework is graded based on correctness. Each incorrect problem will decrease the total score by one point. There is a homework recovery policy as stated in the syllabus. This homework is out of 2 points.
Getting Started Videos

Keyword Lists

In the following problems, you will explore creating two separate implementations for the same abstraction.

A keyword list is the Scheme analogue of a dict in Python, with a few key differences:

• It allows for repeating keys
• It functions as a list as well, which allows for ordering.

The kwlist abstraction keeps a mapping of keys and values. To create a kwlist, call the constructor (make-kwlist keys values) where keys is a Scheme list of symbols and values is a Scheme list of any type. This returns some abstracted item lst that we can call the following methods to either retrieve or add items:

scm> (define lst (make-kwlist '(x y z) '(7 8 9)) ; create the keyword list
lst
scm> (get-first-from-kwlist lst 'x) ; get an item
7
scm> (define lst (add-to-kwlist lst 'a 10)) ; add a new item
lst
scm> (get-first-from-kwlist lst 'a) ; get the new item.
10

Q1: Keyword List: Construct

First, implement abstractions for kwlist in two ways, with the following example: (kwlist '(x y z) '(7 8 9))

1. kwlist1, which stores a keyword list in the following manner: ((key1 key2 key3 ...) (value1 value2 value3 ...). With the example above, this should look like ((x y z) (7 8 9)).
2. kwlist2, which stores a keyword list in the following manner: ((key1 value1) (key2 value2) ...). With the example above, this should look like ((x 7) (y 8) (z 9)).

Specifically, implement constructors and selectors for kwlist1 and kwlist2.

• The constructors, make-kwlist1 and make-kwlist2, should take in Scheme lists for both keys and values, and construct the abstraction as above.
• The selectors, get-keys-kwlist1, get-keys-kwlist2, get-values-kwlist1, and get-values-kwlist1, should take in a kwlist1 or kwlist2 and return their keys and values respectively. Note that because you are currently creating the implementation, you are "under the abstraction barrier;" feel free to refer to specific details of the structure of kwlist1 and kwlist2.

Hint: The map function may prove to be useful, but is not required. You may also use the cadr function, which is defined for you in the file.

scm> (define ex-lst1 (make-kwlist1 '(a b c) '(1 2 3)))
ex-list1
scm> (get-keys-kwlist1 ex-lst1)
(a b c)
scm> (get-values-kwlist1 ex-lst1)
(1 2 3)
scm> (define ex-lst2 (make-kwlist2 '(a b c) '(1 2 3)))
ex-list2
scm> (get-keys-kwlist2 ex-lst2)
(a b c)
scm> (get-values-kwlist2 ex-lst2)
(1 2 3)
scm> ex-lst1
((a b c) (1 2 3))
scm> ex-lst2
((a 1) (b 2) (c 3))

(define (make-kwlist1 keys values)
  'YOUR-CODE-HERE
)

(define (get-keys-kwlist1 kwlist)
  'YOUR-CODE-HERE
)

(define (get-values-kwlist1 kwlist)
  'YOUR-CODE-HERE
)
(define (make-kwlist2 keys values)
  'YOUR-CODE-HERE
)

(define (get-keys-kwlist2 kwlist)
  'YOUR-CODE-HERE
)

(define (get-values-kwlist2 kwlist)
  'YOUR-CODE-HERE
)

Use Ok to test your code:

python3 ok -q kwlist_construct
Copy
✂️

Important: For the following questions, your implementations should be invariant with respect to the abstraction used; that is, it should work regardless of whether kwlist1 or kwlist2 is used. Specifically, in the tests, we will define the abstraction kwlist as either kwlist1 or kwlist2:

scm> (define make-kwlist make-kwlist1)
scm> (define get-keys-kwlist get-keys-kwlist1)
scm> (define get-values-kwlist get-values-kwlist1)
; tests here...
scm> (define make-kwlist make-kwlist2)
scm> (define get-keys-kwlist get-keys-kwlist2)
scm> (define get-values-kwlist get-values-kwlist2)
; tests here...

You should refer to the above kwlist procedures, not kwlist1 or kwlist2's procedures in your implementation.

Q2: (Optional) Keyword List: Add

Now, implement add-to-kwlist, which implements support for adding a new (key, value) pair to any implementation of a kwlist. Specifically, add-to-kwlist takes in a kwlist, a key, and a value as input, and returns a new kwlist with updated keys and values. Note that kwlists are ordered; that is, a pair p1 that was added to a kwlist before a different pair p2 should appear earlier in the kwlist.

Hint: The append method may be useful here. To make your implementation work with both abstractions, be sure to use methods ending in kwlist, not kwlist1 or kwlist2.

scm> (define ex-lst (make-kwlist '(a b c) '(1 2 3)))
ex-lst
scm> (get-keys-kwlist ex-lst)
(a b c)
scm> (get-values-kwlist ex-lst)
(1 2 3)
scm> (define ex-lst (add-to-kwlist ex-lst 'd '4))
ex-lst
scm> (get-keys-kwlist ex-lst) ; note that new items are at the end of the list!
(a b c d)
scm> (get-values-kwlist ex-lst) ; here too!
(1 2 3 4)

(define (add-to-kwlist kwlist key value)
  'YOUR-CODE-HERE
)

Use Ok to test your code:

python3 ok -q kwlist_add
Copy
✂️

Q3: (Optional) Keyword List: Get

Now, implement get-first-from-kwlist, which implements support for getting the first value bound to a key in kwlist. If key is not present in the list, the function should return nil to indicate that there were no valid keys found.

Hint: Consider using let to temporarily bind names to values. To make your implementation work with both abstractions, be sure to use methods ending in kwlist, not kwlist1 or kwlist2.

scm> (define ex-lst (make-kwlist '(a b c) '(1 2 3)))
ex-lst
scm> (get-first-from-kwlist ex-lst 'b)
2
scm> (get-first-from-kwlist ex-lst 'd) ; if not found, return nil
()
scm> (define ex-lst (add-to-kwlist ex-lst 'd '4))
ex-lst
scm> (get-first-from-kwlist ex-lst 'b)
2
scm> (get-first-from-kwlist ex-lst 'd)
4
scm> (define ex-lst (add-to-kwlist ex-lst 'd '5))
ex-lst
scm> (get-first-from-kwlist ex-lst 'b)
2
scm> (get-first-from-kwlist ex-lst 'd) ; return the *first* occurrence
4

(define (get-first-from-kwlist kwlist key)
  'YOUR-CODE-HERE
)

Use Ok to test your code:

python3 ok -q kwlist_get
Copy
✂️

Regular Expressions

Q4: Roman Numerals

Return True if any string of letters that resemble a Roman numeral exists in text and aren't part of another word. A Roman numeral is made up of the letters I, V, X, L, C, D, M and is at least one letter long.

For the purposes of this problem, don't worry about whether or not a Roman numeral is valid. For example, "VIIIII" is not a Roman numeral, but it is fine if your regex matches it.

import re

def roman_numerals(text):
    """
    Returns True if any string of letters that could be a Roman numeral
    (made up of the letters I, V, X, L, C, D, M) is found. Returns False otherwise.

    >>> roman_numerals("Sir Richard IIV, can you tell Richard VI that Richard IV is on the phone?")
    True
    >>> roman_numerals("My TODOs: I. Groceries II. Learn how to count in Roman IV. Profit")
    True
    >>> roman_numerals("I. Act 1 II. Act 2 III. Act 3 IV. Act 4 V. Act 5")
    True
    >>> roman_numerals("Let's play Civ VII")
    True
    >>> roman_numerals("i love vi so much more than emacs.")
    False
    >>> roman_numerals("she loves ALL editors equally.")
    False
    >>> roman_numerals("he loves working in the LIVING room.")
    False
    """
    return bool(re.search(__________, text))

Use Ok to test your code:

python3 ok -q roman_numerals
Copy
✂️

Dog Data

In each question below, you will define a new table based on the following tables.

CREATE TABLE parents AS
  SELECT "abraham" AS parent, "barack" AS child UNION
  SELECT "abraham"          , "clinton"         UNION
  SELECT "delano"           , "herbert"         UNION
  SELECT "fillmore"         , "abraham"         UNION
  SELECT "fillmore"         , "delano"          UNION
  SELECT "fillmore"         , "grover"          UNION
  SELECT "eisenhower"       , "fillmore";

CREATE TABLE dogs AS
  SELECT "abraham" AS name, "long" AS fur, 26 AS height UNION
  SELECT "barack"         , "short"      , 52           UNION
  SELECT "clinton"        , "long"       , 47           UNION
  SELECT "delano"         , "long"       , 46           UNION
  SELECT "eisenhower"     , "short"      , 35           UNION
  SELECT "fillmore"       , "curly"      , 32           UNION
  SELECT "grover"         , "short"      , 28           UNION
  SELECT "herbert"        , "curly"      , 31;

CREATE TABLE sizes AS
  SELECT "toy" AS size, 24 AS min, 28 AS max UNION
  SELECT "mini"       , 28       , 35        UNION
  SELECT "medium"     , 35       , 45        UNION
  SELECT "standard"   , 45       , 60;

Your tables should still perform correctly even if the values in these tables change. For example, if you are asked to list all dogs with a name that starts with h, you should write:

SELECT name FROM dogs WHERE "h" <= name AND name < "i";

Instead of assuming that the dogs table has only the data above and writing

SELECT "herbert";

The former query would still be correct if the name grover were changed to hoover or a row was added with the name harry.

Q5: By Parent Height

Create a table by_parent_height that has a column of the names of all dogs that have a parent, ordered by the height of the parent dog from tallest parent to shortest parent.

-- All dogs with parents ordered by decreasing height of their parent
CREATE TABLE by_parent_height AS
  SELECT "REPLACE THIS LINE WITH YOUR SOLUTION";

For example, fillmore has a parent (eisenhower) with height 35, and so should appear before grover who has a parent (fillmore) with height 32. The names of dogs with parents of the same height should appear together in any order. For example, barack and clinton should both appear at the end, but either one can come before the other.

sqlite> select * from by_parent_height;
herbert
fillmore
abraham
delano
grover
barack
clinton

Use Ok to test your code:

python3 ok -q by_parent_height
Copy
✂️

Q6: (Optional) Size of Dogs

The Fédération Cynologique Internationale classifies a standard poodle as over 45 cm and up to 60 cm. The sizes table describes this and other such classifications, where a dog must be over the min and less than or equal to the max in height to qualify as a size.

Create a size_of_dogs table with two columns, one for each dog's name and another for its size.

-- The size of each dog
CREATE TABLE size_of_dogs AS
  SELECT "REPLACE THIS LINE WITH YOUR SOLUTION";

The output should look like the following:

sqlite> select * from size_of_dogs;
abraham|toy
barack|standard
clinton|standard
delano|standard
eisenhower|mini
fillmore|mini
grover|toy
herbert|mini

Use Ok to test your code:

python3 ok -q size_of_dogs
Copy
✂️

Optional Exam Questions

Homework assignments will also contain prior exam-level questions for you to take a look at. These questions have no submission component; feel free to attempt them if you'd like a challenge!

1. Fall 2019 Final Q7c: *-to-mul
2. Fall 2021 Final Q5a: Spice