Project Topics: Winter Term 2023/24

Martin Sulzmann

Topics

Translating methods, interfaces and structural subtyping

Recall the “run-time method look up” (RT) and “dictionary-translation” (DT) approach covered here

  1. Compare the run-time performance of RT and DT (e.g. call “sumArea” in a loop and measure which version runs faster)

  2. Apply the RT and DT approach to one further example of your own choice.

  3. Extend RT and DT to deal with type assertions. See example below.

  4. Extend RT and DT to deal with type bounds. See example below.

  5. Summarize your findings in a short document (you could set up a github repo).

Example with type assertion

type square struct {
    length int
}

func (s square) area() int {
    return s.length * s.length
}

type shape interface {
    area() int
}

func sumAreaVariant(x, y shape) int {
    z := y.(square)
    // Not every shape value can be turned into a square.
    // Above might fail at run-time.
    return x.area() + y.area() + z.length
}

func testSumAreaVariant() {
    fmt.Printf("%d", sumAreaVariant(square{1}, square{2}))
    // Type checks cause  square <= shape
}

Example with type bound

type node[T any] struct {
    val  T
    next *node[T]
}


func showNode[T Show](n *node[T]) string {
    var s string

    for n != nil {
        s = s + n.val.show() + " -> "
        n = n.next

    }

    s = s + " nil"

    return s

}

Translating “generics”

We consider the translaton of programs with universal type parameters (aka “generics”). We assume that there are no type bounds and no uses of structural subtyping.

There are two established translation methods where source Go programs with generics are translated to a more simple target language.

  1. Apply both translation methods to the three examples below. The first example contains a sketch for each translation method.

  2. Is it possible to apply both translation methods for each example? Why (not)?

  3. What programming language features are required for target programs. Hint: The generic translation method might need to rely on structural subtyping and type assertions.

  4. Summarize your findings in a short document (you could set up a github repo).

Example linked list

type node[T any] struct {
    val  T
    next *node[T]
}

func mkNode[T any](v T) *node[T] {
    return &node[T]{val: v, next: nil}
}

func insert[T any](n *node[T], v T) {
    n.next = mkNode[T](v)
}

// n > 0
func mkList[T any](n int, v T) *node[T] {

    head := mkNode(v)
    current := head

    for i := 0; i < n-1; i++ {
        insert(current, v)
        current = current.next

    }
    return head

}

func len[T any](n *node[T]) int {
    i := 0

    for n != nil {
        i++
        n = n.next

    }

    return i

}

func testNode() {
    n1 := mkList[int](10, 1)
    fmt.Printf("\n%d", len(n1))

    n2 := mkList[bool](10, true)
    fmt.Printf("\n%d", len(n2))

}

// Generic translation (sketch)

type node_G struct {
    val  interface{}
    next *node_G
}

func mkNode_G(v interface{}) *node_G {
    return &node_G{val: v, next: nil}
}

// Monomorphization (sketch)

type node_int struct {
    val  int
    next *node_int
}

func mkNode_int(v int) *node_int {
    return &node_int{val: v, next: nil}
}

Example summing up numeric values

func sum[T int | float32](xs []T) T {
    var x T
    x = 0
    for _, v := range xs {

        x = x + v
    }

    return x

}

Example swap

func swap[T any](x *T, y *T) {
    tmp := *x
    *x = *y
    *y = tmp
}

Arithmetic expressions in Rust - Evaluator

Consider Haskell to implement other languages

  1. Represent the Haskell data type in Rust

  2. Implement the evaluator in Rust including simplifications (e.g. “0 * x” shall immediately yield 0).

  3. Draw a comparison between Haskell and Rust

  4. Summarize your findings in a short document (you could set up a github repo).

Arithmetic expressions in Rust - Type checker

Consider Haskell to implement other languages

  1. Represent the Haskell data type in Rust

  2. Implement the type checker in Rust

  3. Draw a comparison between Haskell and Rust

  4. Summarize your findings in a short document (you could set up a github repo).

OO in Java versus Go

