Maybe preview

[oldk1331]

I have fixed Maybe so that it can be inline optimized.

You can see it here:

https://github.com/oldk1332/fricas/commits/maybe

https://github.com/oldk1332/fricas/commit/bc2b445305da41a74f16dd8b982f31e5582ac274.patch

https://github.com/oldk1332/fricas/commit/513b9e680bdff9a4def2a1b2621f825aa7eb4113.patch

All tests passed : https://travis-ci.org/oldk1331/fricas/builds/280395329

I have to say, there's so many dark magic to make
inline optimization work.

One thing I'm not clear yet: what does 'initial-getdatabase'
in daase.lisp do? Should Maybe be added there?

[Bill Page]

This is great but I definitely do not like to read "wrap" ... "unwrap"
... in spad source code. Didn't you say that we were now "on the same
page" with "coerce" and "retract"?

Do you notice any differences in performance and space utilization?

> --
> 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 post to this group, send email to fricas...@googlegroups.com.
> Visit this group at https://groups.google.com/group/fricas-devel.
> For more options, visit https://groups.google.com/d/optout.

[oldk1331]

The point of 'wrap/unwrap' or something like that is to avoid to
specify type. Like you can use

x := wrap y

instead of

x : Maybe A_VERY_LONG_TYPE := coerce y

And you can use 'coerce' this way, but I prefer 'wrap', because
usually there are many 'coerce' for a type, but there's only one 'wrap'.

As for 'retract', because 'retractIfCan' should return a Maybe,
that makes Maybe more fundamental than RetractableTo.
And for the same reason, one can use 'unwrap' to avoid to
specify type.

