Edit detail for SandBox Trace Analysed revision 1 of 2

This page is work in progress, to be continued ...

Background

Francois Maltey <fmaltey@nerim.fr> wrote on 09 Apr 2006 21:32:00 +0200:

    )trace EXPR
    imag (sin (%i))
      >> System error:
      Bind stack overflow.

Section 1. The Issues

These are probably related to IssueTracker? #232, #233 and some seem to be difficult to fix. You did the right thing using )trace but )trace is fickle.

Summary findings so far:

1. A simpler trigger 1::EXPR INT shows the bug need not involve imag or sin or %i or even EXPR ; in [SandBox Trace EXPR and FRAC]? we showed 2/3::FRAC INT also triggers similar problems.
2. )trace may be responsible for the bug (interfering with computation);
3. Depending on the domains traced, using )math with )trace may give different traces and indeed different outputs (see [SandBox Trace with )math]?); unfortunately, there are so many variations and dependencies that it is difficult to keep track and reproduce behaviors consistently;
4. It is important to start with a new session, or at least a )trace )off , for each experiment because after a Bind Stack Overflow, )trace may not be working the same; even a repeated )trace may alter the outcome.
5. There are differences between Windows and Linux versions. Problem seems to be error in )trace : finding the wrong function names (see [SandBox Trace in Windows]?).

Section 2. The )trace command

The first two points are illustrated in [SandBox Trace EXPR and FRAC]?. This was discovered after what comes next was mostly written. But instead of trying to simplify, perhaps it has more relevance to the given question, and in any case, I would like to understand more about EXPR . I also think tracing 2/3 ::FRAC INT may shed some light on the problem since FRAC INT is a much simpler domain.

To show the last two items, try, with a new session, the three )trace commands, with or without )math (16 cases, but not all different outcomes):

  )set mess auto off
  )trace INT
  )trace EXPR INT
  )trace EXPR INT

Here are two sample outputs (cut and paste from terminal, with empty lines deleted to have the verbatim block working) from Windows (Version of Tuesday November 30, 2004 at 21:11:14). Note the difference in responses both within the same example and between the examples.

Example 1:

  (1) -> )set mess auto off
  (1) -> )trace INT )math 
     Parameterized constructors traced:
        INT
  (1) -> )trace EXPR INT )math
  1<enter Integer.one?,26 : 1>exit  Integer.one?,26 :
   true
  1<enter Integer.zero?,25
     >> Error detected within library code:
     bad functorName
     G1440
  protected-symbol-warn called with (NIL)
  (1) -> )trace EXPR INT
  1<enter Integer.zero?,25
     >> Error detected within library code:
     bad functorName
     G1440
  protected-symbol-warn called with (NIL)

Example 2:

  (1) -> )set mess auto off
  (1) -> )trace INT
     Parameterized constructors traced:
        INT
  (1) -> )trace EXPR INT
  1<enter Integer.one?,26 :
  1>exit  Integer.one?,26 : 0
  1<enter Integer.zero?,25 : 1
  1>exit  Integer.zero?,25 : NIL
     Packages traced:
        Integer, Expression Integer
     Parameterized constructors traced:
        INT
  (1) -> )trace EXPR INT
     Packages traced:
        Integer, Expression Integer
     Parameterized constructors traced:
        INT

On Linux (FC2, Version: Axiom 3.0 Beta (February 2005)), same as Example 2, except Integer.one? was not called.

)trace )off

   Nothing is traced now.

)trace INT )math

   Parameterized constructors traced:
      INT

)trace EXPR INT )math

 1<enter Integer.zero?,25 : 
 arg1= 1
 1>exit  Integer.zero?,25 : 
 false

   Packages traced: 
      Integer, Expression(Integer)
   Parameterized constructors traced:
      INT

)trace EXPR INT

   Packages traced: 
      Integer, Expression(Integer)
   Parameterized constructors traced:
      INT

Before going on, open expr.spad , fraction.spad , multpoly.spad , kl.spad , and integer.spad as references. I don't know why Integer.one? and Integer.zero? appeared or why using )math made a difference (I don't know how to trace )trace itself.) However, I think understanding the following sequence might be useful for later. My interpretation may be wrong.

