Design questions for a Pascal interpreter

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

Design questions for a Pascal interpreter

giulianoxt
Hello,

I've been doing some research for a upcoming homework project, a
Pascal interpreter written in Haskell. As a beginner to the language,
I have a few design questions I'd like to share with you.

I started playing with Parsec, getting a feel for parsing with monadic
combinators. My assumption here is that i'm going to take the source,
transform it in an AST (built with normal data constructors present in
Haskell), maybe build a symbol table while doing that (using the
implicity state in Parsec), do some checking (mainly type checking I
think), and the evaluation itself.

Here are a few questions I had so far:

- Keeping the whole AST in memory for the evalution phase seems
overkill. Is there a better way?

- The evalution, I think, would be a set of nice pure mutually
recursive functions that do some pattern matching on the program AST.
I would pass the current stack and heap for those functions to use and
modify. Is the State monad a good fit for this task? Wouldn't the code
become "too imperative"?

- And finally, the big question. Consider the following pascal source:

program HelloWorld;
begin
  writeln('Hello World');
end.

To evaluate the AST, I would eventually arrive at something like:

eval (FunctionCall func_name func_args) = ...

Obviously, to evaluate writeln I need to be in the IO monad. Here, my
whole scheme went down. Do I really have to mix my own state (stack,
heap) within the IO monad along my evaluation functions?

PS: I could keep a list of things to print, that I would eventually do
after I traversed the whole tree, but that wouldn't be "realistic".


Thank you!

--
[]'s

Giuliano Vilela.
Reply | Threaded
Open this post in threaded view
|

Design questions for a Pascal interpreter

ajb@spamcop.net
G'day all.

Quoting Giuliano Vilela <[hidden email]>:

> - Keeping the whole AST in memory for the evalution phase seems
> overkill. Is there a better way?

In this day and age, it's not considered overkill to keep an entire
program in memory in a tree form.  Perl 5 does that, for example.

However, Pascal is simple enough that it can be translated from
within the parser.  Quite a few influential Pascal compilers,
including the simplest ones such as Pascal-P and Pascal-S, and some
not-so-simple ones such as Turbo Pascal, did not even generate an AST,
but compiled straight to P-code or assembly code from within the parser.

> - The evalution, I think, would be a set of nice pure mutually
> recursive functions that do some pattern matching on the program AST.
> I would pass the current stack and heap for those functions to use and
> modify. Is the State monad a good fit for this task? Wouldn't the code
> become "too imperative"?

Interpretation of an imperative language is imperative.  I wouldn't
worry about it.

You will probably end up using a few monad transformers, because you
need to need at least I/O and a heap, and quite possibly a symbol
table as well.

> Obviously, to evaluate writeln I need to be in the IO monad. Here, my
> whole scheme went down. Do I really have to mix my own state (stack,
> heap) within the IO monad along my evaluation functions?

You really need to learn about monad transformers.  Try this for
starters:

     http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.17.268

Good luck, and let us know how you go.

Cheers,
Andrew Bromage
Reply | Threaded
Open this post in threaded view
|

Design questions for a Pascal interpreter

Peter Verswyvelen-2
Maybe you could get come inspiration from the BASIC interpreter written in
Haskell:
http://hackage.haskell.org/cgi-bin/hackage-scripts/package/vintage-basic



On Tue, Apr 21, 2009 at 2:14 AM, <[hidden email]> wrote:

> G'day all.
>
> Quoting Giuliano Vilela <[hidden email]>:
>
>  - Keeping the whole AST in memory for the evalution phase seems
>> overkill. Is there a better way?
>>
>
> In this day and age, it's not considered overkill to keep an entire
> program in memory in a tree form.  Perl 5 does that, for example.
>
> However, Pascal is simple enough that it can be translated from
> within the parser.  Quite a few influential Pascal compilers,
> including the simplest ones such as Pascal-P and Pascal-S, and some
> not-so-simple ones such as Turbo Pascal, did not even generate an AST,
> but compiled straight to P-code or assembly code from within the parser.
>
>  - The evalution, I think, would be a set of nice pure mutually
>> recursive functions that do some pattern matching on the program AST.
>> I would pass the current stack and heap for those functions to use and
>> modify. Is the State monad a good fit for this task? Wouldn't the code
>> become "too imperative"?
>>
>
> Interpretation of an imperative language is imperative.  I wouldn't
> worry about it.
>
> You will probably end up using a few monad transformers, because you
> need to need at least I/O and a heap, and quite possibly a symbol
> table as well.
>
>  Obviously, to evaluate writeln I need to be in the IO monad. Here, my
>> whole scheme went down. Do I really have to mix my own state (stack,
>> heap) within the IO monad along my evaluation functions?
>>
>
> You really need to learn about monad transformers.  Try this for
> starters:
>
>    http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.17.268
>
> Good luck, and let us know how you go.
>
> Cheers,
> Andrew Bromage
>
> _______________________________________________
> Beginners mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/beginners/attachments/20090421/4bb970c9/attachment.htm