CMSC 331 Final Review

The final will be a closed book exam. The exam will cover all of the material in the course, however the emphasis will be on the material we've covered since the midterm examination.

The syllabus gives the topics we covered. You are responsible for all of the material in the assigned readings mentioned in the syllabus as well as material covered in class. Copies of the slides used in class are online and linked to the syllabus.

Below are some questions and problems that you can use in preparing for the final. You should also look at the old exams that are online.

General topics

Here is a list of topics that you should be familiar with. You should:

• Be able to explain the difference between high level and low level languages
• Be able to name four benefits provided by high level languages
• Be able to explain the difference between a compiler and an interpreter
• Understand the basic difference between semantics and syntax
• Understand the difference between prefix, postfix and infix notation
• Understand operator precedence and associatively
• Be able to write a simple BNF grammar for a language described in English.
• Be able to show a parse tree given a grammar and a string in that language
• Be able to prove that a BNF grammar is ambiguous and to show how to change it to remove the ambiguity.
• Be able to illustrate the difference between lexical (aka static) and dynamic variable scope
• Be able to compare and contrast functional and imperative programming languages
• Understand that functional programming is expression-oriented programming and that programs are expressions that evaluate to values
• Be able to define basic data structures using Scheme lists and to write simple recursive list processing functions.
• Understand that programming languages are simply tools that we use to do our job of solving problems!

General Concepts

• Define tail recursion. Why is it of interest.
• Give three examples of "programming paradigms" and, for each one, identify a programming language that typifies it.
• You are developing a program and must choose between two imperative languages, one of which is interpreted and the other of which is compiled. Under what conditions should you use one instead of the other? Under what conditions does your choice not matter? Cover the following (mutually exclusive) conditions:
  1. You're in a hurry to make the program work.
  2. The program must execute efficiently and with maximal speed.
  3. The program must occupy very little memory.
  4. The program needs a lot of dynamic memory.
  5. The program is huge.
  6. The program is small.
  7. The program must be ported to a lot of machines.

Languages, parsing and grammars

• What does YACC stand for? What does LEX stand for?
• Give an example of a language construct that can not be recognized by a context free grammer?
• Give an example of a language that can not be recognized by a regular grammar but can be recognized by a context free one.
• A finite language is one which has a finite set of sentences. Can any finitie language be recognized by a regular expression?
• Give LEX and YACC files for English ("Standard American" dialect). Use the back of the page if neccessary.
• Describe how a recursive descent parser works.
• Consider the following BNF grammar:

1. (extra credit) Describe the semantics of the following faces:
   1. :+Q
   2. D-;|
• Write a context-free grammar using EBNF for each of the following languages.
  • All binary numbers with 1 or more digits that are palindromes. A palindrome is a sequence of characters that has the exact same sequence when read from left-to-right as it does from right-to-left. E.g., ``101'' and ``0110'' are palindromes.
  • All sequences of vowels that include exactly one occurrence of the letter ``e'' and whose length is >0. Do not include the letter ``y'' as a vowel.

Scheme

• What does (weird 1) return given this definition:

       (define (weird i) (let ((i (* i 2))) (let ((i (* i 3))) i)))              

• Consider the function length which takes a list and returns the number of top-level elements in it. A simple recursive version can be written as:

       (define (length l) (if (pair? l) (+ 1 (length (cdr l))) 0))
  

  Explain why it is not tail recursive.
• Write a tail-recursive version. Hint: try completing the following approach:

  (define (length l) (tail-recursive-length l 0))
  (define (tail-recursive-length l n) ...)        