1. To instantiate 0$(EXPR INT), the code is: 0$Rep .
2. The Rep for EXPR INT is FRAC SMP(INT, KERNEL EXPR INT) ; (yes, it is circular! or if you prefer, recursively constructed)
3. To instantiate 0$Rep , we use 0 and 1 from SMP(INT, KERNEL EXPR INT) to build the fraction 0/1 (see domain Localise in fraction.spad );
4. These two constants are given by the code: 0 = 0$R::% and 1 = 1$R::% , where R is INT .
5. This requires first coercing 0$INT and 1$INT to SMP(INT, KERNEL EXPR INT) .
6. These coercions are given by the code: coerce(n) == n::R::% (see SMP in multpoly.spad ). Here coerce on the left has signature coerce: Integer -> SMP(INT, KERNEL EXPR INT) .
7. When R is INT, the code coerce(n) == n::R::% looks like it is circular but I believe it is not since at compile time, R is not INT. (This raises a general question on boundary cases for parameters). Moreover, I believe Integer is not INT when the domain constructor INT is compiled. This is weird, I know, that's why I am using the word believe; Integer is some domain in Lisp, whereas INT is the Axiom domain we usually call 'Integer'; in a sense, the Lisp Integer is extended, a la Aldor, by the domain constructor Integer, whose abbreviation is INT.

   {Aside: can we use this technique to simulate extend in Axiom? That is, can we simply redefine a domain or domain constructor using its former self?}

   I'll continue to use INT to mean the Axiom domain and Integer for the Lisp domain in this paragraph. Assuming this, n::R refers to the coerce: Integer->INT which is implemented in integer.spad by coerce(m:Integer):% == m pretend % (note that the domain INT has no Rep, and this is, in a sense, saying Rep is Integer of Lisp). Continuing, R::% has signature coerce:R ->%, and is implemented in SMP by coerce(c) == c::%, where the interpretation of % is Rep of SMP(INT, ...), which in turn is Union(R, ...). To cut this short, n::R::% is what we expect.

Section 3. Coercing 1::EXPR INT

First we establish that 1::EXPR INT works as expected without )trace .

)trace )off

   Nothing is traced now.

1::EXPR INT

(1)

coerce(1$INT)@(EXPR INT)

(2)

Now if we add the following )trace command, then we obtain the Bind Stack Overflow. This establishes the claims (1) and (2) in Section 1.

)trace EXPR )math

   Packages traced: 
      Expression(Integer)
   Parameterized constructors traced:
      EXPR
1::EXPR INT

 1<enter Expression.coerce,61 : 
 arg1= 1
 1>exit  Expression.coerce,61 : 
 1

 1<enter Expression.denom,102 : 
 arg1= 1
 1>exit  Expression.denom,102 : 
 1
 1<enter Expression.numer,100 : 
 arg1= 1
 1>exit  Expression.numer,100 : 
 1

(3)

To trace this error, I used the following (recall from Section 1 that )trace is fickle and differs in Windows and Linux; also, the output would be fairly long):

  )trace INT 
  )trace EXPR INT
  )trace SMP(INT, KERNEL EXPR INT)
  1::EXPR INT

