Assignment #13

Source:
Concepts of Programming Languages, Robert W. Sebesta.

Chapter 13: Concurrency, page 625-628

By:
Name : Helena Natanael
NIM  : 1801380333

---

Review Question:

6. Describe the logical architecture of a vector processor.
Vector processor have groups of registers that store the operands of a vector operation in which the same instruction is executed on the whole group of operands simultaneously. Originally, the kinds of programs that could most benefit from this architecture were in scientific computation, an area of computing that is often the target of multiprocessor machines.

7. What is the difference between physical and logical concurrency?
Physical concurrency is a multiple independent processors (multiple threads of control). While logical concurrency is the appearance of physical concurrency is presented by time-sharing one processor (software can be designed as if there were multiple threads of control)

8. What is a thread of control in a program?
A thread of control in a program is the sequence of program points reached as control flows through the program.

9. Why are coroutines called quasi-concurrent?
They are called quasi-concurrent because they have a single thread of control.

10. What is a multithreaded program?

A multi-threaded program is a program designed to have more than one thread of control.

Problem Sets:

6. Suppose two tasks, A and B, must use the shared variable Buf_Size. Task A adds 2 to Buf_Size, and task B subtracts 1 from it. Assume that such arithmetic operations are done by the three-step process of fetching the current value, performing the arithmetic, and putting the new value back. In the absence of competition synchronization, what sequences of events are possible and what values result from these operations? Assume that the initial value of Buf_Size is 6.

The add and subtract operations are not atomic and could be interrupted in mid-operation when the other task could then run. If A runs to completion, then B runs to completion, Buf_Size has the value 7 (6 + 2 – 1). Similarly if B runs to completion then A runs to completion. If A or B get interrupted in the middle of adding or subtracting, then whichever task finishes last will determine the value in Buf_Size. If A runs but is interrupted after it fetches Buf_Size but before it stores the modified value (allowing B to fetch Buf_Size), or if B runs first and is interrupted after the fetch but before the store, allowing A to fetch Buf_Size, then if A finishes last Buf_Size will have value 8, and if B finishes last Buf_Size will have value 5.

7. Compare the Java competition synchronization mechanism with that of Ada.
Java methods (but not constructors) can be specified to be synchronized. A synchronized method called through a specific object must complete its execu- tion before any other synchronized method can run on that object. Competition synchronization on an object is implemented by specifying that the methods that access shared data are synchronized.

The competition synchronization mechanism of the Ada Language is intended to provide a facility for tasks to synchronize their actions. Accept and select statements are the two main features of the language that deal with the issue of synchronization This paper points out one major problem that arises in connection with these features and proposes a possible solution to it.

8. Compare the Java cooperation synchronization mechanism with that of Ada.
In Java, cooperation synchronization  is implemented with the wait, notify, and notify. All methods, all of which are defined in Object, the root class of all Java classes. Every object has a wait list of all of the threads that have called wait on the object. While in Ada, cooperation synchronization is required between two tasks that when the second task must wait for the first task to finish executing before it may proceed.

9. What happens if a monitor procedure calls another procedure in the same monitor?
Implementation of a monitor can be made to guarantee synchronized access by allowing only one access at a time. Calls to monitor procedures are implicitly blocked and stored in a queue if the monitor is busy at the time of the call.

10. Explain the relative safety of cooperation synchronization using semaphores and using Ada’s when clauses in tasks.
We need to take steps to make sure that different threads don't interact in negative ways. If one thread is operating on some data or structure, we don't want another thread to simultaneously operate on that same data/structure and corrupt the results; when Thread A writes to a variable that Thread B accesses, we need to make sure that Thread B will actually see the value written by Thread A; we don't want one thread to hog, take or lock for too long a resource that other threads need in order to make progress.

Assignment #12

Source:
Concepts of Programming Languages, Robert W. Sebesta.

Chapter 12: Support for Object-Oriented Programming, page 570-572

By:
Name : Helena Natanael
NIM  : 1801380333

---

Review Question:

6. Describe a situation where dynamic binding is a great advantage over its absence.
Consider the following situation:
There is a base class, A, that defines a method draw that draws some figure associated with the base class. A second class, B, is defined as a subclass of A. Objects of this new class also need a draw method that is like that provided by A but a bit different because the subclass objects are slightly different. So, the subclass overrides the inherited draw method. If a client of A and B has a variable that is a reference to class A’s objects, that reference also could point at class B’s objects, making it a polymorphic reference. If the method draw, which is defined in both classes, is called through the polymorphic reference, the run-time system must determine, during execution, which method should be called, A’s or B’s.

7. What is a virtual method?
A virtual method is a declared class method that allows overriding by a method with the same derived class signature. Virtual methods are tools used to implement the polymorphism feature of an object-oriented language, such as C#. When a virtual object instance method is invoked, the method to be called is determined based on the object's runtime type, which is usually that of the most derived class.

8. What is an abstract method? What is an abstract class?
An abstract method is a method which all descendant classes should have. An abstract class is a class which has abstract method.

9. Describe briefly the eight design issues used in this chapter for object-oriented
languages.

• What non-objects are in the language?
• Are Subclasses Subtypes? If so, derived objects can be legally used wherever a parent object could be used.
• Type Checking and Polymorphism
• Single and Multiple Inheritance. Inherit from 1 (or more than 1) parent.
• Object Allocation and Deallocation.  Are objects allocated from heap or stack.
• Dynamic and Static Binding. When are messages bound to methods, before or during run-time?
• Nested Classes. Can a class be nested inside another class?
• Initialization of Objects. Are objects initialized when created? Implicit or explicit?

10. What is a nesting class?

A nesting class is a class defined inside another class

Problem Sets:

6. Compare the multiple inheritance of C++ with that provided by interfaces in Java.
C++ inheritance is implementation inheritance. That is, a class inheriting from two of more superclasses actually inherits the code from those classes. Java’s interface mechanism is an interface inheritance. That is, a class implementing two or more interfaces simply inherits (and must provide its own implementations for) the methods of the interface.

7. What is one programming situation where multiple inheritance has a significant advantage over interfaces?
A situation when there are two classes derived from a common parent and they have a child.

