RPN in Oz


Oz was created in 1991 and has been continually developed since then. Initially little known, it received greater popularity in the late 1990s, especially since the responsibility for its development had been taken up by an international group of universities.

Oz was designed as a multi-paradigm language. Its computational model strongly favours declarative programming, as one that makes reasoning about programs feasible and presents good opportunities for optimisation. By virtue of this, Oz is very well suited for functional, logic and constraint-based, as well as concurrent and distributed programming. It also supports imperative and object-oriented programming, blending all these coherently.

Possible influences for Oz must have been, based on observable similarities, Standard ML, Prolog, Lisp, and also perhaps Erlang. The language itself strongly influenced Alice ML, a recent derivative of Standard ML that is at present very actively developed. (Several of the main developers of Oz, including its original author, are now with the Alice ML team.)

Currently, Oz is implemented in the Mozart programming system, which includes a standalone compiler, an interactive development environment (based on the Emacs text editor), and program libraries. Since this is the only implementation of the language, and since there is no available definition of Oz other than that of Mozart, it is somewhat unclear what in the language and in its accompanying libraries is Oz proper and what belongs to Mozart. Regrettably, at present (2008) the Oz/Mozart documentation is also incomplete in other respects.

A recently published introductory textbook on programming, Concepts, techniques, and models of computer programming (see the Links section), is the main – and to a great extent the only – source for learning how to program in Oz.

Computation Model and Kernel Language

Oz is dynamically but strongly typed language: each value is considered to have a type, so that only a certain set of operations can be applied to that value. That does not preclude some values from belonging to several types, if those types extend each other. For example, an integer is a number, but there is no way to treat a number as a string or the other way around.

A small number of basic concepts and constructs constitutes a kernel of the language. More datatypes, syntax forms and other elements are implemented on top of the kernel sub-language, or at least are semantically expressible in it.

The kernel features the following:

‘Names’ (elsewhere, such as in Erlang, known as references) are created by a special procedure in a way that each such value is globally unique even in a distributed environment, and can ensure security through being ‘unforgeable’. Cells are the basic provision for imperative, state-preserving programming.

A record is a set of fields, where both the record itself and the fields are known by labels, and the fields can have values.

Variables in Oz are said to be ‘dataflow’ because of their relation to the execution model of the language. A variable can refer to a value or stay unbound. If a part of a program tries to access the value of an unbound variable, it is suspended until some other part binds a value to the variable. Once it is bound, a variable can only refer to the same value; rebinding is possible but changing the value is not.

Partially unbound, and therefore partially (not) computed values can still be passed across procedure invocations. A record can be constructed with (all or part of) its fields left unbound. Then a variable can get bound to that record and thus be used in computations without blocking them. Blocking only takes place when an unbound field of that variable’s value is accessed. Thus, although Oz has eager semantics, a form of lazyness is none the less available through construction and use of partially computed values. This widens the repertoire of techniques, as well as the possibilities for compile-time optimization, even in sequential programming, and has immence importance for concurrent programming.

Procedures are created at run-time as anonymous values and, like other values, can be referred to by variables. Thus, there is nothing special about a procedure name – it is but a variable bound to a procedure value. Furthermore, in a procedure call the procedure is no different from the arguments – in fact, even syntactically, because the procedure is the first argument of the call operation. It follows that, if that argument is not an immediate value but a variable, and that variable is unbound, the call blocks, awaiting for the variable to be bound to a procedure.

Recursively executing procedures is the only form of repetition that Oz has at its kernel level.

Threads are created with an explicit construct. Any portion of the program can form a thread. Synchronization is implicit, (dataflow) variables being the basic mechanism for synchronization and communication: a thread blocks if it attempts to access a value that is not yet available, and remains blocked until another thread creates the needed binding.

With respect to resource consumption, threads are inexpensive. Due to the low overhead of thread creation, a great number of them can be spawned within a single program without obstructing the underlying operating system.

Additional Constructs

At the extra-kernel level of Oz, there are, among others:

