2.4 Representation of Numeric and Textual Data

As noted already, virtual code applications are specified by functions operating on elements of a set having the properties described in Raw Material, which are convenient to envision as ordered binary trees or pairs of nil. However, virtual code applications normally deal with numeric or textual data, for example when they refer to the contents of a text file. It is therefore necessary for the application and the virtual machine emulator to agree on a way of describing textual or numeric data with these trees.

The purpose of this section is to explain the basic data structures used in the exchange of information between avram and a virtual code application. For example, an explanation is needed for statements like “an application invoked with the --baz option is expected to return a pair (foo,bar), where foo is a list of character strings ...”, that are made subsequently in this document. Such statements should be understood as referring to the trees representing the pairs, lists, character strings, etc., according to the conventions explained below.

Characters

An arbitrarily chosen set of 256 trees is used to represent the character set. They are listed in Character Table. For example, the letter A is represented by (nil,(((nil,(nil,(nil,nil))),nil),(nil,nil))). That means that when an application wants the letter A written to a text file, it returns something with this tree in it.

Booleans

The value of false is represented by nil, and the value of true is represented by (nil,nil).

Pairs

Given any two items of data x1 and x2, having the respective representations r1 and r2, the pair (x1,x2) has the representation cons(r1,r2).

Lists

A list of the items x1, x2 ... xn with respective representations r1 through rn is represented by the tree cons(r1,cons(r2...cons(rn,nil)...)). In other words, lists are represented as pairs whose left sides are the heads and whose right sides are the tails. The empty list is identified with nil. Lists of arbitrary finite length can be accommodated.

Naturals

A number of the form b0 + 2b1 + 4b2 + ... + 2^n bn, where each bi is 0 or 1, is represented by a tree of the form cons(t0,cons(t1...cons(tn,nil)...)) where each ti is nil if the corresponding bi is 0, and (nil,nil) otherwise. Note that the numbers bi are exactly the bits written in the binary expansion of the number, with b0 being the least significant bit.

Strings

are represented as lists of characters.

avram imposes no more of a “type discipline” than necessary to a workable interface between it and an application. This selection of types and constructors should not be seen as constraining what a compiler writer may wish to have in a source language.