8. Explain the two problems with abstract data types that are ameliorated by inheritance.
The problems solved are reusability of code and “extensibility”. Reusability because one won’t have to copy/paste his code from one data type to another, allowing for a greater readability. Extensibility because a method can accept a certain class as an argument, and get a child class of this one. This will allow the user to have a wider set of functionality, but the method will still be able to know that the entities it relies on are present.

9. Describe the categories of changes that a subclass can make to its parent class.
Subclasses can add things (variables, methods). Subclass in C++ can effectively remove a method using "private" inheritance. Inherited methods can be overridden.

10. Explain one disadvantage of inheritance.
Disadvantage of using inheritance is that the two classes (base and inherited class) get tightly coupled.
This means one cannot be used independent of each other.

Assignment #11

Source:
Concepts of Programming Languages, Robert W. Sebesta.

Chapter 11: Abstract Data Types and Encapsulation Constructs, page 519-521

By:
Name : Helena Natanael
NIM  : 1801380333

---

Review Question:

6. Explain how information hiding is provided in an Ada package.
There are two approaches to hiding the representation from clients in the package specification. The first one is to include two sections in the package specification, the second one is in which entities are visible to clients and one that hides its contents.

7. To what is the private part of an Ada package specification visible?
The private part of an Ada package specification is visible to the compiler but not to the client programs.

8. What is the difference between private and limited private types in Ada?
Private types have built-in operations for assignment and comparison. Limited private types don’t have built-in operations.

9. What is in an Ada package specification? What about a body package?
Body package, is an Ada package which provides the implementation of most, if not all, of the entities named in the associated package specification.

10. What is the use of the Ada with clause?

The ‘with’ clause in Ada makes the names defined in external packages visible.

Problem Sets:

6. Discuss the advantages of C# properties, relative to writing accessor methods in C++ or Java.
The advantage of C# Properties relative to writing accessor are:
- Read-only access can be provided, by having a getter method but no corresponding setter method.
- Constraints can be included in setters. For example, if the data value should be restricted to a particular range, the setter can enforce that.
- The actual implementation of the data member can be changed without affecting the clients if getters and setters are the only access.

7. Explain the dangers of C’s approach to encapsulation.
There are two problems with this approach. First, the documentation of the dependence of the client program on the library (and its header file) is lost. Second, the author of the library could change the header file and the implementation file, but the client could attempt to use the new implementation file (not realizing it had changed) but with the old header file, which the user had copied into his or her client program.

8. Why didn’t C++ eliminate the problems discussed in Problem 7? 
Because in C++ these kinds of problems can be handled by allowing nonmember functions to be “friends” of a class. Friend functions have access to the private entities of the class where they are declared to be friends.

9. What are the advantages and disadvantages of the Objective-C approach to syntactically distinguishing class methods from instance methods?
Instance methods use an instance of a class, whereas a class method can be used with just the class name. A class is like the blueprint of a house: You only have one blueprint and (usually) you can't do that much with the blueprint alone. An instance (or an object) is the actual house that you build based on the blueprint: You can build lots of houses from the same blueprint. You can then paint the walls a different color in each of the houses, just as you can independently change the properties of each instance of a class without affecting the other instances.

10. In what ways are the method calls in C++ more or less readable than
those of Objective-C?

In Objective C, all method calls are essentially virtual. This makes it a bit easier on the programmer, but it comes at a possible performance decrease. Hence sometimes methods call in C++ can be more or less readable than those of Objective-C.

Assignment #10

Source:
Concepts of Programming Languages, Robert W. Sebesta.

Chapter 10: Implementing Subprograms, page 467-470

By:
Name : Helena Natanael
NIM  : 1801380333

---

Review Question:

6. What is the difference between an activation record and an activation record instance?
The format, or layout, of the noncode part of a subprogram is called an activation record, because the data it describes are relevant only during the activation, or execution of the subprogram. The form of an activation record is static. An activation record instance is a concrete example of an activation record, a collection of data in the form of an activation record.

7. Why are the return address, dynamic link, and parameters placed in the bottom of the activation record?
Because the return address, dynamic link, and parameters are placed in the activation record instance by the caller, these entries must appear first. The return address usually consists of a pointer to the instruction following the call in the code segment of the calling program unit. The dynamic link is a pointer to the base of the activation record instance of the caller. In static- scoped languages, this link is used to provide traceback information when a run-time error occurs. In dynamic-scoped languages, the dynamic link is used to access nonlocal variables. The actual parameters in the activation record are the values or addresses provided by the caller.

8. What kind of machines often use registers to pass parameters?
In many compilers for RISC machines, parameters are passed in registers. This is because RISC machines normally have many more registers than CISC machines. In the remainder of this chapter, however, we assume that parameters are passed in the stack. It is straightforward to modify this approach for parameters being passed in registers.

9. What are the two steps in locating a nonlocal variable in a static-scoped language with stack-dynamic local variables and nested subprograms?
The first step of the access process is to find the instance of the activation record in the stack in which the variable was allocated. The second part is to use the local_offset of the variable (within the activation record instance) to access it.

10. Define static chain, static_depth, nesting_depth, and chain_offset.

• A static chain is a chain of static links that connect certain activation record instances in the stack. During the execution of a subprogram P, the static link of its activation record instance points to an activation record instance of P’s static parent program unit.
• A static_depth is a static scope that indicates how deeply it is nested in the outermost scope. A program unit that is not nested inside any other unit has a static_depth of 0. If subprogram A is defined in a nonnested program unit, its static_depth is 1. If subprogram A contains the definition of a nested subprogram B, then B’s static_depth is 2.
• A nesting_depth or chain_offset is the difference between the static_depth of the subprogram containing the reference to X and the static_depth of the subprogram containing the declaration for X.

Problem Sets:

6. Although local variables in Java methods are dynamically allocated at the beginning of each activation, under what circumstances could the value of a local variable in a particular activation retain the value of the previous activation?
Each activation allocates variables in exactly the same order. Variables are not initialized to any value unless the program contains an initialization statement for the variable – they simply have whatever value is stored in the location they are allocated. If a procedure finishes executing, returns, and is immediately reinvoked, a variable would be assigned the same stack location it had on the previous invocation, and would have the last value from that previous invocation.

