KBP - Chapter 8

Review Question

1. A control structure is a control statement and the collection of statements whose execution it controls.

2. They proved that all algorithms that can be expressed by flowcharts can be coded in a programming language with only two control statements: one for choosing between two control flow paths and one for logically-controlled iterations.

6. Python uses indentation to specify control statements and using a colon instead of then for a then clause.

12. It was based on multiple selection statement in ALGOL 68, which doesn’t have implicit branches from selectable segments.

19. In Python, range function does the most simple counting loops. The function takes 1, 2, or 3 variables. If range function has 1 variable (let’s say n), then it returns 0, 1, …, n. If range function has 2 variables (let’s say m and n), then it returns m, m+1, m+2, … , n-1. If range function has 3 variables, however (let’s say m,n,d) then it returns m, m+d, up before it goes to larger or equal to n.

25. What are the differences between the break statement of C++ and that of Java?


C++ has unconditional unlabeled exit with name break, while Java has unconditional labeled exit with the same name. C++ can only break the loop in which the break scope it was in, while Java can break straight to any targeted loop.

___________________________________________________
Problem Set

1. What design issues should be considered for two-way selection statements?

The design issues are:

What is the form and type of the expression that controls the selection?
How are then and else clauses specified?
How should the meaning of nested selectors be specified?
2. Python uses indentation to specify compound statements. Give an example in support of this statement.

Example:

if x>y:

x=y

print “case 1”

6. In C language, a control statement can be implemented using a nested if else, as well as by using a switch statement. Make a list of differences in the implementation of a nested if else and a switch statement. Also suggest under what circumstances the if else control structure is used and in which condition the switch case is used.

Switch

More compact than lots of nested if else, therefore it has more readability.
Not quite flexible, as in some languages it can only available to certain (even sometimes should be similar) data types.
If-else

Allows more complex expressions and various possible data types as conditions.
Quite hard to read when it’s too nested.
Switch statement is used to check mostly when a certain variable is equal to a certain value. Example, to check whether variable a is equal to 1, 2, 3, or 4. Other example may be to check whether the choice of variable x is equal to ‘y’ or ‘n’. Switch(x){ case ‘y’: statement1; case ‘n’: statement2}

If-else, on the other hand, can be more practical, especially if the programmer wants to check a certain condition is true while the program is running. Example, checking whether variable var is smaller than 10. If (var<10){statement1} else {statement2}.

 11. Explain the advantages and disadvantages of the Java switch statement, compared to C++’s switch statement.


Java’s variable in the argument of a switch statement can be of integeral type (byte, short, int, etc), char, and String (JDK 1.7 and newer versions), but C++ can only be int or char.

KBP - Chapter 7

Review Question

1. Define operator precedence and operator associativity.
    - Operator precedence : the value of an expression depends at least in part on the order of evaluation of the operators in the expression.
    - Operator associativity : associates from left to right in common, but for exponentiation operator sometimes associates from right to left.

2. What is the ternary operator?
   It means the operator has three operands.

3. What is the prefix operator?
   It means the operator precede their operands.

8. Define functional side effect.
   It occurs when the function changes either one of its parameter or a global variable.

9. What is coercion?
   It is defined as an implicit type conversion that is initiated by the compiler.

18. What is short-circuit evaluation?
    It's one in which the result is determined without evaluating all of the operands "and" / "or" operators.

24. What two languages include multiple assignments?
    Perl, Ruby.

___________________________________________________
Problem Set

7. Describe a situation in which the add operator in a programming language would not be commutative.

   If the add operator for a language is also used to concatenate strings, it's quite apparent that it would not be commutative.
    For example:

        "abc" + "def" = "abcdef" 
        "def" + "abc" = "defabc"

    These two strings are obviously not equal, so the addition operator is not commutative.

