Lisp Interpreter

What is Lisp?

Lisp (historically, LISP) is a family of computer programming languages with a long history and a distinctive, fully parenthesized Polish prefix notation.

Lisp was originally created as a practical mathematical notation for computer programs, influenced by the notation of Alonzo Church's lambda calculus.

Lisp was invented by John McCarthy in 1958 while he was at the Massachusetts Institute of Technology (MIT).

Lisp was first implemented by Steve Russell on an IBM 704 computer. Russell had read McCarthy's paper, and realized that the Lisp eval function could be implemented in machine code.The result was a working Lisp interpreter which could be used to run Lisp programs, or more properly, 'evaluate Lisp expressions.'

More on lisp

Lisp interpreter in Javascript

A language interpreter has two parts: Parsing and Execution.

In PARSING it 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 EXECUTION the internal representation is then processed according to the semantic rules of the language, thereby carrying out the computation.

The parser

Parsing has two phases: read and parse.

At first the input read as a string.In the tokenizing part it is then converted in to list.Say if the input is "(set! twox (* x 2))" then after tokenizing it will look as 

['(', 'set!', 'twox', '(', '*', 'x', '2', ')', ')']

So here is the function tokenize.....

1:  function tokenize(s){  
2:    return s.replace(/\(/g,' ( ')  
3:    .replace(/\)/g,' ) ')  
4:    .trim()  
5:    .split(/\s+/);  
6:  }  

Here read works by calling read_from on the tokens obtained by tokenize.It will try to read an expression from a sequence of tokens.

1:  function read_from(tokens)  
2:  {  
3:   if (tokens.length==0){console.log("SyntaxError:unexpected EOF while reading");}  
4:   var token=tokens.shift();  
5:   if ('('===token)  
6:   {  
7:   var L=[];   
8:   while(')'!==tokens[0])  
9:   {  
10:     L.push(read_from(tokens));  
11:   }  
12:   tokens.shift();  
13:   return L;  
14:   }  
15:   else{  
16:   if (')'===token){  
17:    console.log("SyntaxError:unexpected )");  
18:   }  
19:   else {  
20:   return atom(token);}  
21:   }  
22:   }  

Execution

In execution phase nine forms (variable reference, constant literal, quotation, conditional, assignment, definition, procedure, sequencing, procedure call) are evaluated.

1:  function eval(x,env)  
2:  {  
3:   env=env || global_env;  
4:   if (typeof x==='string')  
5:   {  
6:   return env.find(x.valueOf())[x.valueOf()];  
7:   }  
8:   else if (typeof x==='number')  
9:   {  
10:   return x;  
11:   }  
12:   else if (x[0]==='quote')  
13:   {  
14:   return x[1];  
15:   }  
16:   else if (x[0]=='if')  
17:   {  
18:   var test=x[1],conseq=x[2],alt=x[3];  
19:   if (eval(test,env))  
20:   {  
21:   return eval(conseq,env);  
22:   }  
23:   else{  
24:   return eval(alt,env);}  
25:   }  
26:   else if(x[0]==='set!')  
27:   {  
28:   env.find(x[1])[x[1]]=eval(x[2],env);  
29:   }  
30:   else if (x[0]==='define')  
31:   {  
32:   env[x[1]]=eval(x[2],env);  
33:   }  
34:   else if (x[0]==='lambda')  
35:   {  
36:   var vars=x[1],exp=x[2];  
37:   return function()  
38:   {  
39:    return eval(exp,Env({parms:vars,args:arguments,outer:env}));  
40:   };   
41:   }  
42:   else if (x[0]==='begin')  
43:   {  
44:   var val;  
45:   for (var i=1;i<x.length;i+=1)  
46:    val=eval(x[i],env);  
47:   return val;  
48:  }  
49:  else  
50:  {  
51:  var exps=[];  
52:  for (i=0;i<x.length;i+=1)  
53:   exps[i]=eval(x[i],env);  
54:  var proc=exps.shift();  
55:  return proc.apply(env,exps);  
56:  }  
57:  }  

Environments

Environments are mappings of variable names (symbols) to the values (data objects) held by them.

1:  function Env(dict)  
2:  {  
3:  var env={},outer=dict.outer || {};  
4:  if (dict.parms.length!=0)  
5:  {  
6:  for (var i=0;i<dict.parms.length;i+=1)  
7:  {  
8:   env[dict.parms[i]]=dict.args[i];  
9:  }  
10:  }  
11:  env.find=function(variable)  
12:  {  
13:  if (env.hasOwnProperty(variable))  
14:  {  
15:  return env;  
16:  }  
17:  else  
18:  {  
19:  return outer.find(variable);  
20:  }  
21:  }  
22:  return env;  
23:  }  

Go to the Github respository to see all the code. And here is  lis.py , the simple Scheme interpreter that Peter Norvig wrote in Python.