05 / Strings

Strings, and the one ambiguity they create

MiniJava's published BNF has no strings. B-MJ adds them, because a language without text is hard to write interesting exercises in — and because the addition creates exactly one genuinely tricky parsing question, which is worth understanding.

An extension, deliberately

String is a first-class type here, not a library class. That means the type checker knows about it, all three semantics carry it, and it is listed in the Types toolbox category alongside int and boolean.

It is a small extension by design: one type, one literal form, three operators. Nothing else about MiniJava changes.

Literals and escapes

Double-quoted, with five escapes:

Escape	Produces
`\"`	A double quote
`\\`	A backslash
`\n`	Newline
`\t`	Tab
`\r`	Carriage return

The block is String Literal, in the Values category.

The three operators

Operator	Type	Notes
`s.charAt(i)`	`String → int → String`	Returns a 1-character String. Gets stuck out of bounds.
`s.concat(t)`	`String → String → String`	The only way to join strings.
`s.length()`	`String → int`	Note the parentheses.

System.out.println accepts an int or a String, and prints strings raw — without quotes — as Java's does.

+ stays int-only

There is no string concatenation with +. Java's overloading of + for strings is convenient but it is exactly the sort of implicit conversion MiniJava exists to leave out, and supporting it would mean the arithmetic rules could no longer say simply “two ints give an int”. Use concat.

charAt returns a String

In Java, charAt returns a char. MiniJava has no char type, and adding one for a single method would be a poor trade. So B-MJ's charAt returns a String of length 1.

The practical consequence is pleasant: characters compose with concat and compare with the ordinary string operations, so a program that takes a string apart and puts it back together — the Palindrome example, for instance — needs no conversions.

An out-of-bounds index gets stuck rather than returning a default. This mirrors Java throwing, expressed in the way a small-step machine can express it: there is no transition to take, so the machine halts on that state and shows you where. The same is true of division by zero.

length, length() and calls

This is the ambiguity the extension creates. Three things that look alike:

Written	Means	Type
`a.length`	Array length — no parentheses, as in Java	`int`
`s.length()`	String length — empty parentheses	`int`
`o.length(x)`	An ordinary call to a user method named `length`	whatever it returns

The parentheses do the disambiguating, exactly as they do in Java. In blocks this is unambiguous anyway — Array Length, String Length and Method Call are three different blocks — but it matters when you type into the code editor.

Matched by name, in postfix position

charAt, concat and length are recognised by name where they appear after a dot. So a user method cannot shadow those three names.

Any other use of the identifier stays free: charAt as a variable name is perfectly legal, because a variable never appears in postfix position after a dot. If you find yourself wanting a method called concat, give it another name.

Strings in the steppers

All three semantics carry the type — strings are not a front-end convenience that disappears before execution:

The CESK machine has a Str value and concat, char-at and str-length rules, under both value models.
The substitution rewriter treats string literals as values, with the same salient rule names — so the correspondence check covers string operations too.
The legacy evaluator behind the Structure and Value tabs prints strings raw.

Because strings are inline values rather than heap objects, they behave identically under Model A and Model B. They are one of the things the two models are guaranteed to agree about, which makes them a useful control when you are studying where the models differ.

B-MJ is developed at L-Workshop. This help was written against the build running at b-mj.l-workshop.my.id.