Chapter 7. Another Variation on let

Suppose we have a fairly complicated calculation to make. We'd like to compute intermediate values in order to simplify our code. For example:

> (let ((a 5)
>       (b (* a 2))
>       (c (- b 3)))
>      c)
Error: no binding for a in PScm::Env
[download]

It didn't work. The error occurs when attempting to evaluate (* a 2). Why? Well in much the same way as let fails for recursive definitions: because let binds its arguments in parallel, at the point that it is trying to evaluate (* a 2), it is still doing so in the environment prior to binding a.

letrec can't help here, because it sets up an environment with dummy values to evaluate its values in, which is OK if those values are closures that just capture that environment for later, but very bad if they're actually going to try to do any immediate evaluations with those dummy values.

7.1. Sequential Binding

Of course the solution is quite simple even using our existing let form: we just nest the let expressions so that each value expression gets evaluated in an environment where the previous value is already bound to its symbol:

> (let ((a 5))
>      (let ((b (* a 2)))
>           (let ((c (- b 3)))
>                c)))
7

That would give us a set of environments as in Figure 7.1.

Figure 7.1. Nested environments
figure

The outer let binds a to 5 to create Env2. The next let evaluates (* a 2) in the context of Env2 and creates Env3 with a binding of b to the result 10. The innermost let evaluates (- b 3) in Env3 and binds c to the result, creating Env4. In Env4 the final evaluation of c results in 7, which is the result of the expression.

While that works fine, it's rather ugly and verbose code. Wouldn't it be better if there was a variant of let that did all that for us, binding its variables sequentially? This variant of let is called let* (let-star) and is found in most lisp implementations.

7.2. let*

To implement let*, in the same way as we implemented letrec, we create a new sub-class of PScm::SpecialForm::Let and give it an Apply() method, then bind a symbol (let*) to an instance of that class in the initial environment. Our new class will be called PScm::SpecialForm::LetStar and here's that Apply() method.

 50 package PScm::SpecialForm::LetStar;
 51 
 52 use base qw(PScm::SpecialForm::Let);
 53 
 54 sub Apply {
 55     my ($self, $form, $env) = @_;
 56 
 57     my ($ra_symbols, $ra_values, $body) = $self->UnPack($form);
 58 
 59     return $body->Eval(
 60         $env->ExtendIteratively($ra_symbols, $ra_values));
 61 }

Again it only differs from the let and letrec implementations of Apply() in the way it extends the environment it passes to the Eval() of its body. In this case it calls the new PScm::Env method ExtendIteratively().

 39 sub ExtendIteratively {
 40     my ($self, $ra_symbols, $ra_values) = @_;
 41 
 42     my @symbols = @$ra_symbols;
 43     my @values  = @$ra_values;
 44     my $newenv  = $self;
 45 
 46     while (@symbols) {
 47         my $symbol = shift @symbols;
 48         my $value  = shift @values;
 49         $newenv = $newenv->Extend([$symbol], [$value]);
 50     }
 51 
 52     return $newenv;
 53 }

This method implements the algorithm we discussed earlier, creating a new environment frame for each individual binding, and evaluating the value part in the context of the previous environment frame. The last environment frame, the head of the list of frames rooted in the original environment, is returned by the method18.

7.3. Summary

This may all seem a bit academic, but let's remember that Perl supports both types of variable binding, let and let*, in the following way.

Parallel assignment like let is done in a list context:

my ($a2, $b2) = ($a * $a, $b * $b);

Sequential binding like let* is done by sequential assignment:

my $a = 5;
my $b = $a * 2;
my $c = $b - 3;

let has its uses, just as assignment in a list context does. For instance with parallel assignment it becomes possible to swap the values of variables without needing an additional temporary variable. In Perl:

($b, $a) = ($a, $b);
...

and in PScheme:

(let ((a b)
      (b a))
     ...)

Again, just for completeness, here's our 0.0.4 version of ReadEvalPrint() with the additional let* binding.

 31 sub ReadEvalPrint {
 32     my ($infh, $outfh) = @_;
 33 
 34     $outfh ||= new FileHandle(">-");
 35     my $reader = new PScm::Read($infh);
 36     while (defined(my $expr = $reader->Read)) {
 37         my $result = $expr->Eval(
 38             new PScm::Env(
 39                 let    => new PScm::SpecialForm::Let(),
 40                 '*'    => new PScm::Primitive::Multiply(),
 41                 '-'    => new PScm::Primitive::Subtract(),
 42                 if     => new PScm::SpecialForm::If(),
 43                 lambda => new PScm::SpecialForm::Lambda(),
 44                 letrec => new PScm::SpecialForm::LetRec(),
 45                 'let*' => new PScm::SpecialForm::LetStar(),
 46             )
 47         );
 48         $result->Print($outfh);
 49     }
 50 }

7.4. Tests

The additional tests for 0.0.4 are in t/PScm_LetStar.t which you can see in Listing 15.

Listing 15. t/PScm_LetStar.t
  1 use strict;
  2 use warnings;
  3 use Test::More;
  4 use lib 't/lib';
  5 use PScm::Test tests => 3;
  6 
  7 BEGIN { use_ok('PScm') }
  8 
  9 eval_ok(<<EOF, '1', 'let binds in parallel');
 10 (let ((a 1)
 11       (b 2))
 12      (let ((a b)
 13            (b a))
 14           b))
 15 EOF
 16 
 17 eval_ok(<<EOF, '2', 'let* binds sequentially');
 18 (let ((a 1)
 19       (b 2))
 20   (let* ((a b)
 21          (b a))
 22     b))
 23 EOF
 24 
 25 # vim: ft=perl

The first test proves that ordinary let binds in parallel, by doing the variable swapping trick. The second test demonstrates let* binding sequentially since the innermost binding of b to a sees the immediately previous binding of a to the outer b.

Full source code for this version of the interpreter is available at
http://billhails.net/Book/releases/PScm-0.0.4.tgz
Last updated Sun Mar 14 10:43:08 2010 UST
18

An alternative implementation would be to only create one new environment frame, then iteratively evaluate and bind each value in turn, in the context of that new environment.