CS 380 2025spring ibarland

home—lectures—recipe—hws—exams—D2L—zoom (snow day)

Interpreting H

H0 Implementations

• H0.rkt, with helper files scanner.rkt (and, scanner-demo.rkt); test cases H0-tests.rkt, and student-extras.rkt Updated — re-download for match.

  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.

  For fun, you can run the interactive interpreter, H0-repl.rkt.
• Java: There are two provided Java implementations: a single-Expr-file version using sealed classes (the .jar, or browse files, H0.java is the primary file), and a more conventional one-class-per-file version (the .jar, or browse files, see Expr.java). In both cases, ExprTest.java has the test cases

  Java records: Remember: records are just classes where you don't have to declare the constructor, nor override .equals or .hashCode. All fields are immutable and have a public getter, though we won't need those.

  
  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.
• Java with sealed classes and pattern-matching, all in a single file! This alternate H0 java implementation (browsable-files, .jar) is similar to above, but instead of needing to edit a different file for each Expr variant (Num's eval in one file, and BinOp's eval in another file, etc.), you can put all the eval code for all variants in the single file "H"-java-sealed/"H".java, just like we did in our racket code.

The language H0 syntax

H0:
<Expr>   → <Num> | <Paren> | <BinOp> | <IfZero>
<Paren>  → shake <Expr> bake                     Interpretation: a parenthesized expression
<BinOp>  → add <Expr>1 to <Expr>2                  Interpretation: addition
<BinOp>  → skim <Expr>1 off <Expr>2         Interpretation: subtract <Expr>1 from <Expr>2 (note the order!)
<BinOp>  → scale <Expr>1 to serve <Expr>2      Interpretation: multiplication
<IfZero> → sample <Expr>1; add <Expr>2 to taste or use <Expr>3 instead  Interpretation: if <Expr>1 is 0 (within 1e-6), eval to <Expr>2, else <Expr>3.

H1: see H2.html for details
<BinOp>  → chop <Expr>1 into <Expr>2 Interpretation: “remainder”, except works for negative and fractional amounts.  See H2.html for details.
<Expr>   → … | <IfLT+>                            Interpretation: “if less-than”
<IfLT+>  → if <Expr>1 not <Expr>2  enough, add  <Expr>3  Interpretation: if <Expr>1 is < <Expr>2, result is <Expr>1 + <Expr>3 else <Expr>1.



H2: see H2.html for details
<Expr>    → … | <Id> | <LetExpr>                    Interpretation: identifier; let
<LetExpr> → substitute <Id> with <Expr>0 in <Expr>1 Interpretation: bind Id to result of <Expr>0 (the right-hand-side); then eval <Expr>1 (the body) w/ that binding

H4: see H4.html for details
<Expr> → … | <FuncExpr> | <FuncApplyExpr>

<FuncExpr> → recipe using <Id>: <Expr>             Interpretation: a function-value, with parameter <Id> and body-<Expr>.
<FuncApplyExpr> → use leftover <Expr>0 in <Expr>1   Interpretation: Apply a function (<Expr>1) to an argument (<Expr>0).  Note the order.

Further Details:

<Num> is any numeric literal (as written in either Java or Racket, your choice¹). We'll assume that <Id>s are not one of our H0 reserved words (like skim — i.e. a terminal in the above grammar); you don't need to check/enforce that in your code.

Some similar(??) languages: Implementing one's own language (including let-expressions and functions) is a fairly standard exercise. For example, see Brown University's Programming Languages and Interpretation (Shriram Krishnamurthi), and Virginia Tech's OpenDSA Programming Languages textbook. Feel free to skim or read those books, esp. if wanting a different explanation from the notes in this class & its assignments.

Some similar(??) languages:

• emojicode
• Arnold[Schwarzenegger]C
• Genesis, in Old Hebrew

Discussion

• Give five example programs (<Expr>s) written in H0.
• 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,
  and
  • eval, which actually interprets the program, returning a value (a number for H0-H2, and a number-or-function in H3).
  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 H0.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 H0-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 H0 grammar/datatype-definition.
  • This is called “recursive descent” parsing.

    Note: Parsing H0 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)
    
    

home—lectures—recipe—hws—exams—D2L—zoom (snow day)

This page licensed CC-BY 4.0 Ian Barland Page last generated

Please mail any suggestions (incl. typos, broken links) to ibarlandradford.edu