qnew implementations

[Grégory Vanuxem]

Hello,

I looked a little at the different implementations of qnew and found
some what I think are issues. qnew, which should mean, I think, quick
new, is usually used to construct uninitialized arrays, but is rarely
exposed, presumably because it should only be used by Spad developers
and not FriCAS users.

An issue comes from TwoDimensionalArrayCategory (exposed) that
declares it. Matrix, TwoDimensionalArray and other domains use it (via
MatrixCategory for example). But if a user uses it, and the array is
displayed using OutputForm coercion let's see what happens:

Clozure CL:
=============
(1) -> qnew(4,4)$Matrix(Float)

Fatal error in "FRICASsys" : Fault during read of memory address #x5
=============
and returns to the system shell.
Segmentation fault so.

SBCL:
=============
(2) -> qnew(4,4)$Matrix(Float)

>> System error:
The value
0
is not of type
CONS
===============

What happens is that from what I have seen the elements of the
uninitialized array are integers (0) and OutputForm expects a Float
which is implemented in Lisp with a cons. Same thing happens with
POLY(INT) for example. I agree that the qnew function should only be
used if you know what you're doing and you know, if necessary, the
internal representation of an uninitialized array but having a Lisp
error instead of a system error is somewhat disappointing. Moreover,
if Clozure CL was used to build your FriCAS version, a segfault is
signalled and FriCAS crashes (see Murphy's law).

I put it here before filling an issue because I think "fixing" this
requires some thoughts. Personally I have no opinion on this, doing
nothing, documenting this, do not expose qnew, conditional export (I
only see INT and SINT), modifying qnew-s, but it will no longer be a
"quick" constructor, modifying OutputForm, etc.

BTW, Waldek, in your implementation of (unexposed) DoubleFloatVector,
DoubleFloatMatrix and their Complex counterparts, you use, contrary to
usual uses in FriCAS, for arrays at least, Integer as qnew arguments.
Wouldn't it be preferable to use NonNegativeInteger instead? You had
something in mind while doing this maybe. Again, the following code is
a nonsense but errare humanum est, even when typing:

Clozure CL:
================
(1) -> qnew(-4)$DoubleFloatVector
Fatal error in "FRICASsys" : Cannot allocate a (SIMPLE-ARRAY
DOUBLE-FLOAT (*)) with -4 elements.
Objects of type (SIMPLE-ARRAY DOUBLE-FLOAT (*)) can can have at most
72057594037927935 elements in this implementation.
================
FriCAS crashes and it is a return to the system shell.

SBCL:
================
(9) -> qnew(-3)$DoubleFloatVector

>> System error:
The value
-3
is not of type
(MOD 4611686018427387901)
================

Regards,
__
Greg

PS: the session examples given here were produced using the default CL
binaries from Roswell, I do not know the exact build settings
(roswell.github.io).

[Waldek Hebisch]

Well, in general array produced by 'qnew' is uninitialized and
can contain anything. Due to internal working of Lisp almost
surely such array will be filled with valid Lisp objects.
But one can not count on those object being 0, it could be Lisp
NIL or something else (AFAIK Poplog will use NIL-s).

_Any_ attempt to read elements of uninitialized array may lead
to troubles. So it is not only printing, but in general it is
unsafe to pass uninitialized array to a routine, unless one
_knows_ that the routine will initialize the array.

Currenly exposure is for constructors, if constructor is exposed
all its operations are exposed. And 'qnew' must be exported for
use in packages.

'qnew' is for speed, so IMO at code level we could check if it
actually gives speedup and replace it by 'new' in cases where
is does not matter. Actually, for general integer vectors qnew
gives no speedup and we do not have it. But AFAICS it gives
speedup exactly in cases where inproper uses is dangerous.
So really not much to do at code level.

We could add the followowing to description of 'qnew':

Use only when you know what you are doing.

Possibly we could add a FAQ entry with some explanation.

> BTW, Waldek, in your implementation of (unexposed) DoubleFloatVector,
> DoubleFloatMatrix and their Complex counterparts, you use, contrary to
> usual uses in FriCAS, for arrays at least, Integer as qnew arguments.
> Wouldn't it be preferable to use NonNegativeInteger instead? You had
> something in mind while doing this maybe. Again, the following code is
> a nonsense but errare humanum est, even when typing:
>
> Clozure CL:
> ================
> (1) -> qnew(-4)$DoubleFloatVector
> Fatal error in "FRICASsys" : Cannot allocate a (SIMPLE-ARRAY
> DOUBLE-FLOAT (*)) with -4 elements.
> Objects of type (SIMPLE-ARRAY DOUBLE-FLOAT (*)) can can have at most
> 72057594037927935 elements in this implementation.
> ================
> FriCAS crashes and it is a return to the system shell.
>
> SBCL:
> ================
> (9) -> qnew(-3)$DoubleFloatVector
>
> >> System error:
> The value
> -3
> is not of type
> (MOD 4611686018427387901)
> ================

Again, 'qnew' is for cases when the user knows what she/he is
doing.

I have doubts about general usefulness of NonNegativeInteger. Namely,
arithmetic is likely to produce Integer and then one needs coercion
to get NonNegativeInteger. To avoid extra code one probably would
use qcoerce and then we are back where we started: there is no
checking. And with Integer code is simpler.

--
Waldek Hebisch

[Ralf Hemmecke]

On 11/5/23 01:36, Waldek Hebisch wrote:
> _Any_ attempt to read elements of uninitialized array may lead
> to troubles. So it is not only printing, but in general it is
> unsafe to pass uninitialized array to a routine, unless one
> _knows_ that the routine will initialize the array.

Yes, exactly that is the point. qnew claims to return an object of type
%, but, in fact, it doesn't.

> We could add the followowing to description of 'qnew':
>
> Use only when you know what you are doing.

That is one thing, but does not give enough information. How should a
user know what he is doing? Where would he get this information from?
A better phrase would perhaps be:

qnew constructs structure with uninitialized elements.
Do not pass such a structure to other functions before
its parts are initialized via setelt! or qsetelt!.

> Possibly we could add a FAQ entry with some explanation.

Additionally also good, but I doubt that people jump to the FAQs if the
stumple over problems with qnew.

> I have doubts about general usefulness of NonNegativeInteger.

Indeed. There is no subtraction. Yes, that's not a total function in
NNI, but in most use cases the programmer knows that the result is still
in NNI. I sometimes wished there where a "minus: (NNI, NNI) -> NNI" that
throws an error if the result becomes negative. But I do not care too much.

Ralf

[Grégory Vanuxem]

Yes, this is not reliable, I had guessed that other implementations
can do it in another manner.

> _Any_ attempt to read elements of uninitialized array may lead
> to troubles. So it is not only printing, but in general it is
> unsafe to pass uninitialized array to a routine, unless one
> _knows_ that the routine will initialize the array.

Yes, the main problem for me is the segfault with Clozure CL. Another
one is maybe the Lisp implementation errors displayed in FriCAS, maybe
an adapted CL + boot (because of implementation specific stuff)
routine can be added to throw it in FriCAS, say

LISP error: blabla

Like FriCAS 'System error:'

> Currenly exposure is for constructors, if constructor is exposed
> all its operations are exposed. And 'qnew' must be exported for
> use in packages.
>
> 'qnew' is for speed, so IMO at code level we could check if it
> actually gives speedup and replace it by 'new' in cases where
> is does not matter. Actually, for general integer vectors qnew
> gives no speedup and we do not have it. But AFAICS it gives
> speedup exactly in cases where inproper uses is dangerous.
> So really not much to do at code level.

I didn't benchmark that type of thing, but that's interesting.

>
> We could add the followowing to description of 'qnew':
>
> Use only when you know what you are doing.
>
> Possibly we could add a FAQ entry with some explanation.

+1 for documenting this, and as Ralf suggests, a little more. A well
known expression also that I find funny, in the Unix-like world from
what I know, is "Use at your own risk" :)

