ssm-lang / scoria Goto Github PK

Having a size of 8192 means that we necessarily have at least 8192 repeated entries in the log before we encountere a contqueue full error. Can we consider dropping the queue size down to 128 or something so that the event trace is somewhat more easily auditable?

We already know the entry point of the SSM program based on what is passed to compile. And that entry point should be invoked in the C main function to put it in the continuation queue, before calling tick for the first time.

There are two related questions to discuss:

1. Where should the main function be? Should it be generated from the Haskell codegen, as we currently do for the trace platform, or should it be part of the platform code? I'm an advocate for the latter approach, since there's a lot of platform-specific boilerplate involved, but relatively little SSM program-specific information.

2. What should the interface to the SSM entry point look like? As in, what should its type signature be? The simplest answer would be to keep it as SSM (), which is what compile already expects. But this doesn't support any kind of arguments or return value, which are primitive but valuable ways of interfacing with the environment.

Follow on from #32 --- I patched up the generated code to only use C's unsigned ints, for which we can rely on reliably wrapping around on overflow, but the matter of what happens with the Haskell-side interpreter is another matter. In particular, overflow for Int seems to be undefined no matter what. We're not encountering any failed test cases yet, but we should account for this at some point, with some bounds checks, or by converting all arithmetic to take place with Integer and perform the wraparound ourselves.

Running stack test --profile shows that while the tests are executing, more than 36% of the time is spent in the mainland module, which is responsible for generating the C code. Since every test is generating code it makes sense that it would show up in the profile, but I am not sure if this is a lot or not. I would generally expect many of the other things we do to take a lot of time (writing files, moving files, running the interpreter etc).

It would be interesting, when we have time, to see if we can figure out exactly why so much time is spent generating C code.

There are a lot of expressions which should be easily, statically shrunk into constants. I'm not really sure what is gonig on with the shrinker right now but all the massive expressions really clutter up what could be smaller test cases.

If we want to fiddle with the event trace for coarser grained testing (e.g., only containing externally-visible events to accommodate optimizations), we might want to tidy up its definition and clarify its interface/the behavior it entails about a running program.

There are a few things I had in mind:

• Right now, we are juggling between two different String representations of traces, i.e., what the C program prints out, and what the Show instance of Output looks like. We currently use a parser to convert from the latter to the former, and don't have any mechanism for dumping an OutputEntry to what a line should look like in the running C program. There are two ways to fix this: (1) overload the Show instance for OutputEntry instead of deriving it, to essentially do the opposite of what the parser is doing; or (2) adjust what the C runtime is printing to match what the Show instance looks like. I'm personally in favor of the latter since it means we can just read instead of using a separate parser.

• Right now, the semantic equality comparison procedure lives in a PropertyM monad in Test.Ssm.Output, with some ad hoc diff generation. It should live outside of that monad, like it did before, but instead of just returning a Boolean indicating equality, it should return a Maybe Diff, where Nothing indicates equality and Just d indicates inequality with d containing all the information the PropertyM monad needs to report the information to the test driver.

• There's a test input list still living in the Trace.hs file, which was used for testing. This should probably be placed somewhere else, perhaps in a separate test suite specific to checking basic things about the trace (e.g., the parser, if we still we still need it, as well as some higher level properties about what it means for two traces to be equal.

I feel like perhaps it's a little big & messy right now, even if it works and there's a thought behind everything. SSM/Interpret/Internal.hs is like 1k loc. I am not sure how it could be improved without sitting down and looking at it for a few hours.

So there are two defines that define the max size of the event queue and the continuation queue. In the interpreter, I have simply copied over the constants, but if we want to change these sizes we need to change them in both places. It would be ideal if this could be specified in just one place, perhaps.

There should be a uniform interface for assertions, debugging, and emitting traces, that is used across the generated C code and the platform-generic runtime, but that has a platform-specific implementation. This is useful because each platform might have a different way of logging information (or may even ignore debug statements altogether if not applicable).

A related interface should exist within the Haskell interpreter, to support emitting an Output trace from a program, or for just evaluating it purely.

This all involves some slight code reorganization, but first requires us to figure out what the interface should look like. I like the idea of splitting this interface into 4 levels:

• ERROR: used for reporting errors, and terminating execution. Should take the place of any asserts we currently have.
• WARN: used for indicating any critical issues detected, but without immediately terminating. I don't currently see where this would be useful yet, but it seems in line.
• INFO: this would be used to log information that may be useful to the user when running a program in simulation, e.g., to selectively report the internal information throughout execution.
• TRACE: this would be used to log information that is used to produce event traces for property-based testing. The difference between this and INFO is that this level should define a rigit set of primitives, designed to produce output that can be parsed into an event trace, wheras INFO should be used for printing arbitrary strings and other such information.

All these will take the form of macros, to ensure that they are zero-cost when not needed. the ERROR, WARN, and INFO macros should all take a variable number of arguments and support printf-style formatting.

