Esempio tipico: interprete per le espressioni aritmetiche

Il problema della decomposizione è il problema di come implementare delle operazioni sui nodi di un albero che si comportino diversamente in dipendenza dei tipi di nodi.

Metodi di classificazione e di accesso

Un primo approccio per risolvere il problema della decomposizione (tipico del paradigma imperativo non orientato agli oggetti, ma usato anche in ambito OO) è fornire:

• dei metodi di classificazione, che permettano di identificare diversi tipi di nodi (tipicamente restituendo un valore Boolean che è true se e solo se il nodo su cui si invoca metodo è di un certo tipo)
• dei metodi di accesso alle informazioni contenute nei vari tipi di nodi.

Ad esempio, nel caso della gerarchia di Expr sono necessari:

• due metodi di classificazione

  def isNumber: Boolean
  def isSum: Boolean
  

  rispettivamente per identificare i nodi Number e Sum

• tre metodi di accesso

  def numValue: Int
  def leftOp: Expr
  def rightOp: Expr
  

  rispettivamente per il valore di un nodo Number e i due operandi di un nodo Sum.

Tali metodi vengono dichiarati nel trait Expr (in modo che siano invocabili su tutte le espressioni), e poi implementati nelle sottoclassi.

trait Expr {
	def isNumber: Boolean
	def isSum: Boolean
	def numValue: Int
	def leftOp: Expr
	def rightOp: Expr
}

class Number(n: Int) extends Expr {
	def isNumber: Boolean = true
	def isSum: Boolean = false
	def numValue: Int = n
	def leftOp: Expr = throw new NoSuchElementException("Number.leftOp")
	def rightOp: Expr = throw new NoSuchElementException("Number.rightOp")
}

class Sum(e1: Expr, e2: Expr) extends Expr {
	def isNumber: Boolean = false
	def isSum: Boolean = true
	def numValue: Int = throw new NoSuchElementException("Sum.numValue")
	def leftOp: Expr = e1
	def rightOp: Expr = e2
}

Si noti che, in generale, ciascun metodo di accesso può aver senso solo per determinati tipi di nodi, e per gli eventuali altri tipi solleva un’eccezione.

Infine, si definisce il metodo di valutazione eval; siccome i metodi di classificazione e accesso forniscono tutte le informazioni necessarie sui vari tipi di nodi, eval può essere direttamente implementato concretamente nel trait Expr:

trait Expr {
	// ...
	def eval: Int =
		if (this.isNumber) this.numValue
		else if (this.isSum) this.leftOp.eval + this.rightOp.eval
		else throw
			new UnsupportedOperationException("Unknown expression " + this)
}

Il caso else finale, che solleva un’eccezione, è necessario perchè in generale quando si discrimina sui tipi di una gerarchia si deve mettere in conto che la gerarchia potrebbe cambiare, in particolare potrebbe essere estesa con nuove classi, qundi il codice deve prevedere la possibilità di trovare istanze di classi che non sa come gestire.

Adesso si vuole osservare quali modifiche è necessario apportare al codice per estendere la gerarchia delle espressioni aggiungendo prodotti e variabili. Per prima cosa si implementano due nuove sottoclassi di Expr:

class Prod(e1: Expr, e2: Expr) extends Expr
class Var(x: String) extends Expr

In seguito si aggiungono a Expr due nuovi metodi di classificazione, corrispondenti ai tipi di nodi appena introdotti,

def isProd: Boolean
def isVar: Boolean

e un nuovo metodo di accesso per il nome di una variabile