Ok. So maybe uniformize this in the Spad code?

In fact, I completely forgot/occulted the fact that subtraction is
not available in NonNegativeInteger as pointed out by Ralf.

- Greg

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

[Waldek Hebisch]

On Sun, Nov 05, 2023 at 04:28:42PM +0100, Ralf Hemmecke wrote:
> On 11/5/23 01:36, Waldek Hebisch wrote:
> > _Any_ attempt to read elements of uninitialized array may lead
> > to troubles. So it is not only printing, but in general it is
> > unsafe to pass uninitialized array to a routine, unless one
> > _knows_ that the routine will initialize the array.
>
> Yes, exactly that is the point. qnew claims to return an object of type %,
> but, in fact, it doesn't.

Well, result of 'qnew' is uninitialized, but this does not differ
much from (note no initialization)

a : T

Would you say that a does not have type T? In principle
attempt to read 'a' before initialization may cause the same
trouble as attempt to read elements of array returned by 'qnew'.

> > We could add the followowing to description of 'qnew':
> >
> > Use only when you know what you are doing.
>
> That is one thing, but does not give enough information. How should a user
> know what he is doing? Where would he get this information from?

One of fundamental commandments of programming is:

"Thou shall not attempt to read uninitialized variables"

This is general programming knowledge, to get such knowledge
Dijkstra "Discipline of programming" may be good start.
For people wanting more concrete info, reading GCC bug
reports marked "invalid" may provide plenty of examples.

'qnew' is for micro-optimization and here Knuth applies:
"premature optimization is source of all evil".

> A better phrase would perhaps be:
>
> qnew constructs structure with uninitialized elements.
> Do not pass such a structure to other functions before
> its parts are initialized via setelt! or qsetelt!.

But there is more to this: people may think that someting like

a := qnew(4, 4)$Matrix(Float)
b := a(1,1) - a(1, 1)

will reliably produce 0. But the above is wrong, because 'a'
is uninitilied. The same error appears in

a : Float
b := a - a

Do you want to add a warning in FriCAS book in section describing
declarations that one should initialize variables before use?

Also, discussion about 'qnew' started because we get crash in
Clozure CL. However, once we use Lisp declaration to optimize,
we are subject to possible crashes in buggy code. Nontrivial
fraction of crashes when using GCL were due to user errors
which were cought by other Lisps, but crashed GCL. This time
GCL catches error, but Clozure CL crashes. Different Lisp
may crash on something else.

--
Waldek Hebisch

[Ralf Hemmecke]

