Lexical scope and functions in Perl

This is a post to clear away some mental undergrowth before a deeper post on memoization in Haskell. It’s based on my reading of Chapter 3 of Higher Order Perl by Mark Jason Dominus. This is a great book.

The aim is to understand the following situation: in some programming language (that supports functions as first-class citizens), we have a function f which, given as input a function g, returns a new function g'. Typically g' will call g at some point, and for space efficiency, the code already present for g should be used, not duplicated as part of the code for g'. Suppose that we define g' using f, and that the language permits us to hack away behind the scenes and change the definition of g. Should this change g'? The answer under lexical scope seems unclear to me.

In Perl, the function g' can call g either by using its name, g(n), in which case the code for g is looked up in a global symbol table, or by using its address \&g. The behind the scenes hack is accomplished by changing the binding of the name g in the global symbol table. It seems right that in the former case g' changes after the behind the scenes hack, but in the latter case it does not, since the reference held by g' still points to the original code for g.

This distinction is crucial to the memoization subroutine in Section 3.5 of Dominus’ book, so can’t be dismissed as ‘well that’s a tricky but pointless thing to do’.

Here is an explicit example. Consider the following Perl code.

use warnings;
use strict;
use feature 'say';

my $constant = 42;
sub addGlobalConstant { my $n = shift; return $n + $constant; };
sub addLocalConstant  { my $constant = 42; my $n = shift; 
                        return $n + $constant; };
sub doubleFunction    { my $func = shift;
                        return sub {my $n = shift; return 2*$func->($n); }; 

my $f = \&addGlobalConstant;                    
my $g = doubleFunction(\&addGlobalConstant);
my $h = \&addLocalConstant;
my $k = doubleFunction(\&addLocalConstant);
sub t { my $n = shift; return addLocalConstant($n); };                    

sub evaluateAtThree    { say "f(3) = ",$f->(3)," g(3) = ",$g->(3),
                            " h(3) = ",$h->(3)," k(3) = ",$k->(3),
                            " t(3) = ",t(3); };

evaluateAtThree;                                           #45, 90, 45, 90
$constant = 10; evaluateAtThree;                           #13, 26, 45, 90
*addLocalConstant = \&addGlobalConstant; evaluateAtThree;  #13, 26, 45, 90
$k = doubleFunction(\&addLocalConstant); evaluateAtThree;  #13, 26, 45, 26

This defines function references f, g, h and k, and a function t some of which depend on a global variable, constant, initially 42. (In this discussion I’m omitting the scalar context signs $ from all variables and references.) Another variable, also called constant, also initially 42, is defined in the function addLocalConstant pointed to by h. So very roughly (too roughly, e.g. I’m treating the reference f as a function: the distinction is clear in the real code, since it has to be ‘called’ using the dereferencing syntax f->(arguments)):

  • f(x) = x + constant
  • g(x) = doubleFunction(f)(x)
  • h(x) = x + constant (where constant is defined in addLocalConstant)
  • k(x) = doubleFunction(h)(x)
  • t(x) = x + constant (where result is obtained by a function call to addLocalConstant)

Each call to evaluateAtThree prints out f(3), g(3), h(3), k(3), t(3). The first four values are shown in the code.

On the first call, the global variable constant and the local variable constant are both 42 and we get f(3) = 42, g(3) = 90, h(3) = 45, k(3) = 90, t(3) = 45.

Before the second call, the global variable constant is changed to 10. Under lexical scope this, of course, does not change the variable in addLocalConstant with the same name. So we get f(3) = 13, g(3) = 26, h(3) = 45, k(3) = 90, t(3) = 45.

Before the third call, a type glob (see http://docstore.mik.ua/orelly/perl/cookbook/ch10_15.htm)
is used to manipulate the internal symbol table, so that the name addLocalConstant now points to the function addGlobalConstant. However, the reference h still has the address of the original function addLocalConstant, and the function pointed to by k was also defined using this address. So f(3) = 13, g(3) = 26, h(3) = 45, k(3) = 90. To confirm that addLocalConstant is still called twice, one may add print "*" or similar in its definition. Since t calls addLocalConstant by its name, which now points elsewhere, t(3) = 13.

Before the fourth call, the definition of k is repeated. Since addLocalConstant now points to the function addGlobalConstant, the new definition of k uses the global constant, now 10. So we get f(3) = 13, g(3) = 26, h(3) = 45, k(3) = 26, t(3) = 13. This time addLocalConstant is called only by h.

Note that addLocalConstant can’t be garbage collected because it is still pointed to by h and k after the third call, and by h after the fourth call.


2 Responses to Lexical scope and functions in Perl

  1. George W says:

    Does this point boil down to call-by-value vs call-by-name in Lambda calculus? My apologies if that is a face-palm comment – I’m half-remembering something I once half-understood!

  2. mwildon says:

    My immediate answer is no, since I think of call-by-?? as referring to how function arguments are shared (or not) between caller and callee, and I can’t see how that’s relevant here. But it is true that t calls addLocalConstant by name, whereas h calls addLocalConstant by its reference: the former changes (or more precisely, the thing it points to changes), the latter is fixed. I know next to nothing about the lambda calculus I’m afraid; I should learn: the Y-combinator is relevant to the planned post on memoization.

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 )

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s

%d bloggers like this: