How can we summarize the behavior of composite reactors?

[petervdonovan]

The point of this post is not the syntax (or the math) because both are probably slightly weird or
wrong. The point is to put the general idea down in words.

Summary

• Explicit abstract interfaces for reactors might be useful.
• Such interfaces need not be limited to zero-delay "causality" relations. They could represent cycles
  and encode some timing behavior.
• Such interfaces could be defined abstractly by specifying a finite set of arrows (kind of like
  connections) between ports.

Examples

• Consumer(T: TargetType, n: int): A reactor that accepts n inputs but produces no outputs.
  These reactors will generally have side effects such as writing to actuators or sending messages
  over the network.
• PeriodicProducer(T: TargetType, initial_offset: time, period: time): A timer is a
  PeriodicProducer with T=void. Such reactors as these may be useful for guaranteeing liveness.
• SporadicProducer(T: TargetType): A reactor that produces an output of type t at arbitrary times.
  A PeriodicProducer can be cast to a SporadicProducer, but a SporadicProducer cannot be cast
  to a PeriodicProducer.
• SporadicProducerWithMinSpacing(T: TargetType, min_spacing: time): A reactor that behaves like a
  physical action with a minimum spacing.
• Function(InType: TargetType, OutType: TargetType): A reactor whose output is present at tag g
  iff its input is present at g.
• DelayedFunction(InType: TargetType, OutType: TargetType, delta_g: tag): A reactor whose output
  is present at tag g + delta_g iff its input is present at g, where tag differences are added
  elementwise. For all T, U, Function (T, U) = DelayedFunction(T, U, (0, 0))
• PartialFunction(InType: TargetType, OutType: TargetType): A reactor whose output is not present
  at tag g if its input is not present at g.
• ...

Motivation

In general, one reason why type annotations are valuable in a programming language is that they make
questions that could otherwise only be answered by a global view of the program possible to answer
using only a local view.

• Causality interfaces are necessary in order to determine whether there are cycles. If causality
  interfaces at the reactor level are implicit, a global view of the program is required in order to
  determine whether there are cycles (and why). If they are explicit, then only the containing
  reactor (where connections are made) need be inspected. This convenience may not be important for
  a machine, but humans should be able to interpret how and why their programs have cycles, too.

  reactor HasACycle() {
    input a: int
    f: Function(int, int) = new AddOne()
  
    a -> f.in
    f.out -> f.in
  }
  
  reactor HasNoCycles() {
    input a: int
    f: DelayedFunction(int, int) = new AddOneWithInternalDelay()
  
    a -> f.in
    f.out -> f.in
  }
  

• Causality interfaces alone are insufficient to match the degree of static checking that exists in
  popular statically typed languages.

  • To express the function f(x) := g(h1(x), h2(x)), we write this:

    reactor F() {
      input x: double
      output out: double
      h0 = new H0()
      h1 = new H1()
      g = new G()
    
      x -> h0
      x -> h1
      h0.out -> g.param1
      h1.out -> g.param2
      g.out -> out
    }
    

    This is fine if H0 and H1 are both Functions. But what if one or both of them are
    DelayedFunctions? Then their outputs may not be synchronized. G will have to save whichever
    output comes first so that it can merge it with the output that comes second. Alternatively, if
    they are both DelayedFunctions with the same (precisely specified) delay, then again they will
    certainly be synchronized. This use case is important because:
    • It may be common for reactors to have delays of several microsteps because they may
      internally have pipelines (to maximize parallelism, and perhaps also to ensure correctness in
      the case of hardware reactors with clock cycles that do not permit long combinatorial delays).
    • It may be common for reactors to have delays of many-many microsteps because they may
      require iteration in order to compute some value. For example, the following function applies
      a matrix to a vector many times, until the vector seems to be in an eigenspace. The number of
      microsteps required for it to terminate is data-dependent and impossible to determine
      statically.

      reactor FindEigenvectorInEigenspaceWithGreatestEigenvalue(n: size_t)
          implements DelayedPartialFunction(
        Matrix(n, n),
        double,
        (0, *)  // The "*" represents any natural number of microsteps
      ) {
        input matrix: Matrix(n, n)
        output eigenvector: Vector
      
        state matrix: Matrix(n, n)
        state current_vector: Vector(n)
      
        initial_vector: Supplier(Vector(n)) = new VectorSupplier(n)
        apply_matrix: BiFunction(Matrix, vector, vector) = new ApplyMatrixToVector()
        is_in_span_of_previous = new CheckIfConsecutiveVectorsAreAlmostScalesOfEachOther()
      
        initial_vector, Matrix -> apply_matrix
        apply_matrix -> is_in_span_of_previous after 0
      
        reaction(matrix) {=
          self->matrix = matrix->value
        =}
      
        reaction(apply_matrix.result) {=
          self->current_vector = apply_matrix.result->value;
        =}
      
        reaction(is_in_span_of_previous.no) -> apply_matrix.matrix, apply_matrix.vector {=
          lf_set(apply_matrix.matrix, self->matrix);
          lf_set(apply_matrix.current_vector, apply_matrix.vector->value);
        =}
      
        reaction(is_in_span_of_previous.yes) -> eigenvector {=
          lf_set(eigenvector, self->current_vector);
        =}
      }
      

  • It is important to know whether a reactor will ever respond to a query. In Kotlin, for example,
    whether a value is nullable is part of its type. The LF analogue of the Kotlin type
    (input: Double) -> Int? (a function that might return an integer or might return null instead) is
    PartialFunction(Double, Int), for that is the type of a reactor that might or might not
    produce a response to a request.

