Tracing Lazy Functional Computations Using Redex Trails (Pre-alpha draft)

Colin Runciman and Jan Sparud

February 10, 1997

Abstract

We describe the design and implementation of an experimental system for tracing Haskell computations. The basis of our tracing method is a program transformation carried out by the compiler: transformed programs compute the same values as the original, but embedded in functional data structures that also include redex trails showing how the values were obtained. When a final result is obtained in a computation with redex trails, or when an error occurs, the programmer can use a special-purpose interactive display program to investigate the derivation in detail, with cross-links to the source program.

Similar schemes attempted by others have typically been limited, for example, with respect to the language used to express traced programs, the speed of traced execution, the detail recorded in the trace, and the size of computations for which traces can be built and explored. We aim to build a tracer for full Haskell, and ultimately a tracer that can be applied to large computations. Our present tracer, hosted by the nhc compiler, handles most of Haskell. Though applications to date have been small, we can give examples of fully-traced computations of upto a million reductions, derived from original programs several pages in length.

1 Introduction

1.1 Motivation

Functional programming languages offer many advantages over the conventional alternative of procedural languages. For example, program construction is more rapid, more modular, less error-prone and yields much smaller programs to maintain.

Yet functional programming systems are not very widely used. There are various reasons for this, but one that crops up time and again is the lack of tracing facilities. Though there is less scope for making mistakes in a functional language, programmers do still make them. When a program goes wrong they need to trace the cause. And that is rather awkward — it is much harder to trace evaluation by normal order graph reduction than to follow a sequence of commands already explicit in a source program. Implementors of functional languages are hard-pressed to provide equivalents of the ‘debugging tools’ used by many programmers to investigate faults in their procedural programs.

There have been various attempts to tackle this problem of tracing (lazy, higher-order) functional programs. we discuss some of them in §??. But so far as we know there is as yet no really effective solution — a state of affairs that prompted us to engage in our own current work on the tracing problem.

1.2 Design goals and assumptions

We choose to concentrate on purely functional languages such as Haskell with compiled implementations by graph-reduction: it is the combined used of lazy evaluation and higher-order functions in such languages that makes the problem difficult.

Further, we aim to provide ‘backward’ traces from results or from run-time errors, because the most pressing need for traces arises in the context of an unexpected output or failure. In a simplified view of graph reduction, the objective of computation is to evaluate an expression represented by a graph. This is achieved by repeatedly selecting some sub-graph (a redex) whose value is needed and which can be reduced to another (its contractum). The reduction rules used to define replacements are derived from the equations given in the program. At each reduction step, a redex matching the left hand side of an equation is replaced by a contractum that represents the corresponding instance of the right hand side. Parts of the redex no longer reachable from the main graph are normally discarded, and the memory they occupy is reclaimed. If we instead make a link from the contractum to the redex, a trace of the computation is built as reduction proceeds, it is possible to trace back through the redex trails by which some result (or error) came about.

Some of our other design goals, and the assumptions on which they are based, are as follows.

Complete traces Until we have a very strong reason to discard parts of the information in redex trails, and a clear argument which parts should go, we must have a system that gives the programmer access to a complete trace. There must be a representation of every reduction step for definitions and expressions of every kind.

Selective display However, a full trace of even a modest computation contains a great deal of information — too much for the programmer to absorb in its entirety. Programmers should therefore have fine control over what trace information is actually displayed to them, down to the level of interactive linkby-link examination of the trails leading to a run-time fault or selected fragment of output.

Non-invasive traces The transformation to introduce redex trails should not change the course of the underlying computation in any way. For example, unevaluated expressions should remain unevaluated. Neither is there any call to provide the programmer with a means of circumventing this principle — for example, by substituting a value for an expression without regard to the value that would be obtained according to the equations of the program. If the tracing could affect the behaviour of the program (beyond the consumption of extra time and memory) it might only hinder the programmer’s understanding of normal computation.

