Concepts of Programming Language: Chapter 16

Yay last chapter! And that concludes T0152 assignment complete!

Taken from Robert Sebesta’s “Concepts of Programming Language” chapter 16 (yay, last chapter! ^^V) for T0152 assignment

Review: 33% of 25 (rounded down to 8) and 33% of 10 (rounded down to 3)

Review

1. What are the three primary uses of symbolic logic in formal logic?

They are used to:

  • Express propositions
  • Express the relationships between propositions
  • Describe how new propositions can be inferred from other propositions that are assumed to be true.

2. What are the two parts of a compound term?

One of them is functor, which is the function symbol tha tnames the relation, and the other one is an ordered list of parameters, which together represent an element of the relation.

4. What is the general form of a proposition in a clausal form?

That is B1 U B2 U … U Bn ⊂ A1 ∩ A2 ∩ … ∩ An

5. What are antecedents? Consequents?

Antecedents are the right side of clausal form propositions, whereas consequents are the left side of clausal form propositions, because it is the consequence of the truth of the antecedent.

7. What are the forms of Horn clauses?

There are two forms: They have either a single atomic proposition on the left side or an empty left side.

8. What is the basic concept of declarative semantics?

The basic concept of declarative semantics is there is a simple way to determine the meaning of each statement, and it does not depend on how the statement might be used to solve a problem.

11. What is an uninstantiated variable?

An uninstantiated variable is a variable that has not been assigned a value.

13. What is a conjunction?

A conjunction is a container of multiple terms that are separated by logical AND operations.

Problemset

1. “All predicate calculus propositions can be algorithmically converted to clausal form”. Is this statement true or false? Explain.

In my opinion, it’s true, because Nillson (1971) gives proof that this can be done along with one simple conversion algorithm for doing such thing.

2. Describe how a logic programming language is different from a general programming language.

Logical programming language uses a form of symbolic logic as a programming language, unlike other general programming language.  Languages based on symbolic logic are called logic programming languages, or declarative languages.

8. Critically comment on the following statement : “ Logic programs are nonprocedural”.

I think it’s true, since logical programs use lots of different processes based on its conditions. If a certain logical requirement is true, then a program will execute the corresponding process, instead of procedurally executing the statements.

 

Concepts of Programming Language: Chapter 15

Taken from Robert Sebesta’s “Concepts of Programming Language” chapter 15 for T0152 assignment.

Review: 25% of 50 (rounded down to 12) and Problemset: 33% of 10 (rounded down to 3)

Review

1. Define functional form, simple list, bound variable and referential transparency.

Functional form is one that either takes one or more functions as parameters or yields a function as its result. Simple list is a list that does not include sublist. Bound variable a bound variable is a variable which never changes in the expression after being bound to an actual parameter value at the time evaluation of the lambda expressions begin. Referential transparency is a state where execution of function always produces the same result when given the same parameters.

2. What does a lambda expression specify ?

A lambda expression specifies parameters and the mapping of a function.

3. What data types were parts of the original LISP ?

Atoms and list were those data types.

4. In what common data structure are LISP lists normally stored ?

LISP lists are stored as linked list structure in which each node has two pointers.

5. Explain why QUOTE is needed for a parameter that is a data list.

QUOTE is needed for a parameter that is a data list to return lists or atoms without changing them.

6. What is a simple list ?

A simple list is a list that does not include a sublist.

8. What are the three parameters to IF ?

The three parameters to IF are predicate expression, then expression, and else expression.

11. What are two forms of DEFINE ?

One form of DEFINE binds a name to value of an expression, and the other binds lambda expression to a name.

29. What is a curried function ?

A curried function is a function that takes multiple parameters.

30. What does partial evaluation mean ?

The function is evaluated with actual parameters for one or more of the leftmost formal parameters.

 32. What is the use of the evaluation environment table?

A table called the evaluation environment stores the names of all implicitly and explicitly declared identifiers in a program, along with their types. This is like a run-time symbol table.

33. Explain the process of currying.

The process of currying replaces a function with more than one parameter with a function with one parameter that returns a function that takes the other parameters of the initial function.

Problemset

7.   What features make F# unique when compared to other languages?

