Oz (language)

Oz is a programming language allowing to use and combine different programming paradigms:

  • Functional ,
  • Procedural and objects ,
  • Relational and logical ,
  • Constraints ,
  • Competition ,
  • distribution.

Oz provides logical variables by default even though it is possible to use mutable variables. Similarly, evaluation is strict by default, but lazy evaluation is possible.

The originality of this language compared to others supporting logical (on the one hand) or concurrent and distributed (on the other hand, as Erlang ) programming is the integration of these paradigms into a coherent whole. A unique abstraction is provided by Oz: the computational space , which allows the encapsulation of calculations for speculative purposes and combines logical / constraints, object orientation and mutability, competition and distribution, in the same language.

Oz has a garbage collector and an exception handling distributed.

Oz is implemented by the Mozart system, providing a compiler, a virtual machine and a development environment using EMACS for the editing part, a graphical debugger supporting competition and distribution, a search tree search tool for programming By constraints, etc.

The book Concepts, Techniques, and Models of Computer Programming [ archive ] (MIT Press, 2004) uses Oz as its main language to illustrate the different programming concepts. There are academic courses of programming  [ archive ] in French based on Oz and this book.

This language was developed by three schools:

  • Catholic University of Louvain (UCL – Belgium )
  • Universität des Saarlandes (Germany)
  • Swedish Institute of Computer Science (Sweden)

Note: The origin of the name Oz comes from the famous children’s tale, The Magician of Oz .

Language Features

Data Structures

Oz is based on a subset of the language, called “kernel language” containing few types of data that can be extended to others, more convenient through syntactic sugar .

Basic data structures:

  • Numbers: floating-point or integer
  • Registration: composed data structure to group information: circle(x:0 y:1 radius:3 color:blue style:dots). Here, the terms x, y, radius … are the fields (called “features”), with their associated values. “Circle” is defined as the name of the record, its “label”.
  • Tuple: Recording with increasing integer field names: circle(1:0 2:1 3:3 4:blue 5:dots)
  • List: simple linear structure
