For those of you new to this blog, my name is Christopher Diggins, and I am a principal developer on 3ds Max. I work at Autodesk out of Montreal, Canada, and I have been fascinated with programming language implementation and design for 20 years.
The last couple of years have been a real high point in my career, because I was being paid to design and implement a commerical programming language! The result was a functional visual programming language built into Autodesk 3ds Max 2016 called "Max Creation Graph" or MCG for short.
In case you are unfamiliar with 3ds Max, it is a comprehensive 3D modeling, animation, and rendering, solution for games, film, and motion graphics artists. It is also free for students and educators: http://www.autodesk.com/education/free-software/3ds-max.
MCG was initially developed as a way for people to create add-ins for 3ds Max that could create and manipulate geometry. Since geometry is mostly arrays of data (indices, vertices, faces, colors, UVs, selection sets) we decided to make a language that could efficiently manipulate large arrays of data. Because we wanted the language to perform efficiently and predictably in a multi-threaded environment it made sense to take ideas from the functional programming community, and to make a statically typed pure functional language. To be fair, while the core language is pure functional, there are currently a number of stateful objects (e.g. Caches, random rumber generators) and large number of operations with side effects. Interestingly, we have found the pure functional approach to be very rewarding and will continue to work towards making it more pure in the future.
MCG is statically typed. This means that the certain ill-formed programs and computations are detected at compile-time. For example in MCG you cannot add an integer (Int32) to a floating point value (Single), so the type system will detect this at compile-time and reject the program. In addition to the increased assurances that your program is correct, a static type system also enables the compiler to emit more efficient code than when types are checked dynamically at run-time.
In a functional programming language such as MCG functions are first class citizens. They can be dynamically created, passed as function arguments, or returned from functions like any other data type. They can even be stored in arrays. In my opinion, an excellent explantion of functional programming can be found here on the Haskell Wiki.
Graphs as Computation
Computations in MCG are represented visually as directed acyclic graphs. Connections are implicitly directed from left-to-right. Each node in the graph represents a function (called an operator) that is applied to its input values. Each graph rooted at a particular node is an expression that represents the application of the function to its inputs. If the “function” output of a node is used then the value output is an anonymous function (lambda abstraction) representing the graph’s computation.
When capturing a graph’s computation as a function the function arguments are the set of unconnected inputs in the graph.
The order of the arguments are determined by the order in which they appear when searching the graph right to left and top to bottom. The following example is from “OffsetMeshes” which offset each mesh in an array by a vector multiplied by its index in the aray.
For a more detailed tutorial on how function connectors work in MCG, check out Martin Ashton’s excellent two-part function tutorial on the MCG blog.
Creating New Operators with Compounds
New operators in MCG can be created from graphs called “compounds”. A compound graph is saved with the extension “.maxcompound”. Compounds graphs must use an “Output: compound” operator as the terminal node of the graph, and use “Input” nodes (as opposed to “Parameter” nodes used by tools) to represent the graph’s inputs.
When a new compound is created and saved, it will be made available to the user (assuming it validates correctly) when the “Reload Operators” menu option is chosen. The next time 3ds Max starts up its signature will also appear in the help file.
Because MCG has a type-inference engine you don’t have to explicitly specify the output type of compounds, and can even specify “Any” for input parameters. The MCG compiler will attempt to assign the most precise type signature that can be determined will be assigned to the new operator. You can use “Pass-through” operators to help the type engine determine more precise types if needed.
A compound is akin to defining functions in a text-based programming language. Like any programming language MCG is most effective when you break complex algorithms up into small well-defined reusable functions.
MCG Type System
The MCG type system is a subset of the C# type-system. Like C# the type system of MCG supports generic types and typed functions. The core primitive types of the MCG type system are:
- array type (IArray
- function types (Func
, Func , etc.)
- tuple types (Tuple
and Tuple )
- integer numbers (Int32)
- floating point values (Single)
- and Boolean values (Boolean).
There are a number of additional types that have been added to help with geometric processing (such as TriMesh and Vector3) and for interfacing with 3ds Max (e.g INode).
What is displayed in the UI of the operators is actually an approximation of the type (e.g. IArray) but if you read the operator help or hover your mouse over a socket, you can see a more precise representation of the type. The approximation of the type is provided to do a preliminary type checking in the UI. For example the UI won’t let you connect an Int32 to an IArray, but it will let you connect an IArray
Immutable Data and Purity
A key feature of MCG is that it encourages a “pure functional” approach to constructing programs that avoids the usage of side-effects or mutable state. Most data structures in MCG (e.g. arrays, meshes, tuples, vectors) are immutable data structures, meaning that they cannot be changed, you can only construct new versions of these structures. One result of this is that repeated calls to an operator like “SetValue” may create an entire copy of an array and can be inefficient. That said the MCG compiler employs strategies such as lazy evaluation to mitigate the performance issue.
Immutable data structures offer several advantages :
- It is easier to reason about the result of a computation: order of evaluation in inconsequential
- Once a valid data structure has been constructed it cannot “go wrong”. This eliminates a very significant category of software defects.
- Multi-threading becomes most efficient: locks are no longer needed to synchronize access to data elements. Because values never change, there is no possibility of race conditions
- The compiler can perform employ advanced optimization techniques
Lazy Evaluation and Referential Transparency
The MCG compiler may choose a different internal representation of an immutable data structure if a computation always returns the same results given the same inputs and is side effect free. This property is called referential transparency.
An example of an optimization performed by MCG is the “Range” operator which creates an immutable array of N integers from 0 to N-1. It is implemented “lazily” in that it generates values as requested rather than allocating a large block of memory filled with integers.
This is similar to how LINQ (Language Integrated Natural Query) expressions work in C# and the lazy evaluation strategy of Haskell.
Functions with side effects create observable changes in the computation environment. For example they might change the state of a data structure, update the file system, or print something to a console. Examples of operators with side effects in MCG are “Print”, “PseudoRandomFloat”, and “CreateEditableMesh”. In computations with side effects the order of evaluation matter.
Wherever possible you should avoid using functions with side effects, especially in higher-order array operations like “Map”, “Filter”, and “Combine” where there compiler may choose to evaluate the argument in different orders.
Higher Order Functions: Map, Filter, Combine, and Aggregate
Using MCG effectively requires the usage of a special class of higher-order array processing functions. Any function that takes another function as an argument or returns a function as a result, is called a “higher-order function” or HOF for short. Higher order functions are very useful for working with sequences or arrays of data, as they enable you to describe succinctly data transformations without having to use loops or variables.
In MCG arguably the most important array operations are “Map”, “Filter”, "Combine" and “Aggregate”. These are similar to the LINQ operations in C# “Select”, “Where”, "Zip" and “Aggregate”. In some programming languages the "Aggregate" function is called "fold" or "reduce".
The map operation transforms an array into a new array by applying a function to all elements in a source array.
The filter operation applies a predicate function (a function with one argument that returns a boolean) to an array and returns a new array that contains only elements for which the predicate is true.
An aggregate operation applies a binary function to each element in an array with an accumulator value, updating the accumulator value as it goes. The following example computes the sum of an array of values (whether they are Int32, Single, or Vector3).
The combine operator applies a binary function to pairwise elements in two separate arrays to create a new array. The following example computes a dot product of two arrays.
MapWithIndexes and Beyond
With the initial building blocks of “Map”, “Filter”, “Aggregate”, and “Combine”, it is possible to create new operators that are more specialized such as “MapWithIndexes” that acts as a “Map” but takes a binary function which takes the current index as the second input.
Another compound (built using "Map") that is very useful in array processing and that deserves special mention is "SelectByIndex". The "SelectByIndex: operator takes an array of indices and an array of valeus, and returns a new array that contains the values as specified by the indices. Using this you can for example retrieve the vertices of a mesh arranged by face.
Multithreaded Operators: ParallelMap and ParallelCombine
Currentlly there are two operators in MCG that compute results in parallel: ParallelMap and ParallelCombine. These are functionally equivalent to Map and Combine, but are multi-threaded. You should only use them when you have identified a performance bottleneck. It is very important that the function arguments do not call any of the 3ds Max operations, since 3ds Max is not thread-safe. Note that overusing these operators can actually slow down your code.
Debugging MCG Graphs in Visual Studio
MCG tools emit a text output in the same folder as tool (e.g. mytool.txt) that can be loaded in the Visual Studio debugger. If you attach the Visual Studio debugger instance to 3ds Max you can set breakpoints in the text file and inspect the various values.
This text format can be useful for understanding how MCG graphs are converted to byte-code. You’ll notice that variables are declared and the results of the expression are assigned to variables. This allows graphs to be reused in multiple computations and to only be computed once.
Control Flow Operations
MCG is designed primarily for the processing of arrays of data. Many computations in MCG are more easily and efficiently solved when they can be expressed in terms of array operations. There are only a handful of basic control flow operations in MCG, but more can be defined using a bit of ingenuity and functional programming.
The most basic control flow operator is the “If” operator which performs conditional evaluation of one of two inputs depending on whether the condition input is true or false.
The “While” operator is a looping operator takes an initial value and two functions a loop body and a termination function. While the termination function returns false for the current value, the body function is called given the current value as an input. The result of the body function is given to the next iteration of the loop.
The “Repeat” operator is similar to the while function but instead calls the body function a predetermined number of times, and also passes in the current loop index.
As an example of how to build more control flow operators, this example a “RepeatWithoutIndices” compound is defined using the “Repeat” operator.
Notice the usage of the operator “IgnoreSecond” which returns the first input, and does nothing with this argument. This operator is noteworthy (along with ignore first) in that it can also be used to help force the arrangement of inputs and function arguments.
Partial Application (Binding)
A slightly more esoteric higher order function that can be useful in some contexts are the various “Bind” operations (e.g. Bind1Of2) which create functions by binding (fixing) arguments of the function to a particular value. This process is called “Partial Application”. The result is a new function that requires fewer functions than the original.
This advanced example demonstrates a generalized cartesian product function (f(xs, ys), f(xs, ys) … f(xs[n], ys[n]). The “FlatMap” operator applies a function (T -> IArray) to each element of an array (IArray
One area where Bind has become quite useful is dealing with stateful objects like the random number generator. I'll refer you here to another excellent Blog post by Martin Ashton for more detail on this usage of Bind in this context.
Thanks for following me down this long rabbit hole. I hope this article whetted your appetite for functional visual programming and that you consider give MCG a try!
PS: I'm especially interested in hearing from computer science educators interested in using MCG to teach functional or visual programming to their students.