search

Mathics3 / mathics-core

An open-source Mathematica. This repository contains the Python modules for WL Built-in functions, variables, core primitives, e.g. Symbol, a parser to create Expressions, and an evaluator to execute them.
https://mathics.org
Other
780 stars 45 forks source link

MakeBoxes rules shouldn't follow the standard evaluation process. #573

Open mmatera opened 2 years ago

mmatera commented 2 years ago

Description

MakeBoxes has a special meaning in WL: this function is applied over an expression to produce a BoxExpression. In our current implementation, all the boxing rules are associated with the Built-in definition MakeBoxes as standard downvalues rules. So, something like MakeBoxes[f[x]] will apply all the downvalues rules until one matches.

In WMA, the behavior is different: when the expression MakeBoxes[f[x]] is evaluated, the kernel applies first the available format rules for f[x], and afterwards looks for rules for the resulting formatted expression.

Expected behavior

Let's consider the following example, run on WMA:

(*Defines a rule for `MyForm`*)
In[1]:= MakeBoxes[MyForm[F[x__]],fmt_]:=RowBox[{MakeBoxes[{x}],"<F", MakeBoxes[fmt]}]                                                                                         

(*Evaluate an expression of that form, and the rule is applied*)
In[2]:= MyForm[F[1,2]]//MakeBoxes                                                                                                                                             

Out[2]= RowBox[{RowBox[{{, RowBox[{1, ,, 2}], }}], <F, StandardForm}]

(*Now a format rule is defined*)
In[3]:= Format[MyForm[F[x__]]]:=Infix[{x},"\\/"]                                                                                                                              

(*If this would follow the standard evaluation algorithm, the output would be the same
that in %2*)

In[4]:= MyForm[F[1,2]]//MakeBoxes                                                                                                                                             
Out[4]= InterpretationBox[RowBox[{1, "\\/", 2}], 1\/2, Editable -> False]

Output Given in Mathics

On the other hand, in Mathics,

(*Defines a rule for `MyForm`*)
In[1]:= MakeBoxes[MyForm[F[x__]],fmt_]:=RowBox[{MakeBoxes[{x}],"<F", MakeBoxes[fmt]}]                                                                                         
Out[1]=None

(*Evaluate an expression of that form, and the rule is applied*)
In[2]:= MyForm[F[1,2]]//MakeBoxes                                                                                                                                             

Out[2]= RowBox[{RowBox[{{, RowBox[{1, ,, 2}], }}], <F, StandardForm}]

(*Now a format rule is defined*)
In[3]:= Format[MyForm[F[x__]]]:=Infix[{x},"\\/"]                                                                                                                              
Out[3]=None
(* Format is not taken into account in Mathics*)

In[4]:= MyForm[F[1,2]]//MakeBoxes                                                                                                                                             
Out[4]= RowBox[{RowBox[{{, RowBox[{1, ,, 2}], }}], <F, StandardForm}]

Possible fix

MakeBoxes rules should be stored as a separated list in the definition object, just like the format rules. Just one rule must be attached to MakeBoxes downvalues

    def apply_general(self, expr, f, evaluation):
         """MakeBoxes[expr_, f_]"""
         return format_element(expr, evaluation, f)

Then, format_element should apply MakeBoxes rules in a similar way than do_format_element do with format rules.

rocky commented 2 years ago

MakeBoxes has a special meaning in WL: this function is applied over an expression to produce a BoxExpression.

I don't quite understand the specialness of "special" here. I suppose, all built-ins have a "special meaning".

So, something like MakeBoxes[f[x]] will apply all the downvalues rules until one matches.

In WMA, the behavior is different: when the expression MakeBoxes[f[x]] is evaluated, the kernel applies first the available format rules for f[x], and afterwards looks for rules for the resulting formatted expression.

The attributes of MakeBoxes in Mathics is HoldAllComplete which if I understand correctly means that MakeBoxes has complete control over the arguments passed to it and none of them are evaluated or expanded beforehand.

Therefore, it would appear that any incorrect behavior that this function currently has, is just a matter of how that function was written, rather than some deep problem in evaluation.

