---
# System prepended metadata

title: Programming Language Design Assignment \#5

---

# Programming Language Design Assignment \#5

Please hand-in your answers on LMS before 12/20 23:55 and
make sure you're following these rules or you will get penalty:

* Submit your answers in a single pdf file. (only pdf files will be accepted)
* Name your pdf file by your student ID\#. (ex. `107525008.pdf`)
* Use `monospace`-style font to format all the program codes you wrote and **DO NOT** use code screenshots as your answer.


# Functional Programming

## Maybe

Given the function signatures below,

~~~haskell
readData :: String -> Maybe String
parseData :: String -> Maybe [(Int, Int)]
processData :: [(Int, Int)] -> Maybe [Int]
~~~

Rewrite the following code with monad(use `>>=` or do-notation.)

~~~haskell
process :: String -> Maybe [Int]
process filename =
    case readData filename of
      Nothing -> Nothing
      Just rawLines ->
        case parseData rawLines of
          Nothing -> Nothing
          Just parsed ->
            case processData parsed of
              Nothing -> Nothing
              Just processed -> return processed
~~~

:::info
The `case expr of ...` is an expression to perform pattern matching. For example,

~~~haskell
f (Just a) = a + 1
f Nothing  = 1
~~~

can be rewrite as

~~~haskell
f x = case x of
        Just a  -> a + 1
        Nothing -> 1
~~~
:::

:::info
For the sake of simplicity, we don't make `readData` an `IO` action, but it should be one in a real scenario.
:::

## Left, Right or None

Suppose we're going to extends `Either` with a `None` case(like `Nothing` in `Maybe`):

~~~haskell
data MyEither a b = MyLeft a | MyRight b | None
    deriving (Eq, Show)
~~~

Please show the instances of `Functor`, `Applicative` and `Monad` for `MyEither`.

Your implementation must obey functor/applicaitve/monad laws for corresponding instance.

# Aspect-Oriented Programming

## Logging

Suppose that the following code is the only aspect in a AspectJ program. Will it cause stack overflow? Why?

~~~~java
public aspect Logging {
    pointcut logPrintln():
        call(* *.println(..)) && !within(Logging);
    after(): logPrintln() {
        System.out.println("println is called!");
    }
}
~~~~

## Memorization
The following is a Java program calculating binomial coefficients using a recursive algorithm.
Assume `n, k <= 32`, please implement a aspect to memorize/cache the binomial for speeding it up.

~~~java
class Bin {
    int binomial(int n, int k) {
      if (k == 0) return 1;
      if (n == k) return 1;
      return binomial(n - 1, k - 1) + binomial(n - 1, k);
    }

    public static void main(String[] args) {
      Bin b = new Bin();
      System.out.println(b.binomial(32, 16));
    }
}
~~~~
