Is an interpreter without an intermediate representation even possible?

In summary: You can read more about this on the Wikipedia page for "Lisp interpreter":"An interpreter in the Lisp programming language executes S-expressions directly, without the need for any intermediate representation. In Lisp, S-expressions are themselves executable, and there is no need to generate or execute an intermediate form. The interpreter simply reads an S-expression from the user and executes it."In summary, an interpreter in Lisp executes S-expressions directly, without the need for any intermediate representation.
  • #1
TheShermanTanker
13
4
I was reading the page about interpreters on wikipedia and one particular section caught my eye:

"An interpreter generally uses one of the following strategies for program execution:

  1. Parse the source code and perform its behavior directly;
  2. Translate source code into some efficient intermediate representation and immediately execute this;
  3. Explicitly execute stored precompiled code[1] made by a compiler which is part of the interpreter system (Which is often combined with a Just-in-Time Compiler).
Early versions of Lisp programming language and minicomputer and microcomputer BASIC dialects would be examples of the first type."

I know that an example of the third one would be Java or C#, and I understand what the second sentence means too. But the first one in particular intrigued me, is it even possible to have an interpreter that executes parsed code directly without an intermediate representation? I've searched around for quite a while but got no answers, and although the article mentions the early Lisp and BASIC interpreters as examples of interpreters without IRs, I haven't been able to find anything after googling Lisp and BASIC either

(I had to squish even and possible in the title together because I ran out of space oops)
 
Technology news on Phys.org
  • #2
Whenever you type a query into Google's search engine, you are providing source code that the search engine executes, probably directly.

I'm suggesting that you interpret words like interpret (unintentional pun) and compile loosely, not narrowly.
 
  • #3
Don't you trust the reference you quote? Are you looking for more references that say the same thing or looking for more details?
 
  • #4
TheShermanTanker said:
is it even possible to have an interpreter that executes parsed code directly without an intermediate representation

The traditional flow is that you put your textual input through a lexer to get a stream of tokens which you then put through a parser, and these steps are the same no matter if you then let your parser generate some intermediate code (e.g. a parse tree) or if you evaluate/execute the result on the spot. For an example, see this small yacc program to evaluate an arithmetic expression.

I would guess one can say that most line-by-line interpreted languages (perl, phyton, matlab, basic, etc) traditionally are parsed and evaluated using just such a simple "tool chain".

However, that said I would also guess that modern implementations for reasons of flexibility for the user (e.g. to offer the option to precompile modules and similar) and flexibility for the interpreter implementation itself (e.g. separating the concern of parsing from that of executing/evaluation) will end up generate some efficient intermediate representation first and then evaluate that.
 
  • #5
Some systems parse your source into byte code that is then executed on the os. Some examples are python or java.
 
  • #6
Filip Larsen said:
The traditional flow is that you put your textual input through a lexer to get a stream of tokens which you then put through a parser, and these steps are the same no matter if you then let your parser generate some intermediate code (e.g. a parse tree) or if you evaluate/execute the result on the spot. For an example, see this small yacc program to evaluate an arithmetic expression.

I would guess one can say that most line-by-line interpreted languages (perl, phyton, matlab, basic, etc) traditionally are parsed and evaluated using just such a simple "tool chain".

However, that said I would also guess that modern implementations for reasons of flexibility for the user (e.g. to offer the option to precompile modules and similar) and flexibility for the interpreter implementation itself (e.g. separating the concern of parsing from that of executing/evaluation) will end up generate some efficient intermediate representation first and then evaluate that.
I've never seen a Parser execute code directly like that though, how would one go about doing that?
 
  • #7
TheShermanTanker said:
is it even possible to have an interpreter that executes parsed code directly without an intermediate representation?

Sure. For example, in Lisp, when you enter an S-expression at the interpreter prompt, it is a direct representation of the code you want to execute; there is no need for any "translation" into something executable, because in Lisp, S-expressions are already executable as they stand.

In the words of Paul Graham, a well-known Lisp hacker, Lisp programs are written directly in the parse trees that other languages have to produce by parsing their source code. In other words, Lisp programs use directly as source code the same thing that other languages can only produce as an "intermediate representation". That's why a Lisp interpreter can execute Lisp source code directly: Lisp source code is already in the "intermediate representation" that other languages have to take an extra step to produce from their source code.
 

Related to Is an interpreter without an intermediate representation even possible?

1. Is an interpreter without an intermediate representation even possible?

Yes, it is possible to create an interpreter without an intermediate representation. This type of interpreter is known as a direct interpreter, and it works by directly executing the source code without first converting it into another form.

2. What is the purpose of an intermediate representation in an interpreter?

The purpose of an intermediate representation is to make the execution of the source code more efficient. It acts as a bridge between the source code and the machine code, making it easier for the interpreter to translate and execute the code.

3. Are there any advantages to using an interpreter without an intermediate representation?

Yes, there are some advantages to using a direct interpreter without an intermediate representation. It can be faster and more lightweight, as there is no need to convert the source code into another form before execution. It can also be easier to implement, as there is no need to write code for the intermediate representation.

4. Are there any drawbacks to using an interpreter without an intermediate representation?

One drawback is that it may not be as efficient as an interpreter with an intermediate representation. Without the intermediate representation, the interpreter may need to do more work during execution, which can slow down the process. It may also be more difficult to debug issues with the source code, as there is no intermediate representation to help identify errors.

5. What type of languages are best suited for an interpreter without an intermediate representation?

Languages that are simple and easy to interpret, such as scripting languages, are best suited for an interpreter without an intermediate representation. These languages often do not require the efficiency benefits of an intermediate representation and can benefit from the speed and simplicity of a direct interpreter.

Similar threads

  • Programming and Computer Science
Replies
29
Views
2K
  • Programming and Computer Science
Replies
7
Views
932
Replies
6
Views
1K
  • Programming and Computer Science
2
Replies
59
Views
5K
  • Programming and Computer Science
2
Replies
65
Views
3K
  • Programming and Computer Science
Replies
2
Views
1K
  • Programming and Computer Science
Replies
4
Views
2K
  • Programming and Computer Science
Replies
6
Views
1K
  • Programming and Computer Science
Replies
3
Views
2K
Back
Top