Homework 12🔗

Last updated: Mon, 25 Nov 2024 10:22:28 -0500

Out: Mon Nov 25, 2024, 12pm (noon) EST

Due: Wed Dec 04, 2024, 12pm (noon) EST

Overview🔗

In this assignment, we will continue adding features to our "CS450 Lang" "high-level language". By continuing to use the design recipe, however, even advanced features can be added in a straightforward way.

This hw will be graded accordingly:

Setup🔗

Create a new repository for this assignment by going to the CS450 Fall 2024 GitHub Organization and clicking "New".

Note: The CS450 Fall 2024 GitHub Organization must be the owner of the repository. Do not create the repository in your own account.

When done click "Create repository".

Tasks🔗

Reading

• Review the The Design Recipe section of the course website (topics that will be covered in future lectures are marked as such).

Notes and Reminders

• All code you write must now follow the The Design Recipe. (Just submitting code is no longer sufficient.)

• Signatures should use define/contract and the predicates defined in the Data Design Recipe step.

• For Examples and Tests, do not use check-expect from the Beginning Student Language (even though the textbook says to). Instead, use check-equal? or other testing forms from rackunit.

• Examples for a function definition should come right after the define. But Tests should be put into the test-suite in tests.rkt. Try to think about corner cases and code coverage.

• Also, remember that Racket Style and The Design Recipe reserves certain language features only for specific scenarios. For example, set! and other "imperative" features are not allowed ever. Conditionals such as cond should only be used with enumeration or itemization Data Definitions.

• The submitted program must be only a series of defines (both constants and function definitions are allowed) and tests/examples. Do not run any other code, i.e., do not automatically start big-bang! Not following this this will result in GradeScope errors and point deductions.

• You may find the "Syntactic Test Coverage" feature in DrRacket useful. At minimum, one-hundred percent of your code should be run (if not tested) before submission.

• The main code should go in a file named hw12.rkt and tests should go in a tests.rkt file of the appropriate format.

  In this assignment, each function should have at minimum of one (meaningful) Example and two Tests (that are not the same as the example).

Programming

In this assignment, we will add user-defined "lambda" functions to our "CS450 Lang" programming language.

(Note that this assignment can be completed using only information given in the lecture notes. It does not require solutions for any previous homeworks.)

Specifically, write the following functions to accommodate the Data Definitions below. Note that in some instances, the exact data definition is not specified and is left up to you to design.

As usual, you must follow the The Design Recipe (and it will be difficult to complete the assignment if you do not).

Functions

• parse : takes a 450LangExpr (abbreviated Expr) "program" and produces a 450LangAST abstract syntax tree (abbreviated AST) data structure.

  This function should raise a exn:fail:syntax:cs450 exception that you define (which should be a substruct of exn:fail:syntax) if the input is not a valid Expr (but passes the shallow contract check).

• run : takes a 450LangAST tree (abbreviated AST) and "runs" it, to produce a 450LangResult "result" (abbreviated Result).

  This function should define an internal function, e.g., run/env that uses an Environment accumulator. Make sure to follow all steps of the accumulator Design Recipe.

  The initial environment should contain bindings for + and - variables only. These identifiers should be bound to Racket functions that perform the respective arithmetic operations if given (any number of) number inputs, and NaN if any of the input arguments are not numbers.

  The run function should also internally a define a 450apply : FunctionResult -> Result function that is used by run/env to "runs" function calls appropriately based on the type of input.

• exn:fail:syntax:cs450? : returns true if given a exn:fail:syntax:cs450 exception, which should be thrown by parse when given an invalid program, e.g., (fn (x)).

• NaN? : returns true if given a NaN Result, which should be produced when trying to perform arithmetic on non-numbers.

• fn-result? : returns true if given a fn-result Result, which should be the result when "running" a fn program.

• UNDEFINED-ERROR? : returns true if given an UNDEFINED-ERROR Result, which should occur if the program attempts to use an undefined variable.