Explicitly declaring a function lazy makes it compute its result on demand rather than eagerly, which makes sense especially when the result is a composite value: the value can be constructed then piecewise. See the RPN calculator implementation for an example of how this works with lists.

Note that record construction is the only form of data aggregation in the kernel language. Those data structures that are not in the kernel are derived from records.

A tuple is a special case of a record, where implicitly assigned successive integers are used rather than symbolic atoms as field labels. A list is either an empty one, or a tuple of two, i.e. a pair, of its head and tail. As a consequence, unlike other strongly typed languages, lists are heterogeneous. Strings are lists of characters, where characters are small nonnegative integers, interpreted as ascii codes.

All the mentioned, as well as the other ‘datatypes’ of Oz defined outside of the kernel, are not types in the proper sense, but rather, conceptual structures, supported by convenient syntax and library functions.

A chunk is a structure with contents like a record, but with a ‘name’ (in the sense of the kernel) rather than a symbolic atom as its label. Chunks are the clay from which abstract datatypes, language-defined as well as programmer-defined, are built in Oz. All they, e.g. ports, arrays, dictionaries, classes, and objects, are implemented as library modules with corresponding functional interfaces and eventually use chunks to represent structured data. Where mutability is needed, cells, too, enter the picture. A notable example in this respect is the object-oriented programming, because objects have state which must be able to change.

In cases where a more elaborate communication is needed than just waiting in one thread for a value to be made available by another, ports can be used. They are the main message-passing mechanism between threads. The port construct is an encapsulation of the concept of a stream: a list created incrementally, i.e. with ever unbound tail, by one thread and consumed by one or more threads, thus implementing an asynchronous producer-consumer pattern of communication. Any data sent to a port is being appended to the end of the underlying stream. A port, however, is more than just a stream, because it is itself a value and as such can be embedded in other data and passed as an argument in procedure calls. Also unlike a stream, a port can be shared among more than one senders.

An Example

This example is adapted from the Tutorial of Oz and illustrates how the dataflow principle and partially computed values can be used to implement a demand-driven list construction.

Consumer processes values from a list, Cs. While those values are provided by Producer, which is called in a separate thread to do so, the list Cs itself is constructed within Consumer. Demanding a new value, generating it and consuming it follow in strict succession. Here is how it goes.

proc {Producer Ps}
  case Ps of P|Pt then
    P = ...
    {Producer Pt}
  else more must be produced... end

proc {Consumer Cs}
  if ...more needed... then
    C|Ct = Cs in
    ...consume C...
    {Consumer Ct}
  else Cs = nil end

{Consumer thread {Producer $} end}

Cs in Consumer and Ps in Producer are the same value, initially absent. Producer tries to match Ps against P|Pt, a list pattern with P the head and Pt the tail of the list. The matching operation waits until Ps gets bound, and then either succeeds or fails. Ps, however, can only get bound as Cs does in the Consumer thread. Cs gets bound either to a non-empty list, due to executing the unification instruction C|Ct = Cs, or to the empty list nil. It is important that, in the former case, although Cs does get bound, its head and tail, C and Ct, do not. As P and C bind to the same value, Producer can give P whatever value it happens to, and thus C gets bound and is ready for consumption. Meanwhile Pt, and therefore Ct, remain unbound as the two procedures use them in place of the initial Ps and Cs in the respective recursive calls.

If Cs is bound to nil in Consumer, meaning that that procedure needs no more values from Producer, the matching operation in Producer fails, which normally leads to ending that procedure. Thus creating a list item in Consumer is the request necessary to trigger the production of a value in Producer, and just as many values are generated as list items to hold them are created.

Both recursive calls are tail-recursive and therefore compile into loops.

Links of Relevance

Home page for Oz and The Mozart Programming System

Implementation page for Oz and Mozart

A companion website to the book    Concepts, techniques, and models of computer programming
        – a textbook, featuring Oz as the language to expose ideas about programming

An on-line draft version of the above book