(2 '' '(6' | '(nil)))) As a recording
2 | (4 | (6 | (8 | nil))) With a little syntactic sugar
2 | 4 | 6 | 8 | nil% With more syntactic sugar
[2 4 6 8]% And with even more

These data structures are dynamically typed (constants) values. Variable names in Oz are written with a first capital letter in order to differentiate them from literal constants 1 (atoms which begin with a lowercase).

Functions

Functions 2 are first class values, allowing higher order programming :

Fun {Fact N}
 If N = <0 then 1 else N * {Fact N-1} end
End
Fun {Comb NK}
 {Fact N} div ({Fact K} * {Fact NK})% No integer overflow in Oz (as long as memory remains)
End
Fun {SumList List}
 Case List of nil then 0
 [] H | T then H + {SumList T}% Shape Detection
 End
End

Functions can use both free and linked variables. The free variables are found by lexical scope 3 .

Higher order programming

Functions are like other elements of Oz. A function can be passed as an attribute to another function or can be returned by it.

Fun {Square N}% A simple function
 N * N
End
Fun {Map F Xs}% F is a function here (using higher order programming)
 Case Xs
 Of nil then nil
 [] X | Xr then {FX} | {Map F Xr}
 End
End
%Use
{Browse {Map Square [1 2 3]}}% Show [1 4 9]

Anonymous functions

Like many other functional languages, Oz supports the use of anonymous functions (which have no names) with higher order programming. The symbol $ is used for this purpose.

% The function squared is passed as an anonymous argument
{Browse {Fun Map {$ N} N * N end [1 2 3]}}% Show [1 4 9]

Since anonymous functions have no names, it is impossible to recursively define anonymous functions.

Procedures

Functions in Oz must return a value as the last instruction of the function during execution. In the following example, the Ret function returns 5 if X> 0 and -5 in the other cases.

declared
Fun {Ret X}
 If X> 0 then 5 else ~ 5 end
End

But Oz also provides a feature in case we do not wish to return value. Such functions are called procedures 4 . Procedures are defined using the proc keyword, as follows:

declared
Proc {Ret X}
 If X> 0 then {Browse 5} else {Browse ~ 5} end
End

The above example does not return any value, it just displays 5 or -5 in the interface of Oz depending on the sign of X.

Variable dataflow and declarative competition

When the program encounters an unbound variable, it expects a value:

Thread
 Z = X + Y% V wait until X and Y are linked to a value
 {Browse Z}% Displays the value of Z
End
Thread X = 40 end
Thread Y = 2 end

It is not possible to change the value of a dataflow variable once assigned (single assignment)

X = 1
X = 2% Error

Dataflow variables make it easy to create competing agents:

Fun {Ints N Max}
 If N == Max then nil
 Else
 {Delay 1000}
 N | {Ints N + 1 Max}
 End
End
Fun {Sum S Stream}
 Case Stream of nil then S
 [] H | T then S | {Sum H + ST} end
End
Local XY in
 Thread X = {Ints 0 1000} end% Creating an agent that generates a stream
 Thread Y = {Sum 0 X} end% Creating an agent that processes the stream
 {Browse Y}
End

Because of the way dataflow variables work, it is possible to place threads anywhere in the program and it will be guaranteed that it will keep the same result. This makes competing programming really easy. Threads are fairly light: you can run thousands of threads at a time 5

Example: Successive Divisions

This example calculates a prime number flow using the successive divisor algorithm by creating agents that filter the non-prime numbers.

Fun {Sieve Xs}
 Case Xs of nil then nil
 [] X | Xr then Ys in
 Thread Ys = {Filter Xr fun {$ Y} Y mod X \ = 0 end} end
 X | {Sieve Ys}
 End
End

Paresse

Oz uses the strict evaluation but also the lazy evaluation 6 if possible:

Fun lazy {Fact N}
 If N = <0 then 1 else N * {Fact N-1} end
End
Local XY in
 X = {Fact 100}
 Y = X + 1% We need the value of X and Fact is calculated
End

The lazy evaluation gives the possibility to store almost an infinity of data structures in Oz. The power of lazy evaluation can be seen through the following code fragment:

declared
Fun lazy {Merge Xs Ys}
 Case Xs # Ys
 Of (X | Xr) # (Y | Yr) then
 If X <Y then X | {Merge Xr Ys}
 Elseif X> Y then Y | {Merge Xs Yr}
 Else X | {Merge Xr Yr}
 End
 End
End
Fun lazy {Times N Xs}
 Case Xs
 Of nil then nil
 [] X | Xr then N * X | {Times N Xr}
 End
End
Declare H
H = 1 | {Merge {Times 2 H} {Merge {Times 3 H} {Times 5 H}}}
{Browse {List.take H 6}}

The above code elegantly calculates all regular prime numbers 7 in an infinite list. Real numbers are calculated only if they are used.

Competition by sending messages

The competing declarative model can be extended by sending messages using simple semantics:

declared
Local Stream Port in
 Port = {NewPort Stream}
 {Send Port 1}% Stream is now 1 | _ ('_' indicates an unbound variable)
 {Send Port 2}% Stream is now 1 | 2 | _
 ...
 {Send Port n}% Stream is now 1 | 2 | .. | n | _
End

Through a port and a thread, the programmer can define asynchronous agents:

Fun {NewAgent Init Fun}
 Msg Out in
 Thread {FoldL Msg Fun Init Out} end
 {NewPort Msg}
End

State and objects

It is still possible to extend the declarative model in order to support the state and the object-oriented programming by a very simple semantics; We create a new mutable structure, cells (Cells).

Local AX in
 A = {NewCell 0}
 A: = 1% Changes the value from A to 1
 X = @A% @ Used to access the value of A
End

With this very simple semantics, Oz can support all the object-oriented paradigm. A little syntactic sugar allows to easily integrate the OOP as follows:

Class Counter
 attr val
 meth init(Value)
 val:=Value
 end
 meth browse
 {Browse @val}
 end
 meth inc(Value)
 val :=@val+Value
 end
end
local C in
 C = {New Counter init(0)}
 {C inc(6)}
 {C browse}
end

Notes et références

  1. ↑ https://mozart.github.io/mozart-v1/doc-1.4.0/tutorial/node3.html#label18 [archive]
  2. ↑ Leif Grönqvist, « Higher Order Functions », dans Advanced Functional Programming in Oz (lire en ligne [archive])
  3. ↑ Robert Gentleman and Ross Ihaka, “Lexical Scope in Statistical Computing” , in Journal of Computational and Graphical Statistics , vol.  9, ( Read online  [ archive ] ) , chap.  3, Systems and Languages, p.  491-508
  4. ↑ https://mozart.github.io/mozart-v1/doc-1.4.0/tutorial/node5.html#control.procedure  [ archive ]
  5. ↑ http://www.mozart-oz.org/documentation/tutorial/node8.html#chapter.concurrency  [ archive ]
  6. ↑ Paul Hudak , “Design, evolution, and implementation of functional programming languages” , in ACM Computing Surveys (CSUR) , vol.  21, p.  359-411
  7. ↑ Rao, AC and Varada Raju, D, “Application of the Hamming number technology to detect isomorphism Among kinematic chains and inversions” in Mechanism and Machine Theory , Vol.  26,, P.  55-75