If you don't like the name of 'wrap/unwrap', there has to be
replacement other than 'coerce/retract', so what do you suggest?
(Like Haskell's 'just/fromJust'?)

[Bill Page]

On 27 September 2017 at 19:05, oldk1331 <oldk...@gmail.com> wrote:
> The point of 'wrap/unwrap' or something like that is to avoid to
> specify type. Like you can use
>
> x := wrap y
>
> instead of
>
> x : Maybe A_VERY_LONG_TYPE := coerce y
>

That is very much against the spirit of the SPAD language which was
designed to support complete source and target polymorphism of
operators. I do not think it is desirable to avoid specify types -
even when they are long, e.g. use macros to abbreviate if you must.

If I were to accept your argument this would imply that we should try
to reduce this sort of polymorphism in many other existing uses of
coerce/retract and in the case of other similar operators.

> And you can use 'coerce' this way, but I prefer 'wrap', because
> usually there are many 'coerce' for a type, but there's only one 'wrap'.
>

I do not like the idea that there is only one 'wrap'.

> As for 'retract', because 'retractIfCan' should return a Maybe,
> that makes Maybe more fundamental than RetractableTo.

?? RetractableTo is a category constructor, Maybe is a domain. Maybe
is not more fundamental than RetractableTo. I do not see any problem
that in the case of Maybe retractIfCan would become an identity.

> And for the same reason, one can use 'unwrap' to avoid to
> specify type.
>
> If you don't like the name of 'wrap/unwrap', there has to be
> replacement other than 'coerce/retract', so what do you suggest?
> (Like Haskell's 'just/fromJust'?)
>

I like the Axiom/FriCAS convention of using polymorphism to emphasize
the generic algebraic properties of operators. So I do not like to
replace coerce/retract with some other names in specific cases. And
although they are not obviously dual, changing coerce/retract to some
other pair of names throughout FriCAS does not seem desirable either.

Bill.

[oldk1331]

On Thu, Sep 28, 2017 at 10:26 AM, Bill Page <bill...@newsynthesis.org> wrote:
> On 27 September 2017 at 19:05, oldk1331 <oldk...@gmail.com> wrote:
>> The point of 'wrap/unwrap' or something like that is to avoid to
>> specify type. Like you can use
>>
>> x := wrap y
>>
>> instead of
>>
>> x : Maybe A_VERY_LONG_TYPE := coerce y
>>
>
> That is very much against the spirit of the SPAD language which was
> designed to support complete source and target polymorphism of
> operators. I do not think it is desirable to avoid specify types -
> even when they are long, e.g. use macros to abbreviate if you must.

You can also write those long types when using 'wrap'. It's not
against type annotation. We should also have the ability of
type inference, which is impossible for 'coerce' (because there
are too many).

However your suggestion is against another FriCAS spirit:
the ability to avoid type in interpreter. You can simply right
'wrap 1', but 'coerce 1' has so many different meanings.

> If I were to accept your argument this would imply that we should try
> to reduce this sort of polymorphism in many other existing uses of
> coerce/retract and in the case of other similar operators.

It does not hurt to have synonym, I support to have both 'coerce'
and 'wrap'.

>> And you can use 'coerce' this way, but I prefer 'wrap', because
>> usually there are many 'coerce' for a type, but there's only one 'wrap'.
>>
>
> I do not like the idea that there is only one 'wrap'.

I'm not saying "only wrap, no coerce", I'm saying 'wrap' has only
one meaning, that's "create a Maybe".

>> As for 'retract', because 'retractIfCan' should return a Maybe,
>> that makes Maybe more fundamental than RetractableTo.
>
> ?? RetractableTo is a category constructor, Maybe is a domain. Maybe
> is not more fundamental than RetractableTo. I do not see any problem
> that in the case of Maybe retractIfCan would become an identity.

If Maybe R has RetractableTo R, I find this signature a little funny:

retractIfCan : Maybe R -> Maybe R

But it won't hurt to have RetractableTo/retract, but follow the
same reasoning above, I (and others) should prefer 'unwrap'
over 'retract'.

>> And for the same reason, one can use 'unwrap' to avoid to
>> specify type.
>>
>> If you don't like the name of 'wrap/unwrap', there has to be
>> replacement other than 'coerce/retract', so what do you suggest?
>> (Like Haskell's 'just/fromJust'?)
>>
>
> I like the Axiom/FriCAS convention of using polymorphism to emphasize
> the generic algebraic properties of operators. So I do not like to
> replace coerce/retract with some other names in specific cases. And
> although they are not obviously dual, changing coerce/retract to some
> other pair of names throughout FriCAS does not seem desirable either.
>
> Bill.

OK, let me persuade you in this way, Maybe is a Monad, and so is List.
Do you wish to have these signature ONLY for List
(and every possible Monad):

coerce : S -> List S
retract : List S -> S

For List, the signature 'S -> List S' is named 'list', and
the signature 'List S -> S' is named 'first'.

[oldk1331]

Hmm, seems the inline optimization only works for Package,
not Domain. Any hints?

[Ralf Hemmecke]

On 09/28/2017 11:43 AM, oldk1331 wrote:
> Hmm, seems the inline optimization only works for Package,
> not Domain. Any hints?

Sorry, I've no idea about these internals, but it somewhat surprises me.
Packages and domains are not really different, as I see it. It's only
that in domains there are exported signatures that inolve % and in
packages there is no %.

Does % really make such a big difference from a compiler point of view?
In particular when it comes to inlining?

Ralf

[Ralf Hemmecke]

On 09/28/2017 04:53 AM, oldk1331 wrote:
>>> specify type. Like you can use
>>>
>>> x := wrap y
>>>
>>> instead of
>>>
>>> x : Maybe A_VERY_LONG_TYPE := coerce y

one usually writes

x := y :: SOME_TYPE

so I wouldn't be against

y :: Maybe(T)

even if T is A_VERY_LONG_TYPE. As Bill said, one can use a macro to make
it more readable.

I tend to be more on the side of coerce/retract instead of wrap/unwrap.

Unfortunately 'wrap' has noting that reminds me of the fact that the
result type is Maybe(.). Perhaps maybe: T -> Maybe(T) would also be a
good name with counterpart retract: Maybe(T) -> T.

I think that x :: T instead of retract(x) also looks nice.

But, actually, I don't want to discuss the syntax at this point. (I even
think that Partial as in Aldor, is a better name than Maybe.)

Most important is if Qian can prove that the concept makes sense in
order to speed up certain parts of FriCAS. And I am happy that he is so
eager to look seriously into this issue.

Ralf

[oldk1331]

After some debugging, seems this is the cause:

diff --git a/src/interp/nruncomp.boot b/src/interp/nruncomp.boot
index 323080a1..cd7dbea6 100644
--- a/src/interp/nruncomp.boot
+++ b/src/interp/nruncomp.boot
@@ -137,7 +137,7 @@ optDeltaEntry(op,sig,dc,eltOrConst) ==
sig := substitute(devaluate dcval, ndc, sig)
if rest ndc then
for new in rest devaluate dcval for old in rest ndc repeat
- sig := substitute(new, old, sig)
+ sig := substitute(new, "$$", sig)
-- optCallEval sends (List X) to (List (Integer)) etc,
-- so we should make the same transformation
fn := compiledLookup(op,sig,dcval)

So for

)abbrev domain TEST1 Test1
Test1 : with
f1 : % -> Vector %
== add
f1 x == empty()

It used to generate

(SDEFUN |TEST1;f1;$V;1| ((|x| $) ($ |Vector| $)) (SPADCALL (QREFELT $ 7)))

After the patch, it generates:

(SDEFUN |TEST1;f1;$V;1| ((|x| $) ($ |Vector| $)) (MAKE-ARRAY 0))

[oldk1331]

Benchmarks:

Memory usage:
I measured it with ')lisp (sb-ext:get-bytes-consed)'

When storing 100K "failed" values in List,
Union(Integer, "failed") takes 3.2MB memory
Maybe Integer takes 1.6MB memory

I think the "failed" is alloced as String multiple times.

Also see the generated lisp code for subtractIfCan$NNI:

Maybe version, no extra CONS:

(SDEFUN |NNI;subtractIfCan;2$M;4| ((|x| $) (|y| $) ($ |Maybe| $))
(SPROG ((|c| (|Integer|)))
(SEQ (LETT |c| (- |x| |y|) |NNI;subtractIfCan;2$M;4|)
(EXIT (COND ((< |c| 0) *MAYBEFAIL*) ('T |c|))))))

Union version, with extra CONS:

(SDEFUN |NNI;subtractIfCan;2$U;4| ((|x| $) (|y| $) ($ |Union| $ "failed"))
(SPROG ((|c| (|Integer|)))
(SEQ (LETT |c| (- |x| |y|) |NNI;subtractIfCan;2$U;4|)
(EXIT
(COND ((< |c| 0) (CONS 1 "failed")) ('T (CONS 0 |c|)))))))

"unwrap(x)" generates |maybe_unwrap|, "x::R" generates
|check_union2|, and |maybe_unwrap| is slightly simpler than
|check_union2|.

So, Maybe uses less memory and generates better inlined
lisp code than Union.

[Bill Page]

On 29 September 2017 at 07:36, oldk1331 <oldk...@gmail.com> wrote:
> Benchmarks:
>
> Memory usage:
> I measured it with ')lisp (sb-ext:get-bytes-consed)'
>
> When storing 100K "failed" values in List,
> Union(Integer, "failed") takes 3.2MB memory
> Maybe Integer takes 1.6MB memory
>
> I think the "failed" is alloced as String multiple times.

No, in Lisp a string is allocated only once after which only pointers
are involved. The extra space is because the rep of Union requires
both a tag and a pointer to a value. FriCAS Integer (mutliprecision)
is allocated in a similar way. In most Lisps I think a single
precision integer occupies the same space as a pointer. Your new Maybe
uses exactly and only the same space as the underlying domain.

>
> Also see the generated lisp code for subtractIfCan$NNI:
>
> Maybe version, no extra CONS:
>
> (SDEFUN |NNI;subtractIfCan;2$M;4| ((|x| $) (|y| $) ($ |Maybe| $))
> (SPROG ((|c| (|Integer|)))
> (SEQ (LETT |c| (- |x| |y|) |NNI;subtractIfCan;2$M;4|)
> (EXIT (COND ((< |c| 0) *MAYBEFAIL*) ('T |c|))))))
>
> Union version, with extra CONS:

> ...

I think this new generated code is excellent.

On 27 September 2017 at 22:53, oldk1331 <oldk...@gmail.com> wrote:

> ,,,

> However your suggestion is against another FriCAS spirit:
> the ability to avoid type in interpreter. You can simply right
> 'wrap 1', but 'coerce 1' has so many different meanings.
>

The goal in the interpreter is to relieve the user of having to
explicitly specify types in many common situations by applying some
heuristic inferences. It is not a goal to avoid specifying types
altogether. It seems to me that directly construct values in some
'Maybe' domain will not be common operation for FriCAS interpreter
users. However it is possible that they might end up obtaining such a
value as an exceptional result of an operation. That is why I thought
it was important that the interpreter try to do something "sensible"
with a value from a Maybe domain by automatically attempting to
retract the value to the underlying domain - something that the
interpreter will do for values in any domain that satisfies
RetractableTo.

>> If I were to accept your argument this would imply that we should
>> try to reduce this sort of polymorphism in many other existing
>> uses of coerce/retract and in the case of other similar operators.
>
> It does not hurt to have synonym, I support to have both 'coerce'
> and 'wrap'.

Well, it does hurt a little to have to recall the name of a
special-case operator when reading unfamiliar code. But I admit that
my point is only about a minor cognitive dissonance. My only reason
for persisting in this discussion is that now seems like the only
opportunity we will have to avoid it. But if you insist of course it
will not be worse than any of the many other issues already
irrevocably embedded in the FriCAS/SPAD language.

>
>>> As for 'retract', because 'retractIfCan' should return a Maybe,
>>> that makes Maybe more fundamental than RetractableTo.
>>
>> ?? RetractableTo is a category constructor, Maybe is a domain.
>> Maybe is not more fundamental than RetractableTo. I do not see
>> any problem that in the case of Maybe retractIfCan would become
>> an identity.
>
> If Maybe R has RetractableTo R, I find this signature a little funny:
>
> retractIfCan : Maybe R -> Maybe R
>

Identities of this sort are very natural and indeed even critical in
an algebraic design.

> But it won't hurt to have RetractableTo/retract, but follow the
> same reasoning above, I (and others) should prefer 'unwrap'
> over 'retract'.
>
>>> And for the same reason, one can use 'unwrap' to avoid to
>>> specify type.
>>>

Why avoid specifying type?

>
> OK, let me persuade you in this way, Maybe is a Monad, and
> so is List. Do you wish to have these signature ONLY for List
> (and every possible Monad):
>
> coerce : S -> List S
> retract : List S -> S
>
> For List, the signature 'S -> List S' is named 'list', and
> the signature 'List S -> S' is named 'first'.
>

The essential export of Monad (if this concept existed in FriCAS) is
'map'. A Monad need not satisfy RetractableTo(R). 'Maybe' is a very
special Monad that satisfies both.

I would be happy if the 'list' operation was eliminated from FriCAS.
List values are normally and more natural constructed using
'construct', aka. [ ... ]

Bill Page.

[oldk1331]

Bill, since we can't persuade each other, I suggest you to convert
some Union("failed"..) to Maybe using 'coerce/retract', for example
rewrite function 'recip'.

Then you will find using 'coerce/retract' is verbose and unreadable.

[Bill Page]

OK, I will try what you suggest and then present the result.

[oldk1331]

A small problem to think about:

Maybe Maybe Integer

Should 't1 := wrap(failed()$Maybe Integer)' equal to
't2 := failed()$Maybe Maybe Integer'

Logically speaking, 'failed?(t1)' is false because t1 is
a Maybe(Integer) valued being wrapped. And 'failed?(t2)'
is true so they are not equal.

Current implementation of Maybe and Union("failed",...)
both think 't1=t2' is true.

Again, I think this is a small problem, because
1. there's no point of using Maybe(Maybe(XXX)).
2. thinking "failed" as a universal thing is understandable.

[Waldek Hebisch]

There is a big problem:
1) Union(X, "failed") may be used as representation for type
that from outside does not look like Union. Such type
may be used in another Union. When you convert to Maybe
you end up with Maybe(Maybe(...)) as representation.
ATM Union(X, "failed") is probably not used in any existing
domain, but OnePointCompletion uses Union(R, "infinity")
as representation. Arguably you should be able to
replace Union(R, "infinity") by Maybe(R).
2) For correctness we need to distinguish between inner domain
and outer domain.

--
Waldek Hebisch

[Bill Page]

A good model for the semantics of Maybe is a box that can contain at most one thing or otherwise is empty. A box that contains another box is not empty even if that box itself is empty.

Therefore I agree with Waldek.  It seems to me that each instantiation of Maybe should generate its own "failed" symbol rather than using a global value.

On Oct 4, 2017 12:59 PM, "Waldek Hebisch" <heb...@math.uni.wroc.pl> wrote:

oldk1331 wrote:
>
> A small problem to think about:
>
> Maybe Maybe Integer
>
> Should 't1 := wrap(failed()$Maybe Integer)' equal to
> 't2 := failed()$Maybe Maybe Integer'
>
> Logically speaking, 'failed?(t1)' is false because t1 is
> a Maybe(Integer) valued being wrapped. And 'failed?(t2)'
> is true so they are not equal.
>
> Current implementation of Maybe and Union("failed",...)
> both think 't1=t2' is true.
>
> Again, I think this is a small problem, because
> 1. there's no point of using Maybe(Maybe(XXX)).
> 2. thinking "failed" as a universal thing is understandable.

There is a big problem:
1) Union(X, "failed") may be used as representation for type
   that from outside does not look like Union.  Such type

   may be used in another Union.  ...

[oldk1331]

Waldek, Bill, yes, for correctness we need to distinguish
the inner domain and outer domain, and it's easy to
have a GENSYM() for each Maybe domain.

But that will hurt performance.

I think current situation is a good compromise. We can
say in documentation that all instances of Maybe share
a common value of failed(), and nested usage of Maybe
is not recommended, Maybe should not be used as Rep
itself but can be part of Rep. Do you agree?

On the other hand, OnePointCompletion should be able
to nest, and it does.

[Bill Page]

On 4 October 2017 at 19:38, oldk1331 <oldk...@gmail.com> wrote:
> Waldek, Bill, yes, for correctness we need to distinguish
> the inner domain and outer domain, and it's easy to
> have a GENSYM() for each Maybe domain.
>
> But that will hurt performance.
>

Why will this hurt performance?

> I think current situation is a good compromise. We can
> say in documentation that all instances of Maybe share
> a common value of failed(), and nested usage of Maybe
> is not recommended, Maybe should not be used as Rep
> itself but can be part of Rep. Do you agree?
>

I value correctness much more than performance except in the most
extreme and special cases.

[oldk1331]

On Thu, Oct 5, 2017 at 8:32 AM, Bill Page <bill...@newsynthesis.org> wrote:
> On 4 October 2017 at 19:38, oldk1331 <oldk...@gmail.com> wrote:
>> Waldek, Bill, yes, for correctness we need to distinguish
>> the inner domain and outer domain, and it's easy to
>> have a GENSYM() for each Maybe domain.
>>
>> But that will hurt performance.
>>
>
> Why will this hurt performance?

Instead of a direct reference to a global symbol, it will
perform a look up (QREFELT $ 7).

>> I think current situation is a good compromise. We can
>> say in documentation that all instances of Maybe share
>> a common value of failed(), and nested usage of Maybe
>> is not recommended, Maybe should not be used as Rep
>> itself but can be part of Rep. Do you agree?
>>
>
> I value correctness much more than performance except in the most
> extreme and special cases.

I would say Maybe is a special case, there are over 3700 occurrence
of "failed" alone in *.spad.

[Bill Page]

On 4 October 2017 at 20:44, oldk1331 <oldk...@gmail.com> wrote:
> On Thu, Oct 5, 2017 at 8:32 AM, Bill Page <bill...@newsynthesis.org> wrote:
>> On 4 October 2017 at 19:38, oldk1331 <oldk...@gmail.com> wrote:
>>> Waldek, Bill, yes, for correctness we need to distinguish
>>> the inner domain and outer domain, and it's easy to
>>> have a GENSYM() for each Maybe domain.
>>>
>>> But that will hurt performance.
>>>
>>
>> Why will this hurt performance?
>
> Instead of a direct reference to a global symbol, it will
> perform a look up (QREFELT $ 7).
>

How does this compare to the cost of testing case "failed" in the old
Union(R,"failed") representation?

>>> I think current situation is a good compromise. We can
>>> say in documentation that all instances of Maybe share
>>> a common value of failed(), and nested usage of Maybe
>>> is not recommended, Maybe should not be used as Rep
>>> itself but can be part of Rep. Do you agree?
>>>
>>
>> I value correctness much more than performance except in the most
>> extreme and special cases.
>
> I would say Maybe is a special case, there are over 3700 occurrence
> of "failed" alone in *.spad.
>

The number of occurrences is mostly irrelevant. The issue is how many
times is this lookup performed in a given given benchmark situation. I
would grant that the number of times is probably quite high in certain
types of computation. But would the new representation really be
slower than the old one?

[Bill Page]

Here is the first version of my rewrite of function 'recip' using my
proposal to make 'Maybe(R)' satisfy 'RetractableTo(R)' and using
'coerce/retract' insteal of 'warp/unwrap':

https://github.com/billpage/my-fricas/compare/maybe...billpage:maybe-retract

Contrary to the claim below, I did not find using 'coerce/retract'
verbose and unreadable. To me it seems clear and consistent. In fact
there were no cases in any of the 70 different files where 'recip' is
defined and used where I needed to add any additional type
information. In some cases there is slightly less since calling
retract (alias unwrap) instead of writing :: does not require
specifying a type.

I am quite sure that the situation must be the same for the rewrite of
'subtractIfCan' and that 'wrap/unwrap' can simply be replaced with
'coerce/retract' without any ambiguity.

I am sorry that this took me some time but it turned out that 'recip'
is quite deeply buried in FriCAS and the changes affected a lot of
code. I am still reviewing the changes and there may be a few places
where they can be polished a little.

Comments and criticism greatly appreciated.

Bill Page.

[oldk1331]

> How does this compare to the cost of testing case "failed" in the old
> Union(R,"failed") representation?

I did a crude benchmark on failed?, 200 loops over a vector with
10^6 elements of failed():

1. Union(NNI, "failed") 0.40s
2. Maybe NNI, 0.38s
3. "generic" Maybe NNI, can't be inlined, 1.24s

The problem with "generic" Maybe is that it can't be inlined.


About your changes to 'recip', a few comments:

1. There should be a function for 'not retractable?'

2. In xpoly.spad;

recip(p) ==
- p = 0 => "failed"
- p.first.k > 1$E => "failed"
- (u := recip(p.first.c)) case "failed" => "failed"
- (u::R)::%
+ p = 0 => failed
+ p.first.k > 1$E => failed
+ u := recip(p.first.c)
+ not retractable? u => failed
+ coerce(retract(u)::%)

There are 2 diferent coerce in the last line, I'd consider
wrap(unwrap(u)::%) more clear.

3. Again, my reasoning is that, when you see 'retract/coerce',
you don't know which type your are retract/coerce from/to,
you have to look up the context to know. With wrap/unwrap,
you are sure that you are dealing with Maybe.

Also, I have rebased my oldk1332/maybe branch a little.

[Ralf Hemmecke]

On 10/05/2017 02:32 AM, Bill Page wrote:
>> I think current situation is a good compromise. We can
>> say in documentation that all instances of Maybe share
>> a common value of failed(), and nested usage of Maybe
>> is not recommended, Maybe should not be used as Rep
>> itself but can be part of Rep. Do you agree?

> I value correctness much more than performance except in the most
> extreme and special cases.

There is no general "correctness". Code only behaves correctly

with respect to a certain specification.

As Qian said, the specification would claim Maybe to a very special
case. There is a fixed value "failed()" and that is global over all
domains and not element of any other domain than Maybe(X). Then Maybe(X)
represensts

X \cup \{failed()\}

With that, of course, Maybe(Maybe(X)) must behave like Maybe(X). I don't
see any (big) problem with that, just that Maybe(X) is not the same as
extending the domain by some new element, but it stands for "adding
failed() to the domain". I don't see any problem with "correctness".

However, then I would really opt for another name. Otherwise one might
think that Maybe behaves according to the type equation

FX = 1 + X

(see https://wiki.haskell.org/Maybe). Actually, I don't know whether
"Nothing" in Haskell is a global value, but I guess, it it not.

Ralf

[Ralf Hemmecke]

BTW, if X1 := Union(X,"failed") and X2 := Union(X1,"failed"), where in
current FriCAS is it specified that failed$X1 is different from failed$X2?

It probably is, but only by the general rule that no two domain have
elements in common. Even not NNI and Integer. We need coerce/retract (or
some special compiler knowledge in order to claim that 1$NNI is an
Integer. Internally they may have the same representation, but that does
not count on the surface.

Ralf

[Bill Page]

On 5 October 2017 at 01:09, Ralf Hemmecke <ra...@hemmecke.org> wrote:
> On 10/05/2017 02:32 AM, Bill Page wrote:
>>> I think current situation is a good compromise. We can
>>> say in documentation that all instances of Maybe share
>>> a common value of failed(), and nested usage of Maybe
>>> is not recommended, Maybe should not be used as Rep
>>> itself but can be part of Rep. Do you agree?
>
>> I value correctness much more than performance except in
>> the most extreme and special cases.
>
> There is no general "correctness". Code only behaves correctly
> with respect to a certain specification.
>

OK perhaps some word other than "correctness" would be better. Anyone
can write some arbitrary specification after the fact in order to
claim that a given piece of code is "correct". What I am concerned
about is consistency of FriCAS as a whole.

> As Qian said, the specification would claim Maybe to a very
> special case. There is a fixed value "failed()" and that is global
> over all domains and not element of any other domain than
> Maybe(X).

I do not want 'Maybe' to be a special case, like not other domain in
FriCAS. It would be completely against the design philosophy of the
original Axiom system to introduce a "fixed value that is global over
all domains".

> Then Maybe(X) represensts
>
> X \cup \{failed()\}
>
> With that, of course, Maybe(Maybe(X)) must behave like Maybe(X).

You did not define what you mean by \cup . Types are not sets. \cup
could be take to be disjoint union in which case

X \cup \{failed()\}

is not equal to

\cup \{failed()\} \cup \{failed()\}

> I don't see any (big) problem with that, just that Maybe(X) is not the
> same as extending the domain by some new element, but it stands
> for "adding failed() to the domain". I don't see any problem with
> "correctness".

failed() is not a value, it is the absence of a value.

> However, then I would really opt for another name. Otherwise one might
> think that Maybe behaves according to the type equation
>
> FX = 1 + X
>
> (see https://wiki.haskell.org/Maybe). Actually, I don't know whether
> "Nothing" in Haskell is a global value, but I guess, it it not.
>

In Haskell Maybe is a functor.

[Bill Page]

On 4 October 2017 at 23:41, oldk1331 <oldk...@gmail.com> wrote:
>> How does this compare to the cost of testing case "failed" in the old
>> Union(R,"failed") representation?
>
> I did a crude benchmark on failed?, 200 loops over a vector with
> 10^6 elements of failed():
>
> 1. Union(NNI, "failed") 0.40s
> 2. Maybe NNI, 0.38s
> 3. "generic" Maybe NNI, can't be inlined, 1.24s
>
> The problem with "generic" Maybe is that it can't be inlined.
>

It would help me to understand if you presented your benchmark code.
Here is something I just ran:

spage@strix ~ $ fricas -nox
Checking for foreign routines
AXIOM="/usr/local/lib/fricas/target/x86_64-linux-gnu"
spad-lib="/usr/local/lib/fricas/target/x86_64-linux-gnu/lib/libspad.so"
foreign routines found
openServer result 0
FriCAS Computer Algebra System
Version: FriCAS 2017-08-05
Timestamp: Wed Oct 4 20:47:59 EDT 2017
-----------------------------------------------------------------------------
Issue )copyright to view copyright notices.
Issue )summary for a summary of useful system commands.
Issue )quit to leave FriCAS and return to shell.
-----------------------------------------------------------------------------


(1) -> )r maybe-bench.input
)cl co

All user variables and function definitions have been cleared.
All )browse facility databases have been cleared.
Internally cached functions and constructors have been cleared.
)clear completely is finished.
)set message time on

A:PrimitiveArray Maybe NNI

Type: Void
Time: 0 sec
A:=new(10^5,failed()$Maybe(NNI));


Type: PrimitiveArray(Maybe(NonNegativeInteger))
Time: 0.03 (OT) = 0.03 sec
for j in 1..10 repeat for i in 0..#A-1 repeat failed? A(i)

Type: Void
Time: 4.28 (EV) + 0.01 (OT) = 4.28 sec
)co maybe-bench1.spad

Compiling FriCAS source code from file
/home/wspage/maybe-bench1.spad using old system compiler.
...
MaybeBench1 will be automatically loaded when needed from
/home/wspage/MAYB1.NRLIB/MAYB1

test1()


(4) 0
Type: NonNegativeInteger
Time: 1.56 (EV) + 0.01 (OT) = 1.58 sec
B:PrimitiveArray Union(NNI,"failed")

Type: Void
Time: 0 sec
B:=new(10^5,"failed"::Union(NNI,"failed"))$PrimitiveArray(Union(NNI,"failed"));


Type: PrimitiveArray(Union(NonNegativeInteger,"failed"))
Time: 0 sec
for j in 1..10 repeat for i in 0..#B-1 repeat B(i) case "failed"

Type: Void
Time: 3.90 (EV) = 3.90 sec
)co maybe-bench2.spad

Compiling FriCAS source code from file
/home/wspage/maybe-bench2.spad using old system compiler.
...
MaybeBench2 will be automatically loaded when needed from
/home/wspage/MAYB2.NRLIB/MAYB2

test2()


(8) 0
Type: NonNegativeInteger
Time: 0.98 (EV) + 0.01 (OT) = 0.98 sec
)co maybe.spad

Compiling FriCAS source code from file /home/wspage/maybe.spad using
old system compiler.
...
Maybe is now explicitly exposed in frame frame1
Maybe will be automatically loaded when needed from
/home/wspage/MAYBE.NRLIB/MAYBE

C:PrimitiveArray Maybe NNI

Type: Void
Time: 0 sec
C:=new(10^5,empty()$Maybe(NNI));


Type: PrimitiveArray(Maybe(NonNegativeInteger))
Time: 0.01 (OT) = 0.01 sec
for j in 1..10 repeat for i in 0..#C-1 repeat empty? C(i)

Type: Void
Time: 4.15 (EV) = 4.15 sec
)co maybe-bench3.spad

Compiling FriCAS source code from file
/home/wspage/maybe-bench3.spad using old system compiler.
...
MaybeBench3 is now explicitly exposed in frame frame1
MaybeBench3 will be automatically loaded when needed from
/home/wspage/MAYB3.NRLIB/MAYB3

test3()


(12) 0
Type: NonNegativeInteger
Time: 0.87 (EV) + 0.01 (OT) = 0.88 sec
(13) ->

This seems to show that testing 'failed?' in 'Maybe(R)' at 4.26 sec is
just a little slower than testing 'case "failed"' in
'Union(R,"failed")' at 3.91 sec.

For comparison I have included my reference implementation of
'Maybe(R)' using 'Rep:=List R' that I sent in an earlier email. In the
interpreter it seems to be intermediate between your Maybe and Union
but when compiled it seems faster than both. Of course using 'List R'
as a representation is not as space efficient as using the domain R
itself but it does have the advantage of having semantics consistent
with Haskell functor.

Bill Page

[oldk1331]

To Ralf: yes, the failed()$Maybe is like NULL from C,
a unique global special value to indicate failure.
We make that clear in documentation, then there's no
problem. After all, there's currently no usage of
Union("failed", Union("failed", X)) in the code, and
there's only one Rep use Union("failed", X), PatternMatchResult.

> BTW, if X1 := Union(X,"failed") and X2 := Union(X1,"failed"), where in
> current FriCAS is it specified that failed$X1 is different from failed$X2?

Well, currently there's no '=' for Union, and you can't compare
different types. And if you cast failed$X1 into X2, it's same as
failed$X2, just like the current Maybe.

[oldk1331]

To Bill:

1. Benchmarking in interpreter is meaningless, I'm sure
you noticed that you can do 10^6 calls in interpreter in 4s
while do 2*10^8 calls in 0.4s in compiler.

2. The FriCAS you are using should be built from my branch,
to have the inline patch, so that functions from Maybe can be inlined.

3. I didn't include array generation code in test function,
(although it didn't matter much in this case, just my habit)
so the first call from the benchmark package will generate the
array so it should not be timed. I also use 'qelt' to avoid
checking index.

4. I use "failed2?" to represent the "generic" Maybe case:

Qfailed ==> _*MAYBEFAIL_*$Lisp
Qfailed2 := GENSYM()$Lisp pretend %
failed? x == EQ(x, Qfailed)$Lisp
failed2? x == EQ(x, Qfailed2)$Lisp

--- Maybe benchmark package
)abbrev package TESTM TestMaybe
TestMaybe() : Exp == Imp where
Exp == with
f1 : Integer -> Integer
f2 : Integer -> Integer
f3 : Integer -> Integer
Imp == add
NNI ==> NonNegativeInteger
import from Vector NNI
v1 : Vector Maybe NNI := new(10^6, failed())
v2 : Vector Union(NNI, "failed") := new(10^6, "failed")

f1 x ==
v := v1
for j in 1..x repeat
for i in 1..10^6 repeat
failed? qelt(v, i)
x

f2 x ==
v := v1
for j in 1..x repeat
for i in 1..10^6 repeat
failed2? qelt(v, i)
x

f3 x ==
v := v2
for j in 1..x repeat
for i in 1..10^6 repeat
qelt(v, i) case "failed"
x

----- benchmark result
-- compile maybe to make "failed2?" available
(1) -> )co maybe
(1) -> )co bench-maybe
(1) -> )time on
(1) -> f1 1; -- to init the array
(2) -> f1 200;
Time: 0.39 (EV) = 0.39 sec
(3) -> f2 200;
Time: 0.00 (IN) + 1.22 (EV) + 0.00 (OT) = 1.23 sec
(4) -> f3 200;
Time: 0.40 (EV) = 0.40 sec

[Bill Page]

On 5 October 2017 at 20:34, oldk1331 <oldk...@gmail.com> wrote:
> To Bill:
>
> 1. Benchmarking in interpreter is meaningless, I'm sure
> you noticed that you can do 10^6 calls in interpreter in 4s
> while do 2*10^8 calls in 0.4s in compiler.
>

Of course, but not completely meaningless to someone using the interpreter.

> 2. The FriCAS you are using should be built from my branch,
> to have the inline patch, so that functions from Maybe can be
> inlined.
>

OK

> 3. I didn't include array generation code in test function,
> (although it didn't matter much in this case, just my habit)
> so the first call from the benchmark package will generate the
> array so it should not be timed. I also use 'qelt' to avoid
> checking index.
>

OK

> 4. I use "failed2?" to represent the "generic" Maybe case:

> ...

> ----- benchmark result
> -- compile maybe to make "failed2?" available
> (1) -> )co maybe
> (1) -> )co bench-maybe
> (1) -> )time on
> (1) -> f1 1; -- to init the array
> (2) -> f1 200;
> Time: 0.39 (EV) = 0.39 sec
> (3) -> f2 200;
> Time: 0.00 (IN) + 1.22 (EV) + 0.00 (OT) = 1.23 sec
> (4) -> f3 200;
> Time: 0.40 (EV) = 0.40 sec
>

Thank you very much. I reproduced the results above.

(1) -> )co fricas-oldk/src/algebra/maybe.spad

Compiling FriCAS source code from file

/home/wspage/fricas-oldk/src/algebra/maybe.spad using old system
compiler.
...
(1) -> )co maybe-bench-oldk

