Let us consider our object language JavaScripty with number literals and addition from our abstract syntax tree discussion (Section 9.3.2.1). Now, let’s extend it with variable uses and binding.
What makes a language go beyond what we might consider a calculator language is adding variable uses and binding. In the following, we show variable binding const in JavaScript, let in OCaml, and val in Scala. We have intentionally aligned them so that their syntactic differences are superficial (i.e., essentially keywords that introduce binding).
\[ \begin{array}{rrrll} \text{expressions} & e& \mathrel{::=}& n\mid e_1 \mathbin{\texttt{+}} e_2 & \text{number literals and addition} \\ & & \mid& x\mid\mathbf{const}\;x\;\texttt{=}\;e_1\texttt{;}\;e_2 & \text{variable uses and binding} \end{array} \tag{14.1}\]
\[ \begin{array}{lrrll} \text{expressions} & e& \mathrel{::=}& n\mid e_1 \mathrel{\texttt{+}} e_2 & \text{number literals and addition} \\ & & \mid& x\mid\mathbf{let}\;x\;\texttt{=}\;e_1\;\mathbf{in}\;e_2 & \text{variable uses and binding} \end{array} \]
\[ \begin{array}{lrrll} \text{expressions} & e& \mathrel{::=}& n\mid e_1 \mathrel{\texttt{+}} e_2 & \text{number literals and addition} \\ & & \mid& x\mid\mathbf{val}\;x\;\texttt{=}\;e_1\texttt{;}\;e_2 & \text{variable uses and binding} \end{array} \]
Let us consider extending the representation of the abstract syntax of JavaScripty in Scala with variable uses and bindings:
sealed trait Expr // e ::=
case class N(n: Double) extends Expr // n
case class Plus(e1: Expr, e2: Expr) extends Expr // | e1 + e2
case class Var(x: String) extends Expr // | x
case class ConstDecl(x: String, e1: Expr, e2: Expr) extends Expr // | const x = e1; e2defined trait Expr defined class N defined class Plus defined class Var defined class ConstDecl
As we discuss in Section 4.2 regarding scoping in Scala, the scope of a variable binding is the part of the program where that variable can be used and refers to that particular binding. Static scoping is where the scope of a variable can be determined by looking directly at the source code.
We have structured our abstract syntax so that the scope of a variable binding is apparent. In particular, the ConstDecl( \(x\) , \(e_1\) , \(e_2\) ) is the AST node that represents binding a JavaScripty variable \(x\) (whose name is stored in Scala as x: String) to the JavaScripty value obtained by evaluating expression \(e_1\) and whose scope is exactly the JavaScripty expression \(e_2\). Note that in particular, \(x\) is not in scope in \(e_1\).
We can thus define a function to compute the free variables of a JavaScripty expression (represented in Scala) as follows:
def freeVars(e: Expr): Set[Var] = e match {
case N(_) => Set.empty
case Plus(e1, e2) => freeVars(e1) union freeVars(e2)
case x @ Var(_) => Set(x)
case ConstDecl(x, e1, e2) => freeVars(e1) union (freeVars(e2) - Var(x))
}defined function freeVars
For the N(_) case, there are no free-variable uses. For the Plus(e1, e2) case, the Plus node does that change the set of free variables, so it is union of the free variables of e1 and e2.
The x @ Var(_) case is a free-variable use, so the singleton set Set(x) is the set of free variables. The @ pattern in Scala enables binding a variable and matching a specific pattern.
The ConstDecl(x, e1, e2) case shows that it is a binding construct where the variable named by x is not in scope in e1 but is in scope in e2. Uses of the variable named by x in e2 thus must be removed, as they are no longer free outside of this ConstDecl expression.
To see freeVars in action, let us consider a JavaScripty expression in concrete syntax:
const four = (2 + 2); (four + four)We can represent the above JavaScripty expression as an abstract syntax tree in Scala as follows, and let us bind Scala variables to all sub-expressions:
val e_n = N(2)
val e_plusnn = Plus(e_n, e_n)
val e_var = Var("four")
val e_plusvarvar = Plus(e_var, e_var)
val e_constdecl = ConstDecl("four", e_plusnn, e_plusvarvar)e_n: N = N(n = 2.0) e_plusnn: Plus = Plus(e1 = N(n = 2.0), e2 = N(n = 2.0)) e_var: Var = Var(x = "four") e_plusvarvar: Plus = Plus(e1 = Var(x = "four"), e2 = Var(x = "four")) e_constdecl: ConstDecl = ConstDecl( x = "four", e1 = Plus(e1 = N(n = 2.0), e2 = N(n = 2.0)), e2 = Plus(e1 = Var(x = "four"), e2 = Var(x = "four")) )
We then compute the free variables with freeVars for each of these JavaScripty expressions:
val fv_n = freeVars(e_n)
val fv_plusnn = freeVars(e_plusnn)
val fv_var = freeVars(e_var)
val fv_plusvarvar = freeVars(e_plusvarvar)
val fv_constdecl = freeVars(e_constdecl)fv_n: Set[Var] = Set() fv_plusnn: Set[Var] = Set() fv_var: Set[Var] = Set(Var(x = "four")) fv_plusvarvar: Set[Var] = Set(Var(x = "four")) fv_constdecl: Set[Var] = Set()
Note it is simply one software engineering decision for the freeVars function here to have type Expr => Set[Var], that is, it returns a set of values with data-class type Var. Another possible choice is Expr => Set[String], which instead returns a set of the strings within the Var uses in the given Expr. The former does convey a more specific type constraint; however, the latter has the same information. A good exercise is to rewrite freeVars to have type Expr => Set[String] to see the difference.
Exercise 14.1 Rewrite the freeVars function above to have the following type:
def freeVarsAlt(e: Expr): Set[String] = ???defined function freeVarsAlt
As we discuss in Section 4.1.1 regarding value bindings in Scala, the meaning of an expression depends on the meaning of the free variables of an expression. One way to give meaning to free-variable uses is by referencing an environment that specifies the assumed meaning of each variable.
Let us consider a value environment for JavaScripty represented in Scala as a Map[Var, Double]:
type Env = Map[Var, Double]defined type Env
Note that like with freeVars above in Section 14.2, it would also be reasonable to choose type Env = Map[String, Double] for the value environment mapping the variables names to their values.
As compared to the eval for number literals and addition in Section 9.3.2.1, our eval also takes a value environment env:
def eval(env: Env, e: Expr): Double = e match {
case N(n) => n
case Plus(e1, e2) => eval(env, e1) + eval(env, e2)
case x @ Var(_) => env(x)
case ConstDecl(x, e1, e2) => {
val v1 = eval(env, e1)
eval(env + (Var(x) -> v1), e2)
}
}defined function eval
The x @ Var(_) case looks up the variable in the value environment env, while the ConstDecl(x, e1, e2) case extends the environment with a binding for evaluating e2.
Let us a define a “public-facing interface” function that calls eval with an empty environment (with some informational logging):
def evalExpr(e: Expr): Double = {
print(s"$e ⇓ ")
val v = eval(Map.empty, e)
println(s"$v")
v
}defined function evalExpr
It works fine for number literals and addition:
val v_n = evalExpr(e_n)
val v_plusnn = evalExpr(e_plusnn)N(2.0) ⇓ 2.0
Plus(N(2.0),N(2.0)) ⇓ 4.0v_n: Double = 2.0 v_plusnn: Double = 4.0
However, it fails unexpectedly for any expression with a free-variable use
val v_var = evalExpr(e_var)Var(four) ⇓ java.util.NoSuchElementException: key not found: Var(four) scala.collection.immutable.Map$EmptyMap$.apply(Map.scala:225) scala.collection.immutable.Map$EmptyMap$.apply(Map.scala:221) ammonite.$sess.cmd6$Helper.eval(cmd6.sc:4) ammonite.$sess.cmd7$Helper.evalExpr(cmd7.sc:3) ammonite.$sess.cmd9$Helper.<init>(cmd9.sc:1) ammonite.$sess.cmd9$.<clinit>(cmd9.sc:7)
val v_plusvarvar = evalExpr(e_plusvarvar)Plus(Var(four),Var(four)) ⇓ java.util.NoSuchElementException: key not found: Var(four) scala.collection.immutable.Map$EmptyMap$.apply(Map.scala:225) scala.collection.immutable.Map$EmptyMap$.apply(Map.scala:221) ammonite.$sess.cmd6$Helper.eval(cmd6.sc:4) ammonite.$sess.cmd6$Helper.eval(cmd6.sc:3) ammonite.$sess.cmd7$Helper.evalExpr(cmd7.sc:3) ammonite.$sess.cmd10$Helper.<init>(cmd10.sc:1) ammonite.$sess.cmd10$.<clinit>(cmd10.sc:7)
as variables in scope must have a binding in the environment.
Let’s make our requirement that evalExpr can only evaluate closed expressions explicit:
def evalExpr(e: Expr): Double = {
require(freeVars(e).isEmpty, s"Expression $e is not closed.")
print(s"$e ⇓ ")
val v = eval(Map.empty, e)
println(s"$v")
v
}defined function evalExpr
val v_plusvarvar = evalExpr(e_plusvarvar)java.lang.IllegalArgumentException: requirement failed: Expression Plus(Var(four),Var(four)) is not closed. scala.Predef$.require(Predef.scala:338) ammonite.$sess.cmd11$Helper.evalExpr(cmd11.sc:2) ammonite.$sess.cmd12$Helper.<init>(cmd12.sc:1) ammonite.$sess.cmd12$.<clinit>(cmd12.sc:7)
val v_constdecl = evalExpr(e_constdecl)Consider again the JavaScripty expression, along with two rewrites:
const four = (2 + 2); (four + four)const x = (2 + 2); (x + x)const fuzz = (2 + 2); (fuzz + fuzz)let four = (2 + 2) in (four + four)let x = (2 + 2) in (x + x)let fuzz = (2 + 2) in (fuzz + fuzz)val four = (2 + 2); (four + four)val x = (2 + 2); (x + x)val fuzz = (2 + 2); (fuzz + fuzz)Even though these expressions are different in the concrete syntax and quite different for a human user, they are effectively the same for a language implementation. They certainly have the same meaning according to the evalExpr function defined above in Section 14.3.
Just like with the “grouping” structure as in Section 12.1 above, we want to make evident the binding structure of an expression. Therefore, we generally consider terms equivalent up to the renaming of bound variables (e.g., we “see” the three expressions given above as the “same” expression).
Renaming bound variables consistently is also called \(\alpha\)-renaming (alpha-renaming) for historical reasons from the \(\lambda\)-calculus (lambda-calculus). Similarly, this equivalence relation on expressions is also called \(\alpha\)-equivalence.
One way to encode the binding structure into the abstract syntax representation is encode the binding structure of the object language using the variable binding in the meta language:
object HOAS {
sealed trait Expr // e ::=
case class N(n: Double) extends Expr // n
case class Plus(e1: Expr, e2: Expr) extends Expr // | e1 + e2
// | x
case class ConstDecl(e1: Expr, e2: Double => Expr) extends Expr // | const x = e1; e2
}defined object HOAS
Observe that there is no Expr AST node for variable uses in the object language, and instead they are represented by variable uses in the meta language in the ConstDecl AST node. This representation is called higher-order abstract syntax.
Note that the JavaScripty grammar with \(\mathbf{const}\) above (Equation 14.1) specifies the abstract syntax using notation borrowed from the concrete syntax. The actual concrete syntax of JavaScripty is less flexible than this abstract syntax to match the syntactic structure of JavaScript. For example,
Plus(N(1), ConstDecl("a", N(2), Var("a")))res14: Plus = Plus( e1 = N(n = 1.0), e2 = ConstDecl(x = "a", e1 = N(n = 2.0), e2 = Var(x = "a")) )
is an abstract syntax tree that would never be produced by the parser. That is,
1 + const a = 2; aresults in a parse error.
The JavaScripty grammar with \(\mathbf{const}\) above (Equation 14.1) read as concrete syntax is ambiguous in multiple ways, including the relative precedence of \(\mathbf{const}\)-bindings and \(\texttt{+}\)-expressions:
const b = 3; b + 4JavaScript uses additional syntactic categories for “declarations” and “statements” layered on top of expressions. Variable bindings with \(\mathbf{const}\) are declarations (and not expressions).
Thus, we give a more restrictive grammar for JavaScripty with declarations and statements matching the syntactic structure of JavaScript as follows:
\[ \begin{array}{rrrl} \text{declarations} & d& \mathrel{::=}& \mathbf{const}\;x\;\texttt{=}\;e\texttt{;} \mid s \mid d_1\;d_2 \mid\varepsilon \\ \text{statements} & s& \mathrel{::=}& e\texttt{;} \mid\texttt{\{}\;d\;\texttt{\}} \mid\texttt{;} \\ \text{expressions} & e& \mathrel{::=}& \texttt{(}e\texttt{)} \mid\cdots \\ \text{variables} & x \end{array} \]
A declaration can be a \(\mathbf{const}\) binding (with a trailing \(\texttt{;}\)), a statement \(s\), or a sequence of declarations (i.e., \(d_1\;d_2 \mid\varepsilon\) where we consider sequencing declarations right associative). A statement can be an expression \(e\) (with a trailing \(\texttt{;}\)), a block \(\texttt{\{}\;d\;\texttt{\}}\), or an empty statement \(\texttt{;}\). Note that JavaScript parsers (like Scala’s) have some rules for semi-colon \(\texttt{;}\) inference to be a bit more flexible than this grammar. In the concrete syntax, expressions \(e\) can be parenthesized \(\texttt{(}e\texttt{)}\) and otherwise are value literals, n-ary expressions, etc.
To make JavaScripty variable declarations simpler, we also deviate slightly with respect to static scoping rules. Whereas JavaScript (like Scala) considers all bindings to be in the same scope in the same declaration list \(d\), our JavaScripty ConstDecl bindings each introduce their own scope. Essentially, we consider \(\mathbf{const}\;x\;\texttt{=}\;e_1\texttt{;}\;d_2\) in JavaScripty as \(\mathbf{const}\;x\;\texttt{=}\;e_1\texttt{;}\;\texttt{\{}\;d_2\;\texttt{\}}\) in JavaScript.