• NOT-FN-ERROR? : returns true if given a NOT-FN-ERROR Result, which should occur if the program attempts to call a non-function value.

• ARITY-ERROR? : returns true if given a ARITY-ERROR Result, which should occur if the program attempts to call a function with the wrong number of arguments.

Data Definitions

• A Variable (Var) is a Symbol

• An Environment is a List<(list Var Result)>

  Interpretation: gives meaning to variables in a program. Bindings that occur earlier in the list shadow those that occur later.

• A 450LangExpr (Expr for short) is one of:

  • Number

  • Variable

  • ’(bind [Var Expr] Expr)

  • ’(fn List<Var> Expr)

  • (cons Expr List<Expr>)

  Interpretation: represents the surface-level syntax of CS450Lang programs. The last item is a function call, where the function to apply may either be a Racket function (if using a "built in" identifier), or a user-defined fn "lambda" function.

• A 450LangAST (AST for short) is one of:

  • (num Number)

  • (vari Symbol)

  • ????

  • (fn-ast List<Symbol> AST)

  • ????

  Interpretation: represents code before it is "run", i.e., it’s not a Result yet. Specifically, it is an abstract syntax tree data structure that is produced from parsing the surface program

  NOTE: It is recommended that you do not name your Variable AST node var. Past students have run into problems with this due to unintended shadowing (because var is also a match pattern name).

• A 450LangResult (Result for short) is one of:

  • Number

  • NaN

  • FnResult

  • ErrorResult

  Interpretation: possible results after running a CS450Lang program. In this assignment, a NaN should be the result of any arithmetic involving non-number arguments.

• A FnResult is one of:

  • Racket function

  • (fn-result List<Symbol> AST Environment)

  Interpretation: possible functions that can be called in a CS450Lang program. The second is user-defined and is analogous to a lambda in Racket. Note that the fn-result Result differs from the fn-ast AST node in that the former represents a result of running a program and must contain an Environment that gives meaning to any free variables in the body of the function, while the latter merely represents source code.

• An ErrorResult is one of:

  • UNDEFINED-ERROR

  • NOT-FN-ERROR

  • ARITY-ERROR

  Interpretation: possible "error" results of a CS450Lang program.

  • An "undefined" error should occur when trying to use an undefined variable.

  • A "not fn" error should occur if attempting to call a non-function.

  • An "arity" error should occur if attempting to call a function with the wrong number of arguments. (Note that the arithmetic functions in the initial environment should handle any number of arguments and should not generate this error.)

  If one of these errors occurs in an inner expression, it should propagrate to be the final result of the whole expression. If more than one error occurs, e.g., in arguments of a function call, their ordering the data definition specifies their precedence.

Before Submitting🔗

Testing

Style

All code should follow proper Racket Style.

Also, the repository itself must follow proper style. Specifically, it must have appropriate commit messages. See How to Write a Git Commit Message if you are unsure how to write a commit message.

Files

A submission must have the following files in the repository root:

• hw12.rkt: Contains the hw solution code.

  All defines should use the name specified in the exercise (ask if you are unsure) and should be provided.

  The easiest (but not always the most readable) way to ensure all necessary definitions are provided is to (initially) put as the second line in the file:

  (provide (all-defined-out))

  This automatically provides all definitions in the file. (The first line should be #lang racket)

• tests.rkt: This file should require hw12.rkt and define tests for it.

  Specifically, it should define a rackunit test-suite which contains sufficient rackunit test cases (e.g., check-equal?, etc.) for each defined function.

• README.md: Contains the required README information, including the GitHub repo url.

Submitting🔗

When you are done, submit your work to Gradescope hw12. You must use the "GitHub" Submission Method and select your hw<X>-<LASTNAME>-<FIRSTNAME> repository.

Note that this is the only acceptable way to submit homework in this course. (Do not manually upload files and do not email files to the course staff. Homework submitted via any unapproved methods will not be graded.)