The GRL language

Ian Horswill
Northwestern University Computer Science Department

This document describes version 1.3 of the language.

 

GRL (Generic Robot Language) is a robot programming language designed to allow programmers to write real-time sensory-motor systems in a concise, high-level notation based on functional programming.  GRL is embedded within the Scheme language, meaning that GRL programs are allowed to contain arbitrary Scheme code.

Compile-time and run-time

GRL code is a combination of run-time code and compile-time code.   Compile-time code is allowed to make full use of the features of Scheme.   Run-time code, however, is effectively limited to C-style semantics. 

Ontology

Values

Values are the data objects that can be manipulated at run-time.   Integers, floats, Booleans, and enumerated types are all supported as scalar values.   Vectors of uniform types are also supported.  Signals are not values, however.  Nor are procedures.

Types

Types are s-expressions representing the data type of a signal or value.  They can be declared by the programmer or inferred by the compiler.  The default settings of the type inference engine will generate the types:

At present, types are used:

We are planning to add overloading to the language later this year.

Signals and circuits

At run-time, a signal is a time-series of values that are computed incrementally and stored in a memory location.  At compile-time, a signal is a data object.  The following information is visible to the programmer at compile time:

Accumulators and gatherers

An accumulator is a signal with an unspecified set of inputs.  Accumulators are tagged with a gatherer procedure that computes the inputs of the signal.   The gatherer is called after the compiler has reduced all signal procedure applications in to primitive circuits (see below).  The gatherer is called with a list of all signals in the primitive circuit and returns a list of primitive signals that are to be used as inputs for the gatherer's signal.  Because the inputs of an accumulator are determined after signal procedure expansion, its operator cannot be a signal procedure.

The drives declaration

The default gatherer for accumulators searches for signals that have been declared to drive the accumulator in question using the drives declaration.  The drives declaration (see below) can either specify a list of signals directly or can specify a procedure of one argument.  In the latter case, the procedure is called at compile time with the list of all accumulators and should return a list of accumulators that the signal in question is to drive.

Registers

Registers are another special kind of signal that implement shared state variables that can be passed as arguments to functions.  They can be created using the make-shared-register and the make-shared-vector-register procedures.  When passed as arguments to transducers, registers can be assigned using set! and vector-set!.

Signal procedures

Signal procedures are compile-time mappings from signal objects to signal objects.   Since signal objects include their input signal objects, signal procedures are really compile-time mappings from circuits to circuits.

Prior to code generation, the compiler recursively evaluates signal procedure applications.  A primitive signal is signal that is either a constant, a source signal, or an application of a primitive procedure to a set of primitive signals.   Composite signals are applications of signal procedures, or applications of primitive procedures to groups or lists.  A primitive circuit is a network of primitive signals.  A composite circuit is a circuit that contains at least one composite signal.  The aim of the compiler's recursive evaluation of signal procedures is to reduce the circuit on which the compiler was called to a primitive circuit.

Order of evaluation: Signal procedures are evaluated in applicative order, meaning that they act like real procedures and not like macros.  Thus, in the case of a program whose circuit layout is a tree or DAG, it will start at the leaves of the tree, and work upward.  If a signal procedure returns a composite circuit, it is also reduced bottom-up.  Thus, the return value at each point of the evaluation process is always a primitive circuit, and the arguments to a signal procedure when it is evaluated are always a set of primitive circuits.  However, if the program is a cyclic circuit, then the compiler is not guaranteed to call signal procedures with primitive arguments.

Transducers

Transducers implementation finite-state mappings from time series to time series.   A transducer is specified by a set of inputs (formal arguments), a set of state variables, that are preserved between cycles of the system's main control loop, a set of initial values for those state variables, and an update rule, which is a Scheme code fragment that the system calls once to cycle of the update loop.

Vectors can be manipulated by transducers using the normal Scheme primitives vector-ref, vector-set!, and vector-length.  Transducers can allocate vectors in the initialization fields of their state variable declarations using the Scheme primitives vector and make-vector.   However, these primitives cannot be used in the body of the transducer  (since this would require dynamic allocation and GC).  Transducers also may not assign vector-valued variables other than through vector-set! (or array-set!).  Thus you cannot say (set! vec1 vec2), although you can write a copy loop, if you want.