Compiling FriCAS source code from file

/home/wspage/maybe-bench-oldk.spad using old system compiler.
...

(1) -> )time on

(1) -> f1 1

(1) 1
Type: PositiveInteger
Time: 0.01 (EV) + 0.06 (OT) = 0.07 sec
(2) -> f1 200

(2) 200
Type: PositiveInteger
Time: 0.56 (EV) = 0.56 sec
(3) -> f2 200

(3) 200
Type: PositiveInteger
Time: 1.30 (EV) = 1.30 sec
(4) -> f3 200

(4) 200
Type: PositiveInteger
Time: 0.58 (EV) = 0.58 sec


I also repeated this same benchmark using my reference version of
Maybe. I see that the inlining also benefits the List R representation
so it remains a little faster than all of the above.

--- Maybe benchmark (reference implementation)
)abbrev package TESTM4 TestMaybe4
TestMaybe4() : Exp == Imp where
Exp == with
f4 : Integer -> Integer

Imp == add
NNI ==> NonNegativeInteger
import from Vector NNI

v4 : Vector Maybe NNI := new(10^6, empty())

f4 x ==
v := v4

for j in 1..x repeat
for i in 1..10^6 repeat

empty? qelt(v, i)
x
--

(1) -> )co maybe

Compiling FriCAS source code from file /home/wspage/maybe.spad using
old system compiler.
...

