How Sh Works: An Introduction to the Sh Embedded Language
This overview explains how Sh is constructed and why it behaves the way it does. The ideas behind Sh are introduced gradually, using examples that show how a comparable language embedded inside C++ might develop over time. Reading the code samples closely while working through the article is essential.
Sh is a C++ library that functions as a language for programming coprocessors such as Graphics Processing Units (GPUs) directly from within C++ applications. Embedding a language in C++ for a particular purpose is not a new idea; programming language theorists refer to such a language as an embedded domain-specific language, or EDSL. Most other C++ EDSLs rely on template metaprogramming, which uses advanced C++ features to build a language compiled alongside C++. The result can be highly efficient or type-safe code inside C++ programs; the blitz++ library, for instance, lets you express matrix computations in C++ that run very efficiently.
Sh differs from EDSLs like blitz++ in several important ways. Sh does not use template metaprogramming, and Sh programs are compiled at runtime rather than at C++ compile time. Sh programs also need not run on the same processor as the C++ application they are embedded in, though they can.
A First Attempt
So how does Sh work? Imagine reading the paragraphs above and then trying to rewrite Sh with no further knowledge. Suppose the goal is to multiply a C++ variable by an array of a thousand floating point numbers, a tiny example of what Sh can do. After some thought, a first draft might look like this:
- Build a Program object from a text string describing inputs, a variable, an output, and the computation.
- Call compile() to parse that text.
- Declare the C++ arrays and scalar.
- Use set_input, set_variable, and set_output to tie the embedded program's variables to the C++ variables.
- Call execute(1000) to run the program, for example on the GPU, and return results to C++.
This is a start, but not a strong one. There is considerable overhead: the lines binding variables seem superfluous, and sharing variables between the embedded language and C++ would be far better. The compile() function also carries a heavy burden, since it must parse a language defined from scratch, and every new language feature must be implemented by hand. And because we are already writing C++, we would love to use the features we rely on: arrays, functions, classes, inheritance, templates. Implementing all of that would amount to writing a C++ compiler, a workload that makes you want to crawl back into bed.
A Questionable Improvement
Consider how to improve on this. Start with the parsing problem: passing the program as text offers flexibility in syntax, but it is hard to implement and awkward for making variations on the programs being defined. Here is another attempt:
- Create a Program object.
- Add an input, an output, and a variable through program methods.
- Add a computation describing a multiply of the output from the input and the variable.
- Compile the program.
- Attach the C++ array, scalar, and result array to the input, variable, and output.
- Execute over a thousand floats.
At first glance this looks worse than the previous version, since the pleasant text-based syntax has been traded for a cumbersome manual way of specifying the program. But it gains real advantages: no textual syntax needs parsing, so compile() simply generates code from the specified operation. The program can also be modified with C++ code. Replacing the single multiply with a loop that adds the multiply computation nine more times produces a program that multiplies the variable by the input ten times, with no awkward text manipulation. If the surrounding program compiles in C++, it will not fail to compile in the little language, at least not because of syntax errors.
Bringing Back the Operators
How can the syntax resemble the original program again? Input, Output, and Variable are classes, and C++ classes support operator overloading. If the program being defined is globally accessible, an operator* can be written that creates a temporary variable, records a multiply computation, and returns the temporary. In fact, if the Variable, Input, and Output constructors add themselves to the global program, add_variable is unnecessary too. The snippet then becomes:
- Create a Program and assign it to the global program pointer.
- Declare an Input, an Output, and a Variable.
- Write output = input * var.
- Clear the global program pointer.
- Compile the program.
- Attach the C++ array, scalar, and result array.
- Execute over a thousand floats.
That is a great deal better. The code suddenly looks like ordinary C++, yet the operator* call does not actually multiply anything; it merely records that a multiply should happen at that point. The same loop trick still works: writing output = input * var and then looping nine times with output = output * var is far more readable than the earlier attempt, and it is clear what the code does. Remember that ten multiplies are generated from those three lines; operator* simply sees itself called ten times and knows nothing of the surrounding for loop. The example is simple, but the technique is genuinely powerful, and its ramifications are explained later.
Learning to Share
Return to improving the language. As in the previous version, the variable types merely represent variables in the program and carry no values themselves. For inputs and outputs that may make sense, since they stand for a thousand values or more and we do not want to cart all of those values around. But var is equivalent to a single float, so why keep two variables for it, one in the little language and one in C++? They can be unified; the key is distinguishing when the variable is initialised.
- Clear the global program pointer.
- Declare the Variable with a value such as 0.5 while no global program is set.
- Create a Program and assign it to the global program pointer.
- Declare an Input and an Output.
- Write output = input * b.
- Clear the global program pointer, compile, attach the C++ array and result array, and execute over a thousand floats.
What happened here? The Variable constructor became a little smarter: it recognises when it is declared outside of a program, and in that case it allocates and holds a value directly, so the C++ variable and the program variable are one and the same.
Continue Exploring ShWiki
Use the links below to read the article, join the discussion, review its edit history, or browse the wiki.
Read How Sh Works Article Page Discuss This Article Edit This Page View Page History Log In Visit Main Page Recent Changes Random Page What Links Here Related Changes Upload File Special Pages Printable Version MediaWiki About ShWiki General Disclaimer