On 11/7/23 02:29, Waldek Hebisch wrote:
>> Yes, exactly that is the point. qnew claims to return an object of type %,
>> but, in fact, it doesn't.
>
> Well, result of 'qnew' is uninitialized, but this does not differ
> much from (note no initialization)
>
> a : T

Maybe technically (i.e. how it is implemented in the compiler) it gives
similar things, but conceptually, I would say that "a:T" is different.
It is a declaration and thus just a hint to the compiler/interpreter
that when this identifier is used it is to be considered as something of
type T. However, I would expect the compiler to yell at me when I write
code like

=======================
)abbrev package FOO Foo
Foo: E == I where
E ==> with
foo: () -> Integer
I ==> add
foo(): Integer ==
a: Integer
b: Integer := a
=======================

Unfortunately, it doesn't. :-(

> Would you say that a does not have type T?

It has type T, but after a declaration a:T, there is not yet reservation
of memory on my computer, so in fact, I do not yet have a variable, just
a hint to the compiler that the identifier "a" has type T when it comes
to type checking.

>>> We could add the followowing to description of 'qnew':
>>>
>>> Use only when you know what you are doing.
>>
>> That is one thing, but does not give enough information. How should a user
>> know what he is doing? Where would he get this information from?
>
> One of fundamental commandments of programming is:
>
> "Thou shall not attempt to read uninitialized variables"

Of course. But putting a big warning sign is much better than just
mystically saying "Use only when you know what you are doing." and not
telling where to get information about it. It is like saying "Do not use
this function, because we are not telling you what it does."

I do not quite get your rejection of more informative documentation.
Put whatever you want into the ++ docstring.
I just wanted to say that I am more on the side of having documentation
that does not require uses to look at the code in order to understand
what a function does.

> This is general programming knowledge, to get such knowledge
> Dijkstra "Discipline of programming" may be good start.

Are you saying that people how haven't read this, should not use FriCAS?
I fear that then many mathematicians are excluded from or shy away from
FriCAS.

> But there is more to this: people may think that someting like
>
> a := qnew(4, 4)$Matrix(Float)
> b := a(1,1) - a(1, 1)

Why? a(1,1) is clearly the same as elt(a,1,1), i.e. use of a in a
function. Forbidden by my ++ suggestion.

> Do you want to add a warning in FriCAS book in section describing
> declarations that one should initialize variables before use?

Yes, why not. We all know that there is a difference between a FriCAS
(programming) variable and a variable (i.e. something that evaluates to
itself). In traditional CAS that's not totally easy to understand for a
first time user.

Ralf

[Hill Strong]

In terms of defining any kind of variable, the language and its associated semantics should have a [bottom] value. Interestingly, FriCAS does have such a value defined. However, what is not clear is whether this [bottom] can serve for all domains. 

There are a couple of alternatives here. One is that every domain has its own [bottom] value seperate from all other domains. Another is that all domains inherit the same [bottom] value.

I am in the process of looking at the FriCAS language to see where the semantic definition is either problematic or not defined. There appears to be quite a number of such things to fix. Reading the various threads shows that some serious language definitions are required. 

Regards to all of you

--
You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" group.
To unsubscribe from this group and stop receiving emails from it, send an email to fricas-devel...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/fricas-devel/1afe4a05-d804-42ca-802f-6f813f6501eb%40hemmecke.org.

[Waldek Hebisch]

On Tue, Nov 07, 2023 at 01:28:33PM +0100, Ralf Hemmecke wrote:
> On 11/7/23 02:29, Waldek Hebisch wrote:
> > > Yes, exactly that is the point. qnew claims to return an object of type %,
> > > but, in fact, it doesn't.
> >
> > Well, result of 'qnew' is uninitialized, but this does not differ
> > much from (note no initialization)
> >
> > a : T
>
> Maybe technically (i.e. how it is implemented in the compiler) it gives
> similar things, but conceptually, I would say that "a:T" is different.
> It is a declaration and thus just a hint to the compiler/interpreter that
> when this identifier is used it is to be considered as something of type T.

Well, we differ in our opinions what is conceptual. And we differ in
conceputal model of what "a : T" is doing: declaration instructs compiler
to allocate space for one thing (value of the variable) and promises
that we will store there only things of type T. 'qnew' allocate
space for specified number of things and type of array give similar
promise. They differ somewhat in ways you use them: "a : T"
associates name 'a' with allocated storage, in case or arrays
location are denoted by indexing expressions like 't(1,1)'. So
the way how you specify used storage cell is different, but semantics
of essentially the same. In FriCAS access to array element may
look like a function call, but logically is the same as access to
simple variable. So I would say that at Spad level implementaion
differs quite a lot but conceptually they are almost the same
(at lover level again there is some convergence of implementations).

> However, I would expect the compiler to yell at me when I write code like
>
> =======================
> )abbrev package FOO Foo
> Foo: E == I where
> E ==> with
> foo: () -> Integer
> I ==> add
> foo(): Integer ==
> a: Integer
> b: Integer := a
> =======================
>
> Unfortunately, it doesn't. :-(

Compiler emits warnings, it can not be (much) more because problem
of reliably and staticaly detecting reads from uninitialized variables
is unsolvable.

> > Would you say that a does not have type T?
>
> It has type T, but after a declaration a:T, there is not yet reservation of
> memory on my computer,

