Lecture 12

2023-05-10 | Week 6 | edited by Ashwin Ranade

(originally written 2022-11-07 by Siddarth Krishnamoorthy)

Hi! Ashwin here. This lecture covers slides 82-116 from Function Palooza.

Table of Contents

Finally

Some languages, like Java, introduced a third component to a catcher to make error handling simpler. This third component is called a finally block and it’s guaranteed to run whether the try block succeeds or throws. This enables you to place your “cleanup” code in a single place, yet guarantee it runs in both error and success situations. Here is an example of some code that uses finally in Java.

// Java "finally" block
public class FileSaver {
  public void saveDataToFile(String filename, 
				String data) {
    FileWriter writer = null;
    try {
      // Next 2 lines might throw IOExceptions
      writer = new FileWriter(filename);
      writer.write(data); 
    } 
    catch (IOException e) {
      e.printStackTrace();  // debug info
    } 
    finally {
      if (writer != null)
        writer.close();
    }
  }
}

Exceptions and memory safety

Exceptions can create all sorts of bugs if not used appropriately. To see how that can happen, consider the following example in C++.

void h() {
  if (some_op() == failure)
    throw runtime_error("deets");

  do_other_stuff();
}
void g() {
  int* arr = new int[100];
  h();
  // code uses array here... 
  delete[] arr;
}
void f() {
  try {
    g();
  }
  catch (Exception &e) {
    deal_with_issue(e);
  }
}

What happens if h throws a runtime_error? Notice that in g, the memory allocated using new is never freed, thus causing a memory leak!So you should be wary of using exceptions in languages without automatic memory management (like C++).

In languages like C++, you can still use exceptions without worrying about memory leaks if you use Smart pointers.

Some languages like Java force you to annotate functions which throw exceptions with a special token (in the case of Java, you must annotate functions that throw with the throws keyword). This way, you will know if you need to catch an exception when you call a function.

// Java functions must explicitly 
// declare their exceptions!
public class MyClass {
  void h() throws IOException {
    if (some_op() == fail_to_open_file)
      throw new IOException("File mising!");
  }
    
  void g() throws IOException {
    h();
    // other code
  }
    
  public void f() {
    try {
      g();
    }
    catch(IOException e) {
      deal_with_issue(e);
    }
  }
}

Another big drawback of exceptions is that they are extremely slow when they are thrown!

Here are a few more examples of exceptions in other languages.

  • Swift
// Swift exception handling example
enum VendErr: Error {   
    case invalidSelection(selection: String)
    case invalidBill(billValue: Int)
}

class VendingMachine { 
  var dollarsInserted: Int

  func insertMoney(dollars: Int) throws {
    if (dollars != 1 && dollars != 5 && dollars != 10) 
      { throw VendErr.invalidBill(billValue: dollars) }
    dollarsInserted += dollars 
  }

  func buyItem(itemCode: String) throws -> String {
     if itemCode == "A1" && dollarsInserted >= 2 {
        dollarsInserted -= 2 
        return "KitKat"
    } 
    // We got nuthin left!
    throw VendErr.invalidSelection(selection: itemCode)
  } 
}
...
var vm = VendingMachine()
do {
    try vm.insertMoney(dollars:10);
    let item = try vm.buyItem(itemCode: "b3");
    print("Ate \(item). Yum!")
} catch VendErr.invalidSelection {
    print("Invalid Selection.")
} catch VendErr.invalidBill(let billSize) {
    print("Counterfeit $\(billSize) bill!")
}
  • Python
# python exception handling example
def getNumbers(howMany): 
  if howMany < 0:   
    raise ValueError("howMany was < 0")
  return [str(i) for i in range(howMany)]

def saveNums(filename, howMany): 
  try:   
    f = open(filename, "w")   
    try:
       nums = getNumbers(howMany)
       f.write(' '.join(nums))
    except ValueError as ve: 
       print("Had a value error:",ve)
    except IOError:
      print("Badness saving to file")   
    finally:
      f.close()
  except OSError:   
     print("Badness opening file")

Exception handling guarantees

As we’ve seen, exception handling can be tricky and difficult to understand. As such, engineers have produced some rules of thumb to ensure exceptions are used in a safe manner. When writing a function, always make sure you meet one of the following guarantees:

  • No throw guarantee: A function guarantees it will not throw an exception. If an exception occurs in/below the function, it will handle it internally, and not throw. For example, this is required of destructors, functions that deallocate memory, swapping functions, etc.
  • Strong exception guarantee: If a function throws an exception, it guarantees that the program’s state will be “rolled-back” to the state just before the function call. For example, vec.push_back() ensures the vector doesn’t change if the push_back() operation fails.
  • Basic exception guarantee: If a function throws an exception, it leaves the program in a valid state (no resources are leaked, and all invariants are intact). Here, state may not be rolled back, but at least the program can continue running.

Panics