F# has a full-featured IDE, an extensive library of utilities that supports imperative, object-oriented, and functional programming, and has interoperability with a collection of nonfunctional languages. F# includes a variety of data types. Among these are tuples, like those of Python and the functional languages ML and Haskell, lists, discriminated unions, an expansion of ML’s unions, and records, like those of ML, which are like tuples except the components are named. F# has both mutable and immutable arrays.

8. How is the functional operator pipeline (|>) used in F#?

The pipeline operator is a binary operator that sends the value of its left operand, which is an expression, to the last parameter of the function call, which is the right operand. It is used to chain together function calls while flowing the data being processed to each call.

9. What does the following Scheme function do ?
(define (y s list)
(cond
((null? Lis) ‘ () )
((equal? S (car lis)) lis)
(else (y s (cdr lis)))
))
y returns the given list with leading elements removed up to but not including the first occurrence of the first given parameter.

 

Concepts of Programming Language: Chapter 14

Taken from Robert Sebesta’s “Concepts of Programming Language” chapter 14 for T0152 Assignment

Review: 25% of 42 (rounded down to 10) and Problemset: 25% of 14 (rounded down to 3)

Review

1. Define exception, exception handler, raising an exception, disabling an exception, continuation, finalization, and built-in exception.

Exception is any unusual event, erroneous or not, that is detectable by either hardware or software and that may require special processing. Exception handler is  a code unit which processes an exception. Raising an exception occurs when a event associated with an exception occurs. Disabling an exception means ignoring a certain hardware-detectable exceptions. Continuation is control transfer to somewhere in the program outside of the handler code or program might terminate. Finalization is ability to complete some computation regardless of how subprogram execution terminates. Built-in exception is exception that is not made by the user, but rather comes as default.

3. What are the advantages of having support for exception handling built in to a language ?

Without built-in exception handling, the code to detect error condition can be a clutter to the program. Existence of built-in exception handling would simplify a source program.

4. Give an example of hardware-detectable execution.

One of the example of hardware-detectable execution is division by zero.

6. What is exception propagation in Ada ?

Exception propagation in Ada is powerful tool for constructing more reliable software systems.

8. Where does execution continue after an exception is handled in Ada ?

Control simply continues after the exception clause.

10. What are the four exceptions defined in the Standard package of Ada ?

The four exceptions defined in the Standard package of Ada are Constraint_Error, Program_Error, Storage_Error, and Tasking_Error.

11. Are there any predefined exceptions in Ada ?

Yes, there are some predefined exceptions in Ada. For instance, Ada.Text_IO defines the End_Error exception.

12. What is the use of Suppress pragma in Ada ?
Suppress pragma in Ada is used for run-time checks that are parts of built-in exceptions can be disabled in Ada programs

13. Describe three problems with Ada’s exception handling.

The propagation model, which allows exceptions to be propagated to an outer scope in which the exception is not visible, inadequacy of exception handling for tasks, and exception handling was not extended to deal with new constructs in Ada 95.

30.  In which version were assertions added to Java?

Assertions were added to Java in version 1.4.

31. What is the use of the assert statement?

The assert statement is used for defensive programming. A program may be written with many assert statements, which ensure that the program’s computation is on track to produce correct results.

Problemset

1. What mechanism did early programming languages provide to detect or attempt to deal with errors?

Early programming languages were designed and implemented in such a way that the user program could neither detect nor attempt to deal with such errors. In these languages, the occurrence of such an error simply causes the program to be terminated and control to be transferred to the operating system.

2. Describe the approach for the detection of subscript range errors used in C and Java.

In C subscript ranges are not checked. Java compilers usually generate code to check the correctness of every subscript expression. If any exception generates, then an unchecked exception is thrown.

6. In languages without exception-handling facilities, we could send an error-handling procedure as parameter to each procedure that can detect errors than must be handled. What disadvantages are there to this method?

There are several disadvantages of sending error handling subprograms to other subprograms. One is that it may be necessary to send several error handlers to some subprograms, greatly complicating both the writing and execution of calls. Another is that there is no method of propagating exceptions, meaning that they must all be handled locally. This complicates exception handling, because it requires more attention to handling in more places.

Concepts of Programming Language: Chapter 13

Taken from Robert Sebesta’s book “Concepts of Programming Language” chapter 13 for T0152 assignment

Review: 25% of 63 (rounded down to 15) and Problemset: 33% of 10 (rounded down to 3)

Review

1. What are the three possible levels of concurrency in programs?

