Jedi 2.1

Lazy Execution

Lazy Execution in Scala

Recall that Scala provides a mechanism that allows programmers to defer a computation until there's a demand for the result:

scala> lazy val y = {println("computing"); 2 + 3}
y: Int = <lazy>

scala> 5 * y
computing
res0: Int = 25

scala> 5 * y
res1: Int = 25

(Also note that the example shows that the result of the computation is cached for efficiency.)

Lazy Execution in Jedi 2.1

Jedi 2.1 provides two forms of lazy execution: thunks and texts. Both are values that encapsulate an expression to be executed at a later time. The main difference between the two is that a thunk includes its defining environment. In essence, a thunk is a parameterless closure.

Demo

We introduce the following syntax for creating thunks and texts:

freeze(expression) // creates a thunk encapsulating an expression
delay(expression)  // creates a text encapsulating an expression

For example:

-> def x = 5
OK
-> def promise1 = {def x = 10; freeze(2 * x)}
OK
-> def promise2 = {def x = 10; delay(2 * x)}
OK
-> promise1
20
-> promise2
10

This example points out a difficulty with texts. Notice that promise2, a text, ignores its defining environment, which contains the binding x = 10, when it is executed, and uses its calling environment which contains the binding x = 5, instead. On the other hand promise1, a thunk, being a parameterless closure, remembers its defining environment and uses it when it's executed.

Parameter Passing Mechanisms in Jedi 2.1

Parameter passing refers to the way that operands are bound to parameters when a function is called. The choices canbe broken down into s

Eager
   pass-by-value: parameters are bound to copies of the values of the corresponding operands
   pass-by-reference: parameters are bound to the values of the corresponding operands
Lazy
   pass-by-name: parameters are bound to thunks encapsulating the corresponding operands
   pass-by-reference: parameters are bound to texts encapsulating the corresponding operands

Jedi 2.0 function calls use pass-by-reference. Recall that this means all operands are executed, needed or not, before the body of the closure is executed. However, conditionals, conjunctions, and disjunctions require special forms of lazy execution, forcing Jedi to introduce these expressions as special forms. Haskell and a few other functional languages don't need special forms because they pass parameters by name.

Jedi 2.1 introduces a parameter-passing flag that can be set at the start of a Jedi session. (See below.)

Here's a fragment of a Jedi 2.1 session:

-> def z = 10
OK
-> def add5 = lambda(x, y) { def z = 5; x + z }
OK
-> add5(z + 1, {write("computing y"); 10 + 2})
?

Here are a few things to notice:

·       add5 ignores its y parameter.

·       z = 10 in the global environment, but z = 5 in add5's local environment.

·       the second operand has value 12 and produces the side effect of writing "computing y" to the console.

Assume the parameter-passing flag is set to pass-by-reference, then we eagerly execute the two operands, even though we don't need the second one. This produces the side effect:

-> add5(z + 1, {write("computing y"); 10 + 2})
computing y
16

Assume the parameter-passing flag is set to pass-by-name, then we freeze both operands. Since we only need the first operand, the side effect isn't produced:

-> add5(z + 1, {write("computing y"); 10 + 2})
16

Notice that when we did thaw the z + 1 thunk it produced the value 11, even though z = 5 in the thawing environment. That's because the z + 1 thunk remembered that it was frozen in the global environment where z = 10.

By contrast, if the parameter-passing flag is set to pass-by-text, then we delay both operands. The parameters are bound to texts containing the operands. Again y isn't used so the side-effect doesn't appear, however we get an unexpected result:

-> add5(z + 1, {write("computing y"); 10 + 2})
11

Huh? 11 + 5 = 11? What's going on? Indeed this would seem mysterious to a user who assumed he was adding 5 to z + 1 = 11. But unlike thunks, texts don't remember their delaying environment. Instead, they use their resuming environment to look up identifiers. Since the text z + 1 was resumed in an environment where z = 5, its value is 6. And 6 + 5 = 11!

Memoization

We add a cache to our thunks to prevent the inefficiency of having to execute a thunk's body multiple times. This is called memorization:

-> def promise3 = freeze({write("thawing a thunk"); 2 + 3})
OK
-> promise3
thawing a thunk
5
-> promise3
5

Implementing Thunks and Texts

Step 1

Introduce Thunk and Text values:

Here's the complete definition of Text:

class Text(val body: Expression) extends Value

A thunk will need an apply method that calls super.apply(Nil) (i.e. the apply method from closure, but with no arguments.) It will also need to cache the result of apply on the first call.

Step 2: Add MakeThunk and MakeText expression classes

Introduce special forms MakeThunk and MakeText:

The execute method of MakeThunk creates and returns a thunk, while the execute method of MakeText creates and returns a text.

Step 3: Add parsers for freeze and delay

Add freeze and delay parsers to Jedi2Parsers. These should be called by the term parser as follows:

// freeze parser
// freeze ::= "freeze" ~ "(" ~ expression ~ ")" // makes a MakeThunk expression

// delay parser
// delay ::= "delay" ~ "(" ~ expression ~ ")" // makes a MakeText expression
 
override def term: Parser[Expression]  = lambda | freeze | delay | funCall | block | literal | "("~>expression<~")"

 Step 4: Modify Identifier.execute

When executing an identifier we still need to produce an ordinary value. If the identifier is bound to a thunk or a text, then it must first be thawed. To thaw a thunk we simply call its inherited apply method: thunk(). If the identifier is bound to a text, then the expression must be extracted and executed.

Step 5: Add flags to context

Jedi programmers can choose between pass-by-reference (eager), pass-by-text, or pass-by-name (lazy) at the start of a Jedi session by setting the parameter passing flag.

package context

object flags {
   val BY_REF = 0
   val BY_NAME = 1
   val BY_TEXT = 2
  var paramPassing = BY_NAME
}

