Exam 2 Topics

Exam Date: Thursday, 24 April, 5-7PM

Example questions.

• You should expect prolog questions similar to the in-class problems. You will not be allowed to use your book, so you should have the built-in predicates like ! and fail memorized and should be able to create rules without reference to a book.
• You could get definitions of the major terms. E.g., "what does shallow binding mean?" or "what is unification?".
• Two mechanisms for implementing nonlocal references were described in class and in the textbook, static chains and displays. For the program below, provide the stack with ARs for each subprogram and show the static link. Use the AR format given in the book and in the slides in class.

program MAIN_2;
  var X : integer;
  procedure BIGSUB;
    var A, B, C : integer;
    procedure SUB1;
      var A, D : integer;
      begin { SUB1 }
      A := B + C;  <-----------------------1
      end;  { SUB1 }
    procedure SUB2(X : integer);
      var B, E : integer;
      procedure SUB3;
        var C, E : integer;
        begin { SUB3 }
        SUB1;
        E := B + A:   <--------------------2
        end; { SUB3 }
      begin { SUB2 }
      SUB3;
      A := D + E;  <-----------------------3
      end; { SUB2 }
    begin { BIGSUB }
    SUB2(7);
    end; { BIGSUB }
  begin
  BIGSUB;
  end. { MAIN_2 }




Call sequence for MAIN_2
   MAIN_2 calls BIGSUB
   BIGSUB calls SUB2
   SUB2 calls SUB3
   SUB3 calls SUB1

Your Stack with static links:

Give the references for each variable at the position in the program marked 1. In other words, what would the compiler put into the code so that the variable could be referenced at runtime. Assume that the chain-offset is used in the reference.

Now assume that subroutines are implemented using displays. Show what the display would look like when the code is executing at position 1.

Syntax Analysis (Chapter 4)

• Know what LR (bottom-up) parsers are and how they work.
• Be able to trace out the parsing of a sentence given a LR parse table.
• Be able to create a parse tree and then identify phrases, simple phrases, and handles.
• Be able to create the parse tree while performing bottom up parse with the parse table.

Names, Bindings, Type Checking, and Scopes (Chapter 5)

• Understand bindings

• Static and dynamic type binding.
• Binding vs Lifetime.
• Static variables, stack-dynamic variables, explicit heap-dynamic variables, implicit heap-dynamic variables.

• Scope. Static and dynamic. Blocks.
• Scope and Lifetime.

Subprograms (Chapter 9)

• Activation records. Know how they're formatted and used. Memorize the AR format given in the slides in class.
• Know the different models for parameter passing and how they're implemented: in, out, in/out.
• Know the different implemnetation models for parameter passing and how they're used: pass-by-value, pass-by-result, pass-by-value-result, pass-by-reference, pass-by-name.
• Understand how parameter passing is implemented using a run-time stack.
• You do not have to know how multidimensional arrays are passed as parameters.
• Know how procedures and functions are passed as parameters. Know the different ways of creating referencing environments for these procedures: shallow binding, deep binding, and ad hoc binding.
• Be able to pass functions as parameters in C and Scheme.
• You do not have to know about templates in C++.

Implementing Subprograms (Chapter 10)

• Know what activation records are and how they're implemented. How local variables are implemented on the stack, how parameters are passed. Memorize the AR format given in the slides in class.
• Understand how dynamic links are used in a stack.
• Understand how to do recursion using a runtime stack.
• Understand how nested subprograms are implemnted using a stack with static links.
• Understand and be able to use displays to store static links.
• Know how to implement dynamic scoping. Deep access and shallow access.

Logic Programming Languages (Chapter 16)

• Understand predicate calculus as we described it in class: propositions, terms, functors.
• Understand resolution and be able to demonstrate it.
• Understand what unification is and be able to demonstrate it.
• Be able to write Prolog databases (facts and rules) and goals.
• Be able to describe how Prolog performs unification and instantiation.
• Understand the difference between variables in Prolog and in other languages.
• Understand how Prolog does resolution and backtracking.
• Know what anonymous variables ("_"), conjunction (","), and disjunction (";") are in Prolog and how to use them in rules and goals.
• Be able to use structures in goals.
• Be able to write recursive rules in Prolog. Be able to turn recurive goals into tail recursive goals.
• Be able to write Prolog programs that do computation like the factorial example from the third prolog lecture slides.
• Be able to write Prolog rules that use compound goals. Example: the buy_car rule in the third prolog lecture slides.
• Be able to write Prolog programs that make decisions. For example, the temperature example from the second prolog lecture slides.
• Be able to write Prolog programs that involve multiple rules. For example, given a database of facts temps(city, temp1, temp2, temp3), and the rule howHot from the second prolog lecture slides, write a rule that determines the average temperature and returns how hot it is (e.g., very, pretty, etc.).
• Be able to manipulate lists in Prolog.
• Be able to use negation in Prolog rules and goals.
• Know what the fail and cut predicates are and how to use them in prolog.

Parsers

• You must understand the grammar from project 2 and be able to modify it. You do not have to memorize it.
• Be able to modify a parser in Scheme that implements the grammar given in Project 2.
• Know how all the functions given to you in project 2 (getToken, pushBack, error, last, and beginParse) work and be able to use them in scheme programs.

Last updated on 23 Apr 2008 by John Barr