Fundamentals of Computer Science

Lab 8 - Polymorphic Data Definitions, Lambda

Purpose The purpose of this lab is to practice the use of existing list-processing functions and to explore the power of lambda function definitions.

Remember

• Work in Pairs
• Change roles often
• Follow the design recipe.

Chore Today we are pairing you up with a new homework partner. When your lab TA pairs you with a new partner, sit down next to him/her and grab a computer. One of the TAs will come through and write down your Husky email addresses so that we know who is partnered up for the next few problem sets.

You may re-use whatever you did with your previous partner for this problem set but you must turn in the next solution set with your new partner.

This lab gives you a chance to get to know your partner, to exchange vital information (phone, twitter, facebook, email) and to make a first appointment (when/where you will meet to work on problem sets).

Functions

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

Use lambda expressions instead of local wherever appropriate:

• 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 a Number n and checks if all of the members of ln are greater than n.

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

Exercise 4: Design a function that consumes an LON ln and a Number n and multiplies each member of ln by n.

Polymorphic Data Definitions

   
    
(define-struct unop (fun expr)) 
;;interp. (make-unop f n) is an expression where f is a unary operator and n is the operand.
 
(define-struct binop (fun left right))
;;interp. (make-binop f n1 n2) is an expression where f is a binary operator and n1 and n2 are operands.
     
(define-struct var (x)) 
;;interp. (make-var v) where v is a variable  
       
    
     ;; An NAExpr is one of
     ;; -- (make-var Symbol)
     ;; -- (make-unop [Number -> Number] NAExpr)
     ;; -- (make-binop [Number Number -> Number] NAExpr NAExpr)
     ;; -- Number
     
   

An NAExpr is an arithmetic expression of Numbers. For example, to represent the expression
(* (add1 n) 7) as an NAExpr we write

  (make-binop * (make-unop add1 (make-var 'n)) 7)
  

• Exercise 5: Give the data definition for an arithmetic expression of Images, ImgAExpr. You want a definition that can express things like (overlay x (flip-horizontal z)). To use functions which deal with images you need: (require 2htdp/image).

  Some binary functions for Images are: above, beside, overlay, underlay.

  Some unary functions for Images: flip-horizontal, flip-vertical.

• Exercise 6: Give the data definition for an arithmetic expression of Lists, LAExpr. You want a definition that can express things like (append x (reverse z))

• Exercise 7: Abstract over the three previous data definitions to obtain a data definition for a generic arithmetic expression.

• Exercise 8: Design a function that consumes an arithmetic expression and counts all occurrences of plain data (the last case of the data def).

• Exercise 9: Design a function that consumes an arithmetic expression, aexpr, a Symbol s and a value v and substitutes all occurences of (make-var s) in aexpr with v.

  Since we can't compare functions in a check-expect, use the following to write tests for Exercise 9.

  	
  	  
  (define expr0 (make-var 'b))
  (define expr1 (make-var 'a))
  (define expr2 (make-binop + 3 expr1))
  (define expr3 (make-binop - 3 expr1))
  (define expr4 (make-binop - 4 expr1))
  (define expr5 (make-binop - 4 expr0))
  
  ;; aexpr=? : [X] [aexpr X] [aexpr X] -> Boolean
  ;; check if two aexprs are equal while ignoring their functions
  (define (aexpr=? x1 x2)
    (local [(define xs (list x1 x2))]
     (cond
      [(andmap var? xs) 
       (symbol=? (var-x x1) (var-x x2))]
      [(andmap unop? xs)
       (aexpr=? (unop-expr x1) (unop-expr x2))]
      [(andmap binop? xs)
       (and (aexpr=? (binop-left x1) (binop-left x2))
            (aexpr=? (binop-right x1) (binop-right x2)))]
      [else (eq? x1 x2)])))
  
  (check-expect (aexpr=? expr2 expr3) true)
  (check-expect (aexpr=? expr2 expr4) false)
  (check-expect (aexpr=? expr4 expr5) false)
  
  ;; To write tests for Exercise 9, one must use aexpr=? as follows
  (check-expect (aexpr=? (substitute expr4 'a expr0) expr5) true)
       
     

• Exercise 10: Design a function that consumes an arithmetic expression, aexpr, and checks whether there any free variables in the aexpr. If there is any occurence of (make-var ...) in aexpr, it means that the arithmetic expression has free variables.

• Exercise 12: Design a function eval that consumes an aexpr and returns an aexpr which represents the full evaluation of the given expression. For example: (eval (make-binop * (make-unop add1 9) 7) -> 70. An aexpr can be fully evaluated only if it has no free variables. In case the expression has free variables, it should be returned unchanged.

More Polymorphic Data Definitions

A queue is a line of people (or tasks) waiting their turn to proceed. People at the front of the line get served first and people are added to the end of the line.

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, somewhat inefficiently, using lists.


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

   
     ;; An NQueue is one of
     ;; -- empty
     ;; -- (cons Number NQueue)
     ;; where the head of the NQueue is the first item in the list,
     ;; and the tail of the NQueue is the final element of the list.
   

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

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

• Exercise 11: Design a function, size, that consumes a queue and returns its length.

• Exercise 12: Design a function that determines whether a queue is empty.

• Exercise 13: 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.
  

• Exercise 14: 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.4.

• Exercise 15: 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.

---