7. It is stated in this chapter that when nonlocal variables are accessed in a dynamic-scoped language using the dynamic chain, variable names must be stored in the activation records with the values. If this were actually done, every nonlocal access would require a sequence of costly string comparisons on names. Design an alternative to these string comparisons that would be faster.
Using approach that uses an auxiliary data structure called a display. Or, to write variable names as integers. These integers act like an array. So when the activation happens, the comparisons will be faster.

8. Pascal allows gotos with nonlocal targets. How could such statements be handled if static chains were used for nonlocal variable access?
Hint:
Consider the way the correct activation record instance of the static parent of a newly enacted procedure is found (see Section 10.4.2).
Based on the hint statement, the target of every goto in a program could be represented as an address and a nesting_depth, where the nesting_depth is the difference between the nesting level of the procedure that contains the goto and that of the procedure containing the target. Then, when a goto is executed, the static chain is followed by the number of links indicated in the nesting_depth of the goto target. The stack top pointer is reset to the top of the activation record at the end of the chain.

9. The static-chain method could be expanded slightly by using two static links in each activation record instance where the second points to the static grandparent activation record instance. How would this approach affect the time required for subprogram linkage and nonlocal references?
Including two static links would reduce the access time to nonlocals that are defined in scopes two steps away to be equal to that for nonlocals that are one step away. Overall, because most nonlocal references are relatively close, this could significantly increase the execution efficiency of many programs.

10. Design a skeletal program and a calling sequence that results in an activation record instance in which the static and dynamic links point to different activation-recorded instances in the run-time stack.

\verb+   + X : Integer;\\

\verb+   +procedure Bigsub is\\

\verb+   +\verb+   +     A, B, C : Integer;\\

\verb+   +\verb+   +     procedure Sub1 is\\

\verb+   +\verb+   +\verb+   +   A, D : Integer;\\

\verb+   +\verb+   +\verb+   +   begin — of Sub1\\

\verb+   +\verb+   +\verb+   +   A := B + C; $\longleftarrow$ 1\\

\verb+   +\verb+   +\verb+   +     …\\

\verb+   +   end; — of Sub1\\

\verb+   +   procedure Sub2(X : Integer) is\\

\verb+   +\verb+   +       B, E : Integer;\\

\verb+   +\verb+   +       procedure Sub3 is\\

\verb+   +\verb+   +\verb+   +       C, E : Integer;\\

\verb+   +\verb+   +\verb+   +       begin — of Sub3\\

\verb+   +\verb+   +\verb+   +       …\\

\verb+   +\verb+   +\verb+   +       Sub1;\\

\verb+   +\verb+   +\verb+   +       …\\

\verb+   +\verb+   +\verb+   +       E := B + A; $\longleftarrow$ 2\\

\verb+   +\verb+   +       end; — of Sub3\\

\verb+   +\verb+   +       begin — of Sub2\\

\verb+   +\verb+   +    …\\

\verb+   +\verb+   +       Sub3;\\

\verb+   +\verb+   +       …\\

\verb+   +\verb+   +       A := D + E; $\longleftarrow$ 3\\

\verb+   +   end; — of Sub2\\

\verb+   +   begin — of Bigsub\\

\verb+   +\verb+   +     …\\

\verb+   +\verb+   +     Sub2(7);\\

\verb+   +\verb+   +     …\\

\verb+   + end; — of Bigsub\\

begin — of Main\_2\\

\verb+   + …\\

\verb+   + Bigsub;\\

\verb+   + …\\

end; — of Main\_2\\

\\

The sequence of procedure calls is:\\

Main\_2 calls Bigsub\\

Bigsub calls Sub2\\

Sub2 calls Sub3\\

Sub3 calls Sub1\\

\\

The activation records with static and dynamic links is as follows:\\

\begin{figure}

\centering

\includegraphics[scale=0.5]{ari}

\end{figure}

Assignment #9

Source:
Concepts of Programming Languages, Robert W. Sebesta.

Chapter 9: Subprograms, page 436-439

By:
Name : Helena Natanael
NIM  : 1801380333

---

Review Question:

6. What is a Ruby array formal parameter?
Ruby supports a complicated but highly flexible actual parameter configuration. The initial parameters are expressions, whose value objects are passed to the corresponding formal parameters. The initial parameters can be following by a list of key => value pairs, which are placed in an anonymous hash and a reference to that hash is passed to the next formal parameter. These are used as a substitute for keyword parameters, which Ruby does not support. The hash item can be followed by a single parameter preceded by an asterisk. This parameter is called the array formal parameter.

7. What is a parameter profile? What is a subprogram protocol?

Parameter profile is the number, order, and types of its formal parameters. Subprogram protocol is its parameter profile plus, if it is a function, its return type. In languages in which subprograms have types, those types are defined by the subprogram’s protocol.

8. What are formal parameters? What are actual parameters?
- Formal parameters are the parameters in the subprogram header.

- Actual parameters are a list of parameters to be bound to the formal parameters of the subprogram which must be included with the name of the subprogram by the subprogram call statements.

 9. What are the advantages and disadvantages of keyword parameters?
- The advantage : they can appear in any order in the actual parameter list. 

- The disadvantage : the user of the subprogram must know the names of formal parameters.

10. What are the differences between a function and a procedure?
A function returns value but procedures do not. Function are structurally resemble procedures but are semantically modeled on mathematical parameter.



Problem Sets:

6. Present one argument against providing both static and dynamic local variables in subprograms.
In subprograms local variables can be static or dynamic;  
If local variable treated statically:
This allows for compile-time allocation/ deallocation and ensures proper type checking but does not allow for recursion.
If local variables treated dynamically:
This allows for recursion at the cost of run-time allocation/ deallocation and initialization because these are stored on a stack, referencing is indirect based on stack position and possibly time-consuming.


7. Consider the following program written in C syntax:
void fun (int first, int second) {
first += first; second += second;
}
void main() {
int list[2] = {1, 3};
fun(list[0], list[1]);
}
For each of the following parameter-passing methods, what are the values
of the list array after execution?
a. Passed by value : 1,3
b. Passed by reference : 2,6
c. Passed by value-result : 2,6