9. Show the order of evaluation of the following expressions by parenthe-sizing all subexpressions and placing a superscript on the right parenthe-sis to indicate order.
     a). a*b-1+c
         (a*b) --> (a*b)-1 --> (((a*b)-1)+3)
     b). a*(b-1)/c mod d
         (b-1) --> a*(b-1) --> (a*(b-1)/c) --> ((a*(b-1)/c)mod d)
     c). (a-b)/c&(d*e/a-3)
         (a-b) --> ((a-b)/c) --> ...(d*e) --> ...((d*e)/a) --> ...(((d*e)/a)-3) --> (((a-b)/c)&(((d*e)/a)-3))
     d). -a or c=d and e
         (-a) --> ...(c=d) --> ...((c=d)and e) --> ((-a) or ((c=d)and e))
     e). a>b xor c or d<=17
         (a>b) --> (a>b)...(d<=17) --> ((a>b)xor c)...(d<=17) --> (((a>b)xor c) or (d<=17))
     f). -a+b
         (-a) --> ((-a)+b)

15. Explain why it is difficult to elimintae functional side effects in C?
    Functional programming requires that functions are first-class, which means that they are treated like any other values and can be passed as arguments to other functions or be returned as a result of a function.
    Being first-class also means that it is possible to define and manipulate functions from within other functions.
    Special attention needs to be given to functions that reference local variables from their scope. If such a function escapes their block after being returned from it, the local variables must be retained in memory, as they might be needed later when the function is called.
    Often it is difficult to determine statically when those resources can be released, so it is necessary to use automatic memory management.

18. Should an optimizing compiler for C or C++ be allowed to change the order of subexpressions in a Boolean expression? Why or why not?
    No. Because of short-circuit evaluation, the order of subexpressions around an && is important.

21. Why does Java specify that operands in expressions are all evaluated in lest-to-right order?
    Most groups use left-to-right associativity, which means that in an expression with operators in the same precedence group, the operators are applied in left-to-right order.

KBP - Chapter 6

Review Question

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

4. Describe the three string length options.
    - A static length string is the length that can be static and set when the string is created.
    - A limited dynamic strings is the option that allow strings to have varying length up to a declared and fixed maximum set by the variable's definition.
    - A dynamic length strings is the option that allow strings to have varying length with no maximum.

5. Define ordinal, enumeration, and subrange types.
    - An ordinaltype is one in which the range of possible values can be easily associated with the set of positive integers.
    - An enumeration is one in which all of the possible values, which are named constant, are provided, or enumbered, in the definition.
    - A subrange type is a contiguous subsequence of an ordinal type.

8. What are the design issues for arrays?
    - What types are legal for subscripts?
    - Are subscripting expressions in element references range checked?
    - When are subscript ranges bound?
    - when does array allocarion take place?
    - Are ragged or rectangular multidimensioned arrays allowed, or both?
    - Can arrays be initialized when they have their storage allocated?
    - What kinds of slices are allowed, if any?

15. What is an aggregate constant?
    An aggregate constant is a nonscalar constant which value never change or are not changed during execution of the program.

17. Define row major order and column major order.
     - Row major order : the elements of the array that have as their first subscript the lower bound value of that subscript are stored first, followed by the elements of the second value of the first subscript, and so forth.
     - Column major order : the elements of the array that have as their last subscript the lower bound value of that subscript are stored first, followed by the elements of the second value of the last subscript, and so forth.

31. Define union, free union, and discriminated union.
     - A union is a type whose variables may store different type values at different times during program execution.
     - A free union is the union construct is used to specify union structures.
     - A discriminated union is a union with a discriminant.

44. Define type error.
    A type error is the application of an operator to an operand of an inappropriate type.

45. Define strongly type.
    A programming language is called strongly type if type errors are always detected.

47. What is a nonconverting cast?
    A nonconverting cast is a kind of conversion that there's no actual conversion takes place, it's merely a means of extracting the value of a variable of one type and using it as if it were of a different type.

49. Why are C and C++ not strongly typed?
    Because both include union types, which are not type checked.

50. What is name type equivalence?
    It means that two variables have equivalent types if they are defined either in the same declaration or in declarations that use the same type name.

51. What is structure type equivalence?
    It means that two variables have equivalent types if their types have identical structures.

___________________________________________________
Problem Set