• Causality interfaces alone are insufficient to summarize the deep timing analysis that LF has to
  offer. (If I understand, MTL is the powerful "big hammer" for this purpose, but it might not be
  the ideal choice everywhere?)

  • Type annotations that involve time are required in order to observe that the following program
    will produce a response to a request within 100 logical milliseconds, without looking at the
    definitions of R0 and R1:

    reactor MustRespondInTime() implements DelayedPartialFunction(
        int,
        double,
        // this represents a tag difference of up to 100 msec
        (0..100 msec, 0)
    ) {
      input in: int
      output out: double
    
      do_work0: DelayedFunction(int, int, (30 msec, 0)) = new R0()
      do_work1: DelayedPartialFunction(int, int, (20 msec, 0)) = new R1()
    
      in -> do_work0
      do_work0.out -> do_work1.in after 10 msec
      do_work1.out -> out
    }
    

    There may be patterns like the above example in which physical WCETs would need be specified as
    part of the interfaces of components instead of logical times. I am not sure how that would
    work.
  • In the following example, WCETs would be necessary in order to ensure that the
    PossiblyBoundedLag reactor certainly does not have unbounded lag; however, the logical delay
    at least lets us determine that the program might have bounded lag without reading the source
    code of AddOneWithSmallInternalDelay and its nested reactors.

    reactor UnboundedLag() {
      input a: int
      // f produces an output after 1 microstep
      f: DelayedFunction(int, int, (0 msec, 1)) = new AddOneWithSmallInternalDelay()
    
      a -> f.in
      f.out -> f.in
    }
    reactor PossiblyBoundedLag() {
      input a: int
      // f produces an output after 1 msec
      f: DelayedFunction(int, int, (1 msec, 0)) = new AddOneWithBigInternalDelay()
    
      a -> f.in
      f.out -> f.in
    }
    

• In order for reactors to be composed flexibly, they must specify the interfaces of reactors that
  they can be parameterized by. The following is pseudocode (not allowed by our syntax):

  /**
   * Produce an output if an obstacle is too close and it is necessary to apply a brake.
   */
  reactor VisionSystem(
    image_source: PeriodicProducer,
    obstacle_classifier: DelayedFunction(Image, DetectedObject[], (50 msec, 0)),
    apply_brake: PartialFunction(DetectedObject[], void)
  ) implements SporadicProducer {
    output out: void  // present if there is an obstacle
  
    // This reactor is sporadic because apply_brake does not
    // always produce an output, but the delay in
    // obstacle_classifier does not affect its type.
    image_source -> obstacle_classifier -> apply_brake -> out
  }
  

Generalization

I will use the word "objects" to include ports, reactions, and triggers.

For brevity I will use the word "arrows" to refer to happens-before relations.

The following sets of arrows are closed under composition:

• "may be immediately followed by in the same microstep": -> (0, 0) ?
• "will be immediately followed by in the same microstep": -> (0, 0) !
• "may be followed by in the same time instant": -> (0, *) ?
• "will be followed by in the same time instant": -> (0, *) !
• "may eventually be followed by": -> (*, *) ?
• "will eventually be followed by": -> (*, *) !
• "may eventually be followed by, after some number of microsteps that is zero mod 4": -> (0, 4k)

