COMP 524 Midterm Tue Oct 15 2019 12 30 1 45pm Instructions 1 Please spread out and try and sit in alternate seats 2 This is a closed book exam 3 Write in the space provided Write on the opposite side of a question page if there is not enough space to solve a problem Use the overflow pages only if necessary 4 There are 8 numbered pages including this one 3 questions 5 The exam should be printed double sided in case it is not please do not write on the blank 6 unnumbered pages If you need to make any assumptions to clarify a problem write your assumptions down Only reasonable assumptions get full credit 7 You will get partial credit so write down part of the solution even if you cannot develop the complete solution 8 You will not be penalized for errors in syntax as long as your algorithm is understandable 9 You are not required to comment or annotate any code you write but may get partial credit if you write appropriate comments annotations but incorrect code 10 If you cannot remember the name of a predefined language operation or type invent it and identify what it does 11 Your solutions may be graded not only for correctness but also for style and efficiency 12 Please inform the proctor of anything in the exam that you think is a mistake 13 Walk over to the proctor to ask questions so that you do not disturb others 14 If you do not understand some English word do not hesitate to ask the proctor Naturally you are expected to know the computer science terms defined in class 15 Write clearly using a pen pencil with a dark color we will be scanning your exams 16 Do not unstaple the exam Unstapled exams may not be graded NAME ONYEN ALL LARGE LEGIBLE CAPITALS YOUR EXAM MAY NOT BE GRADED OTHERWISE CAP NAME CAP ONYEN Pledge I have neither given nor received unauthorized aid on this exam For survey purposes please indicate the time at which you turned in the exam signed Please do not write below 1 20 2 25 3 30 Total 75 1 1 20 PTS LANGUAGE COMPARISON a What is the difference between a procedural and declarative language You do not have to give pros and cons of these two kinds of languages b Give an example of a procedural and declarative language Procedural Declarative c Name one language construct some component of the language syntax grammar in Java whose equivalent does not exist in the C you have learned in 411 and this course that was used by you to extend the provided Lisp Interpreter A construct is part of the language it is not provided by a library or design pattern based on the language d Identify one example of a Lisp feature you added using this Java construct and how the construct was used to add the feature You do not need to give the algorithm for implementing the Lisp feature only how the implementation used the Java construct 2 2 25 PTS LISP S EXPRESSIONS AND RECURSION Consider a Lisp function numAtoms that takes as an argument an S Expression S and returns the number of atoms leaves in the tree rooted by S Examples numAtoms Nil 1 numAtoms cons 5 cons 2 Nil 3 a What would the following calls to this function return numAtoms cdr cons 5 cons 2 Nil numAtoms list 5 list 2 Nil Nil b Give a recursive implementation of numAtoms You should use the version of Lisp taught in class which is the version implemented in A1 A2 augmented with defun and direct function calls without funcall You can of course use setq and funcall if you are more comfortable with them 3 3 30 PTS TRACING EXECUTION OF LISP INTERPRETER In this question you will trace the completion of the execution of some of the Java operations of the Comp 524 Lisp Interpreter augmented with the features you were required to implement in A1 and A2 when it processes two input expressions For each input s expression you should begin tracing after its textual representation has been converted into an input s expression object which is what we did in lectures Here is what you should trace for each input s expression 1 The s expression eval method and the environment lookup and assign methods 2 The toString method invoked on the output s expression to display the result of processing the input s expression You do not have to trace the execution of getValue getHead and getTail methods The following table illustrates the four kind of operations to be traced Each row describes an operation executed after the ones represented in the earlier rows It identifies the object on which it is invoked and the arguments and result of the operation if applicable An s expression is described by its type Composite Identifier Integer String and its textual representation The initial global environment is named Globals Dynamically created children of it are named by variables assigned to the result of executing new newChild on a previously identified environment You can use this in the arguments or result column to refer to the object on which the operation is invoked The table below shows unrelated example traces Your trace table should trace the operations in the sequence in which they are completed Operation Object toString Integer 5 eval Composite cons 5 6 assign Globals lookup Globals Env1 Globals newChild assign Env1 lookup Here is the Lisp code you should trace setq A quote quote eval list A quote A Result 5 Composite 5 6 N A Composite 5 N A Composite 5 Argument 2 N A N A Composite 5 6 N A Composite 5 6 N A Argument 1 N A Globals Identifier X Identifier Y Identifier X Identifier Y 4 Operation Argument 1 Argument 2 Result Object 5 EXTRA SPACE FOR Q3 you should not need it but just in case you mess up the previous page Object Operation Argument 1 Argument 2 Result 6 EXTRA SPACE AS SOME ARE NOT CONCISE Killing Trees Sigh Please try and fit your answer in the assigned space 7 EXTRA SPACE AS SOME ARE NOT CONCISE Killing Trees Sigh Please try and fit your answer in the assigned space 8