This is an obsolete, archived page. See the Orc documentation for current information.

Introduction#

We saw in part 1.3.1.2 of the user guide how we can declare a site and use an already defined site in Orc. These sites are implemented in the host language (e.g. Java) and the keyword site enables us to import these sites into Orc and use them. They represent a service, which has state and encapsulates data and can have separate thread of control. So far, we know how to use sites that are implemented in the host language. Now, we want to see how we can define a site in the Orc language. Orc classes provide a means to achieve this. A class has the following properties:
  1. Encapsulation: Just like objects in an object-oriented language, classes also provide the encapsulation facility for the programmer. The data defined inside the class can only be accessed and modified through methods defined in class. Therefore, it hides the representation of the data and implementation of functions and methods which work on the data and manage the state.
  2. Methods instead of functions: These are the gateways to access and manipulate the data represented by class. They also enable the user of the class to access the service provided by that. Unlike functions in Orc, methods defined in a class can only publish one value.
  3. Termination protection: The execution of a class and its methods are protected from termination of the rest of the program. In other words, the execution of class cannot be interrupted. In the pruning combinator as soon as the right hand side expression publishes a value, all the on going executions in the right hand side will be terminated. However, if there is any call to a class in the right hand side, that call will proceed until completion. For example, in the following Orc expression, suppose that c is a class.
    y <y< g() | c()
    If g() publishes a value before c() does, the execution of c() will continue. Although, the published value of c() (if any) will never be used. On the other hand, if c() publishes a value first, then the execution of g() will be interrupted since its execution is not protected. This property of classes is very important to prevent the data corruption and invalid state of an object. We will see using an example the significance of this property in the next section.
  4. Strict calls: unlike calls to ordinary function definitions in Orc, calls to class methods are strict. This means that the call will not happen unless all the parameters are bound.

In addition to defining new arbitrary sites, we can also extends the functionality of already defined sites such as Buffer, Array, etc. We are going to see examples of both in the following sections.

Significance of classes#

Before we proceed to see the syntax and usage of classes, let us motivate the significance of classes by using a simple example. Suppose we want to have a sequence number generator. The normal way to do this in a functional language is to define a mutable integer variable and a function to increase and return the sequence number. The following shows the code for this sequence number generator in Orc:
-- the mutable integer defined with seed zero
val seq_num = Ref(0)
-- gen_seq will increase the seq_num and return the new value
def gen_seq() =
  seq_num := seq_num?+1 >> seq_num?
  
gen_seq() >s> println(s) >> gen_seq() >s> println(s) >> stop
The seq_num is a mutable integer variable that gets updated by the gen_seq function. This program will output:
1
2
What is the problem with the above code? The first problem is that the seq_num is exposed to all the expressions which come after it. This means that all those expressions can possibly read and write the value of seq_num. This is not always desirable and makes the reasoning about the program more difficult. The second issue with this code is that it is not flexible enough. What if we want to have different sequence number generator with a different initial seed? For example, we may want a sequence number starting at 0 and another one starting at 1000.

There is another issue associated with the above code from a concurrent programming viewpoint. It is not thread safe. This means that if we make two parallel calls to gen_seq(), we may get the same result. For example, the following piece of code:

gen_seq() | gen_seq()
can generate the following output:
1
1
and in most of the runs, it will. This is a famous phenomenon in parallel programming known as race condition. In fact, access to the shared variable seq_num is subject to race condition between the two threads running the two calls to gen_seq(). To solve the race issue we need to add a semaphore to the above code in order to regulate the access to the shared variable, seq_num. Therefore, every call to gen_seq needs to acquire the semaphore in order to update the variable and release the semaphore at the end. The new safe code is as follows:
-- the mutable integer defined with seed zero
val seq_num = Ref(0)
-- a semaphore to regulate access to shared variable seq_num
val seq_num_sem = Semaphore(1)
-- gen_seq will increase the seq_num and return the new value
def gen_seq() =
  seq_num_sem.acquire() >> seq_num := seq_num?+1 >> 
  seq_num? >x> seq_num_sem.release() >> x
  
