Scope markers

[Waldek Hebisch]

I mentioned that some time ago. I would like to add indication
of scope to OutputForm. Main reason is SparseUnivariatePolynomial.
In SparseUnivariatePolynomial variable is effectively anonymous
and for output uses '?'. This means that in case of nested
SparseUnivariatePolynomial-s it is hard or impossible to decide
which variable is really used.

I think that wrapping polynomial output in new scope construct
will solve the problem, we will be able to decide which variable
is correct one by countion scopes.

To ilustrate, currently we could do:

(7) -> P1 := SUP(INT)

(7) SparseUnivariatePolynomial(Integer)
Type: Type
(8) -> P2 := SUP(P1)

(8) SparseUnivariatePolynomial(SparseUnivariatePolynomial(Integer))
Type: Type
(20) -> p1 := monomial(monomial(1, 1)$P1, 0)$P2

(20) ?
Type: SparseUnivariatePolynomial(SparseUnivariatePolynomial(Integer))
(21) -> p2 := monomial(1$P1, 1)$P2

(21) ?
Type: SparseUnivariatePolynomial(SparseUnivariatePolynomial(Integer))
(22) -> PRETTYPRINT(p1::OutputForm)$Lisp
"?"

(22) ()
Type: SExpression
(23) -> PRETTYPRINT(p2::OutputForm)$Lisp
"?"

(23) ()
Type: SExpression

p1 and p2 are different, but OutputForm is identical. With
scope markers we should get something like

(SCOPE (SCOPE "?"))

for p1 and

(SCOPE "?")

for p2. To make this useful we also need to change output.
One possibility is to have list of variables to substitute for
"?". Assuming that the list is ['%a, '%b] we could transform
the first case to "%a" and the second case to "%b".

Drawback is that all users of OutputForm should be updated.
This could be simplifed by doing transformation above in
precondition (which IIUC is used by all our formatters).

Comments? Aternative ideas?

--
Waldek Hebisch

[Ralf Hemmecke]

On 30.06.22 23:29, Waldek Hebisch wrote:
> I mentioned that some time ago. I would like to add indication of
> scope to OutputForm. Main reason is SparseUnivariatePolynomial. In
> SparseUnivariatePolynomial variable is effectively anonymous and for
> output uses '?'.

Is this the only reason?

In case it is, my first feeling is. No bug, don't fix it. If a user
wants a proper variable name, he should use UnivariatePolynomial,
because that explicitly requires a variable name for the output.

My understanding is that SUP is for internal purposes where the name of
the variable is irrelevant. And I do not see that in our algebra library
the use of SUP causes any problem.

If you do not accept that position, then another simple idea is that
for the variable name is only really a problem, if we have SUP(A) and
SUP(B) with different coefficient rings A and B. That, however, leads to
two instantiations of SUP, right? What about simply generating a new
lisp symbol with every instance of SUP and store it as a domain
variable/constant. That symbol would then be used for output. No need to
change OutputForm.

Ralf

[Waldek Hebisch]

On Fri, Jul 01, 2022 at 12:20:35AM +0200, Ralf Hemmecke wrote:
> On 30.06.22 23:29, Waldek Hebisch wrote:
> >I mentioned that some time ago. I would like to add indication of
> >scope to OutputForm. Main reason is SparseUnivariatePolynomial. In
> >SparseUnivariatePolynomial variable is effectively anonymous and for
> >output uses '?'.
>
> Is this the only reason?
>
> In case it is, my first feeling is. No bug, don't fix it. If a user
> wants a proper variable name, he should use UnivariatePolynomial,
> because that explicitly requires a variable name for the output.

Sorry, this is _very_ wrong. Any fixed name could clash with
user variable names, so library normally uses SUP. In several
cases user has no choice because SUP is the only thing.

SUP is most prominent case because it is widely used. But the
same problems appears with POLY/EXPR like domain nested one
in anothers. Those are less significant as in such case user
has more control of variable names. Also, interpreter forbids
several such combinations (but they are used by the library).

> My understanding is that SUP is for internal purposes where the name of
> the variable is irrelevant. And I do not see that in our algebra library
> the use of SUP causes any problem.

It causes trouble if you start looking at "internal" stuff.
And there were bug reports about this (nothing recent,
apparently our users treat this as "unsolvable problem").

> If you do not accept that position, then another simple idea is that
> for the variable name is only really a problem, if we have SUP(A) and SUP(B)
> with different coefficient rings A and B. That, however, leads to two
> instantiations of SUP, right? What about simply generating a new lisp symbol
> with every instance of SUP and store it as a domain variable/constant. That
> symbol would then be used for output. No need to change OutputForm.