The following sets of arrows are not closed under composition, but that's fine, for they are subsets
of the sets that are closed:

• "may be followed by after 4 microsteps": -> (0, 4) ?
• "will be followed by after 4 microsteps": -> (0, 4) !
• "may be followed by after 2 to 9 microsteps": -> (0, 2..9) ?
• ...

Of the arrows described here, those that we currently express explicitly are:

• -> (0, 0) ! for connections between ports.
• -> (0, 0) ? for arrows between a reaction's inputs and its outputs, and for the "causal
  influence" arrows between reactions in the same reactor. In addition, -> (0, 0) ! arrows are a
  subset of the -> (0, 0) ? arrows. Many ? arrows could perhaps be turned into ! arrows using
  the target language parsing that Shaokai has been working on.

The -> (0, 0) ? arrows are the ones that are relevant to cycle detection.

The rules for composing arrows are as you would expect: A ? arrow composed with a ! arrow gives
a ? arrow, the parenthesized tag part "adds" elementwise, where * plus anything is * and
ranges such as 2..9 are the same as ordered pairs such as (2, 9) that add elementwise.

To represent the interface of a reactor, the user should specify one of the finite sets of arrows
that can generate all arrows. Here are some examples of trivial interface specifications:

interface Consumer(T: TargetType, n: int) {
  input in: T
}

interface PeriodicProducer(T: TargetType, initial_offset: time, period: time) {
  output out: T
  // All times equal to initial_offset modulo period have
  // "will be followed by" arrows pointing to out
  (k * period + initial_offset, 0) -> (0, 0) ! out
}

interface SporadicProducer(T: TargetType) {
  output out: T
  startup -> (*, *) ? out
  out -> (*, *) ? out
}

interface SporadicProducerWithMinSpacing(min_spacing: time) {
  output out: int

  startup -> (*, *) ? out
  out -> (min_spacing..infinity, *) ? out
}

interface Function(InType: TargetType, OutType: TargetType) {
  input in: InType
  output out: OutType
  in -> (0, 0) ! out
}

interface DelayedFunctionWithUndefinedDelay(InType: TargetType, OutType: TargetType) {
  input in: InType
  output out: OutType

  in -> (*, *) ! out
}

interface PartialFunction(InType: TargetType, OutType: TargetType) {
  input in: InType
  output out: OutType

  in -> (0, 0) ? out
}

To determine the interface of an arbitrary reactor, use the arrows that are specified explicitly in
the reactor to generate all arrows and then pick out the arrows between the reactor's input and
output ports, for those are the only ones that are relevant to the outside. In reactors with
infinitely many arrows, (as in the case of timers and self-loops), that algorithm will not work; for
this reason I have not figured out how to determine whether an arbitrary reactor with infinite
arrows implements an arbitrary interface in general.

A reactor of type A can be cast to type B if the ? arrows in A are a subset of the ? arrows
in B and the ! arrows in B are a subset of the ! arrows in A. As a reminder, all ! arrows
are ? arrows, but not all ? arrows are ! arrows.

[edwardalee]

Very interesting ideas! Our current interface information provides some of this, e.g. whether a partial function is delayed or not, but not the distinction between a function and partial function, which is often important (e.g., to be able to infer periodic sources downstream from clocks). What @lsk567 is working on, where he parses the reaction code and analyzes simple patterns, has the potential to provide a conservative over approximation that will infer these types automatically.

[cmnrd]

I know you wrote that this is not about syntax, but since it is not a very prominent feature, I want to make sure that people are ware of the generics syntax that we already have. You can actually write rector DelayedFunction<InType, OutType>(delta_g: tag). This is currently supported in C++ and Typescript.

[petervdonovan]

Part of the reason why I did not use the generics syntax is that the lines between type parameters and other parameters are blurred:

