by Leandro Caniglia
President of FAST (Fundación Argentina de Smalltalk)

Story 4: Hybrid Compilation

Have you ever heard of the idea the creators of Smalltalk had for allowing any class to choose its compiler? To provide support for this classes respond to the #compiler message before the actual compilation is attempted. Why then, this capability hasn’t been exploited yet? Are you willing to investigate it further? OK, bear with me.

In Story 3 of this series we discussed how to inline TaggedNodes in a Smalltalk method. We mentioned several applications of this capability and took JSON as a basic example. Today we can take a similar approach and try to see how to do our exploration with JSON in mind. From there it will become fairly clear how to proceed in other cases. So, let’s put ourselves this objective: compile the following method in our Smalltalk dialect:

jsonCoordinates
  <json>
  ^{
      "latitude": 48.858093,
      "longitude": 2.294694
    }

Where to start? Here is the roadmap:

1. Discuss the introduction of pragmas for enabling foreign compilation.
2. Introduce the HybridCompiler class.
3. Generate the hybrid method when there are no arguments.
4. Introduce the ParametricString class.
5. Generate the hybrid method when there are arguments.

Task 1: Discussion

Let’s start by noticing how our example above is slightly different from what we did in Story 3. Here <json> is not a tag but a pragma (there is no closing tag). We are using this pragma to make it clear that we will be using a foreign compiler.

A similar example with JavaScript

canSimulateCase
    <js>
    $scope.canSimulateCase = function(c) {
        return !$scope.isProcessingCase(c)
    };

One difference with tagged nodes is that here the entire method body is written in a foreign language. Why this variation is interesting? Because it will allow us to pass Smalltalk arguments to foreign methods. Like this:

jsonCoordinates: lat longitue: long
  <json>
  ^{
      "latitude": #lat,
      "longitude": #long
    }

meaning that the foreign source code will be generated dynamically.

Note that I’ve used # to mark what follows as an argument. We don’t want to replace every occurrence of 'lat' and 'long' with the arguments; do we?, so we need to tell where we want the replacements to happen. The reason for using # as a marker is that it presents (almost) no collision with foreign tokens.

Task 2: Hybrid Compiler

If we get back to our examples above, we will see that these methods have two parts: (1) a Smalltalk header including the pragma and (2) the foreign code. This accounts for hybrid compilation. We need to, at least, parse the beginning of the method to read the pragma that tells which compiler to pick, and then pass it the body. For doing all of this we will need the following class

Object
    subclass: #HybridCompiler
    instanceVariableNames: 'source smalltalk foreing method'
    classVariableNames: ''
    poolDictionaries: ''

The smalltalk ivar is initialized to the Smalltalk compiler, and foreign to the parser (or compiler) associated to the method’s pragma. When the source is set, the smalltalk compiler is used to read the pragma ('json' in our example). At this point the Registry (see Story 3) will provide us with the foreign parser. If there is no pragma or there is one which is not in the Registry, the compilation is entirely on smalltalk. The method ivar will hold the compilation result.

Task 3: Hybrid method

Once an instance of HybridCompiler has been initialized, it is time to compile the method. For now we will assume that there are no arguments (unary case).

HybriCompiler >> compile
  | cm |
  foreign isNil ifTrue: [^method := smalltalk compileMethod: source].
  ast := foreign parse: self body.
  cm := smalltalk compileMethod: self template.
  method := ForeignMethod from: cm.
  method
    sourceCode: source;
    foreignCode: ast format;
    foreignParser: foreign

There are several things to explain here:

• The #body method, with the help of the smalltalk parser, answers with the foreign body, i.e., the part of the source code that comes after the pragma.
• The #template method answers with the source code of the Smalltalk method that will actually be executed when the hybrid method is invoked.
• The ForeignMethod class is a subclass of CompiledMethod that adds support to certain messages required from hybrid methods.
• The #format message sent to the ast is optional. I would recommend including it because it is nice to have your foreign code formatted as soon as you save your method.

In the unary case we are now, the #template method has the following source code

template
  ^self selector , '
  #code.
  #parser.
  ^#code'

where #selector answers, with the help of the smalltalk compiler, the method’s selector; the following two symbols are placeholders for two slots in the literal frame that we will change below. Note that the compiled method will answer with the contents of the first literal slot.

ForeignMethod >> foreignCode: aString
  self literalAt: 1 put: aString

ForeignMethod >> foreignParser: aParser
  self literalAt: 2 put: aParser

The second literal holds the foreign parser, which may be needed for further processing (e.g., painting the source code).

Task 4: Macro Expansion

