Ics 313 Programming Language Theory

Front 1

Explain why in-line subroutines are particularly important in object-oriented languages.

Back 1

To avoid direct access to data members, O-O languages often add simple accessor methods. These are inefficient because they require function call overhead (creating a stack frame, jumps to the subroutine code and back, etc.). In-line subroutines allow the function call overhead to be avoided

Front 2

Explain the distinctions among private, protected, and public base classes in C++.

Back 2

Public base class means users of the derived class will see all of the public methods/data of the base class. Private means users of the derived class will not see the public methods/data unless explicitly exported by the derived class. Protected makes public methods/data of the base class act like protected members of the derived class.

Front 3

What is escape analysis?

Back 3

The compiler in a language like Java can analyze the code to determine that references to a given object will always be contained within a method, in which case the object can be allocated in the method’s stack frame instead of the heap for better efficiency.

Front 4

Summarize the fundamental argument for dynamic method binding. Why do C++ and C# use static-method binding by default?

Back 4

Dynamic method binding allows the most specific method for the object type to be called rather than the method for a super class of the object even when the type of the variable pointing to the object is of the super class. This is computationally more expensive because run-time dispatching is needed, so C++ and C# avoid this for efficiency.

Front 5

What is an abstract method? (also called a pure virtual method in C++ and a deferred feature in Eiffel)

Back 5

An abstract method is one that does not have actual code in the superclass and only code is provided for derived classes.

Front 6

What does it mean for a language to be strongly typed? Statically typed? What prevents, say, C frombeing strongly typed?

Back 6

A strongly typed language prohibits the application of any operation to any object that is not intended to support that operation. A statically typed language is a strongly typed language that checks everything at compile time. Variant records (union records in C) prevents C from being strongly typed, because there is no way to check which of the variants is actually stored in the variant record.

Front 7

Explain the differences among type conversion, type coercion, and non-converting type casts.

Back 7

A type conversion (aka type cast) is an explicit programmer call to change a value/variable of one type to another, which may or may not require run-time conversion code. Type coercion is implicit type conversion. Non-converting type casts are changes of type that do not alter the underlying bits.

Front 8

Discuss the significance of “holes” in records. Why do they arise? What problems do they cause?

Back 8

Holes in records arise because some data types must be aligned on word boundaries and do not fill the entire word. They cause problems in wasted space and in comparing records: either the holes must be initialized to a common value like all 0’s to use a block comparison or each field of the records must be compared separately, skipping the arbitrary values in the holes.

Front 9

Discuss the comparative advantages of contiguous and row-pointer layout for arrays.

Back 9

Contiguous is typically more space efficient, but may be slower on machines with slow multiplies,and may be less space efficient when rows have different lengths (aka ragged array; e.g., an array of different length strings). A row-pointer layout allows easy construction of new arrays from pre-existing rows from possibly multiple arrays without copying data.

Front 10

What are dangling references? How are they created, and why are they a problem?

Back 10

Dangling references occur when a pointer remains, but the object pointed to has disappeared. This can happen when the object is allocated on the stack and its lifetime is over (e.g., exiting from the subroutine call that allocated the object). Following the pointer will access unknown data and putting new values in the object will corrupt the new data that is now at the object’s old memory location.

Front 11

What is globbing? What is a wildcard?

Back 11

Globbing is file name expansion. A wildcard is a special character, typically *, that expands into any file name not including periods. A * matches any number of characters. Typically ? is commonly included to match any single character.

Front 12

List several distinctive features of Python.

Back 12

Indentation is used for blocking. Python includes an re (regular expression) library, nested functions with static scoping, lambda expressions and higher-order functions, true iterators, list comprehensions, array slice operations, reflection, structured expression handling, multiple inheritance, and modules and dynamic loading.

Front 13

Why might we prefer to execute a web script on the server rather than the client? Why might we sometimes prefer the client instead?

Back 13

Executing the script on the server allows complete control and protection of proprietary information.Client execution allows more efficient/responsive operation for interactive animations and UI functions.

Front 14

Describe the notion of capture in regular expressions.

Back 14

Any part of the regular expression enclosed in parentheses is copied into variables that can be used later in the regular expression or later in the program.

Front 15

What are associative arrays? By what other names are they sometimes known?

Back 15

Associative arrays, aka mappings, dictionaries, or hashes, are composite types where the index to the array can be any type such as a string.

Front 16

Describe how to maintain the static chain during a subroutine call.

Back 16

If the callee is nested directly in the caller, the callee’s static link refers to the caller’s frame. If the callee is k scopes outward from the caller, de-reference the caller’s static link k times and passes that for the callee’s static link.

Front 17

Describe four common parameter-passing modes. How does a programmer choose which one to use when?

Back 17

Call-by-value copies the value of the actual parameters into the formal parameters and is best used when the actual parameters should not be changed by the subroutine and when the actual parameters are small in space (to avoid copying too much). Call-by-reference passes the address and is best used when the formal parameters should be changed by the subroutine or when very large. Call-by value/result copies the actual parameter value into the formal parameter and copies the value back at the end. Call-by-sharing is the same as call-by-value for languages with a reference model for variables. Call-by-value/result and call-by-sharing do not usually have alternatives, so there is no need to choose which to use when. Call-by-name copies the lexical entry for the actual parameter for every occurrence of the formal parameter much like a macro. It is useful when an actual parameter is an expression than needs to be re-evaluated every time. (I listed 5, you only have to list 4.)

Front 18

What is the principal purpose of generics? In what sense do generics serve a broader purpose in C++ and Ada than they do in Java and C#?

Back 18

Generics allow the same code to work on many different types of parameters. Ada and C++ generics allow subroutines and classes as well as types for generic parameters.

Front 19

Explain why it is useful to implement exceptions as classes in C++, Java, and C#.

Back 19

The exception can have data fields that contain important information about what went wrong and a superclass of exception can capture its subclasses without having to list all possible subclasses.

Front 20

What is an event in the programming language sense of the word?

Back 20

An event is something to which a running program needs to respond, but which occurs outside the program at an unpredictable time.

Front 21

What is a race condition? What is synchronization?

Back 21

A race condition is when two or more threads will touch an object and the behavior of the overall system depends on which thread gets there first. Synchronization explicitly controls the ways that the actions of threads can interweave in time.

Front 22

What is busy-waiting? What is its principal alternative?

Back 22

Busy-waiting (aka spinning) is when a thread enters a loop checking for the status of some lockvariable. The principal alternative is blocking, where the thread puts itself on an operating system queue and gives up control until of its processor until the operating system wakes it up again.

Front 23

Describe the behavior of the compare_and_swap instruction. What advantage does it offer in comparison to test_and_set?

Back 23

Compare_and_swap compares the current value of a shared variable with a given value and if they are the same, replaces the value of the variable with a new given value. It allows non-blocking-concurrency (every thread is guaranteed to be able to make progress regardless of what other threads are doing), which cannot be implemented with test_and_set.

Front 24

What is a semaphore? What operations does it support? How do binary and general semaphores differ?

Back 24

A semaphore is a counter with two associated operations, P (atomic decrement) and V (atomic increment and wake up a waiting thread, if any). A binary semaphore is initialized to 1 whereas a general semaphore is initialized to k copies of some resource.

Front 25

What is a monitor? How do monitor condition variables differ from those of semaphores?

Back 25

A monitor is a module with operations, internal state and a number of condition variables. These condition variables differ from those of semaphores in that they have no memory: if no thread is waiting on a condition at the time of a signal, it does not wake up a future thread that waits on the condition (the future thread is responsible for checking before blocking).