Chapter 15

Concept of Programming Languages by Robert W. Sebesta Answer

Review Questions

1. Define functional form, simple list, bound variable and referential transparency.

Functional form : one that either takes one or more functions as parameters or yields a function as its result. 

Simple list : A list that does not include sublist.
Bound variable : A bound variable is a variable which never changes in the expression after being bound to an actual parameter value at the time evaluation of the lambda expressions begin. 

Referential transparency : A state where execution of function always produces the same result when given the same parameters.

2. What does a lambda expression specify ?

parameters and the mapping of a function.

3. What data types were parts of the original LISP ?

atoms and lists

4. In what common data structure are LISP lists normally stored ?

As linked list structure in which each node has two pointers.

5. Explain why QUOTE is needed for a parameter that is a data list.

To return lists or atoms without changing them.

6. What is a simple list ?

A list that does not include a sublist.

7. What does the abbreviation REPL stand for ?

Infinite Read-Evaluate-Print Loop

8. What are the three parameters to IF ?

a predicate expression, a then expression, and else expression.

11. What are two forms of DEFINE ?

Binds a name to value of an expression, and bind lambda expression to a name.

29. What is a curried function ?

All functions that takes multiple parameters.

30. What does partial evaluation mean ?

The function is evaluated with actual parameters for one or more of the leftmost formal parameters.

Problem Set

4. Refer to a book on Haskell programming and discuss the feature of Haskell.

Haskell has a strong, static type system based on Hindley–Milner type inference. Haskell’s principal innovation in this area is to add type classes, which were originally conceived as a principled way to add overloading to the language, but have since found many more uses. 

Haskell features lazy evaluation, pattern matching, list comprehension, type classes, and type polymorphism. It is a purely functional language, which means that in general, functions in Haskell do not have side effects. There is a distinct construct for representing side effects, orthogonal to the type of functions. A pure function may return a side effect which is subsequently executed, modeling the impure functions of other languages.

9. What does the following Scheme function do ?
(define (y s list)
(cond
((null? Lis) ‘ () )
((equal? S (car lis)) lis)
(else (y s (cdr lis)))
))

y returns the given list with leading elements removed up to but not including the first occurrence of the first given parameter.

10. What does the following Scheme functions do ?
(define (x lis)
(cond
((null ? lis) 0)
((not (list? (car lis)))
(cond
((eq? (car lis) #) (x (cdr lis)))
(else (+ 1 (x (cdr lis))))))
(else (+ (x (car lis)) (x (cdr lis))))

x returns the number of non-NIL atoms in the given list.