8. Argue against the C design of providing only function subprograms.
If a language provides only functions, then either programmers must live with the restriction of returning only a single result from any subprogram, or functions must allow side effects, which is generally considered bad. Since having subprograms that can only modify a single value is too restrictive, C’s choice is not good.


9. From a textbook on Fortran, learn the syntax and semantics of statement functions. Justify their existence in Fortran.

The Fortran 1966 standard provided a reference syntax and semantics, but vendors continued to provide incompatible extensions. These standards have improved portability.

10. Study the methods of user-defined operator overloading in C++ and Ada, and write a report comparing the two using our criteria for evaluating languages.
One of the nice features of C++ is that you can give special meanings to operators, when they are used with user-defined classes. This is called operator overloading. You can implement C++ operator overloads by providing special member-functions on your classes that follow a particular naming convention. For example, to overload the + operator for your class, you would provide a member-function named operator+ on your class. Meanwhile for Ada, since much of the power of the language comes from its extensibility, and since proper use of that extensibility requires that we make as little distinction as possible between predefined and user-defined types, it is natural that Ada also permits new operations to be defined, by declaring new overloading of the operator symbols.

Assignment #8

Source:

Concepts of Programming Languages, Robert W. Sebesta.

Chapter 8: Statement-Level Control Structures, page 381-382

By:
Name : Helena Natanael
NIM  : 1801380333
P.S.: Happy New Year 2015! :)

---

Review Question:

6. What is unusual about Python’s design of compound statements?
Python uses indentation to specify compound statements. 
For example,
if x < y :
x = y
print "value of x is modified".
All statements equally indented are included in the compound statement.

7. Under what circumstances must an F# selector have an else clause?

An F# selector have an “else” clause if the “if” expression does return a value.

8.What are the common solutions to the nesting problem for two-way selectors?
A programmer should avoid syntactic entity because in some cases, syntactic entity leads to ambiguous meaning when it is compiled. Another way to avoid the issue of nested selection statements is to use an alternative means of forming compound statements.


 9. What are the design issues for multiple-selection statements?
1. What is the form and type of the expression that controls the selection?• How are the selectable segments specified?
2. Is execution flow through the structure restricted to include just a single selectable segment?
3. How are the case values specified?
4. How should unrepresented selector expression values be handled, if at all?

10. Between what two language characteristics is a trade-off made when deciding whether more than one selectable segment is executed in one execution of a multiple selection statement?
The C# switch statement differs from that of its C-based predecessors in two ways. First, C# has a static semantics rule that disallows the implicit execution of more than one segment. The rule is that every selectable segment must end with an explicit unconditional branch statement: either a break,
which transfers control out of the switch statement, or a goto, which can transfer control to one of the selectable segments (or virtually anywhere else).

As with C, if there is no break at the end of the selected segment, execution continues into the next segment.



Problem Sets:

6. Analyze the potential readability problems with using closure reserved words for control statements that are the reverse of the corresponding initial reserved words, such as the case-esac reserved words of ALGOL 68. For example, consider common typing errors such as transposing characters.
The potential readability problem is the typing errors. It’s very possible to occur if we don’t type the code carefully.


7. Use the Science Citation Index to find an article that refers to Knuth (1974). Read the article and Knuth’s paper and write a paper that summarizes both sides of the goto issue.
An alternative viewpoint is presented in Donald Knuth's Structured Programming with go to Statements, which analyzes many common programming tasks and finds that in some of them GOTO is the optimal language construct to use.[7] In their quasi-standard book on the C programming language, Dennis Ritchie and Brian Kernighan warn that goto is "infinitely abusable", but also suggest that it could be used for end-of-function error handlers and for multi-level breaks from loops.


8. In his paper on the goto issue, Knuth (1974) suggests a loop control statement that allows multiple exits. Read the paper and write an operational semantics description of the statement.
Operational semantics are a category of formal programming language semantics in which certain desired properties of a program, such as correctness, safety or security, are verified by constructing proofs from logical statements about its execution and procedures, rather than by attaching mathematical meanings to its terms (denotational semantics).


9. What are the arguments both for and against the exclusive use of Boolean expressions in the control statements in Java (as opposed to also allowing arithmetic expressions, as in C++)?

The primary argument for using Boolean expressions exclusively as control expressions is the reliability that results from disallowing a wide range of types for this use. In C, for example, an expression of any type can appear as a control expression, so typing errors that result in references to variables of incorrect types are not detected by the compiler as errors. No , it would not be a good idea. Although this custom precedence sounds like increasing flexibility, requiring parentheses to show a custom precedence would impact in readability and writability of a program.

10. In Ada, the choice lists of the case statement must be exhaustive, so that there can be no unrepresented values in the control expression. In C++, unrepresented values can be caught at run time with the default selector. If there is no default, an unrepresented value causes the whole statement to be skipped. What are the pros and cons of these two designs (Ada and C++)? 

---- C++ :
1. Control expression can be only an integer type 

2. Selectable segments can be statement sequences, blocks, or compound statements 

3. Construct is encapsulated 

4. Any number of segments can be executed in one execution of the construct (there is no implicit branch at the end of selectable segments) (a trade-off between reliability and flexibility–convenience) - To avoid it, the programmer must supply a break statement for each segment.
5. default clause is for unrepresented values (if there is no default, the whole statement does nothing) 

 ----- Ada:

 1. Constant lists can include: - Subranges e.g., 10..15
- Boolean OR operators
e.g., 1..5 | 7 | 15..20
2. Lists of constants must be exhaustive - Often accomplished with others clause
- This makes it more reliable.

Assignment #7

Source:

Concepts of Programming Languages, Robert W. Sebesta.

Chapter 7: Expressions and Assignment Statements, page 342-344

By:
Name : Helena Natanael
NIM  : 1801380333

---

Review Question:

6. What associativity rules are used by APL?
In APL, all operators have the same level of precedence. Thus, the order of evaluation of operators in APL expressions is determined entirely by the associativity rule, which is right to left for all operators.