Like an exception, a panic is used to abort execution due to an exceptional situation which cannot be recovered from (e.g., an unrecoverable error). Essentially, you can think of a panic as an exception which is never caught, and thus which causes the program to terminate. Panics contain both an error message and a stack trace to provide the programmer with context as to why the software failed.

Here is an example of a panic in C#.

// C# FailFast panic
class WorstCaseScenario
{
  public void someFunc()
  {
    if (somethingUnrecoverableHappens())
      Environment.FailFast("A catastrophic failure has occurred.");
  }
}

Classify that language

Consider the following program, which computes a/b given two values a and b. What result or error handling approach does this language use?

use std::io::{Error, ErrorKind};

fn my_div(a:f64, b:f64) -> Result<f64, Error> {
  if b != 0.0 { Ok(a/b) }
  else { Err(Error::new(ErrorKind::Other, 
             "You divided a by zero!"))  }
}

fn main() {
  match my_div(50.0,20.0) {
    Ok(number) => println!("Got {}",number),
    Err(e) => println!("Got an error {}",e),
  };
  match my_div(10.0,0.0) {
    Ok(number) => println!("Got {}",number),
    Err(e) => println!("Got an error {}",e),
  };
}

This is an example of a language using result variables for error handling. The language lets you specify either a value or an error type/message for a failure.

The language is actually Rust!

First Class Functions

In languages with First Class Functions:

  • Functions can be passed/returned to/from other functions
  • Variables can be assigned to functions
  • Functions can be stored in data structures
  • Functions can be compared for equality
  • Functions can be expressed as anonymous, literal values

Functions here are called “first-class citizens” because they are data objects and can be maniupulated like any other data in a program.

Here are some examples of first class functions in some languages:

  • C++

In C++, first-class functions are implemented with function pointers.

int square(int val) { return val * val; }
int fivex(int val) { return val * 5; }

using IntToIntFuncPtr = int (*)(int val);

void apply(IntToIntFuncPtr f, int val) {
  cout << "f(" << val << ") is " << f(val) << endl;
}

IntToIntFuncPtr pickAFunc(int r) {
  if (r == 0) return square;
         else return fivex;
}

int main() {
 IntToIntFuncPtr f = pickAFunc(rand() % 2);
  if (f == square) cout << "Picked square\n";
               else cout << "Picked fivex\n";
  apply(f, 10);
}
  • Go
func square(val int) int { return val * val }
func fivex(val int) int  { return val * 5 }

type IntToIntFuncPtr func(int) int

func apply(f IntToIntFuncPtr, val int) {
  fmt.Println("f(", val, ") is ", f(val))
}

func pickAFunc(r int) IntToIntFuncPtr {
  if r == 0 {
    return square
  } else {
    return fivex
  }
}

func main() {
  var f = pickAFunc(rand.Intn(2))
  if f != nil {
    apply(f, 10)
  }
}

Anonymous (Lambda) Functions

A lambda function is a function that does not have a function name – it’s anonymous. Typically we pass a lambda function as an argument to another function or store it in a variable. Lambdas are used when a short, temporary function is needed just once in a program, and it doesn’t make sense to define a general-purpose named function.

Every lambda has three different parts:

  • Free Variables to Capture - What variables defined outside the lambda function should be available for use in the lambda function when it is later called.
  • Parameters & Return Type - What parameters does the lambda function take and what type of data does it return.
  • Function Body - The body of the lambda function that performs its operations.

Capture by Value

As the name suggests, in capture by value, only the values of the free variables are captured by the lambda. This means that any changes made to the captured variable inside the lambda will not be reflected outside it. Here is an example of capture by value in C++.

// C++ lambda function
auto create_lambda_func() {
  int m = 5;  
  int b = 3;
  return [m,b](int x) -> int { return m*x + b; };
}

int main() {
  auto slope_intercept = create_lambda_func();
  cout << "5*100 + 3 is: " << slope_intercept(100);
}

Capture by Reference

C++ (and some other languages) can also capture values by reference. Here is an example.

// C++ lambda function – capture by reference
auto fun_with_lambdas() {
  int q = 0;  
  auto changer = [&q](int x) { q = x; };
  changer(5);
  cout << "q is now: " << q; // Outputs "q is now: 5"
  return changer;
}

int main() {
  auto f = fun_with_lambdas();
}

Capture by Environment

In capture by environment, an object reference to the lexical environment where the lambda was created is added to the closure. The lexical environment is a data structure that holds a mapping between every in-scope variable and its value. That includes all variables in the current activation record (locals, statics), and all global variables. Python uses capture by environment semantics. Here is an example.

def foo():
  q = 5
  f = lambda x: print("q*x is: ", q*x)
  f(10)

When you define the lambda, it creates a closure containing:

  • the lambda function itself
  • an object reference to the current lexical environment

When running the lambda, it looks up each free variable in the lexical environments to obtain its value. Now consider this slightly modified code.

def foo():
  q = 5
  f = lambda x: print("q*x is: ", q*x)
  f(10) # outputs "q*x is: 50"
  q = q + 1
  f(10) # outputs "q*x is: 60"