Traces linked to source However good the tracing system, source programs are likely to remain the primary reference for programmers. So not only should expressions in traces be displayed just as they might be written in a source program; trace text should be also be linked directly to source text. For example, the programmer should have convenient access, from any identifier in any expression displayed as part of a trace, to either the corresponding definition or the relevant applied occurrence of that identifier in the source program. ^{1}

A portable implementation Finally, although our prototype tracer is implemented in the nhc Haskell compiler [1], our goal is to produce a portable tracer, that could be incorporated in other implementations of Haskell or similar functional languages.

2 The design of a trace structure

We must first define what we mean by a redex trace. We propose to use backward traces from contractums to the redexes that created them. If we for example see the number 42 in the trace, we would like to be able to answer the question: Which redex “produced” that number? If we get a run-time error, we would like to be able to see the redex that was responsible for creating the faulting expression. We would also like to be able to trace backwards from parts of the program output, to see which function calls were responsible for creating that part of the output. We will describe the trace structure with an example. Consider the program in Figure 1.

                      f 2 where f x = x + 1

Figure 1: A small program.

1The importance of good links from trace to source was strongly confirmed in a student evaluation of our first working tracer.

The sequence of reductions in this program is f 2 → 2 + 1 → 3. In a trace for the program, we want to be able to trace back from all subexpressions in that sequence, i.e., all applications, identifiers and literals should be annotated with the redex that was responsible for their creation. Figure 2 shows how the back traces (represented by dashed arrows) for the program in Figure 1 will look like.

*--+--+-+--------------+
   |  | |              |
   |  | |       +----------------+
   |  | |       |      |         |
   |  | |       v      |         |
   ap f 2  -->  ap (+) 2 1  -->  3
   ^|   |    |
   |            |   |    |
   +------------+---+----+

Figure 2: A picture of the trace of the call f 2 in the small program in Figure 1.

We can see that the final result, 3, is annotated with a pointer to the redex for 2 + 1, which itself is annotated with a pointer to the redex for f 2. All subparts of the top-level call f 2 are annotated with a null pointer (the trace root), meaning that they have no ancestral redex that was responsible for their creation. The picture is a bit misleading in that it shows two occurrences of the number 2; they are in fact the same, and thus have the same backward trace.

The idea is to construct such a trace giving comprehensive information about a functional computation. The trace should be built as the computation proceeds. Once the computation is over the trace is just a static data structure. A suitable Haskell representation for traces is presented in Figure 3.

data Node =
     Ap Trace [Trace]
   | Nm Trace String
data Trace =
     Trace ⊕ Node
   | Root

Figure 3: Datatypes for the trace structure.

A Trace for an expression is the sequence of Nodes describing the intermediate results in the computation of that expression. Note that if the expression was not evaluated during the computation, then the trace for it should of course not be evaluated either, although a trace node describing the original expression will always be in the trace. An application is represented by Ap t_{ap} [t_{f}, t_{x_{1}}, …, t_{x_{n}}], where t_{ap} is the trace for the application itself, t_{f} is the trace of the function part of the application, and t_{x_{1}} … t_{x_{n}} are the traces of the arguments. A name (a function, variable, constructor or literal) is represented by Nm t_{nm} name where t_{nm} is the trace of the name and name is the string representation of the name. Figure 4 shows how the trace for the program in Figure 1 is represented in our trace datatypes. The trace sequence-constructors ⊕ are labeled with consecutive numbers as they are introduced, and references to them are denoted by t_{n}.

Root ⊕_{1}
Ap Root
   [Root ⊕_{2} Nm Root "f"
   ,Root ⊕_{3} Nm Root "2"

]⊕_{4}

Ap t_{1}
   [t_{1} ⊕_{5} Nm t_{1} "+"

,t_{3}

   ,t_{1} ⊕_{6} Nm t_{1} "1"

]⊕_{7}