They are Instruction level, statement level, and unit level.

2. Describe the logical architecture of an SIMD computer.

In an SIMD computer, each processor have its own local memory. Because all of the processors, except the controller, execute the same instructions at the same time, no synchronization is required in the software.

4. What level of program concurrency is best supported by SIMD computers?

SIMD computers best support instruction concurrency level.

5. What level of program concurrency is best supported by MIMD computers?

MIMD computers best support unit concurrency level.

7. What is the difference between physical and logical conccurency?

Physical concurrency is when it is assumed that if more than one processor is available, several program units from the same program literally execute simultaneously. Logical concurrency is assuming multiple processors can execute simultaneously while the actual execution is taking place in a single processor.

8. What is the work of  a scheduler?

Scheduler manages the share of processors among tasks.

9. Give some examples of languages which can be used for synchronization.

They are Ada 95, Java, C#, F#, Python and Ruby.

10. When is a task in a blocked state?

A task in blocked state is when a task that is blocked has been running, but that execution was interrupted by one of several different events, the most common of which is an input or output operation.

21. What is a binary semaphore? What is a counting semaphore?

Binary semaphore is a semaphore that requires only a binary-valued counter, like the one used to provide competition synchronization. Counting semaphore is semaphore which allow an arbitrary resource count.

24. In what three common languages can monitors be implemented?

Monitors can be implemented in Ada, Java, and C#.

30. What is the purpose of Ada terminate clause?

Ada terminate clause is a special statement selected only when it’s pen and no other accept clause is open. Ada terminate clause, if selected, means that the task is finished with its job but is not yet terminated.

53. What is different about C#’s Sleep method, relative to Java’s sleep?

C#’s Sleep method doesn’t raise any exceptions, so it neet not be called in a try block, unlike Java’s sleep.

55. What is Conccurent ML?

Conccurent ML is an extension to ML that includes a form of threads and a form of synchronous message passing to support conccurency, and the language is completely described in Reppy (1999).

56. What is the use of the spawn primitive of CML?

A thread is created in CML using the spawn primitive, which functions as its parameter.

58. What is the use of the DISTRIBUTE and ALIGN specifications in HPC?

DISTRIBUTE and ALIGN specifications in HPC are used to provide information to the compiler on machines that do not share memory, that is, each processor has its own memory.

Problemset

1. Explain clearly why a race condition can create problems for a system.

Because two or more tasks are racing to use the shared resource and the behavior of the program depends on which task arrives first (and wins the race). The importance of competition synchronization should now be clear.

2. What are the different ways to handle deadlock?

When deadlock occurs, assuming that only two program units are causing the deadlock, one of the involved program units should be gracefully terminated, thereby allowed the other to continue.

3. Busy waiting is a method whereby a task waits for a given event by continuously checking for that event to occur. What is the main problem with this approach ?
A continuous check might mean a deadlock for a task, where it does something that does not has a direct impact on the program unless the specified event happens. It does consume extra processor capability. A better way to do this might be executing the same task when an event occurs, instead of running it first and make it waiting and continuously wasting CPU capability.

Concepts of Programming Language: Chapter 12

Taken from Robert Sebesta’s book “Concepts of Programming Language” chapter 12 for T0152 assignment

Review: 25% of 52 (exactly 13) and Problemset: 25% of 28 (exactly 7)

1. Name two functional languages that support object-oriented programming.

Two of some functional languages that support object-oriented programming are CLOS and OCaml.

3. What is advantage of inheritance?

Inheritance gives solution to both the modification problem posed by abstract data type reuse and the program organization problem. Furthermore, it provides a framework for the definition of hierarchies of related classes that can reflect the descendant relationships in the problem space.

4. What is message protocol?

Message protocol is the entire collection of methods of an object.

7. What is dynamic dispatch?

Dynamic dispatch is dynamic binding of messages to method definitions.

12. From where are Smalltalk objects allocated?

Smalltalk objects are allocated from the heap and are referenced through reference variables, which are implicitly dereferenced.

15. What kind of inheritance, single or multiple, does Smalltalk support?

Smalltalk supports single inheritance, it doesn’t support multiple inheritance.

16. What are the two most important effects that Smalltalk has had on computing?

The two most important effects are the advancement of object-oriented programming  and the integrated use of windows, mouse-pointing devices, pop-up and pull-down menus which are greatly used in softwares nowadays.

