Interpreters

Review : Tail Recursion

- An expressio in a tail context is evaluated a sthe last step the function call

- Function calls in a tail context are called tail calls

- If all recursive calls are in tail contexts, we say that function is tail recursive

Review : Writing Tail Recursive Functions

1. Identify recursive calls that are not in a tail context

2. Create a helper function with arguments to accumulate the computation that prevents if from being tail recursive

Example : Length of Linked List

Goal : Write a function that takes in a list and returns the length of the list. Make sure it is tail recursive.

 

Translation

problem : computers can only understand one language, binary ( 0s and 1s )

solution : programming languages, Languages like Python, Java, C etx are translated to 0s and 1s

This translation step comes in a couple forms :

compiled ( pre-translated ) _ translate all at once and run later

Interpreted ( translated on-the-fly ) _ translated while the programs is running

Interpreters

An interpreter does 3 things :

- Reads input from user in a specific programming language

- Translates input to be coputer readable and evaluates the result

- Prints the result for the user

There are two languages involved :

- Implemented language _ this is the language the user types in

- Implementation language _ this is the language interpreter is implemented in 

Implemented language is translated into the Implementation language ( in our case, implement Scheme to Python )

Read - Eval - Print Loop ( REPL )

input string : Read -> expression : Eval -> value : Print : output string -> loop

Reading Input

Lexical Analysis ( Lexer ) : turning the input into a collection of tokens

- A token : single input of the input string, ex. literals, names, keywords, delimiters

Syntactic Analysis ( Parser ) : turning tokens into a representation of the expressio in the implementing language

Representing Scheme Primitive Expressions

Self-Evaluating expression : use Python booleans and Python numbers

Symbols : use Python strings

Representing Combinations

: Combinations are just Scheme lists containing an operator and operands

Python Pairs

: To accurately represent Scheme combinations as linked lists, let's write a Pair class in Python

: There is one instance of nil. No other instances can be created

Reading Combinations

Special case : quote

- Recall that the quote special form can be invoked in two ways : ( quote < expr > ) '< expr >

- The special ' syntax gets converted by the reader into a qupte expression, which is a list with 2 elements

Eval

Evaluating Expression 

: Rules for evaluating an expression depends on the expression's type.

: Types of Scheme expressions _ self-evaluating expressions, symbols, call expressions, special form expressions

: Eval Takes in one arguemnt besides the expression itself _ the current environment

Frames and Environments

- When evaluating expressions, the current environment consists of the current frame, its parent frame, and all its ancestor frames until the Global Frame.

Frames in our interpreter

- Frames are represented in our interpreter as instances of the Frame class

- Each Frame instance has two instance attributes :

 1. bindings : a dictionary that binds Sheme symbols ( Python strings ) to Scheme values 

 2. parent : the parent frame, another Frame instance

Evaluating primitive expressions

- self-evaluating expressions : These expressions evaluate to themselves

- symbols :

 1. Look in the current frame for the symbol. If it is found return the value bound to it.

 2. If it is not found in the current frame, look in the parent frame. If it is not found in the parent frame, look in its parent frame, and so on.

 3. If the global frame is reached and the name is not found, raise a SchemeError.

Evaluating Combinations

( < operator > < operand 1 > < operand 2 > )

: The operator of a combination tells us whether it is a special form expression or a call expression

- If the operator is a symbol and is found in the dictionary of special forms, the combination is a special form

( each special form has special rules for evaluation )

Types of Procedures

- A built-in procedure is a procedure that is predefined in our Scheme interpreter. 

 ( ex. +, list, modulo, etc )

- A user-defined procedure is a procedure defined by the user, either with a lambda expressio or a define expression.

Built-In procedures

Applying built-in procedures

: call the Python function that implements the built-in procedure on the arguments

User-Defined procedures

: applying user-defined procedures

step 1. open a new frame whose parent is the parent frame of the procedure being applied

step 2. bind the formal parameters of the procedure to the arguments in the new frame

step 3. evaluate the body of the procedure in the new frame

The evaluator

: the evaluator consist of two mutually-recursive components

Evaluator

-   Eval

Base cases : self-evaluating expressions, look up values bound to symbols

Recursive cases : Eval ( operator ), Eval ( o ) for each operand o, Apply ( proc, args ), Evale (expr ) for expression expr in body of special form

-   Apply

Base cases : Built-in procedures

Recursive cases : Eval ( body ) of user defined procedures

Counting eval / apply calls : built-in procedures

: how many calls to eval and apply are made in order to evaluate this expression ?

Counting eval / apply calls : user-defined procedures

: how many calls to eval and apply are made in order to evaluate the second expression ?