Help defining mutually recursive classes

I don’t see how to define the classes which describes an application I’m trying to write. Can someone give me some suggestions? I mainly don’t see how it can be done functionally.

I have three kinds of entity. An Dfa (deterministic finite automata) has a set of State objects, along with two subsets, I and F of that set which denote the set, of initial states and the set of final states. A State has a set of Transition instances. A Transition has a source State and destination State and a transition label which is an instance of some independent type, controlled by a type parameter.

One strategy would have the Dfa constructor take a list of integers which name the states, a list of integers which designates the I subset, a list of Integers which designates the F subset, a list of 3-tuples containing integers representing the sources/destinations/labels, then allocate State instances and Transition Instances, and then using mutable manipulation to set the fields in the Transition instances pointing to the State objects, then using mutable manipulation set the fields of the State instances pointing to the Transition instances. Finally, set the fields of the Dfa to the list of State instances and Transition instances?

That sounds awful.

Is there a better way?

Can you post a small example of what you’d like to do? Even if it doesn’t compile, that’s ok.

But the Dfa doesn’t need to take integers directly, does it? Maybe I’m not understanding your requirements?

case class State[S](stateId: S)

case class Transition[T, S](transitionId: T, source: State[S], destination: State[S])

case class Dfa[T, S](states: Set[State[S]], initials: Set[State[S]], finals: Set[State[S]], transitions: Set[Transition[T, S]])

Doesn’t look too awful to me.

You can also just take a set of transitions and extract states, initials and finals from the transitions.

1 Like

One way of wiring cyclic dependencies would be lazy vals.

class A(bInit: => B) {
  lazy val b: B = bInit
}

class B(aInit: => A) {
  lazy val a: A = aInit
}

val a: A = new A(b)
val b: B = new B(a)

I’d be tempted to explore different design approaches, though, where the states don’t “know” their transitions, like a Map[State, Set[Transition[L]]] in the DFA class - YMMV.

Why not modeling

  • states as arbitrary compareable elements of type S
  • Transition as a hash map of type (S,T)=>S
  • letters as arbitrary compareable elements of type T

Pseudocode:

@tailrec
def acceptance(state:S,transition:(S,T)=>S,word:List[T]):Bool
{
   if(state in errors)
   {
       return false;
   }
   if(state in final)
   {
       return true;
   }
   if(word.isEmpty)
   {
       return false;
   }
   head::tail=word
   return acceptance(transition(state,head),tail);
}

@sighoya, thanks for the suggestion, but don’t want state machines in the code, I want data structures which represent state machines so I can perform operations on them such as minimization, construction, intersection.

@curoli, the problem with this approach is how do I create a Dfa. Take the simple case of a Dfa with one state, q, having a transition which points from q to q ? having q be the only initial state and only final state? I need the state object to create the Transition object, but I need the Transition object to create the State object. I don’t know of any way other than to create them both, then modify those of their fields or the other.

Here is my sample code. In this case I have to call the constructor Dfa with sets of integers which obey certain requirements, but then I construct the objects and thereafter modify them. it’s not sooooo bad, but not functional.

class State[L](val id:Int) {
  var transitions:Set[Transition[L]] = Set()
}

class Transition[L](var source:State[L], var label:L, var destination:State[L]) {}

class Dfa[L,E](Qids:Set[Int], q0id:Int, Fids:Set[Int], delta:Set[(Int,L,Int)], combineLabels:(L,L)=>L, f:Int=>Option[E]) {
  require(Qids.contains(q0id))
  require(Fids.subsetOf(Qids))
  require(delta.forall { case (from: Int, label: L, to: Int) => Qids.contains(from) && Qids.contains(to) })

  def findState(id: Int): State[L] = {
    Q.find(s => s.id == id).get
  }

  var Q: Set[State[L]] = Qids.map(id => new State[L](id))
  for{
    (from , fromTriples) <- delta.groupBy(_._1)
    fromState = findState(from)
    (to, toFromTriples) <- fromTriples.groupBy(_._3)
    toState = findState(to)
    label = toFromTriples.map(_._2).reduce(combineLabels)
  } fromState.transitions += new Transition(fromState,label,toState)

  var q0: State[L] = findState(q0id)
  var F: Set[State[L]] = Fids.map(findState)
}

Here is an example usage:

  test("build set dfa") {

    val t1 = Set(1) // fixnum
    val t2 = Set(1, 2) // integer
    val t3 = Set(1, 2, 3) // number
    val t4 = Set(4) // string
    val t6 = t3.diff(t1) // !fixnum & number
    val t7 = t3.diff(t2) // !integer & number
    val t9 = Set(9) // symbol

    val dfa = new Dfa[Set[Int], String](Set(0, 1, 2, 4, 5, 6, 7, 8),
                                        0,
                                        Set(4, 5, 6, 7),
                                        Set((0, t1, 1),
                                            (0, t4, 2),
                                            (0, t9, 8), // mergable
                                            (0, t4, 8), // mergable
                                            (1, t6, 4),
                                            (1, t1, 5),
                                            (1, t7, 6),
                                            (2, t3, 7),
                                            (8, t7, 6),
                                            (8, t2, 7)),
                                        (a: Set[Int], b: Set[Int]) => a.union(b),
                                        Map(5 -> "clause-1",
                                            5 -> "clause-2",
                                            6 -> "clause-3",
                                            7 -> "clause-3").get(_))
    assert(dfa.F.size == 4)
    assert(dfa.q0.id == 0)
    assert(dfa.F.map(_.id) == Set(4, 5, 6, 7))
    assert(dfa.findState(0).transitions.size == 3)
    assert(dfa.findState(0).transitions.exists(tr => tr.label == t9.union(t4)))
  }

