Completing the Spike

July 23, 2007

This entry continues work on the Spike Solution for HST – a simple Smalltalk interpreter developed in Haskell. In my previous two posts, I developed a parser that was able to parse a Smalltalk version of ‘Hello World’. In this entry I begin developing the execution phase.

I’m going to continue with my approach of keeping it simple and naive for now. I’m aiming for an interpreter than can parse and execute ‘Hello World’ before I begin adding features and improving robustness.

The Plan

First, a quick review. The program to be parsed was:

Transcript show: 'Hello World'

The resulting data structure generated is:

BasicExpression
  (PrimaryIdentifier (Identifier "Transcript")) 
  (KeywordMessage 
    (Keyword "show") 
    (PrimaryLiteral (StringLiteral "Hello World")))

So, how should execution proceed?

One simple approach is as follows:

  1. An object identified by “Transcript” is retrieved
  2. That object is sent a keyword message with a keyword of
    show” and a String object as the argument
  3. The “Transcript” object reacts by printing the
    String argument to the console

I’m sure that this will not be how the ‘Hello World’ program will be executed in a final implementation, but for this simple spike solution I think it is sufficient.

Getting to Objects

What seems easiest for me to work on now is the conversion of primaries to objects. That is, the implcit conversion of a StringLiteral to a String object and the retrieval of the object identified by “Transcript“. These are both of type Primary. This suggests a method of the following type:

evaluatePrimary :: Primary -> Object

But what is the best way to define the type Object?

In keeping with my approach so far, I’ll be naive about this. To start with I’m only going to need two Objects, so the following might be sufficient:

data Object = StringObject String | TranscriptObject

I’m not sure this is the best way to continue, but I think that as long as I am disciplined in spotting and refactoring duplicated code I will end up with a general Object data type. This will probably not happen during the development of this spike solution however.

With that definition of Object implementing evaulatePrimary becomes straight forward.

evaluatePrimary (PrimaryLiteral (StringLiteral s))
  = StringObject s
evaluatePrimary (PrimaryIdentifier (Identifier "Transcript"))
  = TranscriptObject

I could have been more intelligent with the second definition by creating a Map which would represent an execution context. It would map Identifiers to Objects and be initialized with the TranscriptObject mapped to “Transcript” already. I’m pretty sure this will be one of the first steps I take after the spike solution is completed, but I want to see how far this ‘being dumb’
approach gets me.

Expressions

Next, I’m going to move on to expression evaluation. In Smalltalk there are three kinds of expressions: Assigments, message
sends, and method returns. At the moment only message sends conern me – that will be all that is needed for ‘Hello World’. Message sends are represented by the BasicExpression type. So, I can start by writing evaluateExpression as follows:

evaulateExpression (BasicExpression prim msg)
  = sendMessage (evaluatePrimary prim) msg

This isn’t going to be sufficient, even just for now. Missing from this is the evaulation of the message’s arguments. Instead of sending the message to the object what is really required is that a selector with arguments be sent to the receiving Object. This suggests a method of type Message -> (String, [Object]).

prepareMessage (KeywordMessage (Keyword k) prim)
  = (k, [evaluatePrimary])

Now evaulateExpression can be written:

evaulateExpression (BasicExpression prim msg)
  = sendMessage (evaluatePrimary prim) sel args
    where sel, args = prepareMessage msg

The final step in the spike is to handle the “show” message on the TranscriptObject.

sendMessage TranscriptObject "show" (StringObject s) = putStrLn s

Testing in ghci:

> case (parse basicExpression "" "Transcript show: 'Hello World'") of
    Right e -> evaluateExpression e
Hello World

Hooray.

Conclusion

This completes my spike solution for HST. As it currently stands the interpreter is able to parse and execute a Smalltalk version of the famous ‘Hello World’ program. By no means is it complete or robust, but it has provided me with a basis on which I can build and refine further functionality. My plan now is to begin adding testing before increasing the functionality to execute a more complex program.

About these ads

2 Responses to “Completing the Spike”

  1. araujo Says:

    Cool, a Smalltalk implementation written on Haskell is indeed an interesting project, i have been thinking about it for a while now, but never got anything done, at least nothing big but a few lines of code here and there as a way of drafting ideas.

    Do you have the source code of what you have so far posted somewhere?

    Thanks and Good stuff!

  2. lstephen Says:

    Thanks.

    I don’t have the source code posted anywhere yet. I did plan to put it on something like Google code or Sourceforge, but a little further along (I’d like to at least get some testing done first, and probably a more complex Smalltalk program running). But, at the moment, I think all the code I’ve done is actually in the three blog posts, so I’m not much past the few lines of code yet either ;).


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: