Lab 9: Highway to Abstractions

Remember

Work in Pairs
Change roles often
Follow the design recipe.

Exit 1: Functions

 
    ;; An LON is is one of
    ;; -- empty 
    ;; -- (cons Number LON)

Exercise 1: Design a function that consumes an LON ln and checks if 0 is a member of ln.

Exercise 2: Design a function that consumes an LON ln and checks if 6 is a member of ln.

Exercise 3: Abstract over the previous two functions to design a function that consumes an LON ln and a Number n and checks if n is a member of ln.

Exercise 4: Design a function that consumes an LON ln and filters out all members of ln that are greater than 3.

Exercise 5: Design a function that consumes an LON ln and a Number n and filters out all numbers less than n in ln.

Exercise 6: Abstract over the two previous functions.

Exit 2: Polymorphic Data Definitions


     (define-struct unop (expr)) 
     (define-struct binop (left right))
     (define-struct var (x)) 
        
     ;; An NAExpr is one of
     ;; -- (make-var Symbol)
     ;; -- (make-unop NAExpr)
     ;; -- (make-binop NAExpr NAExpr) 
     ;; -- Number

Exercise 7: An NAExpr is an arithemetic expression of Numbers. Give the data definition for an arithemetic expression of Booleans, BAExpr.

Exercise 8: Abstract over the two previous data definitions to obtain a data definition for a generic arithemetic expression.

Exercise 9: Design a function that consumes an arithemetic expression and counts all occurrences of plain data (the last branch of the data def).

Exercise 10: Design a function that consumes an arithemetic expression, sexpr, a Symbol s and a value v and substitutes all occurences of (make-var s) in sexpr with v.

Quiz

Turn off your monitors
Closed book, closed notes
No talking and no surfing the web until all quizes have been handed in

New Homework Pairs

Write down your partner's:
1. name
2. email
3. telephone number
4. AIM
5. homework server user name
Arrange a meeting as early as possible
Update your blue book

Exit 3: More Polymorphic Data Definitions

A queue comes with two functions: enqueue and dequeue. Enqueue adds an element at the end of a queue and dequeue removes an elements from the front of a queue.

We will implement queues using lists.

A data definition for a queue of Numbers is the following:

     ;; An NQueue is one of
     ;; -- empty
     ;; -- (cons Number NQueue)

Exercise 11: Give the data definition for a queue of Symbols.

Exercise 12: Abstract over the two previous data definitions to obtain a data definition for a generic queue.

Exercise 13 Design a function that consumes a queue and returns its length.

Exercise 14 Design a function that determines whether a queue is empty.

Exercise 15: Design enqueue . The function consumes an element and a queue. It produces a queue with the element added at the end of the given queue.
Hint: check append in the Help Desk

Exercise 16 Design a function that consumes a queue and produces the first element of the queue, unless it is empty. If it is empty, the function signals an error. See checked functions in section 8.

Exercise 17 Design the function dequeue that consumes a queue and returns the queue that contains everything but the first element from the given queue. If the given queue is empty, the function signals an error.