Skip to content
Tutorials Center
My learning

Topics

Lesson 37 of 38 ยท Projects and Practice

Project: A Smalltalk Message Interpreter

Build a small interpreter for Smalltalk-style expressions in JavaScript: a tokenizer, a parser for unary, binary and keyword messages with the right precedence, and an evaluator with blocks. Runs in your browser.

Smalltalk syntax is famously small, and its three kinds of messages follow one simple precedence rule. That makes it an excellent first interpreter project. In this lesson you will write a tiny evaluator, in JavaScript, for Smalltalk-style expressions such as 3 + 4 * 2, 10 max: 3 + 1, 5 factorial and [ :x | x * x ] value: 7. It is not a real Smalltalk, just a stand-in that teaches how a language like it is parsed and evaluated.

You should be comfortable with message syntax from the earlier chapters. The project has four stages: tokenizing, parsing, evaluating and extending. Everything you run here is JavaScript; Smalltalk code in the text is read-only.

The grammar we support

Three kinds of messages, from strongest to weakest binding:

  1. Unary messages: 5 factorial, 3 negated, 'abc' size.
  2. Binary messages: 3 + 4, a < b, x * y.
  3. Keyword messages: 10 max: 3, 3 between: 1 and: 5.

An expression is evaluated by parsing unary messages first, then binary (left to right with no operator precedence!), then keyword. In real Smalltalk, 3 + 4 * 2 is (3 + 4) * 2 = 14, not 11. That surprises people from other languages, and our parser reproduces it (read-only):

SMALLTALK
3 + 4 * 2.             "14"
2 raisedTo: 3 + 1.     "16: the binary + runs first, then the keyword"
5 factorial + 1.       "121: unary first"

Stage 1: the tokenizer

The tokenizer turns text into pieces: numbers, strings, identifiers, keywords (ending with a colon), binary operator characters, and punctuation for blocks and parentheses.

JS Stage 1: tokenizer

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Notice that max: becomes one keyword token, and the doubled quote in a string is an escape.

Stage 2: the parser

The parser follows the precedence rule with three functions that each call the next: keywordExpr calls binaryExpr, which calls unaryExpr, which calls primary. Each builds a send node { send, receiver, args }.

JS Stage 2: parser

Press Run (or Ctrl + Enter) to see the console output here.

No output.

The output for 3 + 4 * 2 nests as ((3 + 4) * 2): the first send is the innermost receiver. That left-to-right shape is exactly why Smalltalk has no operator precedence table.

Stage 3: the evaluator

The evaluator walks the tree. Numbers, strings and blocks are JavaScript values; a primitive table maps class + selector to behaviour. Blocks are closures that capture their environment.

JS Stage 3: evaluator

Press Run (or Ctrl + Enter) to see the console output here.

No output.

The method send is the heart of the whole thing: it looks up a selector in the receiver's table and fails with a "does not understand" message otherwise. Compare this with the lookup described in reflection. The tokenizer and parser repeat in every stage, because each TryIt must run on its own.

Stage 4: extend it

Try these in order; each is a small change to one function:

  1. Add ifTrue:ifFalse: for booleans, so (3 > 2) ifTrue: [ 'yes' ] ifFalse: [ 'no' ] works. Booleans are JavaScript true and false, so add a third table.
  2. Add variables and assignment: parse x := 5. and keep an environment object across statements.
  3. Add cascades (;), where several messages go to the same receiver.
  4. Add a Transcript show: global so programs can print.
  5. Add user-defined classes: a table of method blocks per class name. That is the first step towards a real object system; compare metaclasses.
flowchart LR
  S["source text"] --> T["tokenizer"]
  T --> P["parser<br/>unary > binary > keyword"]
  P --> A["syntax tree of sends"]
  A --> E["evaluator<br/>send / lookup"]
  E --> V["value"]

Smalltalk needs almost no grammar: literals, variables, blocks and one kind of expression, the message send.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does 3 + 4 * 2 evaluate to in Smalltalk?

    Binary messages evaluate left to right with no precedence: (3 + 4) * 2 = 14.
  2. 2. In which order do message kinds bind?

    Unary binds tightest, then binary, then keyword.
  3. 3. How does the interpreter model a block?

    A block remembers its defining environment so it can run later.
  4. 4. What does the interpreter do for an unknown selector?

    send looks up the selector in the receiver's table and fails if there is none.

Summary

  • Smalltalk expressions are chains of sends with three precedence levels: unary, binary, keyword.
  • A tokenizer, a three-level recursive-descent parser and a small evaluator are enough for a working subset.
  • Blocks are closures; primitives are tables from selector to function.
  • Unknown selectors become does-not-understand errors.
  • Everything run here is JavaScript; real Smalltalk is not available on this site.

Next: Practice: Smalltalk Exercises