Theory of Programming Language

Posted by Winnie Melda on October 4th, 2018

Chapter 3

Question 3.1

        i.            The number of built-in functions is specifically bound at language design time. However, it can increase by specific implementations.

      ii.            The variable declaration that corresponds to a particular reference is bound at compile time

    iii.            The maximum length of the character string in case there is a limit is bound at a language implementation time

    iv.            The referencing environment for a subroutine which is passed as a parameter is same as the environment at the declaration of subroutine

      v.            The address of a particular library function is bound by the linker in most of the systems. However, it may not be easily known until load time and run time in the systems performing dynamic linking.

    vi.            The total amount of space occupied by program code and data is bound at run time. Additionally, the amount of stack and heap space that is required will also depend on the output.

Question 3.2

        i.            Fortran 77 does not have a recursion and therefore, there is no more than one live instance of the local variables of a certain subroutine. Algol together with its descendants needs a stack to enable accommodation of multiple copies. The following is not going to work correctly with statically allocated local variables:

function sum(f, low, high) if low=high return f(low) else return f(low) + sum(f, low + 1, high)

      ii.            Algol and its descendants have a limitation in extent for local variables while lisp and its descendants should be allocated in the heap thus accommodating unlimited extent. The following is not likely to work well with stack-allocated variables:

function add_n(n) return {function (k) return n+k}

Question 3.3

        i.            Some different aspects of code generation might be delayed until link time to help in facilitating the improvement of whole code

      ii.            Local variables on Fortran 77 might be allocated on the stack instead of static memory. This will minimize imprint of memory and facilitate interoperability with standard tools.

Question 3.4

        i.            If procedure P declares a local variable name x in Ada, then a global variable with similar name x will be live but not in scope in the execution of P

      ii.            In C, a static variable declared within a function becomes live but not in scope when executed outside the function.

    iii.            In C++, the non-public fields of an object of the class C are live although not in scope when they are executed outside a method of C

Question 3.5

a)      94214

b)     

c)      A finds g by dereferencing its static link thus finding the sack frame of B. It finds B’s static link at an offset known statically within this frame. It then dereferences that to find the stack frame of main where it finds g again at an offset known statically.

Question 3.6

a)      The reverse_list routine lead to the production of a new list comprising of the nodes. Upon assigning of the return value back into L by Brad, he is bound to lose track of the nodes from the old list and will never reclaim them. The program has a memory leak. After several iterations of the main loop, Brad will exhaust the heap thus discontinuing the program.

b)      Although the call delete_list reclaims the old list of nodes successfully, it also reclaims widgets. The resultant reversed list comprises of dangling references. The dangling references refer to the locations within the heap that are likely to be used for the newly allocated data. The newly allocated data may also be corrupted because of the use of elements within the reversed list. Brad is lucky because he has not corrupted the heap. However, his widgets might be of the same size as list nodes. Without the help from Jane, Brad might have a lot of challenges as he tries to figure out why widgets have a spontaneous changing of value.

Question 3.7

        i.            The module-as-abstraction which is equivalent of the Figure 3.7 with header file stack.h

#define STACK_SIZE 100

Typedef in element;

extern void push (element);

extern element pop();

Implementation file stack.c;

#include

#include

#include “stack.h”

Typedef short stack_index;

Element s[STACK_SIZE];

Stack_index top = 0;

static void error (const char* err){

fprintf (stderr, “stack error: %s\n”, err);

exit(1);

}

void push (element elem) {

if (top ==STACK_SIZE) error (“overflow”);

else s[top++] = elem;

}

Element pop (){

If (top == 0) error (“underflow”);

Else return s[--top];

} 

Client file:

#include

#include “stack.h”

Int main (){

Element x, y;

x = 3;

push (x);

y = pop ();

printf (“y==%d\n”, y);

}

      ii.            The module-as-manager which is equivalent to Figure 3.8 with header file stack_manager.h

#define STACK_SIZE 100

typedef int element;

 typedef short stack_index;

typedef struct {

element s (STACK_SIZE);

stack_index top;

}stack

extern void init_stack (stack*);

extern void push (stack*, element);

extern element pop (stack*);

Implementation of file stack_manager.c:

#include

#include

#include “stack_manager.h”

Static void error (const char* err) {

Fprintf (stderr, “stack error: %s\n”, err);

exit (1);

}

extern void init_stack(stack* stk){

stk->top = 0;

}

extern void push (stack* stk, element elem){

if (stk ->top== STACK_SIZE) error (“overflow”);

else stk ->s[stk->top++] = elem;

}

extern element pop (stack* stk) {

if (stk - >top == 0) error (“underflow”);

else return stk - >s[--stk->top];

}

Client file

#include

#include “stack_manager.h”