• The builtin Scheme function map applies a function to each element of a list and returns a list of all results. Implement it in Scheme recursively without using any other mapping function or global variables. You will at least need `if', `null?', `cons', `car', `cdr', and `apply'. Example: (map add1 '(1 2 3)) => (4 5 6)

• Write a simple version for map that takes just two argument, where the first being a function of one argument and the second is a proper list. Write the general version of map that takes N (where N>0) arguments where the first is a function of N-1 arguments and the remaining N are lists of equal length. Example: (map < '(1 2 3) '(3 2 1)).

• Write iota as a Scheme function that takes a positive integer as an argument and returns a list of the numbers between 1 and that integer.

       > (iota 5)
       (1 2 3 4 5)
       > (iota 1)
       (1)
       > (iota 0)
       ()
       > (iota -2)
       ()        

• Consider the following Scheme function definition:

(define (mystery l a) 

     (cond ((null? l) a) 

           (else (mystery (cdr l) (cons (car l) a)))))

Give the values of the following expressions, explaining your reasoning.

1. (mystery '(1 2 3 4 5) '())
2. (mystery '() '(1 2 3 4 5))

 

• Draw a box and pointer representation of the following lists: (1 2 3) (((1))(2) 3) (1 . 2) ((()))

 

• Show the values returned by each of the following expressions.

    > (define L1 (cons '(1 2) (cons (cons 3 nil) '(4 (5)))))
    
    > (car (cdr (cdr L1))
    
    > (cdr (car L1))
  
  
  

 

• Write a simple Scheme function contains which takes two arguments both of which are arbitrary expressions and returns #t if the first is equal to or contained somewhere within the second and #f otherwise. For example:

  > (contains 'C '(A '(B (C)) D))
  #t
  > (contains 'E '(A '(B (C)) D))
  #f
  > (contains '(B (C)) '(A '(B (C)) D))
  #t
  > (contains '(A B) '(A B))
  #t
  > (contains 'A 'A)
  #t
  > (contains '(B (C)) 33)
  #f
  

• Give at least two reasons why macros are useful in Scheme.
• Write a recursive function that returns the depth of the most deeply nested atom of a list. The depth of an empty list is 0, the depth of any atom in a linear list is 1, the depth of any atom in a list inside a list is 2, and so on. You can use the system defined function max that returns the maximum of its arguments. Your function should work like this:

  (maxdepth '()) = 0
  (maxdepth '(a)) = 1
  (maxdepth '(a (b))) = 2
  (maxdepth '(a ((b h) c) j)) = 3
  

   

• Write a function collect that takes a list lst and a number n and returns a new list in which the elements of lst are grouped into sublists of length n. The last sublist might be shorter than n if there are no more elements in the list. Example:

  (collect '(a b c d) 2) = ((a b) (c d))
  (collect '(a b c d e) 3) = ((a b c) (d e))
  

   

• Write Scheme code to cefine a function max-of that takes one argument, a number, and returns the greatest argument passed to it so far [Hint: you need a function that keeps its state. Use a closure.] Examples:

  (max-of 3) = 3
  (max-of 5) = 5
  (max-of 1) = 5        

• You are given the following definitions:

  (define (foo) (let ((x 10)) (lambda (y) (* x y))))
  (define (bar) (let ((x 20)) (foo 30)))

  Show the value returned by the function call (explain briefly your result): (bar)
• Write recursive Scheme functions height and weight each of which take one expression and returns an integer for the height and weight of their argument, where:

  • the height of an atom is 0.
  • the height of a list is one plus the maximum height of any of the elements of the list.
  • the weight of an atom is 1.
  • the weight of the empty list is 0.
  • the weight of a list is the sum of the weights of its elements.
• Write a function called shuffle which takes two lists as input (assume both lists have the same length) and returns one list which contains the first element of the first list followed by the first element of the second list followed by the second element of the first list and so on, like this:

       > (shuffle '(A K Q) '(J 10 9))
       (A J K 10 Q 9)
  

• Given the following Scheme code

  (define (unknown L)
      (cond ((null? L) null)
            (else (cons (list (cadar L) (caar L))
                        (unknown (cdr L))))))
  

  what is the result of evaluating the following expression?

       (unknown '((1 a) (2 b) (3 c) (4 d) (5 e))))
              
  Implement the function without recursion using map.        

• What is the result of evaluating the following LISP expression?

       ((lambda (x y) (+ x y y 3)) 2 5)        

• In the following expression, put squares around the free variable references, and circles around the bound variable references. Put lines between the bound references and the places they are bound. Also, show the result returned by each expression.

      (let ((x 1))
        (let ((f (function (lambda (y) (list y x)))))
             (let ((x 2)) (list x (funcall f x)))))
    
      RESULT:         

• Many languages have a macro facility. They were first used in assembly languages and helped to relieve some of the tedious and repetitive coding required by assembly language.
  • What is the difference between a macro and a function?
  • Briefly describe the macro facility in Scheme
• Define a closure. Why is it useful.
• Suppose we define the function adder as:

      (define (adder n) (lambda (x) (+ x n)))

  What should ((adder 10) 5) return. How would you describe what (adder N) returns where N is some number?
• Suppose we define the function curry as follows:

  (define (curry function . args)
      (lambda more-args
        (apply function (append args more-args))))

  Nore that this defines curry such that it has one required argument (function) and any number of optional arguments which are assembled into a list and bound to the parameter args. What should ((curry + 100) 5) return. Can you describe what curry does?
• Consider the problem of creating a strem of the Fibonacci numbers (e.g., 1 1 2 3 5 8 13 ...). The series is defined as fib(1)=1, fib(2)=1 and fib(N)=fib(N-1)+fib(N-2). Write a simple expression that assigns the variable FIBS a value that is an infinte stream of the Fibonacci numbers. (Hint: you can do this easily by binding FIBS to a stream whose first elment is one, whose second element is one, and whose remaining elements are a stream formed by adding the streams FIBS and (scdr FIBS)).
• To what will each of the following expressions evaluate assuming an environment in which x is 10, y is 100 and z is 1000.
  • (* x y)
  • ((lambda (x y) (* x y)) 2 3)
  • ((lambda (x) (* x y)) 2)
  • ((lambda (y) (* x y)) 2)
  • ((lambda () (* x y)) )
• Briefly describe what the following functions does.

  (define (foo f g) (lambda (x) (f (g x))))

  What should the arguments F and G be if this function is to make sense? How would you describe the return value of each of these expressions
  • (foo add1 abs)
  • (foo not integer?)
  • (foo (lambda (x) (> x 0.5)) (foo (lambda (x) ( + 0.1 x)) abs))

Functional Programming

• Understand the benefits and drawbacks of a functional programming style

• Be able to recognize tail calls and understand the notion of tail-call optimization as well as its importance in a language that encourages recursion

• Understand how to use functional programming concepts in both Scheme and Python

  • lambda
  • closures
  • map
  • reduce
  • filter

Other

• Suppose we have a row of 100 lights, and in front of each light a light switch. The switches are each a simple toggle switch and initially all turned off. Activating a switch changes it's mode (from off to on or from on to off). In addition there are 100 frogs which jump (in order) on the switches in the following manner. Frog #1 jumps on switch 1, 2, 3, ... 100; Frog #2 jumps on switch 2, 4, 6, 8, ...; Frog #3 jumps on switch 3, 6, 9, ...; and in general Frog #i jumps on switch i, 2*i, 3*i, ... After all 100 frogs make their passes through the light switches, which lights are on? Explain. Clearly.
• The phrase "The first number not nameable in under eleven words" appears to name it in nine words. Is this a problem?