Generating assignments and transforming code inside held forms when generating code

I have been playing with slightly above trivial code manipulations in Mathematica. I thought Mathematica would be great for this kind of work because of rule replacement and expression manipulation, but I have been running in a lot of issues (I am an old lisp programmer and I love manipulating ASTs).

The code generation I am doing is taking DSP expressions like

{ f[x] -> a0 * x + b1 * y z^-1,
  y -> af0 * f[x] + bf1 * f[x] z^-1 + bf2 * f[x] z^-2 }

and transform them to code working on discrete samples by keeping sample delayed values (the values multiplied by z^-n in a ring buffer. The generated code (this is just pseudo code and by no means correct) is of the form:

Module[{ fxRingBuffer = {0, 0}, fxRingBufferIdx = 1,
         yRingBuffer = {0}, yRingBufferIdx = 1 },
   Function[x, 

      Module[{ fx = a0 * x + b1 * yRingBuffer[...], ...},
         fxRingBuffer[[fxRingBufferIdx]] = fx;
         fxRingBufferIdx = Mod[fxRingBufferIdx + 1, Length[fxRingBufferIdx]; 
         ...
         y]]]

Here is an actual example (see the link to the full code at the bottom):

expRecurseMakeFunction[{y → Expand@Simplify[x a0 + y z-1 b]}]

Hold[Module[{yrb$8738 = {0}, yidx$8739 = 1}, Function[x, Module[{ycur$8740},

    Sequence[{ycur$8740 = a0 x + b1 yrb$8738〚1 + Mod[-2 + yidx$8739, 1]〛}];
    Sequence[yrb$8738〚yidx$8739〛 = ycur$8740, yidx$8739 = 1 + Mod[yidx$8739, 1]];
ycur$8740]]]]

The approach I am taking is to use a template like this:

Hold[Module[ringBufferInitialization, 
    Function[x, 
       Module[{sampleUpdates},
          ringBufferUpdates;
          y]]]

and then doing code replacement. The problems I have been having is how to have the code I generate not be evaluated. I have reduced the issues to two toy examples. The first one is generating a list of Set[var, val] assignments to be plugged into ringBufferInitialization and sampleUpdates above. The approach I have taken is to generate MySet forms that are replaced by Set once they are safe inside the toplevel Hold:

generateAssignments[symbols_, values_] :=
  Hold[Module[assignments,
     someBody[]]] //. {
    assignments -> MapThread[MySet, {symbols, values}],
    MySet -> Set
    };

For example:

ClearAll[a, b, c, d];
generateAssignments[{a, b, c, d}, {1, 2, 3, 4}]

Hold[Module[{a = 1, b = 2, c = 3, d = 4}, someBody[]]]

Is there a better way to do this?

The other issue is replacing code inside forms with a Hold* attribute. For example, if any of my functions have the form If[], replacing variable access with the form to access the ring buffers won't evaluate properly and cause problems. Here my solution is really half-baked, as I just replace my If[] blocks with Piecewise[], which worked for my usecase. Again a toy example:

useLookupTable[body_, symbolMap_] :=
 body /. lookupForm[a_, idx_] :> symbolMap[a][[idx]]


useLookupTable[Hold[If[a > 1, lookupForm[b, 23], lookupForm[c, 24]]],
 <|a -> aLookup, b -> bLookup|>]

Hold[If[a > 1, <|a -> aLookup, b -> bLookup|>[b][[
   23]], <|a -> aLookup, b -> bLookup|>[c][[24]]]]

I was looking forward to manipulating my AST, but fighting the evaluation order was pretty frustrating, and I feel like I am missing some general mechanism (like the lisp quasiquote + splicing reader macros) to handle this case.

Here is a link to the (very hacky...) full code: wavefolder DSP analysis

Edit:

Here is an approach using Inactive which seems nice:

generateAssignments[symbols_, values_] :=
  Hold[Module[assignments,
      Print[a, b, c, d]]] //. {
     assignments -> MapThread[Inactive[Set], {symbols, values}]
     } // Activate;

Answer

I think, your question is as much about techniques of evaluation control, as it is about code generation. I will show several different methods to achieve the first result you asked for, which would illustrate different approaches and techniques of evaluation control.

Working with unevaluated parts

You can, if you want to, work with parts of your expression, carefully avoiding evaluation leaks. This method is perhaps one of the most difficult and least economical, since it requires a good knowledge of evaluation control, and even then can be tedious and error-prone, if one doesn't stay really focused.

I will first show the solution step by step, and then assemble it into a function. We will start with the lists of variables and values, but first let us give some of the variables some global values, to test that our solution will not capture global bindings:

ClearAll[a, b, c, d];
a = 10;
b = 20;
{{a, b, c, d}, {1, 2, 3, 4}}

(* {{10, 20, c, d}, {1, 2, 3, 4}} *)

The idiom with MapThread that you suggested is a good one, and we will use it. But not with Set directly. We could use a temporary wrapper, and replace it with Set afterwards, but I will pick a different road. Here is what we would like to do:

MapThread[Hold[#1 = #2] &, {{a, b, c, d}, {1, 2, 3, 4}}]


(* {Hold[10 = 1], Hold[20 = 2], Hold[c = 3], Hold[d = 4]} *)

But this doesn't work. The first step in the right direction will be to insert Unevaluated:

MapThread[Hold[#1 = #2] &, Unevaluated@{{a, b, c, d}, {1, 2, 3, 4}}]

(* {Hold[10 = 1], Hold[20 = 2], Hold[c = 3], Hold[d = 4]} *)

This, however, is not good enough. The premature evaluation happens also in Function during the parameter-passing stage, and thus we need this:

step1 = MapThread[
  Function[Null, Hold[#1 = #2], HoldAll], 

  Unevaluated @ {{a, b, c, d}, {1, 2, 3, 4}}
]

(* {Hold[a = 1], Hold[b = 2], Hold[c = 3], Hold[d = 4]} *)

We are good now, but what we need is we need is single Hold around an assignment list, while we have a List of assignments each wrapped in individual Hold. The useful trick here is to use Thread[#, Hold]&, so that:

step2 = Thread[#, Hold] &@step1

(* Hold[{a = 1, b = 2, c = 3, d = 4}] *)

This is closer to what we need, but now we want to wrap Module around the variable / assignment list, and get it into Hold. One of the simplest ways to do this is by using rules, which would be a version of a so-called injector pattern:

step3 = Replace[step2, Hold[a_List] :> Hold[Module[a, someBody[]]]]

(* Hold[Module[{a = 1, b = 2, c = 3, d = 4}, someBody[]]] *)

which is the final result.

As a function, the resulting code would look like this:

ClearAll[genMT];
SetAttributes[genMT, HoldAll];
genMT[vars : {___Symbol}, vals_List] :=

  Composition[
    Replace[Hold[a_List] :> Hold[Module[a, someBody[]]]],
    Thread[#, Hold] &
  ] @ MapThread[
    Function[Null, Hold[#1 = #2], HoldAll],
    Unevaluated @ {vars, vals}
  ]

Where I used an operator form for Replace. So, for example, we have

genMT[{a, b, c, d}, {1, 2, 3, 4}]


(* Hold[Module[{a = 1, b = 2, c = 3, d = 4}, someBody[]]] *)

Note that this method is hard. We had to use several advanced techniques (evaluation control, a trick with Thread, injector pattern) in combination. I have shown this method to illustrate the "brute-force" approach, which is certainly possible, but is not the most economical or elegant one. One reason why this approach is hard is that we don't use rules and pattern-matching to the full extent.

Using holding symbolic containers for expression transformations

There is an alternative way to build an expression we need. I frequently find it more convenient than other methods, since it often gives you more control, and makes it easier to control evaluation.

The method is to replace iteration (where it is necessary) with recursion, and use symbolic containers with Hold* attributes to transform unevaluated expressions into suitable form. For the case at hand, it may look like this:

ClearAll[a, b, c, d, gen];
SetAttributes[gen, HoldAll];
gen[vars : {___Symbol}, vals_List] := gen[{}, vars, vals];

gen[{a___}, {v_, rvars___}, {val_, rvals___}] :=
  gen[{a, Set[v, val]}, {rvars}, {rvals}];
gen[a_List, {}, {}] := Hold[Module[a, someBody[]]]; 

We can test:

a = 1;
b = 2;
gen[{a, b, c, d}, {1, 2, 3, 4}]

(* Hold[Module[{a = 1, b = 2, c = 3, d = 4}, someBody[]]] *)

The way this works is that gen function gradually picks elements from lists of variable names and values and accumulates the assignments built out of them. When the lists are exhausted, we obtain a list of assignments in an unevaluated form, and can then generate the code we need, straightforwardly.

Using Block trick

The method I will describe here is completely different. It is based on the ability of Block to make (almost) any symbol "forget" its definitions temporarily. This may be used to non-trivially change the evaluation order. For the case at hand, it will be one of the most economical methods.

Here is the code:

ClearAll[genB];
SetAttributes[genB, HoldAll];
genB[{vars___Symbol}, vals_List] :=
  Block[{vars, Set, Module, Hold},
    SetAttributes[Module, HoldRest];

    Hold[Module[MapThread[Set, {{vars}, vals}], someBody[]]]
  ]

The way this works is that it temporarily switches off the standard behavior of Set, Module, and Hold, making them just symbolic wrappers during the evaluation of the body of the Block. This is what we need here for code generation. I had to attach a temporary HoldRest to Module inside Block, so that the body of the Module (someBody[]) is kept unevaluated.

We can test:

genB[{a, b, c, d}, {1, 2, 3, 4}]

(* Hold[Module[{a = 1, b = 2, c = 3, d = 4}, someBody[]]] *)

More advanced techniques

One can base more formal, universal and advanced techniques on methods I have described above, by generalizing and automating them to fit one's needs.

For example, some time ago I've developed code generator based on the generalized Block trick used above. The seriously simplified version of this technique I posted here, and with the help of the FrozenCodeEval function defined there, the solution to your problem becomes trivial:

FrozenCodeEval[
  Hold[Module[MapThread[Set, {{a, b, c, d}, {1, 2, 3, 4}}], someBody[]]],
  {MapThread}
]

(* Hold[Module[{a = 1, b = 2, c = 3, d = 4}, someBody[]]] *)

basically, here you just tell FrozenCodeEval, which heads should evaluate (in this case, only MapThread), and all the rest are kept "frozen". This technique I have also illustrated (among some others) in this answer.

Another possible (but IMO somewhat less powerful) technique is to use rules. I have illustrated this technique in this answer.

Yet another technique can be based on generalizing the holding symbolic container approach I described above. One good example of this approach is the LetL macro (nested With replacement), which is described in this answer, and particularly its more complex extension. This method is the one I've preferred recently.

One can also base code generation on introducing several (many) inert heads (like mySet), and replacing them with some "actual" heads (like Set) at the end, after the code has been generated. This was one of your original suggestions, and is certainly also a possibility.

Finally, one may implement a macro system, which would provide macros in a way similar to Lisp. However, that would require introducing read-time, which currently sort-of exists (parsing code to expressions), but can't really be used much. This is possible to do if one implements an alternative code loader, that would parse code to symbolic expression and give the user access to that parsed code before actually evaluating it.

Why I think that Inactive is in general not an answer

This is certainly an opinionated topic, but I personally did not see (almost) any case where Inactive would solve a problem of evaluation control (outside math-related functionality), in a way that would be simpler than other means of evaluation control.

From the viewpoint of evaluation control, the problem of Inactive is that while it inactivates a given head, it does not hold the arguments of that head, so they can freely evaluate. And the effort needed to prevent them from doing so will most of the time invalidate all the benefits of using Inactivate, as compared to Hold, Unevaluated etc.

For example, in our case (taking your code):

Hold[Module[assignments, Print[a, b, c, d]]] //. {
  assignments -> MapThread[Inactive[Set], {{a, b, c, d}, {1, 2, 3, 4}}

]} // Activate

(* Hold[Module[{10 = 1, 20 = 2, c = 3, d = 4}, Print[a, b, c, d]]] *)

shows that the global bindings to a and b were picked up in this method. And avoiding that will make the code no less complex than the first alternative I have shown above.

Summary

There exist several (many) techniques, allowing one to dynamically generate Mathematica code. The ones I have illustrated are based on

• Direct manipulations with unevaluated parts of expressions


• Using symbolic holding containers for expression transformations


• Using Block trick

One can come up with more advanced / general / universal frameworks for code generation. The ones I mentioned are based on

• Block trick (code "freezing")


• Symbolic holding containers


• Repeated rule application to held expressions


• Inert intermediate (temporary) heads


• (Read-time) macros

Which one to use depends on the case. For simple cases, some of the simpler techniques may be just enough. If you need to routinely generate code, you may be better off with some heavier but more general and systematic approach.