Stateful computation using loops

[Jeff Smits]

This thread will continue a discussion that has been going for a while now. The most recent previous thread about this subject was already the third about the subject.

If you haven't been following those threads, please read them first. I know there are a lot of posts to go through, but I'd really like to make progress towards an implementable feature in this thread. And posts about ideas which were discussed already just slow the thread down.

Just a refresher for those who have read the previous threads: We're looking for a safe and synchronous implementation of a signal loop to get a more general way to add state to Elm programs. The only current way to do stateful computation is using foldp, which restricts to the use of a pure function.
But a general signal loop is dangerous. It can have the behaviour to recompute it's state value (or "loopback" value) whenever that state value changes (because of the previous re-computation).

The previous thread pretty much dried up. Evan said he would like to have someone look at theory of FRP on loops/recursive signals. I responded that I would read up on E-FRP, RT-FRP and A-FRP.

That was on June 8, it's Juli 18 now. I've read a few papers (some of which I didn't understand completely). I've read the following papers:

[1] Event-Driven FRP (Wan, Tahay and Hudak)

[2] Real-Time FRP (Wan, Tahay and Hudak)

[3] Functional Reactive Programming, Continued (Nilsson, Courtney and Peterson)

[4] Functional Reactive Programming from First Principles (Wan and Hudak)

[5] Functional Reactive Programming as a Hybrid System Framework (Pembeci and Hager)

The first three were the most relevant ones. The other two I just had a look at to see if I could find out a little more about AFRP.

I couldn't find anything about recursive signals or loops in E-FRP [1], and the example gave me the impression that the implementation of E-FRP was particularly tailored to the needs of interrupt programming on embedded systems.

Real-Time FRP has recursive signals. The language features are described as distinct from the "external" language which takes care of mundane programming things like arithmetic and whatever else you want with values from signals. They use a let snapshot syntax:

lift0 e       <-> ext e

lift1 e s     <-> let snapshot x <- s in ext (e x)

lift2 e s1 s2 <-> let snapshot x1 <- s1 in
                    let snapshot x2 <- s2 in ext (e x1 x2)

I'm pretty sure a feedback loop like the following would be dissallowed to do in E-FRP because x doesn't have a value:

let snapshot x <- ext x in ext x

(It is discussed in the paper and said to be a problem in untyped programs)

Now the stateful construct delay is the most interesting thing in RT-FRP IMHO.

delay takes a value and a signal, delays the signal for a single program execution round and takes the value as the value of the first round.

Using delay and a recursive signal, you can get stateful computation. Another example from the paper [2], computing a running maximum:

let snapshot cur <- s in

  let snapshot rmax <- delay (-inf) (ext max{rmax,cur}) in ext rmax

This sounds a lot like foldp to me. The semantics of RT-FRP is also presented in the paper, but I don't know how to read the notation. So what I don't know is what the following would be mean in RT-FRP:

let snapshot x <- delay 0 (ext x) in ext x

On to AFRP. AFRP has a primitive signal function called loop, which has the type SF (a,c) (b,c) -> SF a b (where SF means signal function). What it does is loop output of type c back to input of type c. [3]

I tried to find out when you might give the starting value of this loop but apparently you don't. I then read some more about AFRP [4,5] but I can't seem to develop even an intuitive feeling for Behaviours. I looked up the implementation of the loop primitive, since the description in the paper [3] is that of Yampa:
class Arrow a => ArrowLoop a where
    loop :: a (b,d) (c,d) -> a b c

instance ArrowLoop (->) where
    loop f b = let (c,d) = f (b,d) in c

I've always been very bad at understanding haskell's recursive definitions...

So the result of my little literature study is:
E-FRP doesn't compare well

RT-FRP has something like we have/are developing, but I don't have the required knowledge to understand it completely

A-FRP has a loop which I again don't understand completely.

My hope is that this at least makes more sense to some of you. And that this information actually saves people some time.

@Evan: Is this enough info for you? Can you conclude from this information that we are or aren't looking into the right direction with the signal loops we're considering*?

* I mean the idea with the loopback having a Change message at the start of the execution and having that loopback connect to a filter to keep the loop under control.

[John Mayer (gmail)]

Awesome compilation! 

Too bad about EFRP, and the RT-FRP delay+recursive strategy seems to exactly describe an async loop.

The AFRP definition is tricky, but not impenetrable. It means exactly as it's represented in pictures; given a signal function, hook up it's output to one of its inputs. Taking into account CFRP requirement for initial values, I think it's translated to one of versions we looked at:

loop : (S (a,c) -> S (c,b)) -> c -> (S a -> S b)

Above, c is the looped type. It's pretty similar to this version:

loop : (S a -> S b -> S b) -> b -> (S a -> S b)

Look at the type of the second version, and look how similar it is to foldp! I know there was some push back to considering a loop that used SF, but the fact that it exists as a primitive in AFRP may help its case. I also tend to think that CFRP is most similar to AFRP in expressiveness, if not in runtime semantics.

When I played with this version in github.com/johnpmayer/thorium it worked pretty well, and as you realized early on, it's a good idea to throw in sampleOn, for the built in trigger. I think it fits all of the requirements.

John

Sent from my iPhone

--
You received this message because you are subscribed to the Google Groups "Elm Discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to elm-discuss...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Tim hobbs]

Hello,

I've just gotten done reading(skimming) a lot of the posts in the previous threads.  I'd like to restate Jeff's previous proposal, just with different words.  I think this will help make things more intuitive:

Evan's thesis describes a programming language (Elm) which structures it's programs as discrete non-cyclic signal graphs.  All signals sampled actively. This means that when a signal gets changed, Change events are propagated to all signals which depend on them. This causes a domino effect of re-evaluation through a section of the graph.  Because of this domino effect, cyclicity is impossible.  If the graph were cyclic, we would see both undefined behavior and signal looping.  Jeff Smits proposed to use passive signal sampling to allow for determinate and non looping signal cyclicity. 

 

When a signal is sampled passively I like to denote that fact by drawing the edge in as a dotted line rather than a solid line.  In the included diagram, the signal F is sampled passively by C on A.  This almost exactly what Jeff initially proposed.  That we do c = something <~ sampleOn a f.

I would prefer syntax that was more like:

c = something <~ a ~ passively f default

You should also be able to write something like:

c = something <~ a ~ z ~ passively f default

c would be re-evaluated every time a change event came through on the signals a or z, and when it was re-evaluated it would use the current value of f.  However, when a change event comes through on f, the value is simply cached and nothing is done with it.

passively : Signal a -> a -> PassiveSignal a  -- My example is not exactly well typed, but looks great ;)

The exact semantics are rather important.  In the case of graph cyclicity, the value of a passively sampled signal lags behind by one graph re-evaluation.  That is:

foldp : (a -> b -> b) -> b -> Signal a -> Signal b
foldp f d s =
 let
  accS = foldp f d s
 in
  (\sv acc->f acc) <~ s ~ passively accS d

Jeff was distressed, by an apparent limitation to passive signal sampling.  He had suggested a pausable game which could be paused by internal game logic as his example.  He was distressed that in his example case passive signal sampling was not ideal:

frames =
 let
   fnp = (,) <~ (fps 25) ~ passively paused
 in
  keepIf (\(_,p)->p) (0,True) fnp

The keepIf keeps on being re-evaluated 25 times a second even when the game is paused!

I agree that this is not ideal, but it is certainly better than the current situation.  Jeff's pausing example is only one of many examples in which graph cyclicity is needed for code cleanliness.

I'll present a better example later on, but first I'll introduce a new trick:

stutter : Int -> Signal a -> Signal a
stutter a signal, reduplicate the Change events from this signal N times.

main = asText <| foldp (\s acc->acc + 1) 0 <| stutter 3 Mouse.clicks  -- The number displayed increments by 3 every time the mouse is clicked.

onset : Signal a -> Signal Bool -- True if at the onset of a stutter 2 pair.(by the way, comments do not work after type declarations)
onset s = foldp (\_ acc->not acc) True s

