We will begin with Q & A. I would like it if any question you want to ask is first asked in Piazza. You can hash tag it with #s29 to indicate that it is a question that is (specifically) for in-class. Any question you ask in class must be entered into Piazza as well.
You will then be expected to capture the answer to your own question, and report it back to Piazza as an answer. This is not to discourage you from asking questions: it is to help you learn.
We will then move on to a short introduction to parsing and interpretation.
UPDATE: Thursday actually was spent in Q & A (around 40 minutes) and then I issued the problem "squeeze", because it was being explored in CMPSC 210 at the same time. This is a problem that asks you to remove all of the characters in string1 that occur in string2. In other words, you look at two sets, and remove all of the elements in S1 that occur in S2. In C, this is a (my opinion) tedious operation involving the proper handling of null-terminated blocks of memory. In Scheme, it is a simple recursive procedure on lists.
"From Structure to Learning" was left to the students to do on their own time, and the subsequent sections became the work of Tuesday the 4th.
From Structure to Learning
UPDATE: As you prepare for Tuesday, October 4th (or O4), you can skip this section. However, you should do this for yourself regardless. If you do not feel you mastered the material in the previous problem set, you will likely struggle as we move forward. Given how few questions have been asked out of class, I must assume you are, as a class, mastering the material. If you have not, and you are not asking questions, then you are failing to take responsibility for your learning.
The lab-centric model of instruction puts the onus on you to read, explore, become confused, read some more, and throughout that process, ask questions when you feel you are not yet understanding the material. My role is to assign learning tasks that I think will be of benefit to you on this journey. I am working hard to resist the idea that me reading to you (giving a lecture) is somehow better than you discussing and debating problems with me and/or your peers.
I was about to write what I thought the essential "take-aways" are for each of the problems. Instead, that is your task for tomorrow's class: what is the essential learning outcome for each of these problems or groups of problems?
Questions 1, 2, and 3 are related.
Questions 4, 5, and 6 are related.
Questions 7, 8, 9, and 10 are, in many ways, related.
Question 11, in some ways, sets you up for later problems. Why?
Questions 12, 15, and 16 are related.
Questions 17 and 18 are related.
Question 19 is vaguely related, and is (in some ways) out of place.
The remaining questions challenge you to bring together what you learned from the previous questions. You may find lessons in each, but they are where it all comes together.
Up through question 10 are the core ideas that you must master. Successfully working questions past that point prepare you for the kinds of work you will be doing, but the concepts are (possibly) indirect to the task of writing interpreters.
Interpreting Structures
UPDATE: We will essentially begin here on O4. I will add additional content to O4 for in-class activity, but it will be in keeping with what you find here. A placeholder page for O4 has been created.
Today, we'll be working into our exploration of parsers. A parser takes code as input and produces a data structure as output. By code I mean "the textual source code of a program." By data structure I mean... well, a data structure. Like those things produced when we use define-struct.
Identifying Syntaxes We Know with cond (30m)
The first challenge is to match syntaxes we are familiar with using cond. I would like you to write a function called cond-parse that consumes a list of symbols, numbers, and lists, and tells me what kind of syntax it is. (In other words, it will consume a list representing a piece of Scheme code.)
For example, I should be able to write:
(cond-parse 42)
and get back the string
"number"
The following are your check-expects for this problem.
#lang racket
(require test-engine/racket-tests)
;; CONTRACT
;; cond-parse : ...
;; PURPOSE
;; ...
(define (cond-parse expr) '...)
;; TESTS
(check-expect (cond-parse 42) "number")
(check-expect (cond-parse 'artistformerlyknownas) "symbol")
(check-expect (cond-parse "Uh oh.") "string")
(check-expect (cond-parse false) "boolean")
(check-expect (cond-parse true) "boolean")
(check-expect (cond-parse '(1 2 3)) "list")
(check-expect (cond-parse '(a b c)) "list")
(check-expect (cond-parse '(define meaning 42)) "value definition")
(check-expect (cond-parse '(define x (+ 1 3)))
"value definition")
(check-expect (cond-parse '(define-struct point (x y)))
"point structure")
(check-expect (cond-parse '(define-struct onion (color ogre)))
"onion structure")
(check-expect (cond-parse '(define (even? n) ...))
"definition of function even? with body ...")
(check-expect (cond-parse '(define (super n) ...))
"definition of function super with body ...")
(test)
The order of your cond clauses will matter. You will want to research the format function for some of these; ask if you get stuck/confused on the use of format.
This is not exactly a parser. It does not create a data structure as a result; instead, it is something that tells us what kind of thing has been input. But, it does get us thinking about how to use cond to identify syntaxes.
STOP. At this point, find someone who is still working on this, and check and see if they could use a copilot. Proceed when you both reach this point.
Before proceeding, the instructor or TA must sign off on your work.
Identifying New Syntaxes with cond (45m)
Now, we're going to try something different.
A grammar defines a language. If we wanted to define a grammar for arithmetic expressions (AE), we might define the grammar as follows:
<AE> ::= <number?>
| {+ <AE> <AE>}
| {- <AE> <AE>}
This is an example of a BNF for a language. It says that an AE (an Arithmetic Expression) is either
• a number, or
• an expression that starts with a sqiggly bracket, followed by a plus and two more AEs, and then a closing squiggly, or
• it is an expression that starts with a sqiggly bracket, followed by a plus and two more AEs, and then a closing squiggly.
From the BNF, you can tell we're going to have three cond clauses. In the BNF, each right-hand side will likely yield one cond clause.
Note: The squiggly is handled by DrRacket as if it were a paren. You do not need to do anything special to detect them; treat them as lists. They are used to set off programs written in the AE language from the rest of our Scheme code.
Exercises
1. Write a function called AE?. It should consume any Scheme expression, and return true if it is an AE.
(check-expect (AE? 42) true)
(check-expect (AE? '{+ 3 5}) true)
(check-expect (AE? '{- 3 5}) true)
(check-expect (AE? '{+ 3 x}) false)
(check-expect (AE? 'artistformerlyknownas) false)
This will, you may have noticed, require some recursion. How do we know? Because AE's definition contains AEs. Therefore, everywhere you see an <AE> in the BNF, you should expect to see a recursive call to AE?.
2. Define a structure called num. It should have one field called value.
3. Define a structure called plus. It should have two fields, lhs and rhs.
4. Define a structure called minus. It should have two fields, lhs and rhs.
5. Define a function called cond-parse-ae. It should consume any valid AE, and return a parsed version of that expression. That is, when a number is encountered, a new num structure should be created. When a plus expression is encountered, a new plus structure should be created.
Note that I use { and } to indicate code being written in the AE language.
(check-expect (cond-parse-ae 42) (make-num 42))
(check-expect (cond-parse-ae '{+ 3 5})
(make-plus (make-num 3) (make-num 5)))
(check-expect (cond-parse-ae '{- 0 0})
(make-minus (make-num 0) (make-num 0)))
(check-expect (cond-parse-ae '{+ {+ 0 0} {+ 0 0}})
(make-plus (make-plus (make-num 0) (make-num 0))
(make-plus (make-num 0) (make-num 0))))
You might want to write a few more tests here.
You have now written your first parser. It consumes code, and produces data structures as a result.
STOP. Find someone who is still working on this part, and ask if they would like a copilot. Continue when they have reached this point.
Turn In
1. Extend the BNF with expressions for multiplication and division. Extend your parser to include these, and create data structures that are appropriate. Save this in username-parser1-basic.rkt.
2. Write a set of check-expect statements that you feel completely test your parser. You are not trying to make it fail—but you do want to be sure it works in all likely/possible cases. Save these in the above file, and be sure everything works.
UPDATE: For Thursday, ignore part 3 if you want to. We'll get there. Or, you can do it; it isn't hard. It is a good idea to do it, though. It shows you how we can use multiple data representations for our grammar, and get the same result.
3. Merge your four data structures (plus, minus, and so on) into one structure called arith. It should contain three fields: op, rhs, and lhs. Rework your parser accordingly. Save this in username-parser1-refactor.rkt. Copy your test cases into this file, and demonstrate to yourself that your parser still works.
