lisp/functional programming practice questions

Sample discussion questions

(D1) Higher order functions

The sort function in lisp takes two arguments: the list to be sorted and the comparison operation to be used when sorting, e.g. (sort '(10 6 17 -3 8) '<)
Briefly explain how this relates to our discussions of higher order functions in lisp.

(D2) Benefits of "pure" functional programming

In the lectures we mentioned ease of testability and support for concurrency as two reasons for using functional programming.

For the version of lisp we're using in the labs and assignment, discuss some of the language features that make it less suitable in those terms, and why you think this is the case.

(D3) Static vs dynamic typing

Lisp uses dynamic typing - i.e. variables/parameters do not have a specific type associated with them, rather their current type is purely a reflection of the value currently stored in them.

Discuss how programming in lisp would be impacted if each lisp variable and parameter had to have a fixed defined data type.

(D4) Identifiers

In many programming languages identifiers are case sensitive. In common lisp, however, identifiers by default are not case sensitive, e.g. by default x and X are treated as the same variable.

In common lisp, like most languages, identifiers cannot normally contain whitespace. Unlike most languages, however, you can allow identifiers to contain whitespace and you can also make them case sensitive by enclosing the identifier in | symbols. For example, |abc xyz| could be a valid variable name, and |x| and |X| would indicate different variables.

Discuss the potential advantages and disadvantages of using common lisp's approach to identifiers.

(D5) Macros and closure

(i) Clearly and carefully describe the differences between closure and macros.
(ii) Provide an example illustrating where using a macro would be more suitable than using closure.
(iii) Provide an example where using closure would be more suitable than using a macro.

(D6) Symbols and property lists

Are symbol property lists appropriate in a pure functional language? Why or why not.

(D7) Macros, let

Suppose a macro takes let blocks of the form shown on the left and transforms them into code of the form shown on the right, where the function names FNNNN are generated via gensym.

(let ((var1 val1)(var2 val2) ... (varM valM)) (statement1) (statement2) ... (statementN))

(apply '(FNNNN (var1 var2 ... varM) (if (and (statement1) nil) nil (if (and (statement2) nil) nil ... (statementN)...))) '(val1 val2 ... valM))

Would this allow lisp programmers to write their code using let blocks, while maintaining functional "purity"? Clearly describe why or why not.

(D8) Context free grammars

In lectures we discussed the simple context free grammar shown below, to handle unary and binary arithmetic expressions with +, -, *, and /, operating on integers and variables.

Suppose we now want to add "string" as a data type, with unary operators "length" and "reverse", and binary operator "append".

Discuss in detail the changes that must be made to the grammar to support this.

;    Statement --> Value
;              --> Expression
;    Expression --> (UnaryOperator Statement)
;               --> (BinaryOperator Statement Statement)
;    BinaryOperator --> +, -, *, /
;    UnaryOperator --> +, -
;    Value --> symbol, integer

(defun statement (s)
   (cond
       ((value s) t)
       ((expression s) t)
       (t nil)))

(defun expression (e)
   (cond
       ((not (listp e)) nil)
       ((< (length e) 2) nil)
       ((null (cddr e))
          (and (unaryOp (car e)) (statement (cadr e))))
       ((null (cdddr e))
          (and (binaryOp (car e)) (statement (cadr e)) (statement (caddr e))))
       (t nil)))

