How should a program make a function out of a symbolic expression?

[Stephen Tashi]

TL;DR Summary

How should a computer program make a function out of a symbolic expression that is not known before the program executes?

Suppose a program computes or reads-in a symbolic mathematical expression like $2x^2 - xy + y$. What's an effective way to cause the program to implement the expression as a function (e.g. implement $f(x,y) = 2x^2 - xy + y$) when the programmer doesn't know in advance what the expression will be?

It would be nice to find a way it to implement the function so it runs (as efficiently) as if the programmer had known he expression in advance and coded and compiled it in the normal way.

I've deliberately not mentioned a specific computer language. I'd be interested in how different languages approach this task.

If the programmer knew "the general form" of the expression in advance (e.g. $Ax^2 + Bxy + Cy$) then the function could be coded in advance "by hand" and implemented by having he program set the appropriate values of the constants. However, suppose the programmer doesn't have such specific information.

 

[anorlunda]

It sounds like you are asking about symbolic mathematics.

This Wikipedia article may serve to introduce you to the subject. If you want more, follow the links to references at the bottom of the article.

https://en.wikipedia.org/wiki/Computer_algebra

 

[FactChecker]

That would require a scripting language that allows the evaluation of a string. Both Python and Perl have an eval(string) function that will execute the string as though it is code. R has a parse function. I have never used the Python or R functions that way, but I have used the Perl eval several times.

 

[pbuk]

https://en.wikipedia.org/wiki/Computer_algebra

In some languages there are libraries already available that avoid reinventing wheels such as Math.js which is used by a number of online calculators.

Both Python and Perl have an eval(string) function that will execute the string as though it is code. R has a parse function. I have never used the Python or R functions that way, but I have used the Perl eval several times.

But eval is evil!

 

[FactChecker]

But eval is evil!

It has never done anything bad to me. When you need it, it is good.

 

[S.G. Janssens]

It sounds like you are asking about symbolic mathematics.

Continuing along these lines, yes, what the OP asks is a very common task in symbolic computation. For instance, in Maple this is accomplished using the unapply functional operator. For the given example, you could do

foo := 2*x^2-x*y+y:
bar := exp(foo)*sin(x*z):
f := unapply(foo,[x,y]);
g := unapply(bar,[x,y,z]);

In symbolic computation, expressions are typically stored in trees, rather than in strings. Some background about this is provided in this section of the SymPy tutorial.

 

[Baluncore]

Write code that inserts the expression into the main program source code.
That then compiles and runs that modified source.

 

[Mark44]

Continuing along these lines, yes, what the OP asks is a very common task in symbolic computation. For instance, in Maple this is accomplished using the unapply functional operator. For the given example, you could do

foo := 2*x^2-x*y+y:
bar := exp(foo)*sin(x*z):
f := unapply(foo,[x,y]);
g := unapply(bar,[x,y,z]);

I don't think this is relevant to what the OP is asking. Since the expression isn't known before run time, it must be entered by the user or taken as input from a file, etc. A program would need to parse an input string in order to create some expression that could be evaluated by the program.

 

[Stephen Tashi]

That would require a scripting language that allows the evaluation of a string. Both Python and Perl have an eval(string) function that will execute the string as though it is code.

Yes, that would one way of doing it. If code is only executed by an interpreter then I suppose executing a function defined by a string variable would be as (in)efficient as executing a function defined by the (non-variable) strings that the programmer uses to write the program.

I assume that modern interpreted languages let programmers write user defined functions. So I visualize having a long string variable that defines a user defined function $f(x,y)$. After that string is processed then subsequent references to $f(x,y)$ would not need to be a re-interpretation of the entire definition of $f(x,y)$.

I don't know if a similar trick can be done with a compiled language like C++ or Dlang. Once a program begins executing, can a library that it uses be dynamically modified?

 

[anorlunda]

I don't know if a similar trick can be done with a compiled language like C++ or Dlang. Once a program begins executing, can a library that it uses be dynamically modified?

If the program makes use of a symbolic math library, yes.

Programs like Mathematica and Wolfram Alpha can be written in C++, or any other compiled language. They handle user supplied strings that represent math functions.

 

[FactChecker]

Yes, that would one way of doing it. If code is only executed by an interpreter then I suppose executing a function defined by a string variable would be as (in)efficient as executing a function defined by the (non-variable) strings that the programmer uses to write the program.

I assume that modern interpreted languages let programmers write user defined functions. So I visualize having a long string variable that defines a user defined function $f(x,y)$. After that string is processed then subsequent references to $f(x,y)$ would not need to be a re-interpretation of the entire definition of $f(x,y)$.

Yes. Scripting languages often compile into an intermediate p-language that runs faster after the first interpretation.