19. How are C++ heap-allocated objects deallocated?

C++ heap-allocated objects are deallocated with destructor.

23. What are the differences between private and public derivations in C++?

The public and protected members of a base class are also public and protected respectively in public-derived class. Meanwhile, in a private-derived class, all public and protected members of the base class are private.

33. What is the purpose of Objective-C category?

The purpose of an Objective-C category is to add certain functionalities to different classes and also try to provide some of the benefits of multiple inheritance, without the naming collisions that could occur if modules did not require module names on their functions.

38. What is boxing?

Boxing is primitive values in Java 5.0+ which is implicitly coerced when they are put in object context. This coercion converts the primitive value to an object of the wrapper class of the primitive value’s type.

39. How are Java objects deallocated?

Java objects are deallocated by implicitly calling a finalize method when the garbage collector is about to reclaim the storage occupied by the object.

42. Under what circumstances is a Java method call statically bound to a method?

Java method call is statically bound to a method when the called method has been defined as final, in which case it cannot be overridden and all bindings are static.

Problemset

1. What important part of support for inheritance is missing in Java?

Java doesn’t support the private and protected derivations of C++. One can think that Java designers believed that subclasses should be subtypes, which they are not when both private and protected derivations are supported.

2. In what ways can “compatible” be defined for the relationship between an overridden method and the overriding method?

In ways of its formal definition, the parameters, and return types.

7. What is one programming situation where multiple inheritance has a significant disadvantage over interfaces?

A situation when there are two classes derived from a common parent and they have a child.

10. Explain one advantage of inheritance.

Inheritance offers the reuse of the abstract data type and provides framework for the definition of hierarchies of related classes that can reflect descendant relationships in the problem space.

12. Compare inheritance and nested class in C++. Which of these supports an is-a relationship?

Inheritance is when one child class inherits the members of its parent class. Nested class is a class declared entirely within the body of another class or interface. The Inheritance supports an is-a relationship.

17. What are the different options for object destruction in Java?

There is no explicit deallocation operator, but only a finalize method is implicitly called when the garbage collector is about to reclaim the storage occupied by the object.

25. Study and explain private and public modifiers in C++. How do these modifiers differ in C#?

C++ includes both classes and structs, which only differ in default access modifier. Class has a default of private, while struct has public one. C# has structs, but they are, in instance, lightweight classes which can have constructors, properties, methods, and data fields implementable to interfaces, but do not support inheritance.

Concepts of Programming Language: Chapter 11

Taken from Robert Sebesta’s book “Concepts of Programming Language” chapter 11 for T0152 assignment

Review: 33% of 48 (exactly 16) and Problemset: 25% of 19 (rounded down to 4)

Review

1. What are the two kinds of abstractions in programming language?

Two kinds of abstractions in programming language is process abstraction and data abstraction.

2. Define abstract data type.

Data type that satisfies the following conditions:

  • The representation of objects of the type is hidden from the program units that use the type, so the only direct operations possible on those objects are those provided in the type’s definition.
  • The declarations of the type and the protocols of the operations on objects of the type, which provide the type’s interface, are contained in a single syntactic unit. The type’s interface does not depend on the representation of the objects or the implementation of the operations. Also, other program units are allowed to create variables of the defined type.

9. What is in an Ada package specification? What about a body package?

An Ada package specification has interface of the encapsulation and even more. Meanwhile, body package has implementation of most, if not all, of the entities naemd in the associated package specification.

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

It makes the names defined in external packages visible.

11. What is the use of the Ada use clause?

It eliminates the need for explicit qualification of the references to entities from the named package.

12. What is the fundamental difference between a C++ class and an Ada package?

C++ class must be accessed from an instance of itself, whereas Ada packages can be accessed directly.

13. From where are C++ objects allocated?

C++ objects are allocated from the heap.

15. What is the purpose of C++ destructor?

It serves as a deallocator for C++object from the heap, while functionally, destructor serves a debugging aid, in which case they simply display or print the values of some or all object’s data members before those members are deallocated.

16. What are the legal return types of a destructor?

Destructors neither have return types nor use return statements.

22. What is the use of @private and @public derivatives?

They are used to specify the access levels of the instance variables in a class definition. Similar to the reserved words private and public in C++.

23. When are constructors implicitly called in Objective-C?

