CSC123/252 Midterm Study Guide (Spring 2021)
With Practice Problems
Topics of focus:
1. No direct questions on lambda calculus but you need to understand how
lambda terms appear in scheme, perl, and to what extend can they be
represented in C.
2. Functional programming in C/Perl.
You need to be able to understand and analyze Scheme, C and Perl
programs. However, when I ask you to write code you can use any of
these languages. You'll be asked to follow certain restrictions in
coding, as on the first two programming assignments.
Don't forget to study the following mechanisms and concepts:
*Limitations to pure functional programming in C
*Tail versus non-tail recursive programs.
*Functions that are defined within other functions.
*Higher-order functions that take other functions as arguments and
possibly return functions (map, fold, howmany, etc...).
*Study how this is done in Scheme, Perl, as well as C.
3. The difference between static (lexical) and dynamic scoping of
variables. Do not confuse this topic with static vs dynamic
dispatch with respect to inheritance, or with other uses of "static"
and "dynamic". They're not directly related.
EVERY YEAR THERE ARE PEOPLE WHO GET THESE TWO CONCEPTS CONFUSED. SO
PLEASE REMEMBER TO STUDY THIS DIFFERENCE. NO MERCY POINTS!
Static vs dynamic scoping is a major topic to study carefully.
4. Closures and objects. How assignment (mutation) affects the nature of
programming. What is a closure (read the handout on "modularity,
objects and state"). Study the scheme/perl bank account
program and assignment. Study the handout, assignments, and
examples I did in class (as well as video lectures for Perl).
Also see the sample problems below.
5. Fundamental characteristics of inheritance and oop. static versus
dynamic dispatch, multiple inheritance issues, etc.
6. Inheritance in C# - understand the *purpose* as well as the mechanics
of dynamic dispatch. Know the consequences of the keywords "virtual",
"override" and "new" with respect to inheritance. Understand
when and where dynamic dispatch occurs, and the difference between
dynamic dispatch (overriding) and static overloading.
*The Visitor Design pattern. Study the EXPRESSION TREE programs in C#.
7. Type safety and type casting, including how they differ in C/C++ and Java/C#
8. Generics in C++, Java and C# and how they differ
8b. Covariant and Contravariant types, especially in C#
Practice Problems (Sample solutions to be posted)
---
1. What is the purpose of "bless" in Perl?
2. The following function in C computes 2**n (2 to the nth power) in
log(n) steps by binary factorization on n.
int pw2(unsigned int n)
{
int ax = 1; // accumulator
factor = 2; // start with 2**1 = 2
while (n>0)
{
if (n%2==1) ax *= factor;
n = n/2; // shift over next bit
factor = factor * factor; // only need 2**2, 2**4, 2**8, 2**16, etc...
}
return ax;
}
Rewrite the function in a purely functional style, without loops,
without destructive assignment and with a tail-recursive function
wrapped inside a larger function.
3. Consider the following Scheme/perl program:
(define (fold f identity L)
( if (null? L) identity (f (car L) (fold f identity (cdr L)))))
sub fold
{
my ($f,$identity,@L) = @_;
if (@L==()) {$identity}
else { my ($head,@tail) = @L;
$f->($head,fold($f,$identity,@tail));
}
}
a. Explain what this function does. Give an example of how to call it
and what result you can expect.
4. What is the difference between static and dynamic scoping? Why
is static scoping almost always used?
Determine the output of the following program and explain why:
my $x = 1;
sub f
{ $x }
{
my $x = 2;
print f();
}
What would be result of changing my to local?
4.2 I may also ask a question like the following:
Suppose you're shown a new language that has C-style syntax
int x = 1;
void f() { print(x); }
int main()
{ int x = 2;
f();
}
Explain how you would use this program to determine if the language
uses static or dynamic scoping.
4.3 Even harder variant of scoping question: show how to emulate dynamic
scoping using static scoping (in any language)
5. What is a closure? Write a scheme/perl closure function that takes
no arguments, but which returns 2 the first time it's called, 4 the
second time it's called, 8 the third time, 16 the fourth time, and so
on. That is,
print f() # prints 2
print f() # prints 4, etc..
6. Given the following class in C++, write the equivalent in Scheme or Perl.
You must use the closure method for implementing objects (no perl packages).
Also write code that would be equivalent to the main function -
that is, show how to create and use the objects.
hint: you'll need to create a function to return the ghz value, because
"private" in C++/Java/C# only gives class-level protection.
#include<iostream>
#include<string>
using namespace std;
class pc // objects that represent personal computers
{
private:
string cpu; // cpu type
double ghz; // cpu speed
double gigs; // memory in gigabytes
double teras; // hard drive capacity in terabytes
public:
pc(string c, double g, double r, double d) // constructor
{ cpu = c; ghz = g; gigs = r; teras = d; }
virtual void upgrade() // increase memory and speed
{ gigs = gigs*2; ghz = ghz + ghz/2; }
virtual int fasterthan(pc *otherpc) //in C++, int is same as boolean
{ return ghz > otherpc->ghz; }
}; // class pc
int main()
{
pc *newpc, *oldpc;
oldpc = new pc("i7",2.0,1,0.5);
newpc = new pc("core i9",3.8,16,2.0);
oldpc->upgrade();
if (newpc->fasterthan(oldpc)) cout << "newpc is faster\n";
else cout << "newpc isn't very fast\n";
}
*** Note that A->B is equivalent to A.B in C#/Java.
8. Determine the output of the following C# program and explain why:
(I suggest you run it to see if you're right!)
using System;
class superclass
{ private int x = 1;
protected static int y = 1;
public void f()
{ Console.WriteLine("I'm the f in superclass\n"); }
public virtual void g()
{ Console.WriteLine("I'm the g in superclass\n"); }
}
class subclass : superclass
{ public new int x = 1;
public new void f() // static override
{ Console.WriteLine("I'm the f in subclass\n"); }
public override void g() // dynamic override
{ x++;
y++;
Console.WriteLine("x is " + x + " and y is " + y);
}
}
public class goodquestion
{
public static void h(string x) { Console.WriteLine("x is a string!");}
public static void h(object x) { Console.WriteLine("x is an object!"); }
public static void Main(string[] args)
{
superclass A;
subclass B1;
A = new subclass();
B1 = new subclass();
A.f();
A.g();
B1.f();
B1 = (subclass)A;
B1.f();
object x = "abcd";
h(x);
}
}
8.2 can you write code to call the superclass.g() function?:
9a. Assume that in the visitor pattern, the visitee classes are
A, B, and C. Write the interfaces for the abstract visitee and
the abstract visitor.
9b. Show how the accept function of the visitor pattern should be
implemented (write the function).
9c. Would the visitor pattern still work without the ability to overload
the visit function inside each visitor?
10. Compare the following implementations of polymorphic linked lists:
class list
{
object head;
list tail;
}
class list<A>
{
A head;
list<A> tail;
}
What are the advantages of using one form instead of another?
11. Describe what will happen with the following C# segments of code, in terms
of any compiler errors, or runtime errors, and EXPLAIN WHY
// assume using System; and using System.Collections.Generic;
a. object[] A = new string[10];
A[0] = 1; // 1 is not a string but it's an object
b. List<object> B = new List<string>(); // equivalent to ArrayList in java
12. Determine if the following program will compile and run, and EXPLAIN WHY.
using System;
interface I<T>
{
int f(T other);
}
class A : I<A>
{
protected int x = 2;
public int f(A other) { return x-other.x; }
}
class B : A
{
double y;
public B(double z) {y=z;}
}
public class hardquestion
{
public static void Main()
{ I<B> x = new B(2.5);
}
}
12b. What minimal changes (without changing main) should be made to
get the program to work as intended.
13. Explain why the following java generic class won't compile:
class someclass<T>
{
public T x;
public static T y;
}
Would the class compile in C#? Why?