how to implement the rxjs .scan operator with S.js?

Question

how to implement the rxjs .scan operator with S.js?

brucou opened this issue 4 years ago · 7 comments

I am quite excited to investigate S as it has a clock system as do synchronous data flow languages (thinking about Lucid Synchrone for instance). I could not find an obvious way to replicate the behavior of the scan operator of Rxjs. The semantics can be found in the official documentation with marble diagrams. In short, a stream emits a value, a reducing function takes that value, and uses its accumulator to compute another value that is both emitted and put back in the accumulator. The resulting stream is thus a stream of accumulator values.

The issue here is that you need access to values of the accumulator at time n-1 (+ the triggering stream) to produce the values at time n. I tried using reduce but I got into running away clock messages.

To give you some background, I am trying to implement a chess game:

The chess application behaviour follows stream equations (pseudo code follows), and have an implementation in Rxjs using the scan operator):

const behaviours$ = boardClicks.pipe(
  scan((acc, clickedSquare) => {
    const {
      gameOver,
      playerTurn,
      selectedPiece,
      whitePiecesPos: wPP,
      blackPiecesPos: bPP,
      squareStyles,
      position,
      whiteMove,
      blackMove,
      chessEngine
    } = acc;

    let nextGameOver, nextPlayerTurn, nextSelectedPiece, nextWhitePiecesPos;
    let nextBlackPiecesPos, nextSquareStyles, nextPosition;
    let nextWhiteMove, nextBlackMove;

    nextWhiteMove =
      !gameOver &&
      playerTurn === WHITE_TURN &&
      selectedPiece !== NO_PIECE_SELECTED &&
      wPP.indexOf(clickedSquare) === -1 &&
      isValidMove(selectedPiece, clickedSquare, chessEngine)
        ? { from: selectedPiece, to: clickedSquare }
        : NO_MOVE;

...

For information, the pseudo-code inspired from synchronous data-flow languages is as follows:

Move commands

---- Main types

-- one possible position on the check board
Square :: ["a1", "a2", ..., "a8", "b1", ..., "h8"]
-- type synonym for Square, with the added implication that there is a piece on that square
Square => PiecePos
- record describing a move with an origin square and target square
Move :: {from :: Square, to :: Square} | ∅

---- Application logic

-- a move is either a white piece move or a black piece move
moves = whiteMoves || blackMoves

-- Whites move iff: 
-- the game is not over, 
-- it is Whites turn to play, 
-- there is already a selected piece (origin square), 
-- user clicks on a square which does not contain a white piece (target square), 
-- the corresponding move (origin square to target square) is valid
whiteMoves = ∅ `then` map boardClick(square)
   case !gameOver & 
        playerTurn == White & 
        selectedPiece & 
        !hasWhitePiece(square) & 
        isValidMove(selectedPiece, square): {from: selectedPiece, to: square}
   case _ : ∅
-- Black moves is the symmetric version of White moves
blackMoves = ∅ `then` map boardClick(square)
  case ...

-- a piece is selected if the game is on, the click does not trigger a valid move and
-- + when Whites play, and a white piece is clicked on
-- + or when Blacks play, and a black piece is clicked on
-- 
-- a piece is deselected if the game is on, and the click triggers a valid move
selectedPiece :: Maybe PiecePos
selectedPiece = ∅ `then` map boardClick(square)
  case gameOver: ∅
  case moves: ∅
  case playerTurn == White & square in whitePiecesPos: square
  case playerTurn == Black & square in blackPiecesPos: square
  case _: rec last selectedPiece 
  
-- the game is over if a valid move ends the game. 
gameOver = false `then` map moves isWinningMove

-- Whites initially have the turn, then that alternates with Blacks after every move
playerTurn = White `then`
  case whiteMoves: Black
  case blackMoves: White
  case _: rec last playerTurn

-- Board state
-- the position of white pieces is set initially per the chess game rules
-- then it changes with every move performed by the players
-- achtung! white pieces may be affected by a black piece move and vice versa
whitePiecesPos :: Array of PiecePos
whitePiecesPos = whitesStartPos `then`
  -- remove old white piece position and add new one
  case whiteMoves({from, to}): 
    rec last whitePiecesPos |> filter not(from) |> concat [to]
  -- remove old black piece position if any - case when a white piece gobbles a black one
  case blackMoves({from, to}):
    rec last whitePiecesPos |> filter not(from)

-- blackPiecesPos is deduced from whitePiecesPos by symmetry
blackPiecesPos :: Array of PiecePos
  ...

Render command

-- The render uses the ChessBoard React component. 
-- We specify some look and feel options for the component.
-- We essentially render a board position (`position`) 
-- and possibly one highlighted piece (`squareStyle`).
renderProps = {
  draggable: false,
  width: 320,
  boardStyle: {
    borderRadius: "5px",
    boxShadow: `0 5px 15px rgba(0, 0, 0, 0.5)`
  },
  onSquareClick: eventSourceFactory(boardClicks),
  -- only the following two properties vary
  squareStyles,
  position
}

-- the position *prop* is [as defined by the ChessBoard React component](https://chessboardjsx.com/props) we are using
position = "start" `then` map moves getPositionAfterMove

-- the squareStyle prop allows us to manage the style for a highlighted piece
squareStyles = selectedPiece(square)
  ? { [square]: { backgroundColor: "rgba(255, 255, 0, 0.4)" }}
  : {}

Answer 1 · 2020-07-24T19:46:16.000Z

If I understand correctly, then scan would be simply:

var stream = S.data(0);

var scanned = S((acc) => stream() + acc, 0);

S(() => console.log(scanned()));

stream(1);
stream(3);
stream(5);

//0
//1
//4
//9

Answer 2 · 2020-07-24T20:54:56.000Z

@webstrand mmm. That does seem like so, I'll see how it works in my use case. Don't see how that escaped me, it is pretty simple indeed. Actually I may not even need scan anymore,,, The totality of the variables depend on a single signal. Thanks!

Answer 3 · 2020-07-26T01:03:54.000Z

Alright, after fighting a few hours with this, the conclusion is that it is pretty unnatural (not to say impossible) to refer to the previous values of signals with the current API (keep running in circular dependency warning). So a scan may be the best way to go forward. But then if all variables are put in one giant scan there is no longer any point in using S.js... My idea was to write synchronous equations with it, like in dataflow languages.

To summarize the problem:

I want Yn = f(Yn-1, Xn-1), Xn = f(Xn-1)
S( val => ..., seed) only allows Sn = f(Sn-1)

If somebody is interested in investigating, the (not working) S code is here. The working Rxjs code is here. If no answer in a few days, I will close this.

Answer 4 · 2020-07-26T04:18:17.000Z

Lucid Synchrone is definitely an influence on S :).

S doesn't have a global ability like Lucid Synchrone's pre keyword because S is a library, not a compiler. That means S doesn't know ahead of time which values need to have their previous values retained. So it would have to store all previous values, even though very few will actually be read. That would be a global cost and an avenue for memory leaks.

So instead, you have to tell S which signals you want to keep the previous value for. There are a few ways to write that function -- I see one in your code but yeah, it's not the one you want, because it depends on the current value, which for your purposes creates a cycle.

You may have better luck with a definition like this:

const prev = (s, init) => {
    const _prev = S.data(init);
    S(() => _prev(s()));
    return _prev;
}

That uses a data signal to store the value of the signal from the previous tick without creating a dependency in consumers on the current value as well.

All that said, I generally find games and other "forward integration"-style programs much easier to write based on a "current, next" pattern rather than a "previous, current" one. In effect, that means putting game state into data signals instead of computations. Computations become the "rules" that update the data signals representing game state. But that does mean that the new state doesn't become current until the tick after the event advancing the game occurs, so it breaks synchrony.

Answer 5 · 2020-07-26T12:20:17.000Z

Thanks @adamhaile. That seems to make sense. I still have to make an intuition of this S syntax. I can see why prev is updated when s is, but not why it is deferred in time. In the beginning it is obvious, prev is init. the confusion comes after. I will try though.

I agree about the current, next approach working better. In fact, revising my pseudo-code vs. Rxjs implementation, I am realizing that most of the equations on the right side involves previous values of streams... But then, how would you write a next operator? Is that even possible?

Putting game state in data signals as you suggest should work too. I wanted somehow to derive everything from the user click on the chess board, as user clicks work as a clock signal that drives all the computations. That looks like a more declaratve approach. The esterel dataflow language has a more imperative approach where you listen on signals and emit values in signals manually. That seems similar to what you are suggesting here?

Anyways, I'll try again today. Hopefully I meet success and I can report it here.

Answer 6 · 2020-07-28T01:49:44.000Z

Thanks all of you for your support. I made some progress, but now I have a stubborn runaway clock error (see updated codesandbox), and I am giving up here. Spent too much time already. It may very well be possible to do what I want with S.js (for instance as @adamhaile suggested putting game state in data signals) but the bottomline is that if I have to spend this amount of time and still fail, it is not the good tool for me. What I would suggest for future beginners:

add examples in the docs that go beyond the simple use cases
develop some more the trouble shooting section from the notes on runaway mutation
not sure if it is possible, but tracing the computation or logging the dependency tree would be helpful for debugging

Thanks again

Answer 7 · 2021-07-06T16:13:25.000Z

Coming back to this and adding this jsfiddle:

https://jsfiddle.net/7w1bcg69/4/

var prev = (s, init) => {
    const _prev = S.data(init);
    S(() => _prev(s()));
    return _prev;
}

var counter = S.data(0);
var prevCounter = prev(counter, -8);
S.effect(() => console.log(`counter`, counter()))
S.effect(() => console.log(`prev counter`, prevCounter()))

var dep = S(() => counter() + prevCounter());
S.effect(() => console.log(`dep`, dep()))

document.getElementById("btn").addEventListener("click", ev => counter(counter()+1))

Console (init and then one button click):

JSFiddle Console (beta). Turn on/off in Editor settings.
☁️ "Running fiddle"
"computations created without a root or parent will never be disposed"
"counter", 0
"prev counter", 0
"computations created without a root or parent will never be disposed"
"dep", 0
"counter", 1
"dep", 1
"prev counter", 1
"dep", 2

Expected behavior:

dep should update only once. prev counter should start with its configured initial value (-8). And then prevCounter should equal the previous value of the counter.