Need help with Functional Programming in Inductive/Recursive Descriptions of Data assignments code. 1. Write Scheme programs (i.e. expressions) for each of the following identical definitions of a set S made up of natural numbers: (a) n S iff: (a) n = 0, and (b) (n 3) S. (the top-down style of definition.) (b) n S iff: (a) n = 0 S, and (b) if n S, then (n + 3) S. (the bottom-up style). (c) The inference rule style: n S iff: (a) 0S , and (b) nS (n+3)S. (An inference rule is of the form A B where A is called as the hypothesis (or antecedent), and B is called as the conclusion (or consequent). We read an inference rule as: If A, then B.. This means only that we can use the rule to conclude B given A. It does not mean that A implies B. An inference rule without the hypothesis is called as an axiom (as in (a) above). Axioms are often written with the horizontal line.) Try to write the programs so that they reflect the style of the definitions. Note that all the three definitions of the set S are identical.

2. Another problem similar to problem 1. We can define a list-of-integers using the three styles as below. Write Scheme programs for each. A Scheme list is a list of integers iff: (a) Top-down: (a) it is an empty list, or (b) it is a pair whose car is an integer and whose cdr is a list of integers. (b) Bottom-up: (a) () list-of-integers, and (b) if n Int and l list-of-integers, then (n . l) list-of-integers. (The infix dot notation (n . l) is the pair notation of Scheme.) (c) Inference rule: (a) () list-of-integers (an axiom), and (b) nInt, llistofintegers (n .l)listofintegers .

3. Grammars: A grammar is another way of defining recursive sets. Here is a list of integers defined using a grammar. ListOfInt := () (1) ListOfInt := (Int . ListOfInt) (2) The equations, called production rules, describe a recipe of producing the entity on the left of := using the prescription on its right. The entity on the left is called a non terminal. One or more non terminals may exist and can be described by a number of production rules. Some entities in a grammar never occur on the left. These are called terminals, and form the basic symbols that are usually intuitively clear. They are used to produce the non terminals. Thus the (, ), . and Int are terminal symbols, and ListOfInt is a non-terminal. A compact syntax for writing the above grammar is: ListOfInt := () | (Int . ListOfInt). Another compact syntax is: ListOfInt := ({Int} ), where the denotes zero or more occurrences of Int. In languages like Scheme, we represent code, i.e. expressions, as lists of symbols. Here is a grammar for S(ymbolic)-Expressions (short: S-Exps): SList := ({SExp}) (3) SExp := Symbol | SList Write a predicate, is-s-list?, that takes another Scheme program as a list, and returns true if it is an S-List and false otherwise. To what extent does your Scheme procedure (i.e. program) follow the inductive definition of an S-list? What aspects of your program differ, and why?

4. Another problem similar to problem 3. The calculus is a language that is made up of only variables (i.e. the ability to e name objects in a computation), procedures that take a single arguments (i.e. the ability to specify the transformation of objects into new ones), and procedure calls (i.e. the ability to apply). Here is the definition of a calculus expression as a grammar: LcExp := Identifier := (lambda (Identif ier) LcExp) := (LcExp LcExp) (5) Write a Scheme program that takes either an S-List or an S-Exp (see Prob. 3) and returns true if it is a expression, and false otherwise.

5. Write a Scheme procedure (i.e. a program), convert-to-string, that takes a natural number less than 100000, and returns its string representation. For example, when the number 12345 is given to convert-to-string, it should return the string one ten thousands two thousands three hundreds four tens five. Write a recursive solution!