Step 6: Modify FunCall.execute:

FunCall.execute either executes its operands, delays them, or freezes them depending on the selected parameter passing mechanism.

case class FunCall(val operator: Identifier, val operands: List[Expression]) extends Expression  {
  def execute(env: Environment): Value = {
    var args: List[Value] = Nil

    if (env.contains(operator)) {
      if (flags.paramPassing == flags.BY_NAME) {
        args = operands.map(/* turn operand into a Thunk */)
      } else {
        args = operands.map(_.execute(env))
      }
      // etc.
    } else {
      args = operands.map(_.execute(env))
      alu.execute(operator, args)
    }
  }
}

Static versus Dynamic Scoping

Add another flag to flags:

object flags {
  val BY_VALUE = 0
  val BY_NAME = 1
  val BY_TEXT = 2
  var paramPassing = BY_REF
  var staticScope = true
}

Setting the static scope rule flag to false means closures are executed using their calling environments rather than their defining environments. This can produce some undesirable results:

-> def abs = lambda(x) if (x < 0) -1 * x else x
ok
-> def delta = 100
ok
-> def isSmall = {def delta = 0.00001; lambda(x) abs(x) < delta}
ok
-> isSmall(99)
true

To implement this the apply method of Closure needs the calling environment as an extra parameter. (This must be passed in by FunCall's execute method.) The calling environment instead of the defining environment is extended by the temporary environment.

Setting the static scope rule flag to false means closures are executed using their calling environments rather than their defining environments. This can produce some undesirable results

Pairs and Lists in Jedi

Similar to a tuple in Scala, a pair is a value consisting of two values simply called first and second.

Similar to Nil in Scala, empty is a singleton value that prints as Nil and represents the empty list.

Here's the design:

Here's a sample session working with empty and pairs:

-> def point2d = cons(3.0, 5.0)
OK
-> car(point2d)
3.0
-> cdr(point2d)
5.0
-> point2d
(3.0, 5.0)
-> nil()
Nil

Notes:

·       We can't define a value called Nil in Scala for obvious reasons, so we call it empty, instead. However, we can get it to print as "Nil".

·       We can't define a constant called Nil in Jedi, either:

def Nil = ?

·       But we can define an alu function called getEmpty that returns the empty value and is called when the opcode is "Nil".

·       Cons, car, and cdr are the traditional names (from Lisp) for constructing a pair and extracting its first and second members.

It would be nice to have triples, 4-tuples, and n-tuples in Jedi, but we don't need them:

-> def point3d = cons(2.0, cons(3.0, 4.0))
OK
-> point3d
(2.0, (3.0, 4.0))
-> def xc = lambda(p) car(p)
OK
-> def yc = lambda(p) car(cdr(p))
OK
-> def zc = lambda(p) cdr(cdr(p))
OK
-> xc(point3d)
2.0
-> yc(point3d)
3.0
-> zc(point3d)
4.0

List is an alu function that returns a linked chain of pairs ending in the empty value:

-> def vowels = list("a", "e" ,"i", "o", "u")
OK
-> vowels
(a, (e, (i, (o, (u, Nil)))))
-> car(cdr(cdr(vowels)))
i

Problems

1.     Implement pairs and lists in Jedi.

2.     In Jedi write a function called size that returns the length of a list:

3.     In Jedi write a function called nth that returns the nth element of a list:

-> nth(vowels, 4)
u
-> nth(vowels, 0)
a
-> nth(vowels, 10)
Nil

Catch and Throw in Jedi

Instead of exceptions, Jedi has error values:

A Jedi function can return an error value:

-> def dist = lambda(x, y) if (y < x) throw("no negative distances") else y - x
OK
-> def dist2 = lambda(x, y, z) dist(x, y) + dist(y, z)
OK
-> try {write("here i am"); def x = dist2(3, 2, 6); write("whew"); x } catch {write("error:" + errorRaised)}
here i am
error: no negative distances
DONE
-> 2 + 3
5

A try-catch-block in Jedi consists of two blocks:

Executing a try-catch block executes its try block. If the value returned is an error, then the catch block is executed. The error can be passed to the catch block by adding it to an extension of the environment passed to the catch block.

We add an errorRaised flag to the flags singleton. This is normally set to Notification.UNSPECIFIED. But if it is set to an instance or Error, every call to execute immediately returns this error value.

object flags {
  val byRef = 0
  val byName = 1
  val byText = 2
  var paramPassing = byRef
  var staticScoping = true
  var errorRaised: Value = Notification.UNSPECIFIED
  def setError(gripe: String) = { errorRaised = new Error(Chars(gripe))}
  def getError = errorRaised.asInstanceOf[Error]
  def errorSet: Boolean = errorRaised.isInstanceOf[Error]
  def clearError = {errorRaised = Notification.UNSPECIFIED}
}

The errorRaised flag is set in a Jedi expression by calling throw, which calls alu.error:

private def error(args: List[Value]): Value = {
  if (args.size != 1) {
    flags.setError(Chars("Unspecified"))
  } else {
    flags.setError(args(0).asInstanceOf[Chars])
  }
  flags.getError
}

Every implementation of execute must begin with the line:

if (flags.errorSet) return flags.getError

This prevents the rest of the method from executing. We will also need this line in Closure.apply.

After the call to execute in console.execute an exception is thrown if the error flag is set:

val result = exp.execute(globalEnv)  // execute the expression
if (flags.errorSet) {
  throw new JediException("Uncaught error: " + flags.getError.gripe.toString)
}

Finally, the error flag should be cleared in the repl's finally clause as well as in TryCatch block's execute method.

Notes

·       A better mechanism would be to use a stack of error object so that exceptions could be thrown and caught from inside catch blocks.