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

Chapter 2: Evolution of Major Programming Languages

This post is about chapter 2 of Sebesta's Programming Language Concept book. I will show you about how I think about this chapter by answering 5 numbers of Review Questions, and 5 numbers of Problem Set.

Review Questions:

1. In what year was Plankalkül designed? In what year was that design published?

   Plankalkul was designed in 1945 by a German scientist called Konrad Zuse, but the Plankalkul itself was published in 1972.

2. What two common data structures were included in Plankalkül? 

   The data structures included in Plankalkul were arrays and records. Those two are just addition to the usual scalar type.

3. How were the pseudocodes of the early 1950s implemented?
   In the early 1950s, the computers  weren't as fast as they are nowadays. They were unreliable, expensive, and having extremely small memories. There were no high-level programming languages, so people have to do the programming using the machine code, which means using numeric codes for specifying instructions. Pseudocodes were made to avoid the errors by making new instructions to replace the numeric codes.

4. Speedcoding was invented to overcome two significant shortcomings of the computer hardware of the early 1950s. What were they?
    They were pseudoinstructions for the four arithmetic operations on floating-point data and also novel facility of automatically incrementing address registers.

5. Why was the slowness of interpretation of programs acceptable in the early 1950s? 
    Because in that time the available computers were far less usable than they were today. The computers were slow, unreliable, expensive, and having small memories. There was also lack of supporting software.

Problem Set:
1. What features of Plankalkül do you think would have had the greatest influence on Fortran 0 if the Fortran designers had been familiar with Plankalkül?
   It would be the arrays, loop, and selection features.

2. Determine the capabilities of Backus’s 701 Speedcoding system, and compare them with those of a contemporary programmable hand calculator.
   Backus's speedcoding system converted the 701 to a virtual three-address floating-point calculator which includes four arithmetic operational on floating point such as sqrt, sine, arc tangent, exponent, and logarithm. It was so fast because it only needs 4.2 miliseconds to execute.

3. Write a short history of the A-0, A-1, and A-2 systems designed by Grace Hopper and her associates.
  A-0, A-1, and A-2 was a project developed by a team led by Grace Hopper. They were actually a series of compiling system that expanded pseudocodes into machine code subprograms.

4. As a research project, compare the facilities of Fortran 0 with those of the Laning and Zierler system.
The Laning and Zierler system (Laning and Zierler, 1954) was the first algebraic translation system to be implemented. It translated arithmetic expressions, used separately coded subprograms to computer transcendental functions (e.g., sine and logarithm), and included arrays. Meanwhile, Fortran 0 was mathematical formula translation system implementation

5. Which of the three original goals of the ALGOL design committee, in your opinion, was most difficult to achieve at that time?
   It would be the second goal: "It should be possible to use the language for the description of algorithms in printed publications". In my opinion, it would be hard for someone who hasn't learnt about programming language to know the meaning of syntaxes. Even the syntax was made by human and still being adapted from natural language, sometimes it's hard to find out what does it mean, or when to use the syntax, etc.
   

First Meeting

Hello there, my name is Rizky Andiputra. I'm Binusian 2018 from School of Computer Science. This is my official blog for Programming Language Concept assignment, which is taught by Mr. Tri Djoko Wahjono, Ir.,M.Sc. He told us to make a blog where we can post our assignments. So this is my first assignment, he told me to do  review questions no. 1 - 5 and problem set no. 1-5 from Robert Sebesta's Concept of Programming Language ch. 1.

Review Questions:
1. Why is it useful for a programmer to have some background in language design, even though he or     she may never actually design a programming language?
   It is useful for a programmer to have some background in language design because even though the programmer hasn't designed a programming language, they have to know which vocabulary are commonly used for programming language syntax. For example: print, scan, if, end, etc.

2. How can knowledge of programming language characteristics benefit the whole computing community?
    By learning programming language characteristics, a programmer may

• increase his/her ability to express ideas,
• improve background for choosing appropriate programming language (which makes he / she knows which programming language is better for his / her needs), 
• increase ability to learn new language,
• understand the significance of implementation better, 
• use languages that have already known better, and
• have overall advancement in computing

3. What programming language has dominated scientific computing over the past 50 years?

     Fortran is the programming language that has been dominating for the scientific computing for more than 50 years. Fortran is also the first language used for scientific applications.

4. What programming language has dominated business applications over the past 50 years? 

    The programming language that has dominated business applications is COBOL. COBOL was made in 1960. It is still used for business applications until now.

5. What programming language has dominated artificial intelligence over the past 50 years?

    There are 2 most used programming languages for AI: LISP (appeared in 1959) and C. Actually there is one more programming language called Prolog, but it is not used a lot.

Problem Set:

1. Do you believe our capacity for abstract thought is influenced by our language skills? Support your opinion.
   For me language skills is important for the abstract thought. It's just the same as the time we want to share ideas to people. We have the rough idea, but still we have to ellaborate the idea into the bigger and greater ideas. We have to know what we are going to talk about, how to say it, etc. In programming, when we already have the idea about what we were going to do we still have to know how to make the program work, So language skill is important.

2. What are some features of specific programming languages you know whose rationales are a mystery to you? 

  I've already learnt the basic of some programming language such as C, HTML, and VB, and as far as I've learnt I haven't found something irrational in the syntax of the program. Every syntax has its own function.

3. What arguments can you make for the idea of a single language for all programming domains?     

   In every programming domain, we still use the same steps to do what we want the program do. It is called algorithm. Since there are algorithm, it is still possible to use a single language for all programming domains. All we have to do is translate the algorithm into the programming language.

4. What arguments can you make against the idea of a single language for all programming domains?

       Every programming domain has its own characteristics, e.g. for Web Software, it requires the head and body part, not like the other domain. So I think it's a little hard to do all programming domains with only using one programming language.

5. Name and explain another criterion by which languages can be judged (in addition to those discussed in this chapter).

• Easy to learn: Sometimes there are programming language that people find very difficult to learn. For me it would be better if a programming language is easier to learn, so programmer can explore more ideas and become more productive.
• Understandable: A good programming language is a language that can be understandable by the programmer or the user. It is important for user to understand the program. By understanding the  program, the user may know if there were any illegal activities such as phising, indentity stealing, etc.