We compare inheritance in Java (nominal subtyping, virtual methods) versus Go interfaces and structural subtyping

  1. Consider several Java examples (of your own choice) that make use of nominal subtyping and virtual methods

  2. Re-implement these examples in Go

  3. Draw a comparison between Java and Go

  4. Summarize your findings in a short document (you could set up a github repo).

Monads in the OO context

Monads allow for the systematic control of side effects where

Thanks to functional composition and the ability to overload monadic operators such as >>= and return, monadic programs “almost” look like imperative programs.

  1. Your task is to collect examples of monads in the OO context (Java, C++, …)

  2. To get started you find a below a description of the “Maybe” monad in Haskell as well as an implementation in C++.

  3. Summarize your findings in a short document (you could set up a github repo).

Haskell “Maybe” monad

Functions with implicit side-effects

divInt :: Int -> Int -> Int
divInt _ 0 = error "can't divide by zero"
divInt n m = n `div` m

Making side-effects visible via types

divSafe :: Int -> Int -> Maybe Int
divSafe _ 0 = Nothing
divSafe n m = Just $ n `div` m

Monads

Monads allow for the systematic control of side effects

Maybe is a monad

divSafe2 :: Int -> Int -> Maybe Int
divSafe2 _ 0 = fail ""
divSafe2 n m = return $ n `div` m

Example

-- (x/y)/z
example x y z = case (divSafe x y) of
                  Just res -> case (divSafe res z) of
                                Just res2 -> "Just " ++ show res2
                  Nothing -> "Nothing"

Functional composition to the rescue

exampleM x y z = do res <- divSafe x y
                    res2 <- divSafe res z
                    return res2