We will now address the case where the method has arguments which are inserted in the foreign code using # as the marker prefix. Let’s refer to these prefixed identifiers as hashed tokens.

What we need is to dynamically replace all hashed tokens with the corresponding arguments. For doing this we will introduce a new class named ParametricString, which will implement this transformation as a service.

Basically this new object takes aString including hashed tokens and a sequence of all possible tokens (in our case, the sequence of method arguments). Using this information the object produces a sequence of strings and indexes. The strings are the fragments between hashed tokens, the indexes refer to the sequence of hashed tokens. For instance if the inputs are:

• 'hello #world, this is a #test'.
• #('test' 'dummy' 'word')

the object should generate the following sequence:

#('hello ' 3 ', this is a ' 1 '.')

with the somewhat clearer Squeak-braces syntax, this would be

{'hello'. 3. ', this is a '. 1. '.'}

Later on, when the object is required to expand the tokens using actual arguments it will replace the indexes with the corresponding values, concatenating them all. The message to do this will be

aParametricString expandWith: arg1 with: arg2 ...

Task 5: Hybrid method with arguments

Since we have already worked on the unary case in Task 3, we only need to redo the #template method for the case where there are arguments.

The first change to consider is that what before was simply the selector, it is now a keyword message with the formal arguments. This can be simply accomplished with the help of the smalltalk compiler, so I will not go in detail here. We will just assume that self selector will answer with the signature of the method (i.e., 'keyword1: arg1 keyword2: arg2'…).

Since the source code will be now a bit more complex, I will use the #streamContents: constructor.

template
  | arguments processor |
  arguments := self arguments.
  processor := ParametricString from: self body tokens: arguments.
  ^String streamContents: [:strm |
    strm
      nextPutAll: self selector;
      crtab;
      nextPutAll: '| ast |';
      crtab;
      nextPutAll: '#code.';
      crtab;
      nextPutAll: '#parser.';
      crtab;
      nextPutAll: 'ast := #parser parse: (#code expandWith: '.
    arguments
      do: [:arg | strm nextPutAll: arg]
      separatedBy: [strm nextPutAll: ' with: '].
    strm
      nextPutAll: ').';
      crtab;
      nextPutAll: '^ast format']

A key remark here is that in order to connect processor with: #code we need to make sure we plug the processor in the first literal slot, where #code acts as its placeholder. This is achieved by a modification to the #compile method we saw in Task 3. Instead of sending ast format as the argument of foreignCode: we need to send

ParametricString from: code tokens: self arguments

Final words

As always, the code presented here is just a sketch of the actual code, which might end up being a bit more complex (but not too much!). Also, there are lots of details in my description for which I haven’t included any code at all. The reason is two-fold. Firstly, my goal is to provide a roadmap rather loadable code. Secondly, I don’t want to capture all the fun just for myself.

by Leandro Caniglia
President of FAST (Fundación Argentina de Smalltalk)

Story 3: Tagged Nodes

What do you do when you have to include JSON in a Smalltalk method? Something like this?

jsonCoordinates
  ^'{
      "latitude": 48.858093,
      "longitude": 2.294694
    }'

In other words, do you represent JSON data with plain strings? Wouldn’t it be nice to improve this? What if the compiler knew that this String should conform to a specific syntax? What if the Smalltalk browser knew how to format JSON strings? Or even color them for the sake of readability?

Before jumping to JSON strings, let’s step back and think of other cases that might be similar. Have you ever represented HTML as a plain String? What about CSS or even JavaScript? I’m sure you have faced situations where you inlined foreign code as a plain String in a method, keeping that information in your head rather than in the method, where it should naturally belong? Want to change this? Ok. Let’s do it.

Where to start? Here is the roadmap:

1. Consider the introduction of tags for inlining foreign scripts.
2. Introduce a new subclass of LiteralNode named TaggedNode .
3. Consider the introduction of foreign parsers such as a JsonParser.
4. Introduce a new class of AST node named ForeignNode.
5. Process the body of the foreign script, according to its semantics.

Task 1: Smalltalk tags?

Before making a decision for tags, let’s see which other options do we have. In order to inline foreign scripts, we must tell the Smalltalk parser how to delimit them. There are several delimiters already taken in Smalltalk:

• White space
• Single and double quotes
• Parenthesis and brackets (both square and curly)

Can we think of any other? Backticks are tempting. The problem is that they would only work for a single semantics. Say we decide to delimit JSON using backticks; how would we delimit HTML or CSS or JavaScript or Assembly or C, should the future bring a need for any of them?

We want flexibility and that’s why tags are a good choice.
Using tags we will be able to inline foreign code like this:

