# CS51 Final Project
## *Victor Goncalves --- May 2021*
Alongside my implementation of MiniML, a small subset of an OCaml-like language, I have created three extensions in addition: I have added the float type and math operations sin, cos, and ln, a lexical environment evaluator, and added a function for derivatives.
### 1. Adding Floats and Some Math Operations
When looking at the distribution code for the project, the only number type provided for us in the Expr file was the included **Num** type for integers. Furthermore, the division binary operator was not provided for integers, most likely as the division between two numbers is not always a whole number.

Therefore, I wanted to provide more flexibility for users with another expression and provide operations to give the "mini" language more accuracy in terms of dealing with numbers and math operators.

Firstly, I wanted to add an ability for users to divide and power numbers. To implement this, it made sense to add float types, not only to make this type of operation possible and accurate, but to also give users more accuracy when any operating on any sort of numbers via addition, subtraction, etc. Also, adding powers made it crucial to implement derivatives of expressions later in the extension.

To add float types, I wanted to do this in a similar way to OCaml, having a period after a number to have the option for significant digits or just to keep it a whole number. Ex: 30. or 30.457584. I also wanted to add distinguished float operators as well, for example by having:
* **+.**
* **-.**
* ***.**
* **/.**

Furthermore, as I am implementing floats into my MiniML, it would be reasonable to also add additional unary operators that can use/output floats as well. I wanted to include:

* **Sin**
* **Cos**
* **Ln**

To implement floats and these additional unary operators, I started by additing neccessary keywords and distinctions in the parser and the lexical analyzer to identify the floats and operators themselves.

in miniml_lex.mll, I added the following keywords for the word keywords for the unary operators, and symbols to account for the different operation symbols.

*Keywords:*

("ln", LN);
("sin", SIN);
("cos", COS);

*Symbols:*

("/", DIVIDE);
("^", POWER);
("+.", PLUSFLOAT);
("-.", MINUSFLOAT);
("*.", TIMESFLOAT);
("/.", DIVIDEFLOAT);

Furthermore, in the parser, I defined each respective token to account for when it is called in the lexical analyzer in miniml_parse.mll. It creates a usable Expr of either a Binop or Unop in terms of its passed in argument expressions.

| exp GREATERTHAN exp   { Binop(LessThan, $1, $3) }
| exp PLUSFLOAT exp     { Binop(PlusFloat, $1, $3) }
| exp MINUSFLOAT exp    { Binop(MinusFloat, $1, $3) }
| exp TIMESFLOAT exp    { Binop(TimesFloat, $1, $3) }
| exp DIVIDEFLOAT exp   { Binop(DivideFloat, $1, $3) }
| LN exp                { Unop(Ln, $2) }
| SIN exp               { Unop(Sin, $2) }
| COS exp               { Unop(Cos, $2) }

I also played around with the order of operations for some of these to ensure they are mathematically sound.

%nonassoc IF DERIVATIVE
%left LESSTHAN EQUALS
%left PLUS MINUS PLUSFLOAT MINUSFLOAT
%left TIMES TIMESFLOAT DIVIDEFLOAT
%left POWER
%nonassoc NEG LN SIN COS 

Giving preference to power over times, times and divide the same preference over addition, and made sure the float operators had the same preference as their integer operator counterparts.

Now finally, we are able to test in our MiniML terminal!

*New Unary Ops:*
(Note: I thought it would be useful to allow users to input either floats or integers into these unary ops to output a float.)

<== ln 1;;
==> 0.
<== ln 2.71828;;
==> 0.999999327347
<== cos 0;;
==> 1.
<== cos (3.1415926535 /. 2.);;
==> 4.48965921698e-11
<== sin 0;;
==> 0.
<== sin (3.1415926535 /. 2.);;
==> 1.

*Float Operations*

==> 1.
<== 1. +. 4.;;
==> 5.
<== 4. -. 2.42;;
<== 8. *. 1.234;;
==> 9.872
<== 4. /. 5.;;
==> 0.8