Nm t_{4} "3"

Figure 4: The trace for the simple program in Figure 1.

data R a = R a Trace

Figure 5: The definition of the value wrapper type

data Tree a = Node (Tree a) Int (Tree a)
    | Leaf a
=>
data Tree a = Node (R (Tree a)) (R Int) (R (Tree a))
            | Leaf (R a)

Figure 6: Transformation of a datatype.

3 Creating traces

The central idea is to derive a self-tracing transformed version of any given program. We will introduce a number of combinators that actually perform the trace creation, but first we will describe how the types of a program will change due to the transformation.

3.1 Type transformation rules

Every value in the program will be wrapped in the R datatype (see Figure 5). The intuition is that every value in the original program should have a wrapped value in the transformed program containing the original value and a trace for that value.

Rules showing how the types will change in the transformed program are presented in Figure 8 and we will now describe the motivation for the rules.

3.1.1 Traces for structured data values

For a structured data value, we want a trace not only for the outermost construction but also for all components. For example, Figure 6 shows how a simple tree datatype will be transformed.

3.1.2 Traces for values of function type

In principle, a value of function type α → β is a structured value with constructor → and components α and β. The transformation rule for structured values says that the type α → β should be transformed into R (R[[α]]→R[[β]]). A function of type α → β has a guarantee to fulfill, i.e., given an argument of type α it guarantees that it will return a value of type β. But transformed functions has a further obligation; they must also return a trace for that value of type β. Functions of types transformed using the simple rule for structured values cannot possibly fulfill that obligation, since when the function is applied it does not know the current trace (or evaluation context) so it cannot produce a

R[[ (α → β) → [α] → [β] ]]
⇒
R (Trace → R[[α → β ]]→ R[[[α] → [β] ]])
⇒

    R (Trace → R (Trace → R α → R β) → R (Trace → R [α] → R [β]))

Figure 7: Transformation of a function type.

full trace for the return value. We solve this problem by requiring that function values are given the trace of the application site as an extra argument when they are applied. As an example, the type of the standard map function will change as described in Figure 7 (remember that → is right associative).

We also want to be able to trace partially applied functions. That means that functions must return an R-value for each argument it is applied to. We can see that this requirement is fulfilled by the type transformation rules in Figure 8.

R[[ t ]] = R (T [[ t ]])

T [[tcon t_{1} … t_{n} ]] = tcon R[[ t_{1} ]] … R[[ t_{n} ]] (n ≥ 0, tcon ≠ ’→’)

T [[ t_{1} → t_{2} ]] = Trace → R[[ t_{1} ]] → R[[ t_{2} ]]

T [[ α ]] ⇒ α

Figure 8: Type rules for transformed expressions.

3.2 Trace-building primitives

3.2.1 Tracing constants

A constant is the name of a function, variable, constructor or literal. It is represented in the trace by the Nm constructor. We define a function con to produce an Nm node, given a trace and a constant, see Figure 9. The N -scheme gives a textual representation of an identifier.

con t v = R v (t ⊕Nm t N [[v]])

Figure 9: Definition of the constant node-builder.

3.2.2 Tracing function applications

We will now describe how function applications will be traced. A syntactic occurrence of an n-ary function application consists of a function part f and arguments e_{1} to e_{n}. The trace for the application has a one-to-one correspondence with the Ap constructor that also contain traces for the function part and the arguments. Figure 10 shows the definition of a function vap_{n} that constructs a trace for applications.

vap_{n} T_{0}(R f t_{f}) e_{1}@(R t_{e_{1}}) e_{2}@(R t_{e_{2}}) … e_{n}@(R t_{e_{n}}) = let t_{1} = t_{0} ⊕Ap t_{0} [t_{f}, t_{e_{1}}, t_{e_{2}}, …, t_{e_{n}}]

in vap_{n−1} t_{1} (f t_{1} e_{1}) e_{2} … e_{n}

