CHapter 9: Subprograms

Review Questions

1. What are the three general characteristics of subprograms?
    - Each subprogram has a single entry point.
    - The calling program unit is suspended during the execution of the called subprogram, which implies that there is only subprogram in execution at any given time.
    - Control always returns to the caller when the subprogram execution terminates.

2. What does it mean for a subprogram to be active?
    It means that after having been called, a subprogram has begun execution but has not yet completed that execution.

3. What is given in the header of a subprogram.
    Subprogram header, which is the first part of the definition, serves several purposes. First, it specifies that the following syntactic unit is a subprogram definition of some particular kind.1 In languages that have more than one kind of subprogram, the kind of the subprogram is usually specified with a special word. Second, if the subprogram is not anonymous, the header provides a name for the subprogram. Third, it may optionally specify a list of parameters.

 4. What characteristic of Python subprograms sets them apart from those of other languages?
    One characteristic of Python functions that sets them apart from the functions of other common programming languages is that function def statements are executable. When a def statement is executed, it assigns the given name to the given function body. Until a function’s def has been executed, the function cannot be called.

Consider the following skeletal example:if . . .
def fun(. . .):
. . .
else
def fun(. . .):
. . .

5. What languages allow a variable number of parameters ?

    C,C++,Perl JavaScript, and Lua. Also, C# allows methods to accept a variable number of parameters, as long as they are of the same type.

Problem Set

1. What are arguments for and against a user program building additional definitions for existing operators, as can be done in Python and C++? Do you think such user-defined operator overloading is good or bad? Support your answer.

    FOR:

    It allows the developer to program using notation “closer to the target domain” and allows user-defined types a similar level of syntactic support as types built into the language. It can easily be emulated using function calls.

    AGAINST:

    It can be implemented according to user’s want, eventhough it is not logically true.

I think such user-defined operator overloading is good as long as user use it according to its logical rules. User must use for example, + operator to be overloaded to implement “add” not “substraction”. And sometimes, in C++ there is condition when user need to add many data in class, so user-defined operator like this is needed to make it easier.

2. . In most Fortran IV implementations, parameters were passed by reference, using access path transmission only. State both the advantages and disadvantages of this design choice.

    The main advantage of this method is the fast accesses to formal parameters in subprograms. The disadvantages are that recursion is rarely useful when values cannot be passed, and also that a number of problems, such as aliasing, occur with the method.

3. . Argue in support of the Ada 83 designers’ decision to allow the implementor to choose between implementing in out mode parameters by copy or by reference.

    The tradeoff is one of efficiency of passing parameters vs. efficiency of accessing the parameters in the subprogram. Ada leaves this choice to the implementor, rather than forcing a single solution, because different situations may require different approaches. Passing a large array which the subprogram only accesses a few times is faster with reference. Passing any argument that the subprogram accesses a lot is faster with copy.

4. Suppose you want to write a method that prints a heading on a new output page, along with a page number that is 1 in the first activation and that increases by 1 with each subsequent activation. Can this be done without parameters and without reference to nonlocal variables in Java? Can it be done in C#?

    This can be done in both Java and C#, using a static (or class) data member for the page number.

5. Consider the following program written in C syntax:

void swap(int a, int b) {
int temp;
temp = a;
a = b;
b = temp;
}

void main() {
int value = 2, list[5] = {1, 3, 5, 7, 9};
swap(value, list[0]);
swap(list[0], list[1]);
swap(value, list[value]);
}

For each of the following parameter-passing methods, what are all of the values of the variables value and list after each of the three calls to swap?
a. Passed by value
b. Passed by reference
c. Passed by value-result

 a. Passed by value

-value =1 , list[5] = {2,4,6,8,10}
b. Passed by reference
-value =6, list[5] ={4,1,2,8,10}
c. Passed by value-result
-value =6, list[5] ={4,1,2,8,10}

Chapter 8: Statement-Level Control Structures

Review Questions: 
1. What is the definition of control structure?
    A control structure is a control statement and the collection of statements whose execution it controls.

2. What did Bohm and Jocopini prove about flowcharts?
     It was proven that all algorithms that can be expressed by flowcharts can be coded in a programming languages with only two control statements: one for choosing between two control flow paths and one for logically controlled iterations.

3. What is the definition of block?
     In Ruby, block is a sequence of code, delimited by either breves or the do and and reserved words.

4. What is/are the design issue(s) for all selection and iteration control statements?
    Selection

    Two-way :

• What is the form and type of the expression that controls the selection ?
• How are the then and else clauses specified ?
• How should the meaning of nested selectors be specified ?

    Multiple-Selection :

