Recall the calculator interpreter you implemented in Lab 12. The following is an extension of that prompt.
Q1: Counting Eval and Apply
How many calls to
calc_apply would it
take to evaluate each of the following Calculator expressions?
scm> (+ 1 2)
For this particular prompt please list out the inputs to
scm> (+ 2 4 6 8)
scm> (+ 2 (* 4 (- 6 8)))
scm> (and 1 (+ 1 0) 0)
scm> (and (+ 1 0) (< 1 0) (/ 1 0))
Q2: From Pair to Calculator
Write out the Calculator expression with proper syntax that
corresponds to the following
Pair constructor calls.
>>> Pair('+', Pair(1, Pair(2, Pair(3, Pair(4, nil)))))
>>> Pair('+', Pair(1, Pair(Pair('*', Pair(2, Pair(3, nil))), nil)))
>>> Pair('and', Pair(Pair('<', Pair(1, Pair(0, nil))), Pair(Pair('/', Pair(1, Pair(0, nil))), nil)))
SQL is an example of a declarative programming language. Statements do not describe computations directly, but instead describe the desired result of some computation. It is the role of the query interpreter of the database system to plan and perform a computational process to produce such a result.
For this discussion, you can test out your code at sql.cs61a.org. The records table should already be loaded in. We can use a SELECT statement to create tables. The following statement creates a table with a single row, with columns named “first” and “last”:
sqlite> SELECT "Ben" AS first, "Bitdiddle" AS last; Ben|Bitdiddle
Given two tables with the same number of columns, we can combine their rows into a larger table with UNION:
sqlite> SELECT "Ben" AS first, "Bitdiddle" AS last UNION ...> SELECT "Louis", "Reasoner"; Ben|Bitdiddle Louis|Reasoner
We can SELECT specific values from an existing table using a FROM clause. This query creates a table with two columns, with a row for each row in the records table:
sqlite> SELECT name, division FROM records; Alyssa P Hacker|Computer ... Robert Cratchet|Accounting
The special syntax SELECT * will select all columns from a table. It’s an easy way to print the contents of a table.
sqlite> SELECT * FROM records; Alyssa P Hacker|Computer|Programmer|40000|Ben Bitdiddle ... Robert Cratchet|Accounting|Scrivener|18000|Eben Scrooge
We can choose which columns to show in the first part of the SELECT, we can filter out rows using a WHERE clause, and sort the resulting rows with an ORDER BY clause. In general the syntax is:
SELECT [columns] FROM [tables] WHERE [condition] ORDER BY [criteria];
For instance, the following statement lists all information about employees with the “Programmer” title.
sqlite> SELECT * FROM records WHERE title = "Programmer"; Alyssa P Hacker|Computer|Programmer|40000|Ben Bitdiddle Cy D Fect|Computer|Programmer|35000|Ben Bitdiddle
The following statement lists the names and salaries of each employee under the accounting division, sorted in descending order by their salaries.
sqlite> SELECT name, salary FROM records ...> WHERE division = "Accounting" ORDER BY salary desc; Eben Scrooge|75000 Robert Cratchet|18000
Note that all valid SQL statements must be terminated by a semicolon (;). Additionally, you can split up your statement over many lines and add as much whitespace as you want, much like Scheme. But keep in mind that having consistent indentation and line breaking does make your code a lot more readable to others (and your future self)!
The next part of the discussion will refer to the table records, which stores information about the employees at a small company.
|Ben Bitdiddle||Computer||Wizard||60000||Oliver Warbucks|
|Alyssa P Hacker||Computer||Programmer||40000||Ben Bitdiddle|
|Cy D Fect||Computer||Programmer||35000||Ben Bitdiddle|
|Lem E Tweakit||Computer||Technician||25000||Ben Bitdiddle|
|Louis Reasoner||Computer||Programmer Trainee||30000||Alyssa P Hacker|
|Oliver Warbucks||Administration||Big Wheel||150000||Oliver Warbucks|
|Eben Scrooge||Accounting||Chief Accountant||75000||Oliver Warbucks|
|Lana Lambda||Administration||Executive Director||610000||Lana Lambda|
Q3: Oliver Employees
Write a query that outputs the names of employees that Oliver Warbucks directly supervises.Run in 61A Code
Q4: Self Supervisor
Write a query that outputs all information about employees that supervise themselves.Run in 61A Code
Q5: Rich Employees
Write a query that outputs the names of all employees with salary greater than 50,000 in alphabetical order.Run in 61A Code
This last question refers to the following salaries table:
|Alyssa P Hacker||40000||80000|
|Cy D Fect||35000||74000|
|Lem E Tweakit||25000||28000|
Write a query that outputs the names of the top 3 employees with the largest salary raises from 2022 to 2023 along with their corresponding salary raises, ordered from largest to smallest raise.Run in 61A Code
Additional Exam Practice: Scheme Lists
Q7: Longest increasing subsequence
Write the procedure
longest-increasing-subsequence, which takes in a list
lst and returns the
longest subsequence in which all the terms are increasing. Note: the elements do not have to appear
consecutively in the original list. For example, the longest increasing subsequence of
(1 2 3 4 9 3 4 1 10 5) is
(1 2 3 4 9 10). Assume that the longest increasing subsequence is unique.
Run in 61A Code