but we need a new session, and there are many lines of output. So I set up a new page in [SandBox Trace EXPR and FRAC]?. Here's a sample ([SandBox Trace in Windows]?) of an abbreviated output (that page is subject to experimentation, so you will find the following only if the code above is run there at the top):

  1::EXPR INT
  1<enter Expression.coerce,34 : 1
   1<enter Fraction.*,60 : 1\((0 . 1) 0 . 1)
    1<enter SparseMultivariatePolynomial.coerce,77 : 1
    1>exit  SparseMultivariatePolynomial.coerce,77 : (0 . 1)
    1<enter SparseMultivariatePolynomial.=,97 : (0 . 1)\(0 . 1)
     1<enter Integer.=,64 : 1\1
     1>exit  Integer.=,64 : T
    1>exit  SparseMultivariatePolynomial.=,97 : T
    1<enter SparseMultivariatePolynomial.*,65 : (0 . 1)\(0 . 1)
     1<enter SparseMultivariatePolynomial.*,90 : 1\(0 . 1)
      1<enter Integer.=,64 : 1\1
      1>exit  Integer.=,64 : T
     1>exit  SparseMultivariatePolynomial.*,90 : (0 . 1)
    1>exit  SparseMultivariatePolynomial.*,65 : (0 . 1)
    1<enter SparseMultivariatePolynomial.zero?,17 : (0 . 1)
     1<enter Integer.zero?,25 : 1
     1>exit  Integer.zero?,25 : NIL
    1>exit  SparseMultivariatePolynomial.zero?,17 : NIL
    1<enter SparseMultivariatePolynomial.=,97 : (0 . 1)\(0 . 1)
     1<enter Integer.=,64 : 1\1
     1>exit  Integer.=,64 : T
    1>exit  SparseMultivariatePolynomial.=,97 : T
   1>exit  Fraction.*,60 : ((0 . 1) 0 . 1)
  1>exit  Expression.coerce,34 : ((0 . 1) 0 . 1)
  1<enter Expression.coerce,397 : ((0 . 1) 0 . 1)
   2<enter Expression.coerce,397 : ((0 . 1) 0 . 1)

Now let's follow the trace above.

1. coerce$EXPR INT is implemented as
   coerce(n:Integer) == coerce(n)$Rep@Rep::%
2. We already know that Rep (from $Rep) for EXPR INT is FRAC SMP(INT, KERNEL EXPR INT) .
3. We also know that the Rep (from @Rep) is the Rep for FRAC SMP(INT, KERNEL EXPR INT) and hence is a pair from SMP(...) . So eventually, the ::% is the coercion from FRAC SMP(...) back to EXPR INT .
4. This is done via the coercion from SMP(...) to EXPR INT . This is possible because SMP(...) belongs to POLYCAT .
5. All the above worked fine, ending in the trace line: 1>exit Expression.coerce,34 : ((0 . 1) 0 . 1) . That is, 1::EXPR INT results in the object represented internally as ((0 . 1) 0 . 1) . It is a list with two items, the first is a list (0 . 1), representing the constant polynomial 1, and the other 0 . 1 without the parenthesis represent the constant 1, and 1 . It simply represents 1$SMP(...).
6. The infinite loop comes when the previous result is passed to Expression.coerce, 397 . This last coerce is coerce:%-> OutputForm and is implemented in EXPR by calling coerce$Rep . (I found this out by recompiling expr.spad and looking at the file index.KAF in EXPR.NRLIB).
7. coerce$(FRAC SMP(...) is implemented as:

         coerce(x:%):OutputForm ==
           ((xd:=x.den) = 1) => (x.num)::OutputForm
           (x.num)::OutputForm / (xd::OutputForm)
   

8. So the output is finally done by calling coerce$SMP(INT, KERNEL EXPR INT) , which is implemented as:

        coerce(p):OutputForm ==
           p case R => (p::R)::OutputForm
           outputForm(p.ts,p.v::OutputForm)
   <li> The 'Rep' for 'SMP(INT, KERNEL EXPR INT)' is 'Union(R, V)' where 'V' is ::
   
      'Record(v: KERNEL EXPR INT, ts: SUP(SMP(INT, KERNEL EXPR INT))' 
   

   (again, this is circular).

9. The Rep for SUP(R) where R is any ring, is just a list of its terms, that is:

      Term := Record(k:NonNegativeInteger,c:R)
      Rep  := List Term
   

10. So ((0 . 1) 0 . 1) means a list but this means the representation of EXPR INT is to be a fraction, whose numerator and denominator are written as a p
11. It seems to me that when )trace is not on, the first line of coerce succeeds for input ((0 . 1) 0 . 1) (as it should) but fails when )trace is on.
12. The function outputForm is taken from SUP(SMP(INT, KERNEL EXPR INT)) (more generally, from SUP(R) for any ring R . It is implemented as:

       outputForm(p:%,v:OutputForm) ==
         l: List(OutputForm)
         l:=[toutput(t,v) for t in p]
         null l => (0$Integer)::OutputForm -- else FreeModule 0 problems
         reduce("+",l)
    

To be continued.