Questions about SPAD / best practices / resources?

[Tobias Neumann]

Hello!

What is the best resource for SPAD? Aldor has a really excellent book

( https://www.aldor.org/docs/aldorug.pdf ) and I don't suppose that SPAD has something similar? Presumably the FriCAS book ( https://fricas.github.io/book.pdf ) and the FriCAS source are the best resources? The FriCAS book covers SPAD in chapters 12 and 13, but I feel it's not sufficient for me, especially when it comes to compiler errors.

I am currently struggling to implement functions around series expansions. It's probably one of the most complicated situations to start with due to the dependent types, but it's what I need :)

My ultimate goal is to write a function (in a package) that takes an expression for series expansion and the expansion point and returns the series expansion. So basically as a first step I would just like to write a simple wrapper around series/taylor/puiseux with fixed input/output types.

I've tried this in a SPAD function:

           x := 'x

           ex := x :: Expression(Integer) 

           eqn := (ex = 0)

           testseries := taylor(x,eqn)

But the compiler complains about

   >> Apparent user error:

   NoValueMode

    is an unknown mode

What does such an error mean? I tried to get away with a minimal number of type annotations, but adding additional for the taylor function doesn't seem to help this error.

Furthermore, suppose I want to write a wrapper around taylor, could I write the function with dependent types like this (I think something like this would work in Aldor):

wrapper : (Expression(Integer), p:Expression(Integer), x0:Integer) -> UnivariateTaylorSeries(Expression(Integer), p, x0)

wrapper (expr, x, x0) == series(expr,x=x0)

I would appreciate some help regarding this. Eventually I might be able to write a tuturial with my struggles for future users.

Tobias

[Waldek Hebisch]