• On which type the selector is based ?

    Iteration :

• How is the iteration controlled ?
• Where should the control mechanism appear in loop statement?

5.  What are the design issues for selection structures?    

• What is the form and type of the expression that controls the selection ?
• How are the then and else clauses specified ?
• How should the meaning of nested selectors be specified ?

Problem Set

1. Describe three situation where a combined counting and logical looping statement is needed.

    A list of values is to be added to a SUM, but the loop is to be exited if SUM exceeds some prescribed value.

A list of values is to be read into an array, where the reading is to terminate when either a prescribed number of values have been read or some special value is found in the list.

The values stored in a linked list are to be moved to an array, where values are to be moved until the end of the linked list is found or the array is filled, whichever comes first.

2. Study the iterator feature of CLU in Liskov et al. (1981) and determine its advantages and disadvantages

    The key addition was the concept of a cluster, CLU’s type extension system and the root of the language’s name CLUster. Clusters correspond generally to the concept of an “object” in an OO language, and have roughly the same syntax.

CLU did not offer any sort of structure for the clusters themselves. Cluster names are global, and no namespace mechanism was provided to group clusters or allow them to be created “locally” inside other clusters. This problem is not unique to CLU, but it is surprising that so many languages have lacked this feature — given the centralness in ALGOL of giving scope to variables, it seems that giving scope to cluster/object names would be an obvious extension.

CLU does not perform implicit type conversions. In a cluster, the explicit type conversions ‘up’ and ‘down’ change between the abstract type and the representation. There is a universal type ‘any’, and a procedure force[] to check that an object is a certain type.

Another key feature of the CLU type system are iterators, which return objects from a collection one after the other. Iterators were “black boxes” that offered an identical API no matter what data they were being used with. Thus the iterator for a collection of complex_numbers would be identical to that for an array of integers.

CLU also includes exception handling, based on various attempts in other languages; exceptions are raised using signal and handled with except. Oddly, given the focus on type design, CLU does not offer enumerated types, nor any obvious way to create them.

A final distinctive feature in CLU is multiple assignment, where more than one variable can appear on the left hand side of an assignment operator

3. Compare the set of Ada control statements with those of C# and decide which are better and why.

    C# because the C# multiple selection structures is a great boost to C# writability, with no obvious negatives, furthermore C# control statement is the most flexible iteration statement.

4. What are the pros and cons of using unique closing reserved words on compound statements?

    Unique closing keywords on compound statements have the advantage of readability and the disadvantage of complicating the language by increasing the number of keywords.

5. What are the arguments, pro and con, for Python’s use of indentation to specify compound statements in control statements?

    Pros of indentation:

• Helps reduce inconsistent indentation in code which makes it easier to read (in other words consistency)
• clears the screen by replace visible tokens with whitespace to serve the same purpose

    Cons of indentation

• Much easier to cut and paste code to different levels (you don’t have to fix the indentation)
• More consistent. Some text editors display whitespace(s) differently.
• You cannot safely mix tabs and spaces in Python such that it would be easy to cause an error by putting too few spaces in an indentation level, thus going to the previous indentation level and closing the loop/block. This decreases writability.

Chapter 7: Expressions and Assignment Statements

Review Question: 
1. Define operator precedence and operator associativity.
    - Operator precedence: defines order and priority of the operator evaluation from different precedence levels.

    - Operator associativity: defines the order of operators evaluation when it is from the same precedence level.

2.  What is a ternary operator?

    Ternary operator is an operator with three operands.

3. What is a prefix operator?

     Prefix operator is a operator that precede their operands.

4. What operator usually has right associativity?

    Operator that usually has right associativity are operator which can be found in Fortran and Ruby.

5. What is a nonassociative operator?
   Nonassociative operator means that the expression is illegal.

Problem Set: 
1. When might you want the compiler to ignore type differences in an expression?
    When I want to evaluate a string as a number.

2.  State your own arguments for and against allowing mixed-mode arithmetic expressions.
   - For: A mixed mode arithmetic expression is needed in calculating expressions that might have decimal results. It is compulsory as it allows two different type of number data type such as float and integer to be summed without losing the precision of the float.
   - Against: While it is compulsory to have mixed-mode expressions, it is more error prone when expressions made are more likely to have non-decimal results. A mixed mode might produce a decimal result even though the result wanted is a non-decimal.

3. Do you think the elimination of overloaded operators in your favourite language would be beneficial? , why or why not?
    No, it would not be beneficial. Overloading operator would be a helpful feature in developing a complex program with complex arithmetic operation as well. It allows developers to create a class whose function can replace countless lines of codes with an operator. This clearly will help a readability and writability of a program. Eliminating overloaded operators would null this advantage.