jsonCoordinates
  ^<json>
    {
      "latitude": 48.858093,
      "longitude": 2.294694
    }
  </json>

And how do we make sure that tags do not confuse the Smalltalk parser? To answer this question think of all the places where $< is misplaced in regards to the Smalltalk syntax:

• On the right of assignments
• When a message argument is expected
• On the right of the return symbol

In other words, none of the following sequence of characters conforms to the Smalltalk syntax:

• temp := < …
• 3 + < …
• self msg: < …
• ^< …

See? Every potential syntax error is an opportunity for extending the syntax!

Of course, angle brackets <...> are already legal in the Smalltalk syntax as pragma delimiters. But pragmas are illegal when placed in assignments, arguments and returns. To be valid, they must start a Smalltalk statement. And this is precisely why we will forbid tags at the beginning of statements and restrict them to assignments, arguments and returns.

Task 2: Add the class for tagged nodes

A tagged node is a way of delimiting foreign code and as such it is a new type of literal. So, add a subclass of LiteralNode named TaggedNode. This subclass will add the tag ivar that will link its instances to their specific meaning.

As we depticted above, instances of TaggedNode need to be instantiated by the parser in the following four cases:

• When parsing an argument of a keyword message
• When parsing the argument of a binary message
• When parsing the expression of an assignment
• When parsing the expression of a return node

This means that we need to modify essentially four methods so that they now check whether the next character is $<. If it is not, the original code regains control. Otherwise, the code branches to a new method that will scan the TaggedNode or fail (if there is no closing tag, etc.).

I’ve used the verb to scan because in order to form a TaggedNode, we will need to scan the input at the character level (usually the parser deals with tokens provided by the scanner).

When scanning the opening tag we will need to read the input until $> is reached (issuing and error if it isn’t). This will give us the value for the tag ivar of the TaggedNode. At this time we will also know that the closing tag should be '/', tag. So we can read the body of the foreign code until '</', tag, '>' is found (error if not).

At this point we are ready to

Task 3: Decide how to process the foreign script

Now we have access to the body of the TaggedNode. What do we do with it? Well, this depends on the semantics we want to give it. In the case of JSON, for instance, it would be enough to parse it using a JSON parser, and then format it using a JSON writer. We could also paint it with colors and emphases, so to make it look great in our environment.

In other cases, such as the one where the foreign code is Assembly, we could decide to go a step further and compile it into machine code. This will bring two capabilities: (1) Parsing and formatting/painting the Assembly source code and (2) Making the node answer with the corresponding machine code when the method is executed.

There are many other possibilities. In the case of JavaScript or any other programming language, we could decide to execute it on top of Smalltalk (at least up to some extent, this should be feasible).

On the other end of our wide horizon of possibilities there is one that consists in doing nothing, i.e, simply keeping the body as a String with no special semantics. This is useful for experimentation. For instance, if you plan to write a parser for inlining VBA code, before embarking in such a project, you might want to see how
the tagged code would look. You will need to format it yourself and will have no coloring available. However, it will bring a secondary benefit: you will not have to worry about duplicating embedded quotes (in VBA the quote is the comment separator).

The last case is the simpler one. Still, it requires the introduction of a new kind of literal node, which we will call StringNode. So, instead of keeping the body in the TaggedNode as a String, we will create a StringNode with the body as its value and will keep this new node as the value of the TaggedNode. This indirection will provide the flexibility we need for making free use of TaggedNode.

Note also that while making these decisions you should keep in mind that sometimes it is not necessary to implement a parser of the entire specification of the foreign language. For instance, if you will only deal with CTypes and C-Structures, you don’t need to parse arbitrary C, you just need to parse these declarations. The same might be true with other languages. Usually you will only inline a limited subset of them. The key here is to create the machinery that will make further enhancements easier and consistent.

Task 4: The foreign node

So far we have discussed two new nodes: TaggedNode and StringNode, both subclasses of LiteralNode. The ivar tag in TaggedNode holds the node’s tag string. Where we have to be careful is in deciding the contents of the value ivar because this is where the semantics enters the game.

Since we are planning for support of different languages, we will need a global Registry of available parsers/compilers. For instance, the package that loads the JSON parser will be able to register the <json> tag with the corresponding parser. Similarly for <html>, <css>, <asm>, <js>, <vba>, etc.

In this way, when the TaggedNode receives the #body: message with the foreign code as the argument, it will be able to enter the Registry with its tag and get the corresponding parser from there. If there is none, the TaggedNode will resort to StringNode, passing it the body and keeping this node in its value ivar.