gen_seq() | gen_seq()
This guarantees that we will not end up with the same value from the two calls. The output of the above code is:
1
2
Because of the non-deterministic nature of parallel execution, the output of the above program can also be 2 followed by 1. The above code, besides the issue of encapsulation and the complexity of having more than one sequence number generator, looks fine. However, there is a subtle problem with this code. The problem is data corruption and invalid state which can be caused by abrupt termination of the call to gen_seq(). Consider the following piece of code:
y <y< 1+1 | gen_seq()
Now, suppose the following scenario of the execution:
1- 1+1
2- seq_num_sem.acquire()
3- y is bound to 2
4- terminate gen_seq()
As illustrated in the above execution sequence, the semaphore seq_num_sem got acquired but never released because of abrupt termination. Therefore consecutive calls to gen_seq will never proceed because they cannot acquire the semaphore. So, we need to somehow protect the execution of gen_seq. Classes address all the above issues in a succinct way. In the next part we are going to see how we can use them.

Class usage#

Defining a class is very similar to defining a normal function. The following shows the syntax for defining a class.
D::=                             Declaration  	 
  val P = E                      Value Declaration
  | def X( P , ... , P ) = E       
CP::=                            Class Declaration
  def class C( P , ... , P ) = 
    (D | CP)* 
    def X( P , ... , P ) = E
    E                            Goal Expression
It is required for the class to have at least one internal definition. It can have zero or more value declaration. The role of the goal expression is to do the necessary initialization for the class. It is analogous to constructors in the object oriented languages. Note that the goal expression merely initialize and construct the class. No value is published from goal expression. In fact, any value published from the goal expression is suppressed from publication. All the functions and classes defined inside a class are accessible from outside the class and can be called (They are considered public as in object oriented languages). However, no val declaration is accessible from outside the class. (They are considered private as in object oriented languages). The internal definitions of the class can be called by specifying their name and list of parameters after the name of the class instance followed by a dot. Here is the syntax for calls to the class.
class_instance.X( V, ..., V )

Example#

As an example of the class definition we write a class for the simple version of the sequence number generator that we explained in the previous part.
def class gen_seq(init) =
  -- the mutable integer defined with seed init
  val seq_num = Ref(init)
  -- the next function will increase the seq_num and return the new value
  def next() =
    seq_num := seq_num?+1 >> seq_num?
  signal
As can be seen in this code, the seq_num is encapsulated inside the class. No other expression except the expressions and definitions inside the class can access that. Every time the method next is called, it increases the current sequence number and returns it. The goal expression for this class is signal. Since no initialization is required, it does not do anything.

Class Instantiation and Application#

A class can be instantiated by a variable declaration. For example, the following piece of code will create a sequence number generator with the initial seed of 1000.
val g = gen_seq(1000)
g is a handle to the sequence number generator class with initial seed 1000. In order to call this class we simply write the name of the handle to class instance followed by a dot and the name of the internal function definition (next in this example). So, to get the next sequence number we write:
g.next()
As a complete example see the following code:
def class gen_seq(init) =
  -- the mutable integer defined with seed init
  val seq_num = Ref(init)
  -- the next function will increase the seq_num and return the new value
  def next() =
    seq_num := seq_num?+1 >> seq_num?
  signal

val g = gen_seq(1000)

g.next() >y> println(y) >> g.next() >y> println(y) >> stop
The above example will generate the following output:
1001
1002

It is very easy to instantiate a new sequence number that starts with a different seed. We just need to create a new instance of gen_seq with a different seed. The following code shows an example of creating two sequence number generator with two different seeds.

val g0 = gen_seq(0)
val g1 = gen_seq(1000)

g0.next() >y> println(y) >> g1.next() >y> println(y) >> stop
The output of the above code is:
1
1001
Notice how easy it is to have a new sequence number generator. Whereas, in a pure functional language where we just have functions we need to declare new declarations of seq_num to accomplish the job.

Now, in order to solve the issue of thread safety, we want to add a semaphore to the class. Note that since the execution of the class is protected we will not run into the problem of invalid state or data corruption caused by abrupt termination. The following code shows the thread safe version of the sequence number generator.

def class gen_seq(init) =
  -- the mutable integer defined with seed init
  val seq_num = Ref(init)
  -- a semaphore to regulate access to shared variable seq_num
  val seq_num_sem = Semaphore(1)
  -- gen_seq will increase the seq_num and return the new value
  def next() =
    seq_num_sem.acquire() >> seq_num := seq_num?+1 >>
    seq_num? >x> seq_num_sem.release() >> x
  signal
seq_num_sem is encapsulated inside the class and is used inside the next function to make sure that race condition on the seq_num will not happen. The following piece of code uses the above safe sequence number generator. Although there are four parallel calls to the next function we will never get a repeated sequence number.
val g0 = gen_seq(0)

g0.next() | g0.next() | g0.next() | g0.next()
The output of the above program would not contain any duplicate value in any run. The output is:
1
2
3
4

Active nature of classes#