(1) -> )co maybe-bench4

Compiling FriCAS source code from file

/home/wspage/maybe-bench4.spad using old system compiler
....

(1) -> )time on
(1) -> f4 1

(1) 1
Type: PositiveInteger
Time: 0.00 (EV) + 0.04 (OT) = 0.04 sec
(2) -> f4 200

(2) 200
Type: PositiveInteger
Time: 0.48 (EV) = 0.48 sec

Bill Page.

[Martin Baker]

On 01/10/17 04:49, oldk1331 wrote:
> Again, I think this is a small problem, because
> 1. there's no point of using Maybe(Maybe(XXX)).

I have not followed this thread closely so apologies if my thoughts here
are off track.

I get the impression that you now agree that monads are not currently
practical in Fricas? However I still have hopes that, in the future, the
type system in Fricas may be enhanced to allow monads (am I wrong to
hold out hopes for this?). If this might be possible in the future then
I think maybe should be implemented in such a way that it could be made
an instance of monad to avoid re-working the library code a second time.

Also the terminology is well known from Haskell (where maybe is an
instance of monad) so its best not to diverge from that unless necessary
for a genuine mathematical reason.

I believe that monads are an (endo) functor with two natural
transformations:

M M X -> M X
X -> M X

In the maybe instance:

Maybe Maybe X -> Maybe X
X -> Maybe X

So I think Maybe Maybe X is a fundamental mathematical requirement.
This seems to be about how Maybes are chained which is the practical
purpose. So when chaining this things you could write:

Some partial function
if "failed" then handle error
next partial function
if "failed" then handle error
next partial function
if "failed" then handle error
...

This seems very messy with lots of repetitive code. What I would like to
do is this:

Some partial function
next partial function
next partial function
if "failed" then handle error

I'm not sure about the practicalities but perhaps to chain something
like subtractIfCan would require a signature like:

(Maybe X,Maybe X) -> Maybe X
rather than:
(X,X) -> Maybe X

but I have not really thought this through. Does anyone know how Maybe
is used in Haskell?

For me the most important thing is to optimise for simple and readable
code rather than optimising for performance. Perhaps if Fricas were
simplified it would be easier to move to a better type system. In fact I
have issues with all this diminishing returns performance optimisation.
If things could be made simpler perhaps Fricas could be built on top of
other languages than Lisp. I thought Krystian s project might move
things in that direction?

The way computer hardware is evolving with more core it seems to me
that, if you really want to optimise for speed, then multithreaded code
is the real future. So we need to move away from Lisp rather than
optimise around what Lisp happens to do fast now.

Martin B.

[Bill Page]

On 6 October 2017 at 11:40, Martin Baker <ax8...@martinb.com> wrote:
> On 01/10/17 04:49, oldk1331 wrote:
>>
>> Again, I think this is a small problem, because
>> 1. there's no point of using Maybe(Maybe(XXX)).
>
> I have not followed this thread closely so apologies if my thoughts here are
> off track.
>

Not at all. Thanks for contributing.

> I get the impression that you now agree that monads are not currently
> practical in Fricas? However I still have hopes that, in the future, the
> type system in Fricas may be enhanced to allow monads (am I wrong
> to hold out hopes for this?).

I think you are not wrong to continue to hope. :)

> If this might be possible in the future then I think maybe should be
> implemented in such a way that it could be made an instance
> of monad to avoid re-working the library code a second time.
>

+1

> Also the terminology is well known from Haskell (where maybe is an
> instance of monad) so its best not to diverge from that unless necessary
> for a genuine mathematical reason.
>
> I believe that monads are an (endo) functor with two natural
> transformations:
>
> M M X -> M X
> X -> M X
>
> In the maybe instance:
>
> Maybe Maybe X -> Maybe X
> X -> Maybe X
>
> So I think Maybe Maybe X is a fundamental mathematical requirement.

+1

> This seems to be about how Maybes are chained which is the practical
> purpose. So when chaining this things you could write:
>
> Some partial function
> if "failed" then handle error
> next partial function
> if "failed" then handle error
> next partial function
> if "failed" then handle error
> ...
>
> This seems very messy with lots of repetitive code. What I would like to do
> is this:
>
> Some partial function
> next partial function
> next partial function
> if "failed" then handle error
>

Do you mean something like this:

failed? f(g(h(x))

where f, g and h are "partial functions" with signatures like e.g.
'Integer -> Maybe Integer'

map(f,map(g,h(x)))

would return a value of type 'Maybe Maybe Maybe Integer' and the
natural transformation you mention can reduce that to a single 'Maybe
Integer' with a final testable result. I think oldk's current proposed
specification for 'Maybe' with a single global representation of
'failed' would make testing the final result easy but the resulting
type is still awkward, requiring 3 'unwrap/retract' calls to return an
Integer value. And this proposal would making testing for intermediate
failures impossible.

> I'm not sure about the practicalities but perhaps to chain something like
> subtractIfCan would require a signature like:
>
> (Maybe X,Maybe X) -> Maybe X
> rather than:
> (X,X) -> Maybe X
>
> but I have not really thought this through. Does anyone know how Maybe is
> used in Haskell?
>

This is not a problem using the 3 argument form of 'map' in Maybe.
(See my "reference version" of 'Maybe(R)' using 'List(R)' as a
representation.)

> For me the most important thing is to optimise for simple and readable code
> rather than optimising for performance. Perhaps if Fricas were simplified it
> would be easier to move to a better type system. In fact I have issues with
> all this diminishing returns performance optimisation. If things could be
> made simpler perhaps Fricas could be built on top of other languages than
> Lisp. I thought Krystian s project might move things in that direction?
>

+1

> The way computer hardware is evolving with more core it seems to me that,
> if you really want to optimise for speed, then multithreaded code is the real
> future. So we need to move away from Lisp rather than optimise around what
> Lisp happens to do fast now.
>

I agree. I think it is a good idea to try to avoid adding more Lisp
dependencies to the FriCAS library. But we can still depend on code
generation in the SPAD compiler and even Lisp to do whatever
optimizations are possible at those levels. Some day there may even
will be a SPAD compiler that generates LLVM code instead of Lisp. But
in any case, the choice of representation can make a big difference
depending on just what optimizations are available. For example the
'List(R)' representation can make testing for failed very fast (using
oldk's inlining enhancements) but at the cost of using a little more
space and a bit of time for unwrapping non-failed values. At this
point in the discussion I am again leaning toward this alternative.

Bill Page.

[oldk1331]

On Fri, Oct 6, 2017 at 11:40 PM, Martin Baker <ax8...@martinb.com> wrote:
>
> I get the impression that you now agree that monads are not currently
> practical in Fricas? However I still have hopes that, in the future, the
> type system in Fricas may be enhanced to allow monads (am I wrong to hold
> out hopes for this?). If this might be possible in the future then I think
> maybe should be implemented in such a way that it could be made an instance
> of monad to avoid re-working the library code a second time.

Monad is practical in FriCAS. But just like this time, we couldn't agree
on a lot of things. So instead of introducing Monad first, Maybe later;
I think introducing Maybe first, then add Monad later will be easier.

> Also the terminology is well known from Haskell (where maybe is an instance
> of monad) so its best not to diverge from that unless necessary for a
> genuine mathematical reason.

In previous discussion on Monad, we couldn't agree on the name
'Functor', because we already use that for Domain Constructor.
I agree with you that we should borrow terminology from Haskell
instead of introducing new one.

> I believe that monads are an (endo) functor with two natural
> transformations:
>
> M M X -> M X
> X -> M X
>
> In the maybe instance:
>
> Maybe Maybe X -> Maybe X
> X -> Maybe X

That's another difficult for Monad in previous discussion.
In Category Monad, you can't express signature like "Maybe Maybe X",
where % stands for Maybe X.

There's another set of natural transformations for Monad:

return : X -> Maybe X
>>= : (Maybe X, X -> Maybe X) -> Maybe X

> I'm not sure about the practicalities but perhaps to chain something like
> subtractIfCan would require a signature like:
>
> (Maybe X,Maybe X) -> Maybe X
> rather than:
> (X,X) -> Maybe X
>
> but I have not really thought this through. Does anyone know how Maybe is
> used in Haskell?

It's the >>= I mentioned above. It can chain single argument
functions together.

f : X -> Maybe X
g : X -> Maybe X

a >>= f >>= g

> For me the most important thing is to optimise for simple and readable code
> rather than optimising for performance. Perhaps if Fricas were simplified it
> would be easier to move to a better type system. In fact I have issues with
> all this diminishing returns performance optimisation. If things could be
> made simpler perhaps Fricas could be built on top of other languages than
> Lisp. I thought Krystian s project might move things in that direction?

Waldek has this plan that the compiler should be written in Spad,
so targeting other languages is a matter of new code generator and runtime.
That is a far far goal though.

> The way computer hardware is evolving with more core it seems to me that, if
> you really want to optimise for speed, then multithreaded code is the real
> future. So we need to move away from Lisp rather than optimise around what
> Lisp happens to do fast now.
>
> Martin B.

Yes. Common Lisp can do parallel computing but it's not standardized.
I think provide a parallel version "map" solves 50% problems.

[Martin Baker]

On 07/10/17 00:59, oldk1331 wrote:
> Monad is practical in FriCAS. But just like this time, we couldn't agree
> on a lot of things. So instead of introducing Monad first, Maybe later;
> I think introducing Maybe first, then add Monad later will be easier.

But if you cant agree the form of monad how can you be sure that any
maybe code you introduce will be compatible with it? It seems to me
that, to avoid reworking the library code multiple times, it would be
better to have an overall plan first? If you can't agree that perhaps it
would be better to leave the library code as it is?

> There's another set of natural transformations for Monad:
>
> return : X -> Maybe X
>>> = : (Maybe X, X -> Maybe X) -> Maybe X

Yes, I get the impression that there are two forms of monad:
1) The mathematical form.
2) The form used in Haskell to chain impure code.

