CSCI 3155: Lab Assignment #3 Solution

$30.00

Category:

Description

The purpose of this lab is to grapple with how dynamic scoping arises  and  how to formally specify  semantics. Concretely, we will extend JAVA SC R I P T Y with recursive functions and  imple- ment two interpreters. The first will be a big-step interpreter that is an extension of Lab 2 but implements dynamic scoping “by accident.” The second will be a small-step interpreter that exposes evaluation order and  implements static scoping by substitution.

Like last time,  you will work on this  assignment in pairs. However, note that each  student needs to submit a write-up and  are individually responsible for completing the assignment.

You are welcome to talk about these questions in larger  groups. However, we ask that you write  up your  answers in pairs. Also, be sure  to acknowledge those with which you discussed, including your partner and  those outside of your pair.

Recall the evaluation guideline from the course syllabus.

 

Both  your ideas and  also the clarity  with which they are expressed  matter—both in your English prose and your code!

 

We will consider  the following criteria in our grading:

 

  • How well does your submission answer the questions? For example, a common mistake is to give an example when a question asks for an  explanation.  An example may  be useful in your explanation, but it should not take the place of the explanation.

 

  • How clear is your  submission?  If we cannot understand what you are trying to say, then  we cannot give you points for it.  Try reading your answer aloud to yourself  or a friend; this technique is often  a great way to identify holes in your reasoning.  For code, not  every program that  “works”  deserves  full  credit.   We must be able to read and understand your intent. Make sure you state any pre- conditions or invariants for your functions (either  in comments, as assertions, or as require clauses as appropriate).

 

Try to make your code  as concise and  clear as possible. Challenge yourself to find the most crisp,  concise way of expressing the  intended computation. This may mean using ways of ex- pression computation currently unfamilar to you.

Finally, make sure that your file compiles and runs (using  Scala 2.10.3). A program that does not compile will not  be graded.

 

1

 

Submission Instructions.   Upload to the moodle exactly four files named as follows:

 

  • Lab3-YourIdentiKey.pdf with your  answers to  the  written questions (scanned, clearly legible handwritten write-ups are acceptable).

 

  • Lab3-YourIdentiKey.scala with your answers to the coding exercises.

 

  • Lab3Spec-YourIdentiKey.scala with any updates to your unit tests.
  • Lab3-YourIdentiKey.jsy with a challenging test case for your JAVA SC R I P T Y interpreter. Replace YourIdentiKey with your  IdentiKey (e.g., I would submit Lab3-bec.pdf and  so forth).

Don’t use your student identification number. To help  with managing the submissions, we ask that you rename your uploaded files in this manner.

Sign-up for an interview slot for an evaluator. To fairly accomodate everyone, the interview times are strict  and  will not be rescheduled. Missing an interview slot means missing the inter- view evaluation component of your lab grade. Please  take advantage of your interview time  to maximize the  feedback that you are able  receive. Arrive at your  interview ready  to show  your implementation and your written responses. Implementations that do not compile and run will not be evaluated.

 

 

Getting Started.    Download the code  pack lab3.zip from the assignment page.