That has many problems. One is getting unpredictable variable names.
Another is that logically the same domain may be re-instantiated
effectlevely getting different name.

Change to OutputForm is appropriate as only output is affected:
if nobody looks at output then new OutputForm will be unused...

--
Waldek Hebisch

[Qian Yun]

On 7/1/22 05:29, Waldek Hebisch wrote:
> p1 and p2 are different, but OutputForm is identical. With
> scope markers we should get something like
>
> (SCOPE (SCOPE "?"))
>
> for p1 and
>
> (SCOPE "?")
>
> for p2. To make this useful we also need to change output.
> One possibility is to have list of variables to substitute for
> "?". Assuming that the list is ['%a, '%b] we could transform
> the first case to "%a" and the second case to "%b".
>
> Drawback is that all users of OutputForm should be updated.
> This could be simplifed by doing transformation above in
> precondition (which IIUC is used by all our formatters).
>
> Comments? Aternative ideas?
>

This is useful to have, not sure if implementation will be tricky.
This can also be helpful for nested Union("failed",...).

- Qian

[Ralf Hemmecke]

>> In case it is, my first feeling is. No bug, don't fix it. If a user
>> wants a proper variable name, he should use UnivariatePolynomial,
>> because that explicitly requires a variable name for the output.
>
> Sorry, this is _very_ wrong. Any fixed name could clash with
> user variable names, so library normally uses SUP. In several
> cases user has no choice because SUP is the only thing.

Yes, clear.
In SUP the name is irrelevant. SUP is essentially for library developers.

> SUP is most prominent case because it is widely used. But the
> same problems appears with POLY/EXPR like domain nested one
> in anothers. Those are less significant as in such case user
> has more control of variable names. Also, interpreter forbids
> several such combinations (but they are used by the library).

OK, but what is the exact problem of POLY or EXPR for a user or developer?

>> My understanding is that SUP is for internal purposes where the name of
>> the variable is irrelevant. And I do not see that in our algebra library
>> the use of SUP causes any problem.
>
> It causes trouble if you start looking at "internal" stuff.
> And there were bug reports about this (nothing recent,
> apparently our users treat this as "unsolvable problem").

I agree, for debugging purposes it would be nice to be able to
distinguish from where a printed variable "?" comes from. But I do not
see why this requires a change in OutputForm.

>> If you do not accept that position, then another simple idea is that
>> for the variable name is only really a problem, if we have SUP(A) and SUP(B)
>> with different coefficient rings A and B. That, however, leads to two
>> instantiations of SUP, right? What about simply generating a new lisp symbol
>> with every instance of SUP and store it as a domain variable/constant. That
>> symbol would then be used for output. No need to change OutputForm.
>
> That has many problems. One is getting unpredictable variable names.

Hmmm... what variable name would (SCOPE "?") give?

> Another is that logically the same domain may be re-instantiated
> effectlevely getting different name.

Yes. But why would that be a problem? For debugging purposes, it's
completely enough if one can figure out to what the printed "?" belongs
to and that would be easy if it prints as "%s3" or so.

> Change to OutputForm is appropriate as only output is affected:
> if nobody looks at output then new OutputForm will be unused...

You say it. If no output is produced, then everything is irrelevant.
But why constructing a new output form? Let's take SUP(R). In order to
be able for this domain to produce "(SCOPE "?") as an output form, it
would have to investigate the structure of R. Now let's suppose that can
be done. Then a formatter get's (SCOPE "?") and has to translate it into
something that looks like a variable, "?'" or "?1". However, SUP instead
of giving (SCOPE "?") could immediately use "?'" or "?1" as variable name.

The same can apply for Union(X, "failed"), although Union is a somewhat
special case.

I am not convinced that introducing a new marker in OutputForm is really
needed.

I also wonder how a domain/package can actually recognize that it would
have to output its variable as (SCOPE "?") instead of simply "?".

Ralf

[Waldek Hebisch]

I think it is better to explain more how SCOPE is supposed to
work and what problem it solves. Main point is that coerce
to OutputForm works in recursive way, so at any point coerce
need to work with incomplete information. To avoid variable
clashes we need semi-global approach, that is coordinate
use of varibables on for whole expression or sequence of
expressions.

With SCOPE coerce can work alost as it works now: affected
domains will always wrap output in SCOPE marker, so no
need to "recognize". Also, the whole output of coerce
will be wrapped, so change to coerce will be quite small.

