CFWAE++

Introduction

Let’s design a new object-oriented extension of CFWAE, we can call it CFWAE++. It will include most of CFWAE, plus mutation (and recursion), iteration, and objects. Much of the extended syntax is borrowed from ParselTongue, and you can read the ParselDesugar assignment to see more examples, just remember our grammar is different.

History

  • 2014/03/28 - Started interp assignment.
  • 2014/03/14 - Fixed several typos in the data definitions.
  • 2014/03/14 - Put a CFWAE++ template on github.

Grammar

<CFWAE> ::= <num>
    | <string>
    | true
    | false
    | (+ <CFWAE> <CFWAE>)
    | (- <CFWAE> <CFWAE>)
    | (== <CFWAE> <CFWAE>)
    | (> <CFWAE> <CFWAE>)
    | (< <CFWAE> <CFWAE>)
    | (print <CFWAE>)
    | <id>
    | (if <CFWAE> <CFWAE> <CFWAE>)
    | (defvar <id> <CFWAE> <CFWAE>)
    | (deffun (<id> <id> ... ) <CFWAE> <CFWAE>)
    | (fun (<id> ...) <CFWAE>)
    | (obj ((<id> <CFWAE>) ...))
    | (getfield <CFWAE> <CFWAE>)
    | (setfield <CFWAE> <CFWAE> <CFWAE>)
    | (setvar <id> <CFWAE>)
    | (begin <CFWAE> ...)
    | (while <CFWAE> <CFWAE>)
    | (for <CFWAE> <CFWAE> <CFWAE> <CFWAE>)
    | (<CFWAE> <CFWAE> ...)

where an id is a sequence of letters and digits that starts with a letter and is not true, false, defvar, deffun, if, fun, obj, getfield, setfield, setvar, begin, while, print, or for.

Specification

I’m stealing some of the ParselTongue language from the Brown Course. I’ve changed the syntax to make it easier to parse, but copied most of the ExprP and ExprC. You can use most of the spec, but if you see something not listed below, (like the Dotted Object Lookup Expression, Bracket Object Lookup Expression, …) skip it.

Syntax

An informal syntax, with examples.

An expression is one of:

number

110

You know what to do.

string

"Hello, World."

true

true

false

false

(begin expression …)

(begin 1 "hello" 3)

(if test then else)

(if true 2 "3")

(for init test update body)

(defvar x 0 (for (setvar x 0) (< x 10) (setvar x (+ x 1)) 
  (print x)))

(while test body)

(while true
   (print "Infinite loops are bad."))

(fun (arg …) body)

(fun (x) x)

(function actual …)

((fun (x y) (+ x y) 5 3)

(deffun (name arg …) body in-body)

(deffun (f x) x (f 3))

(defvar var val body)

(defvar x 5 (* x x))

(obj ((id val) …))

(obj ((x 5) (f (fun (x) x))))

(getfield obj field)

(getfield (obj ((x 5) (y 3))) x)

(setfield object field value)

(defvar o (obj ((x 5) (y 3)))
  (setfield o y 23))

(op expression …)

(begin 
  (print "Hello World")
  (== 4 (- 5 1)))

An op is one of: <, >, ==, +, -, and print.

Parsing

I will write the parser for you, and generate an ExprP. 

data FieldP:
  | fieldP (name :: String, value :: ExprP)
end

data ExprP:
  | ObjectP (fields :: List<FieldP>)

  | FuncP (args :: List<String>, body :: ExprP)
  | AppP (func :: ExprP, args :: List<ExprP>)
  | DefvarP (id :: String, bind :: ExprP, body :: ExprP)
  | DeffunP (name :: String, ids :: List<String>, funbody :: ExprP, body :: ExprP)
  | IdP (name :: String)

  | GetfieldP (o :: ExprP, field :: ExprP)
  | SetfieldP (o :: ExprP, field :: ExprP, newval :: ExprP)
  | SetvarP (id :: String, val :: ExprP)

  | WhileP (test :: ExprP, body :: ExprP)
  | ForP (init :: ExprP, test :: ExprP, update :: ExprP, body :: ExprP)

  | SeqP (es :: List<ExprP>)
  | IfP (cond :: ExprP, thn :: ExprP, els :: ExprP)

  | NumP (n :: Number)
  | StrP (s :: String)
  | TrueP
  | FalseP

# An op is one of '+ '- '== 'print '< '>
  | PrimP (op :: String, args :: List<ExprP>)
end

Desugaring

You will need to desugar all ExprP into ExprC. 

data FieldC:
  | fieldC (name :: string, value :: ExprC)
end

data ExprC:

  | ObjectC (fields :: List<FieldC>)
  | GetFieldC (obj :: ExprC, field :: ExprC)
  | SetFieldC (obj :: ExprC, field :: ExprC, value :: ExprC)

  | FuncC (args :: List<String>, body :: ExprC)
  | AppC (func :: ExprC, args :: List<ExprC>)
  | LetC (id :: String, bind :: ExprC, body :: ExprC)
  | IdC (id :: String)
  | Set!C (id :: String, value :: ExprC)

  | IfC (cond :: ExprC, thn :: ExprC, els :: ExprC)
  | SeqC (e1 :: ExprC, e2 :: ExprC)

  | NumC (n :: Number)
  | StrC (s :: String)
  | TrueC
  | FalseC

  | ErrorC (expr :: ExprC)

# The core operations are 'string+ 'num+ 'num- '== '< '> 'print 'tagof
  | Prim1C (op :: String, arg :: ExprC)
  | Prim2C (op :: String, arg1 :: ExprC, arg2 :: ExprC)]
