promo banner for Computing & Info Sciences

Interpreting B
TENTATIVE -- to be developed in lecture

B0 Implementations

B0.rkt, with helper files scanner.rkt (and, scanner-demo.rkt); test cases B0-tests.rkt, and student-extras.rkt.
Note: Download the racket files, and then choose Open… from DrRacket. Do not copy/paste into an empty DrRacket window, since that window is probably using a student-language, and some of the files below use full racket.
Java: You may browse B0-java/. See the .java files, and a .jar is also in each directory.
Java 17 records: Remember: records are just classes where you don't have to declare the constructor, nor override .equals and .hashCode. All fields are public and immutable.

Note the composite pattern to implement union-types, in Java: The classes Expr and its four variants Num/BinOp/IfZero/Paren are organized in the same way AncTree and its two variants Child/Unknown were.

The language B0 syntax

   B0:
   Expr    ::= Num | Paren | BinOp | IfZero | Nop
   Paren   ::= dark Expr light                     Interpretation: a parenthesized expression
   BinOp   ::= ^ Expr Expr Op               Interpretation: apply a binary operator
   Op      ::= / | | | !              Interpretation: addition, subtraction, multiplication (resp.)
   IfZero  ::= mace Expr Expr windu Expr      Interpretation: if 3rd-expr is 0 (within 1e-6), eval to 1st-expr, else 2nd-expr.
   Nop     ::= force Expr             a no-op: just evaluates to the Expr (like a Paren)

   B1:see B2.html for details
   Op      ::= … | #                      Interpretation: “remainder¹”
   Expr    ::= … | IfGT                     Interpretation: “if greater than”
   IfGT    ::= obi Expr Expr wan Expr Expr Interpretation: if third Expr is > than fourth, result is the first Expr else the second.

   

   B2:see B2.html for details
Expr    ::= … | Id | LetExpr             Interpretation: identifier; let
LetExpr ::= hrrm Expr in Expr, Id is        Interpretation: bind Id to result of 1st Expr (the “right-hand-side”); then eval 2nd “body” Expr w/ that binding

 B4:to be changed see B4.html for details
 Expr ::= … | FuncExpr | FuncApplyExpr

 FuncExpr ::= fun Id -> Expr          Interpretation: a function-value, with parameter Id and body-Expr.
 FuncApplyExpr ::= pass Expr |> Expr   Interpretation: apply a function (2nd expr) to an argument (1st expr)

Further Details:

Num is any numeric literal (as written in either Java or Racket, your choice ²). We'll assume that Ids are not one of our B0 “reserved” words (like obi — i.e. a terminal in the above grammar); you don't need to check/enforce that in your code.

Some similar(??) languages:
emojicode

Arnold[Schwarzenegger]C

Genesis, in Old Hebrew

Discussion

Give five example programs (Exprs) written in B0.
Give their parse trees.
How should we represent these trees, internally? (In Racket, and equivalently in Java).

Where we're headed

For interpreting this language, we will implement three methods:
- parse, which turns source-code into an internal representation,
- toString which turns internal representation back into source-code,
- eval, which actually interprets the program, returning a value (a number for B0-B2, and a number-or-function in B3).
I recommend implementing and testing the methods in this order. Some test-cases will be provided. There might be other helper functions to implement as well.

Discuss the implementation

Once we've talked in class about internal-representation (and given examples of the W programs and corresponding internal-data), then we can discuss the provided-implementation, including recursive-descent parsing:

2018 version: The videos below are based on 2018fall's language, T0. So details of the syntax are different than this semester, and some statements might have different semantics, but overall the content is extremely similar to this semester's language.

Look over expr->string, eval in B0.rkt (or T0.rkt, the exact version from the video). The code directly follows the design recipe. video (9m13s)
Look over the same code written in B0-java/ (or T0-java/, the exact version from the video). The code is equivalent to the racket — still just following the design recipe. video (13m04s)

todo-ibarland: Post the 2021-spring Y0-java/ upload version that uses lambda in BinOp#eval?
parse — recursive-descent parsing: video (17m21s)
- It does not exactly follow the the design recipe (because it processes a string/scanner, not Exprs), yet the code's shape is still extremely correlated to the B0 grammar/datatype-definition.
- This is called “recursive descent” parsing.
  Note: Parsing B0 is particularly easy because each expression-type's leading-token lets us know exactly what to expect, removing the need for look-ahead, backtracking, or cleverer algorithms.
- The Java code is essentially the same, up to class Scanner working a bit differently. video (12m19s)
  
  .
Optional, but helpful for your own test cases:
- Writing test-cases the regular, same-ol’ same-ol’ way, and then realizing what we can re-factor into easier-to-write tests, via an “test-harness” specific to this assignment. In racket: video (14m14s)
- The same test-harness, in Java (slightly more involved, and less flexible): video (8m08s)

¹ Like remainder, except working for negative and fractional amounts. See homework for details. ↩

² This is so we can just use our language's built-in number-parsing functions, without getting bogged down in tokening input. So racket implementations will allow exactly those strings recognized by number?, (including +nan.0, -inf.0, and 2+3i).

Similarly, if using Java, the semantics of B0's arithmetic will be similar to IEEE floating point arithmetic (rather than perfectly-correct arithmetic).

Don't confuse B0's class Num (which extends Expr) with the existing java.lang.Number, which doesn't extend Expr.

↩

This page licensed CC-BY 4.0 Ian Barland
Page last generated Please mail any suggestions
(incl. typos, broken links)
to ibarlandradford.edu

Interpreting B TENTATIVE -- to be developed in lecture