Constructors in Objective-C are implicitly called after the object is created through the calling of alloc.

26. Why does Java not have destructors?

Because Java has an implicit garbage collection which stores all objects which was supposed to be destroyed.

27. Where are all Java methods defined?

They are all defined completely in a class.

37. What is the name of all Ruby constructors?

Constructors in Ruby are named as initialize.

43. What is a C++ namespace, and what is its purpose?

A namespace is a container for a set of identifiers and allows the disambiguation of homonym identifiers residing in different namespaces. The purpose is to help programs manage the problem of global namespace.

45. Describe a .NET assembly.

.NET assembly is a .NET applications appearing as single dynamic link library (.dll files) or executable files (.exe). An assembly defines a module, which can be separately developed and include several components.

Problemset

4. What are the advantages of the nonpointer concept in Java?

Any task that would require arrays, structures, and pointers in C can be more easil and reliably performed by declaring objects and arrays of objects. Instead of using complex pointer manipulation, arrays are accessed by arithmetic indices. The Java runtime system checks all array indexing to make sure indices are within bounds of array. No more dangling pointers and trashing of memory in Java anymore.

9. What happens if the constructor is absent in Java and C++?

The object cannot be initialized in user’s own way, but since Java and C++ classes have default constructor, it is called instead.

11. Why is the destructor of C# rarely used?

Because C# also has its own garbage collection method, similar to those in Java.

12. How are classes in Ruby made dynamic?

Classes in Ruby are made dynamic in the sense that members can be added anytime. This is done by including additional class definitions specifying new members. In Ruby, built-in class of language can be extended.

 

Concepts of Programming Language: Chapter 10

Taken from Robert Sebesta’s book “Concepts of Programming Language” chapter 10 for T0152 assignment

Review: 33% of 19 (rounded down to 6) and Problemset: 33% of 12 (exactly 4)

 

Review

2. Which of the caller or callee saves execution status information?

Status information can be saved by either caller or callee.

4. What is the task of a linker?

Task of a linker is to find the files that contain the translated subprograms referenced in that program and load them into memory. Then, the linker must set the target addresses of all calls to those subprograms in the main program to the entry addresses of those subprograms.

6. What is the difference between an activation record and an activation record instance?

By definition, activation record is the format or layout of the noncode program of a subprogram, named so because the data it describes are relevant only during activation. Activation record instance, on the other hand, is a concrete example of an activation record, a collection data in the form of activation record.

8. What kind of machines often use registers to pass parameters?

Usually, RISC machines use registers to pass parameters.

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. A static depth is an integer indicating how deep the static chain is nested in the outermost scope. Nesting_depth and chain_offset are somewhat similar, that is, the difference between the static_depth of the subprogram containing the reference to a certain variable and the static_depth of the subprogram containing the declaration of that certain variable.

15. Explain two methods of implementing blocks.

  • Blocks can be implemented using the static-chain process for implementing nested subprograms, so blocks in this case are treated as parameter-less subprograms that are always called from the same place in the program.
  • Another way is to implement block in a different and somewhat simpler and more efficient way. The maximum amount of storage required for block variables at any time during the exaction of program can be statically determined, because block are entered and exited in strictly textual order. Since offsets for all block variables can be statically computed, block variables can be addressed exactly as if they were local variables.

19. Compare the efficiency of deep access method to that of the shallow access method, in terms of both calls and nonlocal accesses.

The deep access methods provides fast subprogram linkage, but references to non local, and it’s very costly when it comes to non locals accessed with long call chain. Shallow access methods, however, provide faster references to non locals, but more costly in subprogram linkage.

Problemset

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 previous activation?

A local variable can retain the value of previous activation when declared as static. Static modifiers in Java are history-sensitive.

7. It is stated in this chapter that when a 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 comparison on names. Design an alternative to these string comparisons that would be faster.

Use an approach of auxillary data structure, the so-called display, or perhaps, try to write variables as integers which act like an array. Upon activation, it will compare 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.

The target of every goto in a program could be represented as an address and a nesting_depth, where nesting_depth is the difference between the nesting level of the procedure that contains the goto and that of the procedure containing the target. 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?

The nesting of scopes is known at compile time. So, the compiler can determine not only that a reference is nonlocal, but also the length of the static chain that must be followed to reach the activation records instance that contains the nonlocal object.