CPL 3: Function Interpretation and Environments

목차

 

Environments Basic Functions

Environments represent the bindings available at different locations. 

Environment = list of bindings

Bind is a case class (ADT) Bind(name: String, value: Value)

E.g. Environment = [Bind("x", NumV(3)), Bind("y", NumV(5))]

Difference between maps: environments allow for duplicate keys  → allow access to shadowed bindings

 

1. add()

def add(myEnv: Environment, name: String, value : Value): Environment = {
    Bind(name, value) :: myEnv
  }

 

이 함수는 Environment myEnv에 새 Bind를 추가만 해주면 된다 → Bind(name, value).

It is possible for there to be bindings with the same name. In that case, the last added binding should be the one returned by the take method. 

즉, take를 했을 때, 마지막에 추가된 binding를 반환해야 하기 때문에 리스트 맨 앞에 추가해 준다.

 

2. take()

def take(myEnv: Environment, name: String): Value = {
    val filtered = myEnv.filter(x => x.name.equals(name))
    if (filtered.isEmpty) throw new MyInterpException("")
    filtered.head.value
}

 

이 함수는 Environment에서 가장 최근에 추가된 Binding 중에서 이름이 name과 동일한 Binding의 value를 반환한다.

그래서, 먼저 filter()를 통해서 Environment에 name과 같은 Binding이 있는지 확인을 하고 없으면 Exception, 있으면 head(맨 앞)의 value를 반환하면 된다.

 

3. update()

def update(myEnv: Environment, otherEnv: Environment): Environment = {
  val otherNames = otherEnv.map(x => x.name)
  myEnv.map(x => if (otherNames.contains(x.name)) otherEnv.filter(y => y.name.equals(x.name)).head else x)
}

 

이 함수는 myEnv에 있는 Binding 중에서 otherEnv에도 같은 이름의 Binding이 있으면 otherEnv에 있는 Binding의 값으로 바꾼 후 반환하면 된다. 

 

 

4. extend()

def extend(myEnv: Environment, otherEnv: Environment): Environment = {
  val myNames = myEnv.map(x => x.name)
  val toAdd = otherEnv.filter(x => !myNames.contains(x.name))
  myEnv ::: toAdd
}

 

이 함수는 otherEnv에 있는 Binding 중에서, myEnv에 없으면 otherEnv에 append 시켜주면 된다. 

→ 리스트를 append 할 때는 ::: 사용

 

 

 

Scoping and Substitution

Lexical scoping, which is indicated by curly brackets. This means:

• You can refer to something that is defined in a higher scope (e.g. method can refer to things in class)
• You cannot refer to something that is not defined in your scope or a higher scope.

1. Scoping in Java

class A {
  int myMethod(int x) {
    if (x > 10) {
      return 0;
    } else {
      int y = 5;
      return y + x;
    }
  }

 

There is a scope for the class A, in which there is one name defined, myMethod.
There is a scope for myMethod, in which there is a name defined, x (the parameter).
There is a scope for the if, which is empty.
There is a scope for the else, in which there is a name defined, y.
The lexical scopes are as follows:

(A) <- (myMethod) <|- (if)
                   |- (else)

 

 

2. Scoping in Paret

Scoping in Paret is based on parentheses; every s-expr in Paret has a scope, which depends on the environment under which it is evaluated.

(let (
      (x 1)
     )
  (let (
        (y 0)
       )
    (+ x y)
  )
)

Scopes:

• the let binding x in line 2;
• the let binding y in line 5, which has access to the value of x;
• the binary operation in line 7, which has access to the values of x and y;

 

(let (
      (x 0)
      (y 1)
      (z false)
     )
  (let (
        (x y)
       )
    (if z
        x
        y
    )
  )
)

The scopes are:

• the let binding x in line 2;
• the let binding y in line 3;
• the let binding z in line 4;
• the let binding x in line 7, which has access to the values of x (from line 2), y and z;
• the if condition, true result, and false result in lines 9, 10, and 11, which have access to the values of x (from line 7), y and z;

 

Name Shadowing in Java

Name shadowing is the concept of using multiple scopes that contain the same variable names, where the highers scopes are shadowed by lower scopes.

int yourMethod(int x) {
    int x = 5;
    return x * x;
}

 

yourMethod(10) 하면 25 return due to Name Shadowing. 

→ int x declaration in line 2 is shadowing the method’s argument x.

 

class A {
  final int x = 5;