Class is an active entity. Active objects, unlike passive ones, have their own thread of control. They can initiate a computation without receiving a method call (in procedural languages) or a message (in languages with message passing model). Note that this definition of active objects subsumes reactive objects and actors. We said that the execution of class is protected from the rest of the program. Here we want to clarify what do we mean by creation of the class and when the class actually exists.

A class exists as soon as all the parameters and free variables in the class are bound to their values. Thereafter, any method on the class can be called. This means that the creation process would not wait for goal expression of the class to finish. Therefore, the creation of the class would return immediately. But the goal expression continues to execute. The goal expression will not publish anything. However, it can have side effects. For example, it could print something on the screen or it can initiate some other processes and send and receive data to and/or from buffers.

The following example explains the notion of activeness of classes. We want to design a clock that ticks every n (user specified) milliseconds. We want to be able to get the number of ticks passed since the process started. The following example shows a class implementation of this clock.

def class nclock(n) = -- tick every n milliseconds
  -- tick_cnt counts the number of ticks
  val tick_cnt = Ref(0)
  -- getTick returns the number of ticks passed so far
  def getTick() = tick_cnt?
  metronome(n) >> tick_cnt:=tick_cnt?+1

val ticker = nclock(250)
-- prints a mutiple of 4 every one second
Rtimer(1000) >> metronome(1000) >> ticker.getTick()
In this example, the class nclock has a tick counter tick_cnt that records the number of ticks passed so far. The method getTick returns the number of ticks. The interesting point about this class is its goal expression. The goal expression is a metronome that publish a signal every n milliseconds. Each time a signal is issued it causes the tick_cnt to increase by one. As can be seen, the goal expression would never stop. It keeps increasing the tick counter for ever and a thread is always active in the nclock class instance. This program keeps publishing the multiples of 4 starting from 4 upward.
4
8
12
16
20
...

Class clauses#

We have already seen the clausal definition of functions. Similar to function clauses we can have class clauses which gives us a powerful tool to create different forms of the same class. We need to put the class modifier for every clause definition. The syntax for class clauses is as follows:
def class cap_name(P, ..., P) = Class Body
...
def class cap_name(P, ..., P) = Class Body
Note that we still need at least one function or class definition inside the Class Body.

Here is an example of the clausal definition of class. It is a linear-time version of Fibonacci series. In this version the class H(n) memoizes the pair of the Fibonacci number n and n+1.

{- Helper class H to find the pair (Fibonacci(0), Fibonacci(1)) -}
def class H(0) =
  def pair() = (0,1)
  def fib() = 0
  stop
{- Helper class H to find the pair (Fibonacci(n), Fibonacci(n+1)) -}
def class H(n) =
  -- value of the previous pair
  val hn_1 = H(n-1)
  -- the pair for the current number n, (Fibonacci(n), Fibonacci(n+1))
  def pair() = hn_1.pair() >(x, y)> (y,x+y)
  -- the Fibonacci number for n 
  def fib() = pair() >(x, y)> x
  stop
  
def fib(n) =
  if (n < 0) then 0
  else (
    val h = H(n)
    h.fib()
  )
-- computing the Fibonacci numbers from 0 to 9
upto(10) >n> println(n+":"+fib(n)) >> stop
The output of the above program is:
0:0
1:1
2:1
3:2
4:3
5:5
6:8
7:13
8:21
9:34

Another example of using class clauses is to define recursive data structures. This simple example shows a Balanced Binary Tree. The class BBTree creates a balanced binary tree of height n. It has two functions; read and write. The function read accepts a list as the argument. This list represent a path to a node from which we would like to read the value. A zero in this list means the left child and a one indicates the right child. An empty list means we arrived at the desired node. The write function accepts a value to write into the node and the path (which is the same list we explained for read function) to the node. The following code is the Balanced Binary Tree in Orc written using classes.

def class BBTree(0) =
  def read(is) = stop
  def write(v,is) = stop
stop

def class BBTree(n) =
  val (root, left, right) = (Ref(), BBTree(n-1), BBTree(n-1))
 
  def write(v,[]) = root := v
  def write(v,i:is) =
    if i = 0 then left.write(v,is) else right.write(v,is)

  def read([]) =  root?
  def read(i:is) =
    if i = 0 then left.read(is) else right.read(is)

  stop

val store = BBTree(3)

store.write(7,[]) >> store.write(5,[0,1]) >>  store.read([0,1])
The output of the above program is
5

Add new attachment

Only authorized users are allowed to upload new attachments.
« This page (revision-51) was last changed on 06-Jan-2012 05:40 by John Thywissen