1. Homepage
  2. Programming
  3. CS440 Programming Languages, Fall 2022 - Machine Problems 3: Interpreters

CS440 Programming Languages, Fall 2022 - Machine Problems 3: Interpreters

Engage in a Conversation
IITUSCS440CS 440Programming LanguagesRacketInterpretersMP3

CS 440 MP3

Overview

In this machine problem you will be updating the interpreter we started building in class in order to implement a number of new language constructs. CourseNana.COM

The core language constructs you will be adding include: CourseNana.COM

  • Boolean values: #t and #f
  • If-expression: if
  • Relational expressions: =<

You will also add the following "syntactic sugar" forms: CourseNana.COM

  • Subtraction: -
  • Boolean expressions: and and or
  • Cond-expression: cond
  • Relational expressions: <=>>=

Finally, you will also be adding the define form, which can be used to define functions using the same syntax as Racket. These functions will be loaded before the REPL is started (or some expression is evaluated). Unlike the functions supported by the interpreter we built in class, define'd functions will support recursion. CourseNana.COM

Details

Core language additions

  • As with integer values, the Boolean values #t and #f evaluate to themselves (note that the reader already recognizes Boolean values, and you can match them in the parser using the boolean? predicate) CourseNana.COM

  • The if expression is a simplified version of Racket's. It has the following form: CourseNana.COM

    (if BOOL-EXP TRUE-EXP FALSE-EXP)
    

    where BOOL-EXP is a form that evaluates to a Boolean value, and TRUE-EXP and FALSE-EXP are any valid form. Its semantics are the same as Racket's. CourseNana.COM

  • The relational expressions = and < have the forms: CourseNana.COM

    (= LHS RHS)
    
    (< LHS RHS)
    

    where LHS and RHS are forms that evaluate to integer values. = evaluates to #t if LHS and RHS are equal and #f otherwise. < evaluates to #t if LHS is less than RHS and #f otherwise. CourseNana.COM