vap_{0} t_{0} e = e

Figure 10: Definition of the application trace-builder.

However this definition has a drawback. If we are tracing the function call f 1 2 3, it will produce a trace with separate nodes for each of f 1 2 3, (f 1) 2 3, and ((f 1) 2) 3, which is not want we want. We only want the trace of the toplevel call. To achieve this, instead of calling vap_{n−1}, we call a function ap_{n−1} in vap_{n} that does not build a trace node for the application. See Figure 11. We do not need the vap_{0} definition anymore, since ap_{0} will do the job instead.

vap_{n} t_{0} (R f t_{f}) e_{1}@(R t_{e_{1}}) e_{2}@(R t_{e_{2}}) … e_{n}@(R t_{e_{n}}) = let t_{1} = t_{0} ⊕Ap t_{0} [t_{f}, t_{e_{1}}, t_{e_{2}}, …, t_{e_{n}}]

in ap_{n−1} t_{1} (f t_{1} e_{1}) e_{2} … e_{n}

ap_{n} t_{0} (R f t_{f}) e_{1}@(R t_{e_{1}}) e_{2}@(R t_{e_{2}}) … e_{n}@(R t_{e_{n}}) =

ap_{n−1} t_{0} (f t_{0} e_{1}) e_{2} … e_{n} ap_{0} t_{0} e = e

Figure 11: Definition of ap_{n} and the modified vap_{n}.

Figure 12 shows how the application tracer will be used in the transformation of the expression f x (g 1), where f and g are let-bound functions and x is a λbound variable. The scheme used for transforming expressions is called the E-scheme, and it has a context that is the current trace t for the application that created the expression.

3.3 Function definitions

One might think that a function definition could be transformed as in Figure 13, but there is a problem with this naive transformation.

E[[f x (g 1) ]]_{t} ⇒ vap_{2} t (f t) x (vap_{1} t (g t) (con t 1))

Figure 12: An example transformation of function application

F[[ f x_{1} … x_{n} = e ]] ⇒ f_{D} t_{0} x_{1} … x_{n} = E[[ e ]]_{t_{0}}

Figure 13: A naive function definition transformation.

Since functions need to take arguments one at a time, we instead use a wrapper function fun_{n} that turns a curried function (the naively transformed function) into a function that for each argument returns an R-value. Given a curried function, the name of the function, and a trace, fun_{n} returns an R-value containing the wrapped function and the trace for the function identifier. Figure 14 shows the definition of fun_{n}. Note that there is a separate application for each real argument. This is because the function might be partially applied and we want to have traces for both the result f of the partial application, and the results obtained by applying f.

fun_{n} f fs t_{0} =

R (λt_{1} e_{1}→

R (λt_{2} e_{2}→
…
R (λt_{n} e_{n}→f t_{n} e_{1} … e_{n})
t_{n−1})
…
t_{1})
[Nm t_{0} fs]

Figure 14: The definition of fun_{n}.

Using the fun_{n} function we can now give the full transformation of function definitions, shown in Figure 15.

Figure 16 shows the transformation of a simple example program. In the program T_{0} denotes the initial trace.

The trace for the result of the program in Figure 16 can be seen in Figure 17. Many parts of the trace structure are shared. For example, the initial (empty) trace T_{0} is shared by all sub-traces. Whenever a new node is introduced in the trace, it is given a name (in the right column). That name is used instead of F[[ f x_{1} … x_{n} = e ]]

= f_{D} = fun_{n} f′ ”f”

where f′ t_{0} x_{1} … x_{n} = E[[ e ]]_{t_{0}}

Figure 15: The full function definition transformation.

  let f x = g x x + x
      g x y = x*y
  in  f 3

⇒

  let f = fun_{1} f' N [[ f ]]
          where f' t x = vap_{2} t ((+) t) (vap_{2} t (g t) x x) x
      g = fun_{2} g' "g"
          where g' t x y = vap_{2} t ((*) t) x y
  in  vap_{1} t_{0} (f t_{0}) (con t_{0} 3)

