Interpreters

So whats an interpreter?

A program that accepts statements, executes them immediately and then outputs the result.

At it's core these are the only 3 things an interpreter does

1. Accepts input
2. Executes statement inputted
3. Outputs result

An interpreter needs to loop through these three steps over and over to allow for more and more input (the Python interpreter doesn't stop after typing one thing). We call this the Read-Eval-Print-Loop (REPL)

Note: an interpreter is likely to be implemented in a different language than which it interprets (example: scheme interpreter written in python)

REPL

Each part of this loop can be further divided up:

• Read: This is the part where the interpreter accepts an input

  • Lexer: Turns strings into list of 'tokens', small important pieces
  • Parser: Takes the 'tokens' and puts it into a format to make the job of the interpreter easier

• Eval: This is the part where the interpreter does stuff with what was inputted

  • Eval: takes expressions and evaluates them according to specification of the language (may call apply to figure out what it may eval to)
  • Apply: applies a function to the operands (may call eval to figure things out)

• Print: This is where the interpreter displays the results to the user

Pictorally:

Read

This is an example of the lexer/parser from the scheme project (pulled from lec 21):

Eval/Apply

Follow the same steps as usual for call expression!

1. Evaluate operator
2. Evaluate operand(s)
3. Apply operator to operand(s)

Apply

When we apply a function we follow the process we followed before when constructing environment diagrams:

1. Create a new frame
2. Assign parameters to values
3. Evaluate the body of the function

Counting Calls

This is the process of determining the number of calls to eval and apply are needed to fully evaluate a statement.

You'll want to use the process for evaluating call expressions to determine the number of eval/apply calls.

For example:

 
xxxxxxxxxx
(+ 1 2)

To determine the number of calls let's walk through the statement element by element:

1. (+ 1 2) this is what we were inputted and we have to call eval on it to do anything with it (+1 eval)

2. now we follow the 3 previously mentioned steps

   1. + here we evaluate the operator (+1 eval)
   2. 1 we evaluate an operand (+1 eval)
   3. 2 we evaluate an operand (+1 eval)
   4. apply + to 1 and 2, this is the final step for call expressions (+1 apply)

In this case we had: 4 evals and 1 apply

Problems

What does lexer turn these into?

1.  
   (1 2 4)
   

2.  
   (define (f x) 5)
   

What does the parser turn these into?

1.  
   xxxxxxxxxx
   ['(', '+', 1, 2, ')']
   

2.  
   xxxxxxxxxx
   ['(', 1, '(', 2, ')', 3, ')']
   

How many calls to scheme_eval/scheme_apply?

1.  
   xxxxxxxxxx
   (define (f x) (* ((lambda () x)) 2))
   

2.  
   xxxxxxxxxx
   ((lambda (x y) (+ (y 2) x)) 3 f)
   

3.  
   xxxxxxxxxx
   (let ((f 4)
         (g f))
        (g (+ f (eval (define h ((lambda (a b) (* a b)) f 5)))))
   )
   

4.  
   xxxxxxxxxx
   (+ (* (if (and #t) 1 2) 4) (begin (+ 1 2) (+ 3 4)))
   

Generalized counting Eval/Apply

Given these general forms, write the number of Eval/Apply calls in terms of the expressions $a,b,c,d,e$ (for these problems assume these can be anything so we'll generalize by using $\texttt{eval_count}$ and $\texttt{apply_count}$):

Example:

 
xxxxxxxxxx
(/ a b)

Solution:

• Evals (total of $2+\texttt{eval_count}(a)+\texttt{eval_count}(b)$)

  • $2$, for total evaling entire statement (/ a b) and evaling /
  • $\texttt{eval_count}(a)+\texttt{eval_count}(b)$ represents the number of evals for a and b combined

• Apply (total of $1 +\texttt{apply_count}(a) + \texttt{apply_count}(b)$)

  • 1, for applying / to a and b
  • $\texttt{apply_count}(a) + \texttt{apply_count}(b)$ representing the number of applies to evaluate a and b

1.  
   xxxxxxxxxx
   (define a (+ b c))
   

2.  
   xxxxxxxxxx
   (if a b c)
   

3.  
   xxxxxxxxxx
   (define (fn a b) c)
   

4.  
   xxxxxxxxxx
   (let ((a b) (c d)) e)
   

5.  
   xxxxxxxxxx
   ((lambda (a) b) c)
   

6.  
   xxxxxxxxxx
   (and a b c)
   

7.  
   AخA
   (begin a b c)