Possible fix MakeBoxes rules should be stored as a separated list in the definition object, just like the format rules.

Let me back up a little bit here. The Wolfram Language is pretty regular; as best as I can tell, the language lends itself to implementation like any other similar symbolic and message oriented interpreter. If something seems "special" when looked at bottom up, it might be that we don't understand the general pattern by which this falls under.

One way to decompose Wolfram Alpha functions to expose there naturalness is to see if we can write them in pure Wolfram Alpha using other functions. If nothing else, that forces us to look for other builtin functions, often lower level, or often with better documented behavior. It forces us to think about this in higher-level WMA concepts and functions, rather than the Mathics Python-specific structures and Python constructs.

It may be that after coming up with a Pure Wolfram Alpha implementation, we may decide to implement a part of it in Python because that is faster. In my view, this is currently the case with Infix operator conversion. We could have created a mapping or table via a function to map operator names into specific unicode values, and have Mathics and read in this Mathics code. Instead, we opted to set up the mapping by efficiently using ujson (when that is available or the standard json loader when it is not).

Another approach to understanding things like what's up with MakeBox that I would like to see done more often is to just ask on https://mathematica.stackexchange.com/ when there are questions we can't answer by looking at documents and that are not obvious. There are a lot of smart people at that site who answer questions.

mmatera commented 2 years ago

MakeBoxes has a special meaning in WL: this function is applied over an expression to produce a BoxExpression.

I don't quite understand the specialness of "special" here. I suppose, all built-ins have a "special meaning".

The standard evaluation algorithm is what we have documented there https://github.com/Mathics3/mathics-core/blob/603125c928eb200803900d33522490daeae979c0/mathics/core/expression.py#L991. What I mean is that applying this sequence of steps, we do not reproduce what MakeBoxes[expr_,fmt] does.

The attributes of MakeBoxes in Mathics is HoldAllComplete which if I understand correctly means that MakeBoxes has complete control over the arguments passed to it and none of them are evaluated or expanded beforehand.

Yes, it could be done, but we want also the implementation to be modular and scalable and that it avoids duplicating code.

Therefore, it would appear that any incorrect behavior that this function currently has, is just a matter of how that function was written, rather than some deep problem in evaluation.

Possible fix MakeBoxes rules should be stored as a separated list in the definition object, just like the format rules.

Let me back up a little bit here. The Wolfram Language is pretty regular; as best as I can tell, the language lends itself to implementation like any other similar symbolic and message oriented interpreter. If something seems "special" when looked at bottom up, it might be that we don't understand the general pattern by which this falls under.

OK. This is why during the last weeks I have been studying and testing what is that pattern in WMA. I do not have experience with the internals of other interpreters/compilers, but now I am in the position of describing mostly how the evaluation of this kind of expression goes, and how to mock it with "crapy code".

One way to decompose Wolfram Alpha functions to expose there naturalness is to see if we can write them in pure Wolfram Alpha using other functions. If nothing else, that forces us to look for other builtin functions, often lower level, or often with better documented behavior. It forces us to think about this in higher-level WMA concepts and functions, rather than the Mathics Python-specific structures and Python constructs.

Wolfram Alpha is a different thing than WL. Focusing on WL, indeed, in WMA, I could emulate most of the Formater/MakeBoxes behavior using WL builtins. But to to that, I would need to have a working ToString and MakeBoxes, so this path leads us to bite our own tails.

It may be that after coming up with a Pure Wolfram Alpha implementation, we may decide to implement a part of it in Python because that is faster. In my view, this is currently the case with Infix operator conversion. We could have created a mapping or table via a function to map operator names into specific unicode values, and have Mathics and read in this Mathics code. Instead, we opted to set up the mapping by efficiently using ujson (when that is available or the standard json loader when it is not).

Again, that approach fails because we are dealing with the basic elements of the language. Provided ToString and StringReplace work, then I could emulate most of the "formatters"/ "renders", but probably in a very inefficient way.

Another approach to understanding things like what's up with MakeBox that I would like to see done more often is to just ask on https://mathematica.stackexchange.com/ when there are questions we can't answer by looking at documents and that are not obvious. There are a lot of smart people at that site who answer questions.