*GreaterThan Binop*

<== 4 > 5;;
==> true
<== 4. > 5.;;
==> true

And to ensure that I accounted for the cases where users inputed different types to either operate/compare:

<== 3. -. 4;; 
xx> evaluation error: can't use float operations on non-floats or mismatching types
<== 3. > 5;;
xx> evaluation error: can't compare nonsimilar types

### 2. Lexical Environment Semantics
For the second extension in my MiniML implementation, I created a lexically scoped environment evaluator in addition to both my dynamic and substitution evaluators.

When comparing lexical environment semantics to dynamic environment semantics, the crucial difference comes to the way that functions are evaluated. In the lexical environment, functions are evaluated when they are defined rather than when they are applied as in a dynamic environment. This way, functions can be evaluated context of the environment they were defined with. To do this, we must evaluate functions to a "package" called a **closure**. This packages a function with its lexical environment for evalutation.

We see this in the value type alongside its Val counterpart in evaluation.ml:

`| Closure of (expr * env)`

And when looking at closures in the repl:

<== let x = 3 in fun y -> x + y ;;
==> fun y -> (x + y) where [x |-> 3]

To implement lexical environment semantics, I started with the dynamic evaluation rules from `eval_s` in evaluation.ml, and I sought to change the ways that both functions and application were evaluated.

`| Fun (var, def) -> Env.close exp env`

and

