---
# System prepended metadata

title: Programming Language Design Assignment \#2

---

# Programming Language Design Assignment \#2

Please hand-in your answers on LMS before 10/23 23:55.

In this assignment, you're asked to implement an AST and operations to interpret boolean expressions.

Please note that you should:
   
  * Implement 1 & 2 (90pt) in Java and 3 in C lang (10pt).
  * Use different directory for each answers.
  * Zip your all the directories to a single zip, name it by your student id\#, e.g. `107525008.zip` 

Please feel free to ask TA if the question is not clear to you. (Check out the [FAQ](#FAQ) below first)

----

~~~~java
public abstract class Exp {
    public abstract boolean eval();
}

public class Lit extends Exp {
    private boolean val;
    public Lit(boolean val) {
        this.val = val;
    }
    
    public boolean eval() {
        return this.val;
    }
}
~~~~

### 1. Simple Interpreter

Following the code above, implement `And`/`Or` and `eval` methods using inheritance.

Example Test Cases:
~~~java
(new And(new Lit(true), new Lit(false))).eval() == false;
(new And(new Lit(true), new Lit(true))).eval()  == true;
(new Or(new Lit(true), new Lit(false))).eval()  == true;
(new Or(new Lit(false), new Lit(false))).eval() == false;
~~~

### 1-1. Add Expression

Add a new expression `Not` to the your AST.

Example Test Cases:
~~~~java
(new Not(new Lit(true))).eval() == false;
(new Not(new Lit(false))).eval() == true;
~~~~

### 1-2. Add Interpretation

Add a new interpretation `toSExp` to the AST,

~~~~java
public abstract class Exp {
    public abstract boolean eval();
    public abstract String toSExp();
}
~~~~

which return the S-expression of a boolean AST in `String`.

Example Test Cases:
~~~~java
(new Lit(true)).toSExp() == "T";
(new Lit(false)).toSExp() == "F";
(new And(new Lit(true), new Lit(false))).toSExp() == "(and T F)";
(new Or(new Lit(true), new Lit(false))).toSExp() == "(or T F)";
(new Or(new Lit(true), new And(new Lit(true), new Lit(false)))).toSExp()
    == "(or T (and T F))";
~~~~

### 2. Simple Interpreter using Visitor pattern

Following the code below, rewrite the simple interpreter in Question 1 using the visitor pattern.


~~~~java
abstract class Exp {
  public abstract Object accept(Visitor v);
}

class Lit extends Exp {
  public boolean val;
  public Lit(boolean val) {
    this.val = val;
  }
  public Object accept(Visitor v) {
    return v.visit(this);
  }
}

interface Visitor {
  public Object visit(Lit e);
}

class Interpreter implements Visitor {
  public Object visit(Lit n) {
    return n.val;
  }
}
~~~~

Example Test Cases:
~~~~java
Interpreter intp = new Interpreter();
(Boolean) (new And(new Lit(true), new Lit(false))).accept(intp) == false;
(Boolean) (new And(new Lit(true), new Lit(true))).accept(intp)  == true;
(Boolean) (new Or(new Lit(true), new Lit(false))).accept(intp)  == true;
(Boolean) (new Or(new Lit(false), new Lit(false))).accept(intp) == false;
~~~~

:::info
For the sake of simplicity, we make `accept` return an `Object`, which make you need to perform downcasts to extract values.
~~~~java
Interpreter intp = new Interpreter();
(Boolean) (new Lit(true)).accept(intp) == true;
~~~~

There is a better way to do this called "parametric polymorphism" (or "generic" in Java), which will be discussed in future lectures.
:::


### 2-1. Add Interpretation

Like 1-2, add a new interpretation `SExpPrinter` to your Visitor-based AST.

Example:
~~~~java
SExpPrinter printer = new SExpPrinter();
(String) (new Lit(false)).accept(printer) == "F";
~~~~

### 2-2. Add Expression

Like 1-1, add a new expression `Not` to your Visitor-based AST.

:::info
Althouth these exercise is simple, you can still feel that Visitor-style is hard to add expressions and OO-style is hard to add interpretations. 
:::

:::info
Furthermore,
The famous "[Open-Closed Principle][ocp]" said "classes should be open for extension, but closed for modification".
As you can see, both OO-style and Visitor-style breaks the principle when you try to add an interpretation(expression),
this phenomenon is called "Expression Problem".
:::

[ocp]: https://en.wikipedia.org/wiki/Open%E2%80%93closed_principle

### 3. (Challenge) Implement AST Without OO-Support (10pt)


The following code is a C implementation and it uses some trick to simulate OO mechanisms.
In this question, you need to complete `And_t`, `and_new`, `and_eval`.

~~~~c
#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>

/* Exp
 *   since this is an abstract class with no constructor,
 *   we don't need to implement a new method for it. */
typedef struct ExpTable ExpTable_t;
typedef struct Exp Exp_t;
struct Exp {
  ExpTable_t * table;
};

struct ExpTable {
  bool (*eval)(Exp_t * exp);
};

bool exp_eval(Exp_t * e) {
  return e->table->eval(e);
}

/* Lit
 *   the virtual table for Lit is omitted,
 *   since it don't have any other methods. */
typedef struct Lit {
  ExpTable_t * table;
  bool val;
} Lit_t;

bool lit_eval(Exp_t * e) {
  return ((Lit_t *) e)->val;
}

Exp_t * lit_new(bool val) {
  ExpTable_t * table = (ExpTable_t *) malloc(sizeof(ExpTable_t));
  table->eval = lit_eval;

  Lit_t * obj = (Lit_t*) malloc(sizeof(Lit_t));
  obj->table = table;
  obj->val = val;

  return (Exp_t*) obj;
}

/* And */
typedef struct And {
  ExpTable_t * table;
// COMPLETE HERE...
} And_t;

// IMPLEMENT THESE FUNCTIONS
bool and_eval(Exp_t * e);
Exp_t * and_new(Exp_t *e1, Exp_t * e2);
~~~~

Example Test Cases:
~~~~c
exp_eval(lit_new(true))  ==  true;
exp_eval(lit_new(false)) == false;
exp_eval(and_new(lit_new(true), lit_new(true)))  == true;
exp_eval(and_new(lit_new(true), lit_new(false))) == false;
~~~~


# FAQ

* Is there any request about input/output?
  
  No, we don't have any restriction/request on it.
  
* What is desired folder layout?

  As long as you follow the rule - one dir. per one question, it is acceptable.
  
  A possible example is:
  
~~~~  
  + q1
    - Exp.java
    - And.java
    - ...
  + q2
    - Exp.java
    - And.java
    - ...
~~~~