Why does a State object need to contain its Transitions?

Just looking at this quickly, I don’t see why Q or transitions need to be vars. Couldn’t you instead have the for comprehension build up a Map from id to a Set of Transitions, and then build up the States from that? I’m also confused why q0 needs to be a var – that looks like a perfectly reasonable lazy val.

I think all of the mutability here could be squeezed out by changing a couple of things to lazy val and putting in an intermediate step or two, but I don’t have time to really look at it properly…

@curoli, are you suggesting that rather than having a state contain its transition, there just be a function (method whatever) which knows which transitions are associated with each state? So the Dfa would know its transitions, but the state would not.

That is an interesting idea, but it violates part of the semantic definition. (perhaps not the end of the world though). For example, if two different Dfas contain the same state, then the state has the same transitions w.r.t both Dfas. For example, sort of a subgraph of a Dfa.

I agree that Q, q0, and F don’t really need not be val, they could indeed be vars, not even lazy vars.

I think you meant that the other way around?

Note that transitions also doesn’t need to be a var – you can just make State immutable, with a + operator that takes another Transition, and builds a new State with that Transition added. This is pretty bog-standard functional code. (Although sometimes it’s useful to add Monocle or another lens library to reduce the boilerplate for it.)

Yes, they can be val, not var and not lazy. Sorry, yes you’re right.

As far as states creating a new state when a transition is added, the thing that would have to be maintained is that those NEW states are the ones which are members of F, Q, and q0. And if a state already has a transition leading to it, you can “replace” it with a new one, because you’ll strand other transitions. E.g., if state 0 had a transition leading to 1, and 1 has a transition leading to 0, I don’t see how to functionally create two states and two transitions without mutation.

Ah, I see – yeah, the mutual dependency between State and Transition kind of forces the mutability.

Frankly, I think the functional answer is “don’t build it that way”. I’d probably instead have State be basically nothing but an id, possibly even make it just an AnyVal over an id. (Or possibly include the Dfa itself as a parameter for convenience, or possibly define State inside of Dfa, so it inherits the type parameter and gets free access to the contents of Dfa.)

The Dfa would contain a Map[State, Set[Transition]], replacing the transitions inside of State. That would break the dependency loop, I believe. The data structures would be a tad more complex, but it seems like you could get rid of all the mutability by building things up that way, and I think you could even preserve the calling syntax as you have it…

Having the state simply be an Int, is something I thought of. But I’d like to avoid because it looses type information. How to distinguish between an Int representing a state, and an Int just representing the count of something. One of the purposes of the OO paradigm is to model phenomena by objects whose type tells you the semantics of the object.

Of course another argument for using Int to represent a State, is because the constructor function takes Ints. Thus every time I want to derive one Dfa to another, I have to somehow serialize the old one (to Ints), then deserialize the modified Ints into a new Dfa.

As far as states creating a new state when a transition is added,

I don’t quite understand what you mean. If you add a transition you get a new dfa?

That’s what the extends AnyVal suggestion is for. I’m not saying to use raw Int’s – I’m saying to define State as a wrapper around Int, as a separate type. Scala’s AnyVal mechanism, while imperfect (it’s being replaced by the better opaque type mechanism in Scala 3) is a decent way of wrapping a primitive inside a strong type with relatively little overhead. No type information is lost, but you still gain a lot of efficiency.

Seriously – if you don’t know AnyVal, I strongly recommend reading into it. It’s a useful tool, and important to understand its strengths and weaknesses.

Yes I see. Thanks, that’s an insightful suggestion.

Right. Basically

class State(val id: Int) extends AnyVal
case class Transition[L](source: State, label: L, destination: State)

class Dfa[L, E] private (
    val q: Set[State],
    val init: State,
    val finals: Set[State],
    trans: Map[State, Set[Transition[L]]]) {
  def findState(id: Int): Option[State] = q.find(_.id == id)
  def transitions(s: State): Set[Transition[L]] = trans.getOrElse(s, Set.empty)
}

At first glance it seems easier to filter all transitions with src/dest not contained in the subgraph when creating a new Dfa instance than creating copies of all State instances and filtering each transition set individually…

…or, just for the kicks, allow arbitrary types as state.

trait Stateable[S] {
  def mkState(id: Int): S
  def id(s: S): Int
}

class Dfa[S : Stateable, L, E](...) { ... }

object Dfa {
  def apply[S : Stateable, L, E](...): Either[IllegalDfaSpec, Dfa[S, L, E]] = ...
}