We will start with a quiz followed by some Q & A, but I want to limit the amount of time we spend on previous material. If you are not done with the list problems, you need to finish them promptly.
This week we begin our exploration of language interpretation using pattern matchers to write parsers.
Update 20110928: Tuesday did not run this way. Some people made headway on the problems, some made almost none. However, only three students asked questions, despite the majority of the class coming in and expressing confusion. In this regard, the lab-centric model broke: people did not ask questions, which is a critical part of the feedback loop in this system.
That said, I put out a set of practice problems that expected new learning to occur, and that could have been structured better. However, the set went out because no one was ready for class the previous Tuesday—the take-home exam was used as an excuse, in some ways, not to do the preparatory material. So, to keep the class moving, we needed to do some work outside of class. In truth, I could use two, three-hour sessions per week to make this model work.
The side effect is that we spent the day doing problems in groups of 4 on paper and/or the whiteboard. This way, people had to discuss what the parts meant, and clearly communicate about the syntax and meaning of the code they were working with. I feel we loose this at the keyboard, and get into a hack-n-slash mode too easily when the keyboard is involved. Paper slows down the process and requires us to be clear.
While I'm glad we made progress on several fronts on Tuesday, I would have preferred to have more people demonstrate how they were engaging (but stuck) by asking questions. The way to demonstrate that is to ask questions, and to have evidence of the steps they had taken to share when they came to class.
These are all things to consider, and work into the next rev of the course. I'm inclined to focus the problem set more on structural recursion, and ignore other kinds of problems.
I've pulled the plan that used to be here apart, and moved some of it forward to Thursday.
Your New Best Friend: match (0m)
See this link?
http://docs.racket-lang.org/reference/match.html
You'll want to spend time reading that page. Now, most of it won't be necessary... but it is your ultimate reference and source of examples.
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.
From cond to match (30m)
match is pretty nifty. It can make quick work of taking lists apart.
Here's a small part of cond-parse rewritten as a function called match-parse.
(define (match-parse sexp)
(match sexp
[(? number? sexp) "number"]
[`(define ,(? symbol? id) ,val) "value definition"]
))
Using the documentation for match, extend match-parse to handle all of the cases you had for cond-parse. You'll have to update the check-expects, of course.
This example makes use of the most excellent quasiquote and unquote. You could also write this as
(define (match-parse sexp)
(match sexp
[(? number? sexp) "number"]
[(list 'define (? symbol? id) val) "value definition"]
))
Which might be easier for you to understand. Try and figure out why they are the same, but ask questions if you need to.
From cond to match again... (45m)
Look again at AE?. Start a new file (perhaps called username-20110927-match.rkt), and lets try rewriting AE? using match.
(define (AE? sexp)
(match sexp
[(? number sexp) true]
[(list '+ (? AE?) (? AE?)) true]))
which could also be written as
(define (AE? sexp)
(match sexp
[(? number sexp) true]
[`(+ ,(? AE?) ,(? AE?)) true]))
if you want to use quasiquote.
That, so you know, is the (almost) complete implementation of AE? using match. You need to add in handling for subtraction, and you need an else clause. Do that now, so you have a complete implementation of AE? that uses match.
Do the same now with cond-parse-ae, so that you have match-parse-ae.
It is all in the interpreter... (45m)
You've now written your first parser. It takes in a list of Scheme data and turns it into data structures.
An interpreter consumes data structures, evaluates them using a set of semantics, and produces a result. The semantics of a language are the meanings or rules we use to evaluate each syntactic form. In the case of AE, we know how plus and minus work, because we aren't creating a new universe where they do something wacky.
1. Look up how match can be used to match structures. Write a small function that experiments with this. When you think you've got something that will pull a data structure apart, grab an instructor or TA and ask if you're on the right track.
2. Write a function called interp. It should consume a valid AE structure (meaning, either a num, a plus, or minus structure) and do the correct arithmetic operations on all the parts.
The contract for interp is as follows:
;; interp : AE -> number
In other words, the interpreter takes in structures (adhering to a strict set of rules) and it returns a number.
To help get you started:
;; pni is short for parse-and-interp
(define (p-n-i sexp)
(interp (match-parse-ae sexp)))
(check-expect (pni 42)) 42)
(check-expect (pni '{+ 3 5}) 8)
(check-expect (pni '{+ 0 0}) 0)
(check-expect (pni '{- 1 1}) 0)
You may want to write more tests here to make sure you are handling the recursive nature of the language correctly.
You have now written your first parser and interpreter. The only thing between you and changing the world through the invention of the next great programming language is time and a ton of effort.
