Lisp Interpreter

    An interpreter is also a program that translates a high-level language into a low-level one, but it does it at the moment the program is run. You write the program using a text editor or something similar, and then instruct the interpreter to run the program. It takes the program, one line at a time, and translates each line before running it: It translates the first line and runs it, then translates the second line and runs it etc.

A language interpreter has two parts:

1. Parsing: The parsing component takes an input program in the form of a sequence of characters, verifies it according to the syntactic rules of the language, and translates the program into an internal representation. In a simple interpreter the internal representation is a tree structure that closely mirrors the nested structure of statements or expressions in the program.
2. Execution: The internal representation is then processed according to the semantic rules of the language, thereby carrying out the computation.
    

Here is a picture of the interpretation process and an interactive session showing how parsing and execution operate on a short program: 

 

Parsing:

Parsing is traditionally separated into two parts: lexical analysis, in which the input character string is broken up into a sequence of tokens, and syntactic analysis, in which the tokens are assembled into an internal representation.

Execution:

The translated programme is processed according to the semantic rules of the language. Considering an example, its output after evaluation step will be as follows.

>>> program = "(begin (define r 3) (* 3.141592653 (* r r)))"

After parsing the program we get,

['begin', ['define', 'r', 3], ['*', 3.141592653, ['*', 'r', 'r']]]

After Executing this, we will get,

28.274333

Here is the code of Lisp Interpreter in Javascript. Now lets go through the code.

Function Env():

This function defines the environment for a variable used in execution. The function find(variable) will find the correct environment of execution for the variable. If the variable is defined in the existing environment, the current environment is considered, else the function is called recursively to the outer environments untill the correct environment is found, property known as lexical scoping.

Function addGlobal():

This functions defines the global environment. Basic math functions such as '+', '*' etc are defined in the global environment. Other than these 21 basic functions, some other math functions such as sin,cos,log etc are also included in the global environment as shown below.

         var functions = ['abs', 'acos', 'asin', 'atan', 'atan2', 'ceil', 'cos', 'exp', 'floor', 'log',
                                               'max', 'min', 'pow', 'random', 'round', 'sin', 'sqrt', 'tan'];

             for (var i = 0; i < functions.length; i += 1) {

                 env[functions[i]] = Math[functions[i]];

             }

Function eval():

Evaluation function defines the steps of evaluation processes for all types of lines of codes. It represents the execution part of the interpreter. 9 cases are defined in the function. 

Functions for parsing:

Parsing is the first stage of the interpreter. It converts the input code into a set of tokens and reads according to the semantic meanings of the language. We use a number of functions for these actions which are listed below. 

• parser() : Returnes the output of readFrom function. 
• tokenize() : Converts the input code into a set of tokens. A set of built in functions are used here. s.replace() is used to replace the parenthesis with a space before and after it. s.trim() removes the spaces at the beginning and end of the expression. s.split() is applied to split the code after every space into a set of tokens. 
• readFrom() : The functions takes the output of tokenize() function as input and forms a list avoiding all parenthesis and resembles the internal ordering of the expression. 
• atom() : Converts integers in string format to numbers. 

Function repl():

repl() represents the read evaluation print loop. The function is used to form an interactive Lisp interpreter.