7. What is the difference between the way operators are implemented in C++ and Ruby?

What sets Ruby apart from the C-based languages in the area of expressions is that all of the arithmetic, relational, and assignment operators, as well as array indexing, shifts, and bitwise logic operators, are implemented as methods. For example, the expression a + b is a call to the + method of the object referenced by a, passing the object referenced by b as a parameter.

8. Define functional side effect.
A side effect of a function, naturally called a functional side effect, occurs when the function changes either one of its parameters or a global variable. (A global variable is declared outside the function but is accessible in the function.)

 9. What is a coercion?
Coercion is an implicit type of conversion only if they are widening (from a “smaller” type to a “larger” type). So int to float coercions are done across the assignment operator, but float to int coercions are not.

10. What is a conditional expression?
Conditional Expression is a logical feature of programming language which perform different actions based on true or false. 
In trinary, the format is statement ? action_1 (if true) : action_2 (if false).



Problem Sets:

6. Should C’s single-operand assignment forms (for example, ++count) be included in other languages (that do not already have them)? Why or why not?
Yes C should, because it will ease the increment or even decrement while we use in looping rather than manually by the assigning, and also by using that we can easily know that it is not operation, instead it is an increment or decrement which is usually used in repetition.

7. Describe a situation in which the add operator in a programming language would not be commutative.
It wouldn’t be commutative when it deals with the negative integers.

8. Describe a situation in which the add operator in a programming language would not be associative.
It is not associative when it includes the other operator with higher precedence like the multiplication and division.

9.Assume the following rules of associativity and precedence for expressions:

Precedence                    

Highest                          *, /, not

                                      +,–,&,mod

                                      (unary)

                                      =, /=, < , <=, >=, >

                                      and
Lowest                           or, xor
Associativity                  Left to right


Show the order of evaluation of the following expressions by parenthesizing all sub expressions and placing a superscript on the right parenthesis to indicate order. For example, for the expression
a+b*c+ d
the order of evaluation would be represented as
((a + (b * c)¹)² + d)³

1. a * b – 1 + c

( ( (a * b)¹– 1)² + c)³
2. a* ( b – 1) / c mod d
( ( (a* ( b – 1)¹ )²/ c )³ mod d)⁴
3. (a – b) / c & (d * e / a – 3)
( ( (a – b)¹/ c)² & ( ( (d * e)³ / a)⁴ – 3)⁵ )⁶
4. –a or c = d and e
( (–a)¹ or ( (c = d)² and e)³ )⁴
5. a > b xor c or d <= 17
( ( (a > b)¹ xor c)³ or (d <= 17)² )⁴
6. –a + b
( – (a + b)¹ )²

10. Show the order of evaluation of the expressions of Problem 9, assuming that there are no precedence rules and all operators associate right to left.

a. ( a * ( b – ( 1 + c )¹ )² )³
b. ( a * ( ( b – 1 )² / ( c mod d )¹ )³ )⁴
c. ( ( a – b )⁵ / ( c & ( d * ( e / ( a – 3 )¹ )² )³ )⁴ )⁶
d. ( – ( a or ( c = ( d and e )¹ )² )³ )⁴
e. ( a > ( xor ( c or ( d <= 17 )¹ )² )³ )⁴
f. ( – ( a + b )¹ )²

Assignment #6

Source:

Concepts of Programming Languages, Robert W. Sebesta.

Chapter 6: Data Types, page 312-314

By:
Name : Helena Natanael
NIM  : 1801380333

---

Review Question:

6. What are the advantages of user-defined enumeration types?
Enumeration types can provide advantages in both readability and reliability. First is no arithmetic operations are legal on enumeration types; this prevents adding days of the week, for example. And second, no enumeration variable can be assigned a value outside its defined range.

7. In what ways are the user-defined enumeration types of C# more reliable than those of C++?

C# enumeration types are like those of C++, except that they are never coerced to integer. So, operations on enumeration types are restricted to those that make sense. Also, the range of values is restricted to that of the particular enumeration 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 allocation 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?

9.Define static, fixed stack-dynamic, stack-dynamic, fixed heap-dynamic, and 
heap-dynamic arrays. What are the advantages of each?
A static array is one in which the subscript ranges are statically bound and storage allocation is static. The advantage of static arrays is efficiency: No dynamic allocation or deallocation is required.

A fixed stack-dynamic array is one in which the subscript ranges are statically bound, but the allocation is done at declaration elaboration time during execution. The advantage of fixed stack-dynamic arrays over static arrays is space efficiency.

A stack-dynamic array is one in which both the subscript ranges and the storage allocation are dynamically bound at elaboration time. The advantage of stack-dynamic arrays over static and fixed stack-dynamic arrays is flexibility.

A fixed heap-dynamic array is similar to a fixed stack-dynamic array, in that the subscript ranges and the storage binding are both fixed after storage is allocated. The advantage of fixed heap-dynamic arrays is flexibility the array’s size always fits the problem.

A heap-dynamic array is one in which the binding of subscript ranges and storage allocation is dynamic and can change any number of times during the array’s lifetime. The advantage of heap-dynamic arrays over the others is flexibility: Arrays can grow and shrink during program execution as the need for space changes.

10.What happens when a nonexistent element of an array is referenced 
in Perl?
A reference to a nonexistent element in Perl yields undef, but no error is reported.


Problem Sets:

6.Explain all of the differences between Ada’s subtypes and derived types.
A derived type is a new type that is based on some previously defined type with which it is not equivalent, although it may have identical structure. Derived types inherit all the properties of their parent types. Consider the following example:
type Celsius is new Float;
type Fahrenheit is new Float;

The types of variables of these two derived types are not equivalent, although their structures are identical. Furthermore, variables of both types are not type equivalent with any other floating-point type. Derived types can also include range constraints on the parent type, while still inheriting all of the parent’s operations.

On the other hand Ada subtype is a possibly range-constrained version of an existing type. A subtype is type equivalent with its parent type. Ada’s derived types are very different from Ada’s subrange types.
For example, consider the following type declarations:
type Derived_Small_Int is new Integer range 1..100; subtype Subrange_Small_Int is Integer range 1..100;
Variables of both types, Derived_Small_Int and Subrange_Small_Int, have the same range of legal values and both inherit the operations of Integer.