-- "do" Syntax desugared in a sequence of "bind" (>>=) operations
-- In our case,
-- (>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b
exampleM2 x y z =   (divSafe x y)
                     >>=
                    (\res -> divSafe res z
                           >>=
                           (\res -> return res))

Complete source code

import Control.Applicative
import Control.Monad

-- Function with side-effect.
-- We raise an exception if we attempt to divide by zero.
divInt :: Int -> Int -> Int
divInt _ 0 = error "can't divide by zero"
divInt n m = n `div` m

divSafe :: Int -> Int -> Maybe Int
divSafe _ 0 = Nothing
divSafe n m = Just $ n `div` m

-- Maybe is a monad, can use fail/return instead of Nothing/Just.
divSafe2 :: Int -> Int -> Maybe Int
divSafe2 _ 0 = fail ""
divSafe2 n m = return $ n `div` m

example x y z = case (divSafe x y) of
                  Just res -> case (divSafe res z) of
                                Just res2 -> "Just " ++ show res2
                  Nothing -> "Nothing"

exampleM x y z = do res <- divSafe x y
                    res2 <- divSafe res z
                    return res2


-- "do" Syntax desugared in a sequence of "bind" (>>=) operations
-- In our case,
-- (>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b
exampleM2 x y z =   (divSafe x y)
                     >>=
                    (\res -> divSafe res z
                           >>=
                           (\res -> return res))

runMaybe comp = case comp of
                 Just x -> "The result is: " ++ show x
                 Nothing -> "Failure"


-- Defining our own simple 'maybe' monad

data Res a = Something a | Fail String deriving Show


instance Monad Res where
   return x = Something x
   p >>= f = case p of
              (Fail e) -> Fail e
              (Something x) -> f x

instance Applicative Res where
   pure = return
   x <*> y = do f <- x
                a <- y
                return (f a)

instance Functor Res where
   fmap f x = do a <- x
                 return (f a)

“Maybe” monad in C++

template<typename T>
class Optional {
  bool b;
  T val;
public:
  Optional() : b(false) {}
  Optional(T v) : val(v), b(true) {}
  bool isJust() { return b; }
  bool isNothing() { return !b; }
  T fromJust() { return val; }


  template<typename S>
  Optional<S> bind(function<Optional<S>(T)> f) {
     if (this->isNothing()) {
       return *this;
     } else {
       auto v = this->fromJust();
       return f(v);
     }
  }

  void print() {
      if (this->isNothing()) {
        cout << "\n Invalid result";
      } else {
        cout << "\n" << this->fromJust();
      }
  }

}; // Optional class

template<typename T>
Optional<T> ret(T x) {
    return Optional<T>(x);
}

template<typename T>
Optional<T> fail() {
    return Optional<T>();
}

Compose monad computations via functional composition

Our running example “(x/y)/z” rephrased in terms of C++.

Optional<int> exampleM(int x, int y, int z) {

  return divSafe(x,y).bind<int>([z](int res) -> Optional<int> {
      return divSafe(res,z).bind<int>([](int res2) -> Optional<int> { return ret(res2);});});

}

Method chaining to the resuce

template<typename T>
class Optional {

  Optional<T> div(T x) {
     if (this->isNothing() || x == 0) {
       return *this;
     } else {
       auto v = this->fromJust();
       return Optional(v/x);
     }
  }
};
Optional<int> exampleM2(int x, int y, int z) {

  return Optional<int>(x).div(y).div(z);

}

Complete source code

/*

Monads. A concept none in functional languages such as Haskell.
Turns out, monads are also useful in imperative languages.

- Systematic control of side effects.
- We use types to describe effects.
- Effectful computations are built via function composition.

Benefits.

Systematic control of side effects.
What and where side effects take place can be easily read out of the program text.

User needs to follow the "monadic" design pattern.


Example: The Optional (aka Maybe) monad.

Side effect we wish to control:
    Result is successful ("just some value") or fails ("nothing").

*/


#include <functional>
#include <stdio.h>
#include <iostream>
using namespace std;


// Haskell's Maybe rephrased in C++.
template<typename T>
class Optional {
  bool b;
  T val;
public:
  Optional() : b(false) {}
  Optional(T v) : val(v), b(true) {}
  bool isJust() { return b; }
  bool isNothing() { return !b; }
  T fromJust() { return val; }


  template<typename S>
  Optional<S> bind(function<Optional<S>(T)> f) {
     if (this->isNothing()) {
       return *this;
     } else {
       auto v = this->fromJust();
       return f(v);
     }
  }

  void print() {
      if (this->isNothing()) {
        cout << "\n Invalid result";
      } else {
        cout << "\n" << this->fromJust();
      }
  }

  // Assumes type T supports division.
  Optional<T> div(T x) {
     if (this->isNothing() || x == 0) {
       return *this;
     } else {
       auto v = this->fromJust();
       return Optional(v/x);
     }
  }
}; // Optional class

template<typename T>
Optional<T> ret(T x) {
    return Optional<T>(x);
}

template<typename T>
Optional<T> fail() {
    return Optional<T>();
}


// Fail safe integer division

Optional<int> divSafe(int x, int y) {
  if (y == 0) {
    return Optional<int>();
  } else {
    return Optional<int>(x / y);
  }
}

// (x/y)/z

Optional<int> example(int x, int y, int z) {

  auto res = divSafe(x,y);
  if (res.isNothing()) {
    cout << "\n Invalid result";
  }
  auto res2 = divSafe(res.fromJust(),z);

  return res2;

}


// Optional is a monad.
// Use functional composition.

Optional<int> exampleM(int x, int y, int z) {

  return divSafe(x,y).bind<int>([z](int res) -> Optional<int> {
      return divSafe(res,z).bind<int>([](int res2) -> Optional<int> { return ret(res2);});});

}

// Method chaining instead of functional composition.
Optional<int> exampleM2(int x, int y, int z) {

  return Optional<int>(x).div(y).div(z);

}



int main() {
  int x,y,z;
  x = 12; y = 2; z = 3;
  example(x,y,z).print();

  exampleM(x,y,z).print();

  exampleM2(x,y,z).print();


}

Dependent types

  1. Look for examples of “dependent types” in Rust.

  2. Rephrase the Dependent types in Haskell in Rust (as many Haskell code parts as possible).

  3. Summarize your findings in a short document.