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

[Pal-Kristian Engstad <pal_engstad@naughtydog.com>]

I've probably got the nomenclature wrong, but this is how I would 
explain it. I do think this is an advanced topic though - it definitely 
does not belong in an introductory programming course.

Caml, and many other languages, has the interesting concept of being 
able to create functions on-the-fly. That is to say, you can define an 
auxiliary helper-function within the function you are working on. This 
is a very powerful concept, because it allows you to re-factor code 
quite easily. Somewhere along the line, you see that: "Oh, I need to do 
.... another time, this time using variable ..." If this happens, you 
can simply create a sub-function within the function, and start using that.

Now, a function needs input parameters to work. However, it would be 
quite tedious to have to specify all the parameters for all your 
sub-functions. Therefore, Caml lets you use variables from the 
"outside", or the outer scope, as we say. An example:

# type env = { mutable scale : int; mutable offset : int };
type env = { scale : int; offset : int; }
# let work env a b =
    let linear x = env.scale * x + env.offset in
       linear a + linear b
;;
val work : env -> int -> int -> int = <fun>
#

As you can see in this contrived example, we introduced a new function 
linear, since we needed to use that calculation twice. But notice also 
that we did not specify the "env" variable as an input to linear. Thus, 
functions in OCaml are slightly more complicated than appears at first 
sight. Now, in OCaml it is also possible to return functions. For 
instance, we could change the above function to the following:

# let work' env =
    let linear x = env.scale * x + env.offset in
       (fun a b -> linear a + linear b)
;;
val work' : env -> int -> int -> int = <fun>

So, when you call "work' env", you get returned a function that adds 
together the results of the "linear" functions. [Note: For the observant 
reader, work' is actually the same function as work.].

Example:

# let env1 = { scale = 0; offset = 1 };;
val env1 : env = {scale = 0; offset = 1}
# let fun = work' env1;;
val fun : int -> int -> int = <fun>
# fun 1 2;;
- : int = 2
# env1.scale <- 1;;
- : unit = ()
# fun 1 2;;
- : int = 5

The first call to fun works, because: fun 1 2 = linear 1 + linear 2 = 
(env.scale * 1 + env.offset) + (env.scale * 2 + env.offset) = 
(0*1+1)+(0*2+1) = 2. But, in the second call to fun, the environment has 
changed, now env.scale is 1, so fun 1 2 = linear 1 + linear 2 = 
(1*1+1)+(1*2+1) = 5.

So, to conclude. For this to work, the function fun can not only depend 
on the input arguments. The function must retain a pointer to the 
environment that was used to create it. We call this a "closure". 
Scoping in this respect is important, because it tells us which external 
variables are captured by the function. This is cool, because it means 
that we don't have to use "function objects" (C++) or anything like that.

Flame on,

PKE.

Loup Vaillant wrote:
> My brother is currently learning Camllight at the Toulouse 3
> university, France. Five years ago, I followed the same course.
>
> 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.)
>
> -> They talk about closures, even in the case of pure functional
> style, even in the absence of free variable (except the built in
> constructions, such as '+').
> -> They take hours and hours of boring an silly looking exercises
> about environment, so we can understand how important environments
> are.(we even had to learn a specific syntax to talk about them).
> -> The promised power of the language is completely overlooked. Even
> the crippled Pascal on my calculator looked more powerful.
>
> Luckily, I had later a professor, who showed us the real power of
> Caml. He didn't talked about environments.
>
> So here are a few questions:
> -> Is lexical scope that important when learning pure functional 
> programming?
> -> Are environments helpful (even the slightest bit) when teaching
> lexical scope?
> -> Where does this idea come from? I have not read a single book, as
> single article nor blog talking about environments.
> -> How can we teach lexical scope? Is there a simple solution, the
> kind of a first year student can understand in less than an hour?
>
> Thanks,
> Loup
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>

-- 
Pål-Kristian Engstad (engstad@naughtydog.com), Lead Programmer, ICE
team, Naughty Dog, Inc., 1601 Cloverfield Blvd, 6000 North,
Santa Monica, CA 90404, USA. Ph.: (310) 633-9112.

"Most of us would do well to remember that there is a reason Carmack
is Carmack, and we are not Carmack.",
                       Jonathan Blow, 2/1/2006, GD Algo Mailing List