TaggedNode >> body: aString
  value := Registry
    at: tag
      ifPresent: [:p | ForeignNode new parser: p]
      ifAbsent: [StringNode new].
  value value: aString

The ForeignNode will have two ivars: parser and ast. The latter is computed as follows:

ForeignNode >> value: aString
  ast := parser parse: aString

Task 5: Compile/Process

Now that we have all the pieces in place we can use them to, at least, format and/or color the foreign code. This is simply achieved by asking the ForeignNode, its ast or its formatted/colored representation. You could also provide more advanced featrues such as the ones we have mentioned in Task 3, or even take advantage of yet another technique that we will discuss in the next story which is Hybrid Compilation.

by Leandro Caniglia
President of FAST (Fundación Argentina de Smalltalk)

Story 2: Supporting Pragmas

All Smalltalk dialects support pragmas. Here is one:

identityHash
  <primitive: Hash>
  ^0

However, not all of them support other types of pragmas, as Pharo does. So, let’s see what it would take to add support for them to our dialect.

Where to start? Here is the roadmap:

1. Find the Smalltalk Parser in your system
2. In the Smalltalk Parser find the place where primitives are parsed
3. Modify the code that parses primitive declarations to recognize pragmas as well
4. Find a place in the CompiledMethod to store the pragma annotation

Now let’s see some hints on how to accomplish the tasks above:

Task 1: Find the Smalltalk Parser

Look for selectors like parse, parse:, parseMethod:, parseLiteral:, etc. In some dialects the entry point to parsing services is the Compiler, so you can debug the initial steps required to compile any expression until you reach the parser. You can also check to see if there are implementors of parserClass.

Task 2: Find the parsing of primitive declarations

This is best accomplished by debugging the compilation of any method with a primitive declaration. Just create a primitive method and debug its compilation. After some few clicks you should get to the parser method that distinguishes it as primitive.

Task 3: Parse the pragma

For this task I would recommend starting simple. There will be time for further sophistication. In this case “simple” means: assume the pragma is just one token. Much like:

methodWithPragma
  <ourPragma>
  self doSomething; etc.

The existing code in the parser should complain if the token that comes after $< is not 'primitive:' (or friends). And this is precisely where we need to branch, save the token as our pragma and (in this first attempt) save it in the MethodNode. Note that there is no need to add a new ivar to MethodNode, we can save the token in the same ivar where primitives are held. After all, primitives are numbers while pragmas are not, so we will be able to distinguish between them.

Don’t forget to consume the closing $>, which should be the next token. Otherwise issue a parsing error.

Task 4: Save the pragma in the method

This step is actually not required as we could always resort to the AST for getting the pragma. One could argue that it would be too slow to parse the entire method every time we want to access its pragma, should it have any. However, since pragmas occur before any other statements, there is no need to build the entire AST. In fact, we would only need a service in the parser that will stop parsing right before the parsing of the method sentences starts.

However, if you insist on avoiding any parsing, when a new CompiledMethod is compiled, the MethodNode should somehow inject the pragma in it. One way to do this is to add the pragma as the first literal. A practice also known as stealing literals. However, if we steal the first literal, how are we going to tell whether this first literal is a pragma or not?

There might be several tricks for solving this. For instance, in most dialects 0 (the SmallInteger) is never saved in the literal frame. The reason is that there are special bytecodes to operate with it, so the constant 0 doesn’t need to go into the literal frame.

Therefore, we could add the pragma as the first literal, and then add 0 as the second. Thus, in order to check and retrieve the pragma of a method we would do the following:

CompiledMethod >> pragma
  literals := self literals.
  ^(literals size >= 2 and: [(literals at: 2) = 0])
    ifTrue: [literals at: 1]

Note that the method will answer with nil if it has no pragma.

Final words

To make sure that 0 doesn’t go to the literal frame in your dialect, evaluate the following:

CompiledMethod allInstances select: [:cm | cm literals includes: 0]

It should answer with an empty array. If not, you will need to find another trick (hint: add two 0s instead of one.)

The simple case I’ve depicted here is for adding support to unary pragmas. You might want to allow for binary and keyword pragmas as well. The idea is the same. Just keep reading more tokens in Task 3, until $> is reached. Take a look at how Pharo does this for inspiration, starting at RBParser >> parsePragma. Then adapt the idea to your case.

If you decide to add support for multiple pragmas, note that you will need to steal n + 1 literals rather than 2 as we did in Task 4. You only need to move the 0 right after the last injection in the literal frame.

by Leandro Caniglia
President of FAST (Fundación Argentina de Smalltalk)

Story 1: Adding Squeak Braces