Actual renaming of variables will be done as optional
and configrable extra transformation of output form.
AFAICS simple modification to 'precondition' should
handle this for formatters that call 'precondition'
(hopefull all our formatters). So the most impact
will be on external users. That is why I sent my
initial message: it is intended as early warning
to any such users.

More generally, the idea is that we can have more
flexible relation between output form and actual
output. That is we can do various transformation
on output form. For example, with SCOPE markers
appropriate transformer could reorder terms of polynomial
so that computations would user order optimal
from computational point of view and output
could be in user-preferred order (currently
output form mostly follows internal structure,
so people are forced to use different types to
change form of output).

Note: such transformations are possible now and some
are done by default. But they may be wrong for
some domains, so we need extra semantic info in
output form to make sure such transformations
are reliable.

You somewhat think that changing output form
is problematic. Well, output form is internal
to FriCAS so from point of view of compatibility
change to output form is preferable compared
to changes to visible interfaces. And IMO to
improve output we need to change structure of
output form. Introducing SCOPE markers is
just one step in this direction.

--
Waldek Hebisch

[Ralf Hemmecke]

> I think it is better to explain more how SCOPE is supposed to
> work and what problem it solves. Main point is that coerce
> to OutputForm works in recursive way, so at any point coerce
> need to work with incomplete information. To avoid variable
> clashes we need semi-global approach, that is coordinate
> use of varibables on for whole expression or sequence of
> expressions.

If I understand correctly, the semi-global approach will then come from
the fact that the construction of the OutputForm happens recursively in
different domains and the actual formatter (function precondition) has
the complete OutputForm structure with basically a global view on it.

> With SCOPE coerce can work alost as it works now: affected
> domains will always wrap output in SCOPE marker, so no
> need to "recognize". Also, the whole output of coerce
> will be wrapped, so change to coerce will be quite small.

OK, I understand. Such an approach would certainly work.

Just as a side remark if "precodition" is a must then Qian's recent
commit 976a6434f04f1fc9cd2ba04e2d8b13aed061796f should rather use

format(op::OutputForm)$Formatter(Format1D)

instead formatExpression. I've overlooked that when I gave my OK.

> Actual renaming of variables will be done as optional
> and configrable extra transformation of output form.

If "precondition" removes all the (SCOPE ...) stuff and replaces the
variables accordingly that would be doable. However, how would it
recognize which symbols it actually has to replace and which not?

Something like

S1 ==> SUP INT; S2 ==> SUP S1
s1 := monomial(1,1)$S1
s2 := monomial(1, 2)$S2
s := s1*s2
(s::OutputForm) pretend SExpression

with output (* "?" (^ "?" 2))
would become (SCOPE (* "?" (SCOPE (^ "?" 2)))) and easy to transform.
I worry a bit about cases where there is "?" is inside a SCOPE but is
not a variable. It would be safer if then the default variable name
would rather be something that does not occur otherwise. But "failed" is
another candidate to worry about.

> More generally, the idea is that we can have more
> flexible relation between output form and actual
> output.

Well, one may wish that and I a not strictly against it. However,
already OutputFormat itself is a bit questionable. It not only holds the
actual data that is to be shown, but already contains constructs how the
data should be show, in particular VCONCAT is such a construct. But OK,
we treat this as logical construct and the formatter can decide what to
do with it.

AFAIU, you want to introduce another layer with the signature
OutputForm -> OutputForm. I don't think there would be any problem with
it as long as we either leave the relevant heads of OutputForm as they
are now, or even better document their intended meaning as clearly as
possible, so that transformer and formatter routines can build on it and
one could perhaps apply even two or more transformers.

In that sense SCOPE should be included into the list of possible
OutputForm heads and can be treated as NOOP by the current formatters.

> Note: such transformations are possible now and some
> are done by default. But they may be wrong for
> some domains, so we need extra semantic info in
> output form to make sure such transformations
> are reliable.

I am sceptical about putting more semantics into OutputForm. In fact, I
see OutputForm as the structure that comes right before the actual
output. So I would not put algebraic knowledge into it. If we want that,
I would rather opt for a general expression tree structure that has all
semantic information. You might want to look at ExpressionTree and
related domains in the Aldor library. Yes, it is a different approach
than that of OutputForm. I could not yet decide which one I find better,
but both have their pros and cons. Anyway, a proper ExpressionTree in
FriCAS would probably not be such a bad idea. I haven't thought deeply
about this, but it would also be a bit like input form.

Anyway, why can transformations not be done in our current Expression
domain and then be converted to OutputForm?

I think for a really flexible approach there is much open for discussion.

> You somewhat think that changing output form
> is problematic.

No, not really. Just thought it is unnecessary.

Ralf

PS: I will be away from the internet till August.