Text Box: 0 00/ 1 10/ 2 05/ 3 15/ 4 05/ 5 05/ 6 10/ 7 15/ 8 15/ 9 10/ 10 10/ 100/ CMSC 331 Midterm Exam

Section 0201 – Oct 25, 2000

 

Name:         Williams Gates   

 

Student ID#:   666-66-6666

 

 

You will have seventy-five (75) minutes to complete this closed book exam.  We reserve the right to assign partial credit, and to deduct points for answers that are needlessly wordy. 

 

 

0. Logic (0)

 

Is “no” your answer to this question?

 

This is of course a variation of a famous logical paradox.  If you like these sorts of things, I can recommend any of the books by the logician Raymond Smullyan.  I just checked with Amazon and see that many are, unfortunately, out of print.  So, buy the ones that are still available while you can.  I highly recommend him.  Besides being a Math professor at NYU he’s also a magician.

 

1. Name that Language (10)

 

Answer the following questions, choosing your answers from the set {Lisp, Algol68, Fortran, C++, Smalltalk, Simula, Modula, Pascal, Snobol, Prolog, ML, Cobol, C, Ada, Perl, Tcl and Java}.  You may use an answer more than once and need not use all of the answers.

 

(a) FORTRAN What programming language has dominated scientific computing over the past 35 years?

 

(b) COBOL What programming language has dominated business applications over the past 35 years?

 

(c) LISP What programming language has dominated artificial intelligence programming over the past 35 years?

 

(d) ALGOL68  What language FIRST used orthogonality as a major design criterion?

 

(e) C  In what language is UNIX written?

 

(f) SIMULA  What language was the first to introduce some object-oriented concepts.

 

(g) ML What is a language that performs type inference?

 

(h)  JAVA  What language has the slogan "Write once, run anywhere"?

 

(i) SMALLTALK  Which language is considered to be the first fully object-oriented language?

 

(j) ADA  What language did the US Department of Defense try to mandate for use in all of its software?

 

2. Name that Paradigm (5)

 

Answer the following questions, choosing your answers from the set {Imperative, Denotational, Functional, Non-procedural, Constraint, Assembly, Object-oriented, Agent-based, Democratic, Republican}. You may use an answer more than once and need not use all of the answers.

 

(a) IMPERATIVE   What is the name of the category of programming languages whose structure is dictated by the von Neumann computer architecture?

 

(b) NON-PROCEDURAL  A paradigm that allows specification of what has to be computed rather than just how a computation is to be carried out.

 

(c) OBJECT-ORIENTED A paradigm incorporating encapsulation, inheritance, and dynamic type binding.

 

3. True/False (15)

 

1.      ___F__  One of the advantages of interpreted languages is their faster execution time compared to compiled languages.

2.      ___T__  If the grammar for a language  is ambiguous, then some valid program in that language has more than one parse tree.

3.      ___F__  BNF grammars do not allow left-recursive rules.

4.      ___T_  BNF grammars can be used for both language generation as well as language recognition.

5.      ___F__  Even though Java uses a garbage collector, there can still be memory leaks due to circular data structures that appear to be referenced even though they are not.

6.      ___T__  Dynamic type checking adds some execution-time overhead, but improves reliability of programs.

7.      ____T_  Attribute grammars can capture some features in a language that BNF grammars can not.

8.      ___F__  If two languages have different  non-terminal symbols, and productions, the languages can not be identical.

9.      ___F__  In an attribute grammar, a node's synthesized attributes are based on the values associated with that node's ancestors.

10.   __F___  Axiomatic semantics provide a good way of documenting the design of a program.

11.  __F___ Union types in Pascal are safer than those in Ada because each variant must have a discrimination field.

12.  __F___ One advantage the garbage collection technique over a reference counter scheme for automatic memory management is that it can handle negative reference counts.

13.  ___F__ One of the advantages of Java is that its pointers are represented as objects, making pointer arithmetic easier.

14.  __F___ A programming language is considered to be strongly typed if every variable must be associated with a single primitive data type.

15.  __T___ A union type is a type that can store different type values at different times during the execution of a program.

 

4. Scope and Lifetime (5)

 

What's the difference between scope and lifetime with regard to variable declarations?

 

A variables scope refers to the range of the program in which the variable can be referenced.  Its lifetime refers to the period of time during which it can be referenced.

 

5. Enumerated sets (5)

 

In a language like Pascal, where sets are built on enumeration types of fewer than 32 elements, how might sets be easily implemented?

 

The best representation for such small sets is as a “bit vector”.  A vector of 32 bits can be easily represented in many machines as a single word of memory.  Besides being compact, this representation allows the basic set operations (union, intersection, difference) to be implemented in single machine instructions that are found on most computers (e.g., bit-wise logical and). 

 

6. Grammars I (10)

 

Prove that the following BNF grammar is ambiguous by showing a string in the language defined by this grammar that has two different parse trees.   Assume that capital symbols are non-terminals and lower-case symbols are terminals and that S represents the start state.

 

S -> aaA

S -> aB
A -> bB

A -> a

B -> aA

B -> b

 

The string “aaa” is ambiguous with parse trees S(a a A(a)) and S(a B(a A(a)))

 

 

7. Grammars II (15)

 

Assume that Boolean expressions are built up from the following symbols:

 

Binary infix operators: AND, OR, IMPLIES

Unary prefix operator: NOT

Variables: a, b, c

Parentheses: ( )

 

