DOC PREVIEW
UVA CS 415 - CS 415 Midterm Exam

This preview shows page 1-2-3-4 out of 11 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CS415 Anderson – Fall 2003 Page 1 of 11 CS 415 Midterm Exam – Fall 2003 Name __________________KEY______________________________ Email Address _________________ Student ID # ___________________ Pledge: This exam is closed note, closed book. Questions will be graded on quality of answer. Please supply the best answer you can to each question. Good Luck! Score Fortran & Algol 60 Compilation Names, Bindings, Scope Functional Programming Logic Programming Control Flow Total /72CS415 Anderson – Fall 2003 Page 2 of 11 Fortran and Algol 60 (11 points) 1. [1 point] Fortran uses pass by __reference_____ for parameters. 2. [1 point] Algol was designed by _a committee of 8, in Zurich in 1958 ______. 3. [5 points] List 3 significant differences between Fortran and Algol 60. (Many different answers possible here) 4. [4 points] Algol 60 introduced blocks of statements. List three reasons why these were useful in Algol 60. - programs easier to read (compared to gotos in Fortran) - supported structured programming - can use in place of a single statement - allows nested scopes - efficient storage management (allocate on entrance to a block and de-allocate on exit) - allows a fix to the dangling else problemCS415 Anderson – Fall 2003 Page 3 of 11 Compilation [15 points] 1. [5 points] List the phases a typical compiler uses in converting a program into assembly language. Indicate what is passed from one phase to the next. A full credit answer would have at least 5 phases. character stream -> Scanner (Lexical Analysis) -> token stream -> Parser (Syntax Analysis) -> parse tree (concrete syntax tree) -> Semantic Analysis & -> abstract syntax tree intermediate code generation or other intermediate form -> Machine-Independent Code -> modified intermediate form Improvement (optional) -> Target Code Generation -> assembly code or other target language -> Machine-Specific Code -> modified target language Improvement (optional) 2. [3 points] Why might a program written in a compiled language execute faster than one written in a language that is interpreted? Interpreted – must read and execute each statement as it is running, incurs overhead of analysis at run-time. Compiled – compiler does analysis at compile-time, so this overhead is not incurred at runtime. In addition, a compiler can afford to take more time to do optimizations and may have access to more information at compile time than can typically be done in an interpreter.CS415 Anderson – Fall 2003 Page 4 of 11 3. [2 points] Write a regular expression for an identifier in the cs415 language. Identifiers can consists of only letters (upper and lowercase) and digits, and must start with a capital letter and end with a digit. [A-Z] [A-Za-z0-9]* [0-9] 4. [2 points] Draw a finite automaton for the regular expression you gave in question 3 above. Be sure to properly denote the accepting states. 5. [3 points] Describe the dangling else problem. In the example below, it can be unclear which if stmt the else clause matches with. This can be solved in a number of ways, either by having an else should match the closest unmatched then, or by requiring explicit end markers to show the end of an IF statement. if cond then if cond then stuff else other stuff startA-Z0-9accept A-Za-z0-9CS415 Anderson – Fall 2003 Page 5 of 11 Names, Scopes, and Bindings (10 points) 1. [4 points] What does the function test print if the language uses static scoping? What does it print with dynamic scoping? (otherwise assume C++ syntax and semantics). int n = 100; // global print_plus_n(int x) { cout << x + n; } increment_n() { n = n + 1; } test() { int n; n = 1; print_plus_n(25); n = 33; print_plus_n(n); increment_n(); cout << n; print_plus_n(n); } With Static Scoping: 125 133 33 134 With Dynamic Scoping: 26 66 34 68CS415 Anderson – Fall 2003 Page 6 of 11 2. [4 points] Support the claim: “Early binding generally leads to greater efficiency.” First, define binding, and then give evidence why this might be true. binding – an association between two things, such as a name and the thing it names (examples: a variable bound to a location in memory, a function name bound to a specific piece of code) Reasons why early binding can lead to greater efficiency: - compilation generally binds things earlier than interpretation. This can allow the compiler to do more optimization at compile time, or to avoid some indirection at run-time. - binding variables to memory locations early can avoid indirection at run-time (we can use a particular address rather than an indirect access). - binding variables to types ahead of time can eliminate some run-time type checking or can bind function addresses to call sites (rather than needing to consult a vtable at run-time to determine which function to call as in dynamic dispatch of functions). 3. [2 points] What does reference counting refer to? Give one problem with this approach. As discussed in class, this is an approach to garbage collection that keeps track of the number of references to an object. When the count goes to zero, then the object can be reclaimed. One problem with this approach is that it does not work on circularly linked structures (like a circularly-linked list) as each node will always be pointed to even if the structure is unreachable from the program.CS415 Anderson – Fall 2003 Page 7 of 11 Functional programming (14 points) 1. [5 points] At several schools (MIT, Berkley, Rice) Scheme is the programming language used in introductory programming courses. Give at least 3 reasons why Scheme could be argued to be well-suited for this purpose? A few reasons: - garbage collection (don’t need to worry about memory management) - simple syntax makes it easy to learn - if used in a purely functional style, no side effects will be used, this tends to avoid bugs related to un-expected side effects and makes it easier to reason about programs - good environments/interpreters are available free of charge (Dr. Scheme) - benefits of using an interpreter – fast response (don’t have to wait to recompile the whole program each time you change something, makes it easy to experiment), good error messages - closely related to math functions – draws on students’ math


View Full Document

UVA CS 415 - CS 415 Midterm Exam

Download CS 415 Midterm Exam
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view CS 415 Midterm Exam and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view CS 415 Midterm Exam 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?