• All parameters (type parameters or otherwise) are determined at compile time in LF, unlike in C++ and Java (well, yes, some LF targets allow parameters to be specified on startup, but this doesn't seem like a core feature of LF, esp. since, as a DSL for embedded systems, LF can be compiled for each system where it is deployed)
• Even parameters that are not type parameters (such as integers) can affect the interface of a reactor by changing the width of its multiports.

To put it another way -- type parameters in C++ are like fancy macros, but in LF, all parameters are like fancy macros.

This is related to the fact that the new keyword also doesn't mean the same in LF as in these OO languages. In Java and C++, for instance, it is used in an imperative statement that means, "allocate memory on the heap for a new object and initialize that memory by applying the constructor to these arguments which will be determined at runtime," whereas in LF, it is used in a declarative statement that means, "define this variable to represent a specific instance of this reactor class, parameterized by these values which are determined at compile time (or startup)."

Supposing we allow reactor type parameters -- the blurred line between type and non-type parameters is one reason why, when using reactor type A as a parameter to reactor type B, it isn't clear which of the parameters of A should be specified when B is instantiated and which should be specified when B instantiates A.

• It might be nice if we could sort of "curry" the compile-time function that instantiates the reactor class. This would have the advantages of composition as it is used in Java and in functional-style code for code reuse, without the excess generality that can come from composition at runtime. However, it would also open a conceptually heavy can of worms because we don't currently think of instantiation as involving functions, let alone higher-order functions.
• An alternative is to treat the parameters of the reactor class as configuration options that can be overridden in any of several places (where the reactor type is passed around), but then the programmer would have to look in several places to figure out which parameter value is being used. (We already kind of have this problem since parameters all have default values.)
• Yet another alternative is to treat the parameters as config options, but to forbid overriding. The user would still have to look in several places to figure out which parameters remain to be specified.

[cmnrd]

To put it another way -- type parameters in C++ are like fancy macros, but in LF, all parameters are like fancy macros.

I disagree with this statement. I strongly believe that runtime parameterization needs to be supported by LF and should be considered as a core feature. Without it, it will be very tough to compete with ROS, AUTOSAR, etc., as flexible deployment without recompilation is a core feature of these tools. Therefore, I think we should conceptually also distinguish type parameters and runtime parameters in LF (syntactically and semantically). We can then still decide for some targets (like C) that we actually treat runtime parameters as compile-time constants.

This is related to the fact that the new keyword also doesn't mean the same in LF as in these OO languages. In Java and C++, for instance, it is used in an imperative statement that means, "allocate memory on the heap for a new object and initialize that memory by applying the constructor to these arguments which will be determined at runtime," whereas in LF, it is used in a declarative statement that means, "define this variable to represent a specific instance of this reactor class, parameterized by these values which are determined at compile time (or startup)."

In the C++ target (and I believe also Rust) new means exactly what it means in the OO sense (plus a function call to initialize the instance).

t might be nice if we could sort of "curry" the compile-time function that instantiates the reactor class. This would have the advantages of composition as it is used in Java and in functional-style code for code reuse, without the excess generality that can come from composition at runtime. However, it would also open a conceptually heavy can of worms because we don't currently think of instantiation as involving functions, let alone higher-order functions.

But we do. In the C++ target, reactor creation is handled by two functions. The constructor of the reactor class and the assemble() method that is called on each reactor instance. These can be parameterized and from view of the runtime implementation there should be no problem whatsoever to pass reactor instances as parameters to another reactor and build higher level functions.

I think that probably the C target is not the best choice for exploring such features and our OO based targets would provide a more fertile ground. The C++ and TypeScript runtimes can be used standalone. So a good starting point might be to write (simple) demonstrations of what we want to do directly using the runtimes without LF and then consider how we can support this syntactically in LF.

[petervdonovan]

Thanks for all the explanation. I think I see your perspective, and I will think about it.

[cmnrd]

I think another discussion worth having is what we even mean by higher level functions in LF. If all we want to do is provide library reactors that implement a certain pattern while allowing users to specify the precise functionality, then I think all that we would need are function pointers (or lambda functions). In fact, this already works in the C++ target. See the following example:

target Cpp;

reactor GenericWorker<T, U>(worker_function: {=std::function<U(const T&)>=} {{=nullptr=}}) {
  input in: T;
  output out: U;

  reaction(in) -> out {= out.set(worker_function(*in.get())); =}
}

reactor Source {
    timer t(1 sec, 1 sec);
    state value: int{0};
    output out: int;
    reaction (t) -> out {= out.set(value++); =}
}

reactor Print {
    input in: int;
    reaction(in) {= reactor::log::Info() << "result: " << *in.get(); =}
}

main reactor {
    source = new Source()
    worker1 = new GenericWorker<int, int>(worker_function={=[](const int& x) { return x * 2; }=})
    worker2 = new GenericWorker<int, int>(worker_function={=[](const int& x) { return x + 42; }=})
    print = new Print()

    source.out, worker1.out, worker2.out -> worker1.in, worker2.in, print.in;
}

It prints:

[INFO]  Starting the execution
[INFO]  result: 42
[INFO]  result: 44
[INFO]  result: 46
[INFO]  result: 48
[INFO]  result: 50
...

[petervdonovan]

I tried to formalize some of these ideas in this document. Unfortunately the PDF is too long for me to ask anyone to read it in detail, and I have had difficulty purging it of false statements. However, I'll share it now because a month has passed since I promised @lsk567 that I would write it, and because the rate at which I have been finding counterexamples has gone down. The document is also somewhat related to conversations I had recently with @erlingrj.

Related: #1464 (for addition of logical times), #805 (for another reason to place restrictions on what I refer to as smears)

UPDATE: It seems like we might choose elementwise addition of logical times, in which case most of the gnarly, distracting details in the PDF will disappear. (This is being discussed in #1464.) (**EDIT 6/3/23: We agreed many months ago not to use elementwise addition. We are still using the noncommutative addition.)

EDIT: When I wrote "strongly connected component" on page 18, I actually meant "complete subgraph."

EDIT (6/23/23): A quote from Kahn (1974):

A good concept is one that is closed

1. under arbitrary composition
2. under recursion.

[lsk567]

My GitHub notification settings were misconfigured earlier, which made me unaware of all of the interesting discussions here for the past few months...

Overall, this seems to be a very interesting proposal. The proposed type annotations remind me of two closely related areas of research:

1. Behavioral type system in Ptolemy II

This seems to be exactly what you are doing but for Ptolemy II and with specifications written in interface automata. You can definitely get some inspiration from here.

2. Assume-guarantee contracts

Assume-guarantee (AG) contracts are essentially specifications that describe the behaviors of components in a system. Each contract is a pair of an assumption (on the environment) and a guarantee (on the component). In plain English, a contract is essentially saying "if the environment can provide these conditions specified in the assumption, then this component can guarantee these behaviors: ..." AG contracts are usually written in some formal logic. It turns out that if one organizes specifications in the form of contracts, there exist handy operations that enable compositional reasoning by composing or decomposing contracts.

@YuTaiwan and I worked on a course project together two years ago on this topic. We tried to generate contracts for reactor components and perform compositional verification.

Your type system could behave like a contract. For example, a reactor of type DelayedFunction assumes that the environment provides an input and guarantees that an output will be produced some logical time later. Once this contract is specified, we can check the validity of the contract by further analyzing the internals of the reactor. The SMT model that I am working on (mentioned by @edwardalee earlier) could serve this purpose specifically. To prove a functional or timing property at the system level, only the contract needs to be considered and not the specific implementation of the reactor.

Not sure if the above is in line with what you have in mind. Hopefully you find it helpful. :-)

[petervdonovan]

Relationship with tokens/smart pointers

One of the claims made here was that it is desirable and possibly feasible to extract information about the logical time intervals between events on certain elements of programs, such as ports.

Here is another use case for such a thing: if implemented, it would lead to an alternative to the token/smart pointer mechanism with different tradeoffs.

Related: #1526

Motivation

Imagine a Camera reactor that produces one video frame every 100 logical milliseconds.

If the video frame is completely processed in a single timestep, then the rest of the program can re-use the memory on the output port of the Camera reactor for the purpose of accessing the video frame, without having to do any copying or having to allocate more memory. So far so good.

However, if a downstream reactor wishes to use the video frame at a later tag, then it must schedule the video frame into the future. Use cases for scheduling such a large object into the future include

• not stopping the world with one very long tag execution that includes all steps of processing the video frame
• pipelining the processing of the video frame
• giving some components access to a sliding window of multiple consecutive video frames

If I understand, the C target supports such use cases by requiring the video frame to be wrapped in a token, and incrementing a reference count on that token when the video frame is scheduled into the future. Reference counting is a time-tested solution that works well in practice for many important applications.

However, I am under the impression that a reference-counting-based approach is inherently based on dynamic memory allocation. Dynamic memory allocation is a symptom of not having statically checked how much memory we will use. It also tends to make performance less consistent and less predictable than is possible without dynamic memory allocation.

So, it is possible to imagine wanting a "more static" approach that has more predictable run-time behavior, at the cost of requiring more information at compile time.

Idea

The form of lifetime annotations that has been popularized by Rust lets programmers annotate their programs with guarantees that some reference will be valid (i.e., it will not point to freed memory) for as long as some other reference will be valid.

If we can extract information about the logical time intervals between activity in certain subprograms -- for instance, if we can reduce the Camera reactor to an arrow model of this form:

then we can guarantee that a certain reference will be valid for any period that is strictly less than 100 logical milliseconds (right-)plus one microstep.

Example 1

Suppose that a reactor that is downstream of Camera schedules a video frame that it receives from Camera 100 msec and 0 microsteps into the future.

Then the Camera reactor must be given a lifetime annotation that says that its frames must have a lifetime of 100 msec and 0 microsteps.

In this case this version of the Camera reactor only needs one video-frame-sized block of memory, and no token nor reference count is required. The Camera reactor can simply write a new video frame in its memory block every 100 msec, and always pass the same reference to that memory block every 100 msec. It is guaranteed at compile time that after initialization, additional memory will not be allocated.

Example 2

Suppose that a reactor Erode that is downstream of Camera schedules a video frame 100 msec into the future. Then, Erode passes the video frame along to another reactor, EdgeDetector, via an after 0 connection, which introduces a delay of one microstep.

Then the Camera reactor must be given a lifetime annotation that says that its frames must have a lifetime of 100 msec and 1 microstep because (100 msec, 0) + (0, 1) = (100 msec, 1).

In this case this version of the Camera reactor must be compiled down to a reactor that has two video-frame-sized blocks of memory, and when it writes video frames, it must alternate between writing between the first block and writing to the second block. The references that it passes to its downstream reactors must alternate between these blocks.

Example 3

Suppose that a reactor Erode that is downstream of Camera schedules a video frame 1 microstep into the future. Then, Erode passes the video frame along to another reactor, EdgeDetector, via an after 100 msec connection, which introduces a delay of 100 msec.

Then the Camera reactor must be given a lifetime annotation that says that its frames must have a lifetime of 100 msec and 1 microstep because (0, 1) + (100 msec, 0) = (100 msec, 0).

Therefore, this case is the same as example 1.

Further developing the idea

It is possible to ask whether it makes sense to consider giving lifetimes of state variables, it is possible to ask whether it should be permitted for a reactor to mutate one of its outputs without setting it, and it is possible to ask when downstream reactors are allowed to modify their inputs (I understand that this last question has been addressed with our mutable inputs mechanism, but the answer could be different in a slightly different context). However, I have not considered these questions yet because it should first be determined whether any notion of lifetimes in LF is worth investigating in the first place.

[edwardalee]

This is a great idea! I think this could be implemented using the existing token mechanism. In fact, it's not quite the case that the reference-counting-based approach is inherently based on dynamic memory allocation. With the token mechanism, you can provide your own constructor, copy-constructor, and destructor (the mechanism only needs pointers to the latter two functions). These need not be based on malloc/free. If you know a bound on the number of instances that can coexist, then you can statically allocate the required memory. You could even write the constructor and copy-constructor to handle violations of the bound in some application-specific way.

The pattern you describe would be a great addition to the growing collection of examples we have in the examples repo. Right now, you would have to derive the bound manually. But as you say, we could derive it automatically and store it in the port struct. Be careful, however, because the bound depends not only on what is downstream of a reactor, but also on how many instances of the source reactor you have.

But I think that today, we would still have to use malloc to allocate the memory. The difference is that it would be done exactly once, in a startup reaction, to be freed in a shutdown reaction.

Is a one-time malloc an adequate solution? I'm not sure, but we are already using this pattern extensively in the C target. It would be good to understand why this is not a good pattern before putting a lot of effort into replacing it.

The reason for this pattern is that Currently, a reactor has no way to define instance-specific static code. Perhaps we could have an instancepreamble, a chunk of code generated for each instance of a reactor. Perhaps these could be put into separate .c files so they could define file-scope static variables. This would not scale well, however.

Another alternative would be for each instance (rather than each reactor class) to have its own typedef for its self struct. I don't think this would scale well either.

[petervdonovan]

These need not be based on malloc/free. If you know a bound on the number of instances that can coexist, then you can statically allocate the required memory.

Ah, I get your point. I guess it would have been more accurate for me to say merely that reference counting becomes superfluous in the presence of sufficiently advanced static analysis. But the observation that it is compatible with this mechanism is helpful for avoiding breaking changes.

But as you say, we could derive it automatically and store it in the port struct. Be careful, however, because the bound depends not only on what is downstream of a reactor, but also on how many instances of the source reactor you have.

Well, I guess this depends on whether the memory is allocated globally vs. on a per-reactor basis. By the way, I had imagined this as being implementable by specializing reactor classes according to required lifetimes of their outputs, kind of like how we specialize generic reactor classes according to their concrete types. But this is not essential in order to turn the allocations and frees into a one-time malloc.

Is a one-time malloc an adequate solution? I'm not sure, but we are already using this pattern extensively in the C target. It would be good to understand why this is not a good pattern before putting a lot of effort into replacing it.

I personally am not highly motivated to try to replace it right now. I would not invest a lot of time into thinking of ways to avoid one-time malloc without talking to other people first.

IIRC Martin Schoeberl might have mentioned that cache analysis tools need to statically know exactly where data will be in memory, and that one-time malloc might not provide that knowledge (I should check with him). I think Erling may have mentioned that if memory is static and the target platform has insufficient memory then there can be a compiler error, which can be easier to debug than loading a program onto a microcontroller and then finding out that (for some reason) it does not work.

[cmnrd]

It is a great idea to consider the connection between our notion of logical time and the lifetime of objects (I would be very curious to see how a Rust like language would work if it has a logical lifetime concept built in). However, I have some concerns with respect to the proposal laid out here.

Edward already pointed out that tokens are not inherently connected to dynamic memory allocation. The same is true for smart pointers in general. First and foremost, smart pointers allow to model ownership of data. Knowing about ownership, it becomes possible to also free memory that is not owned but anyone (kind of like garbage collection). This, however, is only a secondary concern. The STL smart pointers use dynamic memory allocation by default, but they are not limited to that. In fact, you can pass a raw pointer to any object (independent of if and how it was allocated) to std::unique_ptr and it will manage this pointer for you. To customize how the pointer is deleted, std::uniqe_ptr has a template argument Deleter. In principle, this allows you to implement custom allocation strategies, and a very simple strategy would be to just use statically allocated memory and to not delete anything.

It is not quite clear to me what the motivation is here. Are you concerned about performance in general? Or is this more about memory constrained platforms and time predictability? I have experimented with using memory pools to speed up the allocation of "tokens" in the C++ target, but to my surprise this performed much worse than the default fully dynamic strategy. After reading up a bit on this topic, I found that malloc/free is heavily optimized and its hard to beat this with other strategies. malloc is only slow and unpredictable if memory tends to get heavily fragmented. However, in applications like the one you describe, the allocation pattern is very regular. Even without any lifetime annotations, an malloc/free based implementation is very likely to give you the desired behavior. If you always free a block of size N and then allocate a block N, malloc will likely just give you the block that was just freed (or maybe one out of a pool of N sized blocks). It is very tough to beat that in terms of performance. Predictability, of course is a different concern. But before we think about solutions for this, I think we should look for evidence and measure the range in which malloc varies on an embedded device. My conjecture is, that it is not too bad for programs with regular execution patterns (i.e. that are mostly driven by timers).

I am also concerned with respect to composability. I think it is generally a bad idea to make the behavior of one component dependent on the components that are connected to it. Maybe a better angle would be to think about this in terms of guarantees. A reactor Camera could make it part of its contract that it produces a frame every 100ms and guarantee that this frame is valid for a while, but only until the next frame is produced. Then it is the responsibility of the surrounding context to consider this contract. This, however, we can already do with the tools we have. The camera reactor could make the frame just a state variable and pass a pointer to that frame to the receiver. The receiver could use this pointer, but only until a certain tag.

Now we tell our users not use raw pointers. And with the approach that I laid out in the above paragraph it would be difficult to verify that no one violates the contract. However, I think the same would be true with the lifetime approach. How would you guarantee that no one uses a reference to some data after its lifetime exceeded? To me, Peter's description sounds very much like sending raw pointers in disguise and there is not much of a guarantee one can give in C.

Generally, I am under the impression that this is trying to solve a problem that is better solved by domain experts. Engineers working with a certain platform know best how to allocate memory on this platform. Also predictability is a very application specific concern. So I find it would be better to give users the tools to build their custom solution, instead of trying to have a LF solution that then likely would not fit all the use cases.