main = asText <~ onset <| stutter 2 Mouse.clicks -- Always displays False.

stutter is essential to making things work well.  It is also missing in Elm as far as I can tell, there is no reduplicate, copy, twoTimes, or any other such named function) to making passive signal sampling work well.  Say we want to add items to a list every time an Event comes in, but reset that list every time that list becomes full.

We want something like this:

(Oops: listS should be listS:[Int])

stutteredNewItemS : Signal Int
stutteredNewItemS = stutter 2 newItemS

onsetS = Signal Bool
onsetS = onset stutteredNewItemS

listS : Signal [Int]
listS = foldp (\(onset',newItem,full) acc ->if full then [] else if onset' then newItem :: acc else acc) [] <| (,,)<~ onsetS ~ stutteredNewItemS ~ passively fullS False

fullS : Bool
fullS = (\l->length l == 5) <~ listS

What's going on here?  We have an event stream of new items for our list e : [Int] which might come through as e = [1,5,4] and we stutter that stream by 2 giving ourselves an event stream e = [1,1,5,5,4,4].  We then mark onsets of the stuttering, thus esentially giving one input to listS as [(1,True),(1,False),(5,True),(5,False),(4,True),(4,False)].  We then add each of the onsets(the pairs that our true) to our list.  Twice each time we add an item to our list, we check to see if it's full.  When the list becomes full, fullS becomes True, this is on the onset of our stutter.  At the coda(end) of our stutter, listS see's that it is full, and empties itself.

Why not just check if the list is full within the listS signal?  If the full logic is complex, this can make the listS signal code unwieldy.

Why do we need stuttering at all? Couldn't we just change fullS to almostFullS and empty the list when the next element came through?  Yes, in this example we could. However, with stuttering, it is possible, to change this code to, say, a version which would add more than one element to the list at once.  If that were the case then such a trick would no longer work.

stutter is in a way an alternative to Evan's proposal of making Change Int a typed events.

A more convincing example might come from a game that I'm writing. In my game a small robot named Veek travels around an infinite cavern eating particles.

Veek has various tasks, and depending on what task he is currently completing, the particles he eats may either fulfill the task or poison him.  There are 3 counters: task(which task is Veek on?), attempts(how many poisonous particles has Veek eaten this task?), lives(how many lives does Veek have).  For each task, Veek has 5 attempts.  When he runs out of attempts, the lives counter goes down by one, the task counter is incremented by one, and the eatenParticles buffer is cleared.  If he fulfills a task by eating the right particles, the attempts counter returns to 5, the lives counter is untouched, the task counter is incremented by one, the eatenParticles buffer is cleared.  If the lives counter reaches 0 then a redirect signal is filled and the game returns to the start screen.  If the tasks counter exceeds the number of tasks in the level, then a redirect signal is filled and the game goes on to the next level.

Right now, my game engine successfully handles this case with a rather ugly looking signal eatenParticlesAttemptsLivesAndTaskS https://github.com/timthelion/veek/blob/master/Veek.elm#L343

I believe this is a much better example of where Jeff's passive signal sampling could be put into use.  All of these values are mutually dependent, but with passive signal sampling we can create a cyclic graph:



Such a graph requires some extra filtering.  It would require veek'sMouthS to send Change events only when a particle had been eaten, and not every frame(10 times a second).

Each node in this example has the ability to do it's task:

tasks : [[Particle]]

veek'sMouthS : Particle -- this signal changes every time a particle is eaten by Veek

stutteringVeek'sMouthS = stutter 2 veek'sMouthS

eatenParticlesS = foldp (\(pim,isOnset,att,f) acc-> if f then [] else (if att == 0 then [] else (if isOnset then pim :: acc else acc))) [] <| (,,,) <~ stutteringVeek'sMouthS ~ onset stutteringVeek'sMouthS ~ passively attemptsS 5 ~ passively fulfilledS False
-- As particles are eaten, fill the eaten particles buffer, if the attempts counter goes to 0 clear the buffer, if the task is fulfilled, clear the buffer.

isEdible : Int -> Particle -> Bool -- aka not poisonous
isEdible task particle = elem particle (myTaskList !! task)

-- What edible particles has Veek eaten?
edibleS = (\eatenParticles task-> filter (isEdible task) eatenParticles) <~ eatenParticlesS ~ passively taskS 0

-- What poisonous particles are in Veek's stomache?
poisonousS = (\eatenParticles task-> filter (not <| isEdible task) eatenParticles) <~ eatenParticlesS ~ passively taskS 0

attemptsS : Signal Int
attemptsS = (\poisonous->5 - length poisonous) <~ poisonousS
-- 5 == the total number of attempts Veek has per task. We subtract that by the number of attempts Veek has used up.

livesS : Signal Int
livesS = foldp (\as acc->if as == 0 then acc - 1 else acc) 3 attemptsS  -- Note, that despite the fact that veek'sMouth is stuttered by 2 we do not need to do anything weird here, like trying to "unstutter" the signal.  attemptsS will only be 0 at the onset of the stutter.  As soon as attemptsS is 0 at the onset of a double stutter, eatenParticles sees that attemptsS is 0 and by the coda it is [], this means that attempts will be 5 at the coda since the poisonous particles list will be empty.

taskS : Signal Int
taskS = foldp (\(attempts, fulfilled) acc-> if attempts == 0 then acc + 1 else if fulfilled then acc + 1 else acc) 0 <| (,) <~ unstutter 2 attemptsS 5 ~ passively fulfilledS False
-- If the current task has been fulfilled at the onset of the stutter, then go onto the next task.  At the coda of the stutter, the new task will of course will not be fulfilled.  At the time of the coda, eatenParticles will be [] if the task was fulfilled at the onset.  Remember that eatenParticles also saw that the task had been fulfilled at the onset).

fulfilledS : Signal Bool
fulfilledS = (\task edible ->all (\pit->elem pit edible) (tasks !! task))<~ taskS ~ edibleS
-- If Veek has eaten all the particles he was supposed to this task, then the task has been fulfilled.

Uff!  That was tricky!

I hope you understood all that:

active signals: Those are the ones we have already.
passive signals: Allow for cyclicity.
stuttering: The duplication of a Change Event in order to cause the sampling of passive signals twice.
onset: The first of two Change events in a stutter 2 change event pair.
coda: The second of two Change events in such a pair.

That's all for now.  Looking forward to questions, comments.
Tim

[John Mayer (gmail)]

> Because of this domino effect, cyclicity is impossible. 

That's actually not true. A signal node with two inputs does not produce any change or no-change messages until one message from each input has arrived. By carefully controlling the program invariant that the output is a no-change whenever all of the non-cyclic, or trigger, inputs are no-change, it is possible to build a cyclic signal graph with active sampling and without the "domino cascade".

Active sampling via message passing is Elm's (and CFRP's) core model that allows non-blocking concurrency.

John

Sent from my iPhone

--

[Jeff Smits]

@Tim:
Thanks for joining the discussion! :D I see you put quite some thought into your post.
But I think you misunderstood my proposal. As John said, you can use active sampling without problems if you're careful. And set a Change message on the loopback at the start of the program.
I think I explained this idea best in this post with the first set of images.

The biggest downside of this passive sampling you're proposing is that it is doesn't have to be in sync with the system. So you need tricks like that stutter and onset to get a passive sampling re-evaluated. I think this is very bad because it looks like the code does nothing, but in stead it does do something: influencing the runtime's passive sampling which the programmer shouldn't even have to be aware of to write Elm (at least that is the case now and IMHO this is awesome and should be preserved).

On a side note: stutter creates new Change messages, so as you need async to make that kind of functionality work. If you do have async, you could implementation it yourself:

stutter : Int -> Signal a -> Signal a

stutter stutterAmount input =
  if| stutterAmount == 1 -> input
    | stutterAmount >  1 -> let
        asyncInput = async input
      in merge (asyncInput) <| stutter (stutterAmount-1) asyncInput