Translating Descriptions to C Code

Also in the trnsrc directory are a number of .alg files, which contain the source code for the translator (more on these will follow), and a number of corresponding .h and .c files.

To translate a .alg file to .c and .h files, you start XLisp or Nyquist in the trnsrc directory and type

(translate "prod")

Note: On the Macintosh, just run Nyquist out of the runtime directory and then use the Load menu command to load init.lsp from the trnsrc directory. This will load the translation code and change Nyquist's current directory to trnsrc so that commands like (translate "prod") will work.

Rebuilding Nyquist

Accessing the New Function

For some functions, you must write some Lisp code to impose ordinary Nyquist behaviors such as stretching and time shifting. A good approach is to find some structurally similar functions and see how they are implemented. Most of the Lisp code for Nyquist is in nyquist.lsp.

Finally, do not forget to write up some documentation. Also, contributions are welcome. Send your .alg file, documentation, Lisp support functions for nyquist.lsp, and examples or test programs to rbd@cs.cmu.edu. I will either put them in the next release or make them available at a public ftp site.

Why Translation?

The main idea behind the translation is that all of the checks and setup code are similar and relatively easy to generate automatically. Programmers often use macros for this sort of task, but the C macro processor is too limited for the complex translation required here. To tell the translator how to generate code, you write .alg files, which provide many details about the operation in a declarative style. For example, the code generator can make some optimizations if you declare that two input signals are commutative (they can be exchanged with one another). The main part of the .alg file is the inner loop which is the heart of the signal processing code.

Writing a .alg File

(PROD-ALG
  (NAME "prod")
  (ARGUMENTS ("sound_type" "s1") ("sound_type" "s2"))
  (START (MAX s1 s2))
  (COMMUTATIVE (s1 s2))
  (INNER-LOOP "output = s1 * s2")
  (LINEAR s1 s2)
  (TERMINATE (MIN s1 s2))
  (LOGICAL-STOP (MIN s1 s2))
)

(name
  (attribute value)
  (attribute value)
  ...
)

Understanding what the attributes do is not easy, so here are three recommendations for implementors. First, if there is an existing Nyquist operator that is structurally similar to something you want to implement, make a copy of the corresponding .alg file and work from there. In some cases, you can merely rename the parameters and substitute a new inner loop. Second, read the generated code, especially the generated inner loop. It may not all make sense, but sometimes you can spot obvious errors and work your way back to the error in the .alg file. Third, if you know where something bad is generated, see if you can find where the code is generated. (The code generator files are listed in init.lsp.) This code is poorly written and poorly documented, but in some cases it is fairly straightforward to determine what attribute in the .alg file is responsible for the erroneous output.

Attributes

(NAME "string")

specifies a base name for many identifiers. In particular, the generated filenames will be string.c and string.h, and the XLisp function generated will be snd-string.

(ARGUMENTS arglist)

describes the arguments to be passed from XLisp. Arglist has the form: (type1 name1) (type2 name2) ..., where type and name are strings in double quotes, e.g. ("sound_type" "s") specifies a SOUND parameter named s. Note that arglist is not surrounded by parentheses. As seen in this example, the type names and parameter names are C identifiers. Since the parameters are passed in from XLisp, they must be chosen from a restricted set. Valid type names are: "sound_type", "rate_type", "double", "long", "string", and "LVAL".

(STATE statelist)

describes additional state (variables) needed to perform the computation. A statelist is similar to an arglist (see ARGUMENTS above), and has the form: (type1 name1 init1 [TEMP]) (type2 name2 init2 [TEMP]) .... The types and names are as in arglist, and the "inits" are double-quoted initial values. Initial values may be any C expression. State is initialized in the order implied by statelist when the operation is first called from XLisp. If TEMP is omitted the state is preserved in a structure until the sound computation completes. Otherwise, the state variable only exists at state initialization time.

(INNER-LOOP innerloop-code)

describes the inner loop, written as C code. The innerloop-code is in double quotes, and may extend over multiple lines. To make generated code extra-beautiful, prefix each line of innerloop-code with 12 spaces. Temporary variables should not be declared at the beginning of innerloop-code. Use the INNER-LOOP-LOCALS attribute instead. Within innerloop-code, each ARGUMENT of type sound_type must be referenced exactly one time. If you need to use a signal value twice, assign it once to a temporary and use the temporary twice. The inner loop must also assign one time to the psuedo-variable output. The model here is that the name of a sound argument denotes the value of the corresponding signal at the current output sample time. The inner loop code will be called once for each output sample. In practice, the code generator will substitute some expression for each signal name. For example, prod.alg specifies

(INNER-LOOP "output = s1 * s2")

(s1 and s2 are ARGUMENTS.) This expands to the following inner loop in prod.c:

*out_ptr_reg++ = *s1_ptr_reg++ * *s2_ptr_reg++;

In cases where arguments have different sample rates, sample interpolation is in-lined, and the expressions can get very complex. The translator is currently very simple-minded about substituting access code in the place of parameter names, and this is a frequent source of bugs. Simple string substitution is performed, so you must not use a parameter or state name that is a substring of another. For example, if two sound parameters were named s and s2, the translator might substitute for "s" in two places rather than one. If this problem occurs, you will almost certainly get a C compiler syntax error. The fix is to use "more unique" parameter and state variable names.

