Return-Path: <kfoury@cs.bu.edu> Received: from cs.bu.edu (cs [128.197.12.2]) by cs3.bu.edu (8.12.11/8.12.11) with ESMTP id i96HctVX001281; Wed, 6 Oct 2004 13:38:56 -0400 Received: from cs.bu.edu (kfoury@fiddle [128.197.10.114]) (authenticated bits=0) by cs.bu.edu (8.12.2/8.12.2) with ESMTP id i96HcusG016535; Wed, 6 Oct 2004 13:38:57 -0400 (EDT) Sender: kfoury@cs.bu.edu Message-ID: <41642DAB.4BC91485@cs.bu.edu> Date: Wed, 06 Oct 2004 13:38:51 -0400 From: "Assaf J. Kfoury" <kfoury@cs.bu.edu> Organization: Boston University X-Mailer: Mozilla 4.78 [en] (X11; U; SunOS 5.8 sun4u) X-Accept-Language: en To: Yarom Gabay <yarom@cs.bu.edu> CC: cs520@cs.bu.edu Subject: Re: cs 520 implementation References: <000a01c4abc5$09cf3ce0$0200a8c0@YaromAtHome> Content-Type: multipart/alternative; boundary="------------69CFB2651D1861A8BF39F92A" X-Spam-HitLevel: X-Spam-DCC: : cs3.bu.edu 1074; Body=19 Fuz1=19 Fuz2=19 X-Spam-Checker-Version: SpamAssassin 2.64 (2004-01-11) on cs3.bu.edu X-Spam-Level: X-Spam-Status: No, hits=0.1 required=10.0 tests=AWL,HTML_MESSAGE autolearn=ham version=2.64 X-Spam-Pyzor: Reported 0 times. Status: X-Mozilla-Status: 8011 X-Mozilla-Status2: 00000000 X-UIDL: 411f69ec0000104c
Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit
Thanks for the message. It depends on what
you mean by "substitution": My point is that,
with an environment, you will only need to do
lookups, one at a time (to find out the normal
form, i.e. value, associated with a free variable
occurrence x when you want to evaluate x).
So, you will never need to carry out a substitution
in the sense of substituting a term for all occurrences
of the same free variable in the body of a lambda
abstraction.
EXCEPT, possibly, at the very end of the evaluation
when you are ready to return an output. For example,
on input
(lambda x. lambda y. y x x) (lambda x. x)
if you use the idea of an environment, your interpreter
will reach a point when it wants to return the final
term
(lambda y. y x x)
relative to the environment [x : (lambda x. x) ]. What you
should really return is the same final term but with all free
occurrences of x replaced by (lambda x. x), i.e.,
(lambda y. y (lambda x. x) (lambda x. x))
But note this substitution will occur right before returning
an output, which is tantamount to emptying the
environment.
Assaf
PS: I send a cc to the entire class list.
Yarom Gabay wrote:
> Hi Assaf, Going back to what we talked about the interpreter
> resulted lambda with free variables. I ran the foolowing on both SCM
> and DrScheme: ( (lambda (x) (lambda (y) x)) (lambda(x) x) )What we
> expected was (lambda(y) (lambda(x) x)) The result was: #<CLOSURE
> <anon> (y) x> I believe that in order to get the result of
> (lambda y. lambda x. x) when working with any sort of environment,
> one would have to use substitution mechanism at some point. Do you
> agree? Thanks,Yarom.
This archive was generated by hypermail 2b29 : Fri Nov 19 2004 - 17:00:43 EST