So far we've been able to define our own procedures in Scheme using the define special form. When we call these procedures, we have to follow the rules for evaluating call expressions, which involve evaluating all the operands.

We know that special form expressions do not follow the evaluation rules of call expressions. Instead, each special form has its own rules of evaluation, which may include not evaluating all the operands. Wouldn't it be cool if we could define our own special forms where we decide which operands are evaluated? Consider the following example where we attempt to write a function that evaluates a given expression twice:

scm> (define (twice f) (begin f f))
twice
scm> (twice (print 'woof))
woof

Since twice is a regular procedure, a call to twice will follow the same rules of evaluation as regular call expressions; first we evaluate the operator and then we evaluate the operands. That means that woof was printed when we evaluated the operand (print 'woof). Inside the body of twice, the name f is bound to the value undefined, so the expression (begin f f) does nothing at all!

The problem here is clear: we need to prevent the given expression from evaluating until we're inside the body of the procedure. This is where the define-macro special form, which has identical syntax to the regular define form, comes in:

scm> (define-macro (twice f) (list 'begin f f))
twice

define-macro allows us to define what's known as a macro, which is simply a way for us to combine unevaluated input expressions together into another expression. When we call macros, the operands are not evaluated, but rather are treated as Scheme data. This means that any operands that are call expressions or special form expression are treated like lists.

If we call (twice (print 'woof)), f will actually be bound to the list (print 'woof) instead of the value undefined. Inside the body of define-macro, we can insert these expressions into a larger Scheme expression. In our case, we would want a begin expression that looks like the following:

(begin (print 'woof) (print 'woof))

As Scheme data, this expression is really just a list containing three elements: begin and (print 'woof) twice, which is exactly what (list 'begin f f) returns. Now, when we call twice, this list is evaluated as an expression and (print 'woof) is evaluated twice.

scm> (twice (print 'woof))
woof
woof

To recap, macros are called similarly to regular procedures, but the rules for evaluating them are different. We evaluated lambda procedures in the following way:

• Evaluate operator
• Evaluate operands
• Apply operator to operands, evaluating the body of the procedure

However, the rules for evaluating calls to macro procedures are:

• Evaluate operator
• Apply operator to unevaluated operands
• Evaluate the expression returned by the macro in the frame it was called in.

Recall that the quote special form prevents the Scheme interpreter from executing a following expression. We saw that this helps us create complex lists more easily than repeatedly calling cons or trying to get the structure right with list. It seems like this form would come in handy if we are trying to construct complex Scheme expressions with many nested lists.

Consider that we rewrite the twice macro as follows:

(define-macro (twice f)
  '(begin f f))

This seems like it would have the same effect, but since the quote form prevents any evaluation, the resulting expression we create would actually be (begin f f), which is not what we want.

The quasiquote allows us to construct literal lists in a similar way as quote, but also lets us specify if any sub-expression within the list should be evaluated.

At first glance, the quasiquote (which can be invoked with the backtick ` or the quasiquote special form) behaves exactly the same as ' or quote. However, using quasiquotes gives you the ability to unquote (which can be invoked with the comma , or the unquote special form). This removes an expression from the quoted context, evaluates it, and places it back in.

By combining quasiquotes and unquoting, we can often save ourselves a lot of trouble when building macro expressions.

Here is how we could use quasiquoting to rewrite our previous example:

(define-macro (twice f)
  `(begin ,f ,f))

Important Note: quasiquoting isn't necessarily related to macros, in fact it can be used in any situation where you want to build lists non-recursively and you know the structure ahead of time. For example, instead of writing (list x y z) you can write `(,x ,y ,z) for 100% equivalent behavior

A stream is an example of a lazy sequence. Specifically, it is a lazily evaluated Scheme list. In other words, the stream's elements (except for the first element) are only evaluated when the values are needed. In addition, streams are memoized: the elements that have already been computed are saved!

Because a stream is simply a lazy list, the rest of a stream is also a stream (just like the rest of a list is also a list). In addition, nil can also serve as an empty stream. To check if a stream is empty, we can use the built-in procedure null?.

The procedures involved for working with streams are as follows:

• (cons-stream first rest): A special form that constructs a stream by evaluating the first operand first and storing its value as the first element in the stream, and storing the second operand rest, unevaluated, to be evaluated later.
• (car s): A procedure that works on streams the same way it does on lists. It returns the first element of the stream, which had already been computed on construction of the stream.
• (cdr-stream s): A procedure that returns the rest of the stream by evaluating the rest expression that was stored on construction of the stream. It then stores the value of this expression so that on subsequent calls to cdr-stream on this stream, rest no longer has to be evaluated.

Now we are ready to look at a simple example. This stream is an infinite stream where each element is 1.

scm> (define ones (cons-stream 1 ones))
ones
scm> (car ones)
1
scm> (cdr-stream ones)
(1 . #[promise (forced)])

The reason we are able to recursively reference this object without causing an error is because the second operand to cons-stream is not evaluated. Instead, it is stored until cdr-stream is called, at which point the expression will be evaluated and the resulting value will be stored.

Next, here's one way to build a stream of the natural numbers starting at n.

scm> (define (naturals (n))
       (cons-stream n (naturals (+ n 1))))
naturals
scm> (define nat (naturals 0))
nat
scm> (car nat)
0
scm> (car (cdr-stream nat))
1
scm> (car (cdr-stream (cdr-stream nat)))
2

Here, the expression that is stored is a recursive call to naturals. When we evaluate this call, we get another stream whose first element is one greater than the previous number in the sequence. The second element of this stream is uncomputed until cdr-stream is called on it, which will activate yet another call to naturals. Hence, we effectively get an infinite stream of integers, where each integer is computed one at a time. This is almost like infinite recursion, but one which can be viewed one step at a time, so it does not crash.

scm> +
#[+]
scm> list
#[list]

scm> +
______
#[+]
scm> list
______
#[list]
scm> (define-macro (f x) (car x))
______
f
scm> (f (2 3 4)) ; type SchemeError for error, or Nothing for nothing
______
2
scm> (f (+ 2 3))
______
#[+]
scm> (define x 2000)
______
x
scm> (f (x y z))
______
2000
scm> (f (list 2 3 4))
______
#[list]
scm> (f (quote (2 3 4)))
______
SchemeError
scm> (define quote 7000)
______
quote
scm> (f (quote (2 3 4)))
______
7000

scm> (define-macro (g x) (+ x 2))
______
g
scm> (g 2)
______
4
scm> (g (+ 2 3))
______
SchemeError
scm> (define-macro (h x) (list '+ x 2))
______
h
scm> (h (+ 2 3))
______
7

scm> (define-macro (if-else-5 condition consequent) `(if ,condition ,consequent 5))
______
if-else-5
scm> (if-else-5 #t 2)
______
2
scm> (if-else-5 #f 3)
______
5
scm> (if-else-5 #t (/ 1 0))
______
SchemeError
scm> (if-else-5 #f (/ 1 0))
______
5
scm> (if-else-5 (= 1 1) 2)
______
2

scm> '(1 x 3)
______
(1 x 3)
scm> (define x 2)
______
x
scm> `(1 x 3)
______
(1 x 3)
scm> `(1 ,x 3)
______
(1 2 3)
scm> '(1 ,x 3)
______
(1 (unquote x) 3)
scm> `(,1 x 3)
______
(1 x 3)
scm> `,(+ 1 x 3)
______
6
scm> `(1 (,x) 3)
______
(1 (2) 3)
scm> `(1 ,(+ x 2) 3)
______
(1 4 3)
scm> (define y 3)
______
y
scm> `(x ,(* y x) y)
______
(x 6 y)
scm> `(1 ,(cons x (list y 4)) 5)
______
(1 (2 3 4) 5)

(define-macro (def func args body)
    'YOUR-CODE-HERE)

python3 ok -q scheme-def

(define (map-stream f s)
	(if (null? s)
		nil
		(cons-stream (f (car s)) (map-stream f (cdr-stream s)))))

(define (map-stream f s)
    (if (null? s)
    	nil
    	(cons-stream (f (car s)) (map-stream f (cdr-stream s)))))

(define all-three-multiples
  'YOUR-CODE-HERE
)

python3 ok -q multiples_3

python3 ok --submit

scm> (define (square x) (* x x))
square
scm> (define (add-one x) (+ x 1))
add-one
scm> (define (double x) (* x 2))
double
scm> (define composed (compose-all (list double square add-one)))
composed
scm> (composed 1)
5
scm> (composed 2)
17

(define (compose-all funcs)
  'YOUR-CODE-HERE
)

python3 ok -q compose-all

a1, a2, a3, ...

a1, a1 + a2, a1 + a2 + a3, ...

(define (partial-sums stream)
  'YOUR-CODE-HERE
  (helper 0 stream)
)

python3 ok -q partial-sums