(INNER-LOOP-LOCALS "innerloop-code")

The innerloop-code contains C declarations of local variables set and referenced in the inner loop.

(SAMPLE-RATE "expr")

specifies the output sample rate; expr can be any C expression, including a parameter from the ARGUMENTS list. You can also write (SAMPLE-RATE (MAX name1 name2 ...)) where names are unquoted names of arguments.

(SUPPORT-HEADER "c-code")

specifies arbitrary C code to be inserted in the generated .h file. The code typically contains auxiliarly function declarations and definitions of constants.

(SUPPORT-FUNCTIONS "c-code")

specifies arbitrary C code to be inserted in the generated .c file. The code typically contains auxiliarly functions and definitions of constants.

(FINALIZATION "c-code")

specifies code to execute when the sound has been fully computed and the state variables are about to be decallocated. This is the place to deallocate buffer memory, etc.

(CONSTANT "name1" "name2" ...)

specifies state variables that do not change value in the inner loop. The values of state variables are loaded into registers before entering the inner loop so that access will be fast within the loop. On exiting the inner loop, the final register values are preserved in a "suspension" structure. If state values do not change in the inner loop, this CONSTANT declaration can eliminate the overhead of storing these registers.

(START spec)

specifies when the output sound should start (a sound is zero and no processing is done before the start time). The spec can take several forms: (MIN name1 name2 ...) means the start time is the minimum of the start times of input signals name1, name2, .... Note that these names are not quoted.

(TERMINATE spec)

specifies when the output sound terminates (a sound is zero after this termination time and no more samples are computed). The spec can take several forms: (MIN name1 name2 ...) means the terminate time is the minimum of the terminate times of input arguments name1, name2, .... Note that these names are not quoted. To terminate at the time of a single argument s1, specify (MIN s1). To terminate after a specific duration, use (AFTER "c-expr"), where c-expr is a C variable or expression. To terminate at a particular time, use (AT "c-expr"). spec may also be COMPUTED, which means to use the maximum sample rate of any input signal.

(LOGICAL-STOP spec)

specifies the logical stop time of the output sound. This spec is just like the one for TERMINATE. If no LOGICAL-STOP attribute is present, the logical stop will coincide with the terminate time.

(ALWAYS-SCALE name1 name2 ...)

says that the named sound arguments (not in quotes) should always be multiplied by a scale factor. This is a space-time tradeoff. When Nyquist sounds are scaled, the scale factor is merely stored in a structure. It is the responsibility of the user of the samples to actually scale them (unless the scale factor is exactly 1.0). The default is to generate code with and without scaling and to select the appropriate code at run time. If there are N signal inputs, this will generate 2^(N) versions of the code. To avoid this code explosion, use the ALWAYS-SCALE attribute.

(INLINE-INTERPOLATION T)

specifies that sample rate interpolation should be performed in-line in the inner loop. There are two forms of sample rate interpolation. One is intended for use when the rate change is large and many points will be interpolated. This form uses a divide instruction and some setup at the low sample rate, but the inner loop overhead is just an add. The other form, intended for less drastic sample rate changes, performs interpolation with 2 multiplies and several adds per sample at the high sample rate. Nyquist generates various inner loops and selects the appropriate one at run-time. If INLINE-INTERPOLATION is not set, then much less code is generated and interpolation is performed as necessary by instantiating a separate signal processing operation.

(STEP-FUNCTION name1 name2 ...)

Normally all argument signals are linearly interpolated to the output sample rate. The linear interpolation can be turned off with this attribute. This is used, for example, in Nyquist variable filters so that filter coefficients are computed at low sample rates. In fact, this attribute was added for the special case of filters.

(DEPENDS spec1 spec2 ...)

Specifies dependencies. This attribute was also introduced to handle the case of filter coefficients (but may have other applications.) Use it when a state variable is a function of a potentially low-sample-rate input where the input is in the STEP-FUNCTION list. Consider a filter coefficient that depends upon an input signal such as bandwidth. In this case, you want to compute the filter coefficient only when the input signal changes rather than every output sample, since output may occur at a much higher sample rate. A spec is of the form

("name" "arg" "expr" [TEMP "type"])

which is interpreted as follows: name depends upon arg; when arg changes, recompute expr and assign it to name. The name must be declared as a STATE variable unless TEMP is present, in which case name is not preserved and is used only to compute other state. Variables are updated in the order of the DEPENDS list.

(FORCE-INTO-REGISTER name1 name2 ...)

causes name1, name2, ... to be loaded into registers before entering the inner loop. If the inner loop references a state variable or argument, this happens automatically. Use this attribute only if references are "hidden" in a #define'd macro or referenced in a DEPENDS specification.

(NOT-REGISTER name1 name2 ...)

specifies state and arguments that should not be loaded into registers before entering an inner loop. This is sometimes an optimization for infrequently accessed state.