NOT has a higher precedence than the other three operators, which all have the same precedence. To disambiguate expressions involving more than one binary operator, properly balanced parentheses must be used  (rather than an associativity convention). A Boolean expression may have but need not have parentheses around itself. Here are some sample legal Boolean expressions:

 

(NOT a AND NOT b) OR (NOT c IMPLIES a)

NOT a AND NOT c

NOT (a AND NOT c) OR b

(a IMPLIES b)

(NOT (a))

 

Here are some sample illegal Boolean expressions:

 

a OR b OR c

(NOT a) AND (NOT b) OR (NOT c)

NOT (a AND) NOT c

 

Write a grammar in BNF (or some form of extended BNF, if you prefer), which generates all Boolean expressions as defined above.

 

<exp>        ::=  <term> AND <term>

                         | <term> OR <term>

                         | <term> IMPLIES <term>

                         | <term>

<term>       ::=  NOT <term>

                         | ( <exp> )

                         | <var>

<var>        ::=  a | b | c

 

 

 

8. Variable Scope (15)

 

Consider the following code fragment in a new language currently under design called ALGORE, which has Pascal-like syntax except that all procedures have no formal parameters. The designers cannot decide whether to adopt dynamic or static scoping.

 

program test;

   var a, b: integer;

 

   procedure sub1;

     var a, c, e: integer;

   begin

     a := 6; c := 7; e := 8;

     ...         {position 3}

   end; {sub1}

 

   procedure sub2;

     var a, c, d: integer;

   begin

     a := 3; c := 4;  d := 5;

     ...         {position 2}

     sub1();

     ...

   end; {sub2}

 

begin

   a := 1; b := 2;

   ...           {position 1}

   sub2();

   ...

end. {test}

 

(a)    Determine what variables are visible at positions 1, 2, 3 and  what their values are (given the call sequence indicated) with static  scoping. (6)

(b)   Determine what variables are visible at positions 1, 2, 3 and  what their values are (given the call sequence indicated) with  dynamic scoping. (6)

 

        Position        Static Scoping                        Dynamic Scoping

1                a=1, b=2                                 a=1, b=2

2                a=3, b=2, c=4, d=5               a=3, b=2, c=4, d=5

3                a=6, b=2, c=7, e=8                a=6, b=2, c=7, d=5, e=8

 

(c)    You advise for static scoping in general. Why? (3)

 

The advantages of static scoping over dynamic scooping include: (1) We can do type checking at compile time, which allows us to find error sin programs earlier, (2) Generally, statically scoped languages execute quicker (at run-time, obviously), (3) While code of statically scoped languages can be confusing (more variables are often visible than one thinks), dynamically scoped languages produces even less readable code, since the scope of a variable can only be determined at run-time.

 

9. Java I (10)

 

What is the output of the following Java  program?  The program compiles and runs correctly as shown.

 

public class C1 {

    public C1() {System.out.println("Hello from C1");}

    public int v1() {return( 3 );}

    public int v2() {return( 1 );}

    static public void main(String[] args) {

        System.out.println("Hello from main");

        C3 x = new C3();

        C2 y = new C2();

        C1 z = new C1();

        System.out.println ( x.v1() );

        System.out.println ( y.v2() );

        System.out.println ( z.v1() );

        System.out.println ( x.v2() );

        System.out.println ( y.v1() );

        System.out.println ( z.v2() );

    }

}

 

class C2 extends C1 {

    public int v1() {return( 2 );}

    public int v2() {return( 4 );}

    public C2() {System.out.println("Hello from C2");}

}

 

class C3 extends C2 {

    public int v2() {return( 6 );}

    public C3() { System.out.println("Hello from C3");}

}

 

Hello from main

Hello from C1

Hello from C2

Hello from C3

Hello from C1

Hello from C2

Hello from C1

2

4

3

6

2

1Text Box: Write your output here

 

10. Java II (10)

 

What is the output of the following Java  program?  The program compiles and runs correctly as shown.

 

class Teacher {

    private String name;    // Teacher's name

    private int    size;    // Size of class

 

    public Teacher (String theName) { size = 0; name = theName; }

 

    public Teacher (int theSize, String theName) {this.setSize(theSize); name = theName;}

 

    public int getSize () {return size;}

    public int setSize (int n) { return size = n;}

 

    public void print(){System.out.println(name+" has "+size+" students.");}

 

    public void compare (Teacher theTeacher) {

        System.out.println (name + " says:");

        if (theTeacher.size>16)System.out.println("  You have many students.");

        if (size < 17) System.out.println ("  I don't have many students.");

        if (theTeacher.size<size)

            System.out.println ("  I have more than you.");

        else if (theTeacher.size == size)

            System.out.println ("  We have the same.");

Text Box: Write your output here         else

            System.out.println

             ("  I have fewer than you.");

    }

 

    public void enroll () {size++;}

    public void enroll (int n) {

      size = size+n;

    }

}

 

public class School {

    public static void main(String args[]) {

        Teacher one = new Teacher(18, "Sue");

        one.print();

        Teacher two = new Teacher("Ed");

        two.print();

        two.enroll(16);

        two.print();

 

        one.compare (two);

        two.compare (one);

 

        one.enroll (); one.print ();

 

        one.enroll (3); one.print ();

 

        two = one;

        one.enroll();

        two.enroll();

        one.print ();

        two.print ();

 

    } }

 

 

Sue has 18 students.

Ed has 0 students.

Ed has 16 students.

Sue says:

  I have more than you.

Ed says:

  You have many students.

  I don't have many students.

  I have fewer than you.

Sue has 19 students.

Sue has 22 students.

Sue has 24 students.

Sue has 24 students.