4. Would it be a good idea to eliminate all operator precedence rules and require parentheses to show the desired precedence in expressions? Why or why not?
    No. Because it will affect the readability and writability, and maybe it can make the answer ambiguous.

5.  Should C’s assigning operations (for example, +=) be included in other languages (that do not already have them)? Why or why not?
    No. assigning operations of C should not be included in other languages. Because the assigning operations would be the different part of the code if it is implemented on other code that might cause confusion for the programmer.

Chapter 6: Data Types

Sorry for the late post, in this post I will answer the review questions and problem sets from Sebesta's Programming Language Concept.

Review Questions: 
1. What is a descriptor?
    Descriptor is collection of the attributes of a variable.

2. What are the advantages and disadvantages of decimal data types?
    The advantages of decimal data types is being able to precisely store decimal values, at least those within a restricted range, which can’t be done with floating-point. And the disadvantages of decimal data types are that the range of values is restricted because no exponents are allowed, and their representation in memory is mildly wasteful.

3. What are the design issues for character string types?
The two most important design issues that are specific to character string types are should strings be simply a special kind of character array or a primitive type and should strings have static or dynamic length.

4. Describe the three string length options.
Static length: the length can be static and set once the string is created.
Limited dynamic length : allow strings to have varying length up to a declared and fixed maximum set by the variable’s definition.
Dynamic length: allow strings to have varying length with no maximum.

5. Define ordinal, enumeration, and subrange types.
    1) Ordinal type is one in which the range of possible values can be easily associated with the set of positive integers. In Java, for example, the primitive ordinal types are integer, char, and Boolean.

    2) Enumeration is one in which all of the possible values, which are named constants, are provided, or enumerated, in the definition. Enumeration types provide a way of defining and grouping collections of named constants.

    3) Subrange is a contiguous subsequence of an ordinal type. For example, 12..14 is a subrange of integer type.

Problem Set

1. What are the arguments for and against representing Boolean values as single bits in memory?

    A Boolean value could be represented by a single bit. But, a single bit of memory cannot be accessed efficiently on many machines, so they are often stored in smallest efficiently addressable cell of memory, typically a byte.

2. How does a decimal value waste memory space?

    Decimal types are stored very much like character strings, using binary codes for decimal digits. These representations are called binary coded decimal (BCD). In some cases, they are stored one digit per byte, or two digits per byte. Either way, they take more storage than binary representations. It takes at least four bits to code a decimal digit. Therefore, to store a six-digit coded decimal number requires 24 bits of memory. However, it takes only 20 bits to store the same number in binary.

3.  VAX minicomputers use a format for floating-point numbers that is not the same as the IEEE standard. What is this format, and why was it chosen by the designers of the VAX computers? A reference for VAX floating –point representations is Sebesta (1991).
    The existing DEC VAX formats, inherited from the PDP-11, because the PDP-11 had several uniquely innovative features, and was easier to program than its predecessors through the additional general-purpose registers.

4. Compare the tombstone and lock-and –key methods of avoiding dangling pointers, from the points of view of safety and implementation cost.
    Tombstones take more memory, while lock-and-key requires additional cpu time on each pointer assignment to copy key as well as pointer. Pointer arithmetic could overwrite key in the heap.

5. What disadvantages are there in implicit dereferencing of pointers, but only in certain contexts? For example, consider the implicit dereference of a pointer to a record in Ada when it is used to reference a record field.
    When implicit dereferencing of pointers occurs only in certain contexts, it makes the language slightly less orthogonal. The context of the reference to the pointer determines its meaning. This detracts from the readability of the language and makes it slightly more difficult to learn. 

Chapter 5: Names, Bindings, and Scopes

Review Questions:
1. What are the design issues for names?
   There are 2 primary design issues for names: first we have "are names case sensitive?", and second one is "are the special words of the language  reserved words or keywords?".

2. What is the potential danger of case-sensitive names?
   Writ ability and readability (because sometimes names that look alike are different thing).

3. In what way are reserved words better than keywords?
   Reserved words can be better than keywords because the ability to redefine keywords are confusing.

4. What is an alias?
   When more than one variable can be used to access the same memory location the variables are called alias.

5.  Which category of C++ reference variables is alwas aliases?
   Union types.

 Problem Set:
1. Which of the following identifier forms is most readable? Support your decision.

• SumOfSales
• sum_of_sales
• SUMOFSALES

   The most readable identifier is "sum_of_sales", because there are underscores as separator of the words in that variable.