| App (f, exp) -> 
    let vq = ref (eval exp env) in 
    (match eval f env with
    | Env.Closure(Fun (var, def), prev_env) ->
    let new_env = Env.extend prev_env var vq in 
      eval def new_env

Where the function was wrapped in a closure with its current environment, evaluated with this current environment, and

However, when looking at my lexical and dynamic evaluators together, they shared many similarities that could be refactored into another function that creates both evaluators. Therefore, I created a function called `create_evaluator` that takes in a bool titled `is_dynamic` upon calling to differentiate between whether it is a lexical or dynamic evaluator. I changed the rules for applications and functions respectively.

| Fun (var, def) -> 
    if is_dynamic then wrap (Fun (var, def))
    else Env.close exp env
| App (f, exp) -> 
    let vq = ref (eval exp env) in 
    (match eval f env with
    | Env.Val (Fun (var, def)) -> 
    let new_env = Env.extend env var vq in 
      eval def new_env
    | Env.Closure(Fun (var, def), prev_env) ->
    let new_env = Env.extend prev_env var vq in 
      eval def new_env

*Looking at differences between dynamic and lexical evaluations with an example*

Using the textbook provided example,

let x = 1 in 
let f = fun y -> x + y in
let x = 2 in f 3;; 

expanding the case to use our own numbers,

let x = 5 in
let f = fun z -> x + (3 * z) in
let x = 3 in f 7;; 

and evaluating using our dynamic and lexical evaluators, we get the evaluations respectively

*Dynamic*

<== let x = 21 in let f = fun z -> x + (3 * z) in let x = 3 in f 7;; 
==> 24

*Lexical*

<== let x = 21 in let f = fun z -> x + (3 * z) in let x = 3 in f 7;; 
==> 42

Notice how with the dynamic evaluation, at the time when the function f was applied, `[x |-> 3]` was the scope of the environment in which f 3 was evaluated with. Therefore, in fun z -> x + (3 * z) with x = 3 and z = 7, it should evaluate to 24. However, if we were to look towards the lexical evaluation, at the time when f was defined, `[x |-> 21]` was the scope which f 3 eas evaluated with. fun z -> x + (3 * z) with x = 21 and z = 7 should evaluate to 42!

### 3. Derivatives

Lastly, for the last and favorite part of my extension for this final project, I thought it would be interesting to add the ability to find the derivatives for certain expressions like x² and more.

To implement this, I glanced back to my work in Problem Set 4: A Language for Symbolic Mathematics where we implemented a more basic language than MiniML. In this problem set, we had basic expressions consisting of

(* Binary operators. *)
type binop = Add | Sub | Mul | Div | Pow ;;

(* Unary operators. *)
type unop = Sin | Cos | Ln | Neg ;;

(* Expressions *)
type expression =
  | Num of float
  | Var
  | Binop of binop * expression * expression
  | Unop of unop * expression ;;

that were similar to the expressions in MiniML. Furthermore, we were asked to provide a derivative function for this problem set that when when given an expression, it returns the derivative of this expression.

*Derivative Function*

To start, I also used the contains_var function from the problem set to account for the case where we must differentiate an expression with a variable in the exponent. Also, due to MiniMl including many more expressions, like conditionals, functions, and applications, I had to raise errors when trying to differentiate these non-mathmatical expressions.

let rec derivative (e : expr) : expr =
  let rec contains_var (e : expr) : bool =
    match e with
    | Float _-> false
    | Var _ -> true
    (* Need to check both sides of expresion if Binop *)
    | Binop (_, l_expr, r_expr) -> contains_var l_expr || contains_var r_expr
    | Unop (_, expr) -> contains_var expr 
    (* Raising errors *)
    | Num _ -> error "must use floats"
    | _ -> error "not valid expression" in

When actually differentiating expressions, I wanted to enforce two particular invarients that I thought would be particularly helpful when evaluating. For my implementation, I only wanted to include my new float types to prevent the usage of two types for this function. Furthermore, ints might produce an innacurate outputs when considering the trig functions and dividing expressions. As another invariant, I decided to only allow for differentiation using the variable x. This would prevent errors when inputing a multivariate function and not having to specify which partial derivative to take.

  match e with
  | Float _ -> Float 0.
  | Num _ -> error "must use floats"
  | Var x -> 
    if x = "x" then
        Float 1.
    (* Must use only x as a variable name to prevent multivariabLe functions *)
    else error "Must use x as a variable name"

*Derivative rules for unary operators like ln, sin, and more:*

  | Unop (u, e1) ->
     (match u with
      | Sin -> Binop (TimesFloat, Unop (Cos, e1), derivative e1)
      | Cos -> Binop (TimesFloat, Unop (Negate, Unop (Sin, e1)), derivative e1)
      | Ln -> Binop (DivideFloat, derivative e1, e1)
      | Negate -> Unop(Negate, derivative e1))

(Note: for readability, I have only included the addition rule for this function)

*Derivative addition rule example:*

  | Binop (b, e1, e2) ->
    (match b with
    (* Addition rule *)
    | PlusFloat -> Binop (PlusFloat, derivative e1, derivative e2)
    | _ -> error "Must only use float operators for derivatives")

If you look closely at the binary operations included, only the Float binops are included to enforce the invarient raising an error otherwise.

Now, that I have the derivative function itself, I need a way to implement its usage through the parser and lexical analyzer in a similar way to adding the new float and unops from part 1. In miniml_lex.mll, I added the following derivative keyword along with its DERIVATIVE token.

*Keywords:*

("derivative", DERIVATIVE);

In the parser, I defined the respective token to account for when it is called in the lexical analyzer in miniml_parse.mll. It takes the input expression and sends it to the derivative function as a parameter. I had the derivative of the expression evaluated here to prevent substitution and evaluation issues later down the line.

| DERIVATIVE exp        { derivative $2 }

Now to test in our MiniML terminal! I am going to use the trivial evaluator to show the actual expressions themselves post differentiation.

<== derivative x ^ 3.;;
==> ((3. *. 1.) *. (x ^ (3. -. 1.)))
<== derivative ln x;;
==> (1. /. x)

Now to switch evaluators and test derivatives with other aspects of MiniML!

<== let x = 2. in derivative ln x;;
==> 0.5

First the derivative of ln x is evaluated, then x -> 2. is substituted into all occurances of x in the derivative. The derivative of ln x is 1. /. x and when substituted 2. for x, you get 1. /. 2. or 0.5!