No, declaration reserves memory for variable. Resonable model is
that memory is reserved when declaration is "executed", that is
allocation happens at runtime when control flow reaches block
in which variable is declared (so actually "before" declaration,
but the difference is not important as you can use variable only
after declaration).

> so in fact, I do not yet have a variable, just a hint
> to the compiler that the identifier "a" has type T when it comes to type
> checking.
>
> > > > We could add the followowing to description of 'qnew':
> > > >
> > > > Use only when you know what you are doing.
> > >
> > > That is one thing, but does not give enough information. How should a user
> > > know what he is doing? Where would he get this information from?
> >
> > One of fundamental commandments of programming is:
> >
> > "Thou shall not attempt to read uninitialized variables"
>
> Of course. But putting a big warning sign is much better than just
> mystically saying "Use only when you know what you are doing." and not
> telling where to get information about it. It is like saying "Do not use
> this function, because we are not telling you what it does."
>
> I do not quite get your rejection of more informative documentation.

Well, when we got our first Unix machine in math in Wroclaw (in 1993)
it came with manual pages. There were hundreds of programs, each
having a manual "page", frequently having size of several printed
pages. Typical user reacion was "the system is badly documented,
documentation is so big that it is impossible to find anything".

And there is question what is "informative": I do not think
that _very_ basic "safety" warnings are informative.

> Put whatever you want into the ++ docstring.
> I just wanted to say that I am more on the side of having documentation that
> does not require uses to look at the code in order to understand what a
> function does.

Well, 'qnew' docstring clearly says that allocated array is
uninitialized. Rest is general knowledge (and code will not
help if somebody lacks that knowledge).

> > This is general programming knowledge, to get such knowledge
> > Dijkstra "Discipline of programming" may be good start.
>
> Are you saying that people how haven't read this, should not use FriCAS?
> I fear that then many mathematicians are excluded from or shy away from
> FriCAS.

Well, we are talking about 'qnew' here. Begining users, or even more
advanced ones who do not want to think about prgramming concepts should
avoid dangerous functions, like 'qnew' or destructive operations.

> > But there is more to this: people may think that someting like
> >
> > a := qnew(4, 4)$Matrix(Float)
> > b := a(1,1) - a(1, 1)
>
> Why? a(1,1) is clearly the same as elt(a,1,1), i.e. use of a in a function.
> Forbidden by my ++ suggestion.

Well, you look at implementaion and you see what looks like a function.
But conceptually it is not a function. With your proposal users having
right conceptual model may think that the above is allowed, while some
legal uses are forbiden (like using a function to intialize an array).

> > Do you want to add a warning in FriCAS book in section describing
> > declarations that one should initialize variables before use?
>
> Yes, why not. We all know that there is a difference between a FriCAS
> (programming) variable and a variable (i.e. something that evaluates to
> itself). In traditional CAS that's not totally easy to understand for a
> first time user.

Well, FriCAS book (and more so docstrings) is a reference documentation.
One merit of such documentation is shortness, that is skipping
information that user should already know. To say that truth,
I expect users to "know" that thay should not read vatiable before
initialization. "Know" in sense that users heard that at some
moment and forgot/ignored that information. I expect that short
warning in our documentaion would be ignored like previous
information.

Another is "findability": information should be in places were users
are expected to search for it. User unaware of dangers of using
uninitialized variables is unlikely to seach for such information
is section called "declarations". It makes sense to have a separate
section or chapter with title like "Programming model and safety"
which explains this and related things in more depth. Then we
could put short reference to this in part about declarations.
Docstring of 'qnew' is simply wrong place for such information.

--
Waldek Hebisch

[Waldek Hebisch]

On Wed, Nov 08, 2023 at 11:51:12AM +1100, Hill Strong wrote:
> In terms of defining any kind of variable, the language and its associated
> semantics should have a [bottom] value. Interestingly, FriCAS does have
> such a value defined. However, what is not clear is whether this [bottom]
> can serve for all domains.
>
> There are a couple of alternatives here. One is that every domain has its
> own [bottom] value seperate from all other domains. Another is that all
> domains inherit the same [bottom] value.
>
> I am in the process of looking at the FriCAS language to see where the
> semantic definition is either problematic or not defined. There appears to
> be quite a number of such things to fix. Reading the various threads shows
> that some serious language definitions are required.

Well, 'bottom' may be used in _description_ of semantics of a language.
There are many approches to describing semantics. One approach that
I like and I think fits well to FriCAS is axiomatic approach.
In this approach we have logical formulas associated with states
and each piece of code have two related formulas: precondition
and postcondition with meaning that if precondition is satisfied
then code will execite succesfuly and finish satisfying postcondition.
Theoretically, only precondition is neccesay, as one can replace
postcondition by appropriate code. Also, theory is nicer when
using infinitary logic, but practical approach uses clasical
(finite) logic.

Fundamental part of this apprach is that when precondition is not
satisfied, then there is no warranty, anything can happen: program
may crash, computer may explode or something else bad may happen.
Some people are unhappy about consequences of failed precondition
and invent formalizms where everthing is "defined", such formalizms
miss important property is real world languages and are not
appropriate to describe FriCAS.