2. Some programming languages are typeless. What are the obvious advantages and disadvantage of having no types in language?

   Advantages    : - It allows coders to write sloppy programs quickly.

   Disadvantages: - You are not in control of the data and variables, the compiler or interpreter is.

                            -  If you miss assigned variables, there's no way for the compiler to catch any of                                      your mistakes. It just "does what you said" even if it's wrong.

                            - Supporting programs in a typeless language is much more difficult. It often                                            couldn't recognize what the programmer actually want to do.

3. Write a simple assignment statement with one arithmetic operator in some language you know. For each component of the statement, list the various bindings that are required to determine the  semantics when the statement is executed. For each binding, indicate the binding time used for the language.

   int count; count = count + 5;

Possible types for count: set as language design time. 

Type of count: bound at compile time.

Set of possible values of count: bound at compiler design time. 

Value of count: bound at execution time with this statement.

Set of possible meanings for the operator symbol '''' in this statement: bound at compile time.

Internal repesentation of literal "5": bound at compiler design time.

4. Dynamic type binding is closely related to implicit heap-dynamic variables. Explain this relationship.

   Both are related to the assignment and the statement.

5. Describe a situation when a history-sensitive variable in subprogram is useful.

   It is useful when you have a subprogram to be recalled again after the subprogram itself had been exited. Then the function doesn't have the variable to be the parameter, but only to return it. 

Chapter 4: Lexical and Syntax Analysis

This is the post for this week's GSLC assignment. It's about Sebesta's Programming Language Concept, chapter 4 Review Question and Problem Set.

Review Question:
1. What are three reasons why syntax analyzers are based on grammars?

• Grammars are clear and concise. 
• The grammar description can be use as a direct basis for the analyzer.
• Grammar are modular or easy to maintain.

2. Explain the three reasons why lexical analysis is separated from syntax analysis.

• Simplicity:  Techniques for lexical analysis are less complex than those required for syntax analysis.
• Efficiency: altough it pays to optimize the lexical analyzer, because lexical analysis requires a significant portion of total compilation time.
• Portability: because the lexical analyzer reads input program files and often includes buffering of that input, it is somewhat platform dependent.

3. Define lexeme and token.

    Lexeme is the logical groupings that the loxical analyzer collects characters into, and token is the internal codes for categories of these groupings.

4. What are the primary task of lexical analyzer?

   A lexical analyzer has to perform syntax analysis at the lowest level of program structure.

5. Describe  briefly the three approaches to building a lexical analyzer.

• Write a formal description of the token patterns of the language using a descriptive language related to regular expression.
• Design a state transition diagram that describes the token patterns of the language and write a program that implements the diagram
• Design a state transition diagram that describes the token patterns of the language and hand-construct a table-driven implementation of the state diagram.

Problem Set:

1. Perform the pairwise disjointness test for the following grammar rules.
a. A → aB | b | cBB
   FIRST(aB) = {a}, FIRST(b) = {b}, FIRST(cBB) = {c}, passes the test.
b. B → aB | bA | aBb
   FIRST(aB) = {a}, FIRST(bA) = {b}, FIRST(aBb) = {a}, failed the test
c. C→ aaA | b | caB
   FIRST(aaA) = {a}, FIRST (b) = {b}, FIRST (caB) = {c}, passes the test
   
2. Perform the pairwise disjointness test for the following grammar rules.
a. S→ aSb | bAA
   FIRST(aSb) = {a}, FIRST(bAA) = {b}, passes the test
b. A → b{aB} | a
   FIRST (b{aB}) = {b}, FIRST (a) = {a}, passes the test
c. B → aB | a
   FIRST(aB) = {a}, FIRST(a) = {a}, failed the test

3. Show a trace of the recursive descent parser given in Section 4.4.1 for the string a + b * c.
   Call lex /* returns a */
   Enter <expr> Enter <term> Enter <factor>   Call lex /* returns + */   Exit <factor> Exit <term>   Call lex /* returns b */   Enter <term> Enter <factor>   Call lex /* returns * */   Exit <factor>   Call lex /* returns c */   Enter <factor>   Call lex /* returns end-of-input */   Exit <factor> Exit <term> Exit <expr>

4. Show a trace of the recursive descent parser given in Section 4.4.1 for the string a * (b + c).
   call lex      // return a
    enter <expr>    enter <term>    enter <factor>   call lex      // return *     exit <factor>   call lex      // return (     enter <factor>   call lex      // return b     enter <expr>     enter <term>     enter <factor>   call lex      // return +     exit <factor>     exit <term>   call lex      // return c     enter <term>     enter <factor>   call lex      // return )     exit <factor>     exit <term>
     exit <expr>   call lex      // return EOF     exit <factor>     exit <term>
     exit <expr>

5. Given the following grammar and the right sentential form, draw a parse tree and show the phrases and simple phrases, as well as the handle.

S → aAb | bBA A → ab | aAB B → aB | b

a. aaAbb

   Parse Tree:

                                   S

                                /   |   \

                             a     A   b

                                 /   |   \

                               a    A   B

                                            |

                                           b

   Phrases: aaAbb, aAb, b

   Simple phrase: b, aAb

   Handle: b

b. bBab

   Parse Tree:

                                    S

                                /    |    \

                             b      B   A

                                         /   \

                                        a    b

   Phrases: bBab, bBA

   Simple phrase: ab

   Handle : ab

c. aaAbBb

   aaAbBb = aSBb = aSBB = x

   The last string cannot be derived from the given grammar. 

Chapter 3: Describing Syntax and Semantics

This time I will post the answer of first 5 numbers of Review Questions and first 5 numbers of Problem Set.

Review Questions:
1. Define syntax and semantics.
   Syntax is more to the structure, form of the programming language; while semantics are more into the meaning of the code.

2. Who are language descriptions for?
   Language descriptions are for initial evaluators, implementors, and users.

3. Describe the operation of a general language generator.
   A general language generator is a device that can be used to generate the sentences of the language. It generates unpredictable sentences which makes a generator seems to be a device of limited usefulness as language descriptor. It is often possible to determine whether the syntax of a particular statement is correct by comparing it with the structure of the generator.

4. Describe the operation of a general language recognizer.
   A general language recognizer is a recognition device capable of reading strings of characters from the alphabet. It would analyze the given string and it would either accept or reject the string based from the language given. These recognition devices are like filters separating correct sentences from those that are incorrectly. A recognizer is used in the syntax analysis part of the compiler. In this role, the recognizer need not test all possible strings of characters from some set to determine whether each is in the language. The syntax analyzer just determines whether the given programs are syntactically correct.
   
5. What is the difference between a sentence and a sentential form?
   A sentence is a sentenential form that has only terminal symbols. A sentence form is every strings of the symbols in the derivation.

Problem Set:
1. The two mathematical models of language description are generation and recognition. Describe how each can define the syntax of a programming language.
   Syntax error refers to an error in the program that caused by misused syntax. Semantics error is caused by wrong logical statements.

2. Write EBNF descriptions for the following:
a. A Java class definition header statement
   <class_head> ® {<modifier>} class <id> [extends class_name]
    [implements <interface_name> {, <interface_name>}]
    <modifier> ® public | abstract | final
b. A Java method call statement
   <for> -> for '(' [[<type>] <id> = <expr> {,[<type>] <id> = <expr>}] ; [<expr>] ; [<expr>{, <expr>}] ')' '{' <stmt_list> '}
c. A C switch statement   
   <stmt> -> switch (<int expr>){case <int const> : {<stmt>;} 
    { case<int const> : {<stmt> :}}
    [default : {<stmt>;}]    }
d. A C union definition
   <union_defn> -> union <var_list> <union_identifier>;
    <var_list> -> <list_of_data-type specifier> <var>    <list_of_data-type specifier> -> int | float | long | char | double    <union_identifier> -> <var>
e. C float literals
   <float-literal> -> <real> <suffix>
    | <real> <exponent> <suffix>    | <integer> <exponent> <suffix>

3. Rewrite the BNF of Example 3.4 to give + precedence over * and force + to be right associative.
    <assign>-> <id> = <expr>
    <id> = A|B|C
   <expr>-> <expr>-<term> |<term>
   <term> -> <term>/<factor>|<factor>  
   <factor> ->(<expr>) |<id>
 
4. Rewrite the BNF of Example 3.4 to add the ++ and -- unary operators of Java.
   <assign> -> <id> = <expr>
   <id> = A|B|C
   <expr> -> <expr> + <term> | <term>++ | <term>--
   <term> -> <term> * <factor> | <factor>
   <factor> -> (<expr>) | <id>

5. Write a BNF description of the Boolean expressions of Java, including the three operators &&, ||, and ! and the relational expressions.

   <Boolean_expr> -> <Boolean_expression> || <Boolean_term> | <Boolean_term>   <Boolean_term> -> <Boolean_term> && <Boolean_factor> | <Boolean_factor>   <Boolean_factor> -> id | !<Boolean_factor> | (<Boolean_expr>) | <relation_expr>   <relation_expr> -> id == id | id != id | id < id | id <= id | id >= id | id > id