However, variables of type Derived_Small_Int are not compatible with any Integer type. On the other hand, variables of type Subrange_Small_Int are compatible with variables and constants of Integer type and any subtype of Integer.

7. What significant justification is there for the -> operator in C and C++?
The justification of –> operator in c and c++ is writability. In c ++ there are 2 ways a pointer record can be used to reference a field in that record. It is slightly easier to write p –> q than(*p).q.

8. What are all of the differences between the enumeration types of C++ and those of Java?
In Java they can include fields, constructors, and methods. The possible values of an enumeration are the only possible instances of the class. All enumeration types inherit toString, as well as a few other methods. An array of the instances of an enumeration type can be fetched with the static method values. The internal numeric value of an enumeration variable can be fetched with the ordinal method. No expression of any other type can be assigned to an enumeration variable. Also, an enumeration variable is never coerced to any other type.

9.The unions in C and C++ are separate from the records of those languages, rather than combined as they are in Ada. What are the advantages and disadvantages to these two choices?
The advantage: Unconstrained variant records in Ada allow the values of their variants to change types during execution. 

The disadvantage: the type of the variant can be changed only by assigning the entire record, including the discriminant. This disallows inconsistent records because if the newly assigned record is a constant data aggregate, the value of the tag and the type of the variant can be statically checked for consistency.

10. Multidimensional arrays can be stored in row major order, as in C++, or in column major order, as in Fortran. Develop the access functions for both of these arrangements for three-dimensional arrays.
Let the subscript ranges of the three dimensions be named min(1), min(2), min(3), max(1), max(2), and max(3). Let the sizes of the subscript ranges be size(1), size(2), and size(3). Assume the element size is 1.

Row Major Order:
location(a[i,j,k]) = (address of a[min(1),min(2),min(3)])
+((i-min(1))*size(3) + (j-min(2)))*size(2) + (k-min(3))
Column Major Order:
location(a[i,j,k]) = (address of a[min(1),min(2),min(3)])
+((k-min(3))*size(1) + (j-min(2)))*size(2) + (i-min(1))

Assignment #5

Source:

Concepts of Programming Languages, Robert W. Sebesta.

Chapter 5: Names, Bindings, and Scopes, page 235-240

By:
Name : Helena Natanael
NIM  : 1801380333

---

Review Question:

6. What is the l-value of a variable? What is the r-value?
The l-value of variable is the address of a variable because the address is required when the name of a variable appears in the left side of an assignment. 
The r-value of variable is a variable’s value because it is required when the name of the variable appears in the right side of an assignment statement.

7. Define binding and binding time.
A binding is an association between an attribute and an entity, such as between a variable and its type or value, or between an operation and a symbol. While the time at which a binding takes place is called binding time.

8. After language design and implementation [what are the four times bindings can take place in a program?]
The compile time binding, the load time binding, the link time binding, the run time binding.

9. Define static binding and dynamic binding.
A static binding is when the binding occurs before run time begins and remains unchanged throughout program execution. If the binding first occurs during run time or can change in the course of program execution, it is called dynamic binding.

10. What are the advantages and disadvantages of implicit declarations?
The advantage of implicit declarations is that simple in naming conventions. In this case, the compiler or interpreter binds a variable to a type based on the syntactic form of the variable’s name. While the disadvantage of implicit declarations is it can be detrimental to reliability because they prevent the compilation process from detecting some typographical and programmer errors.


Problem Set:

6. Consider the following JavaScript skeletal program:
// The main program
var x;
function sub1() {
var x;
function sub2() {
. . .
}
}
function sub3() {
. . .
}
Assume that the execution of this program is in the following unit order:
main calls sub1
sub1 calls sub2
sub2 calls sub3

a. Assuming static scoping, in the following, which declaration
of x is the correct one for a reference to x?
i. sub1
sub1: sub1

ii. sub2
sub2: sub1

iii. sub3
sub3: main

b. Repeat part a, but assume dynamic scoping.
i. sub1
sub1: sub1
ii. sub2
sub2: sub1
iii. sub3
sub3: sub1

7. Assume the following JavaScript program was interpreted using
static-scoping rules. What value of x is displayed in function sub1?
Under dynamic-scoping rules, what value of x is displayed in function
sub1?
var x;
function sub1() {
document.write("x = " + x + "<br />");
}
function sub2() {
var x;
x = 10;
sub1();
}
x = 5;
sub2();

static scoping rule = 5
dynamic scoping rule = 10


8. Consider the following JavaScript program:
var x, y, z;
function sub1() {
var a, y, z;
function sub2() {
var a, b, z;
. . .
}
. . .
}
function sub3() {
var a, x, w;
. . .
}
List all the variables, along with the program units where they are
declared, that are visible in the bodies of sub1, sub2, and sub3, assuming
static scoping is used.

Variable                       Where Declared
In Sub1:
a                                             Sub1
y                                             Sub1
z                                             Sub1
x                                             Main
In Sub2:
a                                             Sub2
b                                             Sub2
z                                             Sub2
y                                             Sub1
x                                             Main
In Sub3:
a                                             Sub3
x                                             Sub3
w                                            Sub3
y                                             Main
z                                             Main


9. Consider the following Python program:
x = 1;
y = 3;
z = 5;
def sub1():
a = 7;
y = 9;
z = 11;
. . .
def sub2():
global x;
a = 13;
x = 15;
w = 17;
. . .
def sub3():
nonlocal a;
a = 19;
b = 21;
z = 23;
. . .
. . .


 List all the variables, along with the program units where they are
declared, that are visible in the bodies of sub1, sub2, and sub3, assuming
static scoping is used.

Variable                       Where Declared
In Sub1:
a                                              Sub1
y                                              Sub1
z                                              Sub1
x                                              Main
In Sub2:
a                                              Sub2
x                                              Sub2
w                                             Sub2
y                                              Main
z                                              Main
In Sub3:
a                                              Sub3
b                                              Sub3
z                                              Sub3
w                                             Sub2
x                                              Sub2
y                                              Main