Does your dialect support Squeak Braces? To answer this question, try to evaluate the following expression:

{Date today. 3 + 4}

If you get an Array with the above two elements, today’s date and 7, it does. Otherwise, you would get a compilation error. In the latter case, you might be interested in extending the syntax of your dialect so to have what I call Squeak Braces.

Where to start? Here is the roadmap:

1. Find the hierarchy of classes that model parse tree nodes.
2. Add a new class for modeling brace arrays (let’s call it BraceNode or ArrayNode).
3. Add an ivar to the class for holding the elements of the array (let’s call it elements).
4. Add a method to the class for transforming the elements into a cascade node (see below).
5. Add all other required methods that nodes need to implement, especially those that message nodes have.

Now let’s see some hints on how to accomplish the tasks above:

Task 1: Finding the AST hierarchy

The Abstract Syntax Tree (a.k.a. AST) is the object that models the decomposition of a piece of source code into its constituents. This typically includes nodes for both the whole method and also its parts: literals, blocks, variables, etc. Therefore I would start by trying to find a class that includes Literal or LiteralNode in its name. From this class, go to the top of the hierarchy and you will get the complete picture of the place where you will be working next.

Task 2: Adding the new class

It’s simple, just subclass from the root of the AST hierarchy a new class appropriately named, say, BraceNode.

Task 3: Adding the required ivars

For sure we will need an ivar to keep the elements of the array. So, add the elements ivar. We will likely add one more ivar later though.

Task 4: Transforming the node into a cascade node

The idea here is to add a new method, say asCascadeNode, whose job is to answer with the CascadeNode that results from the expression:

(Array with: n)
  at: 1 put: (elements at: 1);
  …;
  at: n put: (elements at: 2);
  yourself

where n is elements size. To do this, you need to find the CascadeNode in the AST hierarchy and become familiar with it so you can create one instance of it for the method to return.

Task 5: Add other required methods

Typically, AST nodes implement the #acceptVisitor: message for supporting the Visitor pattern’s double dispatching mechanism. It’s implemenation is straightforward:

acceptVisitor: aVisitor
  aVisitor acceptBraceNode: self

You also need to find all visitors that you will need to enhance. To discover them look for implementors of visiting messages in the AST hierarchy such as visitCascadeNode:, etc. Writing each of the required implementor of visitCascadeNode: is also straightforward:

visitBraceNode: aBraceNode
  self visitCascadeNode: aBraceNode asCascadeNode

For other messages, take inspiration from the other nodes, especially, from CascadeNode.

Improvements

Once you have all of this complete and tested, you may want to improve your implementation a little bit. For instance, some occurrences of these Squeak Braces are just literals. One example would be:

{3. $a. {'hello' 'world'}}

This is actually equivalent to:

#(3. $a. #('hello' 'world'))

However, our implementation would work as well if we had written:

(Array new: 3)
  at: 1 put: 3;
  at: 2 put: $a;
  at: 3 put: (
    (Array new: 2)
      at: 1 put: 'hello';
      at: 2 put: 'world';
      yourself);
  yourself

which sends 9 messages instead of none! To avoid this waste, what we can do is to give literal arrays a special treatment. Here is how:

Task 6

At the top of the AST hierarchy, add the method isLiteral returning false (this might or might not be there already). Now repeat the same for LiteralNode except that this time answer with true.
Finally, add the isLiteral method to BraceNode on the lines of:

isLiteral
   ^elements conform: [:e | e isLiteral]

given that the elements of our BraceNode are themselves instances of AST nodes, this closes the circle.

Task 7

Next, add the asLiteralNode method to BraceNode on the lines of:

asLiteralNode
  ^LiteralNode new
    value: self literal;
    start: self start;
    stop: self stop

So, the only piece that is missing is the #literal message. Here it is:

literal
  ^elements collect: [:e | e literal]

where

LiteralNode >> #literal
  ^self value

Task 8

Finally, modify your implementations of visitBraceNode: method like this:

visitBraceNode: aBraceNode
  aBraceNode isLiteral
    ifTrue: [self visitLiteralNode: aBraceNode asLiteralNode]
    ifFalse: [self visitCascadenode: aBraceNode asCascadNode]

Depending on the internals of your system, some additional tweaks might be required. Just make sure your testing coverage is high enough. I almost forgot! In Task 3, I said that we would likely add another ivar to BraceNode, remember? Well, I was thinking in a cache for the result of asCascadeNode or asLiteralNode, depending on the case. This will help to preserve the identity of the BraceNode substitute should the translation be required more than once. No need to do this in advance though. Just keep it in mind.