2. How are negative integers stored in memory?
   To store negative integers, we can use a notation called twos-complement, which is convenient for addition and subtraction.
   By using this notation, the representation of a negative integer is formed by taking the logical complement of the positive version of the number and adding one.
   Ones-complement notation is still used by some computer. With this notation, the negative of an integer is stored as the logical complemenet of its absolute value.

7. Compare the pointer and reference type variable in C++.
    - Pointer : to implement algorithms and data structures.
    - Reference : to define attractive interfaces in function parameters and return types.

8. What are the differences between the reference type variable of C++ and those of Java?
    - C++ : Pointers, references, and pass-by-value are supported.
    - Java : Primitive and reference data type parameters are always passed by value.

19. Any type defined with typedef is type equivalent to its parent type. How does the use of typedef differ in C and C++?
    Because in C, there are two different namespaces of types : a namespace of struct/union/enum tag names and a namespace of typedef names.
    While in C++, there's only a  subtle difference. It's a holdover from C, in which it made a difference.

21. In what way is dynamic type checking is better than static type checking?
     - it's simpler languages
     - lack of compile time, quicker turnaround
     - can pass variables/objects between modules without declare their type

KBP - Chapter 5

Review Question

1. What are the design issues for names?
    - Are names case sensitive?
    - Are the special words of the language reserved words or keywords?

4. What is an alias?
   Alias is more than one variable name can be used to access the same memory location.

7. Define binding and bingding time.
   Binding is an association between an atribute and an entity, such as between a variable and its type or value, or between an operation and a symbol.
   Binding time is the time which a binding takes place is called.

9. Define static binding and dynamic binding.
   Static binding is a binding that first occurs before run time begins and remains unchanged throughout program execution.
   Dynamic binding is a binding that first occurs during run time or can change in the course of program execution.

13. Define lifetime, scope, static scope, and dynamic scope.
    Lifetime is the time during which the variable is bound to a specific memory location.
    Scope is the range of statements in which the variable is visible.
    Static scope is the method of binding names to nonlocal variables in ALGOL 60.
    Dynamic scope is the calling sequence of subprograms, not on their spatial relationship to each other.

18. What is a block?
    Block is a section of code.

___________________________________________________
Problem Set

1. Decide which of the following identifier names is valid in C language. Support your decision.
   
   _Student : valid.
   int : invalid. Because int is a data type, not an identifier.
   Student : valid.
   123Student : invalid. Because numbers can't be located at the front, can only located at the back after the identifier name.
   Student123 : valid.

4. Why is the type declaration of a variable necessary? What is the value range of the int type variable in Java?
    - Because it associates a type and an identifier with the variable, and allows the compiler to decide how musch storage space to allocate for storage of the value associated with the identifier.
    - Values range for int in Java : from -2,147,483,648 to 2,147,483,647.
    

5. Describe a situation each where static and dynamic type binding is required.
    - Static type binding : the binding to an object is optional, if a name is not bound to an object, the name is said to be null.
    - Dynamic type binding : every variable name is bound only to an object.

KBP - Chapter 3

Review Question

1. Define syntax and semantics.
   Syntax is the form of its expressions, statements, and program units.
   Semantics is the meaning of those expressions, statements, and program unit.

2. Who are language descriptions for?
   For Language Recognizers and Language Generators.

5. What is the difference between a sentence and a sentential form?
   A sentence is the string of a language, while sentential form is each of the strings in derivation.

21. When is a grammar rule said to be left recursive?
    When a grammar rule has its LHS also appearing at the beginning of its RHS.

22. Give an example of an ambiguous grammar.
    Example :

       <assign> -> <id> = <expr>
       <id> -> A|B|C
       <expr> -> <expr> + <expr>
                | <expr * <expr>
                | (<expr>)
                | <id>

28. What is the use of the wp function? Why it is called a predicate transformer?
    Wp fuction is the least restrictive precondition that will guarantee the validity of the associated postcondition.
    It's called predicate transformer because it takes a predicate, or assertion, as a parameter and returns another predicate.

29. Give the difference between total correctness and partial correctness.
    Total correctness is the loop that can be shown, while partial correctness is the other condition that can be met, but termination is not guaranteed.

_______________________________________________________________________
Problem Set

1. Syntax error and semantic error are two types of compilation error.
    Explain the difference between the two in a program with examples.
    
    Syntax error --> struct Abc
                            {
                                int value;
                                char name[100];
                            }
                note : it should be like this :
                           struct Abc
                          {
                               int value;
                               char name[100];
                          };

    Semantic error --> for(int i=0;i<5;i--)
                                  {
                                        printf("Hey!"); printf("\n");
                                  }
                note : it should be like this :
                               for(int i=0;i<5;i++)
                               {
                                     printf("Hey!"); printf("\n");
                               }

3. Rewrite the BNF of Example 3.4 to represent operator – and operator / instead of operator + and operator *.

    <assign>-> <id> = expr

<id> -> A| B| C

<expr>-> <expr> -<term>

|<term>

<term>-> <term> / <factor>

| <factor>

<factor> -> (<expr>)

|<id>

6. Using the grammar in example 3.2, show a parse tree for each of the following statements:

   a).    =

         /   \

       a      *

             /   \

           *       a

         /   \

       b      +

             /   \

           c      a

         

   b).    =

         /   \

        b     *

             /   \

           +      c

          / \

        a    *

            /  \

          c     b

   c).    =

         /   \

        a     +

             /  \

            *    a

          /  \

        b     c

7. Using the grammar in example 3.4, show a parse tree for each of the following statements:

   a). A = (A*B)+C

<assign>-><id>=<expr>

<id>->A|B|C

<expr>-><id>+<expr>

|<term>

<term>-><term>*<factor>

|<factor>

<factor>->(<expr>)

|<id>

   b). A=B*C+A

<assign>-><id>=<expr>

<expr>-><expr>+<id>

|<term>

<term>-><term>*<factor>

|<factor>

<factor> -> (<expr>)

|<id>

   c). A = A + (B*C)

<assign>-><id>=<expr>

<expr>-><id>+<expr>

|<term>

<term>-><term>*<factor>

|<factor>

<factor>->(<expr>)

|<id>

   d). A = B*(C+(A*B))

<assign>-><id>=<expr>

<expr>-><id>*<expr>

|<term>

<term>-><term>+<factor>

|<factor>

<factor>-><id>*<id>

|<id>

13. Write a grammar for the language consisting of strings that have n copies of the letter a followed by double the number of copies of the letter b, where n >0. For example the strings abb, aabbbb, and aaabbbbbb are in the language but, a, aabb, ba, and aaabb are not.

    S-> aSb |ab 

18. What is a fully attributed parse tree?

    The tree is said to be fully attributed if all the attribute in a parse tree have been computed.

24. Compute the weakest precondition for each of the following sequences of assignment statements and their postcondition:

    a). b=a-3 --> b<0

        a-3<0 --> a<3

        a=2*b+1 --> a<3

        2*b+1<3 --> 2*b<2 --> b<1

    b). b=2*a-1 --> b>5

        2*a-1>5 --> 2*a>6 --> a>3

        a=3*(2*b+a) --> a>3

        3*(2*b+a)>3 --> 6*b+3*a>3 --> divided by 3 --> 2*b+a>1 --> b>(1-a)/2

KBP - Chapter 2

Review Questions