Concerning uninitialized variables: it is convenient to use
special "bad" values (say 'bottom') to "mark" uninitialized
variables. That way statement 'a is initialized' can be
written as 'a \ne bottom'. But note that such 'bottom' by
neccessity is _not_ a valid value of variable: initialized
variable can not have 'bottom' as its value. So here
'bottom' is purely virtual: does not exist in reality and
can not be value of any type.

Some people want to eliminate uninitialized variables by
providing default initialization, say to 0 or to 'botton'.
However, this replaces problem of uninitialized variables
by problems of wrongly uninitialized variables. Wrong
initialization is at least as bad as lack in initialization,
so in practice this in not very useful. If variables are
initialized to 'bottom' and attempts to use 'bottom'
in computations are detected, then this may help in
finding uses of uninitialized variables. However, such
approach is costly at runtime, so not appropriate for
high perfomance software.

--
Waldek Hebisch

[Hill Strong]

Comments below.

On Wed, 8 Nov 2023, 2:28 pm Waldek Hebisch, <de...@fricas.org> wrote:

On Wed, Nov 08, 2023 at 11:51:12AM +1100, Hill Strong wrote:
> In terms of defining any kind of variable, the language and its associated
> semantics should have a [bottom] value. Interestingly, FriCAS does have
> such a value defined. However, what is not clear is whether this [bottom]
> can serve for all domains.
>
> There are a couple of alternatives here. One is that every domain has its
> own [bottom] value seperate from all other domains. Another is that all
> domains inherit the same [bottom] value.
>
> I am in the process of looking at the FriCAS language to see where the
> semantic definition is either problematic or not defined. There appears to
> be quite a number of such things to fix. Reading the various threads shows
> that some serious language definitions are required.

Well, 'bottom' may be used in _description_ of semantics of a language.
There are many approches to describing semantics.  One approach that
I like and I think fits well to FriCAS is axiomatic approach.

This is a difference between us. I have found that the denotational semantics is superior. Of course, trying to ensure that you have a consistent model for the language in question via denotational semantics can be quite time consuming. 

In this approach we have logical formulas associated with states
and each piece of code have two related formulas: precondition
and postcondition with meaning that if precondition is satisfied
then code will execite succesfuly and finish satisfying postcondition.

However, this approach fails to define clearly what the code in question is doing. This is especially true if you are dependent on the implementation underlying that code. 

Theoretically, only precondition is neccesay, as one can replace
postcondition by appropriate code.  Also, theory is nicer when
using infinitary logic, but practical approach uses clasical
(finite) logic.

Since I am not a mathematician, my approach is from the computer language position. I have used Icon/Unicorn languages for many decades and SNOBOL 4 prior to that. The feature of these languages that has been essential to me has been the idea that failure is an option. Intriguingly, this idea appears in FriCAS but in a very kludgy manner. 

Within the above languages, failure drives all testing, irrespective of whether this is found in if/then/else or the different types of loops or even assignments. 

Certain kinds of mathematical expressions are significantly clearer in Icon/Unicon than in the normal kinds of languages. A couple of examples:

0 < I < K < 10 tests that both I and K are between the endpoints 0 and 10 and that I is less than K. This is contrast to the following normal formulation:

0 < I and I < K and K < 0.

If any one of these is not true then failure is signalled.

Fundamental part of this apprach is that when precondition is not
satisfied, then there is no warranty, anything can happen: program
may crash, computer may explode or something else bad may happen.

This is precisely what is not wanted.

Some people are unhappy about consequences of failed precondition
and invent formalizms where everthing is "defined", such formalizms
miss important property is real world languages and are not
appropriate to describe FriCAS.

Just because "real world" languages might do this, it does not mean that this is the approach that should be followed. 

You want the least number of surprises and you want risky things to be difficult and not something that just happens.

Concerning uninitialized variables: it is convenient to use
special "bad" values (say 'bottom') to "mark" uninitialized
variables.  That way statement 'a is initialized' can be
written as 'a \ne bottom'.

Better is to have an operator that can fail if a variable is uninitialised and returns the variable if initialised. The dual to that is an operator that fails if the variable is initialised and returns the variable if it is uninitialised.

But note that such 'bottom' by

neccessity is _not_ a valid value of variable: initialized
variable can not have 'bottom' as its value.  So here
'bottom' is purely virtual: does not exist in reality and
can not be value of any type.

Yet the study of lattices with denotational semantics does allow for [bottom] to have a meaningful existence. Of course, in the context of domains, the use of such a value doesn't produce anything other than [bottom]. Its purpose is to indicate uninitialised variables. 

Some people want to eliminate uninitialized variables by
providing default initialization, say to 0 or to 'botton'.

In the vast majority of cases, the creation of a variable is immediately followed by an initialisation. There should be very rare cases where the creation of the variable is not followed by an initialisation. Looking through the FriCAS code base, I have found few places that actually require a definition of a variable without immediate initialisation.

However, this replaces problem of uninitialized variables
by problems of wrongly uninitialized variables.  Wrong
initialization is at least as bad as lack in initialization,

Wrongly initialised variables are always a problem. What this means is that the programmer has not thought through the problem carefully enough. 

It is one thing to have an uninitialised variable containing the [bottom] value, it is another to having some unknown value sitting in the variable coming from the underlying implementation.