Int main (){

Element x, y;

stack A, B;

init_stack (&A);

init_stack (&B);

x = 3;

push (&A, x);

push (&B, pop (&A));

y = pop (&B);

printf (“y == %d\n”, y);

Question 3.8  

• The private section of either a module header or a class declaration gives information which is required by the compiler so as to generate code needed for clients of the abstractions although it is not part of the interface semantically. There are two problems first of which it violates information hiding since it allows the writers of the client codes to access the abstraction even if they cannot use the abstraction. Secondly, it forces abstraction creator to think about and identify explicitly the extra information the compiler needs.
• According to the description of section 9.2.1, Java and C# employ an alternative approach thus dispense headers together. The abstraction creator engages in the identification of the semantically public aspects which define the interface. Then the compiler examines the full implementation to identify other needs.

Question 3.9

a)      In the given code, variables a, b, and c are live when the outer block is being executed. Variables d, e, and f are needed in the first nested block only. They can also overlap the space for g, h, and i. it requires a 24 bytes.

b)      During the compiling of a subroutine, the compiler is able to construct a tree where each of the nodes represents a block and is a child of the node representing the surrounding block. All the variables declared in the outermost blocks are then assigned locations when the subroutine space is beginning. All the variables in a nested block should be assigned locations after the variables of the surrounding block. Additionally, variable siblings also overlap.

Question 3.10

• Fortran 77 does not have recursion and therefore its call graphs are acyclic. Where two subroutines did not appear on the same path from the main in the graph, their local variables might not be needed at the same time. They may also share space.
• If the local variables are allocated by the compiler statically, a minimum-size allocation can be chosen by sorting the call graph topologically. The frame of the subroutine that can only be called from the main program is also placed at address 0. Later, the frame of the rest of the subroutines that can called by the subroutines whose frames already have locations assigned to them is placed at the first address which beyond the frames of the potential callers.

Question 3.11

• P, B, X, Q, R, A (R parameters), C (R parameters), and Z. The parameters and all the local variables of Q are no within the scope as well as the P’s parameter A

Question 3.12

(let ((a (lambda (n) 1))

(b(lambda (n) 2)))

(let ((a (lambda (n) (if (zero? n) 3 (b (- n 1)))))

(b (lambda (n) (if (zero? n) 4 (a (- n 1)))))

(list (a 5) (b 5)))

Chapter 7

Question 7.1

• It is a question of opinion. Name equivalence is an abstract concept when it is defined particularly in Ada. The concept allows the programmers to specify the exact types they should consider compatible and which should not be considered compatible instead of basing their distinction on whether the types have the same implementation. The main advantage of structural equivalence and why it is used in SR and ML is that it makes compatibility becomes an intrinsic property of types that can easily be assessed independent of the contexts in the types it declares. Other things are that it simplifies the implementation of the type checking for the modules compiled separately. It does not need any mechanisms for ensuring that the files are compiled by using the same type of shared declarations.  

Question 7.2

• All of the four arrays have equivalent structure. Under the name equivalence, array D is comprehensively with the rest of arrays. Under the strict name equivalence A and B they are also incompatible with array C. Under loose name equivalence A, B, and C, they are all mutually compatible.

Question 7.3

• No. It is cannot be said to be an alias. Line 1 represents a declaration that is not a definition. However, the definition occurs on the 4^th line. Variables x and y have the same type of definition and therefore, have the same type.

Question 7.4

• type person is record

name: string (1…10);

age: integer;

end record;

P, q : person

A, B : array (1…10) of integer;

Question 7.5

subtype lc_letter is character range ’a’..’z’;
function upper(l : lc_letter) return character is
uc_offset : constant integer :=
character’pos(’A’) - character’pos(’a’);
begin
return character’val(character’pos(l) + uc_offset);
end upper;

Question 7.6

• Var a : integer; b, c: real;

C : a+b;

Question 7.9

• The compiler will not be able to minimize the spaces devoted to the hole in which they are aligned while also keeping the fields aligned.

Question 7.10

UCASE      CSECT

USING UCASE, R 15

MVC UC, PG

MVC LC, PG

OC UC, = 16C’ ‘

NC LC, = 16X’BF’

XPRINT PG, L’ PG

XPRINT UC, L, UC

XPRINT LC, L’ LC

BR R14

PG       DC CL9’ alphaBETA

UC       DS CL (L’PG)

LC       DS CL (L’ PG)

            YREGS

             END UCASE

Question 7.11

• Alternative plan can be devised inspired by the stack frame layout. The problem that will be encountered is that heterogeneous data types will not be stored and manipulated together.

Question 7.13

• In C programming, restrict is a keyword commonly used in pointer declarations which is a declaration of intent which the programmer gives to the compiler. It says that for the time that the pointer is going to be alive, only the pointer itself or a value derived from the pointer directly such as pointer +1 will be used to help and access the object which it is pointing. This will limit the effects of pointer aliasing because it will have aided in optimization. In case the declaration of intent will not be allowed and the object accessed by the independent pointer, it will result into undefined behavior. Therefore, the use of restrict in C programming allows the non-obtuse C to achieve same performance as the same program written in Fortran.

Question 7.19

• Type B = record

y: pointer to A

y: real

type A = record

x: pointer to B

y: real

Question 7.20

double *a[n];  //array of n pointers to doubles

double (*b)[n]; //pointer to array of n doubles

double (*c[n])(); //array of n pointers to functions returning doubles

double (*())[n]; //function returning pointer to array of n doubles

Question 7.21

• Access types and the objects they are used in accessing are used in the creation of a dynamic data structures. They are not implemented as pointers as in other programming languages. Their access all types and aliased objects are implemented by creating dynamic data structures like the lists, trees, and graphs. Their implementation is going to interact with garbage collection through dereferencing.

Question 7.24

a)      What I understand is that when one encounters the suggestion that a certain garbage collected language needs to provide operations such as delete as a choice for optimization. This is enabled by the user deleting some of the objects that are not needed. Therefore, this action enables the programmer to save the garbage collector the need of having to find and reclaim the objects automatically and thus he improves the performance.

b)      Yes, it is a good idea that the programmer tenure the object so that the object will never be used again in being a candidate for reclamation.

Question 7.25

• This will be possible by implementation of hash functions which will help in the generation of a certain length output that then acts as the shortened reference to the original data. The elements will be mapped into a numerical value by use of some numerical mathematical function.

Chapter 8

Question 8.1

• There is no Referential Transparency in C. This means that the functions may not always have the same output for having the same parameters. There is a possibility that one can have math functions defined for an infinite set of inputs. However, the input of the programmer is finite in C functions. In C functions, the programmer can have a function that returns nothing but in math this is not possible.

Question 8.5

• There exist several possibilities. The standard calling sequence on the VAX helps in saving the registers in the stack below it calling the callee’s frame pointer. The bit mask in the callee’s code specifies the registers to be saved. Where the subroutine has several entries, the number of saved registers and therefore the offset between the fp and stack and allocated arguments may fail to be compile-time constant. The VAX helps in word-aligning the fp and sp as side effect of a call. Therefore, this helps in inserting 0-3 bytes of garbage inside the stack. However, it depends on the previous alignment at run time. Both the call and call instructions vary in how the arguments are located. Calls put them inside the stack while callg takes extra address specifier thus indicating their locations which is likely to be somewhere in the memory space. Non-stack arguments are not used on the VAX widely. However, one can imagine them saving some time for calls to the nonrecursive routines having large numbers of read only default parameters.

Question 8.7

• The programmer can tell the difference between a parameter that is a value and a parameter that is s reference to a temporary

Question 8.11

Public static void swap (Object a, Object b){

Object t = b;

b = a;

a = t;

}

Question 8.13

• Parameters are passed to the IDL system and user-written procedures and functions by either value or by reference. There are some differences between the two methods. Expressions , constants, system variables, and subscripted variables references are passed strictly by value while variables are strictly passed by reference

Question 8.16

• In statically typed languages, the addition of extra parameters would not be type safe to produce potentially unexpected results if there was occurrence of type mis-matching

Question 8.19

1. q = [1, 0, 1, 0]

score (q, doc 1) = 0.8974, score (q, doc2) = 0.6883, score (q, doc3) = 1.3015

Ranking: doc3, doc1, doc2

2. q = [0.4778, 0.6024, 0.4692, 0.4344]

score (q, doc1) = 0.6883, score (q, doc2) = 0.7975, score (q, doc3) = 0.7823

Ranking: doc2, doc3, doc1

Question 8.20

{

 ...

 Integer x = new Integer(1);

 System.out.println("x is " + x);

 ...

 }

 void addOne(Integer originalValue)

 {

value = new Integer(originalValue.intValue() + 1);

}

Question 8.22

• In most of language implementations, the activation records referring to different instances of foo might be occupying the same space within the stack. The local variable i will not be initialized and that will bring error in the program. However, if the stack space will not have been used for something else in the meantime, it will inherit a value from the previous instance of the routine. If the stack is going to be created from the space which is full of zeros by the operating system, and in case the space occupied by the activation of foo record will not have been used for anything else before the first time foo is called, the i might be made to start with a zero in its first iteration of the loop.

Question 8.24

• Every bar is a foo. Therefore, it will be tempting to have a thought that anything print_all is going to do to elements of a list<foo*> such as print them. It should do to the elements of a list<bar*>, too. But what if print_all inserts a new foo object into L. After the call has returns, the main program will remove an element from the LB thus obtaining erroneous behavior. This is because it will be expecting the object to be specifically of type bar. Types collectionand collection are not compatible regardless of any possibility of inheritance between T1 and T2

Sherry Roberts is the author of this paper. A senior editor at Melda Research in https://www.meldaresearch.com">already written essay if you need a similar paper you can place your order for https://researchpapers247.com/nursing-paper/">nursing writing services