I don't know if a similar trick can be done with a compiled language like C++ or Dlang.

No. Nothing like that in either language (see this). I don't know how much speed you are looking for. I usually think that scripting languages can be fast enough for programs that interact with user inputs at the keyboard. The user at a keyboard is not very demanding of speed. For processor-intensive tasks, you should know that C++ is slow and D is even slower. Among scripting languages, Perl is significantly faster than Python and R is very slow.

Once a program begins executing, can a library that it uses be dynamically modified?

Not as far as I know. A dll (dynamically linked library) will only be loaded when it is needed, but the linking process has to locate it and its functions before you can run the program. I have never seen it modified during execution.

 

[Stephen Tashi]

It sounds like you are asking about symbolic mathematics.

Yes, I'm thinking about the design of a computer algebra system (CAS) that facilitates giving he same mathematical object different representations. For example, one representation of a "polynomial" is as a function implemented in the code of the program. Another representation of that same polynomial is as a string of symbols (or tree of symbols or other structure). Possible representations in terms of symbols may vary according to context.

For example, a polynomial in variables $x,y$ might be represented as:

1) A string where the constant coefficients only consist of integers and non-numerical symbols like "2A"
2) A string where the constant coefficients are only integers (in the sense of the integer arithmetic as implemented on the computer).
3) A string where the coefficients are only rational numbers (represented on the computer as pairs of integers).
4)A string wher the coefficients are floating point numbers
5) ... etc.

The operation of multiplying two polynomials is not defined in a default manner because one must say what representation one wants the result to be (e.g. in the case of mutliplying two different representations) and one must define an algorithm for computing the result.

It's tempting to think the ideas of classes, inheritance and function overloading (as implemented in some computer languages) could provide a neat way of handling the ambiguities. But I don't yet see how.

In particular, in the zoo of different representations, I don't see how to include the representation of a polynomial as a function implemented in the code of the program itself.

 

[anorlunda]

I think you need a textbook. Check the references in this article.

https://en.wikipedia.org/wiki/Computer_algebra

Edit: This search shows many textbooks.
https://www.amazon.com/s?k=symbolic+mathematics&ref=nb_sb_noss

 

[Stephen Tashi]

I think you need a textbook.

I already have textbooks. I'm not asking about how to use a CAS or what a CAS is.

 

[FactChecker]

In particular, in the zoo of different representations, I don't see how to include the representation of a polynomial as a function implemented in the code of the program itself.

I would recommend that you do it in two steps. At the heart of the program, you can have it input an array of coefficients. That is simple and basic. You can then make a variety of interfaces that convert different formats to the array of coefficients. There are some parsing tools (strtok and others that I can't remember now) available for C programs that may help. Alternatively, a C program can envoke another language that is better at parsing to get the user input and calculate the polynomial coefficients for the main program. Speed is not an issue there since you would not expect the user to enter several polynomials in a millisecond. It sounds like you want the program to allow a great variety of input formats. That is hard to anticipate. It might be something that a user group would add to very willingly.

 

[pbuk]

I think you need a textbook. Check the references in this article.

https://en.wikipedia.org/wiki/Computer_algebra

Edit: This search shows many textbooks.
https://www.amazon.com/s?k=symbolic+mathematics&ref=nb_sb_noss

I agree with @anorlunda, there is a huge amount of prior art here and the answer to whatever question you may have is out there somewhere, you just need to be more familiar with the context so you are able to frame your questions in a more focussed way. To the lists above I will add WikiPedia's List of computer algebra systems: there are a lot there, but apart from the obvious (Mathematica/Wolfram Alpha and Maple), SymPy and GiNaC are good places to start. Perhaps you could explain what you are looking for in terms of how it is different from what some of these programs do?

I already have textbooks. I'm not asking about how to use a CAS or what a CAS is.

No, but you seem to be asking about how a CAS works (or perhaps stating your assumptions about how you think it should work). The answers you need are in the links above.

 

[Stephen Tashi]

I usually think that scripting languages can be fast enough for programs that interact with user inputs at the keyboard.

I used to think of "interpreted" languages that way, but modern interpreted languages are faster than human reflexes. Do we make a distinction between a "scripted" language versus a language that is defined for an interpreter?

 

[FactChecker]

I used to think of "interpreted" languages that way, but modern interpreted languages are faster than human reflexes. Do we make a distinction between a "scripted" language versus a language that is defined for an interpreter?

I might be sloppy in my terminology. To me they are equivalent. But there might be a difference in that scripting languages can use operating system commands as though they were typing them in a command line. (IMHO, Microsoft hates that idea and would like to get rid of any command-line capability in windows.)