The normal quote ' and the quasiquote ` are both valid ways to quote an expression. However, the quasiquoted expression can be unquoted with the "unquote" , (represented by a comma). When a term in a quasiquoted expression is unquoted, the unquoted term is evaluated, instead of being taken as literal text. This mechanism is somewhat akin to using f-strings in Python, where expressions inside {} are evaluated and inserted into the string.

scm> (define a 5)
a
scm> (define b 3)
b
scm> `(* a b)  ; Quasiquoted expression
(* a b)
scm> `(* a ,b)  ; Unquoted b, which evaluates to 3
(* a 3)
scm> `(* ,(+ a b) b)  ; Unquoted (+ a b), which evaluates to 8
(* 8 b)

An interpreter is a program that allows you to interact with the computer using a specific language. It takes the code you write, interprets it, and then executes the corresponding actions, often using a more fundamental language to communicate with the computer hardware.

In Project 4, you'll develop an interpreter for the Scheme programming language using Python. Interestingly, the Python interpreter you've been using throughout this course is primarily written in the C programming language. At the lowest level, computers operate by interpreting machine code, which is a series of ones and zeros that instructs the computer on performing basic tasks such as arithmetic operations and data retrieval.

When we talk about an interpreter, there are two languages at work:

1. The language being interpreted: For Project 4, this is the Scheme language.
2. The implementation language: This is the language used to create the interpreter itself, which, for Project 4, will be Python.

REPL

A common feature of interpreters is the Read-Eval-Print Loop (REPL), which processes user inputs in a cyclic fashion through three stages:

• Read: The interpreter first reads the input string provided by the user. This input goes through a parsing process that involves two key steps:

  • The lexical analysis step breaks down the input string into tokens, which are the basic elements or "words" of the language you're interpreting. These tokens represent the smallest units of meaning within the input.

  • The syntactic analysis step takes the tokens from the previous step and organizes them into a data structure that the underlying language can understand. For our Scheme interpreter, we assemble the tokens into a Link object (similar to a Link), to represent the structure of the original call expression.

    • The first item in the Link represents the operator of the call expression, while the subsequent elements are the operands or arguments upon which the operation will act. Note that these operands can also be call expressions themselves (nested expressions).
      

Below is a summary of the read process for a Scheme expression input:

• Eval: This step evaluates the expressions you've written in that programming language to obtain a value. It involves the following two functions:

  • eval takes an expression and evaluates it based on the language's rules. When the expression is a call expression, eval uses the apply function to obtain the result. It will evaluate the operator and its operands in order. For example, in (add 1 2), eval would identify add as the operator and 1 and 2 as the operands. It evaluates add to ensure it's a valid function and then evaluates 1 and 2 to ensure they're valid arguments.
  • apply takes the evaluated operator (the function) and applies it to the evaluated operands (the arguments). Note that it's possible that, during this process, apply needs to evaluate more expressions (like those found within the function body). This is where apply may call back to eval, and thus these two stages are mutually recursive.
• Print: Display the result of evaluating the user input.

Evaluation

To evaluate the expression (+ (* 3 4) 5) using the interpreter, scheme_eval is called on the following expressions (in this order):

1. (+ (* 3 4) 5)
2. +
3. (* 3 4)
4. *
5. 3
6. 4
7. 5

The * is evaluated because it is the operator sub-expression of (* 3 4), which is an operand sub-expression of (+ (* 3 4) 5).

By default, * evaluates to a procedure that multiplies its arguments together. But * could be redefined at any time, and so the symbol * must be evaluated each time it is used in order to look up its current value.

scm> (* 2 3)  ; Now it multiplies
6
scm> (define * +)
*
scm> (* 2 3)  ; Now it adds
5

Calculator

An interpreter is a program that executes programs. Today, we will extend the interpreter for Calculator, a simple made-up language that is a subset of Scheme. This lab is like the Scheme Project in miniature.

The Calculator language includes only the four basic arithmetic operations: +, -, *, and /. These operations can be nested and can take various numbers of arguments, just like in Scheme. A few examples of calculator expressions and their corresponding values are shown below.

 calc> (+ 2 2 2)
 6

 calc> (- 5)
 -5

 calc> (* (+ 1 2) (+ 2 3 4))
 27

Calculator expressions are represented as Python objects:

• Numbers are represented using Python numbers.
• The symbols for arithmetic operations are represented using Python strings (e.g. '+').
• Call expressions are represented using the Link class below.

>>> p = Link('+', Link(2, Link(3, nil)))
>>> p.first
'+'
>>> p.rest
Link(2, Link(3, nil))
>>> p.rest.first
2
>>> print(p)
(+ 2 3)

>>> map_link(lambda x: 2 * x, p.rest)
Link(4, Link(6, nil))

class Link:
    """Represents the built-in Link data structure in Scheme."""
    empty = ()
    def __init__(self, first, rest):
        self.first = first
        self.rest = rest

nil = Link.empty

def map_link(f, s):
    """Map function f over linked list s.
    >>> square = lambda x: x * x
    >>> map_link(square, Link(1, Link(2, Link(3))))
    Link(1, Link(4, Link(9, nil)))
    """
    if s is Link.empty:
        return s
    return Link(f(s.first), map_link(f, s.rest))