This outputs both 50 and 60. This is because even though the lambda was defined when q = 5, when the lambda runs, it looks up the latest value of the variable in the lexical environment, and therefore outputs 60.

Classify that language

Consider the following program which prints out 7. What capturing strategy does this language employ?

function make_lambda() {
 let puppies = 4;

 // define lambda function with 1 param
 temp = function (kittens) { 
   s = "pup"
   s = s + "pies + kit"
   s = s + "tens" 

   // eval(s) interprets s as if it were a
   // regular statement in the program
   return eval(s)
  }
  return temp
}

f = make_lambda()
console.log(f(3))

Notice that our lambda function never explicitly references puppies! So the language can’t be capturing by value or reference, so it must use capture by environment. The lambda then constructs the string "puppies + kittens". Then the eval function takes it as a parameter and treats it as code, and runs it! So running puppies+kittens computes 4+3 and the code outputs 7.

The language is actually JavaScript!

Polymorphism

Polymorphism is a technique where we define a function or class that is able to operate on multiple different types of values. Our goal is to express algorithms with minimal assumptions about the types of data they operate on, making them as interoperable as possible - ideally without losing computing efficiency. For example, rather than creating a class to represent a linked list of strings, and a separate class for a linked list of ints, we create a single polymorphic linked list class that can hold a list of any type of value.

Polymorphism is generally implemented differently in statically and dynamically-typed languages.

There are three primary types of polymorphism in statically typed languages:

  • Subtype Polymorphism
  • Ad-hoc Polymorphism
  • Parametric Polymorphism

Subtype Polymorphism

In subtype polymorphism, a function is designed to operate on objects of a base class B (e.g., Shape) and on objects of all subclasses derived from B (e.g. Circles). We will cover this in-depth in the OOP section, so we will just give a simple example for now.

class Shape {...}
class Square: public Shape {...}
class Circle: public Shape {...}

void processShape(Shape& s) 
 { ... }

Circle c(10);
processShape(c);
Square s(5);
processShape(s);

Ad-hoc Polymorphism

With ad-hoc polymorphism we define specialized versions of a function for each type of object we wish it to support. The language decides which version of the function to call based on the types of the arguments. This kind of thing is used all the time in C++ for operator overloading!

bool greater(Dog a, Dog b) {
  return a.bark() > b.bark();
}
bool greater(Student a, Student b) {
  return a.gpa() > b.gpa();
}
int main() {
  Dog spot, penny;
  if (greater(spot, penny))
    cout << "Spot wins!\n";

  Student carey, david;
  if (greater(carey, david))
    cout << "Carey wins!\n";
}

Ad-hoc polymorphism isn’t possible in dynamically typed languages. This is because we usually don’t specify types for formal parameters in dynamic languages, there’s no way to define multiple versions of a function with different parameter types. Instead, such languages can specialise behaviour using Type reflection.

Parametric Polymorphism

With parametric polymorphism, we define a single, parameterized version of a class or function that can operate on many, potentially unrelated types. Parameteric polymorphism is implemented in two major ways, templates or generics. The syntax for the two may look similar, but they’re implemented in entirely different ways - with big implications!

Templates

In a language (like C++) that uses the template approach, each time you use the template with a different type the compiler generates a concrete version of the template function/class by substituting in the type parameter. Then it just compiles the newly-generated functions/classes as if they were never templated in the first place. Any operations you use in your templated code must be supported by the types being templated. Here is an example in C++.

template <typename T>
void takeANap(T &x) {
  x.sleep();
}
class Dog {
public:
  void sleep() { ... }
};

class Person {
public:
  void sleep() { ... }
};
...
int main() {
  Dog puppers;
  takeANap(puppers); // OK!

  Person carey;
  takeANap(carey); // OK!

  string val; 
  takeANap(val); // error: no member named 'sleep' in 'string'
}

In the above example, since takeANap uses the sleep() method internally, only types that support sleep() can be used. If you try to use a type that doesn’t support sleep(), you’ll get a compile time error.

When you create a new template, e.g., vector, does the compiler ensure the templated code is type-safe? If so, how?

Answer Yes - since the compiler basically generates a concrete version of the function/class with the specified type, and the compiles it as it would any other class, type safety is guaranteed

Is templated code more or less run-time efficient than an equivalent function that doesn’t use templates, but otherwise has the same logic? Why?

Answer Both implementations have the same runtime efficiency since a custom version of the function/class is generated for each distinct type, and it can be optimized just as if you wrote a dedicated function for that type.

C-style macros are sort of the OG templates. The pre-processor would basically do a textual search-and-replace of the arguments, the compiler doesn’t generate a new function for each parameterized type.

// C macros used to implement template-like functionality

#define swap(T  ,a,b) { T   temp; temp = a; a = b; b = temp; }

int main() {
 int p = 5, q = 6;
 swap(int,p,q);
  
 std::string s = "foo", t = "bar";
 swap(std::string, s, t);
}