(NOT-IN-INNER-LOOP "name1" "name2" ...)

says that certain arguments are not used in the inner loop. Nyquist assumes all arguments are used in the inner loop, so specify them here if not. For example, tables are passed into functions as sounds, but these sounds are not read sample-by-sample in the inner loop, so they should be listed here.

(MAINTAIN ("name1" "expr1") ("name2" "expr2") ... )

Sometimes the IBM XLC compiler generates better loop code if a variable referenced in the loop is not referenced outside of the loop after the loop exit. Technically, optimization is better when variables are dead upon loop exit. Sometimes, there is an efficient way to compute the final value of a state variable without actually referencing it, in which case the variable and the computation method are given as a pair in the MAINTAIN attribute. This suppresses a store of the value of the named variable, making it a dead variable. Where the store would have been, the expression is computed and assigned to the named variable. See partial.alg for an example. This optimization is never necessary and is only for fine-tuning.

(LINEAR name1 name2 ...)

specifies that named arguments (without quotes) are linear with respect to the output. What this really means is that it is numerically OK to eliminate a scale factor from the named argument and store it in the output sound descriptor, avoiding a potential multiply in this inner loop. For example, both arguments to snd-prod (signal multiplication) are "linear." The inner loop has a single multiplication operator to multiply samples vs. a potential 3 multiplies if each sample were also scaled. To handle scale factors on the input signals, the scale factors are automatically multiplied and the product becomes the scale factor of the resulting output. (This effectively "passes the buck" to some other, or perhaps more than one, signal processing function, which is not always optimal. On the other hand, it works great if you multiply a number of scaled signals together: all the scale factors are ultimately handled with a single multiply.)

(INTERNAL-SCALING name1 name2 ...)

indicates that scaling is handled in code that is hidden from the code generator for name1, name2, ..., which are sound arguments. Although it is the responsibility of the reader of samples to apply any given scale factor, sometimes scaling can be had for free. For example, the snd-recip operation computes the reciprocal of the input samples by peforming a division. The simple approach would be to specify an inner loop of output = 1.0/s1, where s1 is the input. With scaling, this would generate an inner loop something like this:

*output++ = 1.0 / (s1_scale_factor * *s1++);

but a much better approach would be the following:

*output++ = my_scale_factor / *s1++

where my_scale_factor is initialized to 1.0 / s1->scale. Working backward from the desired inner loop to the .alg inner loop specification, a first attempt might be to specify:

(INNER-LOOP "output = my_scale_factor / s1")

but this will generate the following:

*output++=my_scale_factor/(s1_scale_factor * *s1++);

Since the code generator does not know that scaling is handled elsewhere, the scaling is done twice! The solution is to put s1 in the INTERNAL-SCALING list, which essentially means "I've already incorporated scaling into the algorithm, so suppress the multiplication by a scale factor."

(COMMUTATIVE (name1 name2 ...))

specifies that the results will not be affected by interchanging any of the listed arguments. When arguments are commutative, Nyquist rearranges them at run-time into decreasing order of sample rates. If interpolation is in-line, this can dramatically reduce the amount of code generated to handle all the different cases. The prime example is prod.alg.

(TYPE-CHECK "code")

specifies checking code to be inserted after argument type checking at initialization time. See downproto.alg for an example where a check is made to guarantee that the output sample rate is not greater than the input sample rate. Otherwise an error is raised.

Another function is name_toss_fetch, which is called when sounds are not time-aligned and some initial samples must be discarded from one or more inputs.

The function that creates a sound is snd_make_name. This is where state allocation and initialization takes place. The proper fetch function is selected based on the sample rates and scale factors of the sound arguments, and a sound_type is returned.

Since Nyquist is a functional language, sound operations are not normally allowed to modify their arguments through side effects, but even reading samples from a sound_type causes side effects. To hide these from the Nyquist programmer, sound_type arguments are first copied (this only copies a small structure. The samples themselves are on a shared list). The function snd_name performs the necessary copies and calls snd_make_name. It is the snd_name function that is called by XLisp. The XLisp name for the function is SND-NAME. Notice that the underscore in C is converted to a dash in XLisp. Also, XLisp converts identifiers to upper case when they are read, so normally, you would type snd-name to call the function.

Scalar Arguments

Choice 2 is to generate a different sound operator for each case. The naming convention here is to append a string of c's and v's, indicating constant (scalar) or variable (signal) inputs. For example, the reson operator comes in four variations: reson, resoncv, resonvc, and resonvv. The resonvc version implements a resonating filter with a variable center frequency (a sound type) and a constant bandwidth (a FLONUM). The RESON function in Nyquist is an ordinary Lisp function that checks types and calls one of SND-RESON, SND-RESONCV, SND-RESONVC, or SND-RESONVV.

Since each of these SND- functions performs further selection of implementation based on sample rates and the need for scaling, there are 25 different functions for computing RESON! So far, however, Nyquist is smaller than Common Lisp and it's about half the size of Microsoft Word. Hopefully, exponential growth in memory density will outpace linear (as a function of programming effort) growth of Nyquist.