Home > Lisp, OCaml, Scheme > Value capture in Lisp

Value capture in Lisp

In one of my previous posts I’ve told about how (define) works and how (lambda) works. Main difference is that (define) evaluates second argument, and (lambda) doesn’t evaluate anything, it just binds all variables to specific scope. Variables could even be defined after definition of (lambda)! See following example (in Scheme):

>(define f (lambda (x) (+ x y)))

>(f 5)

Error: variable y is not bound.

>(define y 5)

>(f 5)

10

In this example, x is bound to scope of function’s arguments, and y is bound to local scope. Each time the function is applied, it tries to use (evaluate) variable in initially defined scope.

The story continues in OCaml. Now I’m reading a book about this language, and I was surprised to know that it is implemented exactly in the way I was mistakenly thinking about Lisp earlier. So, function definition in OCaml doesn’t capture the scope, it captures the value! Look:

# let a = 10;;
val a : int = 10
# let add2a x = a + x ;;
val add2a : int -> int = <fun>
# add2a 5;;
– : int = 15
# let a = 20;;
val a : int = 20
# add2a 5;;
– : int = 15

So, we have fundamental difference between OCaml and Lisp. I don’t know which behaviour is better, and I don’t bother. I just know how it will behave in both languages. But, my next idea was: is it possible to achieve value capture in Lisp, and scope capture in OCaml ?

Value capture in Lisp is, of course, possible. It is done by using (lambda) inside (let). Look:

>(define x 5)

>(define f
    (let
        ((x1 x))
      (lambda (y) (+ x1 y)))
    )

>(f 5)

10

>(define x 10)

>(f 5)

10

Let allows us to create local scope, and each clause in let is like (define), so it evaluates variable. In this way we achieve value capture in scope accessible only from body of function.

Regarding OCaml: I’m sure that “scope capture” will not work. The reason is that OCaml, unlike Lisp, is a language with static type checking. Since any variable could be re-defined with different type after funciton definition, OCaml implements value capture to avoid type errors.

Advertisements
Categories: Lisp, OCaml, Scheme
  1. February 14, 2008 at 4:50 pm

    Yes, I’ve been recently faced with a problem in OCaml which would have required scope capture rather than value capture — something related to exceptions and which I won’t detail. As you correctly state, OCaml implements value capture and not scope capture and OCaml programmers have a strong dislike for anything like scope capture. In their minds (and mine), scope capture make programs harder to trust, because when you have defined a value x as 5, you could end up with a program in which value is 10 without the slightest indication that this could happen.

    Now, there are two ways to get around this absence of scope capture: OCaml macros (which are comparable to Lisp macros, although somewhat more heavy-handed due to the more complex syntax) and references (which are comparable to variables in just about every language outside the ML family).

    I won’t detail the macros here, but let’s take a look at references:

    # let a = ref 10; (*a is worth 10 for now but it may change at a later date*)
    val a : ref int = {value : 10}
    # let add2a x = !a + x; (*!a is the value of a at the instant of evaluation*)
    val add2a : int -> int =
    # add2a 5;;
    – : int = 15
    # a := 20;;
    – : unit = ()
    # add2a 5;;
    – : int = 25

    The big difference is that you have indicated during the creation of a that this name can represent different values during its execution, all of them integers. As always in OCaml, there’s no such thing as an undefined variable during execution, nor as a variable without content.

    This is the “clean” technique to provide something related to scope capture. It is not purely functional, as it involves altering the state of the system — just as define alters the state of the system in Lisp. There’s an even cleaner technique (monads) to encapsulate this impure and turn it into purely functional code, but that’s an other story.

  2. kmatveev
    February 15, 2008 at 11:57 am

    Thanks a lot for a comment!

    When I wrote that, I’ve just started reading the book. Now I’ve re-read this post again, and quickly understood myself that references are the way to achieve “scope capture” in OCaml.

    Of course you are right then you say that references are not purely functional. But I think that since in functional programming there is no state change, so difference between value capture or scope capture doesn’t matter at all.

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: