This file was automatically generated from the interactive Strasheela tutorial. Some aspects of the text only make sense in the original interactive tutorial application (e.g., buttons indicated to press, and positions specified on the screen), and not in this version of the text.
This chapter covers more basic info about Oz. However, despite still being "basic" information, it requires a solid understanding of material in the previous chapter.
Pattern matching is a convenient way to access the elements contained in compund data types (i.e. records, lists, etc). Pattern matching decomposes such compund data, declares new variables, and binds these variables to parts of the compound data.
The primary pattern matching construct is the `case' statement, but some programming constructs (such as functions) allow pattern matching via an implicit case statement.
In the section below, `case' declares the two variables H and T and binds them to the head and tail of the list Xs. Finally, the H and T are inspected. Please note that the pattern-matching expression H|T is written with the usual list syntax using the cons-operation (|).
This approach can be used to pattern match lists of arbitrary length, except empty lists (i.e. nil). Try changing the definition of Xs to a list of a different length and watch how the value of T changes.
local Xs = [1 2 3 4] in case Xs of H | T then {Inspect H} {Inspect T} end end
The previous section matched the head and the tail of a list. Instead, we can also match individual list elements (or the elements of other data structures, such as records or tuples).
WARNING: if the length of the lists is not equal, an error occurs.
local Xs = [1 2 3 4] in case Xs of [A B C D] then {Inspect A} {Inspect B} {Inspect C} {Inspect D} end end
Having only a single clause to match against (as in the previous sections), can be too restrictive. This section presents a typical `case' expression. It matches a list, which checks whether Xs is either a non-empty list, an empty list, or some other value. Additional case-clauses are introduced with the keyword `[]'. You may want to play around with the value of Xs to try out these different clauses.
local Xs = [1 2 3 4] in case Xs of H|T then {Inspect nonEmptyList} [] nil then {Inspect emptyList} else {Inspect notList} end end
The following function GetX expects a record as argument; this record must match test(x:X ...). The variable X is implicitly declared and bound to the value at the feature 'x' of the record given as argument to the function.
Please note that the record in the header of the function GetX is not even complete but contains three dots (...) to indicate that further record features are possible.
local R = test(x:value1 y:value2) fun {GetX test(x:X ...)} X end in %% show the normal record {Inspect R} %% show the feature we want {Inspect {GetX R}} end
Oz provides a rich set of procedures for processing compound data such as lists and records. A few examples are shown here. More procedures are listed in the reference documentation at
Test whether a record has a certain feature.
{Inspect {HasFeature unit(x:1 y:2 z:3) y}}
Return the features of a record as a list.
{Inspect {Arity unit(a b x:1 y:2 z:3)}}
"Merge" two records. Note that features and labels of the second record take precedence over the first.
{Inspect {Adjoin unit(x:1 y:2 z:3) test(foo:hi bar:there z:'overwrite!')}}
Return the nth element of a list. Note that the list is 1-indexed.
{Inspect {Nth [a b c d] 2}}
Reverse a list.
{Inspect {Reverse [a b c d]}}
Append two lists.
{Inspect {Append [a b] [x y]}}
You can define procedures over lists and records as easily as numeric procedures. Following is the definition of the function Append.
local fun {Append Xs Ys} if Xs == nil then Ys else Xs.1 | {Append Xs.2 Ys} end end in {Inspect {Append [a b] [x y]}} end
Oz procedures (and functions) are first-class values. This means that a procedure can be processed like any other value. For example, procedures can be given to other procedures as arguments.
This leads to highly flexible programming technique called higher-order programming. Procedures expecting procedures as arguments are called higher-order procedures. This concept is demonstrated be several sections.
The function Filter expects a list and a test function, and returns only those elements for which the test function returns true.
The function IsEven returns true for even integers and thus a list with only the even integers in [~4 ~3 ~2 ~1 0 1 2 3] is returned. Try replaying IsEven by IsOdd, IsNumber or IsNat (testing for natural numbers) to better understand this filtering.
(BTW: there is a bug in IsOdd concerning negative numbers)
{Browse {Filter [~4 ~3 ~2 ~1 0 1 2 3] IsEven}}
The procedure ForAll applies a given procedure to any element of a list. In this section, the procedure Browse is applied to every list element.
{ForAll [a b c d e f] Browse}
The function Map expects a list and a unary function (i.e. a function expecting a single value) as arguments. It applies the function to every list element, and returns the collected results in a list.
The section defines and uses the function square in order to square all numbers in the list. You may want to change this function to understand that any function can be given to a higher-order function as an argument. For example, replace Square by a function Double, which doubles its argument.
local fun {Square X} X * X end in {Browse {Map [1 2 3 4 5 6] Square}} end
Zip applies a procedure to elements from two lists. The lists must have the same size.
local proc {Max X Y Z} if X >= Y then Z = X else Z = Y end end A = [1 2 3 4 5] B = [5 4 3 2 1] in {Browse {List.zip A B Max}} end
Sometimes we need a function only once — as the function Square in the previous section. In such cases we don't necessarily need to care about giving the function any name. Instead, we can define an anonymous function.
This section restates the previous section by defining the Square function 'inline' without giving it any name. In an anonymous function definition, the variable which names the function is replaced by $ (dollar sign).
{Browse
{Map [1 2 3 4 5 6] fun {$ X} X * X end}}
The function Sort expects a list and a binary function (i.e. a function expecting two values) as arguments. This binary function compares two values, and Sort sorts the list values according to this comparison. For example, the function in the section compares two numbers and returns true if the first number is smaller. Consequently, this section sorts the list elements in ascending order. You may want to replace the < by > in the function definition to sort the numbers in decreasing order.
{Browse
{Sort [1 5 3 2 0 7]
fun {$ X Y} X < Y end}}
You can actually sort the list elements in any way you want using the Sort function. For example, you may place all even numbers at the beginning and all odd numbers at the end of the list and sort all even and odd numbers in ascending order. This is done in the second (commented) Sort call. How does this sorting work?
{Browse
{Sort
[1 5 3 2 0 7]
fun {$ X Y}
if {IsEven X} then
if {IsEven Y} then X < Y
else true
end
else
if {IsOdd Y} then X < Y
else false
end
end
end}}
Higher order procedures are defined like any other procedure: some arguments are simply procedures — which are then usually applied in the definition. This section defines a higher-order function Find which expects a list Xs and a test function Fn: Find returns the first element in Xs for which Fn returns true.
This section also demonstrates the pattern-matching case statement with multiple clauses operating on the list Xs. In case Xs is the empty list nil, then Find returns nil. Otherwise (multiple clauses are separated with the keyword []), Xs is matched with X|Xr, where X is bound to the first element of Xs and Xr to the list's tail or rest. The function Find then checks whether {Fn X} returns true. In that case, the searched for list element has been found and is returned. Otherwise, Find is called recursively with the rest of the list.
local fun {Find Xs Fn} case Xs of nil then nil [] X|Xr then if {Fn X} then X else {Find Xr Fn} end end end in {Browse {Find [1 2 3 4 5 6] IsEven}} end
Terms: first-class value, first-class function/procedure, higher-order function/procedure.
A first-class value is a value (also object, or citizen) which can be stored in data structures, given to procedures as arguments and returned as results. Functions which are first-class values are also called first-class functions.
First-class functions are a central concept of functional programming. They allow for higher-order programming, which make procedures more general and in effect can greatly reduce the length of a program. For example, instead of defining a sort function for every kind of data you need to sort (e.g., numbers, strings, score objects) you only define a single sort function and specify how it compares values.
Reading:
The operator = performs unification of two variables. The variables share all the information they have about their values. A variable without a name (an anonymous variable) is written as an underscore ( _ ).
Unification shares information between two variables, including the domain of possible values. This example introduces finite domain integers (FD), discussed below in more detail.
local X = {FD.int 1#5} % declare an integer with domain {1, ..., 5} Y = {FD.int 0#3} in X = Y % unify X and Y {Inspect X} % X now has the domain {1, ..., 3} end
Compound data structures such as lists may contain free variables. Such lists are then partially bound and they can be unified.
local X = [a _ _] Y = [_ b _] in X = Y % unify X and Y {Inspect X} end
Unification also works recursively. The Inspector and Browser windows show two different ways for representing this.
The Inspector can be configured to show either way: under the options menu, structure tab, below representation, select between tree and relation mode.
local X = unit(x:X) in {Browse X} {Inspect X} end
Terms: logic variables, unification.
Unification is the core operation of logic programming (besides search). Variables which allow for unification are therefore also called "logic variables". Unification is also the first constraint we meet. Constraint programming is discussed further below.
Reading:
Oz supports object-oriented programming (OOP). This programming paradigm introduces the notion of objects. Objects encapsulate internal data and understand methods (or messages) which somehow process this internal data. Different 'kinds' of objects are defined by defining classes: objects are class instances. A class specifies what data are contained in its instances and what methods these instances understand. A method is effectively a procedure which is defined for instances of specific classes only.
The following section creates a graphical user interface button. You do not need to understand the code which creates the window itself (i.e., the call to QTk.build). For our purposes here, only this single line is important:
{Window show}
`Window' is an object, and `show' is the name of the method understood by this object. This method results in showing the window with the button.
Please note that the syntax of a method differs clearly from the procedure syntax shown before. If `show' was a procedure, then we would write:
{Show Window}
Internally, objects are actually procedures which expect a single argument — hence this syntax. When the object is sent a message (i.e. the procedure is called with a specific argument) it processes the message according to its definition.
local Window = {QTk.build lr(button(text:"Hello world!" action:toplevel#close))} in {Window show} end
Class methods are actually records which can contain method arguments. For example, the following statement sends the following message to the object Window. This changes the width of the border around the button and sets the background of this border to the color blue.
{Window set(borderwidth:1.0#c background:blue)}
In general, the record denoting a message can wrap multiple arguments, as in the following example where the method myMethod with multiple arguments is send to the class MyObject.
{MyObject myMethod(Arg1 Arg2 ...)}
We will later see many more method application sections in the context of Strasheela's music representation.
local Window = {QTk.build lr(button(text:"Hello world!" action:toplevel#close))} in {Window show} %% change to button background color after 1000 msec {Delay 1000} {Window set(borderwidth:1.0#c background:blue)} end
Oz provides a special construct for marking return values. This construct is the nesting marker which is notated $ (dollar sign). In a previous example (repeated below), the nesting marker was used for defining an anonymous function. In this case, $ returns the function value itself.
{Map [1 2 3 4 5 6] fun {$ X} X * X end}
More generally, the nesting marker transforms any statement into an expression. For example, method calls are statements by default — they return nothing. The nesting marker can turn methods into expressions. Using the nesting marker can make code more concise. Instead of writing
local X in {Obj get(X)} {Browse X} end
we can write
{Browse {Obj get($)}}
The following example creates a text entry widget. Whenever you edit the widget text, it is (re-)browsed. Again it is not important to understand the full example; just note the code segment which does the browsing (see below). Entry is the entry widget object, and the method get(X) binds its argument X to the present widget text (as string).
{Browse {String.toAtom {Entry get($)}}}
local Entry Window = {QTk.build lr(entry(init:"Change this text..." handle:Entry action:proc{$} {Browse {String.toAtom {Entry get($)}}} end))} in {Window show} end
This example defines a simple counter class. It stores internally a counter value in its attribute i. This value is accessed with the method get, and the method incr raises the counter value by one. Every class defines an initialisation method: the method init expects the initial counter value as argument. Note that the syntax for accessing and overwriting attribute values is very similar the the syntax of cells (see above). In fact, object attributes are also stateful data, like cells.
The example then creates a counter object (MyCounter) with the function New, which expects a class and an initialisation method. The rest of the example uses this object. Its initial counter value 3 is first browsed. The object is then incremented (so the counter becomes 4), and then its value is browsed again. Note the use of the nesting marking for returning the counter value.
local class Counter attr i % define attribute i meth init(I) i := I end % bind i to arg I meth get(I) I=@i end % return i meth incr i := @i+1 end % increment i by one end MyCounter = {New Counter init(3)} in {Browse {MyCounter get($)}} {MyCounter incr} {Browse {MyCounter get($)}} end
Terms: class, object (class instance), method
Strasheela's music representation makes extensive use of object-oriented programming. Even basic Strasheela programs commonly require writing method calls. Extending Strasheela often means writing new Strasheela classes.
Nevertheless, object-oriented programming is a complex programming paradigm. This section therefore presented only the very basics of this paradigm. For more details, please refer to other Oz documentation:
Reading:
Please note that object-oriented programming is often used as a stateful programming paradigm: methods often change the internal state of objects (cf. the counter example above). By constrast, most methods in Strasheela are stateless which is important in the context of constraint programming. The Strasheela music representation is introduced later in this tutorial.
Oz provides excellent support for concurrent programming, where computations run in parallel in multiple threads. We will only touch on this subject and discuss aspects relevant for Strasheela. In general, however, concurrent programming plays a major role in Oz programming.
The computations in different threads can communicate with each other via variables. Multiple threads can use the same variable in a computation. If the value of a variable does not present enough information for performing a specific operation, then the thread simply blocks and waits for more information. As soon as more information about the variable value is available, the thread resumes its execution. This approach makes concurrent programs highly declarative and thus easy to write and understand.
The downside of this concurrency model is that it can result in an unintended blocking of a program which is not explicitly signalled (e.g. no error message is shown when a program blocks, because this is a normal program behaviour). There are a few pragmatic tricks we can use to avoid this downside; these are covered later in this chapter.
This section demonstrates concurrent programming, but does not show a typical application (a typical application would be a program split in a server and one or more clients). In the context of Strasheela, we will seldomly write concurrent programs explicitly. Nevertheless, it is very important to know how concurrent programming works in Oz. Even if we are not explicitly writing a concurrent program, constraint programming in Oz always results in a concurrent program. Concurrent programming forms one of the foundations of Oz' constraint programming model, where each constraint (i.e. each propagator) is a concurrent agent running in its own thread.
Variables may be used to communicate information between different parts of a program — even if the information is not available yet. Browse can handle unknown information, but other parts of the program may wait (i.e. block) until the information is available.
Here, `IsEven' binds the variable B. Please note the order of computations in this section:
However, `Browse' does indeed show the correct value of B. WARNING: not all procedures can handle unknown information.
local B in {Browse B} {Delay 3000} {IsEven 4 B} end
Variables may also be used to communicate between different threads. This example declares X and then browses 'hello' (just to show that the browser works in principle). However, the addition X+3 cannot be executed immediately and blocks. Because this computation is executed in its own thread, the top-level thread continues regardless, and calls the procedure Delay, which waits for 3000 msec. After that time, the top-level thread determines X to 4. This awakes the other thread: it can now compute X+3 and browse the sum.
In the section below, the addition X+3 cannot be performed as long as the value of X is unknown.
local X in {Browse hello} thread {Browse X + 3} end % compute and browse X+3 concurrently {Delay 3000} X = 4 end
This section demonstrates a buggy program which does not signal any error but simply does nothing. The section is very similar to the previous section, but does not place the blocking X+3 in its own thread. As a result, the whole program blocks at that point and never executes X = 4.
local X in {Browse hello} %% !! blocks {Browse X+3} X = 4 end
This section demonstrates a pragmatic approach which checks for blocking programs. The section ends with the statement {Browse endOfProgram}. A non-blocking program will always execute this last line of code and show 'endOfProgram' in the Browser. However, a blocking program (as the present one) does not do that and thus indicates that it is blocking. Although this little trick does not tell us where the program blocks, the information that we wrote a blocking program can prove very helpful already. You may get a feel for this trick by changing the section so that the message 'endOfProgram' is shown (e.g. comment the blocking statement out, or surrounding it with a 'thread .. end' statement).
Of course, this technique is most effective for programs which should complete immediately. By contrast, if we call procedures like Delay in a program (see above), the browsing of 'endOfProgram' will also be delayed accordingly.
local X in {Browse hello} %% !! blocks {Browse X+3} X = 4 end {Browse endOfProgram}
This section demonstrates a technique which causes an error (raises an exception) when the current thread blocks. The function `Thread.this' returns the current thread, and `Debug.setRaiseOnBlock' activates this debugging feature. The error message can even tell you which variable caused the blocking (although in this section the deduced variable name is simply _).
Note that you must load Debug first, before using `Debug.setRaiseOnBlock' (which this tutorial does implicitly). For example, include the following line at the beginning of your program.
declare [Debug] = {Module.link ['x-oz://boot/Debug']}
local X in {Debug.setRaiseOnBlock {Thread.this} true} %% !! blocks {Browse X+3} X = 4 end