Writing an extensible interpreter

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

Writing an extensible interpreter

David House
Hi all.

I'm in the process of writing an interpreter for the self-modifying
automaton languages SMATINY [1], designed by ihope (whose name some of
you may recognise from IRC). The current effort is online [2], but
it's at a rather early stage and there's a few modifications I'd like
to make to it.

To begin with, extensibility is key. Such tiny languages are designed
to be easily extendable, and I'd like my interpreter to follow suit.
At the moment, adding a new command is as follows:

1) Add a new constructor for the Step type to represent your command.
2) Write a Parsec parser for your command in Smatiny.hs.
3) Add said parser to the 'inputs' list in Smatiny.hs.
4) Write a 'handler' for your command; a function in State that will
take the appropriate action.

This is a bit of an ordeal; I'd like new commands to be addable
without touching Smatiny.hs, which will form the base of the
interpreter.

One solution I was thinking about was to write a new module for each
command that exports a "parser" and "handler" function. A bit of
metacode would read the Commands directory then import qualified all
the modules it finds in there. Subsequently, it would call
parseSmatiny (the parser; in Smatiny.hs) with all the parsers it found
as an argument, then send the output of this into runSmatiny (the
interpreter; also in Smatiny.hs).

However, the remaining issue is step 1): how would the metacode handle
additional constructors to the Step ADT? Type classes won't work here:
the intepreter has a type of [Step] -> String. With type classes this
would have a type of something like Step a => [a] -> String, but by
the homogeneity of lists you'd only be able to have one type of step
in your program.

Thanks in advance for your input. Let me know if I didn't explain
something too well; I have a tendancy toward brevity :)

[1]: http://esoteric.voxelperfect.net/wiki/SMATINY
[2]: http://esoteric.voxelperfect.net/files/smatiny/impl/smatiny.tar.gz

--
-David House, [hidden email]
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

RE: Writing an extensible interpreter

Ralf Lammel-2
Hi David,

Readers on this list will not be surprised to hear me saying that, of
course, type classes perfectly make sense for your scenario. You may
have a look at some posts on "extensible interpreters":

- http://compilers.iecc.com/comparch/article/04-12-111
- http://www.haskell.org/pipermail/haskell/2005-February/015346.html

There are at least two ways of making the type "[Step] -> String" work
with a setup that replaces Step by a type class. One is: use an
existential type; another is: use HLists. (There is a third one: use
Typeable.)

I'll send you some draft material in a separate email that I don't want
to share publicly yet. In this draft, your scenario is actually
illustrated in a broader context.

And then I should mention that you may also want to have a look at
Hinze's and Loeh's open data types. I seem to remember that they provide
actual tool support (sort of preprocessing) so that this works with
Haskell today.

HTH
Ralf

> -----Original Message-----
> From: [hidden email] [mailto:haskell-cafe-
> [hidden email]] On Behalf Of David House
> Sent: Sunday, May 21, 2006 5:50 AM
> To: [hidden email]
> Subject: [Haskell-cafe] Writing an extensible interpreter
>
> Hi all.
>
> I'm in the process of writing an interpreter for the self-modifying
> automaton languages SMATINY [1], designed by ihope (whose name some of
> you may recognise from IRC). The current effort is online [2], but
> it's at a rather early stage and there's a few modifications I'd like
> to make to it.
>
> To begin with, extensibility is key. Such tiny languages are designed
> to be easily extendable, and I'd like my interpreter to follow suit.
> At the moment, adding a new command is as follows:
>
> 1) Add a new constructor for the Step type to represent your command.
> 2) Write a Parsec parser for your command in Smatiny.hs.
> 3) Add said parser to the 'inputs' list in Smatiny.hs.
> 4) Write a 'handler' for your command; a function in State that will
> take the appropriate action.
>
> This is a bit of an ordeal; I'd like new commands to be addable
> without touching Smatiny.hs, which will form the base of the
> interpreter.
>
> One solution I was thinking about was to write a new module for each
> command that exports a "parser" and "handler" function. A bit of
> metacode would read the Commands directory then import qualified all
> the modules it finds in there. Subsequently, it would call
> parseSmatiny (the parser; in Smatiny.hs) with all the parsers it found
> as an argument, then send the output of this into runSmatiny (the
> interpreter; also in Smatiny.hs).
>
> However, the remaining issue is step 1): how would the metacode handle
> additional constructors to the Step ADT? Type classes won't work here:
> the intepreter has a type of [Step] -> String. With type classes this
> would have a type of something like Step a => [a] -> String, but by
> the homogeneity of lists you'd only be able to have one type of step
> in your program.
>
> Thanks in advance for your input. Let me know if I didn't explain
> something too well; I have a tendancy toward brevity :)
>
> [1]: http://esoteric.voxelperfect.net/wiki/SMATINY
> [2]:
http://esoteric.voxelperfect.net/files/smatiny/impl/smatiny.tar.gz
>
> --
> -David House, [hidden email]
> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Writing an extensible interpreter

Jonathan Tang-2
In reply to this post by David House

Message: 2
From: "David House" <[hidden email]>
Subject: [Haskell-cafe] Writing an extensible interpreter
 
 
I'm in the process of writing an interpreter for the self-modifying
automaton languages SMATINY [1], designed by ihope (whose name some of
you may recognise from IRC). The current effort is online [2], but
it's at a rather early stage and there's a few modifications I'd like
to make to it.

[snip]

However, the remaining issue is step 1): how would the metacode handle
additional constructors to the Step ADT? Type classes won't work here:
the intepreter has a type of [Step] -> String. With type classes this
would have a type of something like Step a => [a] -> String, but by
the homogeneity of lists you'd only be able to have one type of step
in your program.

You can get around the homogeneity of lists problem with existential types:

http://www.haskell.org/hawiki/ExistentialTypes
http://halogen.note.amherst.edu/~jdtang/scheme_in_48/tutorial/evaluator2.html#equal

Another solution might be to eliminate the algebraic data type entirely and have the Parsec actions return a Smatiny action.  Instead of dispatching on the constructor of Step, package up any information you need as a closure and make Step a type synonym for 'Smatiny ()' or 'Smatiny a' or whatever type you need.  Then the interpreter main loop just executes the action returned by the parser. 

- Jonathan

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe