Prototype for replacement formula parser/interpreter/compiler

[LegalizeAdulthood]

I've wanted to replace the bespoke formula parser and associated data structure for some time now. My first presentation to Utah C++ Programmers from 10 years ago was about a parsing framework from the boost libraries called Spirit. The June 2025 Utah C++ Programmers presentation was about JIT Code Generation with AsmJit where I used the successor parsing library Boost.Parser.

I've taken the code I created for that presentation and started extending it to support the full syntax of formulas as used in Iterated Dynamics in my formula-compiler repository on GitHub. This will let me continue to expand the grammar to handle more and more of what constitutes a formula in Iterated Dynamics and deploy it when it supports everything in the current parser. Then I will be able to extend it even further to support parsing of UltraFractal formula files.

This relates to the following open issues:

• Replace home-brew inverse trig functions with Boost.Math implementations #302
• Generalize coloring methods #297
• Import UltraFractal files #291
• Restore the JIT compiler for formulas #290
• Change LastSqr built-in formula variable to lastsqr #261

[LegalizeAdulthood]

I did a bunch of hacking last night -- I don't know why I enjoy hacking on parsers, interpreters and compilers so much :) -- and I implemented all the remaining expression operators at the same precedence as described for type=formula.

So far all values are of type double and not complex. Using complex values will not implement parsing at all, only the interpreter and the JIT compiler. What's interesting is that the SSE2 registers used by the assembly language are wide enough to hold two doubles and can be used to implement something like complex add in a single instruction. If I remember correctly, in one of the Intel manuals they have a SIMD implementation of complex multiply in a few instructions. So extending the compiler to handle complex values doesn't feel like a significant complication.

The remaining syntactical elements to complete the parsing are:

• Recognizing that ; begins a comment that extends to the end of the line (EOL)
• Recognizing that EOL separates statements
• Recognizing the init : iterate , bailout high level structure of formulas
• Recognizing the built-in variables as read only: p1, p2, p3, p4, p5, pixel, lastsqr, rand, pi, e, maxit, scrnmax, scrnpix, whitesq, ismand, center, magxmag, rotskew
• Recognizing the built-in functions: sin, cos, sinh, cosh, cosxx, tan, cotan, tanh, cotanh, sqr, log, exp, abs, conj, real, imag, flip, fn1, fn2, fn3, fn4, srand, asin, acos, asinh, acosh, atan, atanh, sqrt, cabs, floor, ceil, trunc, round, ident, zero, one
• Recognize control flow statements if, elseif, else, endif
• Recognize \ at EOL continues a logical statement line across multiple physical lines
• Use complex values instead of double

I've been implementing the interpreter and compiler for each element as I extend the parser. This keeps everything working without the parser getting ahead of the interpreter or the compiler.

All the details of parsing, interpreting or compiling are isolated with the Formula class with a get/set on named values exposed to be able to validate the values of variables changed via assignment.

[LegalizeAdulthood]

Some questions arose about the formula language as I implemented the operators last night:

1. Can an assignment operator be used in a sub-expression? e.g. is q=4+(w=6)/2 valid syntax? If so, what are the values of q and w afterwards?
2. Do the logical operators && and || have "short-circuit" behavior like they do in C/C++?

For my implementation:

1. This is valid syntax and results in q=7 and w=6.
2. They do and the short-circuit behavior means that e is unevaluated in the expressions false && e and true || e. No assignment expressions in e change variables, no values in the expression e are computed.

I will need to compare against the existing implementation to find out if this is change in behavior. If the behavior I've implemented isn't the existing behavior, I would consider that a bug and not something with which I need to maintain compatibility.

[LegalizeAdulthood]

This is proceeding nicely. All that remains is to implement the complex valued functions. At this point, the new function parser and compiler will certainly make it into 2.0 and maybe 1.3.

[LegalizeAdulthood]

1. Can an assignment operator be used in a sub-expression? e.g. is q=4+(w=6)/2 valid syntax?

This is not allowed by the legacy formula compiler, but I see no reason to exclude it in the new parser.

2. Do the logical operators && and || have "short-circuit" behavior like they do in C/C++?

Based on the existing parser interpreter, the answer is no.

[PaulTheLionHeart]

Once this is fully working, the next major challenge is to convert "normal" fractals into perturbation code to help gain the speed that it offers at high precision. Is this possible? has anyone tried it? It wouldn't be too difficult for polynomials, but trig functions would be very difficult. Just a thought.

[LegalizeAdulthood]

Perturbation implementations for the few fractal types that support bignum would certainly be helpful.

The existing formula type doesn't support arbitrary precision so that would be an extension.

[PaulTheLionHeart]

Will this new parser be easily to upgrade to double-double, quad-double and arbitrary precision? This would be a real bonus as the Fractint parser ran out of steam at about 10^14. It might be worth looking at the class structure for the variables.

ManpWIN uses the following structure for the parser variables:

struct Arg { Complex d; DDComplex dd; QDComplex qd; };
BigComplex can easily be added once the MPFR routines are written.

[LegalizeAdulthood]

The code that I've written has two execution paths: an interpreter and an x64 SSE2 compiler. It wouldn't be too hard to enhance the interpreter to handle other arithmetic types. Obviously it's more work to support that in the compiler path.

[PaulTheLionHeart]

How does the compiler work? Does it compile the interpreted code in real time so the fractal runs at native speed?

[LegalizeAdulthood]

How does the compiler work?

I'm using a library to emit x64 assembly code. I did a Utah C++ Programmers presentation on it last Wednesday, see this video "JIT Code Generation with AsmJit".

For example to compile |z|, I do this code:

if (m_op == '|') // modulus operator |x + yi| returns x^2 + y^2
{
    asmjit::x86::Xmm operand{comp.newXmm()};
    if (!m_operand->compile(comp, state, operand))
    {
        return false;
    }
    comp.mulpd(operand, operand);     // op *= op           [x^2, y^2]
    comp.xorpd(result, result);       // result = 0         [0.0, 0.0]
    comp.movsd(result, operand);      // result.x = op.x    [x^2, 0.0]
    comp.shufpd(operand, operand, 1); // op = op.yx         [y^2, x^2]
    comp.addsd(result, operand);      // result.x += op.x   [x^2 + y^2, 0.0]
    return true;
}

This is using SSE2 instructions where a complex number is held as two doubles in a single 128-bit wide register.

AsmJIt is making it really easy to emit assembly code at runtime into a chunk of memory that I can then use as a function pointer can call it from C++. The downside, of course, is that it is CPU specific, so this won't work on an ARM CPU for instance. That's why I also have the interpreter path. Even though my interpreter is really stupid, It might still be faster than the existing interpreter in Id. It'll be interesting to benchmark the two implementations on an image and see which is faster.

[PaulTheLionHeart]

Wow This is impressive. Is there a way to generate "generic" code that will operate on all Intel/AMD versions of processor?

We can add the other arithmetic types once this works. This is exciting.

[LegalizeAdulthood]

Is there a way to generate "generic" code that will operate on all Intel/AMD versions of processor?

SSE2 extensions were released in 2000, so 25 years ago :), so I think it's safe to assume SSE2. So this code is already generic Intel/AMD 64-bit assembly code at this point.

AsmJit lets you query the CPU features available so that you can emit different code for what's available on the CPU at runtime. If I were to use newer SIMD vector extensions like AVX10 (from 2023) or AVX-512 (from 2013) I could do runtime checks to see if those are available and fall back to SSE2. However, since the existing fractal engine isn't SIMD aware, there's not much benefit to using something past SSE2.

We can add the other arithmetic types once this works. This is exciting.

Yeah, getting the parser working and the assembly code emitted with AsmJit is pretty fun to work on.

That changes if DD or QD support is added because a DD complex then requires 4 doubles, meaning you need 256 bits instead of 128. That would require the AVX instruction set extensions, which provide 256-bit registers (so-called YMM registers) that can hold 4 64-bit doubles. AVX was introduced around 2011, so about 15 years ago :), still a pretty safe bet for any modern machine to have baseline support.

[LegalizeAdulthood]

Another benefit of the parser replacement is that it would no longer be necessary to "hand optimize" out constant subexpressions in your iteration section into the initialization section by introducing new variables. It should be a simple matter of identifying constant subexpressions in the iteration section and automatically create new variables to compute those expressions in the initialization section.

Honestly, I never quite understood the data structure used by the existing parser. To dig deeper into some of the formula related bugs I would need to reverse engineer it. Since I wanted to replace it anyway, as listed on the roadmap for Id 4.0, integrating this version into the code will tick off that item.

It will also be easier to do things like introduce more datatypes (bool, int, hypercomplex) and so-on as well as looping control structures (for, while, do) and eventually classes to get full compatibility with UltraFractal formula files.

This new parser is really going to be a big step forward.

[PaulTheLionHeart]

That's great. We will have a world-class program. Does UltraFractal compile as well as interpret fractal code or will this make Id a forerunner in the field?

[LegalizeAdulthood]

Does UltraFractal compile as well as interpret fractal code

I'd have to look through their documentation to see if they say; it at least has an interpreter. UltraFractal is a closed source commercial program, so I don't have access to the source code to be able to say for sure.

As far as other open source programs go, I don't believe I've seen any of them do just-in-time compilation and many don't have formula interpreters, either.

Some of them might do just-in-time compilation to the GPU. Really GPU acceleration of formulas is going to be a huge win, but that involves using CUDA and OpenGL, so that's slated until after I get the wxWidgets port completed.

[PaulTheLionHeart]

Id then becomes a truly revolutionary program. Well done.