Scala functional pattern computation state

Question

I'm attempting to write a small compiler for a mini language called minijava, in order to gain insight in compiler construction and functional programming. My current implementation is in Scala, a language which I'm also just starting to learn.

sealed class Record()

case object Usage extends Record
case class Declaration(
    definition: Term,
    typ: Type
) extends Record

class Scope(
val parent: Option[ Scope ],
val scopes: List[ Namespace ],

// represents the actual (local) symbol-table
val symbols: Map[ (Namespace, String), Record ] = new HashMap()
) extends Immutable {

def add( ns: Namespace, id: String, record: Record ): Scope =
    new Scope(parent, scopes, symbols + Tuple2((ns, id), record ))

def enter_scope(scopes: List[ Namespace ]) = new Scope( Some(this), scopes )
def leave_scope() = parent
}

Now I can construct a symbol table using this class by going over the AST, and constructing a tree of scopes. This can be done nicely using pattern matching, and functional programming in scala makes sense this way.

However, I need to keep track of the scope that an AST node belongs to in order to make this thing useful... So I'd like to somehow wrap this thing in order to build a hashmap of nodes to scopes everytime I add a declaration.

I've considered many patterns, but I can't find a way to do this that is:

functional
without mutable state
nice (i.e. does not make me write stuff feels redundant)

Can anyone come up with something nice?

I highly recommend you to take a Programming Languages course by Dan Grossman. During the course you will construct your mini language in some of the existing langs and using different approaches. One of the languages reminds Scala a lot and it is actually Scala ancestor and influencer: SML. — om-nom-nom
I'm currently in 2 compiler construction classes. This question is not about compiler construction, it is on only the context of the code. But thank you anyway. — A.J.Rouvoet
The Purely Functional State chapter from Functional Programming in Scala describes a method for handling state that meets your requirements. Unfortunately, it takes a full chapter written by FP experts to explain! The end result is a new type that describes state transactions. — Quigibo

Apocalisp Apocalisp · Accepted Answer · 2014-01-12T21:55:30

You may want to have a look at Bound for Scala. It is a purely functional library for constructing languages with scoped binders. Instead of a map from symbols to scopes, in which case you would have to have a source of fresh names for your symbols, Bound lets you use "locally nameless" terms, and does all of the work of entering, exiting, and traversing, and substituting into scopes for you.

The core of the library is the data type Scope[B,F[_],A], where F is your expression language, B is a placeholder for bound variables and A is a placeholder for free variables. This wraps a value of (essentially) type F[Either[B, F[A]]].

To demonstrate how this works, the binding of a single variable in your language could be represented by something like a lambda term:

trait Exp[A]
...
case class Variable[A](a: A) extends Exp[A]
case class Lambda[A](e: Scope[Unit, Exp, A]) extends Exp[A]

The body of the lambda is then an Exp, and when you hit a Variable, it is going to be either the bound variable of type Unit, or a free variable, in which case it will be another Exp[A].

The source code for the Ermine programming language is a good reference for how this library is used in practice.

Scala functional pattern computation state

1 Answers