CSCI 305 Concepts of Programming Languages

Programming Lab 3 — Scheming Sets

Scheme:

For this lab you will need to use Scheme. It is required that you use Guile to finish this lab. Guile is installed on esus, or most Linux systems. Type guile -v to check your version. Note that Guile contains a superset of components of Scheme (like C), but we only use the Scheme part in it.

Warmup:

Begin by entering this function in Scheme. The lines that begin with a semicolon are comment lines that you need to fill in.

{`
(define (f list)
; (a) ;
(if (null? list)
; (b) ;
’()
; (c) ;
(cons (+ 1 (car 1st)) (f (cdr list)))))
`}

Lab Questions:

Question 1: Run this function as (f ’(2 7 8 1 3 9)). What output do you get?

Question 2: What does this function f do?

Question 3: Given a comment that explains the line following (a).

Question 4: Given a comment that explains the line following (b).

Question 5: Given a comment that explains the line following (c).

Member? function:

Write a function member? that determines if an element e is part of list list. This function will return #t if e is a member of the list list and #f otherwise. You may use common Scheme functions (e.g., car, cdr, cons, eq?, eqv?, equal?, null?, and list?). In case your Scheme package has a builtin member function, you cannot use it in your answer. Comment your function properly.

(define (member? e list)

; complete this function definition

)

Set? function:

Write a function set? that checks whether its argument list is a well formed set, that is, a set with no duplicates. This function will return #t if list is a set and #f otherwise. You could make use of the function member? that you have just defined.

For example:

{`
(set? (x y z)) −→ #t
(set? (a 1 b 2 c 3)) −→ #t
(set? ()) −→ #t; empty set is a set
(set? (a b b c 3)) −→ #f; duplicate, bad set 
(set? (5 9 7 1 5)) −→ #f; duplicate, bad set
(define (set? list)
; complete this function definition
)
`}

Lab Questions:

Your answers must reflect the output of your code. No credit will be given to answers if your have not submitted the correct function implementation.

Question 6: What output do you get for the call (member? ’one ’(1 2 3 4 5))?

Question 7: What output do you get for the call (member? d ’(a b c d c b a))?

Question 8: What output do you get for the call (set? ’(a b c d c b a))?

Question 9: What output do you get for the call (set? ’(it was the best of times, it was the worst of times))?

Union function:

Write a function union that takes the set union of lists list1 and list2 and returns a list representing the mathematical union of the two lists. Your function does not need to work on embedded lists. You may use the functions you defined previously (set? and member?), in addition to the common Scheme functions mentioned above. Again, in case your Scheme package has a builtin union function, you cannot use it in your answer. Comment your function properly.

(define (union list1 list2)

; complete this function definition

)

Intersect function:

Write a function intersect that takes the set intersection of lists list1 and list2 and returns a list representing the mathematical intersection of the two lists. Your function does not need to work on embedded lists. You may use the functions you defined previously (set? and member?), in addition to the common Scheme functions mentioned above. Again, in case your Scheme package has a builtin intersection function, you cannot use it in your answer. Comment your function properly.

(define (intersect list1 list2)

; complete this function definition

)

Lab Questions:

Your answers must reflect the output of your code. No credit will be given to answers if your have not submitted the correct function implementation.

Question 10: What output do you get for the call (union ’(blue eggs and cheese) ’(ham and sandwich))?

Question 11: What output do you get for the call (intersect ’(blue cheese and cherry) ’(cheese and blue eggs)?

Question 12: Name something you like about Scheme. Explain.

Question 13: Name something you dislike about Scheme. Explain.

Question 14: How many hours did you spend on this lab? (Use your best estimate.)

Question 15: Did you enjoy this lab? Do you think you will use Scheme again?

Troubleshooting

This lab requires an independent study of the Scheme language. Use any web tutorials and resources to learn Scheme. Given the size of the class, we will not be able to debug your code for you. Please do not send panicked emails requesting us fix your bug for you — same as when you work for a company. Do allow yourself plenty of time, and use patience, perseverance, and the internet to debug your code. On the other hand, if you do need help for clarifications and general ideas, you are welcome to contact us.