PL Concepts, C++, FP, Scheme 1. True/False: Racket is a dialect of Scheme, which is a minimal LISP-family language. 2. True/False: Functional programming is mainly about ensuring correctness and functionality through assertions and contract checks. 3. True/False: The substitution model for procedure application is a way of modeling function invocation using a textual-reduction semantics. 4. True/False: Applicative-order evaluation is also called normal-order evaluation. 5. True/False: A first-class function is a function that may be treated as a value. 6. True/False: The function car is called an accessor. 7. True/False: Dynamic lookup (also called dynamic dispatch) applies to all method calls in both C++ and Java. 8. True/False: A box-and-pointer diagram is also called a cons diagram. 9. True/False: Any structure built from cons-cells in Scheme is a proper list. 10. True/False: The natural way to write a list-reversing function recursively is using direct or natural recursion, not tail recursion. 11. True/False: In the expression (if e0 e1 e2), only the expression e2 is in tail position. 12. True/False: In Racket, a let* form executes all right-hand-side expressions simultaneously. 13. Consider the arithmetic expressions below. For each: (a) draw its correct AST, (b) show the intermediate value of each inner-node, evaluating bottom-up, (c) write the same expression in Polish notation, (d) evaluate in Polish notation using stack-based evaluation as discussed in class (show each intermediate redex), and (e) write an equivalent Scheme expression. i. 2 23 3 (4 2 + 1) ii. 2232/222 14. Write an example in Racket where one variable shadows another. Write another example where one variable appears to shadow another, but does not. Explain why one is a case of shadowing but the other is not. 15. Design a C++ class for a cons cell with a constructor, standard accessors, and a method which returns a boolean to indicate if the cons cell is a proper list. Show how to encode (1 2 3) and check that its a proper list. 16. Draw a cons diagram for the value of expression: ((1 . 2) 3 4 . (((5)))) 17. Draw a cons diagram for the value of expression: ((1 . 2) . (3 (4) 5)) 18. Write an expression that uses constructor-calls to build all the cons cells in the quoted datum: ((1) 2 . (3 . 4)), but do not use literal datums except for numbers and null. 19. Write an expression that uses constructor-calls to build all the cons cells in the quoted datum: ((1 . 2) 3 4 . (((5)))), but do not use literal datums except for numbers and null. 20. Write two small classes with methods to implement the Visitor pattern, in C++. Explain with a diagram how dynamic dispatch works in this examplebe as precise as possible. Explain the relationship between the visitor pattern, and the idea of multiple dispatch. 21. Write a Fibonacci function in two ways: using tail recursion, and using direct/natural recursion. Explain the difference between these two approaches, including a complexity analysis of your implementations. 22. Write a Racket implementation of a sqrt function that uses fixed-point iteration to compute the square root either using the Babylonian method or using Newtons method. Use a first-class function in your implementation and point out its use in your implementation. Does this first-class function have any free variables? What role to these play, if it does?