so in practice this in not very useful.  If variables are
initialized to 'bottom' and attempts to use 'bottom'
in computations are detected, then this may help in
finding uses of uninitialized variables. 

Having an uninitialised variable deliberately should be hard to do and not something that can happen as a normal matter of writing your code. 

Writing code takes a great deal thought and skill, this is where the language in question should be not full of surprises.

However, such
approach is costly at runtime, so not appropriate for
high perfomance software.

With today's systems, this mindset is actually counter productive. The algorithms used are far more important than worrying about trying to get high performance from lesser "problems".

It is far more important that the code is correct.

--
                              Waldek Hebisch

--
You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" group.
To unsubscribe from this group and stop receiving emails from it, send an email to fricas-devel...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/fricas-devel/ZUsAUrV8%2BSI51M3K%40fricas.org.

[Waldek Hebisch]

Each formalizm will abstract over (that is leave unspecified) some
details. In axiomatic approach you can define things in fine detail
or leave them unspecified, that is your choice. Concerning clearly,
that depends very much of familiarity with given formalizm.

> > Fundamental part of this apprach is that when precondition is not
> > satisfied, then there is no warranty, anything can happen: program
> > may crash, computer may explode or something else bad may happen.
> >
>
> This is precisely what is not wanted.
>
> Some people are unhappy about consequences of failed precondition
> > and invent formalizms where everthing is "defined", such formalizms
> > miss important property is real world languages and are not
> > appropriate to describe FriCAS.
> >
>
> Just because "real world" languages might do this, it does not mean that
> this is the approach that should be followed.
>
> You want the least number of surprises and you want risky things to be
> difficult and not something that just happens.

Well, anybody wants to avoid bad things. In axiomatic approach
it is "easy": ensire that preconditions are satisfied. However,
you can not "define away" problems. For example PL/I was early
attempt to make everthing defined: it was hard to implement,
and bad things could easily happen in user programs. Those
bad things frequently were "well defined", but where not what
users intended.

> > Concerning uninitialized variables: it is convenient to use
> > special "bad" values (say 'bottom') to "mark" uninitialized
> > variables. That way statement 'a is initialized' can be
> > written as 'a \ne bottom'.
>

> > Some people want to eliminate uninitialized variables by
> > providing default initialization, say to 0 or to 'botton'.
> >
>
> In the vast majority of cases, the creation of a variable is immediately
> followed by an initialisation. There should be very rare cases where the
> creation of the variable is not followed by an initialisation. Looking
> through the FriCAS code base, I have found few places that actually require
> a definition of a variable without immediate initialisation.

Yes. So in practice uninitialized variables are not big trouble:
there is limited number of places where we need delayed initialization
and with some effort we can make sure that initialization happens
before use.

> However, this replaces problem of uninitialized variables
> > by problems of wrongly uninitialized variables. Wrong
> > initialization is at least as bad as lack in initialization,
> >
>
> Wrongly initialised variables are always a problem. What this means is that
> the programmer has not thought through the problem carefully enough.
>
> It is one thing to have an uninitialised variable containing the [bottom]
> value, it is another to having some unknown value sitting in the variable
> coming from the underlying implementation.

Well, in both cases program is wrong. Of course, when debugging
it helps if implementation tells you about uninitialized variables.
But reporting uninitialized variables has its cost, and it is not
clear if it is worth paying this cost.

> so in practice this in not very useful. If variables are
> > initialized to 'bottom' and attempts to use 'bottom'
> > in computations are detected, then this may help in
> > finding uses of uninitialized variables.
>
>
> Having an uninitialised variable deliberately should be hard to do and not
> something that can happen as a normal matter of writing your code.

Well, deliberatly reading uninitialised variable does not happen
as a normal matter of writing code. Having variable which is initialized
some time after declaration while not frequent is quite normal.

OTOH tryning to prevent writing wrong code in many cases is
futile: when programmer can not write useful code in natural
way because some construct was forbiden as dangerous, then
code would get written in less natural way which is freqently
more error prone than natural way.

> Writing code takes a great deal thought and skill, this is where the
> language in question should be not full of surprises.

There is no surprise with uninitialized variables, reading them is
clearly an error. And as you noticed it is not hard to avoid
such errors.

> However, such
> > approach is costly at runtime, so not appropriate for
> > high perfomance software.
> >
>
> With today's systems, this mindset is actually counter productive. The
> algorithms used are far more important than worrying about trying to get
> high performance from lesser "problems".
>
> It is far more important that the code is correct.

Well, premature optimization is bad. But once you have good algoritm
you may find out that speed is still lower than desired. Lower
level implementation details can make a lot of difference. Already
factor of 2 may be significant and factor of 1000 may easily happen
when you compare optimizing compiler to "safe interpreter".

--
Waldek Hebisch

[Hill Strong]

I agree with you in regards to the abstraction provided by each formalism.

 

In axiomatic approach you can define things in fine detail
or leave them unspecified, that is your choice. 

The problem here is: what kinds of things are left unspecified? In many of the [language] standards available, those things that are left unspecified actually give rise to significant problems between each of the implementations trying to provide the spacified [standard]. I have spent forty years designing, implementing and maintaining many different real-life systems. The biggest problems have been involved in moving from one implementation to another. We see this problem here in FricCAS when moving from one implementation of Common Lisp to another. This very thread about "qnew" and how this is implemented.