I seem to remember that Haskell supports both, but the second version is
the main form, used in the prelude. Perhaps FriCAS should also support
both forms but since FriCAS is all about mathematics then it should
differ in this respect and the mathematical form should be the main form.

>> For me the most important thing is to optimise for simple and
readable code
>> rather than optimising for performance. Perhaps if Fricas were
simplified it
>> would be easier to move to a better type system. In fact I have
issues with
>> all this diminishing returns performance optimisation. If things
could be
>> made simpler perhaps Fricas could be built on top of other languages
than
>> Lisp. I thought Krystian s project might move things in that direction?
>
> Waldek has this plan that the compiler should be written in Spad,
> so targeting other languages is a matter of new code generator and
runtime.
> That is a far far goal though.

Is it?

I did some experiments to compile the interpreter boot code
(src/interp/*.boot) using a more conventional compiler:
https://github.com/martinbaker/fricas2aldor
I guess Waldek would just modify the existing compilers? but I find them
far too messy to work with.

I managed to compile this boot code to an Abstract Syntax Tree (AST) I
then wrote a code generator to write AST back to boot code. This code
was different from the original (because the AST does not store format
information) but when I compiled to Lisp the code generated was
identical - all lines (except those starting with ';') were identical.

So I am sure my AST contains all the information from the boot files.

Its then not difficult to generate SPAD or Aldor or any other language
from this AST. But the problems are:

1) how to handle global variables, especially dynamic variables. I think
each function would have to have an additional parameter to pass around
the runtime values of these dynamic variables.
2) The boot 'where' keword seems to hold inner fuctions and variables.
How should inner functions be converted to SPAD? SPAD has lambdas but
can SPAD lambda capture variables (closures)?
3) The native Lisp code would have to be translated by hand, to handle
input/output to console, files and database (which would be different
for each language).

Perhaps another option would be to just translate boot to SPAD manually
but that's hard because Boot/Lisp passes everything around in global
variables whereas well written SPAD should encapsulate information in
domains. This means you cant just translate one function at a time and
check if it works before going on to the next.

> Yes. Common Lisp can do parallel computing but it's not standardized.
> I think provide a parallel version "map" solves 50% problems.

I get the impression that Waldek will not make any changes to library
code that is not supported by all Lisps? Is that correct? I get the
impression there is a lot of natural parallelism in mathematical code,
for instance: vectors, would 'map' make use of all of that?

Martin B

[oldk1331]

On Sat, Oct 7, 2017 at 4:53 PM, Martin Baker <ax8...@martinb.com> wrote:
> On 07/10/17 00:59, oldk1331 wrote:
>> Monad is practical in FriCAS. But just like this time, we couldn't agree
>> on a lot of things. So instead of introducing Monad first, Maybe later;
>> I think introducing Maybe first, then add Monad later will be easier.
>
> But if you cant agree the form of monad how can you be sure that any maybe
> code you introduce will be compatible with it? It seems to me that, to avoid
> reworking the library code multiple times, it would be better to have an
> overall plan first? If you can't agree that perhaps it would be better to
> leave the library code as it is?

My opinion is to do one step at a time. The Maybe change and Monad
change doesn't conflict each other and can be done separately.
And as Linus said, "Talk is cheap, show me the code." It's hard to
get agreement on talk, so it's important to commit code and see how
it goes. I think the overall plan is agreed by everyone, just the details
to be working on.

>> There's another set of natural transformations for Monad:
>>
>> return : X -> Maybe X
>>>> = : (Maybe X, X -> Maybe X) -> Maybe X
>
> Yes, I get the impression that there are two forms of monad:
> 1) The mathematical form.
> 2) The form used in Haskell to chain impure code.
>
> I seem to remember that Haskell supports both, but the second version is the
> main form, used in the prelude. Perhaps FriCAS should also support both
> forms but since FriCAS is all about mathematics then it should differ in
> this respect and the mathematical form should be the main form.

The first form needs changes to compiler, that will be difficult.

>> Waldek has this plan that the compiler should be written in Spad,
>> so targeting other languages is a matter of new code generator and
>> runtime.
>> That is a far far goal though.
>
> Is it?
>
> I did some experiments to compile the interpreter boot code
> (src/interp/*.boot) using a more conventional compiler:
> https://github.com/martinbaker/fricas2aldor
> I guess Waldek would just modify the existing compilers? but I find them far
> too messy to work with.

Your project is very interesting. But how do you generate static
type language from a dynamic type language?

My thoughts on this matter:

1. clean up src/interp. Eliminate special/dynamic variables.
Make the functions more modular and add necessary documentation.

2. write bindings of commonly used data structure into Spad Domain.
So that we can inspect them in REPL and understand it better,
and write new compiler code in Spad.

3. It is possible to replace pieces of Boot code by Spad code, see
SPADCALL in i-output.boot. I think it's possible to test and replace
Boot code by Spad code gradually. (And it will require a running
FriCAS to do the bootstrap.)

> Its then not difficult to generate SPAD or Aldor or any other language from
> this AST. But the problems are:
>
> 1) how to handle global variables, especially dynamic variables. I think
> each function would have to have an additional parameter to pass around the
> runtime values of these dynamic variables.

I think dynamic variables should be eliminated by hand in Boot files.

> 2) The boot 'where' keword seems to hold inner fuctions and variables. How
> should inner functions be converted to SPAD? SPAD has lambdas but can SPAD
> lambda capture variables (closures)?

SPAD lambda isn't closure. That's another thing needs to be fixed in compiler.

> 3) The native Lisp code would have to be translated by hand, to handle
> input/output to console, files and database (which would be different for
> each language).

That's the runtime, it needs a clear specification and clean up.

> Perhaps another option would be to just translate boot to SPAD manually but
> that's hard because Boot/Lisp passes everything around in global variables
> whereas well written SPAD should encapsulate information in domains. This
> means you cant just translate one function at a time and check if it works
> before going on to the next.

Like I said, it's possible after we get rid of special variables.

>> Yes. Common Lisp can do parallel computing but it's not standardized.
>> I think provide a parallel version "map" solves 50% problems.
>
> I get the impression that Waldek will not make any changes to library code
> that is not supported by all Lisps? Is that correct? I get the impression

I think he is open to that. He wrote the GMP bindings for SBCL and CCL.

> there is a lot of natural parallelism in mathematical code, for instance:
> vectors, would 'map' make use of all of that?
>
> Martin B

What I said is, one can manually use parallel map for hotspot found by
profiler, not automatically. A deeper integration of parallelism into
code base will require more work.

[Bill Page]

On 6 October 2017 at 19:59, oldk1331 <oldk...@gmail.com> wrote:
>
> Monad is practical in FriCAS. But just like this time, we couldn't
> agree on a lot of things. So instead of introducing Monad first, Maybe
> later; I think introducing Maybe first, then add Monad later will be
> easier.
>

For me FriCAS/Axiom is first and foremost about mathematics and
mathematics does not require consensus, only rigor, so discussion is
useful in order to consider broader issues but it is not necessary to
agree in order to proceed. In the end the utility of a particular
construction will determine whether or not it is widely adopted.
Unfortunately our community is very small so this process can take a
long time.

> On Fri, Oct 6, 2017 at 11:40 PM, Martin Baker <ax8...@martinb.com> wrote:

>> Also the terminology is well known from Haskell (where maybe is
>> an instance of monad) so its best not to diverge from that unless
>> necessary for a genuine mathematical reason.
>
> In previous discussion on Monad, we couldn't agree on the name
> 'Functor', because we already use that for Domain Constructor.
> I agree with you that we should borrow terminology from Haskell
> instead of introducing new one.
>

It seems to me that in FriCAS, methodologies from computer science are
only a means to the end of implementing more mathematically-oriented
functionality. So I think mathematical notions from category theory
actually trump specific implementations such as represented by
Haskell. However Haskell does represent a significant advance as a
semantically rigorous programming language and can certainly serve as
a good example for FriCAS.

>> I believe that monads are an (endo) functor with two natural
>> transformations:
>>
>> M M X -> M X
>> X -> M X
>>
>> In the maybe instance:
>>
>> Maybe Maybe X -> Maybe X
>> X -> Maybe X
>
> That's another difficult for Monad in previous discussion.
> In Category Monad, you can't express signature like "Maybe Maybe X",
> where % stands for Maybe X.
>
> There's another set of natural transformations for Monad:
>
> return : X -> Maybe X
>>>= : (Maybe X, X -> Maybe X) -> Maybe X
>

The term "natural transformation" has a very specific meaning in
category theory. See for example "Monads Made Difficult" by Stephen
Diehl

http://www.stephendiehl.com/posts/monads.html

I do not see how you can treat "return" and "bind" (>>=) as natural
transformations but they can be defined in terms of the 'eta' and 'mu'
natural transformations together with 'fmap' from Functor.

>> I'm not sure about the practicalities but perhaps to chain something like
>> subtractIfCan would require a signature like:
>>
>> (Maybe X,Maybe X) -> Maybe X
>> rather than:
>> (X,X) -> Maybe X
>>
>> but I have not really thought this through. Does anyone know how Maybe is
>> used in Haskell?
>
> It's the >>= I mentioned above. It can chain single argument
> functions together.
>
> f : X -> Maybe X
> g : X -> Maybe X
>
> a >>= f >>= g
>

See the 'bind' implementation for 'Maybe' in the attached file.

(1) -> )co maybe
Compiling FriCAS source code from file /home/wspage/maybe.spad using
old system compiler.

MAYBE abbreviates domain Maybe
------------------------------------------------------------------------

Maybe is now explicitly exposed in frame frame1
Maybe will be automatically loaded when needed from
/home/wspage/MAYBE.NRLIB/MAYBE

MAYBE2 abbreviates package MaybeFunctions2
------------------------------------------------------------------------
MaybeFunctions2 is now explicitly exposed in frame frame1
MaybeFunctions2 will be automatically loaded when needed from
/home/wspage/MAYBE2.NRLIB/MAYBE2

MAYBE1 abbreviates package MaybeFunctions1
------------------------------------------------------------------------
MaybeFunctions1 is now explicitly exposed in frame frame1
MaybeFunctions1 will be automatically loaded when needed from
/home/wspage/MAYBE1.NRLIB/MAYBE1

(1) -> minus1(x:NNI):Maybe NNI == if x>0 then return x-1 else return
empty()$Maybe(NNI)
Function declaration minus1 : NonNegativeInteger -> Maybe(
NonNegativeInteger) has been added to workspace.

Type: Void
Time: 0 sec

(2) -> M1:Maybe NNI := 1

(2) [1]
Type: Maybe(NonNegativeInteger)
Time: 0 sec
(3) -> M0:=bind(M1,minus1)
Compiling function minus1 with type NonNegativeInteger -> Maybe(
NonNegativeInteger)

(3) [0]
Type: Maybe(NonNegativeInteger)
Time: 0.00 (IN) + 0.04 (OT) = 0.04 sec
(4) -> bind(M0,minus1)

(4) []
Type: Maybe(NonNegativeInteger)
Time: 0 sec
(5) -> M:Maybe NNI := empty()

(5) []
Type: Maybe(NonNegativeInteger)
Time: 0 sec
(6) -> bind(M,minus1)

(6) []
Type: Maybe(NonNegativeInteger)
Time: 0 sec

Note that I have used the notation [ ] for "failed" and that R-values
in 'Maybe R' are also shown inside brackets.

Bill Page

[Martin Baker]

On 07/10/17 10:30, oldk1331 wrote:
> Your project is very interesting. But how do you generate static
> type language from a dynamic type language?

I mapped functions in boot to functions in SPAD. For convenience I just
put them in packages one for each boot file.

Variables in boot can map to variables which are instances of
SExpression. This instance of SExpression can have have common lisp
functions like '+' defined. At runtime this function would add if its a
number and fail if its not. So its checking the type dynamically at
runtime - just like boot/lisp.

> My thoughts on this matter:
>
> 1. clean up src/interp. Eliminate special/dynamic variables.
> Make the functions more modular

As I said before, I think it would be hard to change one function at a
time because all these functions are linked by lots of global variables.

I suspect it would only be possible to untangle all that mess if you
have a very deep understanding of the interpreter and of boot. Since I
would like to remove boot code I would rather not spend a lot of time
learning about it.

One thing that I can easily do, since I have an AST, is generate tables
showing which functions use which variables and another showing which
variables are used in which functions. But I think it would take more
knowledge than I have to untangle them. I might even be able to infer
which variables only get assigned to one type (int,float,string..) so
that they could be assigned those types in SPAD. However many boot
variables could be polymorphic or complicated list structures.

> and add necessary documentation.

Good luck getting Waldek to agree to that!

Martin B

[oldk1331]

About the "Maybe Maybe X" problem:

Since Waldek gives the idea of using GENSYM() to mark failure,
I want to hear his opinion.

One of my original motives to introduce Maybe is performance,
the other motive is better abstraction. Seems we can't have both.
If I have to choose between them, I'll choose better abstraction.

If we choose "Rep := List R", then the performance should be
same as Union(X, "failed").

I did a simple benchmark on subtractIfCan$NNI, the GENSYM()
approach can be 12% faster (or 20% faster if a GC happens).
That may speed up "groebner" by 4%. I guess if such optimization
is really needed, it can be done case by case.

[Bill Page]

On 7 October 2017 at 21:29, oldk1331 <oldk...@gmail.com> wrote:
> About the "Maybe Maybe X" problem:
>
> Since Waldek gives the idea of using GENSYM() to mark failure,
> I want to hear his opinion.
>
> One of my original motives to introduce Maybe is performance,
> the other motive is better abstraction. Seems we can't have both.

I think we can have both. Your inline optimization is all that is needed.

> If I have to choose between them, I'll choose better abstraction.
>
> If we choose "Rep := List R", then the performance should be
> same as Union(X, "failed").
>

With the current SPAD compiler and your most recent inline
optimizations that does not seem to be true. My benchmark below shows
that "Rep := List R" has almost the same performance for testing
failed and retracting/upwrapping a value as using global GENSYM.
Testing empty?/failed? is actually a little bit faster.
"Union(R,"failed")" on the other hand does seem to take about 80%
longer to unwrap a value.

> I did a simple benchmark on subtractIfCan$NNI, the GENSYM()
> approach can be 12% faster (or 20% faster if a GC happens).
> That may speed up "groebner" by 4%. I guess if such optimization
> is really needed, it can be done case by case.
>

I recommend that you try your simple benchmark again using "Rep :=
List R". You should get the same performance as with global GENSYM
(notwithstanding a possible increase in GC).

--

wspage@strix ~ $ fricas -nox

(1) -> )r maybe-bench-all
)co fricas-oldk/src/algebra/maybe.spad

Compiling FriCAS source code from file

/home/wspage/fricas-oldk/src/algebra/maybe.spad using old system

compiler.
MAYBE abbreviates domain Maybe
------------------------------------------------------------------------
Maybe is now explicitly exposed in frame frame1
Maybe will be automatically loaded when needed from
/home/wspage/MAYBE.NRLIB/MAYBE

)co maybe-bench-oldk

Compiling FriCAS source code from file

/home/wspage/maybe-bench-oldk.spad using old system compiler.

TESTM abbreviates package TestMaybe
------------------------------------------------------------------------
TestMaybe is now explicitly exposed in frame frame1
TestMaybe will be automatically loaded when needed from
/home/wspage/TESTM.NRLIB/TESTM

)set message type off

f1 1;


)time on

-- using Maybe(R) with Rep:=R and global GENSYM() to mark failure
-- testing failed?
f1 200;


Time: 0.47 (EV) = 0.47 sec
-- unwarp
g1 200;

Time: 0.39 (EV) = 0.39 sec

--
-- using Maybe(R) with Rep:=R and local GENSYM() to mark failure
-- testing failed2?
f2 200;


Time: 1.20 (EV) = 1.20 sec
--
-- using Union(R,"failed")
-- testing case "failed"
f3 200;


Time: 0.44 (EV) = 0.44 sec
-- coerce to R
g3 200;


Time: 0.00 (IN) + 0.70 (EV) + 0.00 (OT) = 0.71 sec
)time off

)co maybe.spad

Compiling FriCAS source code from file /home/wspage/maybe.spad using
old system compiler.
MAYBE abbreviates domain Maybe
------------------------------------------------------------------------

Maybe is already explicitly exposed in frame frame1

Maybe will be automatically loaded when needed from
/home/wspage/MAYBE.NRLIB/MAYBE

)co maybe-bench4

Compiling FriCAS source code from file

/home/wspage/maybe-bench4.spad using old system compiler.
TESTM4 abbreviates package TestMaybe4
------------------------------------------------------------------------
TestMaybe4 is now explicitly exposed in frame frame1
TestMaybe4 will be automatically loaded when needed from
/home/wspage/TESTM4.NRLIB/TESTM4

f4 1;


)time on

-- using Maybe(R) with Rep:=List R
-- testing empty?
f4 200;


Time: 0.38 (EV) = 0.38 sec
-- retract
g4 200;


Time: 0.43 (EV) = 0.43 sec


-- file: maybe-bench-all.input
)co fricas-oldk/src/algebra/maybe.spad
)co maybe-bench-oldk
)set message type off
f1 1;
)time on
-- using Maybe(R) with Rep:=R and global GENSYM() to mark failure
-- testing failed?
f1 200;
-- unwarp
g1 200;
--
-- using Maybe(R) with Rep:=R and local GENSYM() to mark failure
-- testing failed2?
f2 200;
--
-- using Union(R,"failed")
-- testing case "failed"
f3 200;
-- coerce to R
g3 200;
)time off
)co maybe.spad
)co maybe-bench4
f4 1;
)time on
-- using Maybe(R) with Rep:=List R
-- testing empty?
f4 200;
-- retract
g4 200;
--

-- file: maybe-bench-oldk.spad

--- Maybe benchmark package
)abbrev package TESTM TestMaybe

TestMaybe() : Exp == Imp where
Exp == with
f1 : Integer -> Integer
g1 : Integer -> Integer

f2 : Integer -> Integer
f3 : Integer -> Integer

g3 : Integer -> Integer

Imp == add
NNI ==> NonNegativeInteger
import from Vector NNI

v1 : Vector Maybe NNI := new(10^6, failed())
v2 : Vector Union(NNI, "failed") := new(10^6, "failed")

w1 : Vector Maybe NNI := [wrap i for i in 1..10^6]
w2 : Vector Union(NNI, "failed") := [i for i in 1..10^6]

f1 x ==
v := v1

for j in 1..x repeat
for i in 1..10^6 repeat

failed? qelt(v, i)
x

g1 x ==
w := w1

for j in 1..x repeat
for i in 1..10^6 repeat

unwrap! qelt(w, i)

x

f2 x ==
v := v1

for j in 1..x repeat
for i in 1..10^6 repeat

failed2? qelt(v, i)
x

f3 x ==
v := v2

for j in 1..x repeat
for i in 1..10^6 repeat

qelt(v, i) case "failed"
x

g3 x ==
w := w2

for j in 1..x repeat
for i in 1..10^6 repeat

qelt(w, i)::NNI
x
--

-- file: maybe-bench4.spad
--- Maybe benchmark package

)abbrev package TESTM4 TestMaybe4
TestMaybe4() : Exp == Imp where
Exp == with
f4 : Integer -> Integer

g4 : Integer -> Integer

Imp == add
NNI ==> NonNegativeInteger
import from Vector NNI

v4 : Vector Maybe NNI := new(10^6, empty())

w4 : Vector Maybe NNI := [coerce i for i in 1..10^6]

f4 x ==
v := v4
for j in 1..x repeat
for i in 1..10^6 repeat
empty? qelt(v, i)
x

g4 x ==
w := w4

for j in 1..x repeat
for i in 1..10^6 repeat

qretract qelt(w, i)
x
--

-- file: maybe.spad
)abbrev domain MAYBE Maybe
++ Description:
++ The type Maybe(R) represents either a value of type R, or absence/failure.
++ Using Maybe is a good way to deal with errors or exceptional cases without
++ resorting to drastic measures such as error. It replaces the usage of
++ Union(R, "failed").

Maybe(R : Type) : Exports == Implementation where
Exports == RetractableTo(R) with
construct : R -> %
coerce : List R -> %
empty : () -> %
++ empty() returns a value that indicates failure.
empty? : % -> Boolean
++ empty?(x) checks if x is empty().
retractable? : % -> Boolean
++ retractable?(x) checks if x is of type R.
qretract : % -> R
++ fast retract (no test for empty)
maybe : (%, R) -> R
++ maybe(x, default) returns x as type R if it's not empty(),
++ otherwise returns default.
maybe : (R -> R, %, R) -> R
++ maybe(f,x,default) returns f(unwrap x) or default if empty?(x)
if R has CoercibleTo OutputForm then CoercibleTo OutputForm
if R has BasicType then BasicType
if R has SetCategory then SetCategory

Implementation == add
Rep := List R
errMsg ==> "retract: the argument is empty()"

construct(x) == [x]
coerce(x) ==
if #x>1 then error "not singleton"
x
empty() == empty()$Rep
empty? x == empty?(x)$Rep
coerce(x:R):% == [x]
retractable? x == not empty?(x)
retractIfCan x == if empty?(x) then "failed" else first x
retract x == if empty?(x) then error errMsg else first x
qretract x == first x
maybe(x, default) == if empty?(x) then default else first x
maybe(f,x,default) == if empty?(x) then default else f(first x)

if R has CoercibleTo OutputForm then
coerce(x : %) : OutputForm == coerce(x)$Rep

if R has BasicType then
x = y == (x = y)$Rep

if R has SetCategory then
hashUpdate!(hs : HashState, x : %) == hashUpdate!(hs, x)$Rep
--

Bill Page

[Ralf Hemmecke]

On 10/08/2017 05:55 AM, Bill Page wrote:
> "Union(R,"failed")" on the other hand does seem to take about 80%
> longer to unwrap a value.

I'm not a compiler expert (and I don't actually like Union(X,"failed")
so much, but we can have Monad in FriCAS without changing the language.
We can have Maybe with a global failed().
We can have Maybe with GENSYM(). Since latter behaves (up to function
names) exactly as Union(X,"failed"), why wouldn't it make sense to
specialise the compiler so that Union(X,"failed") uses the
"Maybe+GENSYM" code that Qian wrote?

Ralf

[Bill Page]

On 8 October 2017 at 03:47, Ralf Hemmecke <ra...@hemmecke.org> wrote:
> On 10/08/2017 05:55 AM, Bill Page wrote:
>> "Union(R,"failed")" on the other hand does seem to take about 80%
>> longer to unwrap a value.
>
> I'm not a compiler expert (and I don't actually like Union(X,"failed")
> so much, but we can have Monad in FriCAS without changing the language.

Can you explain how we can define Monad in FriCAS without changing the language?

> We can have Maybe with a global failed().

But then Maybe would not be a Monad (at least in the since used in Haskell).

> We can have Maybe with GENSYM().

Do you mean Maybe with a local instance GENSYM?

> Since latter behaves (up to function
> names) exactly as Union(X,"failed"),

That is true only if the GENSYM is unique to each instance of Maybe.

> why wouldn't it make sense to
> specialise the compiler so that Union(X,"failed") uses the
> "Maybe+GENSYM" code that Qian wrote?
>

Maybe + local instance GENSYM has performance for failed values that
is similar to Union(X,"failed") since it is not possible to get rid of
the svref indirection that is necessary for variables in an instance
of a domain. The so-called singleton types like "failed" used in
Union(X,"failed") actually is a global value but the current
implementation of Union requires tags to distinguish values and
consulting these tags takes extra time (but this data structure does
properly represent nested Union in a manner consistent with Monad).

But what you suggest might be possible in principle provided one is
willing to compromise. In fact it has already been implicitly
considered in the earlier discussion between Waldek and oldk about the
fact the Lisp values have their own tags. That is what allows one to
store a GENSYM value in something the FriCAS is treating as an
Integer.

Because of Lisp's internal value tags one could define untagged Union
like the Union in the "C" language so that it reused the same space
for each possible value. For this to be type-safe one would have to
limit the possible domains in an untagged Union to the small number of
built-in FriCAS types that correspond directly to distinguishable Lisp
values, e.g. Integer, DoubleFloat, and singleton types ls such as
"failed". I think one might be able to extend this to Float since
Float is represented by a dotted pair. Unions like
Union(Integer,"failed") and Union("failed", Integer) would have to be
treated as identical types (they are not right now) and nested Union
would have to be flattened. This is essentially the same as the "big
problem" to which Waldek referred earlier in this thread. Still, with
suitable restrictions on how it is used such an untagged Union might
be useful for space and performance optimizations. Unfortunately
hoping that the SPAD compiler could make such optimizations
automatically is probably unrealistic.

In fact this might have been what the original Axiom designers had in
mind when introducing the first version of the Union type without
tags. The source code contains notes that suggest that it was the
intention of the developers to replace the "old" untagged version of
Union with the "new" tagged version and that this had been at least
partially accomplished. It may have been the recognition of the
limitations mentioned above that originally motivated the desire to
introduce the tagged Union construction.

I have just run a benchmark with oldk's optimizations that shows that
the performance of Union(X,"failed") is identical to Union(val:X,
failed:"failed") while the "Rep := List R" representation of Maybe(R)
where "failed" is represented by empty list (NIL) and non "failed"
values as a singleton list (cons), has performance the same or
slightly better (in the case of failed values) than Maybe with global
fGENSYM (at the cost of using about the same extra storage as the
Union representation, compared to no extra storage for Maybe with the
global or local GENSYM.

Bill Page.

[Ralf Hemmecke]

On 10/08/2017 07:40 PM, Bill Page wrote:
> On 8 October 2017 at 03:47, Ralf Hemmecke <ra...@hemmecke.org> wrote:
>> On 10/08/2017 05:55 AM, Bill Page wrote:
>>> "Union(R,"failed")" on the other hand does seem to take about 80%
>>> longer to unwrap a value.
>>
>> I'm not a compiler expert (and I don't actually like Union(X,"failed")
>> so much, but we can have Monad in FriCAS without changing the language.
>
> Can you explain how we can define Monad in FriCAS without changing the language?

Arrhhh. Sorry. I intended to write

I'm not a compiler expert (and I don't actually like Union(X,"failed")

so much), but we *cannot* have Monad in FriCAS without changing the
language.

>> We can have Maybe with a global failed().
>
> But then Maybe would not be a Monad (at least in the since used in Haskell).

Exactly. And that is why for this case I would be rather against the
name "Maybe". I'd rather opt for "Partial" as in Aldor even though
AldorLib implements Partial via Record and is thus more similar to
Union(X,"failed") or "Maybe with GENSYM()" (in terms of behaviour).

https://github.com/pippijn/aldor/blob/master/aldor/lib/aldor/src/base/sal_partial.as#L92

>> We can have Maybe with GENSYM().
>
> Do you mean Maybe with a local instance GENSYM?

Right. An implementation of Maybe where the failed@Maybe(Maybe(X)) is
not (lisp) equal to failed@Maybe(X). Waldek suggested distinguishable
failed values. So it is more like the Maybe as a type functor FX=1+X.
That equation would not hold for "Maybe with global failed()".

> I have just run a benchmark with oldk's optimizations that shows that
> the performance of Union(X,"failed") is identical to Union(val:X,
> failed:"failed") while the "Rep := List R" representation of Maybe(R)
> where "failed" is represented by empty list (NIL) and non "failed"
> values as a singleton list (cons), has performance the same or
> slightly better (in the case of failed values) than Maybe with global
> fGENSYM (at the cost of using about the same extra storage as the
> Union representation, compared to no extra storage for Maybe with the
> global or local GENSYM.

A more logical representation (which does not rely on the underlying
Lisp) would be similar to what Partial in Aldor has, see link above.

Rep == Record(val:T);

It doesn't suggest that there is ever more than one value. Therefore, I
suggested Rep == Reference(X) in an earlier mail.

Relying on lisp as the target language is not a good idea. I'd rather
like to be independent of such implementation details.

Ralf

[Bill Page]

On 8 October 2017 at 16:09, Ralf Hemmecke <ra...@hemmecke.org> wrote:
> ...

> Exactly. And that is why for this case I would be rather against the
> name "Maybe". I'd rather opt for "Partial" as in Aldor even though
> AldorLib implements Partial via Record and is thus more similar to
> Union(X,"failed") or "Maybe with GENSYM()" (in terms of behaviour).
>

"partial" as in "partial function" makes sense but this is an
attribute of the mapping, not of the target domain. So if I read
"Partial Integer" that does not make much sense to me. "Maybe
Integer" on the other hand says something about the domain Integer.

> https://github.com/pippijn/aldor/blob/master/aldor/lib/aldor/src/base/sal_partial.as#L92
>

This implementation seems very strange to me. If "Rep ==
Record(val:T)" then what does it mean that

failed:% == per nil

'nil' does not seem like a value of Rep. Can all Record types is Aldor
have nil as a value? And a Record with only one component seems like a
kind of pointless indirection unless we have some internal knowledge
of how Record is implemented and we think of this as a kind of hidden
pointer reference. What am I missing here?

> ...

>> I have just run a benchmark with oldk's optimizations that shows that
>> the performance of Union(X,"failed") is identical to Union(val:X,
>> failed:"failed") while the "Rep := List R" representation of Maybe(R)
>> where "failed" is represented by empty list (NIL) and non "failed"
>> values as a singleton list (cons), has performance the same or
>> slightly better (in the case of failed values) than Maybe with global
>> fGENSYM (at the cost of using about the same extra storage as the
>> Union representation, compared to no extra storage for Maybe with the
>> global or local GENSYM.
>
> A more logical representation (which does not rely on the underlying
> Lisp)

Nothing of the implementation of Maybe with "Rep := List R" depends on
the underlying Lisp. All that we need is a List domain and that is
provided by the FriCAS library (although granted the implementation of
List itself does depend on the underlying Lisp for reasons of
performance).

> would be similar to what Partial in Aldor has, see link above.
>
> Rep == Record(val:T);
>

Sorry, I didn't find it very logical.

> It doesn't suggest that there is ever more than one value. Therefore,
> I suggested Rep == Reference(X) in an earlier mail.

It is not important what the representation suggests. In the choice of
representation for any domain it is normal that we only use part of
the functionality that the underlying representation provides and then
build on that. Since we want Maybe to be a functor (in the sense of
Haskell) then using an underlying representation that is a functor
seems like a good idea.

It seems to me that Reference(X) introduces an extra unnecessary level
of indirection and still suffers from a logical inconsistency when the
value of Reference(X) does not in fact point to an actual X value.

>
> Relying on lisp as the target language is not a good idea. I'd rather
> like to be independent of such implementation details.
>

It seems reasonable to me to assume that any target language is likely
to provide at least some form of List as a primitive type. But in any
case we can at least assume that there will be a way to implement List
as a domain.

Bill Page.

[oldk1331]

On Mon, Oct 9, 2017 at 4:09 AM, Ralf Hemmecke <ra...@hemmecke.org> wrote:
>>> We can have Maybe with a global failed().
>>
>> But then Maybe would not be a Monad (at least in the since used in Haskell).
>
> Exactly. And that is why for this case I would be rather against the
> name "Maybe". I'd rather opt for "Partial" as in Aldor even though

Let "Partial" stands for the global GENSYM() solution and "Maybe"
stands for the "Rep := List R" solution.
Then we still need to pick a default: what should 'subtractIfCan' return?
We can't have both signatures because that will complicate type inference.
I propose to use "Maybe" as default and to use "Partial" in performance
critical code.

> A more logical representation (which does not rely on the underlying
> Lisp) would be similar to what Partial in Aldor has, see link above.
>
> Rep == Record(val:T);
>
> It doesn't suggest that there is ever more than one value. Therefore, I

Aldor uses "nil pretend %" for the "failed" value, I guess you don't like
the 'pretend'.

> suggested Rep == Reference(X) in an earlier mail.
>
> Relying on lisp as the target language is not a good idea. I'd rather
> like to be independent of such implementation details.
>
> Ralf

First, "Reference" is not inlined optimized. Second, Maybe is a low level
Domain, and I need optimization like CONSP$Lisp, QCAR$Lisp.

This thread is pretty long, I'll open a new one with Maybe built on

[Ralf Hemmecke]

On 10/09/2017 02:39 AM, oldk1331 wrote:
> Let "Partial" stands for the global GENSYM() solution and "Maybe"
> stands for the "Rep := List R" solution.
> Then we still need to pick a default: what should 'subtractIfCan' return?

In fact, I would choose the one that works faster and has minimal memory
usage. But actually, I tend to want a "canSubtract?" function.

As you mentioned earlier "canSubtract?" might in some cases lead to
recomputation whereas "subtractIfCan" might allocate memory that is not
needed if the computation fails. So what would be the best choice here?
Probably, to provide both? I think a test function is anyway a good
idea. There might be situation where it is only necessary to check if
subtraction is possible, but the actual value is not needed. (Of course,
I do not only speak for subtractIfCan, but also for similar cases.)

> We can't have both signatures because that will complicate type inference.
> I propose to use "Maybe" as default and to use "Partial" in performance
> critical code.

I can agree to that.

> Aldor uses "nil pretend %" for the "failed" value, I guess you don't like
> the 'pretend'.

OK, Bill and you got me with the "not so logical choice". But ...
my understanding is that the memory footprint for List and Record is a
bit different.

List(X): NIL or a pointer to a record r
where r holds a value of type X and a NIL pointer
Record(x: X): NIL or a pointer to a value of type X

So the List version stores an unnecessary NIL pointer together with a
heap allocation for a Record(x: X, next: Pointer).

This is the actual reason why Record(x: X) seems better to me. And I
don't care about the "pretend" in this case, because I consider such a
"Partial" domain as a very low-level domain that would have to be
changed with the runtime support of the language.

Ralf

PS: Oh, only now I've seen your new thread "Maybe preview 2".

[oldk1331]

On Mon, Oct 9, 2017 at 3:52 PM, Ralf Hemmecke <ra...@hemmecke.org> wrote:
> On 10/09/2017 02:39 AM, oldk1331 wrote:
>> Let "Partial" stands for the global GENSYM() solution and "Maybe"
>> stands for the "Rep := List R" solution.
>> Then we still need to pick a default: what should 'subtractIfCan' return?
>
> In fact, I would choose the one that works faster and has minimal memory
> usage. But actually, I tend to want a "canSubtract?" function.
>
> As you mentioned earlier "canSubtract?" might in some cases lead to
> recomputation whereas "subtractIfCan" might allocate memory that is not
> needed if the computation fails. So what would be the best choice here?
> Probably, to provide both? I think a test function is anyway a good
> idea. There might be situation where it is only necessary to check if
> subtraction is possible, but the actual value is not needed. (Of course,
> I do not only speak for subtractIfCan, but also for similar cases.)

It's probably better to offer optimized version in "hotspot code" found
by profiler, for example in GroebnerInternalPackage.

> List(X): NIL or a pointer to a record r
> where r holds a value of type X and a NIL pointer
> Record(x: X): NIL or a pointer to a value of type X
>
> So the List version stores an unnecessary NIL pointer together with a
> heap allocation for a Record(x: X, next: Pointer).

You are misleading here.

List with one element is CONS(X, NIL)
Record with one slot is CONS(X, NIL)

They are identical.

> This is the actual reason why Record(x: X) seems better to me. And I
> don't care about the "pretend" in this case, because I consider such a
> "Partial" domain as a very low-level domain that would have to be
> changed with the runtime support of the language.
>
> Ralf

BTW, what's your opinion on naming?

[Ralf Hemmecke]

On 10/09/2017 12:36 PM, oldk1331 wrote:
>> List(X): NIL or a pointer to a record r
>> where r holds a value of type X and a NIL pointer
>> Record(x: X): NIL or a pointer to a value of type X
>>
>> So the List version stores an unnecessary NIL pointer together with a
>> heap allocation for a Record(x: X, next: Pointer).
>
> You are misleading here.
>
> List with one element is CONS(X, NIL)
> Record with one slot is CONS(X, NIL)
>
> They are identical.

But that's only the case for Lisp, right? I still consider that a waste
of memory.

How would you map List(X) and Record(x: X) to C datastructures?

Ralf

[Bill Page]

On 8 October 2017 at 20:39, oldk1331 <oldk...@gmail.com> wrote:
> On Mon, Oct 9, 2017 at 4:09 AM, Ralf Hemmecke <ra...@hemmecke.org> wrote:
>>
>> Relying on lisp as the target language is not a good idea. I'd rather
>> like to be independent of such implementation details.
>>
>

> First, "Reference" is not inlined optimized. Second, Maybe is a low level
> Domain, and I need optimization like CONSP$Lisp, QCAR$Lisp.
>

My benchmarking shows the Lisp macros QCAR and CONSP are no 'faster'
than calling 'first' and 'not empty?' from the List domain. Perhaps
this is due to some internal optimizations in SPAD and/or SBCL? I
think it is best to avoid explicit Lisp dependencies if possible. Is
your experience different?

Bill Page.

[Waldek Hebisch]

Well, there is(or was) code in Spad compiler to handle "easy"
cases of Union-s in simpler, presumbaly more efficient way
(actually using Lisp tags). But this code was not used
(conditions were set so it was never used). AFAICS really
simple code gives incorrect semantics, and trying to give
correct semantics with simpler code for some cases means
that we need runtime checks that seem to cost more than
just using current code.

--
Waldek Hebisch

[Waldek Hebisch]

oldk1331 wrote:
>
> About the "Maybe Maybe X" problem:
>
> Since Waldek gives the idea of using GENSYM() to mark failure,
> I want to hear his opinion.

Well, I had hope that GENSYM() will be free from problems
with tags. Alas, as it turned out the problem (incompatiblity
of Spad and Lisp semantics) is still there...

--
Waldek Hebisch

[oldk1331]

On Mon, Oct 9, 2017 at 9:22 PM, Bill Page <bill...@newsynthesis.org> wrote:
> My benchmarking shows the Lisp macros QCAR and CONSP are no 'faster'
> than calling 'first' and 'not empty?' from the List domain. Perhaps
> this is due to some internal optimizations in SPAD and/or SBCL? I
> think it is best to avoid explicit Lisp dependencies if possible. Is
> your experience different?
>
> Bill Page.

I didn't do a benchmarking, but I know that "first" does an extra empty check,
and "not empty?" translates to (NULL (NULL x)) and can't be inlined.

The compiler should not be able to optimize them away, there should
be a performance difference in more complicated situation.

[oldk1331]

Since Lisp is dynamic typed, you don't have "sizeof", so you can't
have "struct" in stack but a pointer to heap. In C you can do zero-cost
abstraction, but not in Lisp.

[Bill Page]

The function 'first' in the List domain calls SPADfirst$Lisp which is
a rather clever Lisp macro

(defmacro |SPADfirst| (l)
(let ((tem (gensym)))
`(let ((,tem ,l)) (if ,tem (car ,tem) (first-error)))))

that seems to have no more measurable overhead than calling QCAR.
Perhaps someone with more Lisp experience than me can explain it?

I think probably that (NULL (NULL x)) is optimized by Lisp (at least by SBCL).

[oldk1331]

On Tue, Oct 10, 2017 at 10:30 AM, Bill Page <bill...@newsynthesis.org> wrote:
> The function 'first' in the List domain calls SPADfirst$Lisp which is
> a rather clever Lisp macro
>
> (defmacro |SPADfirst| (l)
> (let ((tem (gensym)))
> `(let ((,tem ,l)) (if ,tem (car ,tem) (first-error)))))
>
> that seems to have no more measurable overhead than calling QCAR.
> Perhaps someone with more Lisp experience than me can explain it?

Well, it's the difference between (if x (car x)) and (car x).

> I think probably that (NULL (NULL x)) is optimized by Lisp (at least by SBCL).

Yes, but at Spad level, (CONSP X) is inlined, while (NULL (NULL x)) is
not inlined,
which involves a ELT lookup and a function call.

BTW, your benchmarking might be misleading, because when you modify
a previously inlined function to not-inlined, then the previous inline
information
is still in the system. This should be considered a small annoying bug.
AKA if you modified a inline domain, you should compile FriCAS again
to do benchmark.

[Bill Page]

On 10 October 2017 at 03:03, oldk1331 <oldk...@gmail.com> wrote:
> On Tue, Oct 10, 2017 at 10:30 AM, Bill Page <bill...@newsynthesis.org> wrote:
>> The function 'first' in the List domain calls SPADfirst$Lisp which is
>> a rather clever Lisp macro
>>
>> (defmacro |SPADfirst| (l)
>> (let ((tem (gensym)))
>> `(let ((,tem ,l)) (if ,tem (car ,tem) (first-error)))))
>>
>> that seems to have no more measurable overhead than calling
>> QCAR. Perhaps someone with more Lisp experience than me
>> can explain it?
>
> Well, it's the difference between (if x (car x)) and (car x).
>

So calling (if x ... ) must have very low cost. If you don't like the
error message produced by SPADfirst it might be a good idea to define
an analogous macro for use in 'Maybe' and that way avoid the need for
the unsafe 'unwrap!' operator.

>> I think probably that (NULL (NULL x)) is optimized by Lisp
>> (at least by SBCL).
>
> Yes, but at Spad level, (CONSP X) is inlined, while
> (NULL (NULL x)) is not inlined, which involves a ELT lookup
> and a function call.
>

OK. I must not have measured what I thought I had measured. Why is
(NULL (NULL x)) not inlined? It looks like it should be easy.

> BTW, your benchmarking might be misleading, because when
> you modify a previously inlined function to not-inlined, then the
> previous inline information is still in the system. This should be
> considered a small annoying bug. AKA if you modified a inline
> domain, you should compile FriCAS again to do benchmark.
>

Thank you for the tip. That is confusing.

[oldk1331]

On Tue, Oct 10, 2017 at 8:05 PM, Bill Page <bill...@newsynthesis.org> wrote:
>>> I think probably that (NULL (NULL x)) is optimized by Lisp
>>> (at least by SBCL).
>>
>> Yes, but at Spad level, (CONSP X) is inlined, while
>> (NULL (NULL x)) is not inlined, which involves a ELT lookup
>> and a function call.
>>
>
> OK. I must not have measured what I thought I had measured. Why is
> (NULL (NULL x)) not inlined? It looks like it should be easy.

Probably because that is a nested call. The current Spad compiler
is weak at optimization anyway.

[Bill Page]

If we are willing to admit a Lisp dependency in 'Maybe' calling CONSP
isn't really needed. Since the 'Rep' is 'List' and true in Lisp (and
in SPAD) is anything that is not 'nil', the best definition of
'wrap?/retractable?' is just

retractable? x == x pretend Boolean

Then

if not retractable? m then error("too bad")

generates inline code like:

(COND ((NULL |m|) (|error| "too bad")))

[oldk1331]

> Since the 'Rep' is 'List' and true in Lisp (and
> in SPAD) is anything that is not 'nil'

No. Boolean in SPAD should be a 2-object category,
aka 'false' and 'true', represented by NIL and T.

> retractable? x == x pretend Boolean

This 'pretend' is much worse that CONSP.

Maybe is a low level domain, and it's one of the few "inline domains",
it's totally OK to have $Lisp calls.

> --
> 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 post to this group, send email to fricas...@googlegroups.com.
> Visit this group at https://groups.google.com/group/fricas-devel.
> For more options, visit https://groups.google.com/d/optout.
>

[Bill Page]

On 12 October 2017 at 22:02, oldk1331 <oldk...@gmail.com> wrote:
>> Since the 'Rep' is 'List' and true in Lisp (and
>> in SPAD) is anything that is not 'nil'
>
> No. Boolean in SPAD should be a 2-object category,
> aka 'false' and 'true', represented by NIL and T.
>

I do not understand 'Boolean' as a category. The 'Boolean' domain
satisfies the following categories: 'OrderedSet', 'Finite', 'Logic'.
Thinking of Boolean as a category in the mathematical sense seems
unnecessarily abstract.

There is no reason that the two values in Boolean need to be
represented internally by just two values. If that were the case then
it would be appropriate also for Boolean to satisfy the category
'Canonical'. There is no evidence in the documentation for 'Boolean'
that the authors intended this domain to be canonical. Instead, like
many other domains in FriCAS it is quite normal for domains to be
implemented as a quotient over their Rep. This means that equality in
the domain is not the same as equality in its Rep. This is consistent
with common Lisp. So far as I can see equality in 'Boolean' and the
boolean operators themselves have been implemented so that False is
represented by 'nil' and True is any other value just like in Lisp.

>> retractable? x == x pretend Boolean
>
> This 'pretend' is much worse that CONSP.
>

In what sense?

> Maybe is a low level domain, and it's one of the few "inline domains",
> it's totally OK to have $Lisp calls.
>

Yes. I was just suggesting that calling Lisp functions is no different
than making the assumption that the data values should be interpreted
in the same manner as Lisp in which case this function has a slightly
faster implementation.

[oldk1331]

On Sat, Oct 14, 2017 at 2:44 AM, Bill Page <bill...@newsynthesis.org> wrote:
> I do not understand 'Boolean' as a category. The 'Boolean' domain
> satisfies the following categories: 'OrderedSet', 'Finite', 'Logic'.
> Thinking of Boolean as a category in the mathematical sense seems
> unnecessarily abstract.
>
> There is no reason that the two values in Boolean need to be
> represented internally by just two values. If that were the case then
> it would be appropriate also for Boolean to satisfy the category
> 'Canonical'.

You said Boolean has 'Finite', and size()$Boolean is 2.
So Boolean should have Canonical. BTW, Canonical is not
used extensively in FriCAS, it is missing in many places.

>> This 'pretend' is much worse that CONSP.
>>
>
> In what sense?

Following previous section, this 'pretend' will be incorrect.
While CONSP returns either T or NIL.

[Bill Page]

On 13 October 2017 at 20:53, oldk1331 <oldk...@gmail.com> wrote:
>
> You said Boolean has 'Finite', and size()$Boolean is 2.
> So Boolean should have Canonical.

Canonical is not about the number of values in a domain, it is about
how equality is defined. Although Boolean has only two possible values
it has many possible representations of this theses values, in
particular, one unique representation for False but many equivalent
representations for True.

> BTW, Canonical is not used extensively in FriCAS, it is missing
> in many places.
>

Yes, that is true. It is probably only present where the authors had a
particular use for it.