A suggested way to get  familiar with  Scala  is to do  some small  lessons with  Scala  Koans (http://www.scalakoans.org/).  If you  haven’t looked at the  ones from  Lab 1, we consider you look at those, particularly AboutCaseClasses and  AboutPatternMatching.

 

  1. Feedback. Complete the survey  on the  linked from  the  moodle after  completing this  as- signment. Any non-empty answer will receive full credit.

 

  1. JavaScripty Interpreter: Tag Testing, Recursive Functions, and Dynamic Scoping.

 

We now have the formal tools to specify exactly how a JAVA SC R I P T Y program should behave. Unless otherwise specified, we will continue to try to match JavaScript semantics as imple- mented by Node.js/Google’s V8 JavaScript Engine. Thus,  it is still useful to write  little  test JavaScript programs and  run  it through Node.js to see how the test should behave. Finding bugs  in the  JAVA SC R I P T Y specification with  respect to JavaScript is certainly deserving of extra credit.

 

In this lab, we extend JAVA SC R I P T Y with recursive functions. This language is very similar to the LETREC language in Section 3.4 of Friedman and  Wand.

 

For  this  question, we  try  to  implement functions as  an  extension of Lab  2 in  the  most straightforward way.  What  we will discover is that we have  made a historical mistake and ended up with a form of dynamic scoping.

 

The syntax  of JAVA SC R I P T Y for this lab is given in Figure  1. Note  that the grammar specifies the abstract syntax  using  notation borrowed from the concrete syntax.  The new constructs are highlighted. We have function expressions function p (x ) e1 and  function calls e1 (e2 ).

 

expressions                     e ::= x | n | b | str | undefined | uop e1 | e1 bop e2

| e1 ? e2 : e3 | const x = e1 ; e2 | console.log(e1 )

| function p (x ) e1 | e1 (e2 ) | typeerror values                             v ::= n | b | undefined | str | function p (x ) e1 unary operators         uop  ::= – | !

binary operators        bop ::= , | + | – | * | / | === | !== | < | <= | > | >= | && | ||

 

variables                       x

numbers (doubles)        n

booleans                        b ::= true | false

strings                           str

function names             p ::= x | ε

 

value environments       E ::= · | E [ x 7→  v ]

 

Figure  1: Abstract Syntax of JAVA SC R I P T Y

 

✭✭

statements    s ::= const  x = e | e | { s1 } | ; | s1 s2

 

= ✭✭1

expressions   e ::= · · · | ✭const x e✭; e2

| (e1 )

 

x )

