# 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
- ...
~~~~