On Mon, Jan 25, 2021 at 11:11:20AM -0800, Tobias Neumann wrote:
> Hello!
>
> What is the best resource for SPAD? Aldor has a really excellent book
> ( https://www.aldor.org/docs/aldorug.pdf ) and I don't suppose that SPAD
> has something similar? Presumably the FriCAS book (
> https://fricas.github.io/book.pdf ) and the FriCAS source are the best
> resources? The FriCAS book covers SPAD in chapters 12 and 13, but I feel
> it's not sufficient for me, especially when it comes to compiler errors.
>
> I am currently struggling to implement functions around series expansions.
> It's probably one of the most complicated situations to start with due to
> the dependent types, but it's what I need :)

You will be looking at darkest corners of Spad compiler. There
are bugs and limitations affecting series. You can look at
existing algebra code to see how it deals with problems.

> My ultimate goal is to write a function (in a package) that takes an
> expression for series expansion and the expansion point and returns the
> series expansion. So basically as a first step I would just like to write a
> simple wrapper around series/taylor/puiseux with fixed input/output types.

It is not clear for me what you really want to do (in FriCAS there
are already several different functions fitting your description
above). For calling existing expanders you may look at
function 'expr_to_series' in 'src/algebra/mrv_limit.spad'.

BTW: 'taylor' already is a wrapper, so to see how wrappers works
you can look up code of 'taylor' in 'src/algebra/expr2ups.spad'.

BTW2: If you look up 'taylor' in HyperDoc you will see several
signatures, you need to tell Spad compiler which one you want
(for example by importing appropriate packege or via explicit
qualification that I did below). Once you found correct
signature in HyperDoc 'descriptions' view you can click at
'Origin' field to see package description. In package
description you can click at 'Source File' field to see
source file. At least on my system title bar of source
window contains file name, so if you prefer you can use
different viewer to see the file (or fiddle a but with
environment variables so that HyperDoc invokes your
preffered viewer).

> I've tried this in a SPAD function:
> x := 'x
> ex := x :: Expression(Integer)
> eqn := (ex = 0)
> testseries := taylor(x,eqn)
>
> But the compiler complains about
> >> Apparent user error:
> NoValueMode
> is an unknown mode
>
> What does such an error mean?

Spad compiler has to deal with potentialy infinte set of types
and with overloading. Also Spad lets you omit most type
annotations. This means that Spad has to reconstruct missing
information. Errors like above mean that Spad is unable to
find consistent types. Spad can not be much more accurate
than this, partially due to internal limitations, partially
because huge (potentially infinte) number of possible
errors and fixes. And yes, adding type/package annotations
is right thing to do.

> I tried to get away with a minimal number of
> type annotations, but adding additional for the taylor function doesn't
> seem to help this error.

You need to be persistent. AFAICS the following works:

-------------<cut here>----------------

)abbrev package MYTAYL MyTaylorExpansion

MyTaylorExpansion : with
my_taylor : Expression(Integer) -> Any
== add

e_pak ==> ExpressionToUnivariatePowerSeries(Integer,
Expression(Integer))

my_taylor(f) ==

x := 'x
ex := x :: Expression(Integer)

eqn := equation(ex, 0)$Equation(Expression(Integer))
testseries := taylor(f, eqn)$e_pak

-------------<cut here>----------------

BTW: Error messages typically point to offending part, first
error pointed out to 'taylor' so it was easy to deduce that
I need to specify the package. Then I got:

error in function my_taylor

(SEQ (|:=| |x| '|x|) (|:=| |ex| (|::| |x| (|Expression| (|Integer|))))
(|:=| |eqn| (= |ex| 0))
(|exit| 1
(|:=| |testseries|
((|Sel|
(|ExpressionToUnivariatePowerSeries| (|Integer|)
(|Expression| (|Integer|)))
|taylor|)
|f| | << eqn >> |))))
****** level 5 ******
$x:= eqn
$m:= (Equation (Expression (Integer)))
$f:=
((((|eqn| #) (|ex| #) (|x| #) (|f| # #) ...)))

>> Apparent user error:
Cannot coerce eqn
of mode (Boolean)
to mode (Equation (Expression (Integer)))

This told me that Spad took wrong type for 'ex = 0'. So
I replaced '=' with 'equation'. Then I got another
error about 'equation(ex, 0)' so I made it more specific.

> Furthermore, suppose I want to write a wrapper around taylor, could I write
> the function with dependent types like this (I think something like this
> would work in Aldor):
>
> wrapper : (Expression(Integer), p:Expression(Integer), x0:Integer) ->
> UnivariateTaylorSeries(Expression(Integer), p, x0)
> wrapper (expr, x, x0) == series(expr,x=x0)

No. You can get similar effect to dependent types using extra
indirection via helper packages/domains, but in this case
extra indirection would defeat your purpose.

--
Waldek Hebisch

[Tobias Neumann]

Hello Kurt, Waldek,

thank you for those helpful links and the detailed example.

I have extended the example type domain so that I can use 'approximate' (see below), which induces some further type constraints

that do not seem to be satisfied by just Expression(Integer).

While the code example below compiles fine, it seems that the retraction from AnyFunctions1 fails:

   >> Error detected within library code:
   Cannot retract value.

The statements work fine with the FriCAS interpreter, so I assume that the interpreter performs some additional type conversion

that I am missing here. What is the best way to debug something like this, given that the interpreter seems to take some additional steps that make it work.

Could, in this case, 'retract' not report the type wrapped by 'Any' for debugging? 

If 'Any' acts as a wrapper to any type and saves that information, why can 'retract' fail? Wouldn't it just have to always unwrap the internally saved type?

Otherwise, how does the interpreter automatically unwrap it to the correct type?

For example in the interpreter this works without any issues (with bottom messages on), and apparently without any additional type conversions:

(31) -> fromany := retract(testseries)$AnyFunctions1(UnivariateTaylorSeries(FE,ex,ex0))

 Function Selection for retract
      Arguments: ANY
      Target type: UTS(EXPR(INT),x,x0)
      From:      ANY1(UTS(EXPR(INT),x,x0))

 [1]  signature:   ANY -> UTS(EXPR(INT),x,x0)
      implemented: slot (UnivariateTaylorSeries (Expression (Integer)) x ((1 #S(SPAD-KERNEL :OP #(|x0| 0 (((|%symbol|)))) :ARG NIL :NEST 1) (1 0 . 1)) 0 . 1))(Any) from ANY1(UTS(EXPR(INT),x,x0))

   (31)  f
                       Type: UnivariateTaylorSeries(Expression(Integer),x,x0)

---- SNIP ----

)abbrev package MYTAYL MyTaylorExpansion

MyTaylorExpansion(R, FE) : Exports == Implementation where
    R  : Join(GcdDomain, Comparable, RetractableTo Integer, _
              LinearlyExplicitOver Integer)
    FE : Join(AlgebraicallyClosedField, TranscendentalFunctionCategory, _
              FunctionSpace R)

    Exports ==> with
        my_taylor : (FE, R) -> FE

    Implementation ==> add
        e_pak ==> ExpressionToUnivariatePowerSeries(R,FE)

        my_taylor(f, x0) ==
            ex := 'x :: FE
            ex0 := x0 :: FE
            eqn := equation(ex, ex0)$Equation(FE)
            testseries := taylor(f, eqn)$e_pak
            fromany := retract(testseries)$AnyFunctions1(UnivariateTaylorSeries(FE,ex,ex0))
            approx := approximate(fromany::UnivariateTaylorSeries(FE,ex,ex0),3)$UnivariateTaylorSeries(FE,ex,ex0)
            approx

---- SNIP ----

--
You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" group.
To unsubscribe from this group and stop receiving emails from it, send an email to fricas-devel...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/fricas-devel/20210125230626.GA11077%40math.uni.wroc.pl.

[Waldek Hebisch]

On Wed, Jan 27, 2021 at 09:54:42PM -0500, Tobias Neumann wrote:
> Hello Kurt, Waldek,
> thank you for those helpful links and the detailed example.
>
> I have extended the example type domain so that I can use 'approximate'
> (see below), which induces some further type constraints
> that do not seem to be satisfied by just Expression(Integer).
>
> While the code example below compiles fine, it seems that the retraction
> from AnyFunctions1 fails:
> >> Error detected within library code:
> Cannot retract value.
> The statements work fine with the FriCAS interpreter, so I assume that the
> interpreter performs some additional type conversion
> that I am missing here. What is the best way to debug something like this,
> given that the interpreter seems to take some additional steps that make it
> work.
> Could, in this case, 'retract' not report the type wrapped by 'Any' for
> debugging?

The problem here is that you gave wrong type as argument to
AnyFunctions1 (type wrapped by Any was OK). I saw the
problem by adding Lisp debugging printouts to
AnyFunctions1 and recompiling it.

In principle the problem should be catched at compile time,
but currently Spad compiler can not catch it. Difficulty is
that to do type checking we need types, but types have parameters
which need type checking and the whole thing is recursive
so we may learn that type parameters are OK only after we
had to use the type. Currently Spad compiler resolves this
taking type "on faith" and hoping that error will be caught
later. In this case type error survives to runtime.
Anyway, the problem is that you wrote:

UnivariateTaylorSeries(FE,ex,ex0)

where 'ex' is expression, while correct type is symbol.
At runtime (as Lisp value) 'x' as expression is quite
different than 'x' as symbol so AnyFunctions1
decided that you try to retract to wrong type and
signals error. Interpreter was smart enough to
notice that it needs symbol and converted 'x'
from expression to symbol.

There is another difficulty, literal 'x' does not
work as expected due to different representation
used in Spad compiler and in interpreter. Enough
indirection should work around this problem, for
example pass 3 arguments to 'my_taylor', including
symbol.

--
Waldek Hebisch

[Tobias Neumann]

Thank you, that indeed explains the issue. My confusion

arose because the equation (obviously) has to take the symbol as FE.

My next issue is when trying to construct a list of series expansions (see my snippet later):

(I added the [1,1,1] at the end to not introduce more errors from trying to use 'approximate')

(Ultimately I want to obtain a Matrix or Lists of Lists of series expansions)

testseries := map((elem:FE): uts +-> retract(taylor(elem, eqn)$e_pak)$any1, ff) :: List(uts)

This fails with:

   >> Apparent user error:
   Cannot coerce (CONS (CLOSEDFN (LAMBDA ((elem ) ($$ )) (PROG (eqn $ uts any1) (SETQ eqn (QREFELT $$ 3)) (SETQ $ (QREFELT $$ 2)) (SETQ uts (QREFELT $$ 1)) (SETQ any1 (QREFELT $$ 0)) (RETURN (PROGN (SPADCALL (SPADCALL elem eqn (QREFELT $ 15)) (compiledLookupCheck (QUOTE retract) (LIST (devaluate uts) (LIST (QUOTE Any))) any1))))))) (VECTOR any1 uts $ eqn))
      of mode (Mapping uts FE)
      to mode ##2

If I leave out the anonymous function type signature,

    testseries := map(elem +-> retract(taylor(elem, eqn)$e_pak)$any1, ff) :: List(uts)

the error changes to:
   >> Apparent user error:
   Cannot coerce elem
      of mode uts
      to mode ##2

Is this another user error or a problem with the compiler?

Another unrelated question: Assuming I pass a series expansion wrapped as type 'Any' to some function,

am I able to reconstruct the underlying series type just from that? Schematically, having

myseries of type Any, can I do something like unwrapped := retract(myseries)$AnyFunctions1(dom(myseries)),

(where dom returns the domain and not an SExpression),

or can I pass the underlying domain as another parameter to a function? Along the lines of:

doSomethingWithSeries : (Any, Type)-> Expression(Integer)

doSomethingWithSeries (ser, type) ==

    unwrapped := retract(ser)$AnyFunctions1(type)

    approximate(unwrapped,5)

--- SNIP ---

)abbrev package MYTAYL MyTaylorExpansion

MyTaylorExpansion(R, FE) : Exports == Implementation where
    R  : Join(GcdDomain, Comparable, RetractableTo Integer, _
              LinearlyExplicitOver Integer)
    FE : Join(AlgebraicallyClosedField, TranscendentalFunctionCategory, _
              FunctionSpace R)

    Exports ==> with

        my_taylor : (List(FE), Symbol, R) -> List(FE)

    Implementation ==> add
        e_pak ==> ExpressionToUnivariatePowerSeries(R,FE)

        my_taylor(ff, sym, x0) ==
            eqn := equation(sym :: FE, x0 :: FE)$Equation(FE)
            uts := UnivariateTaylorSeries(FE,sym,x0::FE)
            any1 := AnyFunctions1(uts)
            testseries := map((elem:FE): uts +-> retract(taylor(elem, eqn)$e_pak)$any1, ff) :: List(uts)
            [1,1,1] :: List(FE)

--- SNIP ---

I have tried something similar using interpreted FriCAS:

EI ==> Expression(Integer)

dostuff3(x0, sym, lst) ==
    local uts, any1, x
    uts := UnivariatePuiseuxSeries(EI,sym, x0)
    any1 := AnyFunctions1(uts)
    map((elem:EI): uts +-> retract(puiseux(elem, equation(sym :: EI,x0)))$any1, lst)

x := 'x :: Symbol
expr := x^2 + x :: EI
lst := [expr,expr,expr]
dostuff3(3::EI, x, lst)

which results in

   Local variable or parameter used in type
   We will attempt to interpret the code.
   Cannot compile a $-expression involving a local variable.
   FriCAS will attempt to step through and interpret the code.

   any1 is not a valid type.

Thanks again for the great help. I think once I've stepped through the struggles with the parametrized types

for series anything else should reduce to getting familiar with the API.

[Waldek Hebisch]

I do not know it is all, but there is basic user error above:
before you call a function package/domain containing the
function must be imported. Spad compiler automatically
is doing some imports, but this is quite limited.
Unlike interpreter which aggressively searches database
of defined functions Spad compiler will not see 'map'
that you want to use. To clarify a bit: Spad uses
overloading so from point of view of Spad compilers
there are a lot of different 'map' functions defined
in many places. You need to either import package
defining this function or use '$' qualification.
Error may look weird, but simply Spad tells you that
your arguments do not fit 'map' that Spad tried to use.
This is because there is a lot of 'map' functions and
without import (or '$' qualification) Spad has only
wrong ones.

Extra things:
- ATM '$' qualification is doing import, so next use
of the same function works without qualification,
but at some moment this will be fixed
- each parameter tuple gives you different type and
requires separate import
in the future

AFAICS you want 'map' from ListFunctions2 (with appropriate
parameters). There are a lot of packages called like
XxxxFunctions2 and they contain functions acting between
two types (like 'map' that you want).

> Another unrelated question: Assuming I pass a series expansion wrapped as
> type 'Any' to some function,
> am I able to reconstruct the underlying series type just from that?
> Schematically, having
> myseries of type Any, can I do something like unwrapped :=
> retract(myseries)$AnyFunctions1(dom(myseries)),
> (where dom returns the domain and not an SExpression),
> or can I pass the underlying domain as another parameter to a function?
> Along the lines of:
>
> doSomethingWithSeries : (Any, Type)-> Expression(Integer)
> doSomethingWithSeries (ser, type) ==
> unwrapped := retract(ser)$AnyFunctions1(type)
> approximate(unwrapped,5)

1) You can pass types as parameters. Note that types also
have types, and if you have something that is just 'type'
there is not much that you can do with it. In
particular call to 'approximate' would fail.
Rather, normally instead of Type you would have category
like Group, then you should be able to call group operations
I can not tell you code above will work with proper category
definition, but it can not work without category definition
(or other type info). To call approximate appropriate
category is 'UnivariateTaylorSeriesCategory', but specifying
it means that you need to specify cefficient type
(variable name and center remain unspecified).

2) Usually types are passed of parameters to domain
constructors. Namely, for example 'Expression' is
effectively a function from types to types. You
can pass type constructed at runtime to 'Expression'
and get new type. Spad compilers handles domain
constructors is special way, in particular uses
elaborate caching scheme to avoid repeating computations
on types. If you create new types on whim and
intensively use them you may be surprized by poor
performance. Computers are now fast enough that
you will feel nothing for small computations, but
when you care about speed computations that limits
runtime use of types may be much faster. If you
are doing something inherently expensive, then
runtime use of type may be insignificant in
comparison, but avoid runtime types in inner loops.

3) There is no official way to get type from Any.
Internaly there is Lisp function 'evalType' that
given Sexpression returns Type.

4) I would discourage Spad code based on Any. Any
is used in limited number of situations, basically
when type depends on something known to code but
dependence is too complicated to express in Spad.
Once type is known use normal package parameters to
pass type info. So instead of

AnyPak : with
doSomethingWithSeries: (Any, Type)-> Expression(Integer)
....

have

Pak(T : Type) : with
doSomethingWithSeries: T -> Expression(Integer)

doing 'retract' at call site. If you need to pass Any,
than

Pak(T : Type) : with
doSomethingWithSeries: Any -> Expression(Integer)
...

doSomethingWithSeries(a) ==
a_val := retract(a)$AnyFunctions1(T)
...

is better.

5) Current style in FriCAS algebra is to pass around a lot
of parameters to domain constructors. And use helper
packages like ListFunctions2 so that needed types are
are determined by parameters. This is sometimes
inconvenient and certainly different coding styles are
worth investigation. But current code and design
is adapted to coding style and all this together
works reasonably well. Different coding style
would probably require large changes to algebra
code to make new style really viable.

> I have tried something similar using interpreted FriCAS:
>
> EI ==> Expression(Integer)
>
> dostuff3(x0, sym, lst) ==
> local uts, any1, x
> uts := UnivariatePuiseuxSeries(EI,sym, x0)
> any1 := AnyFunctions1(uts)
> map((elem:EI): uts +-> retract(puiseux(elem, equation(sym ::
> EI,x0)))$any1, lst)
>
> x := 'x :: Symbol
> expr := x^2 + x :: EI
> lst := [expr,expr,expr]
> dostuff3(3::EI, x, lst)
>
> which results in
>
> Local variable or parameter used in type
> We will attempt to interpret the code.
> Cannot compile a $-expression involving a local variable.
> FriCAS will attempt to step through and interpret the code.
>
> any1 is not a valid type.

There are bugs with handling local types in interprter (this may
be one of them). I would suggest sticking to global ones if
possible (at least you should get better error messages). Note
that you can re-assign global types and FriCAS interpreter will
recompile your functions to take into account changed types. Also,
interprter code using global types is easy to convert to
Spad code which uses domain parameters. Local types
behave better in Spad code but there is potential inefficiency
(probaly smaller than cost of recompilation...).

--
Waldek Hebisch