Syntactic sugar additions

  • - (subtraction) takes two arguments that evaluate to integer values and evaluates to their difference. It is syntactic sugar for addition of the first value to the negative of the second. I.e., CourseNana.COM

    (- EXP1 EXP2)
    

    desugars to: CourseNana.COM

    (+ EXP1 (* -1 EXP2))
    
  • and takes one or more argument forms, and evaluates to #t if and only if all its arguments evaluate to #t; otherwise it evaluates to #f. It is syntactic sugar for one or more if forms. E.g., CourseNana.COM

    (and BEXP1 BEXP2 BEXP3)
    

    desugars to: CourseNana.COM

    (if BEXP1 (if BEXP2 (if BEXP3 #t #f) #f) #f)
    
  • or takes one or more argument forms, and evaluates to #t if any of its arguments evaluate to #t; otherwise it evaluates to #f. It is syntactic sugar for one or more if forms. E.g., CourseNana.COM

    (or BEXP1 BEXP2 BEXP3)
    

    desugars to: CourseNana.COM

    (if BEXP1 #t (if BEXP2 #t (if BEXP3 #t #f)))
    
  • cond is a multi-way conditional, similar to Racket's. It is syntactic sugar for one or more if forms. E.g., CourseNana.COM

    (cond [BEXP1 REXP1]
          [BEXP2 REXP2]
          [BEXP3 REXP3]
          [else REXP4])
    

    desugars to: CourseNana.COM

    (if BEXP 
        REXP
        (if BEXP2
            REXP2
            (if BEXP3
                REXP3
                REXP4)))
    

    note that the last "default" case is mandatory, and that else is syntactically required but not an identifier/variable. CourseNana.COM

  • <=>>= are syntactic sugar for combinations of <=, and or. E.g., CourseNana.COM

    (>= LHS RHS)
    

    desugars to: CourseNana.COM

    (or (< RHS LHS) (= LHS RHS))
    

define

The define form will be used to define one or more functions in a separate source file. This source file will be loaded and evaluated to create an environment within which we can either run a REPL or evaluate an expression. CourseNana.COM

The syntax of define is identical to that of Racket's (though we will not support "rest" parameters and any other options). E.g., below we define a function named sum with two parameters x and y, which returns their sum. CourseNana.COM

(define (sum x y)
  (+ x y))

You will implement the function load-defs, which takes the name of a file and returns an associative list containing all the name → function-value mappings defined in that file. E.g., given a file named "test1.defs" with the following contents: CourseNana.COM

(define (fn-a x)
  (+ x 10))

(define (fn-b x)
  (* x 20))

(define (fn-c x)
  (fn-a (fn-b x)))

Calling (load-defs "test1.defs") would return the following (nested closures are omitted): CourseNana.COM

(list
  (cons 'fn-a
        (fun-val 'x
                  (arith-exp "+" (var-exp 'x) (int-exp 10))
                  '(...)))
  (cons 'fn-b
        (fun-val 'x
                  (arith-exp "*" (var-exp 'x) (int-exp 20))
                  '(...)))
  (cons 'fn-c
        (fun-val 'x
                  (app-exp (var-exp 'fn-a)
                          (app-exp (var-exp 'fn-b) (var-exp 'x)))
                  '(...))))

This list is suitable for passing as an initial env argument to eval. I.e., after modifying eval to take an initial environment, we can do: CourseNana.COM

> (eval (desugar (parse '(fn-c 10)))
        (load-defs "test1.defs"))
210

Critically, define will allow us to define recursive functions. Note that our implementations of lambda and function application in class did not support recursion (it's worth taking some time to make sure you understand why not!). After correctly implementing define, however, we can evaluate a definition like: CourseNana.COM

(define (sum-to n)
  (if (= n 0)
      0
      (+ n
        (sum-to (- n 1)))))

Et voila: CourseNana.COM

> (eval (desugar (parse '(sum-to 10)))
        (load-defs "test2.defs"))
55

This will likely be the toughest part of this machine problem (though it doesn't translate into much code!). The most straightforward implementation does require a new mechanism: a cyclic structure. If you feel up for a challenge and want to figure it out for yourself, check out Immutable Cyclic Data in the Racket documentation. CourseNana.COM

For more detailed hints, see the "Hint" section in the next section. CourseNana.COM

Implementation and Starter code

All your changes should be made to "mp2.rkt". It is the only source file we will evaluate. CourseNana.COM

We provide you with the (slightly amended) interpreter that we wrote together in class. We also provide you with the following starter code for load_defs: CourseNana.COM

(define (load-defs filename)
  (let* ([sexps (file->list filename)]
         [fn-names (map (compose first second) sexps)])
    fn-names))

which reads all the s-expressions (corresponding to define forms) from the named file and returns a list of the function names being defined. You should use it as a starting point. CourseNana.COM

You are free to add new struct definitions, alter existing structs, define new functions, alter existing functions, etc. Just take care that you do not change the APIs of the parsedesugarevalload_defs, and repl functions, as we will be testing those directly. CourseNana.COM

Hint: On implementing recursion

First of all, recall that a "function value" is a structure that contains a function definition (consisting of parameter names and a body) and a closure. A closure represents the environment at the time the function is created, and is in our case just an associative list. CourseNana.COM

Here's the structure we defined: CourseNana.COM

(struct fun-val (id body env) #:transparent)

When we apply this function to an argument, we evaluate its body in the environment env, with a new mapping for the parameter and argument. CourseNana.COM

Here's the relevant bit from eval: CourseNana.COM

[(app-exp f arg)
    (match-let ([(fun-val id body clenv) (eval f env)]
                [arg-val (eval arg env)])
      (eval body (cons (cons id arg-val) clenv)))]

Now imagine that the body of the function contains a recursive call (i.e., a call to the function itself). Would we be able to locate the value corresponding to the function's own name? CourseNana.COM

No! The problem is that when we create a closure, we are saving the "outside" environment, but we are not saving the name of the function itself (which should map to the self-same function value). Here's where we create function values from lambdas in eval: CourseNana.COM

[(lambda-exp id body)
    (fun-val id body env)] -- env is the closure

See how the function value (and closure) doesn't see its own "name"? CourseNana.COM

To fix this, your implementation will need to create a cyclic structure. Specifically, you want the closure to refer to the function value in which it is contained. CourseNana.COM

To create a cyclic structure in Racket, we can use the make-placeholderplaceholder-set!, and make-reader-graph functions. Intuitively, make-placeholder creates a bookmark that can later be filled in by placeholder-set!, and make-reader-graph constructs a graph (which, unlike a tree, may contain cycles) based on these bookmarks. CourseNana.COM

E.g., to create a cyclic list of the infinitely repeating sequence: 1, 2, 3, 1, 2, 3, 1, 2, 3, ..., we can do: CourseNana.COM

(define inf-list
  (let* ([ph (make-placeholder '())]          ; placeholder with val '()
        [lst (cons 1 (cons 2 (cons 3 ph)))])  ; acyclic list ending with ph
    (placeholder-set! ph lst)  ; replace ph val with list head
    (make-reader-graph lst)))  ; read off the resulting cyclic list

We can use placeholders with Racket structs to create cyclic structures, too. We just need to mark those structs as "prefab", first. E.g., if we modify our function value struct as follows: CourseNana.COM

(struct fun-val (id body env) #:prefab)

We can do: CourseNana.COM

(define cyc-env
  (let* ([ph (make-placeholder '())]
         [env (list (cons 'f (fun-val 'x (int-exp 10) ph)))])
    (placeholder-set! ph env)
    (make-reader-graph env)))

And now we have a closure that refers back to the environment in which its associated function is defined! CourseNana.COM

Check it out: CourseNana.COM

> cyc-env
#0=(list (cons 'f (fun-val 'x (int-exp 10) #0#)))

> (fun-val-env (cdr (assoc 'f cyc-env)))
#0=(list (cons 'f (fun-val 'x (int-exp 10) #0#)))

(The #0= and #0# notation is to help us visualize the cyclical structure -- those values aren't actually present as data.) CourseNana.COM

Testing

We have provided you with test cases in "mp2-test.rkt" and sample definition files in "test1.defs" and "test2.defs". Feel free to add to and alter any and all tests, as we will be using our own test suite to evaluate your work. CourseNana.COM

Note that passing all the tests does not guarantee full credit! In particular, we will be checking that your desugaring function correctly transforms the syntax of syntactic sugar to core language forms, and that you aren't using any metacircular hacks. CourseNana.COM

Get in Touch with Our Experts

WeChat (微信) WeChat (微信)
Whatsapp WhatsApp
IIT代写,US代写,CS440代写,CS 440代写,Programming Languages代写,Racket代写,Interpreters代写,MP3代写,IIT代编,US代编,CS440代编,CS 440代编,Programming Languages代编,Racket代编,Interpreters代编,MP3代编,IIT代考,US代考,CS440代考,CS 440代考,Programming Languages代考,Racket代考,Interpreters代考,MP3代考,IIThelp,UShelp,CS440help,CS 440help,Programming Languageshelp,Rackethelp,Interpretershelp,MP3help,IIT作业代写,US作业代写,CS440作业代写,CS 440作业代写,Programming Languages作业代写,Racket作业代写,Interpreters作业代写,MP3作业代写,IIT编程代写,US编程代写,CS440编程代写,CS 440编程代写,Programming Languages编程代写,Racket编程代写,Interpreters编程代写,MP3编程代写,IITprogramming help,USprogramming help,CS440programming help,CS 440programming help,Programming Languagesprogramming help,Racketprogramming help,Interpretersprogramming help,MP3programming help,IITassignment help,USassignment help,CS440assignment help,CS 440assignment help,Programming Languagesassignment help,Racketassignment help,Interpretersassignment help,MP3assignment help,IITsolution,USsolution,CS440solution,CS 440solution,Programming Languagessolution,Racketsolution,Interpreterssolution,MP3solution,