南京大学：《计算机程序的构造和解释 Structure and Interpretation of Computer Programs》课程教学资源（PPT课件讲稿）20-Interpreters

Interpreters

Interpreters

Tail Recursion

Tail Recursion

Tail Recursion An expression in a tail context is evaluated as the last step the function call o That means nothing is evaluated/applied after it is evaluated 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 0 If a language supports tail call optimization,a tail recursive function will only ever open a constant number of frames

Tail Recursion ● An expression in a tail context is evaluated as the last step the function call ○ That means nothing is evaluated/applied after it is evaluated ● 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 ○ If a language supports tail call optimization, a tail recursive function will only ever open a constant number of frames

Writing Tail Recursive Functions (Method I) 1)Identify recursive calls that are not in a tail context.Tail contexts are: o The last body subexpression in a lambda (a function) o The consequent and alternative in a tail context if o All non-predicate sub-expressions in a tail context cond o The last sub-expression in a tail context and,or,begin,or let 2)Create a helper function with arguments to accumulate the computation that prevents it from being tail recursive

Writing Tail Recursive Functions (Method I) 1) Identify recursive calls that are not in a tail context. Tail contexts are: ○ The last body subexpression in a lambda (a function) ○ The consequent and alternative in a tail context if ○ All non-predicate sub-expressions in a tail context cond ○ The last sub-expression in a tail context and, or, begin, or let 2) Create a helper function with arguments to accumulate the computation that prevents it from being tail recursive

Demo 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. (define (length 1st) (define (length-tail lst) (if(nu11？1st) 0 (1 (1ength (cdr 1st))))) scm> (1 ength‘() 0 scm>(1 ength‘(12(34) 3

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. (define (length lst) (if (null? lst) 0 (+ 1 (length (cdr lst))))) scm> (length ‘()) 0 scm> (length ‘(1 2 (3 4)) 3 (define (length-tail lst) ) Demo

Interpretation

Interpretation

Translation Problem: Computers can only understand one language,binary (0s and 1s) Humans can't really write a program using only 0s and 1s (not quickly anyways) Solution: Programming languages Languages like Python,Java,C,etc are translated to 0s and 1s This translation step comes in a couple forms: Compiled (pre-translated)_-translate all at once and run later iInterpreted (translated_on-the-fly)-translate while the program is running We'11 focus on interpreted languages

Translation Problem: Computers can only understand one language, binary (0s and 1s) Humans can’t really write a program using only 0s and 1s (not quickly anyways) Solution: Programming languages Languages like Python, Java, C, etc 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) - translate while the program is running We’ll focus on interpreted languages

Interpreters An interpreter does 3 things: Reads input from user in a specific programming language Translates input to be computer 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

Interpreters An interpreter does 3 things: Reads input from user in a specific programming language Translates input to be computer 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

Read-Eval-Print Loop (REPL) input expression value output Read Eval Print 。 string string loop while True: exp read() val eval(exp) print(val)

Interpreter input string Read-Eval-Print Loop (REPL) Read Eval Print expression value loop output string while True: exp = read() val = eval(exp) print(val)

Read

Read