Difference between revisions of "Itty Bitty Programming Language Assignment"

From CSE425S Wiki
Jump to navigation Jump to search
 
(29 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
=Credit=
 
=Credit=
 
This assignment is based on [[MUPL_Assignment|MUPL]] by Dan Grossman and his team at UW.
 
This assignment is based on [[MUPL_Assignment|MUPL]] by Dan Grossman and his team at UW.
 +
 +
=Code To Use=
 +
* [https://docs.racket-lang.org/reference/exns.html#%28def._%28%28quote._~23~25kernel%29._raise-argument-error%29%29 raise-argument-error]
 +
* [https://docs.racket-lang.org/reference/number-types.html#%28def._%28%28quote._~23~25kernel%29._exact-integer~3f%29%29 exact-integer?]
 +
* [https://docs.racket-lang.org/reference/pairs.html#%28def._%28%28lib._racket%2Flist..rkt%29._cons~3f%29%29 cons?]
 +
* [https://docs.racket-lang.org/reference/pairs.html#%28def._%28%28quote._~23~25kernel%29._null~3f%29%29 null?]
 +
* [https://docs.racket-lang.org/reference/pairs.html#%28def._%28%28quote._~23~25kernel%29._cons%29%29 cons]
 +
* [https://docs.racket-lang.org/reference/pairs.html#%28def._%28%28quote._~23~25kernel%29._car%29%29 car]
 +
* [https://docs.racket-lang.org/reference/pairs.html#%28def._%28%28quote._~23~25kernel%29._cdr%29%29 cdr]
  
 
=Code To Investigate=
 
=Code To Investigate=
 
==Ast==
 
==Ast==
 +
===Expression Structs===
 
<syntaxhighlight lang="racket">
 
<syntaxhighlight lang="racket">
 
(struct IdentifierExp (name)                                          #:transparent)
 
(struct IdentifierExp (name)                                          #:transparent)
Line 17: Line 27:
 
(struct FunctionExp  (name_option parameter_name body_exp)            #:transparent)
 
(struct FunctionExp  (name_option parameter_name body_exp)            #:transparent)
 
(struct CallExp      (function_exp argument_exp)                      #:transparent)
 
(struct CallExp      (function_exp argument_exp)                      #:transparent)
 +
</syntaxhighlight>
 +
===expression?===
 +
<syntaxhighlight lang="racket">
 +
(define (expression? exp)
 +
  (or (IdentifierExp? exp)
 +
      (IntExp? exp)
 +
      (AddExp? exp)
 +
      (IfGreaterExp? exp)
 +
      (NilExp? exp)
 +
      (IsNilExp? exp)
 +
      (ConsExp? exp)
 +
      (CarOfConsExp? exp)
 +
      (CdrOfConsExp? exp)
 +
      (LetExp? exp)
 +
      (FunctionExp? exp)
 +
      (CallExp? exp)))
 
</syntaxhighlight>
 
</syntaxhighlight>
  
 
=Code To Implement=
 
=Code To Implement=
 
==Warmup==
 
==Warmup==
{{RacketToImplement|warmup|racket-integers->ibpl-IntExps<br/>ibpl-IntExps->racket-integers|ibpl}}
+
{{RacketToImplement|warmup|racket-integers->ib-IntExps<br/>ib-IntExps->racket-integers|ibpl}}
  
===racket-integers->ibpl-IntExps===
+
===racket-integers->ib-IntExps===
  
===ibpl-IntExps->racket-integers===
+
===ib-IntExps->racket-integers===
  
==Eval==
+
==Interpreter==
{{RacketToImplement|eval|value?<br/>ensure-value?<br/>expand-environment<br/>eval-under-env|ibpl}}
+
{{RacketToImplement|interpreter|value?<br/>expand-environment<br/>evaluate|ibpl}}
  
 +
===closure===
 
<syntaxhighlight lang="racket">
 
<syntaxhighlight lang="racket">
 
(struct closure (env function) #:transparent)
 
(struct closure (env function) #:transparent)
Line 45: Line 72:
 
   (if (value? v)
 
   (if (value? v)
 
       v
 
       v
       (error (string-append "not a value: " (~a v)))))
+
       (raise-argument-error 'v "value?" v)))
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Line 59: Line 86:
  
 
===expand-environment===
 
===expand-environment===
 +
<syntaxhighlight lang="racket">
 +
(define (expand-environment name value env)
 +
        (error 'not-yet-implemented))
 +
</syntaxhighlight>
  
===eval-under-env===
+
'''Requirement:''' [https://docs.racket-lang.org/reference/exns.html#%28def._%28%28quote._~23~25kernel%29._raise-argument-error%29%29 raise-argument-error] for invalid parameters.
 +
 
 +
: <code>name</code> must be a <code>[https://docs.racket-lang.org/reference/strings.html#%28def._%28%28quote._~23~25kernel%29._string~3f%29%29 string?]</code>
 +
: <code>value</code> must be a <code>[[#value.3F|value?]]</code>
 +
: <code>env</code> must be a <code>[https://docs.racket-lang.org/reference/pairs.html#%28def._%28%28quote._~23~25kernel%29._list~3f%29%29 list?]</code>
 +
 
 +
===evaluate===
 +
Evaluate the expression <code>exp</code> in the environment <code>env</code>.
 +
 
 +
The provided shell ensures that the parameters <code>exp</code> and <code>env</code> pass expression? and list? respectively.  ensure-value? is then used to ensure that what you evaluate the expression to is correctly a value.
  
===eval-exp===
 
 
<syntaxhighlight lang="racket">
 
<syntaxhighlight lang="racket">
(define (eval-exp e)
+
(define (evaluate exp env)
   (eval-under-env e null))
+
   (if (expression? exp)
 +
      (if (list? env)
 +
          (ensure-value?
 +
                (error 'not-yet-implemented))
 +
          (raise-argument-error 'env "list?" env))
 +
      (raise-argument-error 'exp "expression?" exp)))
 
</syntaxhighlight>
 
</syntaxhighlight>
 +
 +
The evaluation of sub-expressions described below, unless otherwise specified, should be performed in the current environment <code>env</code>.  Any sub-expression evaluation which does not pass what is to be "ensured" should result in an [https://docs.racket-lang.org/reference/exns.html#%28def._%28%28quote._~23~25kernel%29._error%29%29 error].
 +
 +
* <code>IdentifierExp</code> evaluates to the value found by looking its name up in the environment.
 +
* <code>NilExp</code> evaluates to the empty list (this is: the value [https://docs.racket-lang.org/reference/pairs.html#%28def._%28%28quote._~23~25kernel%29._null%29%29 null])
 +
* <code>IntExp</code> evaluates to its value.
 +
* <code>AddExp</code> first evaluates its sub-expressions: left_exp and right_exp, ensures that they are [https://docs.racket-lang.org/reference/number-types.html#%28def._%28%28quote._~23~25kernel%29._exact-integer~3f%29%29 integers], and evaluates to the [https://docs.racket-lang.org/reference/generic-numbers.html#%28def._%28%28quote._~23~25kernel%29._%2B%29%29 sum] of the left and right values.
 +
* <code>ConsExp</code> first evaluates its sub-expressions: car_exp and cdr_exp, ensures that they are [[#value?|values]], and evaluates to a [https://docs.racket-lang.org/reference/pairs.html#%28def._%28%28quote._~23~25kernel%29._cons%29%29 cons] cell of the car and cdr values.
 +
* <code>CarOfConsExp</code> first evaluates its sub-expression: cons_exp, ensures that it is a [https://docs.racket-lang.org/reference/pairs.html#%28def._%28%28quote._~23~25kernel%29._pair~3f%29%29 pair], and evaluates to the [https://docs.racket-lang.org/reference/pairs.html#%28def._%28%28quote._~23~25kernel%29._car%29%29 car] of the pair.
 +
* <code>CdrOfConsExp</code> first evaluates its sub-expression: cons_exp, ensures that it is a [https://docs.racket-lang.org/reference/pairs.html#%28def._%28%28quote._~23~25kernel%29._pair~3f%29%29 pair], and evaluates to the [https://docs.racket-lang.org/reference/pairs.html#%28def._%28%28quote._~23~25kernel%29._cdr%29%29 cdr] of the pair.
 +
* <code>IfGreaterExp</code> first evaluates its sub-expressions: left_exp and right_exp, ensures that they are [https://docs.racket-lang.org/reference/number-types.html#%28def._%28%28quote._~23~25kernel%29._exact-integer~3f%29%29 integers], if the left value is [https://docs.racket-lang.org/reference/generic-numbers.html#%28def._%28%28quote._~23~25kernel%29._~3e%29%29 greater than] the right value then the result is the evaluation of the sub-expression then_body_exp, otherwise the evaluation of the sub-expression else_body_exp.
 +
* <code>IsNilExp</code> first evaluates its sub-expression: exp, and evaluates to <code>1</code> if it is the [https://docs.racket-lang.org/reference/pairs.html#%28def._%28%28lib._racket%2Flist..rkt%29._empty~3f%29%29 empty list], otherwise <code>0</code>.
 +
* <code>LetExp</code> first creates an expanded environment with the evaluation of the sub-expression: binding_exp bound to the binding_name, and then evaluates the sub-expression: body_exp in that expanded environment.
 +
* <code>FunctionExp</code> evaluates to a [[#closure|closure]] to support lexical scope.
 +
* <code>CallExp</code> first evaluates its sub-expression: function_exp and ensures that it is a closure.
 +
: An expanded environment is created from the closure's environment with:
 +
:: the closure bound to the closure's function's name, if the function has a name, and
 +
:: the evaluation of the CallExp's sub-expression argument_exp bound to the closure's function's parameter_name
 +
: The closure's function's body is then evaluated in this expanded environment.
  
 
==Macros==
 
==Macros==
 +
{{RacketToImplement|warmup|IbIfNil<br/>IbLet*<br/>IbIfEq|ibpl}}
 +
 +
Treat each Racket function as an Itty Bitty macro.  Return an abstract syntax tree of expressions which can later be evaluated.
 +
 +
'''Alert:''' do not invoke evaluate.  Each Racket function's return value should have all of the necessary logic encoded in its AST of expressions.
 +
 
===IbIfNil===
 
===IbIfNil===
 
===IbLet*===
 
===IbLet*===
Line 78: Line 147:
  
 
==Functions==
 
==Functions==
 +
Define Racket values which are abstract syntax trees of expressions that can be later evaluated.
 +
 +
'''Alert:''' do not invoke evaluate.  Each Racket value you  define should have all of the necessary logic encoded in its AST of expressions.
 +
 
===ib-double===
 
===ib-double===
 +
<syntaxhighlight lang="racket">
 +
; racket version for reference
 +
(define (racket-double n) (+ n n))
 +
</syntaxhighlight>
 +
 
===ib-sum-curry===
 
===ib-sum-curry===
 +
<syntaxhighlight lang="racket">
 +
; racket version for reference
 +
(define (racket-sum-curry a) (lambda (b) (+ a b)))
 +
</syntaxhighlight>
 
===ib-call-with-one===
 
===ib-call-with-one===
 +
<syntaxhighlight lang="racket">
 +
; racket version for reference
 +
(define (racket-call-with-one proc) (proc 1))
 +
</syntaxhighlight>
 
===ib-map===
 
===ib-map===
===ib-mapAddN===
+
===ib-map-add-n===
  
 
=Testing=
 
=Testing=
 +
{{RacketUnitTest|test_all|ibpl}}

Latest revision as of 02:45, 5 April 2023

Credit

This assignment is based on MUPL by Dan Grossman and his team at UW.

Code To Use

Code To Investigate

Ast

Expression Structs

(struct IdentifierExp (name)                                           #:transparent)
(struct IntExp        (value)                                          #:transparent)
(struct AddExp        (left_exp right_exp)                             #:transparent)
(struct IfGreaterExp  (left_exp right_exp then_body_exp else_body_exp) #:transparent)
(struct NilExp        ()                                               #:transparent)
(struct IsNilExp      (exp)                                            #:transparent)
(struct ConsExp       (car_exp cdr_exp)                                #:transparent)
(struct CarOfConsExp  (cons_exp)                                       #:transparent)
(struct CdrOfConsExp  (cons_exp)                                       #:transparent)
(struct LetExp        (binding_name binding_exp body_exp)              #:transparent)
(struct FunctionExp   (name_option parameter_name body_exp)            #:transparent)
(struct CallExp       (function_exp argument_exp)                      #:transparent)

expression?

(define (expression? exp)
  (or (IdentifierExp? exp)
      (IntExp? exp)
      (AddExp? exp)
      (IfGreaterExp? exp)
      (NilExp? exp)
      (IsNilExp? exp)
      (ConsExp? exp)
      (CarOfConsExp? exp)
      (CdrOfConsExp? exp)
      (LetExp? exp)
      (FunctionExp? exp)
      (CallExp? exp)))

Code To Implement

Warmup

file: src/main/racket/ibpl/warmup.rkt Racket-logo.svg
functions: racket-integers->ib-IntExps
ib-IntExps->racket-integers

racket-integers->ib-IntExps

ib-IntExps->racket-integers

Interpreter

file: src/main/racket/ibpl/interpreter.rkt Racket-logo.svg
functions: value?
expand-environment
evaluate

closure

(struct closure (env function) #:transparent)

value?

IBPL expressions evaluate to Racket values. value? determines if the paramater v is a valid value.

Valid value types are cons cells, integers, closures, and the null empty list.

For a cons cell to be a valid value, its car and cdr must be valid values.

ensure-value?

(define (ensure-value? v)
  (if (value? v)
      v
      (raise-argument-error 'v "value?" v)))

lookup-value-in-environment

(struct entry (name value) #:transparent)

(define (lookup-value-in-environment env identifier-name)
  (cond [(null? env) (error "unbound identifier during evaluation" identifier-name)]
        [(equal? (entry-name (car env)) identifier-name) (entry-value (car env))]
        [#t (lookup-value-in-environment (cdr env) identifier-name)]))

expand-environment

(define (expand-environment name value env)
        (error 'not-yet-implemented))

Requirement: raise-argument-error for invalid parameters.

name must be a string?
value must be a value?
env must be a list?

evaluate

Evaluate the expression exp in the environment env.

The provided shell ensures that the parameters exp and env pass expression? and list? respectively. ensure-value? is then used to ensure that what you evaluate the expression to is correctly a value.

(define (evaluate exp env)
  (if (expression? exp)
      (if (list? env)
          (ensure-value? 
                 (error 'not-yet-implemented))
          (raise-argument-error 'env "list?" env))
      (raise-argument-error 'exp "expression?" exp)))

The evaluation of sub-expressions described below, unless otherwise specified, should be performed in the current environment env. Any sub-expression evaluation which does not pass what is to be "ensured" should result in an error.

  • IdentifierExp evaluates to the value found by looking its name up in the environment.
  • NilExp evaluates to the empty list (this is: the value null)
  • IntExp evaluates to its value.
  • AddExp first evaluates its sub-expressions: left_exp and right_exp, ensures that they are integers, and evaluates to the sum of the left and right values.
  • ConsExp first evaluates its sub-expressions: car_exp and cdr_exp, ensures that they are values, and evaluates to a cons cell of the car and cdr values.
  • CarOfConsExp first evaluates its sub-expression: cons_exp, ensures that it is a pair, and evaluates to the car of the pair.
  • CdrOfConsExp first evaluates its sub-expression: cons_exp, ensures that it is a pair, and evaluates to the cdr of the pair.
  • IfGreaterExp first evaluates its sub-expressions: left_exp and right_exp, ensures that they are integers, if the left value is greater than the right value then the result is the evaluation of the sub-expression then_body_exp, otherwise the evaluation of the sub-expression else_body_exp.
  • IsNilExp first evaluates its sub-expression: exp, and evaluates to 1 if it is the empty list, otherwise 0.
  • LetExp first creates an expanded environment with the evaluation of the sub-expression: binding_exp bound to the binding_name, and then evaluates the sub-expression: body_exp in that expanded environment.
  • FunctionExp evaluates to a closure to support lexical scope.
  • CallExp first evaluates its sub-expression: function_exp and ensures that it is a closure.
An expanded environment is created from the closure's environment with:
the closure bound to the closure's function's name, if the function has a name, and
the evaluation of the CallExp's sub-expression argument_exp bound to the closure's function's parameter_name
The closure's function's body is then evaluated in this expanded environment.

Macros

file: src/main/racket/ibpl/warmup.rkt Racket-logo.svg
functions: IbIfNil
IbLet*
IbIfEq

Treat each Racket function as an Itty Bitty macro. Return an abstract syntax tree of expressions which can later be evaluated.

Alert: do not invoke evaluate. Each Racket function's return value should have all of the necessary logic encoded in its AST of expressions.

IbIfNil

IbLet*

(struct binding (name exp) #:transparent)

IbIfEq

Functions

Define Racket values which are abstract syntax trees of expressions that can be later evaluated.

Alert: do not invoke evaluate. Each Racket value you define should have all of the necessary logic encoded in its AST of expressions.

ib-double

; racket version for reference
(define (racket-double n) (+ n n))

ib-sum-curry

; racket version for reference
(define (racket-sum-curry a) (lambda (b) (+ a b)))

ib-call-with-one

; racket version for reference
(define (racket-call-with-one proc) (proc 1))

ib-map

ib-map-add-n

Testing

file: test_all.rkt Racket-logo.svg Test
source folder: src/test/racket/ibpl

note: ensure that you have removed all printing to receive credit for any assignment.