| ✭functionp✭( ✭ e1 | function p (x ) { s1 return e1 }

 

Figure  2: Concrete Syntax of JAVA SC R I P T Y

 

 

In a function expression, the  function name p can  either be an  identifier or empty.  The identifier is used for recursion.  For simplicity, all functions are  one  argument functions. Since functions are first-class values, we can get multi-argument functions via currying.

We have  also  added a “marker” typeerror to the  expression language.  This marker is not part  of the  source language is used in our  definition of the  evaluation judgment form.  We discuss this in more detail further below.

 

As before, the  concrete syntax  accepted by the  parser is slightly  less flexible  than the  ab- stract syntax  in order to match the  syntactic structure of JavaScript.  For function expres- sions, the  body  is surrounded by curly  braces (i.e., {   }) and  consists of a statement s1  for const  bindings followed by a return with an expression e1 .

An abstract syntax  tree  representation is provided for you in ast.scala. We also provide a parser and  main driver  for testing. The correspondence between the  concrete syntax  and the abstract syntax  representation is shown in Figure  3.

 

A big-step operational semantics of JAVA SC R I P T Y is given  in Figure  4.  This figure  may  be one  of the first times that you are reading a formal semantics of a programming language.

 

 

case   class   Function(p: Option[String], x: String, e1: Expr) extends  Expr

Function(p , x , e1 ) function p (x ) e1

case   class   Call(e1: Expr, e2: Expr) extends  Expr

Call(e1 , e2 ) e1 (e2 )

 

 

Figure  3:  Representing in Scala  the  abstract syntax  of JAVA SC R I P T Y.  After each case class  or

case object,  we show the correspondence between the representation and  the concrete syntax.

 

 

 

 

 

 

 

 

 

EVA LVA R

 

 

 

EVA LVA L

 

 

EVA L NE G

 

 

EVA L NOT

E ` e v

 

 

E ` x E (x )

 

EVA L SE Q

E ` v v

E ` e 1 v 1         n 0  = − toNumber(v 1 )

E ` − e1 ⇓ n0

 

EVA L PLU S NU M B E R

E ` e 1 v 1         b 0  = ¬ toBoolean(v 1 )

E ` ! e1 ⇓ b0

 

E ` e 1 v 1         E ` e 2 v 2

E ` e1 , e2 ⇓ v2

 

EVA L PLU S ST R I N G1

E ` e 1 v 1         E ` e 2 v 2         n 0  = toNumber(v 1 ) + toNumber(v 2 )        v 1 6= str 1         v 2 6= str 2

E ` e1 + e2 ⇓ n0

 

EVA L PLU S ST R I N G2

 

E ` e 1 str 1         E ` e 2 v 2         str 0  = str 1 + toString(v 2 )

E ` e1 + e2 ⇓ str0

 

EVA L AR I T H

E ` e 1 v 1         E ` e 2 str 2         str 0  = toString(v 1 ) + str 2

E ` e1 + e2 ⇓ str0

 

E ` e 1 v 1         E ` e 2 v 2         n 0  = toNumber(v 1 ) bop toNumber(v 2 )        bop {, , /}

E ` e1 bop e2 ⇓ n0

 

EVA L IN E QUA L I T Y NU M B E R

E ` e1 ⇓ v1          E ` e2 ⇓ v2

b 0  = toNumber(v 1 ) bop toNumber(v 2 )        v 1 6= str 1         v 2 6= str 2         bop {<, <=, >, >=}

E ` e1 bop e2 ⇓ b0

 

EVA L IN E QUA L I T Y ST R I N G

E ` e 1 str 1         E ` e 2 str 2         b 0  = str 1 bop str 2         bop {<, <=, >, >=}

E ` e1 bop e2 ⇓ b0

 

 

EVA L EQUA L I T Y

 

E ` e1 ⇓ v1          E ` e2 ⇓ v2

 

v 1 6= function p 1 (x1 ) e 1         v 2 6= function p 1 (x2 ) e 2         b 0  = (v 1 bop v 2 )        bop {===, ! ==}

E ` e1 bop e2 ⇓ b0

 

 

EVA L AN D TRU E

E ` e 1 v 1         true = toBoolean(v 1 )        E ` e 2 v 2

E ` e1 && e2 ⇓ v2

 

EVA LOR FA L S E

EVA L AN D FA L S E

E ` e 1 v 1         false = toBoolean(v 1 )

E ` e1 && e2 ⇓ v1

 

EVA L PR I N T

EVA LORTRU E

E ` e 1 v 1         true = toBoolean(v 1 )

E ` e1 || e2 ⇓ v1

 

E ` e 1 v 1         false = toBoolean(v 1 )        E ` e 2 v 2

E ` e1 || e2 ⇓ v2

 

EVA L IF TRU E

E ` e 1 v 1         true = toBoolean(v 1 )        E ` e 2 v 2

E ` e1 ? e2 : e3 ⇓ v2

      E ` e 1   v 1          v 1  printed           

E ` console.log(e1 ) ⇓ undefined

 

EVA L IF FA L S E

E ` e 1 v 1         false = toBoolean(v 1 )        E ` e 3 v 3

E ` e1 ? e2 : e3 ⇓ v3

 

 

EVA LCO N S T

E ` e 1 v 1         E [ x 7→ v 1 ] ` e 2 v 2

E ` const x = e1 ; e2 ⇓ v2

 

EVA LCA L L RE C

EVA LCA L L

E ` e 1 v 1         v 1 = function (x ) e 0                    E ` e 2 v 2         E [ x 7→ v 2 ] ` e 0  v 0

E ` e1 (e2 ) ⇓ v 0

 

E ` e 1 v 1         v 1 = function x1 (x2 ) e 0                    E ` e 2 v 2         E [ x1 7→ v 1 ][ x2 7→ v 2 ] ` e 0   v 0

E ` e1 (e2 ) ⇓ v 0

 

 

Figure  4: Big-step operational semantics of JAVA SC R I P T Y (with dynamic scoping).

 

toNumber(n) toNumber(true) toNumber(false) toNumber(undefined) toNumber(str) toNumber(function p (x ) e1 )

def

n

=

def

1

def
=

def

=    0

NaN

=

def

=    parse str

def

=    NaN

 

 

toBoolean(n) toBoolean(n) toBoolean(b) toBoolean(undefined) toBoolean(str) toBoolean(str)

toBoolean(function p (x ) e1 )

def
def

=    false    if n = 0 or n = NaN

true    otherwise

=

def

=    b

def

=    false

def

=    false    if str = “”

def

=    true    otherwise

def

=    true

 

toString(n) toString(true) toString(false) toString(undefined) toString(str) toString(function p (x ) e1 )

def

=    string of n

def
def

=    “true”

def
=

=     “false” “undefined”

def

=    str

def

=    “function”

 

 

 

 

Figure  5: Conversion functions. We do not specify  explicitly the parsing or string conversion of numbers. The conversion of a function to a string deviates slightly  from  JavaScript where the source code  of the function is returned.

 

 

 

 

EVA LT Y PE ER RO R EQUA L I T Y1

E ` e 1 v 1          v 1 = function p 1 (x1 ) e 1          bop {===, ! ==}

E ` e1 bop e2 ⇓ typeerror

E ` e v

 

EVA LT Y PE ER RO R EQUA L I T Y2

E ` e 2 v 2          v 2 = function p 1 (x1 ) e 1          bop {===, ! ==}

E ` e1 bop e2 ⇓ typeerror

EVA LT Y PE ER RO RCA L L

v 1 6= function p (x ) e 1

E ` v1 (e2 ) ⇓ typeerror

 

EVA L PRO PAG AT E UN A RY

    E ` e 1   typeerror

E ` uop e1 ⇓ typeerror

 

EVA L PRO PAG AT E PR I N T

            E ` e 1   typeerror             

E ` console.log(e1 ) ⇓ typeerror

EVA L PRO PAG AT E BI N A RY1

      E ` e 1   typeerror       

E ` e1 bop e2 ⇓ typeerror

 

EVA L PRO PAG AT E IF

       E ` e 1   typeerror       

E ` e1 ? e2 : e3 ⇓ typeerror

EVA L PRO PAG AT E BI N A RY2

      E ` e 2   typeerror       

E ` e1 bop e2 ⇓ typeerror

 

EVA L PRO PAG AT E CO N S T

            E ` e 1   typeerror            

E ` const x = e1 ; e2 ⇓ typeerror

 

EVA L PRO PAG AT E CA L L1

   E ` e 1   typeerror

E ` e1 (e2 ) ⇓ typeerror

EVA L PRO PAG AT E CA L L2

   E ` e 2   typeerror

E ` e1 (e2 ) ⇓ typeerror

 

 

 

Figure  6: Big-step operational semantics of JAVA SC R I P T Y: Dynamic type error rules.

 

It may seem daunting at first, but it will be become easier with practice. This lab is such an opportunity to practice.

 

A formal semantics enables us to describe the semantics of a programming language clearly and  concisely. The initial barrier is getting used to the  meta-language of judgment forms and  inference rules.   However, once you cross  that barrier, you will see that we are telling you exactly how to implement the interpreter—it will almost feel like cheating!

In Figure  4, we define the  judgment form  E ` e v , which says informally, “In value  en- vironment E , expression e evaluates to value  v .” This relation has  three parameters: E , e , and  v .  You can  think of the  other parts of the  judgment as just  punctuation.  This judg- ment form  corresponds directly to the eval function that we are asked to implement (not a coincidence). It similarly has three parts:

 

def  eval(env: Env, e: Expr): Expr

 

It takes  as input a value environment env (E ) and  an expression e (e ) returns a value v .

 

It is very informative to compare your  Scala code  from  Lab 2 with the  inference rules  that define E ` e v .  One  thing you  should observe is that all of the  rules  are  implemented, except for EVA LCA L L, EVA LCA L L RE C, and  part of EVA L EQUA L I T Y.  In essence, implementing those rules is your task for this question.

 

In Lab 2, all expressions could be evaluated to something (because of conversions). With functions, we encounter one  of the  very few run-time errors in JavaScript:  trying  to call something that is not  a function. In JavaScript and  in JAVA SC R I P T Y, calling  a non-function raises a run-time error.  In  the  formal semantics, we  model this  with  evaluating to  the “marker” typeerror.

Such  a run-time error is known as dynamic type  error. Languages are called  dynamically typed  when they allow all syntactically valid programs to run and  check  for type errors dur- ing execution.

In our  Scala  implementation, we will not  clutter our  Expr type  with  a typeerror marker. Instead, we will use a Scala exception DynamicTypeError:

 

case   class   DynamicTypeError(e: Expr) extends  Exception

 

to signal  this case.  In other words, when your interpreter discovers a dynamic type error, it should throw this exception using  the following Scala code:

 

throw   DynamicTypeError(e)

 

The argument should be the  input expression to eval where the  type  error was detected. One advantage of using a Scala exception for typeerror is that the marker does  not  need to be propagated explicitly as in the inference rules  in Figure  6. In particular, your interpreter will implement the  EVA LT Y PE ER RO R rules  explicitly, but  the  EVA L PRO PAG AT E rules  are imple- mented implicitly with Scala’s exception propagation semantics.

 

Note in rule EVA L EQUA L I T Y, we disallow equality and  disequality checks (i.e., === and  ! ==) on function values. If either argument to a equality or disequality check  is a function value, then we consider this a dynamic type error. This choice is a slight departure from JavaScript.

 

(a)  First,  write  some JAVA SC R I P T Y programs and  execute them as JavaScript programs.

This step  will inform how  you will implement your  interpreter and  will serve  as tests for your interpreter.

Write-up:  Give one  test  case  that behaves differently under dynamic scoping versus static scoping (and  does  not  crash). Explain  the test case and  how they behave differ- ently in your write-up.

(b)  Then, implement

 

def  eval(env: Env, e: Expr): Expr

 

that evaluates a JAVA SC R I P T Y expression e in a value  environment env to a value  ac- cording to the evaluation judgment E ` e v .

The following helper functions for converting values to numbers, booleans, and strings are provided:

 

def  toNumber(v: Expr): Double def  toBoolean(v: Expr): Boolean def  toStr(v: Expr): String

 

We suggest the following step-by-step process:

 

  1. Bring your  Lab 2 implementation into  Lab 3 and  make sure  your  previous test cases  work as expected.
  2. Extend your implementation with non-recursive functions. On function calls, you need to extend the environment for the formal parameter but not for the function itself. Do not worry yet about dynamic type errors.
  3. Add support for checking for dynamic type errors.
  4. Check that your interpreter, unfortunately, implements dynamic scoping instead of static scoping.
  5. Modify your implementation to support recursive functions.

 

  1. JavaScripty Interpreter: Substitution and Evaluation Order.

 

In this question, we will do two things. First, we will remove environments and  instead use a language semantics based on substitution. This change will “fix” the  scoping issue,  and we will end  up with static, lexical scoping.

As an aside, substitution is not  the  only way to “fix” the  scoping issue.   Another way is to represent function values  as closures, which is a pair of the function with the environment when it is defined. Substitution is a fairly simple way to get lexical scoping, but in practice, it is rarely used because it is not the most efficient implementation.

The second thing that we do is move to implementing a small-step interpreter. A small-step interpreter makes explicit the  evaluation order of expressions. These  two changes are or- thogonal, that is, one could implement a big-step interpreter using substitution or a small- step  interpreter using environments.

(a)  Implement

 

def  substitute(e: Expr, v: Expr, x: String): Expr

 

 

 

 

 

 

 

DO NE G

n 0  = − toNumber(v )

v −→ n0

 

DO PLU S NU M B E R

 

 

DO NOT

b 0  = ¬ toBoolean(v )

! v −→ b0

 

 

 

D O S E Q            

 

v1 , e2 −→ e2

 

DO PLU S ST R I N G1

e −→ e 0

 

n 0  = toNumber(1 ) + toNumber(2 )       v 1 6= str 1          2 6= str 2

v1 + v2 −→ n0

str 0  = str 1 + toString(2 )

str1 + v2 −→ str0

 

DO PLU S ST R I N G2

str 0  = toString(1 ) + str 2

v1 + str2 −→ str0

 

DO IN E QUA L I T Y NU M B E R1

DOAR I T H

n 0  = toNumber(1 ) bop toNumber(v 2 )       bop ∈ {−, ∗, /}

v1 bop v2 −→ n0

 

0  = toNumber(1 ) bop toNumber(v 2 )       bop ∈ {<, <=, >, >=}        v 1 6= str 1

v1 bop v2 −→ b0

 

DO IN E QUA L I T Y NU M B E R2

0  = toNumber(1 ) bop toNumber(v 2 )       bop ∈ {<, <=, >, >=}        v 2 6= str 2

v1 bop v2 −→ b0

 

DO IN E QUA L I T Y ST R I N G

0  = str 1 bop str 2          bop ∈ {<, <=, >, >=}

str1 bop str2 −→ b0

 

DO EQUA L I T Y

1 6= function 1 (x1 ) e 1          2 6= function 1 (x2 ) e 2          0  = (1 bop v 2 )       bop ∈ {===, ! ==}

v1 bop v2 −→ b0

 

DOAN D TRU E DOAN D FA L S E DO ORTRU E DO OR FA L S E
true = toBoolean(1 )

v1 && e2 −→ e2

false = toBoolean(1 )

v1 && e2 −→ v1

true = toBoolean(1 )

v1 || e2 −→ v1

false = toBoolean(1 )

v1 || e2 −→ e2

 

DO PR I N T

                  v 1  printed                       

console.log(v1 ) −→ undefined

 

 

D O C O N S T                                     

 

const x = v1 ; e2 −→ e2 [v1 /x ]

DO IF TRU E

true = toBoolean(1 )

v1 ? e2 : e3 −→ e2

 

DO CA L L

1 = function (x ) e 1

v1 (v2 ) −→ e1 [v2 /x ]

DO IF FA L S E

false = toBoolean(1 )

v1 ? e2 : e3 −→ e3

 

DO CA L L RE C

    v 1  = function x1 (x2 ) 1         

v1 (v2 ) −→ e1 [v1 /x1 ][v2 /x2 ]

 

 

 

Figure  7: Small-step operational semantics of JAVA SC R I P T Y: DO rules.

 

 

 

 

 

 

SE A RC H UN A RY

 

 

1

SE A RC H BI N A RY1

 

 

2

SE A RC H BI N A RYAR I T H2

e −→ e 0

 

1

        e 1   0             

1

uop e1 −→ uop e 0

 

SE A RC H EQUA L I T Y2

            e 1   0                      

1

e1 bop e2 −→ e 0    bop e2

2 0                       bop ∈ {+, −, ∗, /, <, <=, >, >=}

2
1

v1 bop e2 −→ v1 bop e 0

 

SE A RC H PR I N T

 

2

2 0                        1 6= function p (x ) e 1          bop ∈ {===, ! ==}

2

v1 bop e2 −→ v1 bop e 0

                        e 1   0                                            

1

console.log(e1 ) −→ console.log(e 0  )

 

SE A RC H IF

1

             e 1   0                        

1

e1 ? e2 : e3 −→ e 0    ? e2 : e3

SE A RC H CO N S T

1

                       e 1   0                                          

1

const x = e1 ; e2 −→ const x = e 0  ; e2

SE A RC H CA L L1

1

       e 1   0            

1

e1 (e2 ) −→ e 0  (e2 )

 

 

SE A RC H CA L L2

2

                                   e 2   0                                                                

2

¡function p (x ) e1 ¢(e2 ) −→ ¡function p (x ) e1 ¢(0  )

 

 

Figure  8: Small-step operational semantics of JAVA SC R I P T Y: SE A RC H rules.

 

 

 

 

 

 

 

 

T Y PE ER RO R EQUA L I T Y1

                   bop {===, ! ==}                          

 

(function p (x ) e1 ) bop e2 −→ typeerror

 

 

T Y PE ER RO R EQUA L I T Y1

                   bop {===, ! ==}                          

 

v1 bop (function p (x ) e2 ) −→ typeerror

e −→ e 0

 

 

 

 

 

 

PRO PAG AT E UN A RY

 

uop typeerror −→ typeerror

T Y PE ER RO RCA L L

1 6= function p (x ) e 1

v1 (e2 ) −→ typeerror

 

PRO PAG AT E BI N A RY

 

typeerror bop e2 −→ typeerror

 

 

 

 

 

PRO PAG AT E BI N A RY

 

v1 bop typeerror −→ typeerror

 

PRO PAG AT E PR I N T

 

console.log(typeerror) −→ typeerror

PRO PAG AT E IF

 

typeerror ? e2 : e3 −→ typeerror

 

PRO PAG AT E CO N S T

 

const x = typeerror; e2 −→ typeerror

PRO PAG AT E CA L L1

 

typeerror(e2 ) −→ typeerror

PRO PAG AT E CA L L2

 

v1 (typeerror) −→ typeerror

 

 

 

Figure  9: Small-step operational semantics of JAVA SC R I P T Y: Dynamic type error rules.

 

that substitutes value v for all free occurrences of variable x in expression e. We advise defining substitute by recursion on e. The cases  to be careful about are ConstDecl

and Function because these are the variable binding constructs. In particular, substitute

on expression

 

a; (const   a = 4; a)

 

with value 3 for variable “a” should return

 

3; (const   a = 4; a)

 

not

 

3; (const   a = 4; 3)

 

This function is a helper for the step function, but you might want to implement all of the cases  of step that do not require substitute first.

 

(b)  Implement

 

def  step(e: Expr): Expr

 

that performs one-step of evaluation by rewriting the  input expression e into  a “one- step  reduced” expression. This one-step reduction should be implemented according to the  judgment form  e −→ e 0   defined in Figures 7, 8, and  9. We write  e [v /x ] for sub- stituting value  v for all free occurrences of the variable x in expression e (i.e., a call to substitute).

(c)  Write-up:   Explain  whether the  evaluation order is deterministic as specified by the judgment form e −→ e 0 .

 

It is informative to compare the small-step semantics used in this question and the big-step semantics from the previous one.  In particular, for all programs where dynamic scoping is not  an issue,  your  interpreters in this  question and  the  previous should behave the  same. We have  provided the  functions evaluate and  iterateStep that evaluate “top-level” ex- pressions to a value using your interpreter implementations.

 

  1. Evaluation Order.

 

Consider the small-step operational semantics for JAVA SC R I P T Y shown in Figures 7, 8, and 9. What  is the  evaluation order for e1 + e2 ? Explain. How do we change the  rules  obtain the opposite evaluation order?

 

  1. Short-Circuit Evaluation. In this question, we will discuss some issues with  short-circuit evaluation.

 

(a)  Concept. Give an  example that illustrates the  usefulness of short-circuit evaluation.

Explain  your example.

 

(b)  JAVA SC R I P T Y. Consider the  small-step operational semantics for JAVA SC R I P T Y shown in Figures 7, 8, and  9. Does e1 && e2 short circuit?  Explain.


error: Content is protected !!