end

The ParselDesugar assignment gives an implementation of while. The first 3 lines are in racket, but the rest is all ExprC, and should work: 

[WhileP (test body)
  ;; dummy-fun will tell us it was called if we do so accidentally
  (local ([define dummy-fun (FuncC (list) (ErrorC (StrC "Dummy function")))])
  (IfC (desugar test)

       ;; while-var will hold the actual function once we tie
       ;; everything together
       (LetC 'while-var dummy-fun
         (LetC 'while-func

           ;; this function does the real work - it runs the body of
           ;; the while loop, then re-runs it if the test is true, and
           ;; stops if its false
           (FuncC (list)
             (LetC 'temp-var
               (desugar body)
               (IfC (desugar test)
                    (AppC (IdC 'while-var) (list))
                    (IdC 'temp-var))))

           ;; The Set!C here makes sure that 'while-var will resolve
           ;; to the right value later, and the AppC kicks things off
           (SeqC (Set!C 'while-var (IdC 'while-func))
                 (AppC (IdC 'while-var) (list)))))

       (FalseC)))]

Interpreting

You will need to write a store-passing interpreter with environment. Use the ParselCore assignment description for hints. I’ll put a template in github with a translation of the following plai-typed code into pyret. 

(define-type-alias Env (listof Binding))
(define-type Binding
  [bind (name : symbol) (value : Location)])

(define-type-alias Location number)

(define-type FieldV
  [fieldV (name : string) (value : ValueC)])

(define-type ValueC
  [ObjectV (fields : (listof FieldV))]
  [ClosureV (args : (listof symbol)) (body : ExprC) (env : Env)]
  [NumV (n : number)]
  [StrV (s : string)]
  [TrueV]
  [FalseV])

(define (pretty-value (v : ValueC)) : string
  (type-case ValueC v
    [ObjectV (fs) "object"]
    [ClosureV (a b e) "function"]
    [NumV (n) (to-string n)]
    [StrV (s) s]
    [TrueV () "true"]
    [FalseV () "false"]))

(define (interp-error str)
  (begin
    (raise-user-error str)
    (error 'interp str)))
  • ValueC holds the specification of runtime values for the core interpreter. Values are:
    • NumVs, which are the runtime representation of numbers
    • StrVs, which are the runtime representation of strings
    • TrueV and FalseV, which are the runtime representation of booleans
    • ObjectV, which is the runtime representation of objects (note that fields are held in an ordered list).
    • ClosureV, which is the runtime representation of closures. This refers to a structure for representing environments, Env, which is similar to the structures we’ve talked about in class. Envs map identifiers (symbols) to Locations, which are just an alias for numbers.
  • interp-error takes a string and raises it as an exception that our test harness recognizes
  • pretty-value takes a ValueC and produces its string representation, as per the specifications “Pretty” metafunction
  • Location is a type alias for number, which will be used in the store 
(define-type Cell
  [cell (location : Location) (value : ValueC)])

(define-type-alias Store (listof Cell))

(define-type Result
  [v*s (value : ValueC) (store : Store)])

(define (interp-full [exprC : ExprC] [env : Env] [store : Store]) : Result
  (type-case ExprC exprC
    [NumC (n) (v*s (NumV n) store)]
    [else (interp-error (string-append "Haven't covered a case yet:"
                                       (to-string exprC)))]))

(define (interp [exprC : ExprC]) : ValueC
  (type-case Result (interp-full exprC empty empty)
    [v*s (value store) value]))