Proof that not requiring that unbound variables be declared before being used makes MathPiper fragile

[Ted Kosan]

Ever since I first started learning the MathPiper/Yacas language, the
significant use of unbound variables in the library code has bothered
me. I kept wondering what would happen if a user bound something to an
unbound variable that was being used in the library somewhere. Our
recent discussion on the declaration of unbound variables prompted me
to find out.

The following code uses TemplateFunction to create a function called
MyUntil and it works properly because it returns True:

%mathpiper
TemplateFunction("MyUntil",{predicate,body})
[
Eval(body);
While (Equal?(Eval(predicate),False))
[
Eval(body);
];
True;
];
UnFence("MyUntil",2);
HoldArgumentNumber("MyUntil",2,1);
HoldArgumentNumber("MyUntil",2,2);
Bodied("MyUntil",60000);

%/mathpiper

%output,preserve="false"
Result: True
. %/output

Now, lets bind a value to a variable called "Hold" and then try
defining MyUntil again:

In> Hold := "XX"
Result: "XX"

%mathpiper
TemplateFunction("MyUntil",{predicate,body})
[
Eval(body);
While (Equal?(Eval(predicate),False))
[
Eval(body);
];
True;
];
UnFence("MyUntil",2);
HoldArgumentNumber("MyUntil",2,1);
HoldArgumentNumber("MyUntil",2,2);
Bodied("MyUntil",60000);

%/mathpiper

%error,preserve="false"
Result: Problem with function ***("XX")***, <wrong code: "XX"

(Prog

(Eval $body96)

(While

(Equal?

(Eval $predicate96) False)

(Prog

(Eval $body96))) True)>, <the 1 parameter version of
this function is not defined (MAKE SURE THE FUNCTION IS SPELLED
CORRECTLY).> In function: List. In function: :=, Error near line 11
starting at index -1.
. %/error

Unbinding "Hold" will enable TemplateFunction to work properly again.

---------------------------

Here is another example of how easy it is for users to accidentally
break MathPiper:

In> True := 7
Result: 7

In> True
Result: 7

In> (3 <? 4)
Result: Exception
Exception: Predicate doesn't evaluate to a boolean in pattern. Extra
information: <The predicate True evaluated to 7.>. In function: Prog.
In function: <?,

In> Factor(100)
Result: Exception
Exception: Predicate doesn't evaluate to a boolean in pattern. Extra
information: <The predicate True evaluated to 7.>. In function: Prog.
In function: VarList,

-------------------------

These experiments have confirmed my suspicion that users can break
MathPiper relatively easily by simply binding a value to an unbound
variable that is being used in the library code somewhere. My thought
is that these experiments are a strong indicator that changing
MathPiper so that all unbound variables must be declared before being
used is a good idea.

Ted

[Sherm Ostrowsky]

Interesting!  I had no idea you could bind to "variables" with such names.  Wouldn't it have been easier to have "reserved words" like most other languages do?

Sherm

[Ted Kosan]

Sherm wrote:

> Interesting!  I had no idea you could bind to "variables" with such names.
> Wouldn't it have been easier to have "reserved words" like most other
> languages do?

My understanding is that most Lisp dialects (including MathPiper)
don't have reserved words.

Reduce solves the potential name clash problem between library code
and user code by having the names of identifiers used in the library
contain characters such as *, : and =.

Ted

[grzesiek]

Hi,

Good catch! But you're looking at wrong solution. What we really need is an ability to protect certain

symbols. And in principle all the symbols defined in the standard library should be protected. What I

mean is a pair of functions Protect/Unprotect with interface analogous to Hold/Unhold. Calling Protect 

on a symbol would effect in an attempt to Bind being an error. Of course you can Unprotect a symbol,

but this requires explicit action and can't be made by mistake. Note that such approach would result

in quite clear diagnostic.

Grzesiek

[grzesiek]

Hi,

On Tuesday, September 27, 2011 8:24:31 AM UTC+2, tkosan wrote:

Sherm wrote:

