Message Boards Message Boards

17
|
17994 Views
|
9 Replies
|
25 Total Likes
View groups...
Share
Share this post:

Metaprogramming in Wolfram Language

NOTE: Please see the original version of this post HERE. Cross-posted here per suggestion of Vitaliy Kaurov

Also note: This post has been reposted verbatim, and as such is rather dated. While I believe that it is still mostly accurate, it does not necessarily fully reflect my current views on the subject matter. In particular, a number of newer internal projects have been using metaprogramming techniques in ways not fully reflected here.


What this answer is and is not

To avoid some confusion and misunderstanding, let me state right away what is the intended status of this answer.

This answer is not

  • A tutorial to the subject
  • A systematic, or complete, introduction to the subject
  • An authoritative answer putting the final word on the subject

This answer hopefully is

  • An (subjective!) overview of various meta-programming techniques in Mathematica, in the way they are known to me. I want to explicitly state that I am not trying to convey any kind of the "common wisdom" here, since the answer is largely based on my own experiences, and I have not seen an overwhelming number of meta-programming examples in Mathematica-related resources I had a chance to get acquainted with (so I may have no idea what the common wisdom is :)).
  • A collection of (hopefully relevant) links with some minimal explanations, which would allow the reader to see some examples and applications of metaprogramming in Mathematica, or at least examples of what I consider meta-programming in Mathematica.
  • A possible stub for some future answers, so that this larger one could be eventually rewritten and/or split into more focused and narrow ones, as the interest towards some particular forms of metaprogramming in Mathematica is being developed in our community.

Preamble

Ok, let me give it a shot. I'll start by claiming that Mathematica is very well suited for meta-programming, and one can write much more powerful programs in Mathematica by utilizing it. However, while it allows for very interesting and powerful meta-programming techniques, it does not IMO provide a convenient layer of tools to make these techniques more standard and effortless. Particularly painful is the evaluation control (preventing pieces of code from premature evaluation), because of the absence of the true quotation mechanism (here I will disagree with some other answers), the infinite evaluation model of Mathematica, and a quite complex core evaluator.

Enumerating some meta-programming techniques

There are several forms of meta-programming, so let me give a partial list first, and discuss afterwards

  • Introspection-based metaprogramming
  • Reflection-based metaprogramming (like in say, Java)
  • Run-time code generation
  • Macros (like in Lisp)
  • DSL (domain-specific-language) creation
  • ...?

In addition to these, Mathematica has its own meta-programming devices, such as rule-based metaprogramming and the Block-related techniques.

Introspection

Mathematica is IMO very strong here. There are a couple of reasons for this:

  • Homoiconic language (programs written in own data structures - Mathematica expressions. This is code-as-data paradigm, like Lisp which uses lists for this)

  • One can access global definitions for symbols stored in OwnValues, DownValues, SubValues, UpVaulues, etc, and various other global properties, programmatically.

  • Rule-based destructuring techniques (using Cases etc) seriously simplify many introspection-related operations

  • Mathematica code is "over-transparent" - even pure functions are expressions, available to introspection and destructuring, rather than black boxes. This has its downsides (for example, making a functional abstraction leaky in Mathematica, see the end of this answer), but it also allows for things like withGlobalFunctions macro from this answer, where global function definitions are expanded inside pure functions (that macro also illustrates other meta-programming techniques).

Automatic dependency tracking

I will give a single simple explicit example of what I mean by introspection here, and supply some references to more involved cases. The following line of code gives all the symbols used to build a given expression expr, kept unevaluated:

Cases[Unevaluated[expr],s_Symbol:>HoldComplete[s],{0,Infinity},Heads->True]

Note that this will work for any Mathematica expression, including a piece of (perhaps unevaluated) Mathematica code.

A good illustration of introspection-based meta-programming is the symbol dependency analysis. I gave it a shot here, where I fully used all of the above-mentioned features (homoiconic language, low-level access to symbol's properties, rule-based destructuring). A simpler but practical application of dependency analysis can be found e.g. in the getDependencies function from this answer, where I do use the dependencies to dynamically construct a set of symbols which are encapsulated (not easily available on the top-level) but whose definitions must be saved during the serialization of the list object being constructed.

Working around some language limitations

Sometimes, introspection-based metaprogramming can be also used to go around certain limitations of the language, or to make the language constructs behave in the way you want while minimally affecting them. Some examples off the top of my head: changing the default behavior of SaveDefinitions option for Manipulate, making patterns to match only children of certain elements, and also two functions from this answer: a function casesShielded which implements a version of Cases that shields certain sub-expressions (matching specific pattern) from the pattern-matcher. and a (rather hacky) function myCases which implements a modified depth-first search, where the head is inspected before the elements (this is not what is happening in standard Cases, which sometimes has unwanted consequences). Yet another example here is the tiny framework I wrote to deal with the leaks of standard lexical scoping mechanism in Mathematica, which can be found here.

Summary

To conclude this section, I think that introspection-based meta-programming is a very useful and powerful technique in Mathematica, and the one that is relatively easy to implement without engaging in a fight with the system. I am also positive that it is possible to factor out the most useful introspection primitives and have a higher-level introspection-based metaprogramming library, and hope such a library will emerge soon.

Reflection - based metaprogramming

This may probably be considered a subset of the introspection-based metaprogramming, but it is particularly powerful for languages which impose more rigid rules on how code is written, particularly OO languages (Java for example). This uniform and rigid structure (e.g. all code is in classes, etc) allows for automatic querying of, for example, the methods called on the object, etc. Mathematica per se is not particularly powerful here, because "too many ways of doing things" are allowed for this to be effective, but one can surely write frameworks and / or DSLs in Mathematica which would benefit from this meta-programming style.

Run-time code generation

This type of meta-programming can be used relatively easily and brings a lot to the table in Mathematica.

Automation and adding convenient syntax

I will give a small example from this answer, where an ability to generate a pure function (closure) at run-time allows us to easily define a version of SQL select with a more friendly Mathematica syntax, and based on the in-memory Mathematica representation of an SQL table as a nested list:

ClearAll[select, where];
SetAttributes[where, HoldAll];
select[table : {colNames_List, rows__List}, where[condition_]] :=
  With[{selF = Apply[Function, Hold[condition] /.
      Dispatch[Thread[colNames -> Thread[Slot[Range[Length[colNames]]]]]]]},
  Select[{rows}, selF @@ # &]];

Please see the aforementioned answer for examples of use. Further developments of these ideas (also based on meta-programming) can be found in this and this discussions.

Making JIT-compiled functions, and using Compile in more flexible ways

An important class of applications of run-time code-generation is in improving the flexibility of Compile. A simple example would be to create a JIT-compiled version of Select, which would compile Select with a custom predicate:

ClearAll[selectJIT];
selectJIT[pred_, listType_] :=
  selectJIT[pred, Verbatim[listType]] = 
    Block[{lst},
     With[{decl = {Prepend[listType, lst]}},
      Compile @@ 
       Hold[decl, Select[lst, pred], CompilationTarget -> "C", 
          RuntimeOptions -> "Speed"]]];

This function actually illustrates several techniques, but let me first show how it is used:

test = RandomInteger[{-25, 25}, {10^6, 2}];
selectJIT[#[[2]] > 0 &, {_Integer, 2}][test] // Short // AbsoluteTiming 
selectJIT[#[[2]] > 0 &, {_Integer, 2}][test] // Short // AbsoluteTiming

(*

 ==> {0.4707032,{{-6,9},{-5,23},{-4,4},{13,3},{-5,7},{19,22},<<489909>>,{11,25},{-6,5},
          {-24,1},{-25,18},{9,19},{13,24}}}

 ==> {0.1250000,{{-6,9},{-5,23},{-4,4},{13,3},{-5,7},{19,22},<<489909>>,{11,25},{-6,5},
          {-24,1},{-25,18},{9,19},{13,24}}}
*)

The second time it was several times faster because the compiled function was memoized. But even including the compilation time, it beats the standard Select here:

Select[test,#[[2]]>0&]//Short//AbsoluteTiming

(*
  ==> {1.6269531,{{-6,9},{-5,23},{-4,4},{13,3},{-5,7},{19,22},<<489909>>,{11,25},{-6,5},
    {-24,1},{-25,18},{9,19},{13,24}}}
*)

The other techniques illustrated here are the use of constructs like Compile@@Hold[...] to fool the variable-renaming scheme (see e.g. this answer for a detailed explanation), and the use of With and replacement rules (pattern-based definitions) as a code-injecting device (this technique is used very commonly). Another example of a very similar nature is here, and yet another, very elegant example is here.

Custom assignment operators and automatic generation of function's definitions

Another class of run-time code-generation techniques (which is somewhat closer to macros in spirit) is to use custom assignment operators, so that you can generate rather complex or large (possibly boilerplate) code from relatively simple specifications. Applications range from relatively simple cases of adding some convenience/ syntactic sugar, such as e.g. here (where we define a custom assignment operator to allow us to use option names directly in code), to somewhat more complex cases like making replacements in definitions at the definition-time, as say in the function lex from this answer (see also the code for a LetL macro below), to quite sophisticated generation of boilerplate code, happening e.g. in JLink behind the scenes (which, for JLink, is a big deal, because this (plus of course the great design of JLink and Java reflection) is the reason why JLink is so much easier to use than Mathlink).

Automating error-handling and generating boilerplate code

Yet another use for run-time code generation (similar to the previous) is to automate error-handling. I discussed one approach to that here, but it does not have to stop there - one can go much further in factoring out (and auto-generating) the boilerplate code from the essential code.

A digression: one general problem with various meta-programming techniques in Mathematica

The problem with this and previous classes of use cases however is the lack of composition: you can not generally define several custom assignment operators and be sure that they will always work correctly in combinations. To do this, one has to write a framework, which would handle composition. While this is possible to do, the development effort can rarely be justified for simple projects. Having a general library for this would be great, provided that this is at all possible. In fact, I will argue that the lack of composibility ("out of the box") is plaguing many potentially great meta-programming techniques in Mathematica, particularly macros.

Note that I don't consider this being a fundamental core language-level problem, since the relevant libraries / frameworks can surely be written. I view it more as a consequence of the extreme generality of Mathematica and it being in a transition from a niche scientific language to a general-purpose one (in terms of its typical uses, not just capabilities), so I am sure this problem has a solution and will eventually be solved.

Proper (macro-like) run-time generation of Mathematica code

A final use case for the run-time code generation I want to mention is, well, run-time Mathematica code generation. This is also similar to macros (as they are understood in Lisp) in spirit, in fact probably the closest to them from all techniques I am describing here. One relatively simple example I discuss here, and a similar approach is described here. A more complex case involving generation of entire packages I used for the real-time cell-based code highlighter described here. There are also more sophisticated techniques of run-time Mathematica code generation - one of which (in a very oversimplified form) I described here

Summary

To summarize this section, I view run-time code generation as another meta-programming technique which is absolutely central to make non-trivial things with Mathematica.

Macros

First, what I mean by macros is probably not what is commonly understood by macros in other languages. Specifically, by macro in Mathematica I will mean a construct which:

  • Manipulates pieces of Mathematica code as data, possibly preventing them from (premature) evaluation
  • Expands code at run-time (not "read-time" or "compile-time", which are not so well defined in Mathematica)

Some simple examples

Here is the simplest macro I know of, which allows one to avoid introducing an intermediate variable in cases when something must be done after the result has been obtained:

SetAttributes[withCodeAfter,HoldRest];
withCodeAfter[before_,after_]:=(after;before)

The point here is that the argument before is computed before being passed in the body of withCodeAfter, therefore evaluating to the result we want, while the code after is being passed unevaluated (due to the HoldRest attribute), and so is evaluated already inside the body of withCodeAfter. Nevertheless, the returned result is the value of before, since it stands at the end.

Even though the above macro is very simple, it illustrates the power of macros, since this kind of code manipulation requires special support from the language and is not present in many languages.

Tools used for writing macros

The main tools used for writing macros are tools of evaluation control, such as

  • Hold*- attributes,
  • Evaluate and Unevaluated
  • code injection using With and / or replacement rules
  • Pure functions with Hold - attributes

Even in the simple example above, 2 of these tools were used (Hold-attribute and replacement rules, the latter hidden a bit by using global replacement rules / definitions). The discussion of the evaluation control constructs proper is outside the scope of the present discussion but a few places you can look at are here and here

Typical classes of macros

Macros can widely range in their purpose. Here are some typical classes

  • Making new scoping constructs or environments (very typical use case)
  • Used in combination with run-time code generation to inject some unevaluated code
  • Used in combination with some dynamic scoping, to execute code in some environments where certain global rules are modified. In this case, the "macro" - part is used to delay the evaluation until the code finds itself in a new environment, so strictly speaking these are rather custom dynamic scoping constructs.

Examples of new scoping constructs / environments

There are plenty of examples of the first type of macros available in the posts on StackOverlflow and here. One of my favorite macros, which I will reproduce here, is the LetL macro which allows consecutive bindings for With scoping construct:

ClearAll[LetL];
SetAttributes[LetL, HoldAll];
LetL /: Verbatim[SetDelayed][lhs_, rhs : HoldPattern[LetL[{__}, _]]] :=
   Block[{With}, Attributes[With] = {HoldAll};
     lhs := Evaluate[rhs]];
LetL[{}, expr_] := expr;
LetL[{head_}, expr_] := With[{head}, expr];
LetL[{head_, tail__}, expr_] := 
  Block[{With}, Attributes[With] = {HoldAll};
    With[{head}, Evaluate[LetL[{tail}, expr]]]];

What it does is to expand a single declaration like LetL[{a=1,b=a+1,c = a+b},a+b+c] into a nested With at run-time, and it also works for function definitions. I described in more fully here (where some subtleties associated with it are also described), and used it extensively e.g. here. A very similar example can be found in this answer. Yet another example I already mentioned - it is the macro withGlobalFunctions from this answer, which expands all generically-defined (via patterns) global functions. The last example I want to include here (although it also is relevant for the third use case) is a macro for performing a code cleanup, discussed here, and I particularly like the version by @WReach, which I will reproduce here:

SetAttributes[CleanUp, HoldAll]
CleanUp[expr_, cleanup_] :=
  Module[{exprFn, result, abort = False, rethrow = True, seq}, 
    exprFn[] := expr;
    result = 
      CheckAbort[
         Catch[Catch[result = exprFn[]; rethrow = False; result], _, 
           seq[##] &], abort = True];
    cleanup;
    If[abort, Abort[]];
    If[rethrow, Throw[result /. seq -> Sequence]];
    result]

It is not fully "bullet-proof", but does a really good job in the majority of cases.

Examples of run-time code generation / new functionality

Actually, many of the above examples also qualify here. I'll add just one more here (in two variations): the abortable table from this answer (I will reproduce the final version here):

ClearAll[abortableTableAlt];
SetAttributes[abortableTableAlt, HoldAll];
abortableTableAlt[expr_, iter : {_Symbol, __} ..] :=
  Module[{indices, indexedRes, sowTag, depth =  Length[Hold[iter]] - 1},
   Hold[iter] /. {sym_Symbol, __} :> sym /. Hold[syms__] :> (indices := {syms});
   indexedRes =  Replace[#, {x_} :> x] &@ Last@Reap[
      CheckAbort[Do[Sow[{expr, indices}, sowTag], iter], Null],sowTag];
   AbortProtect[
      SplitBy[indexedRes, Array[Function[x, #[[2, x]] &], {depth}]][[##,1]] & @@ 
      Table[All, {depth + 1}]
   ]];

(it accepts the same syntax as Table, including the multidimensional case, but returns the partial list of accumulated results in the case of Abort] - see examples of use in the mentioned answer), and its version for a conditional Table, which only adds an element is certain condition is fulfilled - it is described [here. There are of course many other examples in this category.

Examples of dynamic environments

Dynamic environments can be very useful when you want to modify certain global variables or, which is much less trivial, functions, for a particular piece of code, so that the rest of the system remains unaffected. The typical constructs used to achieve this are Block and Internal`InheritedBlock.

The simplest and most familiar dynamic environment is obtained by changing the values of $RecursionLimit and / or $IterationLimit inside a Block. Some examples of use for these are in my answer in the discussion of tail call optimization in Mathematica. For a more complex example, see my suggestion for the recent question on convenient string manipulation. Some more examples can be found in my answer to this question. An example of application of this to profiling can be found here.

Again, there are many more examples, many of which I probably missed here.

Problems with writing macros in Mathematica

To my mind, the main problems with writing and using macros consistently in Mathematica are these:

  • Hard to control evaluation. No real quotation mechanism (Hold and HoldComplete don't count because they create extra wrappers, and Unevaluated does not count since it is not permanent ans is stripped during the evaluation)
  • Macros as described above are expanded from outside to inside. Coupled with the lack of real quotation mechanism, this leads to the absence of true macro composition out of the box. This composition can be achieved, but with some efforts
  • The lack of the real compilation stage (The definition-time does not fully count since most definitions are delayed).

To circumvent these issues, one has to apply various techniques, such as

  • Trott - Strzebonski in-place evaluation technique to evaluate parts of held expressions in-place (see also this answer for some more details on that)
  • A technique which I call (for the lack of a better name) "inverse rule-dressing", which exploits the properties of delayed rule substitution (delayed, plus intrusive), to inject some unevaluated code. I used it in the first solution in this answer, in more complex way in the SavePointers function in this answer, and in a number of other cases. It has also been used very elegantly in this answer.
  • using a custom Hold-like wrapper which is first mapped on (possibly all) parts of an expression, and later removed using rules. Two examples of this techniques are here and here
  • ...

Despite all these techniques being useful, and in total covering most of the needs for macro-writing, the need to use them (often in combinations) and the resulting code complexity shows, to my mind, the serious need for a generic library which would provide simpler means for macro-writing. I would prefer to be able to nest macros and not think about zillion of things that may go wrong because of some unwanted evaluation, but rather about things that really matter (such as variable captures).

Summary

Macros are another very powerful meta-programming technique. While it is possible to write them in Mathematica, it is, as of now, a rather involved undertaking, and composing macros is an even harder task. Because composition in the key, I attribute the fact that macros are not in widespread use in Mathematica programming, to this lack of composition, plus the complexity of writing individual macros. That said, I think this is a very promising direction, and hope that some time soon we will have the tools which would make writing macros a more simple and automatic process.

DSL creation

I won't say almost anything here, except noting that this is entirely possible in Mathematica, and some nice syntax can be added easily via UpValues.

Final remarks

I think that meta-programming is one of the most important and promising directions in the present and future of Mathematica programming. It is also rather complex, and IMO, largely unexplored in Mathematica still. I hope that this justifies this post being so long.

I tried to summarize various approaches to meta-programming in Mathematica, which I am aware of, and give references to examples of these approaches, so that the reader can look for him/herself. Since meta-programming is a complex topic, I did not attempt to write a tutorial, but rather tried to summarize various experiences of myself and others to produce a kind of a reference.

One may notice that the references are dominated by the code I wrote. One reason for that is that I am a heavy user of meta-programming in Mathematica. Another reason is that everyone remembers own code the most. I have to apologize for not including some other references which did not come to my mind right away. I invite everyone to edit this post and add more references, which I missed.

POSTED BY: Leonid Shifrin
9 Replies
Posted 1 year ago

I stumbled across this excellent post while searching the following website for a roll-your-own implementation of Lisp in Mathematica:

Make A Lisp

Quite to my surprise, the Wolfram Language was nowhere to be found on the list.

POSTED BY: mma usr

It is possible, yes. As far as I know, a large part (if not all) of the new WL compiler has been written in WL. Also, we wrote the subset-of-WL to SQL compiler mostly in WL, for the new Database Integration project for V12.

I think that symbolic trees representation and transformations are among strong sides of WL. Also, the frontend makes it easy to visualize (parts of) AST, and other relevant data structures. Pattern matching can be a natural tool to work with grammars. So if you are looking at ways to prototype and visualize, then WL is among the best tools available, I think.

One thing you should know is that WL is strongly geared towards immutability, so for best experience, all your data structures (AST, etc.) better be immutable, and stateless. We have used this approach in Database Integration project with very good results, we have zero state in our entire compilation pipeline. But this style of programming needs some time to get used to, unless you are coming from some pure functional languages like Haskell.

POSTED BY: Leonid Shifrin

It this functionality available only in the commercial version, or I can play in online or community distro?

Where can I find intro manuals or tutorials into meta extensions of WL (besides this post)?

POSTED BY: Dmitry Ponyatov

As far as I know, there is no difference between the commercial and other versions in terms of the functionality, the only difference is the licensing.

If you have version 12, both the new compiler and the Database Integration project are parts of it. Finding where they are located is not hard. For example, for Database Integration:

<< Databases`
Lookup[PacletInformation["Databases"], "Location"]

However, both code bases are rather involved, and reading the code is probably not an easy task for someone not familiar well with the internal architecture of the projects.

I am not aware of many resources on meta-programming in WL, particularly on the level of official documentation. You can search for some posts on Mathematica at Stack Exchange.

For dealing specifically with languages and grammars, and actually also for some aspects of metaprogramming, look for posts of Anton Antonov, here on this site, on M SE, and on his blog. He has built a number of tools in this area, and made a number of posts explaining those. There is also a nice chapter on implementing languages in WL, in the book "An introduction to programming with Mathematica" by Wellin, Gaylord and Kamin. They show how to implement a simple graphical language.

POSTED BY: Leonid Shifrin

Is WL suitable as learning workbench for computer languages design?

I don't mean full-functional compiler, but interactive workbench able to visualize internal compiler/interpreter structures, parse BNF-defined grammars, process attribute grammar, etc.

For the first view, WL language itself looks homoiconic itself, so is it possible to use it for compiler frontend implementing, or making functional/dynamic languages engines?

POSTED BY: Dmitry Ponyatov
Posted 7 years ago

Leonid, being a bit of a dummy in this area: Would it be possible for you to give a simple example of what is meta programming in WL, and what is not?

POSTED BY: Hans Milton

Hans,

Metaprogramming is a technique which, as a concept, is rather language-agnostic, as long as the language supports the necessary abstractions to make it easy or possible. For a general description, you can start with the Wikipedia article. In WL, there are a few markers which indicate the use of metaprogramming. To give you a few examples, defining your own scoping construct or inspecting / destructuring some code (written program) will be metaprogramming. Very often, functions which use metaprogramming have one of the Hold - attributes, or otherwise use what is called non-standard evaluation, since they need to prevent some pieces of code from premature evaluation. So, while perhaps not all functions with Hold - attributes can be considered as using metaprogramming, many can.

To give simple examples, some "usual" function like

f[x_]:=x^2

is obviously not using metaprogramming, while, for example, a function which inspects some code and returns a list of all symbols (wrapped in HoldComplete to prevent their possible evaluation), from which that code is built:

ClearAll[getHeldSymbols];
SetAttributes[getHeldSymbols, HoldAllComplete];
getHeldSymbols[expr_]:=Cases[Unevaluated[expr], s_Symbol :> HoldComplete[s], {0, Infinity}, Heads -> True]

does use metaprogramming.

POSTED BY: Leonid Shifrin
Posted 7 years ago

Possibly useful for metaprogramming: VisX software for Wolfram Language.

POSTED BY: Bryan Lettner

enter image description here - Congratulations! This post is now a Staff Pick as distinguished on your profile! Thank you for your wonderful contributions. Please, keep them coming!

POSTED BY: Moderation Team
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract