On 8 October 2017 at 03:47, Ralf Hemmecke <[email protected]> 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.
--
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 [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/fricas-devel.
For more options, visit https://groups.google.com/d/optout.