In terms of the semantics for "qnew", this shows up with the discussion seen far. This is where my point about [bottom] comes to the fore. In effect, This is a logical value and just how a specific implementation implements this [bottom] value becomes irrelevant as long as each implementation provides a logically and semantically consistent value that represents [bottom]. This will not affect any of the source code per se.

 

Concerning clearly,
that depends very much of familiarity with given formalizm. 

> > Fundamental part of this apprach is that when precondition is not
> > satisfied, then there is no warranty, anything can happen: program
> > may crash, computer may explode or something else bad may happen.
> >
>
> This is precisely what is not wanted.
>
> Some people are unhappy about consequences of failed precondition
> > and invent formalizms where everthing is "defined", such formalizms
> > miss important property is real world languages and are not
> > appropriate to describe FriCAS.
> >
>
> Just because "real world" languages might do this, it does not mean that
> this is the approach that should be followed.
>
> You want the least number of surprises and you want risky things to be
> difficult and not something that just happens.

Well, anybody wants to avoid bad things.  In axiomatic approach
it is "easy": ensire that preconditions are satisfied. 

"Risky" things are quite different to "bad" things. You can have all the "preconditions" that you want. However, if some action is left to the implementation or is undefined, all of those preconditions amount to nothing in terms of correctness. Correct code is hard enough to achieve without trying to get code correct with undefined or unspecified behaviour from each implementation.

I have been investigating Maxima and Axiom/FriCAS and there are all sorts of peculiar edge cases in each of these systems that arise from unspecified language semantics. I am currently investigating a significant update (alterations/changes) to the FriCAS language because of these peculiarities. I suspect and have scheduled up to 5 years for the redevelopment of FriCAS language and to have a fully specified denotational semantics available. Now, I am doing this for my own purposes and it may well be of zero interest to anyone else. But since I am effectively retired and this is one of my interests and I have a longer term purpose for the more general use of such a system, I shall proceed along this path and see what results from it/

 

However,
you can not "define away" problems.  For example PL/I was early
attempt to make everthing defined: it was hard to implement,
and bad things could easily happen in user programs.  Those
bad things frequently were "well defined", but where not what
users intended.

I agree that PL/I was an attempt to be all things to all people but this also applies to many languages that have been developed since the late 50's. Being hard to implement is NOT a factor in designing and implementing an appropriately defined semantics for any language. That is part and parcel to those designing a language and building the infrastructure for that language.

A case in point here is my comment about failure being an option. This requires of the implementation quite a few complexities in the implementation. As far as the semantics for the language itself, as long as these are clearly defined and logically explained, then a programming language user can use this to good effect consistently. In addition, keep your various language attributes orthogonal, don't conflate separate ideas where they shouldn't be.

In this discussion about "qnew", this should only be available in the underlying implementation and should have no (as in zero) visibility to any user of the FriCAS language, not a casual user nor somebody building any category/domain/package.

 

> > Concerning uninitialized variables: it is convenient to use
> > special "bad" values (say 'bottom') to "mark" uninitialized
> > variables.  That way statement 'a is initialized' can be
> > written as 'a \ne bottom'.
>
> > Some people want to eliminate uninitialized variables by
> > providing default initialization, say to 0 or to 'botton'.
> >
>
> In the vast majority of cases, the creation of a variable is immediately
> followed by an initialisation. There should be very rare cases where the
> creation of the variable is not followed by an initialisation. Looking
> through the FriCAS code base, I have found few places that actually require
> a definition of a variable without immediate initialisation.

Yes.  So in practice uninitialized variables are not big trouble:
there is limited number of places where we need delayed initialization
and with some effort we can make sure that initialization happens
before use.

Unfortunately, there are instances where they are [big trouble] and this is one of those risky activities that should be very hard to do. I have spent considerable time reading the code base and I am very suspicious as to the veracity of different sections of the code base. Yes effort can be put into making sure that initialisation does occur before use, but as experience has shown me over forty years, this effort is often assumed to have been done when it wasn't. What is interesting here though is that sheer happenstance can occur where it doesn't appear to matter until a edge case scenario occurs and then you are left scratching your head trying to determine what has actually happened.

 

> However, this replaces problem of uninitialized variables
> > by problems of wrongly uninitialized variables.  Wrong
> > initialization is at least as bad as lack in initialization,
> >
>
> Wrongly initialised variables are always a problem. What this means is that
> the programmer has not thought through the problem carefully enough.
>
> It is one thing to have an uninitialised variable containing the [bottom]
> value, it is another to having some unknown value sitting in the variable
> coming from the underlying implementation.

Well, in both cases program is wrong.  Of course, when debugging
it helps if implementation tells you about uninitialized variables.
But reporting uninitialized variables has its cost, and it is not
clear if it is worth paying this cost.

Yes, both are wrong. But having a defined [bottom] value is far better than some  unknown value that has the appearance of being correct. The latter is much more difficult to find, very much more difficult.

As for the cost of reporting uninitialised variables, this is a compiler function and not a runtime function and is worth the cost. If the compiler is not able to determine this then you have a serious problem on your hands. 

 