Sure, I am looking there. However, most of the questions and answers are oriented to solve problems using WMA, not developing a new kernel from scratch.

rocky commented 2 years ago

Wolfram Alpha is a different thing than WL. Focusing on WL, indeed, in WMA, I could emulate most of the Formater/MakeBoxes behavior using WL builtins. But to to that, I would need to have a working ToString and MakeBoxes, so this path leads us to bite our own tails.

I mean write MakeBoxes in WL and run on Wolfram Alpha. Then we have something concrete. If that uses ToString, and Mathics doesn't have some needed feature of ToSting in Wolfram Alpha, then adding that feature is where we should start working. Getting ToString that matches WL and WMA in Mathics is easier than writing a Mathics general MakeBox routine.

Sure, I am looking there.

Great! I see for example https://mathematica.stackexchange.com/questions/151488/is-makeboxes-applied-recursively-or-just-at-top-level

I assume you are using TracePrint, right?

Are there others questions or answers that relate to MakeBoxes?

However, most of the questions and answers are oriented to solve problems using WMA, not developing a new kernel from scratch.

From your standpoint, you should not think of the activity right now along the lines of writing a new kernel from scratch. Please leave that to me.

Right now, there are already a fair number of builtin functions which in fact do work pretty much the way they work in Wolfram Alpha. And when they don't, file issues and we will fix them. Some builtin functions like ToString, are more primitive than others so those are easier to fix. And some builtin functions like MakeBoxes are more generic and high level and use these basic built-in functions or invoke functions that use the basic built-in functions

As a by-product of writing things in Wolfram Language (and that runs on Wolfram Alpha), we can more easily identify the more basic and primitive functions, and focus on those first.

I also believe it will make apparent different layers that exist.

rocky commented 2 years ago

Yes, it could be done, but we want also the implementation to be modular and scalable and that it avoids duplicating code.

Absolutely. However have seen here and fear the problem of "premature optimization". I assume it is possible to write modular and scalable code in the Wolfram Language that avoids duplication? So do that. Later we can work on a separate step to see how best to implement that.

rocky commented 2 years ago

I took a look at

https://github.com/Mathics3/mathics-core/blob/603125c928eb200803900d33522490daeae979c0/mathics/core/formatter.py#L179-L187 and I agree with you that MakeBoxes evaluation is a bit different than general evaluation.

Most of the steps listed in https://mathics-development-guide.readthedocs.io/en/latest/extending/code-overview/evaluation.html#detailed-rewrite-apply-eval-process do not have meaning here.

At a high level, if MakeBoxes is given Plus[1, 2] I do not believe it should not be given the opportunity to turn this into 3.

Currently it doesn't because there is the HoldAllComplete attribute which prevents it. Such a generic evaluation process for something so highly customized seems wrong. Recall we have a specialized evaluation for ListExpression via a custom rewrite_apply_eval_step method.

It is stuff like this which causes a lot of overhead and inefficiency in running.

Fortunately, I don't think this is our major source of slowdown - just a minor one. But it is a source of complexity and lack of clarity.

mmatera commented 2 years ago

Regarding this, it was never about speedup the code, but to have a clearer, more modular code, which would be also compatible with WMA.

Regarding the evaluation sequence of MakeBoxes, differently to the way in which we have specialized ListExpression.evaluate, skipping the irrelevant steps, in MakeBoxes the we have a different way to process rules. Actually, MakeBoxes rules are not stores as downvalues / upvalues in WMA (as we do in Mathics) but as FormatValues. Then, these rules are not processed during a regular evaluation, and regular evaluation rules (ownvalues, downvalues, upvalues, subvalues) are not taken into account in formatting (unless the format rule requires a subsequent evaluation).

Regarding

At a high level, if MakeBoxes is given Plus[1, 2] I do not believe it should not be given the opportunity to turn this into 3.

Indeed, if a MakeBoxes rule like this is set:

In[1]:=MakeBoxes[F[x_],fmt_]:=x+1

then 

then

In[2]:= StandardForm[F[2]]

Out[2]//StandardForm= 3