Does substitution model require an environment

I am writing a tiny evaluator for Scheme.

I need to write the evaluator with substi开发者_开发知识库tution model, therefore no assignments like set! are to be used.

But since I still need to store primitive procedures and user-defined variable in some place, do I need an environment? If so, what is the difference between substitution model and environment model?

Thanks.

No -- for a plain substitution-based evaluator you do not need an environment. This is because as soon as you have a binding (eg, when you perform a function call) you immediately substitute the name with the value, so there is no need to keep the name->value mapping around. In fact, you can view an environment as a way to avoid the overhead involved with substitutions by caching them and performing them later instead. See PLAI for a textbook that follows this view -- in fact, it goes from substitutions to substitution caches, and only later does it change the terminology to environments.

But note that the issue of using set! is unrelated to all of this. When you consider set!, you first need to be clear on what level of set! you're talking about: if it's in the language that you're implementing rather than in the implementation itself, then it's possible to add that given any kind of a mutable value -- for example, in Racket you can use boxes and that's enough for implementing set! in the language. This is traditionally done in an environment-based evaluator, where the environment type is changed from mapping names to values to mapping names to locations (implemented as boxes or a similar mutable value). But that's not really necessary: you can still do that with a substitution-based evaluator where these boxes are becoming part of the domain of values that you're substituting. To give a concrete example, you could start with an expression like (using a scheme-like language):

(let ((x 1))
  (begin (set! x 2)
         (set! x 3)))

and instead of substituting 1 for x you would allocate a box holding 1, then substitute that same box resulting in

(begin (set! #<box> 2)
       (set! #<box> 3))

where the two #<box>es are that single box. (Note that this is not implementation code that I'm talking about, but expressions in the language that you're evaluating.) The reason that this is not usually done is that it can be confusing -- you need to represent values as boxes that can be substituted, those boxes are not something that is part of the source user program yet they are values that the interpreter should deal with (eg, the last #<box> is the return value -- but it's the value that you want to return, not the box), and you need to be careful about box identity (eg, it is important for the two boxes in the above to be the same box for the interpretation of the first set! to be visible in the second).

So doing this is not recommended if you're just learning about writing interpreters. If this is the case, then I suggest you just look in that textbook.

Yes you still need an environment because like you said you need to be able to store variables and such.

The substitution model is a way to help you see how a given procedure will be evaluated. For example, you can define the square function

(define (square x) (* x x))

With the substitution model, if you called

(square 4)

then you substitute the 4 into every occurrence of x in your function definition so

(* 4 4) => 16

The environment is used for you to visualise how variables and state are stored in your interpreter. So in a nutshell, the substitution model is used for helping you evaluate procedures while the environment is used to see how your interpreter will remember the variables and definitions that a user may define when they use your interpreter.