(defun binaryOp (op)
   (cond
       ((equalp op '+) t)
       ((equalp op '-) t)
       ((equalp op '/) t)
       ((equalp op '*) t)
       (t nil)))

(defun unaryOp (op)
   (cond
       ((equalp op '+) t)
       ((equalp op '-) t)
       (t nil)))

(defun value (v)
   (cond
       ((integerp v) t)
       ((symbolp v) t)
       (t nil)))

(D9) Nested functions using labels

In lectures, we considered the use of the labels feature as a way to provide private "helper" functions.
(i) Give a clear example of a situation where this is useful.
(ii) Describe why labels are more than just a syntactic improvement over the use of lambda functions assigned to local variables.

Sample lisp questions: reading/comprehending

Study the lisp functions f and h below, then answer questions (a), (b), and (c).

; perform some type/error checking,
;    then call function h to ....
(defun f (L N)
   (cond
       ((not (listp L)) nil)
       ((not (integerp N)) nil)
       ((< N 1) nil)
       ((< (length L) N) nil)
       (t (h L N '()))
   )
)

(defun h (L N Acc)
   (cond
       ((eq N 1) (append Acc (cdr L)))
       (t (h (cdr L) (- N 1) (append Acc (list (car L)))))
   )
)

(a) For the function call (f '(1 2 3) 1) show the sequence of calls (if any) made to function h, and show the final value returned by function f.

(b) For the function call (f '(1 2 3 4) 3) show the sequence of calls (if any) made to function h, and show the final value returned by function f.

(c) If we observe that function f appears to carry out some basic type/error checking and then calls function h to do the "real" work, what is it that h actually accomplishes?

(R2) Understanding lisp functions

Study lisp functions f and h below, then answer questions (a) through (c).

(defun f  (L) 
   (if (not (listp L)) L (h L '())))

(defun h (L A)
   (if (eq L '()) A (h (cdr L) (cons (car L) A))))

(a) Show the sequence of calls that would be made to function h when evaluating (f '(1 2))

(b) Show the sequence of calls that would be made to function h when evaluating (f '(10 20 (30 40)))

(c) What appears to be the purpose of functions f and its helper function h?

(R3) Labels, local functions and scope

(a) For each variable and parameter in the lisp script shown below, clearly identify and explain its exact scope.

(b) Show the precise output from the script below.

#! /usr/bin/gcl -f

(defvar x 0)

(defvar v1 1)

(defun foo (p0)
   (declare (special x))
   (format t "in foo, x is ~A, p0 is ~A~%" x p0))

(defun f1 (p1)
   (let  ( (v2 2) (x "hi"))
         (labels (   (f2 (p2 x) 
                         (format t "in f2, p2 is ~A, x is ~A~%" p2 x)
                         (format t "in f2, about to call (foo ~A)~%" p2)
                         (foo p2)))
            (format t "in f1, p1 is ~A, v2 is ~A, x is ~A~%" p1 v2 x)
            (format t "in f1, about to call (f2 ~A ~A)~%" v2 p1)
            (f2 v2 p1)
            (format t "in f1, about to call (foo ~A)~%" p1)
            (foo p1))))

(format t "globally, v1 is ~A, x is ~A~%" v1 x)
(format t "globally, about to call (f1 ~A)~%" v1)
(f1 v1)

(R4) Higher order functions

Show the result of each of the following expressions and clearly show how that result is derived.
1. (eval '(- 1 2 3))
2. (funcall '- 1 2 3 4)
3. (apply '- '(2 4 6))
4. (map 'list '- '(1 2) '(5 10) '(4 6))
5. (maplist 'car '(1 2 3))
6. (mapcar '- '(1 2 3))
7. (reduce '- '(4 3 2 1))

(R5) Macro use

Show the output of the script below, and explain the apparent purpose of the macro.

#! /usr/bin/gcl -f

(defmacro /\ (&rest L) `(lambda ,@L))

(setf f (/\ (x) (* x x)))
(format t "f(2) ~A~%" (funcall f 2))

(R6) Macro expansion

For the macro definition and use below, show the code that would be produced when the macro is expanded prior to compilation.

(defmacro within (N low high)
   `(cond
        ((and (not (numberp ,low)) (not (numberp ,high))) nil)
        ((not (numberp ,N)) nil)
        ((< ,N ,low) ,nil)
        (t (<= ,N ,high))))

(defvar x (read))
(defvar ok (within x 1 10))

(R7) Dynamic scope

Show the output from the following script:

#! /usr/bin/gcl -f

(defvar z "global")

(defun f ()
   (declare (special z))
   (format t "1: ~A~%" z))

(defun g (&optional (z "opt"))
        (format t "2: ~A~%" z)
        (f))

(defun h ()
   (let ((z "block"))
        (format t "3: ~A~%" z)
        (f)))

(f) (g) (h)
(format t "4: ~A~%" z)

(R8) Macros

For the macro and call below, show the code that would be produced when the macro call is expanded.

(defmacro concat (strList)
   ; assuming strList is a list of strings,
   ; concatenate them all together
   `(reduce
       (lambda (str1 str2) (concatenate 'string str1 str2))
       ,strList))

(format t "~A~%" (concat '("first" "second" "third")))

(R9) Macros and gensym

The code below shows what happens when we macro-expand an OR statement.

Based on the code shown, clearly explain how and why the OR macro is implemented the way it is, particularly with respect to the gensym symbols.

>(macroexpand '(or x y z))

(LET ((#:G1567 X))
  (IF #:G1567
      #:G1567
     (LET ((#:G1566 Y))
          (IF #:G1566
              #:G1566
              Z))))

T

Sample lisp questions: writing lisp

Without using member, or similar membership-testing built-in functions,
write a lisp function, contains, that takes two parameters: a list L and a potential element E.
The function returns true (t) if list L contains element E, false (nil) otherwise.

(W2) Property tests

Now write a new lisp function, containsIf, that takes three parameters: a list L, a potential element E, and a function f.
The new function returns true iff E is an element of L and (f E) evaluates to true.
For example, someone might make the call (containsIf '(1 2.2 3 4.01 5) 3 'integerp).

(W3) Tree representations

Suppose a binary tree with integer internal data is represented in the form (nodeId leftsubtree rightsubtree) with empty lists used for empty subtrees.

For example, (3 (4 () ()) (10 (1 () ()) (6 () ()))) would represent the tree

        3
       / \
      4   10
         /  \
        1    6

Write a lisp function called rightmost that returns the id of the rightmost node in the tree. I.e. for the tree above (rightmost (3 (4 () ()) (10 (1 () ()) (6 () ())))) would return 6.

(W4) Closure

Write a function (safelyApply func typechk) that works as follows:
• func and typechk must both be functions, otherwise return nil
• otherwise build and return a lambda function that takes one parameter, arg.
• If arg is not a list the lambda function should return nil,
• otherwise if (typechk arg) returns true the lambda function should apply func to arg and return the result,
• otherwise the lambda function should return nil.

(W5) Variable number of arguments: &rest

Write a lisp function, dispArgs, that expects at least one parameter, but uses the &rest token to permit it to accept any number of parameters greater than zero. The function should display the number of parameters passed to it and should display each parameter on a line by itself.

For instance, the call (dispArgs 1 2 3) would result in output like
3 parameter passed
1
2
3
The call (dispArgs "hi") would result in output like
1 parameter passed
hi

(W6) Interval operations

The idea of interval math operations is that each number is given a range, rather than a specific value, e.g. (3.5 3.7) represents a number that could be anywhere in the range 3.5-3.7.

Operations performed on ranges must take into account the possible range of the outcome, e.g. (3.5 3.7) + (4.1 5.2) could result in values anywhere from 7.6 to 8.9.

If an interval is a list of two real numbers (low high) where low <= high,

1. Write a function (check-iv int) that returns true iff int represents a valid interval.

2. Write a function (contains int num) that returns true iff int is a valid interval, num is a valid number, and num lies within the range specified by int.

(W7) Let over lambda

We considered some examples of using let-over-lambda (with labels) to implement something akin to classes and methods in common lisp.

Use this approach to create a (fraction numer denom) function that allows users to work with fractions. The local methods required are setNumerator, setDenominator, and getAsFloat (which should return numer/denom as a float).

(W8) Parsing lisp in lisp

Write a function, lambdaArgs, that takes a single parameter, p. lambdaArgs should return nil if p is not a lambda function, otherwise it should return a list whose first element is the number of required parameters to the function, and whose remaining elements are the default values for any optional parameters (if any).

(W9) Tail recursion

Rewrite the function below to be tail-recursive - you may add extra parameters if needed, but either provide default values for them or include a comment describing what the 'initial' call values should be.

; assuming numLists is a list of list of numbers,
; return a list of the smallest value from each sublist
; e.g.  (mins '((1 2 3) (6 5 4) (8 7 9))) would return (1 4 7)
(defun mins (numLists)
   (cond ((null numLists) nil)
         ; use min on the front list to get its minimum value, and
         ;    call recursively to get the remaining minimum values
         ; use cons to combine the two parts into a single solution
         ((cons (apply 'min (car numLists)) (mins (cdr numLists))))))

(W10) lambda functions

Write a lambda function that takes two variables, x and y, and returns the result of 3xy+4y², or nil if either is not a number.

(W11) apply and mapcar

Suppose the mapcar function, (mapcar func arglist), was not supplied with lisp.

Provide an implementation that achieves the same functionality through recursion and the use of apply.

(W12) Parsing strings

In lectures we discussed the function (int str) shown below, to recognize an integer provided as text, optionally preceeded by + or -, and return its corresponding integer value.

Suppose we want to recognize strings which represent valid variable names, where variable names must begin with a letter (a-z or A-Z) and then may have any number of alphanumeric characters and/or underscores.

Provide a function (variable str) that checks if str represents a valid variable name, and if so creates/returns the corresponding symbol using (intern str). You may create additional helper functions if needed.

(defun digit (d)
   (cond ((not (characterp d)) nil)
       ((not (member d '(#\0 #\1 #\2 #\3 #\4 #\5 #\6 #\7 #\8 #\9))) nil)
       (t (- (char-code d) (char-code #\0)))))

(defun int (str)
   (cond ((not (stringp str)) nil)
       ((equalp str "") nil)
       ((char= #\+ (char str 0)) (intVal (subseq str 1) 0))
       ((char/= #\- (char str 0)) (intVal str 0))
       (t (let ((result (intVal (subseq str 1) 0)))
             (if (null result) nil (- result))))))

(defun intVal (str soFar)
   (cond ((equalp str "") soFar)
      ((not (digit (char str 0))) nil)
      (t (intVal (subseq str 1) (+ (* 10 soFar) (digit (char str 0)))))))

(W13) Higher order functions

Implement the doNtimes function specified below.

; (doNtimes f N arg)
; ------------------
; applies function f a total of N times,
;    initially to arg and afterwards to the result
;    of the previous call to f
; e.g. (doNtimes f 3 arg) effectively runs (f (f (f arg)))
;
; doNtimes takes three parameters:
;    f - a function that takes one argument as a parameter
;           and returns a value of the same type
;        (e.g. sqrt takes a number and returns a number)
;    N - an integer value greater than or equal to 0
;    arg - a value suitable as an argument to f
;
; if f is not a function return nil,
; otherwise if times is not an integer, or is negative, return nil
; otherwise if times is 0 return arg
; otherwise call recursively with parameters
;    f, times-1, and the result of (f arg)

(W14) Regular expressions

Using question W12's descriptions of what constitutes a valid integer and variable name, provide string-match calls to check if (i) a string represents a valid integer, (ii) a valid variable name.