10. Consider the following C program:
void fun(void) {
int a, b, c; /* definition 1 */
. . .
while (. . .) {
int b, c, d; /*definition 2 */
. . . 1
while (. . .) {
int c, d, e; /* definition 3 */
. . . 2
}
. . . 3
}
. . . 4
}
For each of the four marked points in this function, list each visible variable,
along with the number of the definition statement that defines it.

Point 1: a =1, b = 2, c = 2, d = 2
Point 2: a =1, b = 2, c = 3, d = 3, e = 3
Point 3: a = 1, b = 2, c = 2, d = 2
Point 4: a = 1, b = 1, c = 1

Assignment #4

Source:

Concepts of Programming Languages, Robert W. Sebesta.

Chapter 4: Lexical and Syntax Analysis, page 199-201

By:
Name : Helena Natanael
NIM  : 1801380333

---

Review Question:

6. What is a state transition diagram?
A state transition diagram, or just state diagram, is a directed graph. The nodes of a state diagram are labeled with state names. The arcs are labeled with the input characters that cause the transitions among the states. An arc may also include actions the lexical analyzer must perform when the transition is taken.

7. Why are character classes used, rather than individual characters, for the letter and digit transitions of a state diagram for a lexical analyzer?
A lexical analyzer is interested only in determining that it is a name and is not concerned with which specific
name it happens to be. Therefore, we define a character class named LETTER for all 52 letters and use a single transition on the first letter of any name. 

8. What are the two distinct goals of syntax analysis?
There are two distinct goals of syntax analysis. 

First, the syntax analyzer must check the input program, whether it's syntactically correct or not, and if an error is found, the analyzer must create a diagnostic message. However, the syntax analyzer must create an error list because it's possible to find many errors during a single analysis of the input program. So when it finds an error, it saves the diagnostic message and go on checking. If it is not done well, error recovery may create more errors, or at least more error messages. 

Second, it has to produce a complete parse tree, or at least trace the structure of the complete parse tree, for syntactically correct input. The parse tree (or its trace) is used as the basis for translation.

9. Describe the differences between top-down and bottom-up parsers.
The difference is in the making of parsers. 

Top-down: the tree is built from the root downward to the leaves
Bottom-up: the tree is built from the leaves upward to the root.

10. Describe the parsing problem for a top-down parser.
I usually use the bottom-up parsers, and I rarely use top-down parser, because it takes more concern and focus to make it correctly, there's bigger chance of bad parsing or skipped leaves in top-down parser. It also would be confusing if it comes to bad grammar/ambiguous grammar.


Problem Set: 

6. 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 → AbB | bAc
A → Ab | aBB
B → Ac | cBb | c

a. aAcccbbc
S → AbB → aBBbB → aAcBbB → aAccBbbB → aAcccbbc

Phrases: aAcccbbc, aAcccb, Ac, ccb, c, c.

Simple Phrases: Ac, c, c

Handle: Ac

b. AbcaBccb
S → AbB → AbcBb → AbcAcb → AbcaBBcb → AbcaBccb

Phrases: AbcaBccb, caBccb, aBcc, aBc, c

Simple Phrases: c

Handle: c

c. baBcBbbc
S →  bAc → baBBc → baBcBbc → baBcBbbc

Phrases: baBcBbbc, aBcBbb, aBcBb, cBb.

Simple Phrases: cBb

Handle: cBb

7. Show a complete parse, including the parse stack contents, input string,
and action for the string id * (id + id), using the grammar and parse
table in Section 4.5.3.

8. Show a complete parse, including the parse stack contents, input string,
and action for the string (id + id) * id, using the grammar and parse
table in Section 4.5.3.

9. Write an EBNF rule that describes the while statement of Java or C++.
Write the recursive-descent subprogram in Java or C++ for this rule.
<while_stmt> -> WHILE ‘(‘ (<arith_expr> | <logic_expr>) ‘)’ <block> <block> -> <stmt> | ‘{‘ <stmt> {<stmt>} ‘}’

10. Write an EBNF rule that describes the for statement of Java or C++.
Write the recursive-descent subprogram in Java or C++ for this rule.
Assume the following non-terminals are given: <type>, <id>, <literal>, <assign>, <expr>, and <stmt_list>.
<for> -> for ‘(‘ [[<type>] <id> = <expr> {, [<type>] <id> = <expr>}] ; [<expr>] ; [<expr> {, <expr>}] ‘)’ ‘{‘ <stmt_list> ‘}’

Assignment #3

Source:

Concepts of Programming Languages, Robert W. Sebesta.

Chapter 3: Describing Syntax and Semantics, page 162-164

By:
Name : Helena Natanael
NIM  : 1801380333

---

Review Question:

6. Define a left-recursive grammar rule.
When a grammar rule has its left hand side (LHS) also appearing at the beginning of its right hand side (RHS), the rule is said to be left recursive. This left recursion specifies left associativity. 

7. What three extensions are common to most EBNFs?
Extended Backus-Naur Forms has three common extensions:

1. The first extension denotes an optional part of an right hand side (RHS), which is delimited by brackets. 2. The second extension is the use of braces in an RHS to indicate that the enclosed part can be repeated indefinitely or left out altogether. 
3. The third common extension deals with multiple-choice options. When a single element must be chosen from a group, the options are placed in parentheses and separated by the OR operator, |.

8. Distinguish between static and dynamic semantics.
The static semantics of a language is only indirectly related to the meaning of programs during execution; rather, it has to do with the legal forms of programs (syntax rather than semantics).

Dynamic semantics is a perspective on natural language semantics that emphasises the growth of information in time. It is an approach to meaning representation where pieces of text or discourse are viewed as instructions to update an existing context with new information, with an updated context as result.


9. What purpose do predicates serve in an attribute grammar?
An attribute grammar consists of a grammar, a set of attributes, a set of attribute computation functions, and a set of predicates, which together describe static semantics rules. So predicates is a part of attribute grammar which is without the predicates, there would be no attribute grammar.

10. What is the difference between a synthesized and an inherited attribute
The difference between Synthesized and Inherited attribute is :
Synthesized attributes are used to pass semantic information up a parse tree, in the other hand inherited attributes pass semantic information down and across a tree.


