Skip to main content

Lisp Interpreter in Python

Here we are going to discuss about the lisp interpreter written in python by Peter Norvig. The complete code is given here.

Purpose of a language interpreter 

A language interpreter has two main divisions termed as parsing and execution.

Parsing: A parser programme converts the input programme into an internal representation after analyzing the syntactic correctness of the programme. In most of the interpreters the internal representation will be a tree like structure which resembles with the nesting structures of the input programme. Consider the example given below, he output after the parser programme will be as followes.

           >>> program = "(begin (define r 3) (* 3.141592653 (* r r)))"
           >>> parse(program)
           ['begin', ['define', 'r', 3], ['*', 3.141592653, ['*', 'r', 'r']]]
 
Execution: The translated programme is processed according to the semantic rules of the language. Considering the same example for parsing programme, its output after evaluation step will be as follows.

           >>> program = "(begin (define r 3) (* 3.141592653 (* r r)))"
           >>> parse(program)
           ['begin', ['define', 'r', 3], ['*', 3.141592653, ['*', 'r', 'r']]]
           >>> eval(parse(program))
           28.274333

Now let us discuss the two topics in detail

Execution

The function eval() explains the methods to be executed for nine different conditions. These nine conditions covers all different types of expressions. Next we have to define the environment. class env is used for this purpose. Note that env is subclass of dict. So env will have all properties of dictionary and the additional functions such as find() is also included. find() is used to find the appropriate environment for a variable by lexical scoping method. Another function in the execution part is add_globals. This functions defines the global environment. Basic math functions such as '+', '*' etc are defined in the global environment.

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. Consider the example given below.
 
           >>> program = "(set! x2 (* x x))"
           >>> tokenize(program)
           ['(', 'set!', 'x2',  '(', '*', 'x', 'x', ')', ')']
           >>> parse(program)
           ['set!', 'x2', ['*', 'x', 'x']]

The tokenize() function splits the expression into a set of tokens and the parse() function rearranges the tokens into an internal representation. As the final steps of our code, the function atom() converts integers in string format to numbers and every other token is a symbol. 

repl() function is used for making the interpreter user interactive.

Comments

Post a Comment

Popular posts from this blog

Backbone.js - An Introduction

Backbone.js is a lightweight JavaScript library that adds structure to your client-side code.  Developers commonly use libraries like Backbone.js to create single-page applications (SPAs).  What is a Single-Page-Application? A single page Web App is a website that attempts to recreate the experience of a native desktop or mobile application. On a Single Page Web App you are less likely to see page refreshes, the browser navigation within the app is often overridden and  there will usually be some offline capabilities. To a user their interaction with a Single Page Web App will be almost identical to how they interact with a full native application. Backbone has many advantages over other js frameworks. Backbone is mature, popular, and has a number  of plugins and extensions available that build upon it. It has been used to create non-trivial applications by companies such as Disqus, Walmart, SoundCloud and LinkedIn. Backbone organizes its whole code under t...
Post a Comment
Read more

Elements of Programming in Scheme

A powerful programming language provides a framework to interpret our ideas of processes. It generally combines small procedures to complex ones. Usually there are three steps to accomplish this. primitive expressions , which represent the simplest entities the language is concerned with, means of combination , by which compound elements are built from simpler ones, and means of abstraction , by which compound elements can be named and manipulated as units. Some very basic ideas in manipulating with the data are given below. Expressions   A very simple expression is a number. Simple expressions are combined to form complex ones. For example:                   (+ 2  3  4) is an expression where + is the operation and 2,3,4 are the oparents. The expression can be made more complex by combining simple expressions as given below:              ...
Post a Comment
Read more

Abstraction Using Higher Order Procedures

Procedures are, in effect, abstractions that describe compound operations on numbers independent of the particular numbers. Yet even in numerical processing we will be severely limited in our ability to create abstractions if we are restricted to procedures whose parameters must be numbers. Often the same programming pattern will be used with a number of different procedures. To express such patterns as concepts, we will need to construct procedures that can accept procedures as arguments or return procedures as values. Procedures as arguments Procedures are often used as the arguments of an another procedure. This provides a higher level of abstraction in programming. For example consider a procedure to find out the sum of squares of numbers between a range. The procedures inc and square are used as the arguments of the procedure sum, which is generalised as follows.                 (define (inc...
Post a Comment
Read more