Is an interpreter without an intermediate representation even possible?

[TheShermanTanker]

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)

 

[anorlunda]

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.

 

[FactChecker]

Don't you trust the reference you quote? Are you looking for more references that say the same thing or looking for more details?

 

[Filip Larsen]

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.

 

[jedishrfu]

Some systems parse your source into byte code that is then executed on the os. Some examples are python or java.

 

[TheShermanTanker]

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?

 

[PeterDonis]

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.