Code Identity

February 25, 2010

A Ruby Quiz once asked us to print “Hello, world!” in an unusual way. Being an over-achiever-to-a-fault, I wondered whether I could make the computer invent the alternatives for me. Why come up with one peculiar solution when a little program could keep coming up with more?

The idea was to define code identities: transformations that change an expression’s form while preserving something we care about. For a string, reversing it twice gives us the same characters. Splitting it into characters and joining them again does too.

"Hello, World!".reverse.reverse
"Hello, World!".chars.join

Neither is an improvement over the original string. That’s beside the point. We’re generating variations, not optimizing them. In fact, the pointless extra work is part of the fun.

What stays the same?

Before generating anything, we need to decide what counts as a solution. Here, a program must write the requested UTF-8 text to standard output, write nothing to standard error, and exit successfully. Newlines are part of the text. The default is "Hello, World!\n".

This deliberately narrow contract lets us use print, $stdout.write, and printf("%s", ...) as different output forms. Their return values need not agree: write returns a byte count, for instance. We are comparing standalone programs by their output and exit status, not claiming that these calls can replace one another in every Ruby expression.

Likewise, puts isn’t interchangeable with print for arbitrary text: puts can add a newline. Rather than hide that difference, we’ll make the requested bytes explicit.

Growing a family of expressions

Our starting point is a string literal. Ruby’s String#dump produces its quoted Ruby representation, including escapes. A quote, backslash, newline, or interpolation-looking sequence in the text remains data.

We then grow new expressions from the literal. Each expression can be wrapped in .reverse.reverse or .chars.join; those expressions can be wrapped again. The parentheses matter: each rule applies to the whole expression it receives.

require 'set'
require 'open3'
require 'rbconfig'

class CodeIdentity
  RULES = [
    ->(expression) { "(#{expression}).reverse.reverse" },
    ->(expression) { "(#{expression}).chars.join" }
  ].freeze

  def initialize(text, rules: RULES)
    unless text.is_a?(String) && text.encoding == Encoding::UTF_8 && text.valid_encoding?
      raise ArgumentError, 'text must be a valid UTF-8 string'
    end

    @literal = text.dump
    @rules = rules.dup.freeze
  end

  def original
    "print(#{@literal})"
  end

  def generate(limit = 20)
    unless limit.is_a?(Integer) && limit.positive?
      raise ArgumentError, 'limit must be a positive integer'
    end

    queue = [@literal]
    seen = Set.new(queue)
    programs = []
    cursor = 0

    while cursor < queue.length
      expression = queue[cursor]
      cursor += 1

      forms = [
        "print(#{expression})",
        "$stdout.write(#{expression})",
        "printf(\"%s\", #{expression})"
      ]
      forms.each do |source|
        programs << source
        return programs if programs.length == limit
      end

      @rules.each do |rule|
        candidate = rule.call(expression)
        queue << candidate if seen.add?(candidate)
      end
    end

    programs
  end

end

The queue makes this a breadth-first search through expression forms. A set remembers which forms have already been seen, so a rule that returns its input, or a cycle between two forms, does not keep the search alive forever. If the queue runs out, generate returns however many programs it found. If the rules keep producing new forms, the requested limit stops it. The default rules can keep nesting, so there is no fixed number of distinct source strings they can produce—although this particular search always asks for a finite number.

This is deliberately a generator for a small family of string expressions. It accepts text, not arbitrary Ruby source. We aren’t searching through unrelated programs or using a regular expression to guess where Ruby string literals begin and end. The rule functions are code we supply ourselves; they must return Ruby expressions with the intended string value.

Putting the candidates on trial

The generation rules give us a reason to expect the same output. Running the programs gives us a way to catch mistakes in the implementation.

Each candidate runs in a separate Ruby process. That keeps its globals and output streams separate from the program doing the checking. Ruby’s Open3.capture3 collects standard output, standard error, and process status. Binary capture lets us compare the output bytes directly.

require 'open3'
require 'rbconfig'

class CodeIdentity
  def observe(source)
    stdout, stderr, status = Open3.capture3(
      RbConfig.ruby, '-EUTF-8:UTF-8', '-e', source, binmode: true
    )
    [stdout, stderr, status.exitstatus, status.termsig]
  end

  def verify!(programs)
    expected = observe(original)
    programs.each do |source|
      unless observe(source) == expected
        raise "Output mismatch for: #{source}"
      end
    end
    true
  end
end

These methods reopen the same CodeIdentity class. They compare each candidate with the literal-printing baseline, including whether the process exited normally or was terminated by a signal.

There is an important boundary here. Matching these observations is evidence about these runs, not a proof that two arbitrary programs are equivalent. Return values, allocations, object identity, timing, files, and other side effects are outside the comparison. Even our string transformations make new objects. Apply them to an object with different method behavior and the reasoning must start again.

Hello, World, nine ways

The complete script includes a small command-line interface. From the directory containing it:

ruby code_identity.rb -n 9 --check

It produces:

print("Hello, World!\n")
$stdout.write("Hello, World!\n")
printf("%s", "Hello, World!\n")
print(("Hello, World!\n").reverse.reverse)
$stdout.write(("Hello, World!\n").reverse.reverse)
printf("%s", ("Hello, World!\n").reverse.reverse)
print(("Hello, World!\n").chars.join)
$stdout.write(("Hello, World!\n").chars.join)
printf("%s", ("Hello, World!\n").chars.join)

The checker also reports Verified 9 programs. on standard error. That is output from the checker itself, not from the generated candidates.

To generate programs for different text, pass one quoted argument:

ruby code_identity.rb -n 20 --check 'Something else entirely.'

The script and its tests were checked with Ruby 3.4.9. The tests cover quotes, backslashes, literal interpolation syntax, percent signs, Unicode, NUL bytes, and different newline endings. They also check rule exhaustion, duplicate and cyclic rules, exact limits, and candidates that print the wrong output, write to standard error, or exit unsuccessfully.

What interests me most is the separation between three jobs: describing transformations, exploring their combinations, and deciding which results count as equivalent. This little toy gives each job a place. To move beyond strings, we’d need to define another domain and transformations whose assumptions we can state just as clearly.

Other contestants may have found more ingenious individual solutions. I’ve built a machine for producing ever more elaborate ways to say the same thing. Whether that is a triumph of programming or an elaborate waste of clock cycles, I’ll leave to you. ;)

← Selected writing · Older writing