> so in practice this in not very useful.  If variables are
> > initialized to 'bottom' and attempts to use 'bottom'
> > in computations are detected, then this may help in
> > finding uses of uninitialized variables.
>
>
> Having an uninitialised variable deliberately should be hard to do and not
> something that can happen as a normal matter of writing your code.

Well, deliberatly reading uninitialised variable does not happen
as a normal matter of writing code.  Having variable which is initialized
some time after declaration while not frequent is quite normal.

Deliberately reading an uninitialised variable is completely warped in any case and is something that the compiler should already be picking up as it is doing its semantic analysis and code generation. For all purposes, the FriCAS language should be high level code and not delving into implementation issues.

OTOH tryning to prevent writing wrong code in many cases is
futile: when programmer can not write useful code in natural
way because some construct was forbiden as dangerous, then
code would get written in less natural way which is freqently
more error prone than natural way.

You are conflating a couple of ideas here. The first idea is that wrong code is always easy to write. The second idea is related to the allowable constructs within the language. These are quite separate and should not be conflated. The third idea is about wrong code due to semantic lacks in the language. This is a quite separate issue to the available language constructs and the ability to write wrong code using the available language.

As I pointed out above in relation to Icon/Unicon, the use of failure makes the writing of more natural code easier. The example I used was related to range testing as in

0 < I < K < 10

where both I and K are between the limits 0 and 10 and I has to be less than K

But I could also use  an alternate test such as comparing a variable to a series of values as in

currentStr == ("fair" | "good" | "better")

where we are testing if the string value in currentStr is one of "fair" or "good" or "better".

The FriCAS language has some very good natural ways to express particular ideas. But it also has some very awful examples as well and is not consistent in how certain constructs are implemented. This kind of thing is found in all languages, but can be improved over time.

 

> Writing code takes a great deal thought and skill, this is where the
> language in question should be not full of surprises.

There is no surprise with uninitialized variables, reading them is
clearly an error.  And as you noticed it is not hard to avoid
such errors.

Actually, there are various places in the FriCAS code base where just reading the code in front of you doesn't tell you anything about whether or not a particular variable has been initialised. You have to go hunting elsewhere to determine that and may have to read and analyse other sections of the code. It is certainly not as easy as you make it out to be.

 

> However, such
> > approach is costly at runtime, so not appropriate for
> > high perfomance software.
> >
>
> With today's systems, this mindset is actually counter productive. The
> algorithms used are far more important than worrying about trying to get
> high performance from lesser "problems".
>
> It is far more important that the code is correct.

Well, premature optimization is bad. 

I am not talking about premature optimisation. I am talking about getting the code correct. This includes making sure that edge cases don't bite you.

 

But once you have good algoritm
you may find out that speed is still lower than desired. 

Honestly, for today's activities where you are using something like FriCAS, speed will always be lower than desired. If this is a problem, you get better equipment or look for better algorithms.

 

Lower
level implementation details can make a lot of difference. 

Yes of course. But this is NOT your problem in terms of being a user to something like FriCAS. This is a problem for the compiler maintainer and should never ever intrude upon the language user. If you start down that rabbit hole you are going to make a mess of things. There have been many others who have gone down this path and the end results were not worth it.

 

Already
factor of 2 may be significant and factor of 1000 may easily happen
when you compare optimizing compiler to "safe interpreter".

For the vast majority, a factor of 2 is ridiculously insignificant, even a factor of 100 or 1000 will not be significant for the majority. If it is going to affect things significantly, then this is in the hands of the compiler maintainer and still should not affect or be relevant to any user of the system/language. The only thing they should see is a decrease in runtime as the compiler is improved. Their usage or code writing should not be affected.

The last point here is that every language represents a virtual machine that the user is writing for and anything that implements that virtual machine is NOT in the domain (or should NOT be ) of things that concerns the system/language user. If they are forced to have to take notice this interferes with what they are trying to achieve and is seriously detrimental to achieving their goals. Keep in mind that FriCAS (and all such systems) is a tool for achieving certain purposes. For the user of that system  to have to understand the inner workings adds an additional burden that should not be necessary unless they particularly want to get involved. The analogy here is that FriCAS is a motor vehicle that gets you from one place to another, as long as it does, you are not required and should not be required to understand the workings of an internal combustion engine or an automatic gearbox.

 

--
                              Waldek Hebisch

--
You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" group.
To unsubscribe from this group and stop receiving emails from it, send an email to fricas-devel...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/fricas-devel/ZUuPRiOpurvawVUV%40fricas.org.

[Tim Daly]

Hill Strong writes:

"I have been investigating Maxima and Axiom/FriCAS and there are all sorts of peculiar edge cases in each of these systems that arise from unspecified language semantics. I am currently investigating a significant update (alterations/changes) to the FriCAS language because of these peculiarities. I suspect and have scheduled up to 5 years for the redevelopment of FriCAS language and to have a fully specified denotational semantics available. Now, I am doing this for my own purposes and it may well be of zero interest to anyone else. But since I am effectively retired and this is one of my interests and I have a longer term purpose for the more general use of such a system, I shall proceed along this path and see what results from it/"

I'd be very interested in your sematics efforts.

Tim Daly

[Hill Strong]

Good evening Tim,

I will set up a github repository in the near future (in the next couple of months) and let you know when it is ready for any comments (including any negative) as there will be things I won't have seen.