Previous Table of Contents Next


6.3.3.2. Adding Memory to Procedures

It is clear that redundant computation must be avoided if there is to be any hope of computing many values in such a sequence. The obvious way to avoid duplicate procedure calls is to keep track of calls and record their values. Then, when a call occurs that has occurred before, its value can be produced without performing the computation again. In other words, add memory to the procedure. This idea is an old one (Mitchie, 1967), and it is an important component of dynamic programming (Horowitz & Sahni, 1978).

The basic idea is simple: Provide memory in the form of a data structure that is subscripted by argument value. When a procedure is called, the memory is checked. If there is a value for the argument in the memory, the value is returned. If there is not, the computation is performed as before, and the resulting value is added to the memory before the procedure returns.

For Icon, tables provide a particularly convenient form of memory. They can be subscripted by any value; it is not necessary to worry about out-of-range references, and they grow in size automatically as information is added to them.

Here is how the procedure for computing the chaotic sequence looks with memory added:

    procedure q(i)
       static memory

       initial {
          memory := table()
          memory[1] := memory[2] := 1
          }

       if value := \memory[i] then return value
       else return memory[i] := q(i – q(i – 1)) + q(i – q(i – 2))

    end

The use of a static variable allows all calls of q() to access previously computed values.

The first time q() is called, memory is set up, and the two initial values in the sequence are placed in it so that it is not necessary to check for them in subsequent calls. Because the default value for the table is null, it is easy to check whether an argument is in memory. If it is not, the computed value is added to memory before returning.

Using this formulation, the speed of computation is nearly linear in i. Values for q(i) easily can be computed for large i.

A thousand values are more than enough to reveal some startling properties of this chaotic sequence, as shown in this plot produced using Icon’s graphics facilities:

The average value of q(i) appears to be linear and close to i/2. Notice also the self-similarity in the oscillations—a suggestion of a possible relationship to fractals.

6.3.4. Visual Interfaces in Icon

Most programs now provide visual interfaces through which a user can control the program in a high-level manner using interface tools such as menus and buttons.

As mentioned in section 6.2.7, Icon supports a variety of interface tools. The (Icon) program VIB (“visual interface builder”) provides a visual environment for building interfaces. This section provides an overview of the process of building a visual interface and writing a program to use such an interface. A slightly simplified version of the symmetric drawing application shown in section 6.2.7 is used as an example here:

6.3.4.1. The Interface

It is not necessary to know how the functionality of an application is accomplished in order to create a visual interface for it. Interface design—how functionality is expressed and arranged visually—is a complicated and difficult subject. This section does not deal with these topics but instead shows how to create a given interface, such as the one shown previously.

The interface for the symmetric drawing application has four interface tools:

  A menu at the top left
  Two buttons below the menu
  A square region in which the drawing is displayed

In addition, there is a line that separates the menu bar from the rest of the interface.

The file menu has three items:

The save item allows the user to save the current drawing in an image file. The help item leads to information about the application and how to use it. Finally, the quit item terminates execution of the application.

The clear and lines buttons clear the display and toggle the visibility of the lines that indicate the “mirrors” around which drawing is reflected, respectively. The two buttons differ in functionality. The clear button simply causes an action. The lines button retains a state according to whether the mirror lines are shown. This toggle button is highlighted (by reversing colors) when it is on so that its state can be seen on the interface.

The region in which the drawing is displayed accepts mouse events that are translated into drawing that is mirrored to create the symmetry.

Producing this interface involves defining the size of the interface, creating the tools, positioning them, and giving them appropriate attributes.


Previous Table of Contents Next