CIS 352   —   SPRING 2008

Exam 1: Scope and Practice

When, Where, and How

• When: Thursday, February 14
• Where: in class
• How: Closed book, closed notes.

Coverage

You should be familiar with the following:

Procedures and related things

• anonymous procedure
• higher-order procedure
• variable-arity procedure
• BNF specification
• first-class values
• special form

Static properties

• bound variables (and "occurs bound")
• capture of a free variable
• free variables (and "occurs free")
• binding occurrence of a variable (also: bound occurrence, free occurrence)
• hole in the scope
• region
• scope
• shadowing
• lexical address

You should be familiar with (and able to use) the following Scheme procedures and special forms.

Common predicates

• boolean?  
• eq?  
• equal?  
• eqv?  
• list?  
• not  
• null?  
• number?  
• pair?  
• procedure?  
• symbol?  
• zero?

List-related procedures

• append  
• car and cdr (along with cadr, cdar, …)  
• cons  
• length  
• list

Higher-order procedures

• apply  
• map

Special forms

• and  
• or  
• cond  
• define  
• lambda (and its use for variable-arity procedures)  
• let  
• letrec  
• if  
• quote (also ')

Miscellaneous

• =  
• +  
• *  
• /  
• <  
• <=  
• >  
• >=  
• memq  
• memv  
• member

1. Write a Scheme procedure to do X, where X involves one or more of the following:
   • manipulating lists
   • recursion on inductively defined structures
   • recursion on lists
   • recursion on nested lists (i.e., you have to recurse on elements of lists as well)
   • accepting procedures as arguments
   • returning a procedure as a result
   • accepting an arbitrary number of arguments

2. What are the values of the following expressions?

3. Consider the following BNF specification for <banf>. Are the following expressions members of <banf>?

4. Which variables occur {free,bound} in the following expression?

5. What is the scope of the variable x defined on line k? What is this variable's lexical address?

Practice

• Last year's Exam 1 with sample solutions.