Problem Set:

6. Using the grammar in Example 3.2, show a parse tree and a leftmost derivation for each of the following statements:

Grammar in Example 3.2:
<assign> → <id> = <expr>
<id>       → A | B | C
<expr>   → <id> + <expr>
                   | <id> * <expr>
                   | ( <expr>

a. A = A * (B + (C * A))
Parse Tree:

Leftmost Derivation:
<assign> → <id> = <expr>
               → A = <expr>              
               → A = <id> * <expr> 
               → A = A * <expr> 
               → A = A * ( <expr> )
               → A = A * ( <id> + <expr> )
               → A = A * ( B + <expr>)  
               → A = A * ( B + (<expr>) )
               → A = A * ( B + (<id> * <expr>) )
               → A = A * ( B + ( C * <expr>) )              
               → A = A * ( B + ( C * <id>) )     
               → A = A * ( B + (C * A))



b. B = C * (A * C + B)
Parse Tree:

Leftmost Derivation:
<assign> → <id> = <expr>
               → B = <expr>              
               → B = <id> * <expr> 
               → B = C * <expr> 
               → B = C * ( <expr> )
               → B = C * ( <id> * <expr> )
               → B = C * ( A * <expr>) 
               → B = C * ( A * <id> + <expr> )
               → B = C * ( A *  C + <expr> )              
               → B = C * ( A *  C + <id> )     
               → B = C * ( A * C + B )


c. A = A * (B + (C))
Parse Tree:

Leftmost Derivation:
<assign> → <id> = <expr>
               → A = <expr>              
               → A = <id> * <expr> 
               → A = A * <expr> 
               → A = A * ( <expr> )
               → A = A * ( <id> + <expr> )
               → A = A * ( B + <expr>)  
               → A = A * ( B + (<expr>) )
               → A = A * ( B + (<id>) )
               → A = A * ( B + ( C ) )                


7. Using the grammar in Example 3.4, show a parse tree and a leftmost derivation for each of the following statements:

Grammar in Example 3.4:
<assign> → <id> = <expr>
<id>       → A | B | C
<expr>   → <expr> + <term>
                    | <term>
<term>   → <term> * <factor>
                    | <factor>
<factor> → ( <expr> )
                    | <id>

 a. A = ( A + B ) * C
Parse Tree:

Leftmost Derivation:
<assign> → <id> = <expr>
               → A = <expr>
               → A = <term>
               → A = <term> * <term>  
               → A = <factor> * <term>
               → A = (<expr>) * <term> 
               → A = (<expr> + <term>) * <term> 
               → A = (<term> + <term>) * <term>   
               → A = (<factor> + <term>) * <term>    
               → A = (<id> + <term>) * <term>    
               → A = ( A + <term>) * <term>   
               → A = ( A + <factor>) * <term>     
               → A = ( A + <id>) * <term>  
               → A = ( A + B ) * <term>    
               → A = ( A + B ) * <factor> 
               → A = ( A + B ) * <id> 
               → A = ( A + B ) * C


b. A = B + C + A
Parse Tree:

Leftmost Derivation:
<assign> → <id> = <expr>
               → A = <expr>
               → A = <expr> + <term>
               → A = <term> + <term>
               → A = <factor> + <term>
               → A = <id> + <term>
               → A = B + <term>
               → A = B + <term> + <factor>
               → A = B + <factor> + <factor>
               → A = B + <id> + <factor>
               → A = B + C + <factor>             
               → A = B + C + <id>
               → A = B + C + A


c. A = A * (B + C)
Parse Tree:

Leftmost Derivation:
<assign> → <id> = <expr>
               → A = <expr>
               → A = <term> 
               → A = <factor> * <term> 
               → A = <factor> * <factor>              
               → A = <id> * <factor> 
               → A = A * <factor> 
               → A = A * ( <expr> )
                → A = A * ( <expr> + <term> )
               → A = A * ( <term> + <term> )  
               → A = A * (  <factor> + <term> )
               → A = A * ( <id> + <term> ) 
               → A = A * ( B + <term> )
               → A = A * ( B + <factor> )              
               → A = A * ( B + <id> )     
               → A = A * ( B + C )

d. A = B * (C * (A + B))
Parse Tree:

Leftmost Derivation:
<assign> → <id> = <expr>             
               → A = <expr>
               → A = <term> 
               → A = <term> * <factor> 
               → A = <factor> * <factor> 
               → A = <id> * <factor> 
               → A = B * <factor>
               → A = B * ( <expr> )
               → A = B * ( <term>) 
               → A = B * ( <term> *  <factor>) 
               → A = B * ( <factor> *  <factor>) 
               → A = B * ( <id> *  <factor>) 
               → A = B * ( C *  <factor>) 
               → A = B * ( C * ( <expr> ) ) 
               → A = B * ( C * ( <expr> + <term> ) ) 
               → A = B * ( C * ( <term> + <term> ) ) 
               → A = B * ( C * ( <factor> + <term> ) ) 
               → A = B * ( C * ( <id> + <term> ) ) 
               → A = B * ( C * (A + <term> ) )
               → A = B * ( C * (A + <factor> ) )               
               → A = B * ( C * (A + <id> ) ) 
               → A = B * ( C * (A + B ) )

8. Prove that the following grammar is ambiguous:
<S> → <A>
<A> → <A> + <A> | <id>
<id> → a | b | c

The grammar is ambiguous because there's 2 different parse trees can be made from grammar above.

9. Modify the grammar of Example 3.4 to add a unary minus operator that
has higher precedence than either + or *.

<assign> → <id> = <expr>

<id>        → A | B | C

<expr>    → <expr> + <term>   

                     | <term>

                     | - <factor>

<term>    → <term>*<factor>

                     | <factor>

<factor>  → (<expr>)

                     | <id>

10. Describe, in English, the language defined by the following grammar:
<S> → <A> <B> <C>
<A> → a <A> | a
<B> → b <B> | b
<C> → c <C> | c

It means all sentences consisting of one or more a, then a is followed by one or more b and then also followed by one or more c.