Figure 16: Transformation of a simple program.

showing that trace again when it is referred to in other traces.

In the trace we can see that the result is 12 (the last node in the top-level trace) and that it was the result of a + application formed as part of the body of f 3, with arguments that evaluated to 9 and 3. But where are the calls to * and g? If we study the trace we see that 9 was the result of 3 * 3 which formed the body of g 3 3. All values have full traces of how they were computed. For instance, in the application node for the call to g (ap_{3}) the trace of the application that created ap_{3} is stored (ap_{1}, the call to f).

3.3.1 Over-saturated applications

A function application that applies a function to more arguments than it accepts, is said to be over-saturated. The function will use as many arguments as it accepts and produce a new function (provided the program is well-typed) which is applied to the rest of the arguments. The trace-construction mechanism we have designed sofar works well for partially applied and saturated functions.

However, there is a problem with building traces for function applications that over-saturate functions, as can be seen in Figure 19. In such cases traces for calls made from within the over-saturated function actually get lost. The reason can be seen in the definition of ap_{n}. If an application over-saturates a function of arity n, the functional argument f to ap_{n} will represent the result of a saturated call complete with a trace t_{f}, which ap_{n} ignores! We cannot include the trace for the function part for each recursive call to ap_{n}, because

Root ⊕_{1}
Ap Root [Root ⊕_{2} Nm Root "f", Root ⊕_{3} Nm Root "3"]⊕_{4}
Ap t_{1}
   [t_{1} ⊕_{5} Nm t_{1} "+"

,t_{1} ⊕_{6}

Ap t_{1} [t_{1} ⊕_{7} Nm t_{1} "g", t_{3}, t_{3}]⊕_{8} Ap t_{6} [t_{6} ⊕_{9} Nm t_{6} "*", t_{3}, t_{3}]⊕_{10}

    Nm t_{8} "9"

,t_{3}

]⊕_{11}

Nm t_{4} "12"

Figure 17: The trace for the transformed program in Figure 16.

then we get the same problem that made us to introduce ap_{n} in the first place. We only want to include the trace if the function part is the result of a call to a fully saturated function. But how do we know that? If we look in the definition of fun_{n} we see that an unsaturated function is applied to its own trace. When ap_{n} applies a function, it can check if the trace in the result is the same as the one passed to the function as first argument. If the traces are the same, the application is partial; otherwise it is saturated.

This sounds simple, but it is not possible in a pure functional language to test equality of objects, one can only test equality of values. By introducing a function for pointer equality we can overcome this problem. The modified version of ap_{n} is presented in Figure 18. This new equality function is of course not referentially transparent, but at the place it is used we are interested in implementation details of functions (i.e., their syntactical arity) so it is actually of vital importance that it is referentially opaque. From a functional point of view, the two function definitions f x = e and f = \x -> e have the same meaning, but they have different syntactical arities, which means they must be treated differently in the tracer.

ap_{n} t_{0} (R f t_{f}) e_{1}@(R t_{e_{1}}) e_{2}@(R t_{e_{2}}) … e_{n}@(R t_{e_{n}}) =

if t_{0} ‘pointerEqualTo‘ t_{f} then ap_{n−1} t_{0} (f t_{0} e_{1}) e_{2} … e_{n}

else let t_{1} = t_{0} ⊕(Ap t_{0} [t_{f}, t_{e_{1}}, t_{e_{2}}, …, t_{e_{n}}]) in ap_{n−1} t_{1} (f t_{1} e_{1}) e_{2} … e_{n}

ap_{0} t_{0} e = e

Figure 18: The modified version of ap_{n}.

