Dr. Sabah Mohammed,
Department of Computer Science, ATAC 5013, Tel: 3438777 Email: sabah.mohammed@lakeheadu.ca
(1) You can install EMACS, XEMACS or AQAMACS Windows Example: Emacs-23-CvsP090226-EmacsW32-1.58.exe From: http://ourcomments.org/Emacs/EmacsW32.html#download Or http://www.gnu.org/software/emacs/ Mac Example: http://aquamacs.org/download.shtml (2) You need to change your Environment Variable: Example: In Windows XP, right-click on \My Computer", go to \Properties", \Advanced". Click on \Environment Variables". Click on \New" and add a variable with the name \OZEMACS" and the value \c:\Program Files\XEmacs\XEmacs-21.4.6\i586-pc-win32\xemacs.exe", both without the quotation marks. Then \OK" all those windows, and try \Start"!\All Programs"!\Mozart"!\Oz Programming Interface" again.
Declarative programming is a programming paradigm that expresses the logic of a computation without describing its control flow. Declarative programming is often defined as any style of programming that is not imperative A program that describes what computation should be performed and not how to compute it.
Any programming language that lacks side effects (or more specifically, is referentially transparent) A language with a clear correspondence to mathematical logic. Declarative programming is an umbrella term that includes a number of better-known programming paradigms (i.e. Functional + Logic Programming).
Referential transparency means that an expression (such as a function call) can be replaced with its value; this requires that the expression has no side effects and is pure (always returns the same results on the same input). However, the presence of side-effects can make it harder to reason about a program, because there is invisible state to the side of computations which changes. That means a reader/debugger needs to keep track of both the visible aspects of a program and the hidden values off to the side that may change. Easy Solution: Assigning a value to a variable must be done once! {Use immutable Variables!}
1
http://www.mozartoz.org/home/doc/tutorial/index.html
In order to execute fragment, we position the point on the line we just typed and select Feed Line/Region /Buffer from the Oz menu in the menubar. If your OZ program is only accepted without showing the output then you need to go to the OZ menue again and click on the Show/Hide -> Emulator.
Browse: opens a separate Browse window Show: outputs text to standard out (i.e. the command-line) which can be on the same OZ main Window Inspect: opens a separate Inspect window for other purposes…
Oz is a small but expressive language. To start with we will consider:
◦ ◦ ◦ ◦ ◦ ◦ Variables Basic types: • Lists, Records, numbers, atoms, tuples. Scoping Pattern matching Functions and Procedures….
After that we will study what is meant by a Declarative Program….
A variable (identifier) is a name that starts with an upper case letter or a text within back quote characters: Variables must be declared:
◦ declare X ◦ X, Y, Max, DeleteMin, …`a Rather LONG Name`
Use the system as a calculator
The Results will appear in a new window showing 99980001.
> {Browse 9999*9999}
This creates the variable. Variables can be bound to values. ‘Bound' means ‘identical' in the mathematical sense.
◦ Can only be bound once(!). They represent immutable variables (also known as stateless variables) to prevent side effects, ◦ X = 68
~ is unary minus
Later on also variables that can be assigned many times (mutable variables). OZ call them Cells.
2
declare V = 9999*9999 {Browse V*V} This will show: 9996000599960001 Remember when you declare Variables in this way they are are just short-cuts for values. That is, they cannot be assigned more than once. But what if you declared another variable with the same name as a previous one and gave it a different value? This means that the old one is no longer accessible.
%P1
declare X = 21 X = 22 % raise an error X = 21 % do nothing declare X = 22 % from now on, X will be bound to 22
Variable identifiers: is what you type Store variable: is part of the memory system The declare statement creates a new store variable and makes the variable identifier refer to it. Oz variables are single-assignment variables or more appropriately logic variables. In imperative languages like C and Java, a variable can be assigned multiple times. In contrast, single assignment variables can be assigned only once.
A single assignment variable has a number of phases in its lifetime. Initially it is introduced with unknown value, and later it might be assigned a value, in which case the variable becomes bound. Once a variable is bound, it cannot itself be changed. A logic variable is a single assignment variable that can also be equated with another variable.
It is important to restrict the way you declar variables to the scope that uses these variables. Two Ways to declare variables respecting the scope:
◦ local X Y Z in S end ◦ declare X Y Z in S
will introduce three variables X, Y, Z and execute the statement S in the scope of these variables.
3
A data type is a set of values and a set of associated operations Example: Int is the the data type ”Integer”, i.e set of all integer values 1 is of type Int Int has a set of operations including +,-,*,div, etc The model comes with a set of basic types Programs can define other types, e.g., abstract data types ADT
Value
Number
Record Tuple
Procedure
Int
Float Literal List Boolean String true false
Char Atom
Any variable, if it ever gets a value, will be bound to a value of one of these types. The language is dynamically-typed in the sense that when a variable is introduced, its type as well as its value are unknown. Only when the variable is bound to an Oz value, does its type become determined.
4
The following program, introduces three variables I,F and C. It assigns I an integer, F a float, and C the character t in this order. It then displays the list consisting of I,F, and C.
local I F C in I=5 F = 5.5 C = &t {Browse [I F C]} end
Oz supports binary, octal, decimal and hexadecimal notation for integers, which can be arbitrary large. An octal starts with a leading 0, and a hexadecimal starts with a leading 0x or 0X. Floats are different from integers and must have decimal points. Other examples of floats are shown where ~ is unary minus: ~3.141 4.5E3 ~12.0e~2 Characters are a subtype of integers in the range of 0, ..., 255. The standard ISO 8859-1 coding is used (not Unicode). Printable characters have external representation, e.g. &0 is actually the integer 48, and &a is 97. Some control characters have also a representation e.g. &\n is a new line. All characters can be written as &\ ooo, where o is an octal digit.
Literals are divided into atoms and names. An Atom is symbolic entity that has an identity made up of a sequence of alphanumeric characters starting with a lower case letter, or arbitrary printable characters enclosed in quotes. For example: a foo '=' ':=' 'OZ 3.0' 'Hello World' Atoms have an ordering based on lexicographic ordering. Another category of elementary entities is Name. The only way to create a name is by calling the procedure {NewName X} where X is assigned a new name that is guaranteed to be worldwide unique. Names cannot be forged or printed. A subtype of Name is Bool, which consists of two names protected from being redefined by having the reserved keywords true and false. Thus a user program cannot redefine them, and mess up all programs relying on their definition. There is also the type Unit that consists of the single name unit. This is used as synchronization token in many concurrent programs. local X Y B in X = foo {NewName Y} B = true {Browse [X Y B]} end
Tuples and their Operations
A tuple consists of a label and values. Actually, a tuple is a record which has only integer features in ascending order. These features can be omitted.
5
Suppose you defined the Binary tree as: tree(K,D, LT,RT) Then how do you declare the following tree?
Practice Exercises: Using the same representation of a binary tree: 1. Insert new data element at the tree 2. Delete a data element from the tree
Home Exercises Do the other types of tree traversals (Postorder and Inorder).
6
a list of the first three positive integers is represented as:
◦ 1|2|3|nil ◦ [1 2 3]
Another convenient special notation for a closed list , i. e. a list with a determined number of elements is:
The above notation is used only for closed list, so a list whose first two elements are 1 and 2, but whose tail is the variable X looks like:
1|2|X
{Inspect {Inspect {Inspect {Inspect
[a [a [a [a
b b b b
c] == a|b|c|nil} True c] == '|'(a '|'(b '|'(c nil)))} c].1} a c].2} [b c]
True
local Xs = [1 2 3 4] in case Xs of H | T then {Inspect H} {Inspect T} end end
Functions over Lists
7
Suppose you defined a function like Max: fun {Max X Y} if X>Y then X else Y end end fun {MaxOfThree X Y Z} {Max {Max X Y} Z} end You can of course also write it like this: fun {MaxOfThree X Y Z} {Max X {Max Y Z}} end Test as follows: {Browse {MaxOfThree 3 23 9}}
Recursion simply means applying a function as a part of the definition of that same function. The key to making this work is that there must be a terminating condition such that the function branches to a non-recursive solution at some point. The area where recursion is very useful is in processing lists. Provided we can test for an empty list, and generate a list minus its first element we can use recursion easily. Recursion is often, but not always, memory hungry.
Let us do a more involved calculation. Assume we want to calculate the factorial function n!, which is defined as
1 × 2×· · ·×(n − 1) × n. This gives the number of permutations of n items, that is, the number of different ways these items can be put in a row. Factorial of 10 is:
{Browse 1*2*3*4*5*6*7*8*9*10} This displays 3628800. What if we want to calculate the factorial of 100?
◦ ◦ ◦ ◦
declare fun {Fact N} if N==0 then 1 else N*{Fact N-1} end end
Functions are first class values, allowing higher order functional programming The keyword declare says we want to define something new. The keyword fun starts a new function. The function is called Fact and has one argument N. The argument is a local variable, i.e., it is known only inside the function body. Each time we call the function a new variable is declared. Trace it.
factorial 3 3 * factorial 2 3 * 2 * factorial 1 3 * 2 * 1 * factorial 0 3*2*1*1 3*2*1 3*2 6
8
BTW: Fact is a Recursive Function:
◦ Try: ◦ {Browse {Fact 10}} ◦ This should display 3628800
Now Try {Browse {Fact 100}} This will produce:
933 26215 44394 41526 81699 23885 62667 00490 71596 82643 81621 46859 29638 95217 59999 32299 15608 94146 39761 56518 28625 36979 20827 22375 82511 85210 91686 40000 00000 00000 00000 00000 Effective Recursive Functions: A Later Issue? Tail Recursion !!!!
Say we want to calculate with lots of integers. For example, we would like to calculate Pascal’s triangle: Each element is the sum of two other elements: the ones above it and just to the left and right. (If there is no element, like on the edges, then zero is taken.) We would like to define one function that calculates the whole nth row in one swoop. The nth row has n integers in it. We can do it by using lists of integers.
[1 3 3 1] We shift this row left and right and then add them together: [1 3 3 1 0] + [0 1 3 3 1] Note that shifting left adds a zero to the right and shifting right adds a zero to the left. Doing the addition gives: [1 4 6 4 1] which is the fifth row
declare Pascal AddList ShiftLeft ShiftRight fun {Pascal N} if N==1 then [1] else {AddList {ShiftLeft {Pascal N-1}} {ShiftRight {Pascal N-1}}} end end
fun {ShiftLeft L} case L of H|T then H|{ShiftLeft T} else [0] end end fun {ShiftRight L} 0|L end
9
fun {AddList L1 L2} case L1 of H1|T1 then case L2 of H2|T2 then H1+H2|{AddList T1 T2} end else nil end end
fun {Length Xs} case Xs of nil then 0 [] _|Xs1 then 1+{Length Xs1} end end
declare % Return the length of the argument list fun {ListLength L} case L of _|T then 1 + {ListLength T} else 0 end end
declare fun {Append Xs Ys} case Xs of nil then Ys [] X|Xs1 then X|{Append Xs1 Ys} end end {Browse {Append [a b] [c d]}}
declare fun {Reverse Xs} case Xs of nil then nil [] X|Xs1 then {Append {Reverse Xs1} [X]} end end
10
tree(a tree(b nil tree(c nil nil)) tree(d nil nil) )
The size of a tree is given by the number of the elements that it contains. The size of the above tree is 4. A simple definition is as follows: An empty tree has the size 0. A nonempty tree has the size 1 plus the size of its left subtree plus the size of its right subtree.
fun {Size T} case T of nil then 0 [] tree(_ LT RT) then 1 + {Size LT} + {Size RT} end end
{Browse {Size tree(a tree(b nil tree(c nil nil)) tree(d nil nil)) }}
Write a function Depth for measuring the depth of a binary tree, represented as above. The depth of the above tree is 3. fun {Depth T} case T of nil then 0 [] tree(_ LT RT) then 1 + {Max {Depth LT} {Depth RT}} end end
{Browse {Depth tree(a tree(b nil tree(c nil nil)) tree(d nil nil)) }}
11 