Re: [Caml-list] How must we teach lexical scope?

[ls-ocaml-developer-2006@m-e-leypold.de]

"Loup Vaillant" <loup.vaillant@gmail.com> writes:

> 2007/3/28, ls-ocaml-developer-2006@m-e-leypold.de
> <ls-ocaml-developer-2006@m-e-leypold.de>:
>>
>> "Loup Vaillant" <loup.vaillant@gmail.com> writes:
>>
>> > Personally, I think environments are about the implementation of
>> > lexical scope, not  its specifications. Therefore, teaching them in
>> > the first year of a programming course is premature. I may be wrong,
>> > so I am trying to verify that.
>>
>> Personally I think you're wrong here. Environments (as mapping from
>> identifier to values) represent the context in which a given
>> expression must be read and interpreted (in both senses). I cannot
>> imagine a way to do so precisely without using a similar
>> abstraction. With horror I remember some learn-to-program books I read
>> in my youth and which tried to talk about scope by talking about
>> wether a identifier is "valid" or something like this:
>
> Err, I didn't receive your quotation...

Not sure i know what you mean. If you mean "Which books are you
alluding to?" -- thankfully I've forgotten that. What is left is a
memory of really complicated attempts to explain scope and shadowing
(?) of indentifiers -- quite unnecessary if they had concentrated on
free variables first and then explained how "free variables" become
bound (by wrapping something around them that delivers a
environment). Instead there were really jumbled attempts to explain
when identifiers are "valid" and "invalid" or seomthing like
this. Never mind, the details don't matter -- what matters is, that my
conviction that scope can only be explained by introducing something
like an environment into the discussion stems from that experience.

>> horrible. Talking about free variables and environments on the other
>> side makes it very easy to see which parts of an expression must get
>> "meaning" by being interpreted in some context (environment). I find
>> that rather useful.
>>
>> Grasping the idea of a free variable (perhaps in an informal way) and
>> applying the ideas of environment(s) should take a reasonably bright
>> student hardly more than an hour (but I might be wrong).
>>
>> Concerning your
>>
>> > I don't understand the way were are taught lexical scope. Our
>> > professors used "environments", where free variable would suffice.
>> > (An environment is the set of defined values at a given time. The
>> > environment of a value is the environment of when this value is
>> > defined.)
>>
>> -- I'd say that environment and free variables are "dual" or
>> complementary concepts. One is not useful without the other.
>
> I find the concept of free variable a bit more natural, and far less verbose.

Free variables vs. environments are not alternatives. You need both.


>> From what you write, I'm not sure, the course (at Toulouse 3) you've
>> been talking about is just badly structured, whether the problem is at
>> yours or your brothers side or whether (I suggest to consider that) not
>> all students are as bright as you or your brother and therefore things
>> can get a bit repetitive.


> In my second year, I took a rather special course (IUP SI, for those
> who know it). We students therefore came from different horizons, and
> the vast majority has not been exposed to any functional language yet
> (although many has been exposed to Pascal or C already).  In less than
> two weeks, we almost covered the hole first semester of my first year
> (not a single word about environments, however). It felt reasonably
> fast, and no one was lagging behind.

Well -- they must have explained let and lambda/fun somehow: Even if
they didn't call it environment, there it was.

>> On the other side
>>
>> > -> Where does this idea come from? I have not read a single book, as
>> > single article nor blog talking about environments.
>>
>> I wonder that you have not heard about environments before. Perhaps
>> it's not your part yet to improve teaching in that area
>> :-). Nonetheless: If you have a suggestion how to talk about lexical
>> scope or the "meaning" of an expression without resorting to
>> environments, I'd be interested to hear more about it.


> Actually, I have. The first thing we see when learning Caml is the
> interactive loop (Which I believe is a good thing). 

I completely agree. :-)

> So we define
> values one after the other. While we stick to a pure functional style,
> a value (be it a function or not) never, ever change. 

Yes.

> The worse we can
> do to it is to render it unaccessible, by defining a new value of the
> same name. So, to explain this session:


>
> #let a = 3;;
> a: int = 3
>
> #let f x = x + a;;
> f: int -> int = <fun>
>
> #f 5;;
> -: int = 8
>
> # let a = 451;;
> a: int = 451
>
> #f 5;;
> -: int = 8
>
> we just have to say: "As long as we do not redefine a value, it does
> not change. The function 'f' didn't change, because it has not been
> redefined. All happened as if the 'a' was replaced by its value at
> that moment, '3', in the definition of 'f'."

It's the "value at this moment" which makes me a bit suspicious ...

> Pretty harsh, I admit, but you get the idea. One can even explain that
> the value is not redefined, just covered, if needed.
>
> Better (I think) is to teach the notion of binding from the very
> beginning, and draw a sharp distinction between values and symbols
> (even if these notions are less crucial in ML than in Lisp).

Exactly. Environments associate symbols with values :-).

> Then:
> "Values never change, but symbols can be reassigned new values. So,

No reassignment. Somehow you succeed to put really big holes in your
own concept. There is no "assigment" in purely functional: That would
be imperative. The Ocaml top level example is also a really bad one,
since every let produces a new envionment w/o that being obvious
syntactically. If you forget about the Ocaml top level for a moment,
there is no assigment: Expressions just get evaluated in different
environments. Like in

 let a = 5
 in 
   let f x = x * x * a
   in
      ((f 5), (f 8)

the x didn't "change" between the to calls to f, but the parameter
list of f was used to produce 2 different environments for both
evaluations from the definition environment of f. Exactly the same
happens in the Ocaml top level, only the implicit nesting introduced
after every toplevel let is not so obvious.

I find it really difficult to explain all this without coming up with
something like "environment".

> the function known as 'f' has not changed, even if the value know as
> 'a' in no longer '3'."

But 

> #let a = 3;;
> a: int = 3
>
> #let f x = x + a;;     [1]
> f: int -> int = <fun>
>
> #f 5;;
> -: int = 8
>
> # let a = 451;;
> a: int = 451
>
> #f 5;;                 [2]
> -: int = 8

... the 'a' in [1] is still '3' as evidenced by [2]. How do you
explain that without referring to the place / cirumstances (the
environment!) under which f has been defined?

> The notion of lexical scope become critical when we begin to have free
> <and> mutable variables. 

You unfortunately somewhat cryptic example illustrates (in my eyes)
that scope becomes critical even in the purely functional
case. Mutable only introduces a new concept: That of a (mutable)
memory location, a reference to which is bound to the identifier. That
makes scoping a bit more interesting since referential transparency
isn't working any more (i.e. w/o reference to a global state), but per
se has nothing to do with lexical scoping. IMHO.

> From that point, I think one have no choice (well, it is easier if
> students can understand the difference between binding and
> assignment).

> I just hope that any student can distinguish the name and the thing.

So do I :-). 

But perhaps I understand your problem better now: The difference
you're wanting to make is the substitution of symbols by values at
definition time vs. at evaluation time (I hope it is clear what I want
to say). But you'll have to explain substitution at evaluation time
anyway (when a function is called and the formal parameters are
bound). I don't understand what your attempt to avoid to talk about an
environment (from which a comes in the example above) will buy you.

Regards -- Markus