Consider the example program in Figure 19 where the top-level function call over-saturates the function f. Without the modification to ap_{n}, the call to g in f is lost. The trace for the program with the modified ap_{n} is presented in Figure 20.

  let f x = g x
      g x y = x+y
  in  f 2 3

Figure 19: A program with an over-saturated function application.

Root ⊕_{1}
Ap Root
   [Root ⊕_{2} Nm Root "f"
   ,Root ⊕_{3} Nm Root "2"
   ,Root ⊕_{4} Nm Root "3"

]⊕_{5}

Ap t_{1}

[t_{1} ⊕_{6} Ap t_{1} [t_{1} ⊕_{7} Nm t_{1} "g", t_{3}] ,t_{4} ]⊕_{8}

Ap t_{5} [t_{5} ⊕_{9} Nm t_{5} "+", t_{3}, t_{4}]⊕_{10}

Nm t_{8} "5"

Figure 20: The trace for the program in Figure 19.

3.3.2 Argument as results

There is a further problem with our current trace building mechanism. If a function f returns one of its arguments, the trace for the result will be the trace of the argument, which was produced elsewhere. So in the result trace, the call to f will not occur. For example, consider the program in Figure 21. The result of the program is 1 and the trace is the empty trace! The reason is that the id function just returns its argument, which in the end happens to be the 1 given as argument to the top-level call to g. It is true that 1 was produced at the top-level, but it is unfortunate that we cannot from the trace figure out why 1 was returned from the call to g. We solve this problem by introducing an indirection node in the Node datatype. The indirection node is to be used when a function returns one of its arguments, and contains a trace for the result. Figure 22 shows the modified Node datatype. Note that we introduce indirection nodes at exactly the same place where compilers using varying node-sizes need to introduce indirections, i.e., when they return something of unknown size.

  let f x y = x (x y)
      id x = x
      g x = f id x
  in  g 1

Figure 21: A program that illustrates the problem with functions returning arguments.

data Node =
     Ap Trace [Trace]
   | Nm Trace String
   | Ind Trace

Figure 22: The modified Node datatype.

Figure 23 shows the trace for the program in Figure 21 using the new Node datatype. The trace for the result is now an indirection to another trace as its most evaluated part, and the calls to f, g and id in its spine. Jan: Explain the trace!

Root ⊕_{1}
Ap Root [Root ⊕_{2} Nm Root "g", Root ⊕_{3} Nm Root "1"]⊕_{4}

Ap t_{1} [t_{1} ⊕_{5} Nm t_{1} "f", t_{1} ⊕_{6} Nm t_{1} "id", t_{3}]⊕_{7}

Ap t_{4}

[t_{6}

,t_{4} ⊕_{8}

Ap t_{4} [t_{6}, t_{3}]⊕_{9}

    Ind t_{3}

]⊕_{10}

Ind t_{9}

Figure 23: The trace for the program with an over-saturated function application in Figure 21.

3.3.3 Tracing List Comprehensions Jan: Look in the discussion notes.

3.3.4 Tracing Guards Jan: Look in the discussion notes.

3.4 The Source Transformations

3.4.1 Transforming Function Definitions 3.4.2 Transforming Expressions 3.4.3 Transforming Classes

3.5 The Runtime System Support

Jan: Describe evaluated, evaluating, getConstr, ...

3.6 Benchmarks

4 Displaying traces

4.1 Introduction

Jan: Describe the basic structure: Trace window, source window, input/output window, options, example.

4.2 Displaying Expressions 4.3 Selecting Expressions 4.4 Displaying High Level Constructs

Jan: List comprehensions, guarded function calls, etc. Look in the discussion notes.

4.5 Tracing From Output

5 Evaluation and performance 6 Related work 7 Conclusions and Future Work References

[1] Niklas Röjemo. Garbage Collection, and Memory Efficiency, in Lazy Functional Languages. PhD thesis, Department of Computer Sciences, Chalmers University of Technology, S-412 96 Göteborg, Sweden, May 1995.