Path: utzoo!utgpu!water!watmath!watdragon!gvcormack
From: gvcormack@watdragon.waterloo.edu (Gordon V. Cormack)
Newsgroups: comp.lang.misc
Subject: Displays are not expensive (Was:  Var scoping in Wirth-type languages)
Message-ID: <5673@watdragon.waterloo.edu>
Date: 12 Mar 88 22:31:15 GMT
References: <3821@ihlpf.ATT.COM> <2791@enea.se> <3949@ihlpf.ATT.COM> <4426@june.cs.washington.edu>
Organization: U of Waterloo, Ontario
Lines: 38

In article <4426@june.cs.washington.edu>, pardo@june.cs.washington.edu (David Keppel) writes:
> 
> (Paraphrasing) from compilers class:
> 
>     "Displays are a really great idea, but are too expensive to
>     implement to be useful for Algol-class languages."
> 
> Where "too expensive" is measured in terms of the cost of maintaining
> one over each procedure call versus the performance penalty for scanning
> up the dynamic links.

This is just not true.  For ordinary procedure calls, a global
display involves trivial entry and exit overhead.  The only time
displays get expensive is if you do lots of "functional" style 
programming - passing procedures as parameters and/or using
procedure variables.  Even this is quite bearable - it uses time
and space proportional to n to build a local copy of the display
in order to pass a procedure (or procedures) as a parameter.

Here is a comparison of the time to do static links vs. displays.
(in terms of "n", the level of nesting).

    STRATEGY:        static links          global disply

    ENTRY CODE:        O(1)                    O(1)
    EXIT CODE:         0                       O(1)
    NONLOCAL REF:      O(n)                    O(1)
    FUNC PARM:         O(1)                    O(n)*

---
* This cost applies only to procedures containing all of:
  a local variable x
  a nested procedure y that references x
  a procedure call passing y as a parameter
-- 
Gordon V. Cormack     CS Dept, University of Waterloo, Canada N2L 3G1
                      gvcormack@waterloo  { .CSNET or .CDN or .EDU }
                      gvcormack@water         { UUCP or BITNET }