Implement a chained Mul-Add operation

[tampler]

Hello !

I wanna implement a simple Mul-Add with your graph and extend it to a bigger example. I of course wanna have a chain of Mul-Add operations, implemented as a graph nodes.

My code is below, pls show an example how to do that in the right way

sealed trait AST {
  def op(a: Int, b: Int): Int
}

final case class AddNode() extends AST {
  override def op(a: Int, b: Int): Int = a + b
}
final case class MulNode() extends AST {
  override def op(a: Int, b: Int): Int = a * b
}

object App2 extends App {

  val n0 = MulNode()
  val n1 = AddNode()
  val g  = Graph(n0 ~> n1)

  val out0 = n0.op(1, -2)
  val out1 = n1.op(out0, 5)
}

[Peter Empen]

I am not sure about your requirement:

• What is the purpose of modeling Multiply-Accumulate by a graph?
• Could you give an example of what you want to achieve?
  

[tampler]

Hi Peter

What's unclear? I wanna build a graph with 2 nodes. One holds a Mul operation, another holds Add. Inputs are external, Mul result is passed as an input to Add.

Here's an example picture, my simplified code is in prev post

Can I do that with your graph in a more general way?

Thanks,

Boris

[Peter Empen]

Yes, you could fold the nodes of a traverser like

sealed trait AST {
  def op(a: Int, b: Int): Int
}

object AddNode extends AST {

  override def op(a: Int, b: Int): Int = a + b
}

object MulNode extends AST {

  override def op(a: Int, b: Int): Int = a * b
}

val g = Graph(MulNode ~> AddNode)

val factors = List((1, -2), (2, -2))
val addends = List(5, 6)

(g get MulNode).outerNodeTraverser().foldLeft((0, factors, addends)) {
  case ((sum, (f1, f2) :: rest, a), MulNode) => (sum + MulNode.op(f1, f2), rest, a)
  case ((sum, f, addend :: rest), AddNode)   => (AddNode.op(sum, addend), f, rest)
  case ((sum, f, a), _)                      => (sum, f, a)
}

Note that you can insert no more than two nodes in this graph.

[tampler]

Hi Peter

Thanks for a prompt reply. Is there a way to generalize this for a larger graph? I'm working on a compiler tech and have a dynamic graph to build every time. The only thing constant is my AST and the number of inputs.

I'm working on `Arrows` to implement such functionality and will be happy if its possible to make easier with your excellent graph design. Any advice and examples are appreciated !

Thank you,

Boris

[Peter Empen]

Hi Boris,

Here is what comes to my mind first when extending the above to a larger graph:

1. How should nodes be distinguishable? They need be since they build a set. If there exists no node label you need to employ referential equality.
2. Do you need more than just a path? Asked the other way, do you also have branches etc.? If so how to deal with sum with respect to branches?
   

You need a design based on the answers and possibly more...

[tampler]

Hi Peter. Here's what I have

1. I'm working with a DAG. My data input is guaranteed to form a DAG structure by design

2. I have a fixed pretty large AST

3. My goal is to "simulate" some problem, meaning to build a graph to represent the problem and compute output values from input values for different inputs

4. I have a fixed number of inputs and outputs and their (Scala) types

5. What I need is to calculate all paths from inputs to outputs and dump values for each node on each compute iteration

6. I'll assign a UUID to each node during construction and thus will distinguish them by UUID

7. As for paths, YES ! I will have multiple paths there, but no loops and strongly connected components

Let me know if you need more info

Thanks again for your help,

Boris

[Peter Empen]

Hi Boris,

From what I understand you require:

Provided you have a single root node (node with no predecessor), you could fold a DFS-based traverser with an ExtendedNodeVisitor.

In addition you need a map of NodeT -> Sum to store intermediate sums.

The extended visitor allows you to track the depth. On each depth incrementation you may retrieve the sums of the predecessors from your map to calculate the sum for the current node.

If you have multiple root nodes you could try to utilize the result of a topological sort or, if that was not satisfying, implement your own algorithm.

Hope you'll find the suitable concept for your domain.

Peter