WARN and INFO will essentially be print statements, i.e., WARN("this should have your attention: %d\n", x) and INFO("some potentially useful debug information: %d\n", x).

At the ERROR level, we should have ERROR("this is bad: %d\n", x), which prints the error and quits (similar to Linux's BUG macro) , and ERROR_ON(condition, "that error condition was met: %d", x) (similar to Linux's BUG_ON).

For TRACE, we should start with one primitive per notable event in the event trace. Since we expect the output to be in a parseable format, the formatting of each primitive should all be defined in one place (rather than scattered throughout the runtime implementation and generated code). The TRACE primitives should all be #define TRACE_WTV do {} while(0); for non-trace platforms.

Currently, stack is using the manually modified ssm.cabal to construct the build plan. This is not an immediate issue, but it is a bit concerning that stack.yaml and the generated ssm.cabal have now drifted apart. In particular, stack.yaml still points to the src/ directory, which contains some unused code.

The easiest thing to do is just to delete ssm.cabal; stack still works without. We can also consider committing to stack entirely; not having to declare exposed-modules and having stack infer them is nice, but not a must-have.

Box works like this: We have some code, code, which represents some function body. When we write a function such as

f x = code

when we evaluate f x, we get a hold of the statements that make up the functions body. There is nothing in the emitted code that says that this should be a separate procedure that can be invoked.

body-stmts

When we instead define our function like this:

f = box "f" ["x"] $ \x -> do
  code

box helps us by making it explicit that this is a procedure, by inserting some extra meta-statements in the code that delimits the procedure scope.

Procedure "f"
Argument "x" {- and the concrete value it was applied to -}
body-stmts
Result ()

This is nice as we can now 'call' procedures in the generated C code, while having the Haskell code still look like any normal function application. The alternative would be to define some type of functions, and having a special app :: (a :-> b) -> a -> b combinator for applying functions to arguments.

One kink about this is that if you try to generate code for a recursive function, you will never terminate. At each recursive application we will run into the entire functions definition again.

f = box "f" ["x"] $ \x -> do
  fork [ f x ]

becomes

Procedure "f"
Argument "x"
Fork [ Procedure "f"
       Argument "x"
       Fork [ Procedure "f"
              ...
              Result ()
            ]
       Result ()
     ]
Result ()

While we have now gained a very pleasant way of defining and applying functions, we end up with an infinite program instead. To combat this, we have defined a second datatype to represent programs, which uses a different set of statements. For instance, the constructor for fork in that AST is simply Fork :: [(String, [(Either SSMExp Reference)]] -> Stm. It is not recursive at all, and simply represents that we wish to call a function with this name with these arguments, which can be either expressions or references. The types of these arguments are also recorded.

While we do the transpilation from the initial, infinite datatype to this more flatter one, we also produce a map funs :: Map String Procedure. Procedure looks like this:

data Procedure = Procedure
  { -- | Name of the procedure.
    name      :: String
    -- | Parameter names and types of the procedure.
  , arguments :: [(String, Type)]
    -- | Statements that make up this procedure.
  , body      :: [Stm]
  }

This map simply maps function names to their definition. When a program is later turned into a C-file, every procedure in this map is compiled to a C procedure, and at fork sites an ordinary procedure call is generated.
This map is touched at every fork statement by checking the first statement of the forked code (which should be a Procedure n meta statement). If the name in the Procedure constructor has not been seen before, the body of that function will be recursively transpiled and then turned into a Procedure value, and then an entry will be made in the map to reflect that we have now seen and recorded this function. If it has already been seen, we do nothing.

Now comes the issue of polymorphic functions. If we write this function:

f :: Ref a -> Exp a -> SSM ()
f = box "f" ["x", "y"] $ \x y -> do
  x <~ y -- assignment

what code should we generate? When we assign values to references in the generated code, we need to specify the type of the thing we are assigning a value to. Here we are writing a polymorphic function that can be applied at any type, so which type should the generated code talk about? The issue is that we have no way of being polymorphic in the generated code, so this can not be done.

Monomorphization

Monomorphization is a compilation technique where the type at which a function is applied is recorded, and if that function is polymorphic, a specialized version of the function is made. This pleases the type checker.

id :: a -> a
id x = x

f = id 3
g = id True

-- after monomorphization becomes
idint :: Int -> Int
idint x = x

idbool :: Bool -> Bool
idbool x = x

f = idint 3
g = idbool True

After this transformation there are no polymorphic functions left in the program. The price we pay is that we now essentially have two identical functions that we need to generate code for, which will occupy our precious, scarce memory on our IoT devices.

If this is a price that we are willing to pay, I believe we can make this happen very easily. The only thing we need to do is to change box to also accept a list of Types, to reflect the type of the application. We already have a typeclass SSMType that has a function typeOf :: proxy a -> Type, which marshals a Haskell type to the corresponding representation in our EDSL. If we now change box & Procedure to behave like this:

-- | I want to emphasize again that the box crap can probably be generated by a plugin, so hopefully our end users won't have to worry about this.
f :: Ref a -> Exp a -> SSM ()
f = box "f" [typeOf (Proxy @a), typeOf (Proxy @a)] ["x", "y"] $ \x y -> do
  x <~ y -- assignment

Two applications of f would then produce different code if the types of the arguments are different, while the code is still the same if the types are the same.

x <- var 0     -- Ref Int32
y <- var true' -- Ref Bool

fork [ f x 5
     , f y false'
     ]

-- the generated code would look like this
Fork
  [ [ Procedure "f" [Ref TInt32, TInt32]
    , Argument "x" {- some val -}
    , Argument "y" {- some val -}
    , SetRef "x" (Lit TInt32 (LInt32 5))
    , Result ()
    ]
  , [ Procedure "f" [Ref TBool, TBool]
    , Argument "x" {- some val -}
    , Argument "y" {- some val -}
    , SetRef "x" (Lit TBool (LBool False))
    , Result ()
    ]
  ]

When we transpile the above statements to the flat version which replaces the recursive Fork constructor with the non recursive one, we currently only inspect the name of the procedure to determine if we've seen it before. Now I suggest that we also check the type of the arguments to the procedure. If the (name, [type]) pair has not been seen before, specialize a new version of the function and put it in the map, otherwise, just do nothing. The name of this specialized version would be "f" and some generated suffix, to make it distinct from the other versions of f. We can derive a simple name from the types to reflect the type in the name.

This is a simple change that would make it specialize functions by itself, with the machinery that is already in place. We do not need to add a separate compiler pass or anything. Function applications in Haskell still are polymorphic, but behind the scenes, functions would be specialized. In #19 I wrote a bit about polymorphic functions and how we can not write polymorphic programs currently.

A big enhancement with embedding a language in Haskell as opposed to writing a custom compiler frontend is that we can piggyback on the type system in place. Being restricted to writing monomorphic programs would be a real shame. Making use of Haskell's polymorphic type system is a killer feature that we would want.

Moving this discussion here:

On our call last week, @Rewbert and I found that the frontend was encountering some type errors when it came to "inferring" the type of integral instances. The code is here: https://github.com/Rewbert/ssm-edsl/blob/6e632e049a9332bb574f78f487f4d2a222f06922/edsl/Core.hs#L129 :

instance Num SSMExp where
  -- ...
  fromInteger i = if T.typeOf i == T.typeOf (1 :: Int)
                    then Lit TInt   $ LInt   $ fromInteger i
                    else Lit TInt64 $ LInt64 $ fromInteger i

This was trying to work around the lack of a type parameter in the SSMExp data type, and infer the appropriate SSM literal constructors to use when promoting Haskell integeral literals into the EDSL. However, typeOf only knows as much as Haskell's type system does, so in fromInteger, the parameter i appears as an Integer and nothing else. So this code would only ever hit the else branch, converting all integer literals to i64s.

We discovered this when we changed the implementation to this, while refactoring:

fromInteger i = Lit TInt64 $ LUInt8 $ fromInteger i
fromInteger i
  | T.typeOf i == T.typeOf (1 :: Int)   = Lit TInt   $ LInt   $ fromInteger i
  | T.typeOf i == T.typeOf (1 :: Int64) = Lit TInt64 $ LInt64 $ fromInteger i
  | T.typeOf i == T.typeOf (1 :: Word8) = Lit TUInt8 $ LUInt8 $ fromInteger i
  | otherwise                           = error $ show $ T.typeOf i

Doing the principled thing and matching explicitly on each expected type revealed that typeOf is just not the right thing to use here.

This test case fails after 622 trace items, as the event queue in the C-code runs out of capacity before the interpreter does (it does it after 624 trace items). I am logging this here for now as I believe this will be easier to test once we can comfortably run tests with different queue sizes (issue #13), which I think Yalu is working on currently.

prettyprinted program:

entrypoint:
  fun1(ref6)

fun1(*int64 ref6) {
  *int v1 = var (-(130 * 198))
  after 1886 then ref6 = 1
  after 3617 then v1 = 49
  wait [ref6]
  fork [ fun1(ref6)
       , fun1(ref6)
       , fun1(ref6)
       , fun1(ref6)
       , fun1(ref6)
       ]
}

Haskell source file to run test again

module Regression.Test1625657491075Spec where

import Data.Map (fromList)
import SSM.Core.Syntax
import qualified Test.SSM.Prop as T
import qualified Test.Hspec as H
import qualified Test.Hspec.QuickCheck as H

p :: Program
p = Program {entry = "fun1", args = [Right ("ref6",Ref TInt64)], funs = fromList [("fun1",Procedure {name = "fun1", arguments = [("ref6",Ref TInt64)], body = [Skip,Skip,Skip,NewRef (Fresh "v1") (Ref TInt32) (UOpE TInt32 (BOp TInt32 (Lit TInt32 (LInt32 130)) (Lit TInt32 (LInt32 198)) OTimes) Neg),After (Lit TUInt64 (LUInt64 1886)) ("ref6",Ref TInt64) (Lit TInt64 (LInt64 1)),After (Lit TUInt64 (LUInt64 3617)) ("v1",Ref TInt32) (Lit TInt32 (LInt32 49)),Skip,Skip,Wait [("ref6",Ref TInt64)],Skip,Skip,Fork [("fun1",[Right ("ref6",Ref TInt64)]),("fun1",[Right ("ref6",Ref TInt64)]),("fun1",[Right ("ref6",Ref TInt64)]),("fun1",[Right ("ref6",Ref TInt64)]),("fun1",[Right ("ref6",Ref TInt64)])],Skip,Skip]})]}

spec :: H.Spec
spec = T.correctSpec "Test1625657491075" p

So in order to detect cases where the continuation queue gets full I need to perform checks. The eventqueue gets populated either by forking processes explicitly or by the RTS performing updates via scheduled events. To be able to detect that there's no more room for continuation while performing events, I had to modify the tick function in peng-scheduler.c. Perhaps this whole function should also be generated alongside the rest of the program?

To enable us to do better statical analysis of the code base further down the road, I think we should make the core statements more fine-grained. As much as possible should be explicit.

• I have a few suggestions right now:
  • I suggest we remove NewRef and instead compile that into a sequence of a new statement CreateRef, followed by the existing statement SetRef.
  • We should remove the implicit yield from Fork & Wait by adding a Yield :: SSMStm statement.
  • We should split Wait :: [Reference] -> SSMStm into the two statements Sensitize :: Reference -> SSMStm & Desensitize :: Reference -> SSMStm.

If we apply the last two changes we can e.g write an optimization pass which translates

While c
  Code1
  Sensitize a
  Yield
  Desensitize a
  Code2

into

Sensitize a
While c
  Code1
  Yield
  Code2
Desensitize a

This should be a separate issue, but just for some motivation. This issue only concerns making the core syntax more fine-grained.

the way we are currently using the priority and depth, we are evenly distributing the priorities among the forked children.

However, I would imagine a common pattern would be something like this:

main =
  fork outputHandler | actualMain

where most of the interesting stuff starts in actualMain (e.g., forking more processes), while outputHandler is just a leaf process that evaluates output. This means that half of the priorities are effectively wasted on outputHandler.

Is there a better way to distribute the priorities among children, if we know that a process is a leaf process? (tagging @sedwards-lab since he came up with the original approach)

Test cases named using solely their timestamp should be renamed and thoroughly documented, because otherwise they aren't exactly helpful (especially since some of these aren't shrunk as far as they could have been). If the documentation eludes us, then we should just delete these.

This is my bad, I should have set a better precedent when I started building the test suite.

A related nice-to-have would be to improve the regression test naming scheme, and use something more pronounce-able than UNIX timestamps (though it should still be random enough that we could rely on their uniqueness for future parallel testing/CI)

The testing framework currently inspects stderr to figure out if running the c-code went alright, but we might want to use this stream for logging down the road. We should change the testing framework to use error codes instead and not rely on the stderr stream.

@sedwards-lab and I came across this issue when refactoring the runtime. We temporarily changed the debug statements to empty statements, meaning the program shouldn't actually print anything. This led to unexpectedly optimistic results reported by the regression test suite, with most test cases "passing".

I think this is caused by the fact that the length of the compiled program's execution trace is capping the length of the interpreter's trace. This cap was added to prevent the interpreter from running forever, but it also means that if the compiled program prints nothing, the interpreter will yield nothing, leading to misleadingly vacuous equivalence.

I'm marking this as wontfix because we will only encounter this if we make any changes that removes the compiled program's output entirely, but I'm noting this anyway because it may lead to some really misleadingly positive test cases, e.g., if we run tests with an incorrect platform that produces no output.

The more I think about this, the more it seems unnecessary. The original thought was to keep the build directory strictly free of .c files, and only stick other build artifacts in there, but that just makes it really confusing because now we have to worry about putting generated .c files in a separate genc directory.

Also, when I showed @sedwards-lab he expressed concern about this making the build directory structure more complicated than it needs to be, and after mulling on this I agree (especially as I'm thinking about how to support out-of-tree builds, toward #12).

@sedwards-lab and I discussed producing a compiler user interface that isn't strictly tied to the directory structure of this project. Something similar to how Linux kernel modules are organized, i.e.:

$ ls
Makefile
mymodule.c

Where Makefile registers mymodule.o , and includes the Linux kernel source's main Makefile (which should be installed on the machine where this build is taking place).

With make build systems developed in #11, we are most of the way here, though we'll also need to figure out an interface to speak to the SSM compiler (i.e., invoking stack run or some command which gets us to app/Main.hs).

This is a pretty critical issue because we want to be able to rapidly develop interesting examples without being mired in the details of the (continuously shifting) project structure.

What e.g output 1 does is to record the information that output pin 1 has been requested, and to create a reference that can be used to write to the output handler. The call returns this reference along with this output handler, that has to be scheduled in order to actualize the output. The output handler is hand-written by us right now and is just expected to exist.

We have a lot of functionality in the compiler to perhaps hack together a better interface for doing this, where most of the stuff is done in scoria. We do need some FFI, however.

-- This is the actual output handler that will actualize the output
outputHandler :: Ref Bool -> SSM ()
outputHandler out = routine $ do
  while true $ do
    wait out
    ffi "enable_gpio" $ deref out    -- need to be able to do some FFI here, and
                                     -- preferably in some way that is portable across platforms/backends
                                     -- this does right now not specify which GPIO to activate, see comment in program

{- This is the main SSM program, which is written in the same style as before.
   It will blink the LED with a 1 second period. -}
main :: (?out :: Ref Bool) => SSM ()
main = routine $ do
  while true $ do
    after (secs 1) ?out true
    wait ?out
    after (secs 1) ?out false
    wait ?out
  
program :: Compile backend ()
program = do
  {- where the current machinery is expected to create a global reference and associate
     it wil the GPIO, we already support creating global references here. We can try to
     create a global reference like this and associate it ourselves. -}
  out <- global @Bool
  let ?out = out
  
  {- now, what is left to do is to associate the reference with the pin in question.
     Perhaps this can be done with the reference? I am not sure what is the best, simplest,
     most portable way. -}
  schedule $ outputHandler out
  schedule main

A moonshot idea that we are very, very far away from even attempting, but I wanted to leave a note of it here. It would be really cool to have some kind of mechanism for reliably hot-loading code in real-time, onto IoT devices, instead of having to flash them. Kind of like Erlang, but for SSM, on embedded devices.

The shrinker is already really great, and it's producing some excellent counterexamples to populate our regression test suite (thanks @Rewbert !). But it could be even better:

• There are a lot of skips in the generated code that can should be easily pruned out.
• For a lot of the test cases, the values don't actually matter---can we try to replace more complicated expressions with constants where possible? And can we try to replace constants with smaller constants (so it's not just a syntactically smaller test case)?
• Can we try to simplify the types? For instance, if a test case fails with an Int32, does it still fail with a UInt32? And what about a Bool?

I guess the overall theme of this PR is about being more flexible with what constitutes a "smaller" test case---I believe implementing the above may lead to even more intuitive test cases (right now, the test cases are small enough to understand but still require some manual doctoring to be self-explanatory).

I realize that we talk about I/O implementation as somehow one topic, but the implementation for input vs output turn out to be rather orthogonal. Thus, I'm starting this issue to specifically discuss output variables (and will open another issue to discuss input variables when the issues arise).

We want SSM programs (and their generated code) to be I/O agnostic, but it leads to this question: what should the behavior of the following program be:

f :: Ref Bool -> SSM ()
f o = do
  o <~ False

g :: Ref Bool -> SSM ()
g o = do
  o <~ True

m :: Ref Bool -> SSM ()
m o = fork [ f o, g o ]

Within SSM's semantics, o should have the value True at the end of the instant where m is called (assuming nothing else assigns to o), since the priority of g is lower than f due to how the two child processes are forked by m.

However, it's somewhat unclear what the behavior should be if o is an output variable. If we were to naively overload the assignment operation and eagerly transmit its value to the external environment, the environment would briefly see a glitch value of False before seeing the value settling to True, even though the semantics of the language say that these updates are happening at the same logical time. Worse, if the output variable has stream/continuous semantics (e.g., it represents a socket file descriptor), both False and True would be emitted (rather than overwriting one another), apparently at the same time.

(Note, though, that this does not happen for delayed assignments, because SSM's semantics specify that there can be at most one scheduled update in the event queue for each scheduled variable.)

To me, the intuitive behavior of only emitting True at the end of the instant suggests to me that we should take a "lazy" approach to output, where the intra-instant updates are accumulated in the scheduled variable, and only emitted at the end of the instant. But this incurs more latency than necessary, especially in the presence of long-running, lower priority continuations; that latency is less than desirable for a real-time language.

A more extreme option is to make instantaneous assignments to output completely non-effectful, which I am interested in entertaining. After all, what does it even mean to instantly compute and emit output?

Only being able to use expression values in operators is not only inconvenient, but also limiting. For example, runtime/examples/clock.c has a while loop condition on an event variable. This currently cannot be expressed by the edsl.

I would like a statement in the EDSL that allows us to inject arbitrary C statements into the generated C code. This would be extremely useful for platform-specific debugging and prototyping. For instance, we can insert escStm [cstm|printk("hello\r\n");|] to insert a printk statement.

For the purpose of testing, these statements can be left out of the trace build (we can make a pass that prunes these out of the AST before feeding it to the backend).

The EDSL doesn't say anything about expressions having anything to do with scheduled variables, but still the code generator generates C code where expressions are compiled to scheduled variables. E.g sv_int_t can be compiled to an ordinary int instead.

It would be nice if we could have a type checker of SSM.Core.Syntax programs. This would be handy when I am implementing the shrinking stuff, to make sure that a shrinking step doesn't produce an illegal program. Any program should be type-safe both before & after shrinking.

It would be quite a simple exercise, as the language has no polymorphic types or anything fancy like that. It would just be a simple check/inference.

With an EDSL, implementing derived combinators from the primitives becomes very easy. If we can think of some nice derived operators to showcase in the August paper, that would be nice. The first candidate (stolen from Stephens paper) is the waitAll combinator. wait waits for any of the references to be written to, while waitAll will wait for all of them to be written at least once.

-- | Wait for all the references to be written to
waitAll :: [Ref a] -> SSM ()
waitAll refs = fork $ map waitSingle refs
  where
      waitSingle :: Ref a -> SSM ()
      waitSingle = box "waitSingle" ["r"] $ \r -> wait [r]

Another simple combinators is a simple delay, which behaves similarly to a conventional sleep function.

-- | Delays the current process for t 'ticks', essentially the same as sleep
-- for conventional threads.
delay :: Exp Word64 -> SSM ()
delay t = fork [delayprocess t]
  where
      delayprocess :: Exp Word64 -> SSM ()
      delayprocess = box "delay" ["time"] $ \time -> do
          r <- var false'
          after time r true'
          wait [r]

Another pattern that I think might be useful to make a combinator for is that of alternating a reference between two values (e.g blinking a led with a set interval).

-- | Alternates between two values on a reference
alternate :: Ref a -> Exp a -> Exp a -> Exp Word64 -> SSM ()
alternate = fork [ alternateprocess r v1 v2 time ]
  where
        alternateprocess :: Ref a -> Exp a -> Exp a -> Exp Word64 -> SSM ()
         alternateprocess = box "alternate" ["r","v1","v2","time"] $ \r v1 v2 time -> do
               while' true' $ do
                   delay time
                   r <~ v1
                   delay time
                   r <~ v2

This can naturally be generalized to a more general cycle primitive which does the same but for a sequence of values. We can not implement this yet, as we need to add support for lists to do that.

-- | Given a reference and a set of values, and a delay, cycle through the
-- values at the given interval. Starts all over when reached the end of the
-- list of values.
cycle :: Ref a -> [Exp a] -> Exp Word64 -> SSM ()
cycle = undefined

With this, alternate in turn just becomes a specific case of cycle.

alternate :: Ref a -> Exp a -> Exp a -> Exp Word64 -> SSM ()
alternate r v1 v2 t = cycle r [v1,v2] t

Now we see another pattern that we could perhaps abstract away (but that would be mainly for our own sake, not for the end programmer). These derived combinators all define some procedure that does the work and issues a fork call to that procedure. I am not sure how to generalize it right now, since we pass in the procedure & parameter names, but maybe it's something we can look at in the future.

@j-hui mentioned a combinator that would make allocation and deallocation of a resource explicit. The idea is that we want to fork a process that allocates some resource, passes that resource to additional processes that operate on them, and then deallocates the resource. Very similar to these C patterns:

void f() {
  char buffer[64];
  doSomethingWithBuffer(buffer);
  return;
}

void g() {
  int fd = open(...);
  foo(fd);
  close(fd);
}

I don't think we can derive such a combinator right now, but it's interesting to look at. It would surely be a very handy combinator for handling memory resources etc when we are developing IoT applications. I sketched this rough code up yesterday:

-- | If we can somehow create and destroy a value, maybe it can look
-- like this? If `create` does anything special that needs a nice
-- teardown, that work can be done by `destroy`.
class SSMType a => Resource a where
    create  :: proxy a -> SSM (Ref a)
    destroy :: Ref a   -> SSM ()

-- | Simple dummy-instance for int, which is not so exciting. Perhaps
-- a more interesting example could be opening/closing a file instead.
instance Resource Int32 where
    create _  = var 0
    destroy r = return ()

-- | Need to use forall a to make the a in `superviseprocess` the same as
-- the a in supervise.
supervise :: forall a . Resource a => [(Ref a -> SSM ())] -> SSM ()
supervise procs = fork [ superviseprocess procs ]
  where
      -- | We can not generate code for this procedure yet. What type is
      -- the `a`?
      superviseprocess :: [(Ref a -> SSM ())] -> SSM ()
      superviseprocess procs = boxNullary "superviseprocess" $ do
          -- allocate the resource
          v <- create $ Proxy @a
          -- hand the resource over to the other processes
          fork $ map ($ v) procs
          -- release the resource
          destroy v

As my comment says, it's not possible to generate code for superviseprocess yet. Not sure what the best way to go around this is. Specialization? @koengit ?

I've not verified this but I think I thought of a case where names in the core syntax representation generated by the frontend might be duplicated. In different scopes, so it's still valid w.r.t types, but the whole point of generating names is to generate unique names. We don't want to overshadow anything.

Opening for visibility in case anyone has anything else to add!

John and I discussed having dedicated time types for the frontend for specifying time durations in statements like after.. something like (5 :: Ms) which then generates 5 * SSM_MILLISECONDS.

Before changed was changed from SSM (Exp Bool) to Exp Bool I had collected some 30 tests that failed in a regression test suite. Changing that internal representation of the AST broke the syntax of all those tests.

It seems like @j-hui s changes in #11 automatically spits out regression tests if it finds a failing test case. I documented all the bugs I found and what I did to fix them, so a simple but maybe slightly time-consuming thing to do is to just backtrack and remove one fix at a time, and have QuickCheck automatically find the bug and generate the regression test for us. Sounds bad but it's definitely way quicker than manually rewriting the test cases.

It occurs to me that we don't yet have this in the EDSL. This is useful for sending pure events between processes, and should probaby be available in our language in time for the REBLS paper.

The memory leak we discussed at the meeting, I just remembered that I have not implemented the patch in the code generator yet. I'll leave this issue here as a reminder to me to take care of it tomorrow.

The references we have can schedule events and react to events, but they can not interact with anything outside of the scheduler. We need to add another type of reference that carries some extra information, a smarter reference. To the programmer this should look identical to any other reference.

LEDs

import LedLibrary (greenLed)

flipLed :: SSM ()
flipLed = boxNullary "flipLed" $ do
  led <- greenLed -- led :: Ref Bool
  v <- deref led

  ifThenElse v
    (led <~ false')
    (led <~ true')

In the above example we use the LED just as we would any other reference. The only difference is that instead of getting access to it by having it passed to us as a parameter, or creating the reference by using var, we get access to the reference from a module that we import. This module has an SSM (Ref Bool) function that knows how to create the smarter reference.

A simple strategy is to create a variant of references that can carry extra code that is simply inlined when e.g an assignment is done to the variable, but I don't think this is enough. If we schedule an update on a reference, the side effect should be performed when the event occurs as well. When the scheduler applies events, the scheduler only knows that the thing receiving the update is an sv_t*, nothing more. We do need to add additional functionalities to the sv_t* struct, like a pointer to a function, so that having access to an sv_t* is enough to gain access to the side effects.

Buttons

For buttons we need to react to events rather than producing them.

import ButtonLibrary (getButton)
import LedLibrary (greenLed)

listenClick :: SSM ()
listenClick = boxNullary "listenClick" $ do
  -- fetch and disable LED
  led <- greenLed
  led <~ false'

  -- fetch button 1 and wait for 3 clicks on it
  but1 <- getButton 1
  wait [but1]
  wait [but1]
  wait [but1]

  -- enable LED
  led <~ true'

Simply executing getButton 1 should be enough to get a reference that can interact with the HW button. Furthermore, this should be enough to tell the compiler that it has to install a callback on the actual HW button so that the above-mentioned reference gets an event when the button is clicked. This callback should be installed in the main function before the scheduler takes over.

Even though the underlying value in the runtime system will be a reference to something smart that carries this extra information, the Haskell API should not reflect that anything is strange. E.g representing a LED state as a Bool might be very appropriate, in which case the Haskell code should only have to talk about Bools.

A programs entry point can no longer accept any arguments (there must be some nullary main-like function). There are still some remnants of the old system though, where there could be arguments. There's a field arguments in the Program type, for instance. If anyone else wants to do this, let me know and I'll write down some more details of exactly which changes needs to be made.

This is more of a nit than an actual technical issue, but I think it would help us better navigate this codebase if we were to adopt a hierarchical module organization typical of other Haskell libraries (e.g., putting Core.hs's AST under Ssm.Core.Ast). There are also several modules under edsl that are rather specific to testing, such as Trace.hs and the Quickcheck instances; it would be great to move these under the hierarchy starting at test/lib. This can also help people browsing this code what the pipeline of the compiler looks like, without having to grep around.

The only written opinion on this issue that I could find is this fairly recent blogpost: https://www.haskellforall.com/2021/05/module-organization-guidelines-for.html .

For reference, graphmod reports that the repo currently looks something like this:

Soon, support for global references in the EDSL will be merged in with #46 (after it's been merged into that branch first...), and it would be great if we could then add the standard streams to the EDSL.

stdin needs to be written to when there's something on the stdin, and similarly, when stdout & stderr are written to, that write need to be handled by a handler that writes the value to the actual streams.

This is something @koengit & I spoke about that we want to discuss in the next meeting, so @sedwards-lab & @j-hui can help us understand the situation.

Function pointers are expensive to use since we need to load the unknown code before we can execute the function. Normal calls are easy since the code we are jumping to is already known, so it can be loaded in advance. The type of sv_t right now is this struct:

typedef struct {
  /* Generic SV fields */
  void (*update)(sv_t *);
  struct trigger *triggers;
  peng_time_t last_updated;
  peng_time_t event_time;
  void (*to_string)(sv_t *, char *, size_t);
} sv_t;

The function update is here as a function pointer as that is the only function the runtime system will need to call. All other functions are called by the generated programs (assign_type, later_type etc).
When we spoke about these things, it was stated that dereferencing such a function pointer is an expensive operation, and an alternative is to instead insert a tag in the struct that can be used with a switch statement to determine which function to actually call. We will always have a statically known, finite number of these different update functions. E.g update_bool and update_in32 is essentially the same function (as they both copy a 32bit value from one field to another). I think we can get away with a very small number of different functions. This also brings up the question of possibly change the representation of values in sv_ts from a field of a specific type to a field and a size?

The difficulty with generating code for polymorphic functions is that we need to know the type of the thing we are working with in order to generate the proper code (E.g later_int instead of later_bool, when called with an Int). A quick fix is to just put all the type specific functions in the struct as function pointers (instead of just update). Then the type doesn't matter, I guess? However, this incurs additional costs every time we dereference these function pointers. Could we use tags for all of these functions?

How can we prototype this and measure?

We currently assume that C defines typedef int64_t long and typedef uint64_t unsigned long. This is not true on all platforms; for instance, Apple M1 and my NRF52 board (maybe this is an Arm-specific thing?).

Most of the generated code should be fairly robust to this, since we use our own i64 and u64 definitions. But two places where we rely on long == u64 are:

• The formatter, which uses %ld and %lu.
• Literals, which use 42L.

At the very least, this throws warnings. At worst, this causes unexpected behavior. We should modify the Backend compilation pass to be parametrized by some idea of what size the platform thinks long is, or better yet, make Backend agnostic of this issue and push the matter into C.

Starting this meta-issue/thread as a place to collect examples which we want to be able to implement in our language.

Now it just crashes if the parsing fails, but we could change the parse function from Maybe Trace to be Either ParseError Trace instead, and let the client code handle errors in an appropriate way.

I found two bugs that are related to integer overflow---these will be checked into the low-regression test suite in #30 .

I shrank these down into these two programs:

MultOverflowIndirect:

entrypoint:
  fun1()

fun1() {
  *int v0 = var 999999
  int v1 = *v0
  if((0 < (v1 * v1))) {
    after 2 then v0 = 0
  } else {
  }
  *int v3 = var 0
  wait [v3]
}

And MultOverflow:

entrypoint:
  fun1()

fun1() {
  *int v0 = var 999999
  if((0 < (v0 * v0))) {
  } else {
  }
  *int v3 = var 0
  wait [v3]
}

These have the same general cause, but two different symptoms. The cause is that signed integer overflow is undefined in C, allowing it to optimize a statement like 0 < (v * v) into 1 when the value of v is known to be non-zero, allowing the conditional and the computation of its condition to be pruned out altogether. Meanwhile, the Haskell interpreter naively evaluates the computation, which overflows.

In MultOverflowIndirect, this seems to cause the interpreter to take the else branch instead. Meanwhile, in MultOverflow, where I inlined the v0 value, it crashes for some reason.

I'm not familiar enough with the interpreter to directly diagnose this issue, but I know that @Rewbert came across this exact same issue before with integer arithmetic. His solution was to wrap + in a function _add, which would spook the optimizer enough that the problem went away. But it doesn't seem like a complete solution, since it doesn't address the root cause, and an aggressive-enough optimizer would probably be able to inline _add and prune out the branch anyway.

Starting a thread here because I found this to be an interesting idea, and wanted to continue discussion asynchronously. This is a potential workaround/alternative to #8 .

In our meeting today, @koengit proposed handling I/O by spawning handler threads waiting for updates on the variable. My understanding of how this works would be as follows. Suppose we have a reference l :: Ref LED (perhaps obtained via some reference factory as @Rewbert proposed), and a writer thread w which writes to the LED:

-- running in w
l <~ LEDOn

A output listener thread o can handle this asynchronously:

-- running in o
wait [l] -- pick up the assignment from w
-- communicate with hardware after wait unblocks

To handle instaneously assignments, o must run at a lower priority to w; otherwise, the write to l would be lost.

The concern @sedwards-lab had is that if the priority of o is lower than a process with some expensive (but logically instantenously) computation, the wallclock time at which the handler is invoked may be unnecessarily delayed. So, for instance, consider a busy process b whose priority in relation to w and o is:

w > b > o

w runs first, writing to r and scheduling o to run later. However, it does, the higher priority b executes first and stalls the execution of o, even if b is not at all related to o.

Is this an accurate summary of the idea and the issues we think may arise from it?