# Project 1 Challenge Tasks
There are three challenge tasks for project 1, weighted equally.
Copyright By PowCoder代写 加微信 powcoder
## The `quote` special form
The first task is to implement a special form `quote`. The `quote` special form simply returns its argument, unevaluated, as a Scheme datum. For example, the expression `(quote (1 2 3))` returns the proper combination `(1 . (2 . (3 . ())))`. Similarly, the proper expression `(quote (+ 1 2))` returns the proper combination `(+ . (1 . (2 . ())))`, where the first element in the combination is the *unevaluated* symbol `+`.
This provide a good opportunity to check that your `eq?` function is implemented properly: the expression
(eq? (fst (quote (+ 1 2))) (quote +))
should evaluate to `#t`.
The provided parser supports two syntactic shortcuts for writing quoted expressions. First, `’e` is equivalent to `(quote e)`. So, the previous expression could have been written:
(eq? (fst ‘(+ 1 2)) ‘+)
Second, a quoted list can be written in braces:
(eq? (fst {+ 1 2}) ‘+)
You do not have to do anything extra to support this syntax.
## The `eval` primitive function
The second challenge task is to implement a primitive `eval`, which evaluates its argument as if it were a Scheme expression. Note that evaluate is *not* a special form: in the expression `(eval e)`, first `e` is evaluated to find the argument to `eval`; second, the result of evaluating `e` is evaluated as if it were a Scheme expression.
Here is an example:
(eval (cons ‘+ (cons 1 (cons 2 ‘()))))
The argument evaluates to the proper combination `(+ 1 2)`, (where `+` is so far an uninterpreted symbol). Then, `eval` evaluates that resulting combination as a special form, producing 3.
## The `splice` special form
The final challenge task is to implement a special form `splice`.
This special form is unusual in that it is only meaningful *inside* a `quote` special form; `splice` outside of a `quote` fails to evaluate.
Inside a `quote`, the expression `(splice e)` is *not* included in the result of the `quote`; instead, the expression `e` is evaluated and its result is included in the `quote`. For example, the term:
{+ 1 (+ 1 2) 3}
evaluates to the proper combination `(+ 1 (+ 1 2) 3)`, where the `+`s are both uninterpreted symbols. On the other hand, the term
{+ 1 (splice (+ 1 2)) 3}
evaluates to the proper combination `(+ 1 3 3)`, where the spliced expression has been evaluated.
The provided parser supports a syntactic shortcut for writing splices: `$e` is equivalent to `(splice e)`. So the above example could have been written `{+ 1 $(+ 1 2) 3}`. You do not have to do anything extra to support this syntax.
# MiniScheme
MiniScheme is an eagerly-evaluated functional programming language. While MiniScheme is, like Haskell, based on the lambda-calculus, it differs from Haskell in several important ways:
* MiniScheme is *eagerly evaluated*: function arguments are evaluated before function calls, instead of delaying evaluation until argumenst are needed.
* MiniScheme is *untyped*: the same MiniScheme data may be given multiple interpretations depending on the context, and your MiniScheme evaluator will not be able to assume that arguments are of the right form.
* MiniScheme supports *multiple-argument functions*: unlike Haskell, where multi-argument functions are simulated with single-argument functions, MiniScheme has multiple argument functions. In fact, many MiniScheme functions can take variable numbers of arguments.
* MiniScheme is *syntactically simple*: unlike Haskell, MiniScheme has a very simple syntax.
This document describes the MiniScheme language. You should refer to it (as well as the examples and test cases) to direct your implementation of MiniScheme.
The core data structure of MiniScheme is the *datum*. We will use data to represent both MiniScheme values and programs. (In fact, one of the key features of languages like Scheme is that programs can be represented as data.)
Data comes in five kinds:
* Numbers `1`, `-217`, `42` are data.
* Booleans `#t`, `#f` are data. In any use of Booleans, MiniScheme will treat all non-`#f` as truth.
* Symbols `x`, `+`, `f1` are data. Symbols consist of any sequence of letters, numbers, and punctuation that does not start with a number or one of the characters `#`, `’`, `.`, `$`.
* If `d` and `e` are data, then the pair `(d . e)` is data.
* The “nil” value `()` is data.
Note that MiniScheme treats `()` and `[]` as equivalent. That is, you could also choose to write the nested pairs `((1 . 2) . (3 . 4))` as `[(1 . 2) . (3 . 4)]`, `([1 . 2] . [3 . 4])` or `[[1 . 2] . [3 . 4]]`. MiniScheme treats all of these identically.
There are two additional categorizations of data. *Proper lists* are defined by:
* `()` is a proper list
* `(d . e)` is a proper list if `e` is a proper list.
The proper list `(d1 . (d2 . (d3 . ())))` can also be written `(d1 d2 d3)`. (These representations are *equivalent*.) Proper lists in MiniScheme play the role of lists in Haskell; they are also central to representing MiniScheme programs.
*Improper* lists are lists that do not end with `()`. An improper list `(d1 . (d2 . (d3 . d4)))` can also be written `(d1 d2 d3 . d4)`. (Note that, technically, any pair is an improper list, and the syntax for a two-element improper list aligns exactly with that of a pair. Nevertheless, improper lists will play a role in defining MiniScheme programs later in the project.)
# Evaluation
Evaluation of MiniScheme programs is described as transformation on MiniScheme data—that is, MiniScheme programs and values are *both* represented using data.
Evaluation is defined by the following rules.
1. Numbers `-1`, `42` evaluate to themselves.
2. Boolean constants `#t`, `#f` evaluate to themselves.
3. Symbols `+`, `x` are treated as variables. However, in this stage of the project we do not yet have any user-defined functions or values, so symbols will *only* evaluate if they name primitive functions. (Primitive functions are defined later in this document.)
4. Proper lists `(d1 d2 … dn)` evaluate depending on `d1`. In general, there are three cases.
– `d1` may be a symbol naming a *special form*—that is to say, a language feature of MiniScheme—such as `if`, `or,` `define`, or `lambda`. In this case, the evaluation of `(d1 d2 … dn)` is specific to that special form; rules for special forms are given in the next section.
– `d1` may be an expression evaluating to a user-defined function. At this point, we do not have user-defined functions, so we do not need to implement this case.
– `d1` may be a symbol identifying a primitive function. In this case, the remaining arguments `d2`, `d3`, … are evaluated (following the same rules), and the primitive function is called with the resulting values as arguments. Primitive functions are described following special forms.
5. Attempting to evaluate other forms of data is an error.
For example, suppose we were evaluating the datum `(+ 1 (+ 2 3))`.
– We would begin by observing the symbol `+`; this is the name of a primitive function.
– We would evaluate the arguments. `1` is a number and so evaluates to itself. The second argument is a combination, so we proceed (recursively):
– We begin by observing symbol `+`; this is the name of a built-in function.
– We would evaluate the arguments. `2` and `3` are numbers and so each evaluates to itself.
– We would then invoke the primitive `+` function with arguments `2` and `3`, getting result `5`.
– We would then invoke the primitive `+` function with arguments `1` and `5`, getting result `6`.
# Special Forms
Special forms are the “language features” of MiniScheme. Because MiniScheme is eagerly evaluated, many features that are implemented as functions in Haskell are special forms in Scheme. This section enumerates the special forms you should implement in your evaluator.
## Conditionals
MiniScheme has two forms of conditionals.
The simpler form is `if`. The expression `(if d1 d2 d3)` is evaluated by first evaluating `d1`. If `d1` evaluates to `#f`, then the result of evaluating the expression is the result of evaluating `d3`. Otherwise, it is the result of evaluating `d2`. For example, `(if #t 1 2)`, `(if (eq? 1 1) 1 2)` and `(if 0 1 2)` all evaluate to `1`. On the other hand, `(if #f 1 2)` and `(if (eq? 1 2) 1 2)` evaluate to `2`.
The more complex form is `cond`. The `cond` can be given any number (more than 1) of *branches*, each of which is the of the form `(e1 e2)` for two data `e1` and `e2`. For example, the following are syntactically valid instances of `cond`:
(cond [(eq? 1 1) 1] [else 2])
(cond [(eq? 1 2) (+ 1 1)] [(eq? 1 1) (- 1 2)] [#t 3])
(cond [#f 1] [#t 2] [else 3])
A `cond` special form is evaluated by checking the branches in order. In a branch `(e1 e2)`, if `e1` evaluates to anything other than `#f`, the result of the `cond` is the result of evaluating `e2`. Otherwise evaluation continues to the next branch.
If the symbol `else` appears as expression `e1`, then the result of the `cond` is `e2`.
If no `e1` evaluates to a non-`#f` value, or is the symbol `else`, evaluation should fail.
## Booleans
MiniScheme has two conditions for manipulating Booleans.
The special form `(and e1 e2 … en)` computes the conjunction of `e1` … `en`. With no arguments, `(and)` evaluates to `#t.` Otherwise, arguments to `and` are evaluated left-to-right. If any argument evaluates to `#f`, the `and` evaluates to `#f` **without evaluating any further arguments**. Otherwise, the `and` evaluates to the result of the final argument. For example, `(and #f 1 2)` and `(and 1 2 #f)` both evaluate to `#f`; `(and 1 2 3)` evaluates to `3`.
The special form `(or e1 e2 … en)` computes the disjunction of `e1` … `en`. With no arguments, `(or)` evaluates to `#f`. Otherwise, the arguments to `or` are evaluated left-to-right. If any argument evaluates to a non-`#f` value, the `or ` evaluates to that value **without evaluating any further arguments**. Otherwise, the `or` evaluates to `#f`. For example, `(or 1 2 3)` evaluates to `1`; `(or 3 2 1)` evaluates to `3`; and, `(or (eq? 1 2) (eq? 2 1))` evaluates to `#f`.
These are special forms rather than primitive functions because they need not evaluate all their arguments.
# Primitive functions
In addition to the special forms, MiniScheme also has a number of *primitive* (or built-in) functions. Unlike special forms, these functions obey the normal evaluation rules: all of their arguments are evaluated before the function is applied. However, they provide primitive functionality that otherwise could not be expressed with MiniScheme programs. Each intrinsic function is defined for a specific number of arguments; calling it with a different number of arguments causes evaluation to fail.
* `(eq? e1 e2)`: if `e1` and `e2` evaluate to identical values, then this function returns `#t`. Otherwise, it returns `#f`. With other than two arguments, evaluation fails.
* `(+ e1 e2 .. en)`: with no arguments, `(+)` returns 0. If all its arguments evaluate to numeric values, `+` returns their sum; otherwise, evaluation fails.
* `(- e1 e2 .. en)`: with no arguments, evaluating `(-)` fails. If all its arguments evaluate to numeric values, `-`, computes the difference `e1` – `e2` – `e3` – .. – `en`; otherwise, evaluation fails.
* `(* e1 e2 .. en)`: with no arguments, `(*)` returns 1. If all its arguments evaluate to numeric values, `*` returns their product; otherwise, evaluation fails.
* `(= e1 e2 .. en)`: with no arguments, evaluating `(=)` fails. If all its arguments evaluate to numeric values, then `(= e1 e2 .. en)` returns `#t` if their values are equal, and `#f` if their values are not; if any arguments evaluate to non-numeric values, evaluation fails. The primitive functions `<`, `<=`, `>`, `>=` are defined similarly. For example, `(<)` fails, while `(< e1 e2 .. en)` returns #t if each argument evaluates to a number less than the next argument, `#f` if one argument evaluates to a number greater than or equal to the next argument, and fails to evaluate if any argument evaluates to anything other than a number. * `(cons e1 e2)`: returns the pair `(v1 . v2)`, where `v1` is the evaluation of `e1` and `v2` is the evaluation of `e2`. * `(fst e)`: if `e` evaluates to a pair `(v1 . v2)`, returns `v1`. Otherwise, evaluation fails. * `(snd e)`: if `e` evaluates to a pair `(v1 . v2)`, returns `v2`. Otherwise, evaluation fails. * `(list e1 e2 .. en)`: evaluates to the proper collection `(e1 . (e2 . (... . (en . ())))`. Without arguments, evaluates to the nil value. * `(number? e)`: if `e` evaluates to a numeric value, returns `#t`; otherwise, returns `#f`. * `(boolean? e)`: if `e` evalutes to a Boolean value, return `#t`; otherwise, returns `#f`. * `(pair? e)`: if `e` evaluates to a pair value, returns `#t`; otherwise, returns `#f`. * `(nil? e)`: if `e` evaluates to the nil value, returns `#t`; otherwise, returns `#f`. * `(list? e)`: if `e` evaluates to a proper list, returns `#t`; otherwise, returns `#f`. # Overview This document contains a general overview of project 1. Specific details are contained in the other Markdown files in this directory. You should read all the documentation carefully before beginning to work on the project. # Project 1 Tasks In project 1, you will begin implementing a language "MiniScheme", based (loosely) on the Scheme programming language. The MiniScheme language is described in [MiniScheme.md](MiniScheme.md). You have three primary tasks: 1. Implement an abstract syntax tree for MiniScheme. 2. Implement an evaluation function for MiniScheme, including a set of primitive, or built-in operations. 3. Implement a printer for MiniScheme. Each of these tasks is described in more detail in [Tasks.md](Tasks.md). Finally, you will write a function `run` in the `Main.hs` module which ties together your evaluator and printer. # Directory Organization The project directory contains several subdirectories. * `docs`: Contains the descriptions of the project and the MiniScheme language. * `prov`: Contains Haskell code provided as part of the project. **You should not change any code within the `prov` directory.** * `src`: Contains source code that you write as part of the project. Finally, there are the usual dot files in the root of the project folder. You can put all your project code into `Main.hs`. However, you may find it more useful to divide your project code among several modules—for example, an `AST` module for your syntax tree, a `Printer` module for your pretty printer, and so forth. If you add additional modules to your project, you **must** update the `Project.cabal` file in the root of the project accordingly. You should add each new module you create to the `other-modules` list in **both** the `minis` and `Test` targets. Please see [the Cabal documentation](https://cabal.readthedocs.io/en/3.6/intro.html) for more details. # Executables `Project.cabal` defines two executable targets. `minis` is an evaluator for MiniScheme programs: it takes a list of files, and interprets the contents of those files as MiniScheme expressions using your evaluation and printing functions. For example, you could invoke: $ cabal run minis examples/add.scm This behavior is defined in the `main` function in `src/Main.hs`. We do *not* use this main function in testing, so you are free to add additional output as you find useful. `Test` is the test runner target, as in the problem sets. Our tests for the project are essentially end-to-end tests: each test generates a source MiniScheme expression, sends it to your evaluator *and* printer functions (via the `run` function you write), and then compares your result against the expected result. Note that you do *not* have to match the exact formatting of the expected result (for example: you don't have to match spaces, line breaks, or so forth). You do, however, have to produce valid syntax; for example, if the expected result is the list "(1 2 3)", and your output omits the parentheses "1 2 3", the test will not be considered passing. This means that you have to have *some* evaluation and *some* printing code to pass any of the tests. It does not mean you have to have *all* of the evaluation and printing code to pass any of the tests. I strongly encourage you to work iteratively: implement the minimal functionality needed to pass tests, rather than trying to implement the entire evaluator before testing. Your evaluation function will be expected to return a `Nothing` value if evaluation fails (for example, if you try to subtract an empty list of numbers, or take the length of an integer). We have included test cases where evaluation should fail; those test cases will not be considered passing if your evaluator crashes (for example, raises an incomplete pattern match exception) rather than returning `Nothing`. # Challenge The challenge problems for project 1 consists of implementing several additional special forms, which draw on the ability to represent Minischeme programs as Minischeme data, and is described in [Challenge.md](Challenge.md). # Project 1 Tasks Project 1 includes three tasks, described here. For detail on each task, you should also consult the description of [MiniScheme](MiniScheme.md). # Task 1: MiniScheme AST Your first task is to define an *abstract syntax tree* for MiniScheme—that is, a data type that represents MiniScheme expressions. This data type will serve as both the input and output of your evaluation function, as well as the input to your printing functions. The Scheme standard calls Scheme's AST "data", and similarly we have called the AST type `Datum` (in `src/Main.hs`). You do not have to keep this name, but if you do change it, you should change the type signature for `run` accordingly. You also do not have to leave the AST definition in `Main.hs`; if you move it to another file, make sure to update `Project.cabal` to include that file in the `other-modules` for both the `minis` and `Test` targets. You can define your AST as you choose. However, we strongly recommend that you closely follow the specification of Scheme data given in [MiniScheme.md](MiniScheme.md). In particular, note that proper and improper lists are *specific cases of* pairs, not an alternative to pairs. If you represent them separately from pairs in your AST, you are likely to make later parts of the project more complicated. (You may, of course, find it useful to write functions that map between pairs and more Haskell-friendly representations of proper and improper lists to use in writing your evaluator.) You must also make your `Datum` type an instance of the `SchemeData` class, defined in `prov/Interface.hs`. The `SchemeData` class provides a uniform interface to your `Datum` type, allowing our parser (`prov/Parser.hs`) to generate values in your `Datum` type. It also provides the basis for how we will test your code. As in the interface you defined in Problem Set 4, many of the functions in `SchemeData` will correspond directly (or almost directly) to constructors in your `Datum` type. Again, if you choose to move your `Datum` type to a different module, you may wish to move its `SchemeData` instance to that module as well. # Task 2: MiniScheme Evaluator Your second task is to define an *evaluation function* for MiniScheme. Your evaluator must implement the evaluation model and all the special forms and primitive functions described in the [MiniScheme description](MiniScheme.md). Your evaluation function must not crash (for example, throw incomplete pattern match exceptions) in cases where evaluation is undefined. To capture such cases, you will likely want your evaluation func 程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com