1
$\begingroup$

Is it possible to create a some programming language compiler that will perform the composition of primitive functions with optimization?

In fact, the maximum possible optimization in the context of function composition.
In this case, primitive means that the code consists only of while, if, break, continue statements, assignment, standard mathematical operations and functions.

Example 1. x = sqrt(x * x)x = abs(x)
Example 2. filter(filter(list, |x| % 2 == 0), |x| > 2)filter(list, |x| % 2 == 0 && |x| > 2). One list traversal instead of two.
Example 3.

for i in [0:10:1]: # from 0 to 10, step = 1
    first_array[i] = i
for i in [0:10:1]: # from 0 to 10, step = 1
    second_array[i] = first_array[i] + 1
for i in [0:10:2]: # from 0 to 10, step = 2
    third_array[i] = first_array[i] * second_array[i] * input(i)

for i in [0:10:2]: # from 0 to 10, step = 2
    third_array[i] = i * (i + 1) * input(i)  

Update
The goal is to reduce the memory overhead (in fact, the array ceases to be an array and exactly the elements used in it are used for intended purpose) and time (predictable values are calculated in advance).
Output code must satisfy certain correctness criteria, e.g., must compute some particular function.

There are inputs that limit the optimization. But everything else should be optimized at compile time as much as possible.

$\endgroup$
2
  • $\begingroup$ Is there any data type for which x = sqrt(x * x) holds true for all possible values of x? Because of potential overflow during squaring with finite data types, that would not typically be the case. Over the reals the transformation also does not hold when x is negative, as sqrt (x*x) will return a positive result. $\endgroup$
    – njuffa
    Oct 6, 2022 at 19:08
  • $\begingroup$ @njuffa You're right! The programming language is supposed to be an expression language. Let's say lazy evaluation. And the optimization produces equivalent expressions (with the smallest number of operations, etc). $\endgroup$ Oct 6, 2022 at 19:40

1 Answer 1

2
$\begingroup$

This is a very broad topic. You are basically asking about program optimization, which is an entire subfield/topic area within compilers. There are dozens of books and research conferences dedicated to the subject. It is a hard problem. Most solutions are focused on a specific subset of the problem or particular special cases.

Much of the work that I have seen has focused on machine language rather than high-level code, perhaps because the semantics and performance model is easier to specify. Much of the work I've seen focuses on time or the size of the code, rather than the runtime memory usage, because runtime memory usage is challenging to automatically reason about, especially without knowing the workload that the code must handle (e.g., the distribution of inputs to the code).

You might be interested in superoptimization, which does a sort of brute-force search over possible programs, program synthesis, which attempts to construct code that achieves a desired function, and automatic loop vectorization, which converts iterative loops to a form that can be implemented more efficiently.

$\endgroup$
2
  • $\begingroup$ Thanks for the good answer. Initially, I had a desire to create a tool that would translate code from primitive operations into LLVM intermediate code in the most optimized way. For example, the tool would precompute values for variables and arrays that are not directly related to the source data, and perhaps, as for an expression language, would substitute expressions in those places where it is supposed to depend on the input data. And the tool would detect the composition of functions and optimize it too. $\endgroup$ Oct 7, 2022 at 5:56
  • 1
    $\begingroup$ @user51515151, that sounds like a challenging project, but hopefully I've given you some starting points that you can use to learn more about the state of the art and what has been studied so far! $\endgroup$
    – D.W.
    Oct 10, 2022 at 22:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.