> Interesting!  I had no idea you could bind to "variables" with such names.
> Wouldn't it have been easier to have "reserved words" like most other
> languages do?

My understanding is that most Lisp dialects (including MathPiper)
don't have reserved words.

http://reference.wolfram.com/mathematica/ref/Protected.html

 

Reduce solves the potential name clash problem between library code
and user code by having the names of identifiers used in the library
contain characters such as *, : and =.

Tricky. It may work (eg it works in TeX, where you have the special @ symbol), but

this way you strongly differentiate library and user code. And I'm not sure this is desirable.

I've been always thinking of CAS beeing an open-ended system, where user extension

blend in easily.

Grzesiek

[Ted Kosan]

grzesiek wrote:

As I looked into this problem further, I saw that numerous places in
the library code use unbound variables the way that Lisp uses quoted
symbols (for example 'index, 'x, 'answer, etc). In Lisp, a single
quote in front of a symbol causes it to not be evaluated so it can be
used as data instead. In the following two examples, Cos, x, alist,
and aindex are used like this:

ListToFunction({Cos, x});
Result: Cos(x);

Rulebase("Nth",{alist,aindex});

Instead of using an operator such as ' to force a symbol to not be
evaluated, MathPiper uses strings. In the above code, "Nth" is used
this way. For some reason some of the Yacas functions use the symbolic
variables to pass names-as-data to functions, some use strings to pass
these names, and some use a mixture of both techniques. Instead of
using Protect/Unprotect for this kind of use, my thought is to simply
change all the code so that strings are always used instead of unbound
variables when passing names-as-data to functions or obtaining them
from functions.

As for constants like True and False, I like something similar to your
Protect/Unprotect idea, but my thought is to use a name like Constant
to be compatible with the CachedConstant function that is already in
the library:

Constant("True")

Ted

[grzesiek]

Hi,

On Wednesday, September 28, 2011 12:16:45 AM UTC+2, tkosan wrote:

As I looked into this problem further, I saw that numerous places in
the library code use unbound variables the way that Lisp uses quoted
symbols (for example 'index, 'x, 'answer, etc). In Lisp, a single
quote in front of a symbol causes it to not be evaluated so it can be
used as data instead. In the following two examples, Cos, x, alist,
and aindex are used like this:

ListToFunction({Cos, x});
Result: Cos(x);

Rulebase("Nth",{alist,aindex});

Instead of using an operator such as ' to force a symbol to not be
evaluated, MathPiper uses strings. In the above code, "Nth" is used
this way. For some reason some of the Yacas functions use the symbolic
variables to pass names-as-data to functions, some use strings to pass
these names, and some use a mixture of both techniques. Instead of
using Protect/Unprotect for this kind of use, my thought is to simply
change all the code so that strings are always used instead of unbound
variables when passing names-as-data to functions or obtaining them
from functions.

Sorry,  but you've lost me. I just claimed that we need a way of marking 

certain symbols as being immutable to protect their original definition from 

being accidentally overridden. In principle it boils down to having an associative 

array mapping symbols to their attributes and teaching Bind to check if

a symbol to be bound has the Protected attribute. And reading your analysis 

I can't really grasp what you are aiming at.

Grzesiek 

[Ted Kosan]

Grzesiek wrote:

> Sorry,  but you've lost me. I just claimed that we need a way of marking
> certain symbols as being immutable to protect their original definition
> from
> being accidentally overridden. In principle it boils down to having an
> associative
> array mapping symbols to their attributes and teaching Bind to check if
> a symbol to be bound has the Protected attribute. And reading your analysis
> I can't really grasp what you are aiming at.

The problem is that unbound variables are currently used for the
following three different purposes in the library code (the unbound
variable examples which are listed in each category are present in the
library code. Not all of the unbound variables that are in the library
code are in these examples and some of the examples may be
miscategorised):

// 1) Constants:
False
True
Empty
Undefined
Infinity

// 2) Unbound variables which are probably used for symbolic math purposes:
y
x
p
s
t
i
k
n
b
c
m
C
A
B
D

// 3) Unbound variables which are mostly used as Lisp-like symbols to
pass names to functions and for
//name comparisons.
//Most of these names can simply be placed in double quotes so that
they will not be
//affected if a value is bound to a variable of the same name.
Constant?
Hold
Nth
var
sum
expr
PositiveInteger?
Assert
arg
gamma
ToAtom
value
coefs2
mathpiper
ChiSquareTest
Number?
coefs1
*
Pi
int1
num
degree
term
Catalan
GoldenRatio
Ln2

Making the constants in category 1 immutable will not be too difficult to do.

Making the unbound variables in categories 2 and 3 immutable would not
be too difficult to do either, but it looks like it would cause
problems.

Ted

[grzesiek]

Hi,

OK, thanks for the detailed response. I hope that it'll get us to the crux 

of the issue.

On Saturday, October 8, 2011 9:11:02 AM UTC+2, tkosan wrote:

The problem is that unbound variables are currently used for the
following three different purposes in the library code (the unbound
variable examples which are listed in each category are present in the
library code.

IMHO the misunderstandings stem from a simple root. What you call 

unbound variables are in fact symbols.

 

Not all of the unbound variables that are in the library
code are in these examples and some of the examples may be
miscategorised):

// 1) Constants:
False
True
Empty
Undefined
Infinity

A bunch of symbols representing constants. They have to be protected against being accidentaly redefined.

 

// 2) Unbound variables which are probably used for symbolic math purposes:
y
x
p
s
t
i
k
n
b
c
m
C
A
B
D

A bunch of unbound symbols. They should not be used at all by the standard library. (Of course except when they are defined as local symbols, in which case they do not interfere at all with the user code.)

A bunch of symbols representing functions. (Except eg. Pi, which should go to another category, but that's not crucial.) The symbols should be protected as well, to avoid accidental redefinition.

 

Making the constants in category 1 immutable will not be too difficult to do.

Right. However, as soon as you start thinking in the category of symbols, you'll see that there's no real distinction between categories 1 and 3.

 

Making the unbound variables in categories 2 and 3 immutable would not
be too difficult to do either, but it looks like it would cause
problems.

I can see no reason to make the symbols in category 2 immutable. OTOH, categories 1 and 3 should

be marked as immutable to protect the semantics of the standard library.

Now:

 1. Make a (global) map symbol->list_of_properties, let's call it BuiltinProperties

 2. Make a function Protect[symbol_IsAtom] which adds Protected as a property of given symbol in the BuiltinProperties map.

 3. Make a function UnProtect[symbol_IsAtom], which removes the Protected property (if present) from the properties of the given symbol

 4. Teach Bind to throw an exception if a symbol to be bound is protected

 5. Go through the standard library and Protect all the symbols

Grzesiek

[Ted Kosan]

Grzesiek wrote:

> IMHO the misunderstandings stem from a simple root. What you call
> unbound variables are in fact symbols.

I agree that what are referred to as unbound variables in MathPiper
are implemented using Lisp symbols (I did mentioned this in an earlier
email). Here is a definition for what a Lisp symbol is:

"The symbol type is common to Lisp languages, but largely unknown
outside them. A symbol is a unique, named data object with several
parts: name, value, function, property list and package. Of these,
value cell and function cell are the most important. Symbols in Lisp
are often used similarly to identifiers in other languages: to hold
value of a variable; however there are many other uses. Normally, when
a symbol is evaluated, its value is returned. Some symbols evaluate to
themselves, for example all symbols in the keyword package are
self-evaluating. Boolean values in Common Lisp are represented by the
self-evaluating symbols T and NIL. Common Lisp has namespaces for
symbols, called 'packages'."
(http://en.wikipedia.org/wiki/Common_Lisp).

The Lisp implementation that MathPiper uses, however, only implements
some of these capabilities. For example, its symbols do not have
package capabilities.

> categories 1 and 3 should
> be marked as immutable to protect the semantics of the standard library.
> Now:
>  1. Make a (global) map symbol->list_of_properties, let's call it
> BuiltinProperties
>  2. Make a function Protect[symbol_IsAtom] which adds Protected as a
> property of given symbol in the BuiltinProperties map.
>  3. Make a function UnProtect[symbol_IsAtom], which removes the Protected
> property (if present) from the properties of the given symbol
>  4. Teach Bind to throw an exception if a symbol to be bound is protected
>  5. Go through the standard library and Protect all the symbols

I agree that the unbound variables/Lisp symbols in category 1 should
be marked as immutable, but I don't agree that the ones in category 3
should be.

Most versions of Lisp solve the exact problem we are having with
unbound variables/Lisp symbols by using a "quote" operator (which uses
the single quote ' character). The "quote" operator simply causes the
expression to its immediate right to not be evaluated. Unfortunately,
Yacas never had a "quote" operator added to it so most of the unbound
variables/Lisp symbols in category 3 (which are being used like Lisp
quoted symbols are typically used) are being used unsafely.

The closest things that MathPiper has to a quoted Lisp symbol are
strings and the Hold() function. Most of the unbound variables/Lisp
symbols in category 3 can be made safe by simply placing them in
double quotes.

Another solution is to add a Lisp-like "quote" operator to MathPiper
which is a shortcut for the Hold() function. This operator can then be
used to hold the evaluation of the unbound variables/Lisp symbols that
are in category 3. I recently added an experimental "quote" operator
to MathPiper and it seems to work fairly well:

In> a
Result: a

In> a := 7
Result: 7

In> a
Result: 7

In> 'a
Result: a

In> b := 8
Result: 8

In> 'a + b
Result: a+8

In> a + 'b
Result: b+7

In> '(a + b)
Result: a+b

Ted

[grzesiek]

Hi,

On Saturday, October 8, 2011 10:45:20 AM UTC+2, tkosan wrote:

Grzesiek wrote:

> IMHO the misunderstandings stem from a simple root. What you call
> unbound variables are in fact symbols.

I agree that what are referred to as unbound variables in MathPiper
are implemented using Lisp symbols (I did mentioned this in an earlier
email). Here is a definition for what a Lisp symbol is:

"The symbol type is common to Lisp languages, but largely unknown
outside them. A symbol is a unique, named data object with several
parts: name, value, function, property list and package. Of these,
value cell and function cell are the most important. Symbols in Lisp
are often used similarly to identifiers in other languages: to hold
value of a variable; however there are many other uses. Normally, when
a symbol is evaluated, its value is returned. Some symbols evaluate to
themselves, for example all symbols in the keyword package are
self-evaluating. Boolean values in Common Lisp are represented by the
self-evaluating symbols T and NIL. Common Lisp has namespaces for
symbols, called 'packages'."
(http://en.wikipedia.org/wiki/Common_Lisp).

The Lisp implementation that MathPiper uses, however, only implements
some of these capabilities. For example, its symbols do not have
package capabilities.

Except that mathpiper is not really lisp but a term rewriting engine with a set of rules implementing a simple CAS. Hence, the meaning of the symbol differs slightly from lisp.

> categories 1 and 3 should
> be marked as immutable to protect the semantics of the standard library.
> Now:
>  1. Make a (global) map symbol->list_of_properties, let's call it
> BuiltinProperties
>  2. Make a function Protect[symbol_IsAtom] which adds Protected as a
> property of given symbol in the BuiltinProperties map.
>  3. Make a function UnProtect[symbol_IsAtom], which removes the Protected
> property (if present) from the properties of the given symbol
>  4. Teach Bind to throw an exception if a symbol to be bound is protected
>  5. Go through the standard library and Protect all the symbols

I agree that the unbound variables/Lisp symbols in category 1 should
be marked as immutable, but I don't agree that the ones in category 3
should be.

Perhaps it's just me, but I find the ability to assign Cos := 2 weird.

 

Most versions of Lisp solve the exact problem we are having with
unbound variables/Lisp symbols by using a "quote" operator (which uses
the single quote ' character). The "quote" operator simply causes the
expression to its immediate right to not be evaluated. Unfortunately,
Yacas never had a "quote" operator added to it so most of the unbound
variables/Lisp symbols in category 3 (which are being used like Lisp
quoted symbols are typically used) are being used unsafely.

The analysis is wrong for a simple reason: CAS is not LISP.

 

The closest things that MathPiper has to a quoted Lisp symbol are
strings and the Hold() function. Most of the unbound variables/Lisp
symbols in category 3 can be made safe by simply placing them in
double quotes.

Another solution is to add a Lisp-like "quote" operator to MathPiper
which is a shortcut for the Hold() function. This operator can then be
used to hold the evaluation of the unbound variables/Lisp symbols that
are in category 3.

In which way this is better than the solution I suggested?

 

I recently added an experimental "quote" operator
to MathPiper and it seems to work fairly well:

Yep, I've noticed that you redefined quote to mean Hold.

 

In> a
Result: a

In> a := 7
Result: 7

In> a
Result: 7

In> 'a
Result: a

In> b := 8
Result: 8

In> 'a + b
Result: a+8

In> a + 'b
Result: b+7

In> '(a + b)
Result: a+b

Hold is tricky. And making it easier to use opens can of worms. But I don't think I can convince you.

Grzesiek

[Sherm Ostrowsky]

Years ago I complained to Ted because MathPiper did not have a mechanism similar to LISP's "Quote".  I like it because you ALWAYS know exactly what it means and what it will do.  I mistrust things that do things behind your back, and try to figure out what you meant.  Quote just does one thing, every time.
Sherm

[Ted Kosan]

Grzesiek wrote:

> Except that mathpiper is not really lisp but a term rewriting engine with a
> set of rules implementing a simple CAS. Hence, the meaning of the symbol
> differs slightly from lisp.

<...>

> The analysis is wrong for a simple reason: CAS is not LISP.

MathPiper is an M-Lisp which means it is a Lisp that uses an infix
syntax. Lisps are especially good for implementing DSLs (Domain
Specific Languages) and the rules in MathPiper are implemented as a
DSL. DSL-based Lisp applications consist of both Lisp code and DSL
code. Most (probably all) of the symbols that are in category 3 are
used in the Lisp parts of the scripts for programming-oriented things
like passing names of variables to functions.

I have looked further into how the symbols in category 2 are used and
it turns out that most of them (probably all of them) are also used in
the Lisp parts of the scripts for programming-oriented purposes.

So, this specific problem is a Lisp problem, not a CAS problem.

>> The closest things that MathPiper has to a quoted Lisp symbol are
>> strings and the Hold() function. Most of the unbound variables/Lisp
>> symbols in category 3 can be made safe by simply placing them in
>> double quotes.
>>
>> Another solution is to add a Lisp-like "quote" operator to MathPiper
>> which is a shortcut for the Hold() function. This operator can then be
>> used to hold the evaluation of the unbound variables/Lisp symbols that
>> are in category 3.
>
> In which way this is better than the solution I suggested?

The double quotes solution is one that is already heavily used in the
scripts to pass names to functions and it works well. It is simpler
than performing lookups in a map and there is no need to call a
function like Protect() before a symbol can be used.

For the quoted Lisp symbol solution, MathPiper is a Lisp, the problems
we are having are in the Lisp parts of the scripts, and this solution
would simply be applying the standard techniques that have been used
for the past half century to solve this type of problem.

> Hold is tricky. And making it easier to use opens can of worms. But I don't
> think I can convince you.

Do you know how to program in Lisp? If not, I recommend reading a book
called "Land of Lisp":

http://landoflisp.com/

This is the best introduction to programming in Lisp book that I have
read so far.

Ted

[grzesiek]

Hi,

I know Lisp. And I think that over 40 issues I was able to solve suggests that I know how 

mathpiper works. Actually, for one of the projects I'm working on I wrote quite a lot of 

advanced mathpiper code. Anyway, I'm not going to argue. Your project is your castle.

Grzesiek