  class B {
    final int x = 20;

    public int add1(int y) {
       int x = y;
       return x + 1;
    }
  }
}

 

다음을 했을 때:

A a = new A();
A.B b = a.new B();

b.add1(10)); // => 11

 

When defining a in line 1, we have x=5 in the scope of that class.
When defining b in line 2, we have x=20 in the scope of that class. Therefore, the x in class A is shadowed by the x in class B.
When calling add1, we initialise x to y. Hence, the x in class B is shadowed by x in add1.
Furthermore, the name shadowing is transitive, so the x in class A is shadowed by x in add1, too.

 

 

Name Shadowing in Paret

(let ((x 6))
   (let ((x 4) (y 6))
      (if (num= x y)
          y
          x
      )
   )
)

 

When evaluating the expression, the result is going to be NumV(4) and not NumV(6). This is again occurring due to the fact that we have name shadowing in our interpreter. Namely, the value of x during the evaluation of the if statement is going to be 4 and not 6. This is because the let binding of the inner let is shadowing the let binding of the outer let. Furthermore, the let binding of the inner let is of lower scope.

 

 

(let
   (
    (x (let ((y 15)) (* 2 y))
    (y 20)
    (z (not false))
   )
   (if z
       (+ x y)
       (let ((x (- 10)))
         (* x y)
       )
   )
)

 

The only shadowing that will occur is of the let binding x in the outer let expression. It will be shadowed by the inner let, which is inside the if statement.

Since during evaluation we are first going to find the value of x, there will be no shadowing happening between the s-exprs containing identifier y. What is more, if the result of evaluating the if statement was BoolV(true), then there would have been no name shadowing for x either.

 

 

 

Environments

Environments in Java

Example 1:

public static int add() {
  int x = 1;
  int y = 0;
  return x + y;
}

 

1. Our initial environment is empty

[] |-
public static int add() {
  int x = 1;
  int y = 0;
  return x + y;
}

 

 

2.The function add has no parameters, which can modify the environment. However, we are now able to refer to add so we need to add it to the environment (before we enter the sub-scope).

[add |-> () => int] |-
{
  int x = 1;
  int y = 0;
  return x + y;
}

3. Now, we enter the sub-scope (body) of add:

[] |-
int x = 1;
int y = 0;
return x + y;

 

4. Line 2 and Line 3 of the original function will extend the current environment and add the binding x |→ 1, y |→ 0.

[x |-> 1, y |-> 0] |-
return x + y;

5. Finally, we use x and y from the environment and evaluate the expression x + y and return 1. When returning, we will exit the sub-scope of the add function.

 

 

Example 2:

public static void main () {
  int x = 1;
  {
    int y = 3;
    int z = x + y;
  }
  int k = 5;
}

 

1. Our initial environment is empty.

[] |-
public static void main () {
  int x = 1;
  {
    int y = 3;
    int z = x + y;
  }
  int k = 5;
}

 

2. The function main is called, so we add it to the environment.

[main |-> () => ()]
{
  int x = 1;
  {
    int y = 3;
    int z = x + y;
  }
  int k = 5;
}

 

3. The function main has no parameters, so no changes occur to the environment. So we enter its sub-scope (body). 여기서는 Outer curly brackets만 제거.

[main |-> () => ()] |-
int x = 1;
{
  int y = 3;
  int z = x + y;
}
int k = 5;

 

4. Extend the current environment by adding x |-> 1.

[main |-> () => (), x |-> 1] |-
{
  int y = 3;
  int z = x + y;
}
int k = 5;

 

5. We enter the sub-scope (curly brackets).

[main |-> () => (), x |-> 1] |-
int y = 3;
int z = x + y;

 

6. We extend the environment with y = 3.

[main |-> () => (), x |-> 1, y |-> 3] |-
int z = x + y;

 

7. We use the values of x and y from the environment and extend the environment with z  = 4.

[main |-> () => (), x |-> 1, y |-> 3, z |-> 4] |-

 

8. We are done with the current scope so we exit this sub-scope and return to the outer environment, which did not contain y and z.

[main |-> () => (), x |-> 1] |-
int k = 5;

 

9. We extend the environment with k = 5.

[main |-> () => (), x |-> 1, k |-> 5] |-

 

10. After the main function, it can still be called, so we end with the following environment.

[main |-> () => ()] |-

 

 

 

Example 3:

public static int main (int z) {
  int x = 1;
  int y = 5;
  int max = x;
  if (max < y) {
    max = y;
  }
  if (max < z) {
    max = z;
  }
  return max;
}

 

Q: This method has been called with z = 3, so begin the evaluation in the body of main.

1. The main function is defined. 

[main |-> Int => Int] |-
{
  int x = 1;
  int y = 5;
  int max = x;
  if (max < y) {
    max = y;
  }
  if (max < z) {
    max = z;
  }
  return max;
}

 

2. We enter the sub-scope, with our initial environment which contains z |-> 3. 

[main |-> Int => Int, z |-> 3] |-
int x = 1;
int y = 5;
int max = x;
if (max < y) {
  max = y;
}
if (max < z) {
  max = z;
}
return max;

 

3. We extend current environment with x = 1 and y = 5 and m = 1 (by using x from the environment). 여기는 순서대로 environment에 추가.

[main |-> Int => Int, z |-> 3, x |-> 1, y |-> 5, max |-> 1] |-
if (max < y) {
  max = y;
}
if (max < z) {
  max = z;
}
return max;

 

4. We use max and y from the environment to evaluate the if statement. Since it's true, we enter the sub-scope of the body.

[main |-> Int => Int, z |-> 3, x |-> 1, y |-> 5, max |-> 1] |-
max = y;

 

5. When we modify existing bindings in an environment using mutation, the effect will persist in the environments of outer scope. So, we overwrite the environment binding for max |-> 5 and exit the sub-scope of the if body.

[main |-> Int => Int, z |-> 3, x |-> 1, y |-> 5, max |-> 5] |-
if (max < z) {
  max = z;
}
return max;

 

6. We use max and z to evaluate the if statement, which if false, so the body of the if is not executed. 

[main |-> Int => Int, z |-> 3, x |-> 1, y |-> 5, max |-> 5] |-
return max;

 

7. Final step is to return max from the environment and when returning, we exit the sub-scope of the main function.

 

 

Environments in Paret

Example 1:

(let (
      (x 2)
     )
  (let (
        (y 3)
       )
    (+ x y)
  )
)

 

1. Initial environment empty.

[] |-
(let (
      (x 2)
     )
  (let (
        (y 3)
       )
    (+ x y)
  )
)

 

2. Evaluate the bindings of the outer let expression, so we enter the sub-scope. The binding will have an empty environment when evaluated, but it extends the environment of the body of the let expression with x |-> NumV(2).

[] |-
(x 2)

 

3. We exit the let binding scope and enter the let body sub-scope.

[x -> NumV(2)] |-
(let (
      (y 3)
     )
  (+ x y)
)

 

4. We first evaluate the let expression. So, we enter the sub-scope of the binding. The binding will extend the environment of the body of the let expression with y |-> NumV(3).

[x -> NumV(2)] |-
(y 3)

 

5. We exit the let binding scope and enter the let body sub-scope.

[x -> NumV(2), y -> NumV(3)] |-
(+ x y)

 

6. We evaluate x + y using the values from environment and return NumV(5).

 

 

Example 2:

(let (
      (x (cons 3 nil))
     )     
  (let (
        (y (cons 4 nil))
       )    
    (let (
          (z (+ (head x) (head y)))
         )
       (* z z)
    )
  )
)

 

1. Environment initially empty

[] |-
(let (
      (x (cons 3 nil))
     )     
  (let (
        (y (cons 4 nil))
       )    
    (let (
          (z (+ (head x) (head y)))
         )
       (* z z)
    )
  )
)

 

2. We first evaluate the bindings of the outer let expression so we enter the sub-scope of the binding. Extend the environment with x |-> ConsV(NumV(3), NilV()).

[] |-
(x (cons 3 nil))

 

3. We exit the let binding scope and enter the let body sub-scope.

[x -> ConsV(NumV(3), NilV())] |-
(let (
      (y (cons 4 nil))
     )    
  (let (
        (z (+ (head x) (head y)))
       )
     (* z z)
  )
)

 

4. We then evaluate the bindings of the let expression, so we enter the sub-scope of the binding. Extend the environment with let expression with y |-> ConsV(NumV(4), NilV()). 

[x -> ConsV(NumV(3), NilV())] |-
(y (cons 4 nil))

 

5. We exit the let binding scope and enter the let body sub-scope. 

[x -> ConsV(NumV(3), NilV()), y -> ConsV(NumV(4), NilV())] |-
(let (
      (z (+ (head x) (head y)))
     )
   (* z z)
)

 

6. We evaluate the bindings of the let expression, with z |-> NumV(7).

[x -> ConsV(NumV(3), NilV()), y -> ConsV(NumV(4), NilV())] |-
(z (+ (head x) (head y)))

 

7. We exit the let binding scope and enter the let body sub-scope.

[x -> ConsV(NumV(3), NilV()), y -> ConsV(NumV(4), NilV()), z |-> NumV(7)] |-
(* z z)

 

8. We evalaute it using the values from the environment and return 49.

 

 

Example 3: 

(let (                          
      (first (not true))        
      (second (or false true))  
     )                          
     (or first second)          
)

 

1. Initial environment empty

[] |-
(let (                          
      (first (not true))        
      (second (or false true))  
     )                          
     (or first second)          
)

 

2. Evaluate the binding of the outer let expression, so enter sub-scope of the binding. Extend with first |-> BoolV(false).

[] |-
(first (not true))

 

3. Then, evaluate the second binding of the outer let expression, so we enter sub-scope of the binding. The binding will have an empty environment when evaluated, but extend the environment of the body of the let expression with second |-> BoolV(true).

[] |-
(second (or false true))

 

4. We exit the let binding scope and enter the let body sub-scope.

[first |-> BoolV(false), second |-> BoolV(true)] |-
(or first second)

 

5. Evaluate and return BoolV(true).

 

 

Example 4:

(let ((x 5))     
  (+ (let ((y 2) (x 7))    
       (+ x y)
     )
     x
  )
)

 

1. Initially empty environment.

[] |-
(let (
      (x 5)
     )     
  (+ (let (
           (y 2) 
           (x 7)
          )    
       (+ x y)
     )
     x
  )
)

 

2. Evaluate the outer let expressionm so we enter the sub-scope of the binding. The binding will have an empty environment when evaluated, but extend the environment with x |-> NumV(5).

[] |-
(x 5)

 

3. We exit the let binding scope and enter the let body sub-scope.

[x |-> NumV(5)] |-
(+ (let (
         (y 2) 
         (x 7)
        )    
     (+ x y)
   )
   x
)

 

4. We first enter the sub-scope of the first operand of the binary operation +.

[x |-> NumV(5)] |-
(let (
      (y 2) 
      (x 7)
     )    
  (+ x y)
)

 

5. We evaluate the let bindings. So enter the sub-scope of the first let binding. Extend with y |-> NumV(2). 여기서 extend 하는 거는 (y 2)의 environment.

[x |-> NumV(5)] |-
(y 2)

 

6. We enter the sub-scope of the second let binding. The second binding does not contain the value of the first binding in its environment during interpretation. Furthermore, we now have a let binding with the same name as a binding in the environment. This means that the new let binding will shadow the binding in the environment. Thus, during the evaluation of the body of the let expression, binding x will have value NumV(7).

[x |-> NumV(5)] |-
(x 7)

 

7. We exit the let binding scope and enter the let body sub-scope (new environment - 다 포함되어 있는 environment).

[x |-> NumV(7), y |-> NumV(2)] |-
(+ x y)

 

8. We evaluate x + y and return NumV(9).

 

9. We move to the super-scope, which contains a different environment.

[x |-> NumV(5)] |-
(+ [[NumV(9)]]
   x
)

 

10. We fetch x from the current environment and return x + NumV(9), which is NumV(14).

 

 

 

Closures

Example 1:

(
  (lambda (x y)
     (if (num< x y)
         x 
         y
     )
  )
  2 3
)

 

1. Initially empty environment.

[] |-
(
  (lambda (x y)
     (if (num< x y)
         x 
         y
     )
  )
  2 3
)

 

2. First task: evaluate the body of the application so enter that sub-scope

[] |-
(lambda (x y)
   (if (num< x y)
       x 
       y
   )
)

 

3. Since the body of the application is a lambda, we evaluate it to a ClosV(), which will also keep the current environment of the application. Next, we evaluate the argument expressions under the environment of the application.

First argument:

[] |-
2

 

Second argument:

[] |-
3

 

4. We continue to evaluate the lambda inside the ClosV(), so we extend the environment inside the closure with the evaluated values of the lambda arguments, meaning we extend [ ] to [x |-> NumV(2), y |-> NumV(3)].

[x |-> NumV(2), y |-> NumV(3)] |-
(if (num< x y)
    x 
    y
)

 

5. We enter the condition of the if-expression to determine how it will evaluate.

[x |-> NumV(2), y |-> NumV(3)] |-
(num< x y)

 

6. We fetch x and y from the environment and end up with x < y being BoolV(true). So we evaluate the first statement of the body.

[x |-> NumV(2), y |-> NumV(3)] |-
x

 

7. NumV(2) returned.

 

 

 

Example 2:

(
  (lambda (x)           
     (                  
       (lambda (x y)      
          (+ x 1)       
       ) 
       2 4
     )
  ) 
  3
)

 

1. Initially empty environment

[] |-
(
  (lambda (x)           
     (                  
       (lambda (x y)      
          (+ x 1)       
       ) 
       2 4
     )
  ) 
  3
)

 

2. First task: evaluate the body of the application, so we enter that sub-scope.

[] |-
(lambda (x)           
   (                  
     (lambda (x y)      
        (+ x 1)       
     ) 
     2 4
   )
) 

 

3. Since te body of the application is a lambda, we evaluate it to ClosV(). Next, we evaluate the argument expressions.

First argument: 

[] |-
3

 

4. We now evaluate the lambda inside the ClosV(). We extend the environment inside the closure with the evaluated values of the lambda arguments. This means we extend [ ] with [x |-> NumV(3)].

[x |-> NumV(3)] |-
(                  
  (lambda (x y)      
     (+ x 1)       
  ) 
  2 4
)

 

5. It's an application so we have to evaluate the body of the application, so we enter tht sub-scope. 

[x |-> NumV(3)] |-
(lambda (x y)      
   (+ x 1)       
)

 

6. Since the body of the application is a lambda, we are going to evaluate it to a ClosV(), which will also keep the current environment of the application ([x |-> NumV(3)]). Then, we evaluate the argument expressions under the environment of the application.

First argument:

[x |-> NumV(3)] |-
[] |-
2

 

Second argument:

[x |-> NumV(3)] |-
[] |-
4

 

7. We then evaluate the lambda inside the ClosV(). We extend the environment inside the closure with the evaluated values of the lambda arguments. Since both environments have the same binding x, we apply name-shadowing.

[x |-> NumV(2), y |-> NumV(4)]
(+ x 1)

 

8. Return NumV(3).

 

 

Scoping

Example 1:

y is a variable bound to the value NumV(41).

(let (
       (f (lambda (x) (+ x y)))
     )
  (let (
         (y 0)
       )
    (f 1)
  )
)

 

1. Initial environment with y |-> NumV(41)

[y |-> 41] |-
(let (
       (f (lambda (x) (+ x y)))
     )
  (let (
         (y 0)
       )
    (f 1)
  )
)

 

2. We first evaluate the bindings of the outer let expression, so we enter the sub-scope. The let binding has a lambda as a value, so it evaluates it to ClosV() with an environment [y |-> NumV(41)]. We continue evaluating the body of the let expression next:

[y |-> NumV(41), f |-> ClosV(functionBody, [y |-> NumV(41)])] |-
(let (
       (y 0)
     )
  (f 1)
)

 

3. The binding is going to evaluate to NumV(0) and as a result shadow the existing environment's y binding:

[y |-> NumV(41), f |-> ClosV(functionBody, [y |-> NumV(41)])] |-
(y 0)

 

4. We exit the let binding scope and enter the let body sub-scope.

[y |-> NumV(0), f |-> ClosV(functionBody, [y |-> NumV(41)])] |-
(f 1)

 

5. The body of the let expression is an application, so we evaluate it. We fetch f from the environment. The functioBody inside the environment is (lambda (x) (+ x y)).

[y |-> NumV(0), f |-> ClosV(functionBody, [y |-> NumV(41)])] |-
f

 

6. So we evaluate the argument of the application

[y |-> NumV(0), f |-> ClosV(functionBody, [y |-> NumV(41)])] |-
1

 

7. When we interpreted the closure, we received access to its environment. Therefore, the application argument is going to extend the environment of the closure ([y |-> NumV(41)]). Hence, y is still NumV(41) due to the fact that Paret uses lexical scoping:

[y |-> NumV(41), x |-> NumV(1)] |-
(+ x y)

 

8. NumV(42) returned

 

Q. Explain how an interpreter could evaluate to NumV(1) instead of NumV(42). Discuss why such an interpretation strategy could be confusing. 

The interpreter could evaluate the result to NumV(1) if we were to use dynamic scoping. This would mean that the values of the identifiers are to be determined at run-time (during interpretation). 

 

 

Example 2:

(
  (
    (lambda (f) 
      (lambda (x) (f x))
    ) 
    (lambda (y) (* y x))
  ) 
  16
)

 

The program is invalid under static scope and will throw an InterpException.

 

Example 3:

(let ((f (lambda (g) (g x))))
  (let ((x 2) (y 3))
    (f (lambda (y) (+ y 1)))
  )
)

NumV(3)

 

 

 

Currying

Example 1: Transform this to curried version.

(lambda (x y z)
   (* (* x y) z)
)

 

1. We start by creating a lambda, which returns the given lambda. 

(lambda ()
  (lambda (x y z)
     (* (* x y) z)
  )
)

 

2. We move x to the outer lambda. So, we have curried the first identifier.

(lambda (x)
  (lambda (y z)
     (* (* x y) z)
  )
)

 

3. Approach the same method for y. => Curried version

(lambda (x)
  (lambda (y)
     (lambda (z)
        (* (* x y) z)
     )
  )
)

 

Q. Create an application of your curried lambda, which is able to find the product of the numbers 30, 40 and 50.

 

 

(
   (
      (
         (lambda (x)
            (lambda (y)
               (lambda (z)
                  (* (* x y) z)
               )
            )
         )
         30
      )
      40
   )
   50
)

 

 

 

Example 2: Give a general approach of converting a curried lambda expression to its uncurried equivalent.

This can be easily achieved by “merging” curried lambdas the following way. Suppose you have these 2 nested lambdas:

(lambda (first)
   (lambda (second)
      ...
   )
)

 

We can merge them by putting both identifiers in a single lambda, while maintaining the body of the inner lambda:

(lambda (first second)
   ...
)

 

Repeat until the lambad is uncurried.

 

 

Example 3:

(
  (
    (lambda (currywurst)
      (lambda (ketchup)
        (+ currywurst ketchup)
      )
    )
    20
  )
  22
)

 

1. Initially empty environment

[] |-
(
  (
    (lambda (currywurst)
      (lambda (ketchup)
        (+ currywurst ketchup)
      )
    )
    20
  )
  22
)

 

2. First task: Evaluate the body of the application. So we enter the sub-scope.

[] |-
(
  (lambda (currywurst)
    (lambda (ketchup)
      (+ currywurst ketchup)
    )
  )
  20
)

 

3. Since the body of the outer application is another application, we evaluate the body of the inner application. So we enter the sub-scope for the inner application.

[] |-
(lambda (currywurst)
  (lambda (ketchup)
    (+ currywurst ketchup)
  )
)

 

4. Since the body of the inner application is a lambda, we evaluate it to a ClosV(), which will also keep the current environment of the application. Next, we evaluate the argument expressions under the environment of the application.

First argument:

[] |-
20

 

5. After evaluating the arguments of the application, we continue to evaluate the lambda inside the ClosV(). To achieve this, we extend the environment inside the closure with [currywurst |-> NumV(20)].

[currywurst |-> NumV(20)] |-
(lambda (ketchup)
  (+ currywurst ketchup)
)

 

6. Since the body of the lambda is a lambda, we evaluate it to ClosV(), which will also keep the current environment [currywurst |-> NumV(20)]. We are now entering the super-scope of the outer application and we are returning this new closure lambda. So now we evaluate the argument of the outer application. The environment is empty, since the outer application has an empty environment. 

[] |-
22

 

7. Once evaluated, we are going to extend the closure’s environment [currywurst |-> NumV(20)] with the new environment [ketchup |-> NumV(22)].

[currywurst |-> NumV(20), ketchup |-> NumV(22)] |-
(+ currywurst ketchup)

 

8. NumV(42) returned

 

 

Rec-lam

(let
  ((fibbonacci (rec-lam fib (n)
      (if (num= n 0)
        0
        (if 
            (num= n 1)
            1
            (
              + 
              (fib (- n 1)) 
              (fib (- n 2))
            )
        )
      )
  )))
  (fibbonacci 5)
)

 

Recursion 가능하게 해 줌. 

 

 

 

Mandatory Assignment

Desugarer와 Interpret 구현하기

Desugarer: ExprExt → ExprC

Interpreter: ExprC → Value

 

 

1. Basics

desugar:

case TrueExt() => TrueC()
case FalseExt() => FalseC()
case NumExt(n) => NumC(n)
case NilExt() => NilC()

 

interp:

case TrueC() => BoolV(true)
case FalseC() => BoolV(false)
case NumC(n) => NumV(n)
case NilC() => NilV()

 

 

 

2. Unary Operators

desugar:

case UnOpExt(s, e) => s match {
  case "-" => MultC(NumC(-1), desugar(e))
  case "not" => IfC(desugar(e), FalseC(), TrueC())
  case "head" => HeadC(desugar(e))
  case "tail" => TailC(desugar(e))
  case "is-nil" => IsNilC(desugar(e))
  case "is-list" => IsListC(desugar(e))
  case _ => throw new DesugarExceptionImpl("UnOp")
}

 

interp:

case HeadC(e) => interp(e, nv) match {
  case ConsV(h, t) => h
  case _ => throw new InterpExceptionImpl("Head")
}
case TailC(e) => interp(e, nv) match {
  case ConsV(h, t) => t
  case _ => throw new InterpExceptionImpl("Tail")
}
case IsNilC(e) => interp(e, nv) match {
  case NilV() => BoolV(true)
  case ConsV(h, t) => BoolV(false)
  case _ => throw new InterpExceptionImpl("Is Nil")
}
case IsListC(e) => interp(e, nv) match {
  case NilV() => BoolV(true)
  case ConsV(h, t) => BoolV(true)
  case _ => BoolV(false)
}

 

여기에 이제 추가된 거는 environment nv이다. 이 environment는 List of binding을 가지고 있다.

IsNilC(e)는 NilV()일 때만 BoolV(true), 그리고 리스트, 즉 ConsV(h, t)이면 BoolV(false) 아니면 Exception 리턴.

Is ListC(e)는 NilV()일 때도 BoolV(true), 리스트일 때도 BoolV(true), 아니면 BoolV(false) 리턴.

 

 

3. Binary Operators

desugar:

case BinOpExt(s, l, r) => s match {
  case "+" => PlusC(desugar(l), desugar(r))
  case "-" => PlusC(desugar(l), MultC(NumC(-1), desugar(r)))
  case "*" => MultC(desugar(l), desugar(r))
  case "and" => IfC(desugar(l), desugar(r), FalseC())
  case "or" => IfC(desugar(l), TrueC(), desugar(r))
  case "num=" => EqNumC(desugar(l), desugar(r))
  case "num<" => LtC(desugar(l), desugar(r))
  case "num>" => LtC(desugar(r), desugar(l))
  case "cons" => ConsC(desugar(l), desugar(r))
  case _ => throw new DesugarExceptionImpl("Bin-Op")
}

 

interp:

case PlusC(l, r) => (interp(l, nv), interp(r, nv)) match {
  case (NumV(n1), NumV(n2)) => NumV(n1+n2)
  case _ => throw new InterpExceptionImpl("Plus")
}
case MultC(l, r) => (interp(l, nv), interp(r, nv)) match {
  case (NumV(n1), NumV(n2)) => NumV(n1 * n2)
  case _ => throw new InterpExceptionImpl("Mult")
}
case EqNumC(l, r) => (interp(l, nv), interp(r, nv)) match {
  case (NumV(n1), NumV(n2)) => BoolV(n1 == n2)
  case _ => throw new InterpExceptionImpl("EqNum")
}
case LtC(l, r) => (interp(l, nv), interp(r, nv)) match {
  case (NumV(n1), NumV(n2)) => BoolV(n1 < n2)
  case _ => throw new InterpExceptionImpl("Less Than")
}
case ConsC(l, r) => ConsV(interp(l, nv), interp(r, nv))

 

 

 

4. If Condition

desugar:

case IfExt(c, t, e) => IfC(desugar(c), desugar(t), desugar(e))

 

interp:

case IfC(c, t, e) => interp(c, nv) match {
  case BoolV(true) => interp(t, nv)
  case BoolV(false) => interp(e, nv)
  case _ => throw new InterpExceptionImpl("If")
}

 

 

 

5. Function Expressions

desugar:

case FdExt(params, body) => FdC(params, desugar(body))

 

interp:

case fdc@FdC(params, body) => ClosV(fdc, nv)

 

그래머를 보면 ClosV는 다음과 같다.

ClosV(f: FdC, env: Environment)

 

그리고 assignment description에 다음과 같이 써져있다. 

Lambda expressions should return function closures (ClosVs) with the current environment.

따라서, variable fdc를 만든다. 이때 이 fdc의 타입은 FdC이고 (params, body)를 가지고 있다.

그리고나서 Closure에 이 fdc와 현재 environment인 nv를 넣어주면 된다.