Evaluation in Scheme

Question

ok, i have this problem here. i was asked to write a function in Scheme, that takes an "environment", and an expression and it returns the value of this expression, for the variable bindings found in the enviroment.

and a definition of a boolean expression is this according to the question below.

edit sorry my question is what does it mean by "it takes an environment" as an argument and what exactly does the function need to do?

evaluate for example "T OR F" and return "F" ???

"<expr> ::= <boolean>
          |<variable>
          |(not <expr>)
          |(or <expr> <expr>)
          |(and <expr> <expr>"

Answer 1

An environment is basically a dictionary of variable names to values. So given the environment

var1 = #t
var2 = #f
var3 = #t

and an expression

(or var2 (and T (or var1 var3)))

You would need to substitute the given values of var1, var2, and var3 into the expression, and then evaluate the expression.

Your function will probably be given the environment as some sort of Lisp structure, probably an alist, as one of its parameters.

Answer 2

From what I can determine you have been asked to implement eval.

So you should for starters have:

(define (eval expr env)
  ... )

where expr can be any of the forms you mention and env would keep the symbols defined (possibly a association list).

The first 2 cases are relatively trivial, the 3rd one, application of the not procedure should also be easy, given not will be in the environment (eg (list (cons 'not not))).

But the harder part lies in the last 2. Both of those are macros, and will require some expansion. The standard definitions/expansions of those should have been given to you. Once expanded, you can simply call eval recursively to evaluate the expanded expression.

Good luck :)

Edit:

Both and and or expands to if, so you will need to implement that too.

Answer 3

By "environment" they probably mean the equivalent of "scope" in other languages. Consider the following C fragment:

if (7 < 100)
{
   int j = 2;
   if (j < 4)
   {
      int k = 7, j = 14;
      printf("k = %d, j = %d\n", k, j);
   }
}

Note that in the outer scope (marked out by the outer set of braces) the only variable is j. In the inner scope there is a new j and a k. So there are three variables here, the outer j, and the inner j and k.

One way of implementing this is to define a scope to be a list of "environments". As you enter a new block, you put another "environment" in your list. When looking up variables by name, you look first in the most recently added "environment". If it isn't found there, you move along the list of environments to the next and look there, and so on.

An "environment" itself is often just a list of pairs, matching up names of variables with values. So it sounds like you are being asked to pass such a list to your function, each pair giving the symbol for a boolean variable and its value. Based on which variables are currently "in scope", you fetch their values out of the environment and use them in the expressions you are evaluating (according to that expression grammar you've been given).

In your case, it sounds like you aren't being asked to worry about which enviroments are in scope. You just have one environment, i.e. one list of pairs.

Sounds like a fair bit of work, good luck!

One reference that might help is:

http://michaux.ca/articles/scheme-from-scratch-bootstrap-v0_9-environments