FSA (готовой state automaton) в Масштабе


Я начинающий программист Scala с большим опытом работы в области функционального программирования (мл, Хаскелл, схемы) и я только что написал свою первую программу на Java. Это внедрение ФСА (конечного автомата). Ниже приводится упрощенная версия, которая имеет 3 события/действия/этикетки (Е0, Е1, Е2) и четыре государства (С0, С1, С2, С3).

 sealed abstract class Event

 case object E0 extends Event
 case object E1 extends Event
 case object E2 extends Event

 abstract class State { def event ( e : Event ) : State }

 object S0 extends State {
   override def event ( e : Event ) : State = {
     e match {
       case E0 => { S1 }
       case E1 => { S0 }
       case E2 => { S2 } } } }

 object S1 extends State {
   override def event ( e : Event ) : State = {
     e match {
       case E0 => { S1 }
       case E1 => { S2 }
       case E2 => { S0 } } } }

 object S2 extends State {
   override def event ( e : Event ) : State = {
     e match {
       case E0 => { S2 }
       case E1 => { S0 }
       case E2 => { S3 } } } }

 object S3 extends State {
   override def event ( e : Event ) : State = {
     e match {
       case E0 => { S0 }
       case E1 => { S3 }
       case E2 => { S3 } } } }

 class Fsa {
   private var state : State = S0
   def event ( e : Event ) : Unit = { state = state.event ( e ) } }

Типичное использование ФСА объектов будет выглядеть так:

val fsa = new Fsa
while ( true ) {
   fsa.event ( ... nextEvent () ) }

Мне было бы интересно знать, если вы думаете, что это хорошо, или по крайней мере разумным образом по внедрению в учебный процесс СБМ в Scala, и если нет, то почему. Я особенно заинтересован в потреблении памяти подобного решения.



2871
6
задан 5 сентября 2011 в 11:09 Источник Поделиться
Комментарии
2 ответа

Выглядит нормально для меня. Вам не нужно столько скобок:

object S0 extends State {
override def event (e : Event) : State = e match {
case E0 => S1
case E1 => S0
case E2 => S2
}
}

Но в этот простой пример я хотел бы использовать карту для кодирования переходных правил (исправлял):

sealed abstract class State {
def m: Map[Event, State]
def event ( e : Event ) : State = m(e)
}

object S0 extends State{ lazy val m = Map[Event, State](E0 -> S1, E1 -> S0, E2 -> S3) }

3
ответ дан 6 сентября 2011 в 07:09 Источник Поделиться

Следующие предложения от Landei выше, и эта статья на рекурсивный тип объявления в Scala, я придумал немного другое решение, где говорится непосредственно с помощью модели переходов состояний.

trait StateFunc [ T ] extends PartialFunction [ T, StateFunc [ T ] ]

sealed abstract class Event

case object E0 extends Event
case object E1 extends Event
case object E2 extends Event

class FSA {
private type State = StateFunc [ Event ]

private def transitions [ T ] ( pf : PartialFunction [ T, StateFunc [ T ] ] ) = new StateFunc [ T ] {
def apply( event : T ) = pf ( event )
def isDefinedAt ( event : T ) = pf.isDefinedAt ( event ) }

private val ( s0 : State ) = transitions { case E0 => s1; case E1 => s2; case E2 => s0 }
private val ( s1 : State ) = transitions { case E0 => s3; case E1 => s0; case E2 => s1 }
private val ( s2 : State ) = transitions { case E0 => s2; case E1 => s1; case E2 => s0 }
private val ( s3 : State ) = transitions { case E0 => s3; case E1 => s3; case E2 => s1 }

private var state = s0

def handle ( e : Event ) { state = state ( e ) } }

Я не говорю, что это лучше, чем другие предложенные решения, но мне интересно про использование памяти. Ясно, как это сильно рекурсивный конструкт, если компилятор не делает хвост-вызов оптимизации, это решение будет работать из памяти в конце концов. У меня нет понимания компилятор Scala, но мне кажется, что в этом простом случае хвостовые вызовы таким образом, чтобы обеспечить постоянное использование стекового пространства. Но что, если переход функции сделать что-то более сложное (например, возможно создание исключений)? Может постоянное использование пространства по-прежнему быть гарантированы?

Как в сторону, это действительно надо пережить так много обручи, чтобы определить рекурсивный тип? Почему я не могу просто написать, например типа T = карта [ Инт, Т ]?

9.9.2011 редактировать: я добавил @tailrec аннотации к программе со следующими результатами: компилятор принимает @tailrec на С0, ..., С3 просто отлично. Но она отказывается, когда я аннотировать частное определение переходов, что не удивительно. Что это означает на практике для стека использование такая форма реализации СБМ, я не знаю.

4
ответ дан 6 сентября 2011 в 01:09 Источник Поделиться