Modalities

A modality is a single-argument signal procedure.  However, modalities are different from normal signal procedures in that:

Note that the body of a modality is always executed exactly once for each signal for which the modality is defined.  Put in more direct terms:

Signal expression syntax

Circuits are typically built using signal expressions.  A signal expression can be:

A value (4, 12.5, #f, etc.)
This denotes a signal with a constant value
A name (x, a, my-signal, etc.)
The name should be a Scheme variable bound to a signal object
(primitive-procedure  argument-signal  ...)
Returns a signal whose value at any point in time is computed by applying primitive-procedure to the values of the signals argument-signal....
(signal-procedure  argument-signal  ...)
Returns a signal generated by running the signal-procedure at compile-time with the argument-signals.  Note that signal procedures are not automatically mapped over vectors and groups.
(transducer  argument-signal  ...)
Returns a signal whose value at any point in time is computed by the body of the transducer using the current values of the argument-signals and the transducer's state variables.  Note that if a transducer is called several times, each call proceduces a distinct signal with distinct state variables, even if the arguments are identical.  If an argument-signal is a group, then the result is a group and the transducer is mapped across the elements of the group as with a primitive procedure.   Note that transducers are not automatically mapped over vectors, although they probably will be in a future version of GRL.
(enum type name)
As in Scheme48.  The value named name within enumerated type type.
(source scheme-code  ...)
This denotes a source signal.  The value of the signal is computed by evaluating scheme-code
(lambda (args ...) body ...)
This denotes an anonymous signal procedure
(group (label signal-expression) ...)
Returns a group containing the specified signal expressions.
(select label  signal-expression)
Signal-expression must denote a group.  Returns the named component of the group.  If you think of groups as structs or records, then select is like the . or -> operators in C.
(procedure signal-expressions  ...)
Denotes a new signal formed by applying procedure to the arguments signal-expressions ....
(apply function signal-expression  ...)
As in Scheme, but the expressions are all signal expressions.
(accumulate primitive-function)
(accumulate primitive-function  gatherer)
Denotes a signal that is the result applying primitive-function to its inputs, but does not specify those inputs.  The inputs are determined at compile time.   If the gatherer is specified, it is called by the compiler after signal expression time with a list of all signals being compiled.  The gatherer should return a list of signals to be used as inputs.  If no gatherer is specified, the set of inputs is the set of signals being compiled that are declared to drive this signal (see declarations).  Signals that are declared to drive this signal, but which are not traceable from the list of top-level signals passed to the compiler are not included as inputs.
(let ((name  init-expression  declaration ...) ...) result-expression   declaration ...)
(let* ((name  init-expression  declaration ...) ...) result-expression  declaration ...)
(letrec ((name  init-expression   declaration ...) ...) result-expression  declaration ...)
As in Scheme, but the expressions are all signal expressions, and optional declarations can be added.  The names are bound to the values of the init-expressions and the result-expressions are evaluated in the expanded lexical environment and returned.  In a let form, the init-expressions are evaluated in the enclosing lexical environment.  Thus the fragment:
(define-signal a 10)
(let ((a (+ a 1))
      (b (+ a 2)))
  (list a b))

will return two signals with the constant values 11 and 12, respectively, whereas in a let* form, each init-expression is evaluated in a lexical environment that includes the previous name.  Thus the fragment:

(define-signal a 10)
(let ((a (+ a 1))
      (b (+ a 2)))
  (list a b))

will return two signals with the constant values 11 and 13, respectively.  Letrec, however, evaluates all init-expressions in a lexical environment that includes all names.  This allows cyclic signal graphs (also called "reentrant networks") to be created.  Thus:

(letrec ((a (low-pass-filter (- a-input b) 1000))
         (b (low-pass-filter (- b-input a) 1000)))
  (list a b))

will generate an pair of mutually inhibitory signals, a and b, that are stimulated by inputs a-input and b-input, respectively, and that have time constants of 1000ms.

(if signal-expression signal-expression signal-expression)
(cond (signal-expression signal-expression)...  (else signal-expression))
(case ((value ...) signal-expression)...  (else signal-expression))
(and signal-expression ...)
(or signal-expression ...)
As in Scheme, but the expressions are all signal expressions. 
(enum-case enumerated-type ((name ...) signal-expression)...  (else signal-expression))
This is identical to the normal case statement except that it allow the use of enumerated types.  The case tags must all be names of the same type, given by enumerated-type.
(declare signal-expression  declaration ...)
Returns the signal-expression, but applies the declarations to it.

Signal declarations

Many forms allow signal declarations to be added.  A signal declaration may be any of the following:

(name symbol)
(name symbol-or-string ...)
The compiler uses symbol as its internal name for the signal.  If possible, symbol  will be used as the name of the global variable used to hold the value of this signal at run time.  This is useful for debugging purposes.   If multiple symbols-or-strings are included, then the compiler will concatenate them to for the name of the signal.
(initial-value signal-expression)
Used for cyclic signal networks.  Declares that this signal is a recurrence and that its initial value should be the value of the expression signal-expression.   Note that the initial value must be a constant that can be determined at compile time.
(type type-expression)
Declares the type of the signal to be type-expression.
(force-expression Boolean)
If Boolean is true, this prevents the compiler from inlining the signal.   That is, it forces it to generate a separate variable to hold the signal's value at run-time.  This can be useful for debugging purposes.
(properties (property-name  property-value) ...)
Assigns properties to the signal's property list.  Note that property-value is a scheme expression, not a signal-expression.  To specify the property value is a signal expression, the expression should be wrapped with a signal-expression form.
(drives signal-expression ...)
Declares that the signal drives the listed signals.
(mode (modality  signal-expression) ...)
Declares modes for the signal.
(as-function (lambda args  body))
(as-function signal-procedure)
Declares that when the signal is placed in procedure position (used as a function), the specified signal-procedure should be used instead.  This is useful, for example, if you want to represent a sampled function as a vector but still want to be able to treat the vector syntactically as if it were a real function.

Top-level forms

GRL includes a number of top-level forms for defining different kinds of objects.  Each is equivalent to some simpler use of define.   However, these forms do magic behind your back to cause mutation to work properly, and so they should be used in preference to their equivalent define forms.  The specific issue is that if you evaluate the sequence:

(define a (signal-expression 1))
(define b (signal-expression (+ a 1)))
(define a (signal-expression 10))

Then the signal b will have a constant value of 2, rather than of 11 as would be expected.  The reason being that each call to signal-expression creates a fresh signal object, which define blindly binds to the specified variable.  This leaves b with the old value of a as its input, rather than the new value.  The "equivalent" fragment:

(define-signal a 1)
(define-signal b (+ a 1))
(define-signal a 10)

properly handles this situation by overwriting the original data structure for a.

(define-signal name  signal-expression   declarations ...)
Binds the variable name to signal-expression.
(define-signal (name  arg ...) signal-expression)
Binds the variable name to the signal procedure:
    (lambda (arg ...) (signal-expression signal-expression))
(define-signal-procedure (name  arg ...) scheme-expression)
Binds the variable name to the signal procedure:
    (lambda (arg ...) scheme-expression)
(define-transducer (name  arg ...) (type type) (state-variables (name   init) ...)
                   (initializations forms ...)
  body ...)
Binds name to a transducer with inputs arg ... and state variables name ....  The state variables have initial values init ... and body body ..., all of which should be Scheme expressions.  If type is unspecified, the transducer is assumed to return an integer.
(define-signal-modality (name  arg) scheme-expression)
Binds the variable name to the signal modality with default value scheme-expression.
(define-mode (modality  signal-expression1) signal-expression2)
Overrides the default value of modality for signal-expression1 and replaces it with signal-expression2.
(define-signal-syntax name  macro-expression)
Binds the variable name as a macro.  This should be used rather than the normal Scheme define-syntax if the macro is to be used within signal expressions.

Derivative forms

GRL also provides a number of convenience macros that are derived from define-signal.

(define-source name  scheme-expression type)
This is equivalent to (define-signal name (source scheme-expression)(type type)).  Declares that  name is of type type and should be compiled to scheme-expression.
(import-source  type name ...)
Special case of define-source used when you want to define a large number of signals with the same type and those signals are stored in variables in the target language that have the same name as the variable in GRL.
(define-machine name  (inputs inputs ...) (state-variables state-vars ...) body ...)
(define-controller name  (inputs inputs ...) (state-variables state-vars ...) body ...)
This is equivalent to
   (define-signal name
   ((transducer name  (inputs inputs ...) (state-variables state-vars ...) body ...)
           inputs ...).
(define-group-type type-name (maker  label ...) (label accessor) ...)
Analogous to the define-record-type macro of Scheme48.   Creates a set of signal procedures to define a group consisting of the specified set of labels.  It defines a constructor called maker and a set of accessors for the specified labels.

Scheme expressions

GRL defines the following forms that may be included freely as expressions in Scheme code:

(signal-expression signal-expression   declaration ...)
Returns the signal object associated with signal-expression
(signal-function-expression signal-function-expression)
Returns the Scheme procedure, transducer, or signal-procedure denoted by signal-function-expression. This is completely equivalent to just typing the signal-function-expression, unless (A) the expression happens to be if, and, or or, which are not considered procedures in Scheme, but are considered procedures in GRL.  In these cases, it returns the Scheme procedure that implements the GRL procedure.   (B) the expression is a lambda, in which case it returns a signal procedure.
(transducer (name name) (inputs inputs ...) (type type)
            (state-variables state-vars ...)
            (initializations forms ...)
            body ...)
Returns a transducer object.

Primitive procedures supported in GRL

The GRL compiler supports the following primitive procedures

Arithmetic primitives

+, -, *, /, quotient, modulo, arithmetic-shift, min, max, abs
Standard Scheme arithmetic operators.
=, eq?, zero?, >, <, >=, <=, not
Standard Scheme comparison operations.
sqrt, sin, cos, tan, log, atan
Standard Scheme scientific functions.  Note that atan may be called in either the one- or two-argument form.
(arg-min value ...), (arg-max value ...)
Returns the index of its smallest (largest) argument.
round->integer
Like the Scheme function round, but guarantees that the result will be a true integer, rather than a floating-point number with zero after the decimal.  (i.e. it's an exact integer in Scheme R5RS terminology).

List primitives

GRL supports lists of signals, however, lists are not allowable run-time values for signals (since this would require dynamic allocation at run-time, and therefore garbage collection).  Therefore, lists may only be formed and manipulated at compile-time.   Lists can be generated either with rest arguments of signal procedures (e.g. "(define-signal (foo . args) ...)"), or directly with the list primitive.

(list signal-expression ...)
As in Scheme, but the expressions are all signal expressions.
(car list), (cdr list)
As in Scheme.
(null? list)
As in Scheme.  Note that null? is guaranteed to be evaluated at signal-expansion time.  It can therefore be safely used to terminate compile-time recursions.
(length list)
As in Scheme.  Returns the length of the list.
(list-ref list-of-signals  index-signal)
As in Scheme, with the exception that list-of-signals must be a list of signals of the same type.  The result of this operation is a signal whose value at run-time is the value of whichever signal in list-of-signals is specified by index-signal.   If index-signal is 0, then the result is the value of the first signal in the list.  If index-signal is 1, the result is the value of the second signal in the list, etc.   Thus, (list-ref l i) is equivalent to:
     (apply nth-argument i  l)
and, in fact, this is how it is presently compiled.

Vector primitives

GRL supports homogeneous vectors as a run-time data type.  That is, a signal can have a vector as its value.  However, the type system requires that the value of a given signal always have the same vector type over time, that is, the same element type and the same length.

Vectors can be manipulated by transducers using the normal Scheme primitives vector-ref, vector-set!, and vector-length.  Transducers can allocate vectors in the initialization fields of their state variable declarations using the Scheme primitives vector and make-vector.   However, these primitives cannot be used in the body of the transducer  (since this would require dynamic allocation and GC).  Transducers also may not assign vector-valued variables other than through vector-set! (or array-set!).  Thus you cannot say (set! vec1 vec2), although you can write a copy loop, if you want.

Note that the compiler is very agressive about inlining vector signals when possible.   Thus, a signal expression like:

    (* 2 (+ v 1) (index-generator 10))

would compile to a loop like:

    (dotimes (_i 10)
      (vector-set! signal _i
                   (* 2
                      (+ (vector-ref v _i)
                         1)
                      _i)))

That is, the compiler would not actually generate any storage for the results of the index-generator or + expressions.

(vector signal ...), (vector-ref vector  index), (vector-length vector)
As in scheme.
(vector-shift vector count padding), (vector-rotate vector count)
Returns a new vector of the same size as vector, the with the elements shifted or rotated count places to the left.  When count is negative, vector is shifted or rotated to the right.  In the shifting case, empty elements are filled in with padding.  The padding argument is optional and defaults to the value of the rightmost or leftmost element, when count is positive or negative, respectively.
(vector-shorten vector  new-length)
Returns a new vector consisting of the first new-length elements of vector.
(resample vector  new-length)
Returns a new vector that is length new-length and whose elements are taken from . by delta-function sub- (or super-) sampling.  Therefore if v is type (vector integer 16), then the ith element of (resample v 10) will be:

   (vector-ref v (quotient (* i 16) 10))
(index-generator arg)
(vector-dot-iota arg) (this name is deprecated)
Like the i function in APL and the iota function in the Scheme standard list library (formerly dot-iota in the proposed standard).  Returns a vector of values from 0 to n where n is its argument.  You'd never really want to store a vector with this value.  However, it's useful for cleaver functional programming tricks, such as:

   (lambda (number-of-samples)
     (sin (/ (* 2 pi
                (index-generator number-of-samples))
             number-of-samples)))

which returns a vector containing one cycle of a discretely sampled sine wave.

Array primitives (preliminary, alpha-test)

The compiler has provisional support for multidimensional arrays.  These are treated as a subtype of vectors.  Vector type expressions can be tagged with an additional element, which is a list of integer dimensions.

(array-ref array index ...)
Returns the specified element of a multidimensional array.
(array-dimension array dimension-number)
Returns the size of the array along the specified dimension number.
(array-dimensions array)
Returns all dimensions of the array as a list.
(reshape array dimension ...)
Equivalent to the APL r operator.  Returns a new array which identical to array, but that has the specified dimensions.  The two arrays must have the same number of elements.  That is, the product of new dimensions must be the same as the product of the old dimensions.  Note that new array typically shares storage with the old array.

Registers

(make-shared-register initial-value)
Creates a shared variable that can be passed as an argument to functions.  It behaves like a normal signal except that the compiler does not automatically update it on every clock tick.  Instead, the user modifies it directly by passing it to a transducer that assigns it using set!.  The value of the register at any given time is the value last assigned to it by some transducer, or initial-value, if it has never been assigned.  The update code for a given transducer is guaranteed to run as a single, atomic operation.  However, no other guarantees are made about ordering of write operations to a register within a given clock tick.
(make-shared-vector-register length   initial-element-value)
Same, but the register is a vector.  It is assigned using vector-set!.

Primitive signals

ms-clock
An integer that increases by 1 for each millisecond the system runs.  The clock is sampled once per iteration of the main control loop so all signals using the clock see identical values.
clock-period
The target duration between cycles of the main control loop.
measured-clock-period
The actual measured duration between the last two cycles of the main control loop.

Writing transducers

As much as possible, we have tried to allow transducers to use arbitrary Scheme code.   The major restrictions imposed on transducer bodies is that they be "C-like" in the sense that:

When compiling code to run inside of Scheme or LISP, you can sometimes relax these restrictions, but it's generally not a good idea.

The following restrictions should also be followed, but are not enforced by the compiler:

Returning aggregate types from transducers (preliminary, beta-test)

In general, transducers are assumed to return scalars.  However, there is provisional support for returning groups and vectors from transducers.  The current compiler imposes the following restrictions:

Thus a transducer that returns a vector must look something like:

(define-transducer (my-transducer v i)
  (type (proc ((vector integer ,l) integer)
              (vector integer ,l)))
  (state-variables (retval (make-vector (vector-length v)
                                        0))
                   ... other state variable declarations ...)

  ... do some computing and fill in retval ...

  reval)

And transducers that return groups must look something like:

(define-transducer (my-transducer a b c d)
  (type (proc (integer float float boolean)
              (group (x float)
                     (y float))))
  (state-variables (xval 0.0)
                   (yval 0.0)
                   ... other state variable declarations ...)

  ... do some computing and fill in xval and yval ...

  (group (x xval)
         (y yval)))

Static typing of state variables

The compiler infers the types of state variables from their initial values.   Usually, this is a good thing, but it can lead to the following irritating problems:

Nonstandard Scheme-level macros used in transducers

(when condition  body ...)
(unless condition  body ...)
As in Common Lisp.  equivalent to (if condition (begin body ...)), and (if (not condition) (begin body ...)), respectively.
(while test body ...)
A standard while (i.e. pretest) loop.
(dotimes (var  count) body ...)
As in Common Lisp.  Iterates with var from 0 to count-1.
(for (var  start  end) body ...)
As in BASIC.  Iterates with var from start to end.
(comment string)
Ignored.

Array primitives allowed in transducers (preliminary, alpha-test)

(array-ref array index ...)
Returns the specified element of a multidimensional array.
(array-set! array new-value  index ...)
Assigns the specified element of the array to new-value.
(array-dimension array dimension-number)
Returns the size of the array along the specified dimension number.
(array-dimensions array)
Returns all dimensions of the array as a list.
(reshape array dimension ...)
Equivalent to the APL r operator.  Returns a new array which identical to array, but that has the specified dimensions.  The two arrays must have the same number of elements.  That is, the product of new dimensions must be the same as the product of the old dimensions.  Note that new array typically shares storage with the old array.

I/O Primitives allowed in transducers

Support for these is dependent on your compiler back-end.

read, write, display, format
As in Scheme (or Scheme48 in the case of format).  These are only really useful in transducers.
read-byte, write-byte
Like read-char, and write-char but perform binary I/O.  Again, these are only really useful in transducers.

Calling foreign functions from transducers and source signals

(declare-external name type)
Declares that the foreign (C or Scheme) procedure name returns data of type typ
(declare-type-default-value type value)
Declares that the compiler should initialize object-code variables of type type to value

Under normal circumstances, you can call foreign functions with impunity, particularly if you are compiling to scheme or lisp.  However, under some circumstances, you may need to give the compiler type information.  This happens most commonly when compiling to C or BASIC.  The most common issue is that the partial evaluator may be unable to determine the return type of a foreign function.  If this happens, simply tell it the return type with define-external (see below).

Things are somewhat more complicated when working with foreign functions that return values of types the compiler doesn't understand.  By default, the procedures called within transducers or source signals are restricted to return integers, floats, Booleans, or vectors.   However, there is limited support for extending the set of primitive types that the GRL compiler understands.  To add support for a new type, you need to tell the compiler what the default value corresponding to that type is.  When compiling to lisp or scheme, default values are mostly pro forma.   When the compiler generates code for a signal, it stores the value of that signal in a variable.  Since Scheme does not allow uninitialized variables, that variable has to be given some value in its declaration, so the compiler chooses a value based on the signal's type.  This is called the default value for the type.  The default values for integers is 0, for floats is 0.0, and for Booleans is #f.  To provide support for a new data type, simply specify a default value for objects of that type using declare-type-default-value..