2. Its mixed one-dimensional and two-dimensional layout, which has puzzled many readers of the original document.
3. Plankalkul means "plan kalkulus" which means "formal system for planning".
5. The num of bits in a single word of the UNIVAC I's memory is 72 bits, and grouped as 12 six-bit bytes.
7.The speedcoding system developed by John Backus for the IBM 701.
8.The shortcode was developed by John Mauchly in 1949. Shortcode called automatic programming because it was implemented with a pure interpreter, not translated to machine code.
10. The most significant feature added to Fortran I to get Fortran II is Independent-compilation capability.
11. Logical loop statements and IF with an optional ELSE were added to Fortarn IV to get Fortran 77.
12. Fortran 90 was the first to have any sort of dynamic variables.
13. FOrtran 77 was the first to have character string handling.
16. Common LISP allows for static scoping and dynamic scoping, Scheme only uses static scooping. Scheme is relatively small while Common LISP is large and complex.
17. Scheme dialect is used to intriductory programming courses at some universities.
18. Two professional organizations together designed ALGOL 60 were ACM and GAMM.
20. Algol 58 introduced code blocks and the begin and end pairs for delimiting them, Algol 60 was the first language that implementing nested functions definitions with lexical scope.
21. BNF language was designed to describe the syntax of ALGOL 60.
22. On flow-matic language was COBOL based.
46. The primary application for Objectives-C is MacOS/iOS - iPhone.
49. A programming language for embedded consumer electronic devices was the first application for Java.

___________________________________________________
Problem Set

1. Logical data type and logical boolean expression, with this, we can create simple version of the complex compile, and link processes of earlier compilers.
6. Undefined escape sequences in literal strings. The backslash character can be used in literal strings and characters:
    - to escape various characters
    - to introduce an escape sequence representing a character
8. First, it is an interpreter type of language and focused on ease of use at the expense of system resources. Second, the running-time of a program that was written with the help of Speedcoding was usually ten to twenty times that of machine code.
7. Because that language continue to evolve from time to time.
9. It is to shorten the initialization of a variable.
12. Procedural programming is a classic programming where the program language is used to tell the computer exactly what to do, step by step. Non-procedural programming is where you tell the computer what you want, then the computer figures out how to get it. The incorporation of procedural and non-procedural features is used to overcome the lack of computer's knowledge to figure out some procedures by itself efficiently.
13. The reasons why C is more popular than Fortran are C is very broad in scope and C is very common in commercial world.
15. Yes, they are  : 
    - Fortran
    - C++
    - COBOL
    - Algol

KBP - Chapter 1

Review Questions

6. Unix usually written in the C language, with some small snippets of assembler code for low level bootstraps.

13. To be reliable, a program must perform its intended functions and operations in a system's environment, without experiencing failure.

14. Because it's considered very important for reliability.

15. Aliasing is the process of sublimate curves and other lines become jagged, it's because of the file is not high enough to represent a smooth curve.

16. Exception handling is the process of responding to the occurance during the computation, often changing the normal flow of program execution.

17. Because readability affects reliability in both writing and maintenance phases of the life cycle.

20. The name of the category of programming languages whose structure is dictated by Von Neumann is Imperative Languages.

21. Two programming language were discovered as a a result of the research of software development in 1970s are top-down design and stepwise refinement.

25. Three methods of implementing a programming language : Compilation, Pure Interpretation, Hybrid Implementation Sysytems.

28. Byte code provides portalbility to any machine that has a byte codeinterpreter and an associated run-time system.

29. Hybrid implementation systems is the source language statements are decoded only once.
___________________________________________________
Problem Set

2. Ada Lovelace is said to be the first programmer in human history.Her notes on the engine include what is recognized as the first algorithm intended to be processed by a machine. Because of this, she is considered the world's first computer programmer.

3. Java’s thread model is low-level and error-prone, and the language’s stated objective to hide machine details is an obstacle for low-level and real-time applications where such details are intrinsic to the problem.

4. The scientific applications used relatively simple data structures, but requires large number of floating-point arithmetic computations.
   While the business languages are characterized by facilities for producing elaborate reports, precise ways of describing and storing decimal numbers and character data.

5. Artificial Intelligence is a broad area of computer applications characterized by the use of symbolic rather than numeric. Requires more flexibility than other programming domains.
   While the Web Software is an eclectic collection of languages, ranging from markup languages, such as HTML(not a programming language) and to general-purpose programming languages(Java).

15. C++ programming languages uses preprocessor directive while Java is not using preprocessor directive.
Advantage : save time when calling a lot of function.
Disadvantage : the problem is the size of the program. The pre-processor will replace all the macros in the program by its real definition prior to the compilation process of the program.