HW 3.1

Due: before class on Wednesday 15 October

What are some benefits of using a functional programming (FP) style? Select all that apply.

(Refer back to the notes from class 2.7 if you need a refresher.)
1. An expression can be replaced by its value without changing the program’s behavior (referential transparency), which makes code easier to parallelize and optimize.
2. It significantly reduces memory usage compared to imperative programming because new data structures are rarely created.
3. Code becomes easier to reason about and less prone to bugs, as functions do not have side effects and data structures are generally immutable.
4. It relies on commands like set! to manage state, making changes easier for the programmer to track.
5. Functions are more modular and easier to test and compose, since their output depends solely on their input arguments rather than on program state.
Select all TRUE statements regarding parse trees and abstract syntax trees (ASTs):
1. Parse trees are generated during the Semantic Analysis stage, while ASTs are generated during Lexical Analsys.
2. An AST is generally simpler and less cluttered than the corresponding parse tree for the same program.
3. Syntactic elements like semicolons and parentheses are essential components of an AST’s structure.
4. A parse tree’s structure is tightly coupled to the specific grammar rules of the language.
5. An AST represents the program’s semantic meaning rather than its syntactic structure.
In class we contrasted functional programming against declarative/procedural style.

Consider this short Python function:
```
def alchemy(lst):
    i = 0
    while i < len(lst):
        if lst[i] == 'lead':
            lst[i] = 'gold'
        i += 1
```
1. Explain why the Python function alchemy is a clear example of the imperative programming style.
2. Now write a Scheme function (alchemy lst) which accomplishes the same goal but in a purely functional programming style.
  
  For example, it should work like this:
```
> (alchemy '(copper lead gold silver lead))
(copper gold gold silver gold)
```
  Hint: You probably want to use the built-in function symbol=?
A core idea of functional programming is that functions are first class data that can be passed to and returned from other functions.

Write a Scheme function called (compose f g) that takes two functions, f and g, as arguments. It should return a new function (created with lambda) that takes a single argument x and computes the mathematical composition \(f(g(x))\)

For example:
```
> (define (add1 x) (+ x 1))
> (define (double x) (* x 2))
> (define add1 (lambda (x) (+ x 1)))
> (define double (lambda (x) (* x 2)))
> (define double-then-add1 (compose add1 double))
> (double-then-add1 10)
21
> ((compose add1 add1) 100)
102
```
Consider the following short code snippet in the style of C++:
```
int tacos = 3;
while (tacos > 0) {
    tacos = tacos - 1;
}
```
Draw the Abstract Syntax Tree for this program. Follow the style and conventions used in the notes from class.

Write a Python program which could produce the following AST:

                Block
               /     \
 Assign("meat")       ExprStmt
       |                 |
StrLit("lengua")     __FunCall___
                    /    |       \
         Id("order")  IntLit(3)  Id("meat")