CSE P 505 Spring 2013 Homework #1

Due: Thursday, April 11 at 11pm

In this assignment we review what we covered in the first lecture and get some practice programming in Racket.

Revision History

1 Installing the Software

You can download DrRacket by going here, selecting your platform from the dropdown menu, and clicking the "Download" button. Installing and running DrRacket should be straightforward; ask on the discussion group if you run into any difficulties.

If DrRacket is running when you install plai-typed, you may need to close and relaunch it to make the language available.

*** Important Note ***

If you see #lang plai-typed in black text, the langauge is installed and available. If you instead see #lang plai-typed in red, either the language is not installed properly or you should try relaunching DrRacket.

1.1 Racket Documentation

You can get to the main Racket documentation page by either:

• Typing F1 from the definitions or interactions pane while the cursor is in whitespace.

• Selecting Racket Documentation from the Help menu.

This opens a local HTML file in your Web browser, which shows a search box at the top of the page. If plai-typed is installed, typing "plai-typed" (without the quotes) into the search box should locate the main documentation page.

You can also search for documentation on a specific keyword by either:

• Typing F1 from the definitions or interactions pane while the cursor is on a keyword.

• Typing the keyword into the Search box at the top of the Help menu.

2 Working with Lists

Note: if you haven’t done much functional programming before (or if it’s been a while...), you may find these problems confusing. Feel free to contact the course staff or post questions to the discussion group if you’re stuck.

Recall the list operators empty, cons, empty?, cons?, first, rest, and list, and the define syntax for defining functions.

Problem 1

(test (append-lists (list 1 2) empty) (list 1 2))

(test (append-lists (list 'ant 'bird) (list 'cat 'dog))

(list 'ant 'bird 'cat 'dog))

Problem 2

Define a function reverse-list that reverses a list. For example, the following test cases should pass:

(test (reverse-list empty) empty)

(test (reverse-list (list 'fleas 'has 'dog 'my))

(list 'my 'dog 'has 'fleas))

Question: what is the running time of reverse-list in terms of the length of its argument? Is that the best that can be done?

Problem 3

Define a function append-list-of-lists that takes as argument a list of lists and returns the result of appending all of them. For example, the following test case should pass:

(test (append-list-of-lists (list (list 1 2) empty (list 3 4)))

(list 1 2 3 4))

3 Parsing and Interpretation

In class, we defined a Tree type that we used to represent program expressions. Below, we’ve renamed some things to make it look more like a conventional abstract syntax tree:

(define-type Expr

[numE (value : number)] ; a numeric literal expression

[addE (lhs : Expr) (rhs : Expr)] ; an addition expression

[mulE (lhs : Expr) (rhs : Expr)]) ; a multiplication expression

Below is a parser that converts appropriately formed s-expressions into Exprs.

(define (parse s-exp)

(cond

[(s-exp-list? s-exp)

(let ([lst (s-exp->list s-exp)])

(cond

[(= 3 (length lst))

(case (s-exp->symbol (first lst))

[(+) (addE (parse (second lst))

(parse (third lst)))]

[(*) (mulE (parse (second lst))

(parse (third lst)))]

[else (error 'parse

(string-append "unknown operator "

(to-string (first lst))))])]

[else (error 'parse (string-append "syntax error in "

(to-string lst)))]))]

[(s-exp-number? s-exp) (numE (s-exp->number s-exp))]

[else (error 'parse

(string-append "syntax error in "

(to-string s-exp)))]))

And here is an interpreter that evaluates an Expr to produce a number:

(define (interp expr)

(type-case Expr expr

[numE (value) value]

[addE (lhs rhs) (+ (interp lhs) (interp rhs))]

[mulE (lhs rhs) (* (interp lhs) (interp rhs))]))

Problem 4

Extend the Expr type and parser to support conditional evaluation with an if0 form. An if0 expression should contain three sub-expressions: a test-expr, a then-expr, and an else-expr. If the test-expr evaluates to 0, then the value of the whole expression is the value of the then-expr; otherwise, it is the value of the else-expr. (Only one of then-expr and else-expr should be evaluated.)

Problem 5

Extend the interp function to support the if0 form. Example test cases:

(test (interp (parse '(* 3 (if0 (+ 1 2) 5 (* 3 4))))) 36)

(test (interp (parse '(if0 (* 1 0) 5 (* 3 4)))) 5)

Question: can you write a test case to check that then-expr and else-expr aren’t both evaluated? If so, write such a test case. If not, explain why not.

Problem 6

Modeling addition and multiplication as separate types of syntax leads to a fair amount of code duplication (in the type definition, parser, and interpreter). If we continue this pattern for other operations (e.g., subtraction, division), the situation will only get worse.

Question: is it possible to combine these arithmetic operators into a single abstract syntactic form? If you think so, make this change to the definitions. If not, explain why this is not possible.

4 Handin Procedure

Please submit a single .rkt file with your code, along with either a .txt or .pdf file with answers to the written questions.