Expertiza_Wiki - User contributions [en]

CSC/ECE 517 Fall 2009/wiki3 9 rp

2009-11-18T08:17:34Z

7r3ad:

= The Non-Redundancy Principle =

In [http://se.ethz.ch/~meyer/ Bertrand Meyer's] [http://en.wikipedia.org/wiki/Object-Oriented_Software_Construction ''Object Oriented Software Construction''], he outlines many principles to increase reusability by managing complexity in software design. Some of these apply primarily to object oriented programming, primarily the principles dedicated to abstract data types. Most of the principles, however, apply to programming generally. The first five discussed in the book are often discussed in articles (the "Open-Close Principle" perhaps being the most popular), but equally important principles are discussed later in the book as well. One such principle, presented in the section on ''Contracting For Software Reliability'', is called The Non-Redundancy Principle.

== Definition ==

As with all principles presented in ''Object Oriented Software Construction'', the principle itself is quite terse:

<blockquote> Under no circumstances shall the body of a routine ever test for the routine's precondition. </blockquote>

As simple as this may seem on first blush, it has extensive implications.

Before we discuss the implications, it is proper to provide a bit of context regarding preconditions, postconditions and programming by contract.

== Context ==

Meyer outlined the notion of ''programming by contract'', which boils down to a methodology to enforce software modularity by clearly defining the relationships between various components, much in the same way relationships between individuals and/or companies are formalized in contracts.

In Chapter 11, Meyer indicates that for each party in the contract, the aspects of the contract include:

* Rights
* Obligations
* Preconditions
* Postconditions

In short, these indicate what is expected of the ''supplier'' and the ''client'' (terms describing the roles of objects that are party to the contract). Specifically, a ''precondition'' is a minimum criteria that must be satisfied on the part of the client for the contract to be valid. The heart of the Non-Redundancy Principle is ''who'' checks that the preconditions are satisfied, and ''when'' are those checks made.

It must be decided whether the client or the supplier of a service should enforce the preconditions. Once that is made clear, the software designer must decide when the precondition will be enforced, and once it is enforced, it should never be checked.

Meyer goes to some length to justify this position, which flies in the face of the defensive programming mantra, which generally encourages as much checking as possible, ostensibly to help eliminate errors "just in case". As we will see in the following sections, and as Meyer describes, it is difficult to justify this approach, purly on the grounds that such redundant checking inordinately increases the complexity of the software.

== Implications ==

There are a variety of implications that emerge from the Non-Redundancy Principle.

=== DRY Principle ===

A common mantra in programming is "Don't Repeat Yourself" or simply "DRY" for short. In it's simplest form, the Non-Redundancy Principle is a specialization of DRY, in that it prohibits developers from repeating themselves.

Consider the example that Meyer uses of a function responsible for returning a real positive square root of a number. In Java, such a function might look like:

/**
* Returns the postive real square root of the input, d.
*/
public double sqrt(double d) {
return Math.sqrt(d);
}

What happens if the number passed in is negative? Will the method return a real square root? We have specified in the supplier (in this case, the method called "sqrt") is obligated to return a positive real square root. By specifying a precondition that the input must be greater than or equal to zero, we now also qualify that obligation by imposing it only if the precondition is satisfied.

/**
* Returns the postive real square root of the input, d.
* Precondition: input d >= 0
*/
public double sqrt(double d) {
return Math.sqrt(d);
}

Now we have a precondition. But what does all this have to do with the Non-Redundancy Principle?

It might be tempting to then write this:

/**
* Returns the postive real square root of the input, d.
* Precondition: input d >= 0
*/
public double sqrt(double d) {
if (d < 0) throw new IllegalArgumentException("Input must be greater than or equal to zero.");
return Math.sqrt(d);
}

But, according to the Non-Redundancy Principle, this is prohibited! Why? Well, what does Math.sqrt do? Does it also check for a value less than zero? It turns out that it does. But the point here is that if we use the code directly above this paragraph, our system now checkes for numbers less than zero ''twice''. Not only have we repeated ourselves, but we have increased the complexity of the code, which brings us to how the Non-Redundancy Principle reduces code complexity.

=== Code Complexity ===

One way to measure code complexity is through [http://www.mccabe.com/iq_research_iqgloss.htm#cyclomatic cyclomatic complexity] (sometimes called the ''McCabe Number''). Simply put, cyclomatic complexity measures the number of different paths through a piece of code. It is often cited as a good measure of how maintainable a piece of code is, and certainly has an impact on how burdensome testing will be. In the example above:

public double sqrt(double d) {
if (d < 0) throw new IllegalArgumentException("Input must be greater than or equal to zero.");
return Math.sqrt(d);
}

We can immediately see that adding the check for the precondition to the method added an additional exit from the method, namely, the method can now throw an IllegalArgumentExecetion. Taken singly, this may not seem like a big deal, but imagine methods with two or more preconditions, and imagine every method in the system starts checking for each. On a systemic scale, redundant checking vastly increases the code bulk, complexity, and testing burden of the system.

=== Run-time versus Compile-time Errors ===

It may be tempting to look at systems that ''enforce'' preconditions to be in violation of the Non-Redundancy Principle. After all, in the way that Meyer describes design by contract, if the precondition for a method is violated, its behavior is undefined. But since ''Object Oriented Software Construction'' was written, new techniques have emerged to ensure that such preconditions are not violated, but they do so without ''checking'' for the precondition. Rather, they are codified statements of the precondition.

One such example can be seen in [http://jcp.org/en/jsr/detail?id=308 JSR 308] for Java. It specifies that Java annotations could be applied to types (in addition to classes and methods). Indeed, the code to support this has ben written, and is available in the form of the [http://types.cs.washington.edu/jsr308/ Checker Framework].

This type of annotation allows a developer to specify, using type annotations, that a certain precondition must be met. For example, we might want to specify that a particular reference should never be null, perhaps because we want to call a method on it:

/**
* Precondition: ref must be non-null.
*/
public Class(Object ref) {
ref.getClass();
}

In this case, if the precondition is violated, we get a RunTimeError (NullPointerException). If we instead using the checker framework, we can say the same thing, but in a way the compiler (and developers!) can understand:

public Class(@NonNull Object ref) {
ref.getClass();
}

In this case, if a value that might be null is passed in, the ''compiler'' will produce an error. Thus, this approach moves runtime errors to compile time. At first blush it may appear that the checker framework is "checking" for the precondition, but note that it doesn't carry any of the hallmarks Meyer discusses: it does not impact performance, it does not increase cyclomatic complexity, and it does not make the code any bulkier.

More and more modern languages this support of framework. For example, [http://www.scala-lang.org/ Scala] supports it through a [http://www.scala-lang.org/node/140 pluggable compiler architecture]. It is worth noting that such systems, rather than violating the Non-Redundancy Principle, in fact not only comply, but go one step further by, in many cases, eliminating the need for checks at all!

== Glossary ==

;Client
: A class that uses the features of another, its supplier, on the basis of the supplier's interface specification (contract)
;Contract
: The set of precies conditions that govern the relations between a supplier class and its clients. The contract for a class includes the individual contracts for the exported routines of the class, represented by preconditions and postconditions, and the global class properties, represented by the class invariant.
;Design By Contract
: A method of software construction that designs the components of the system so that they will cooperate on the basis of precisely defined contracts.
;Postcondition
: An assertion attached to a routine, which must be guaranteed by the routine's body on a return from any call to the routine if the precondition was satisfied on entry. Part of the contract governing the routine.
;Precondition
: An assertion attached to a routine, which must be guaranteed by every client prior to any call to the routine. Part of the contract governing the routine.
;Supplier
: A class that provides another, its client, with features to be used through an interface specification (contract).

CSC/ECE 517 Fall 2009/wiki3 9 rp

2009-11-18T07:38:40Z

7r3ad:

= The Non-Redundancy Principle =

In Bertrand Meyer's ''Object Oriented Software Construction'', he outlines many principles to increase reusability by managing complexity in software design. Some of these apply primarily to object oriented programming, primarily the principles dedicated to abstract data types. Most of the principles, however, apply to programming generally. The first five discussed in the book are often discussed in articles (the "Open-Close Principle" perhaps being the most popular), but equally important principles are discussed later in the book as well. One such principle, presented in the section on ''Contracting For Software Reliability'', is called The Non-Redundancy Principle.

== Definition ==

As with all principles presented in ''Object Oriented Software Construction'', the principle itself is quite terse:

<blockquote> Under no circumstances shall the body of a routine ever test for the routine's precondition. </blockquote>

As simple as this may seem on first blush, it has extensive implications.

Before we discuss the implications, it is proper to provide a bit of context regarding preconditions, postconditions and programming by contract.

== Context ==

Meyer outlined the notion of ''programming by contract'', which boils down to a methodology to enforce software modularity by clearly defining the relationships between various components, much in the same way relationships between individuals and/or companies are formalized in contracts.

In Chapter 11, Meyer indicates that for each party in the contract, the aspects of the contract include:

* Rights
* Obligations
* Preconditions
* Postconditions

In short, these indicate what is expected of the ''supplier'' and the ''client'' (terms describing the roles of objects that are party to the contract). Specifically, a ''precondition'' is a minimum criteria that must be satisfied on the part of the client for the contract to be valid. The heart of the Non-Redundancy Principle is ''who'' checks that the preconditions are satisfied, and ''when'' are those checks made.

It must be decided whether the client or the supplier of a service should enforce the preconditions. Once that is made clear, the software designer must decide when the precondition will be enforced, and once it is enforced, it should never be checked.

Meyer goes to some length to justify this position, which flies in the face of the defensive programming mantra, which generally encourages as much checking as possible, ostensibly to help eliminate errors "just in case". As we will see in the following sections, and as Meyer describes, it is difficult to justify this approach, purly on the grounds that such redundant checking inordinately increases the complexity of the software.

== Implications ==

There are a variety of implications that emerge from the Non-Redundancy Principle.

=== DRY Principle ===

A common mantra in programming is "Don't Repeat Yourself" or simply "DRY" for short. In it's simplest form, the Non-Redundancy Principle is a specialization of DRY, in that it prohibits developers from repeating themselves.

Consider the example that Meyer uses of a function responsible for returning a real positive square root of a number. In Java, such a function might look like:

/**
* Returns the postive real square root of the input, d.
*/
public double sqrt(double d) {
return Math.sqrt(d);
}

What happens if the number passed in is negative? Will the method return a real square root? We have specified in the supplier (in this case, the method called "sqrt") is obligated to return a positive real square root. By specifying a precondition that the input must be greater than or equal to zero, we now also qualify that obligation by imposing it only if the precondition is satisfied.

/**
* Returns the postive real square root of the input, d.
* Precondition: input d >= 0
*/
public double sqrt(double d) {
return Math.sqrt(d);
}

Now we have a precondition. But what does all this have to do with the Non-Redundancy Principle?

It might be tempting to then write this:

/**
* Returns the postive real square root of the input, d.
* Precondition: input d >= 0
*/
public double sqrt(double d) {
if (d < 0) throw new IllegalArgumentException("Input must be greater than or equal to zero.");
return Math.sqrt(d);
}

But, according to the Non-Redundancy Principle, this is prohibited! Why? Well, what does Math.sqrt do? Does it also check for a value less than zero? It turns out that it does. But the point here is that if we use the code directly above this paragraph, our system now checkes for numbers less than zero ''twice''. Not only have we repeated ourselves, but we have increased the complexity of the code, which brings us to how the Non-Redundancy Principle reduces code complexity.

=== Code Complexity ===

One way to measure code complexity is through [http://www.mccabe.com/iq_research_iqgloss.htm#cyclomatic cyclomatic complexity] (sometimes called the ''McCabe Number''). Simply put, cyclomatic complexity measures the number of different paths through a piece of code. It is often cited as a good measure of how maintainable a piece of code is, and certainly has an impact on how burdensome testing will be. In the example above:

public double sqrt(double d) {
if (d < 0) throw new IllegalArgumentException("Input must be greater than or equal to zero.");
return Math.sqrt(d);
}

We can immediately see that adding the check for the precondition to the method added an additional exit from the method, namely, the method can now throw an IllegalArgumentExecetion. Taken singly, this may not seem like a big deal, but imagine methods with two or more preconditions, and imagine every method in the system starts checking for each. On a systemic scale, redundant checking vastly increases the code bulk, complexity, and testing burden of the system.

=== Run-time versus Compile-time Errors ===

CSC/ECE 517 Fall 2009/wiki3 9 rp

2009-11-18T07:27:57Z

7r3ad:

= The Non-Redundancy Principle =

In Bertrand Meyer's ''Object Oriented Software Construction'', he
outlines many principles to increase reusability by managing
complexity in software design. Some of these apply primarily to
object oriented programming, primarily the principles dedicated to
abstract data types. Most of the principles, however, apply to
programming generally. The first five discussed in the book are often
discussed in articles (the "Open-Close Principle" perhaps being the
most popular), but equally important principles are discussed later in
the book as well. One such principle, presented in the section on
''Contracting For Software Reliability'', is called The Non-Redundancy
Principle.

== Definition ==

As with all principles presented in ''Object Oriented Software
Construction'', the principle itself is quite terse:

<blockquote> Under no circumstances shall the body of a routine ever
test for the routine's precondition. </blockquote>

As simple as this may seem on first blush, it has extensive
implications.

Before we discuss the implications, it is proper to provide a bit of
context regarding preconditions, postconditions and programming by
contract.

== Context ==

Meyer outlined the notion of ''programming by contract'', which boils
down to a methodology to enforce software modularity by clearly
defining the relationships between various components, much in the
same way relationships between individuals and/or companies are
formalized in contracts.

In Chapter 11, Meyer indicates that for each party in the contract,
the aspects of the contract include:

* Rights
* Obligations
* Preconditions
* Postconditions

In short, these indicate what is expected of the ''supplier'' and the
''client'' (terms describing the roles of objects that are party to
the contract). Specifically, a ''precondition'' is a minimum criteria
that must be satisfied on the part of the client for the contract to
be valid. The heart of the Non-Redundancy Principle is ''who'' checks
that the preconditions are satisfied, and ''when'' are those checks
made.

It must be decided whether the client or the supplier of a service
should enforce the preconditions. Once that is made clear, the
software designer must decide when the precondition will be enforced,
and once it is enforced, it should never be checked.

Meyer goes to some length to justify this position, which flies in the
face of the defensive programming mantra, which generally encourages
as much checking as possible, ostensibly to help eliminate errors
"just in case". As we will see in the following sections, and as
Meyer describes, it is difficult to justify this approach, purly on
the grounds that such redundant checking inordinately increases the
complexity of the software.

== Implications ==

There are a variety of implications that emerge from the
Non-Redundancy Principle.

=== DRY Principle ===

A common mantra in programming is "Don't Repeat Yourself" or simply
"DRY" for short. In it's simplest form, the Non-Redundancy Principle
is a specialization of DRY, in that it prohibits developers from
repeating themselves.

Consider the example that Meyer uses of a function responsible for
returning a real positive square root of a number. In Java, such a function
might look like:

/**
* Returns the postive real square root of the input, d.
*/
public double sqrt(double d) {
return Math.sqrt(d);
}

What happens if the number passed in is negative? Will the method
return a real square root? We have specified in the supplier (in this
case, the method called "sqrt") is obligated to return a positive real
square root. By specifying a precondition that the input must be
greater than or equal to zero, we now also qualify that obligation by
imposing it only if the precondition is satisfied.

/**
* Returns the postive real square root of the input, d.
* Precondition: input d >= 0
*/
public double sqrt(double d) {
return Math.sqrt(d);
}

Now we have a precondition. But what does all this have to do with
the Non-Redundancy Principle?

It might be tempting to then write this:

/**
* Returns the postive real square root of the input, d.
* Precondition: input d >= 0
*/
public double sqrt(double d) {
if (d < 0) throw new IllegalArgumentException("Input must be greater than or equal to zero.");
return Math.sqrt(d);
}

But, according to the Non-Redundancy Principle, this is prohibited!
Why? Well, what does Math.sqrt do? Does it also check for a value
less than zero? It turns out that it does. But the point here is
that if we use the code directly above this paragraph, our system now
checkes for numbers less than zero ''twice''. Not only have we
repeated ourselves, but we have increased the complexity of the code,
which brings us to how the Non-Redundancy Principle reduces code
complexity.

=== Code Complexity ===

=== Run-time versus Compile-time Errors ===

CSC/ECE 517 Fall 2009/wiki2 6 rp

2009-10-14T05:50:09Z

7r3ad: /* List Comprehension */

=Topic=

While Smalltalk and Java were instrumental in bringing object-oriented programming into the mainstream, the 1990s also saw the development of hybrid languages that supported multiple programming paradigms, often combining procedural, object-oriented and functional approaches. Discuss the development and design considerations that went into languages like OCaml, Scala, F# and Fan, and how they build upon an object-oriented foundation to offer languages that offer type safety while maintaining brevity and expressive power.

=Introduction=

There are many ways to classify programming languages: on the basis of static or dynamic typing, type safety, high or low levels of abstraction, and by programming paradigm.

In this article, the focus is on programming paradigms, which can loosely be thought of as defining the atomic units a language offers as building block with which to build programs. There are three primary paradigms in use today:

* [http://en.wikipedia.org/wiki/Procedural_programming Procedural]
* [http://en.wikipedia.org/wiki/Object-oriented_programming Object-Oriented]
* [http://en.wikipedia.org/wiki/Declarative_programming Declarative]

Declarative languages span a wide array of programming styles. For simplicity in this article, we will focus on [http://en.wikipedia.org/wiki/Functional_programming functional] languages, which are an important subset of declarative languages.

Many languages provide only one of the paradigms to their users. [http://www.engin.umd.umich.edu/CIS/course.des/cis400/fortran/fortran.html FORTRAN], [http://www.engin.umd.umich.edu/CIS/course.des/cis400/cobol/cobol.html COBOL], [http://en.wikipedia.org/wiki/Pascal_%28programming_language%29 Pascal], [http://cm.bell-labs.com/cm/cs/who/dmr/chist.html C] and [http://en.wikipedia.org/wiki/BASIC BASIC] are all procedural, [http://www.engin.umd.umich.edu/CIS/course.des/cis400/simula/simula.html Simula], [http://www.smalltalk.org/main/ Smalltalk]] and [http://www.eiffel.com/developers/design_by_contract.html Eiffel] are object-oriented and [http://haskell.org/ Haskell] and [http://en.wikipedia.org/wiki/ML_%28programming_language%29 ML] are functional. These languages provide a single paradigm for programming, which limits programmers to the particular set of constructs available in that model.

The three paradigms evolved somewhat independently and offer unique constructs with which to solve programming problems. Some languages are multi-paradigm, however, and allow a programmer to use the tools most fitting for the problem at hand, sometimes mixing and matching freely within a single program. The original language of this type is Lisp, which dates back to the mid-1950s. In the last 20 years, many other hybrid languages have emerged, often derivatives of existing languages. C++ is derived from C, and offers both procedural and object-oriented approaches. [http://java.sun.com Java], one of the most widely used languages today, offers both procedural and object-oriented paradigms as well. [http://caml.inria.fr/ OCaml] is derived from ML, and offers functional and object-oriented styles. There are many others that have become popular in recent years, like [http://python.org Python] and [http://www.ruby-lang.org/en/ Ruby].

In this article, our goal is to examine what these hybrid languages offer above and beyond strictly object-oriented languages. In particular, we will examine the features of object-oriented languages and functional languages, and how they have been blended in a modern hybrid language called [http://scala-lang.org Scala].

=Features of Object Oriented Languages=
The key construct provided by object-oriented languages is the ''object'', which bundles the data and behavior together into a cohesive unit.

==Encapsulation==
Encapsulation is the technique of rolling behavior and data into an object that exhibits (and is handled in terms of) a particular behavior, rather than a particular composition. This technique allows the internals of an object to remain hidden from external entities, which in turn enables the object to modify its implementation over time while providing the same external behaviors.

For example, encapsulation would allow a class to add logging functionality without affecting other classes' collaboration with it. Any feature that is solely an implementation concern (speeding up a sorting algorithm, checking inputs for invalid data, changing the way resource errors are handled, etc.) can be evolved and modified over time within the object without breaking functionality elsewhere in the program that relies on the object in question.

==Dependency Inversion==

One of the major benefits of focusing on the ''behavior'' of objects rather than their ''implementation'' is that the behavior aspects can be well defined and captured in an interface. This allows code that once would rely on an unstable implementation to instead shift its dependency onto a stable interface, and have the implementation then implement the interface. This process is known as ''dependency inversion'', because of the way in which it alter the dependency structure of the code.

For example, let us say we have a web server that makes use of a logging facility to log information to disk. In this case, the web server depends on the logging facility:

[[Image:server-logger.png]]

Later, it becomes apparent that the web server also want to be able to log to other destinations. To facilitate this, we introduce a ''Logger'' interface, and make have the web server depend on that, so as to insulate it from new types of loggers that may be introduced. This allows us to modify both the server and the loggers in isolation, having them both depend on the interface rather than each other, essentially reversing, or ''inverting'' the dependency diagram.

[[Image:server-logger-invert.png]]

In this diagram, the behavior of the logger is well-defined and stable, and is captured in the interface represented by the yellow box. The blue boxes are classes that are implementations, and are insulated from one another by the interface, allowing them to vary independently without breaking the program as a whole. This is an example of the robustness that the object-oriented approach lends to a program through use of encapsulation.

==Polymorphism and Dynamic Dispatch==

The object-oriented approach of thinking in terms of behavior lends itself to have multiple implementations of a single behavior. This allows the behavior (or contract) to have "many forms", and is the source of the term "polymorphism".

As an example, we can see this is the case of the logger above. To the web server, a logger is simply an object with which logs can be stored. There are many possible implementations; we could use the file logger or the network logger as seen above, but we could also implement a console logger or a database logger. Essentially, this means that the web server could call a method to log information without any knowledge of exactly what kind of object it was calling. The raises the question of how (and when) a programming language decides which log method to call. Is it compiled in, or is it determined at runtime?

The answer is that it is determined at runtime. This type of late binding, called ''dynamic dispatch'', allows a program to remain flexible even after it is deployed, permitting end-users to determine what kind of logging functionality they want be passing in various implementations of the logger interface when the web server is run, even implementations that were written ''after'' the web server was written and deployed!

The major theme here is that the object-oriented approach of favoring encapsulation has many effects that ripple throughout the design process, almost all of which allow programmers to reduce the brittleness of their software by delaying commitment to particular implementations.

=Features of Functional Languages=

Much like object-oriented languages, functional languages offer a dominant paradigm that has far-reaching consequences in software design. For object-oriented languages, that element is encapsulation, and for functional languages, it is that functions are first-class entities, which simply means that functions are treated just like any other value in the language. This allows them to be passed as parameters, delayed, composed, invoked, and returned from other functions. But what is a function?

A function's most notable trait is that it is free of ''side-effects'', or state changes to the program that occur as a result of its execution. We could say a lot about side effects, but the general rule is that a function will always return the same value given the same input. This means that functions are ''stateless''. Therefore, entities like random number generators and loggers are not functional, because they either store state or have some effect that is not related to the value they return. Another way to think of functions is that they are completely defined in terms of their input and output.

From this simple feature flows many characteristic language features. We will discuss them in turn.

==Immutability==
Maybe the most noticeable feature (or restriction) to programmers of languages that are not functional, [http://en.wikipedia.org/wiki/Immutable_object immutability] is one of the hallmarks of a functional language. Most non-functional languages allow ''assignment'', or the ability to assign new values to variables as the program runs. In functional programming, a value is declared only once and then never changes. This feature of of the language flows out of the notion that functions have no side-effects, and is often viewed as more of a restriction than a feature.

The power of immutability comes from the fact that programs that fully utilize immutability are much simpler than those that do not, making them amenable to automated analysis by a computer. Computers can then prove various properties about function programs, like concurrent behavior (presence or absence of deadlock/livelock), memory usage, and what within what bounds various values in the program will lie.

==Higher Order Functions==

Higher order functions are simply functions that accept or return other functions as values. This is made possible because functions are treated as first-class entities, and allows very expressive implementations of many algorithms to be written.

There are several hallmark higher order functions: map, reduce, fold left/right and filter are a few examples. Going into the intricacies of each is beyond the scope of this article, but Abelson and Sussman's seminal [http://mitpress.mit.edu/sicp/ Structure and Interpretation of Computer Programs] has an [http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-12.html#%_sec_1.3.1 excellent treatment] of the subject.

==Recursion==

Programmers that are new to functional programming often balk at the notion that values cannot change over time (as variables do in imperative languages). If values cannot change, how can we execute loops?

Let us examine the example of [http://en.wikipedia.org/wiki/Peano_axioms#Arithmetic Peano Arithmetic], which is a simple technique of adding two numbers together by successively decrementing one number while incrementing the other, until the number being decremented is zero. The procedural approach would simply use a loop:

public int add(int a, int b) {
while (a > 0) {
a--;
b++;
}
return b;
}

This is a straight-forward implementation of Peano Arthmetic, but you'll notice that both a and b change over time. How can implement Peano Arthimetic in a functional language?

The answer lies in recursion, where values are immutable, and loops are implemented as successive calls to the current function with new arguments. The avoids the complexity of having values change over time while offering all the power of the loops we often see in imperative languages (for...each, do...while, etc.) Going back to our example, this is what the same function would look like using recursion:

public int add(int a, int b) {
if (a==0) { return b; }
return add(a-1, b+1);
}

In this case, the values for a and b do not change over time, but rather new versions of a and b a created in each stack frame as the method successively calls itself. This has several advantages, perhaps the most important of which is that the recursive version of the add method does not modify the values passed into it, but rather allocates new values for use in each successive call.

A deep treatment of these language features is beyond the scope of this article, but again, Abelson and Sussman have [http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.1 addressed] the topic at some length in their book.

==Delayed (Lazy) Evaluation==
An extremely powerful feature of functional programming that is enabled by immutability is ''lazy evaluation''. This simply means that expressions can be defined, even recursively, and are not computed until the values that would result from that computation are needed. This is possible because values in functional programs don't change over time, which means expressions can be evaluated at any point in time as needed.

Take an imperative expression like this (in Java):

int i = 4;
int j = i + 3;
i++;

If you evaluate these expressions in order, j will be equal to 7, but if you were to delay the evaluation of j until after the third line, j would be equal to 8. This is a very simple example of how variables that change over time require expressions be evaluated in a particular order to maintain the correctness of the program. Functional programming explicitly disallows the third line, and therefore enables the value of j to be calculated only when it is needed. The implications of this are significant, as we'll see in the next section.

=Hybrid Object-Oriented/Functional Languages=

To programmers of languages like SmallTalk, Simula and Java, many of the features provided in functional languages will seem foreign or strange. But, as discussed, there are significant advantages to the functional approach for certain types of programs. While the object-oriented paradigm has proven itself to be very useful, many modern languages have sought to integrate functional features as well to increase the expressiveness and power of the language. One such language is Scala, which, like Java, runs on the Java Virtual Machine (JVM), and is thus shares Java's libraries and portability while offering many [http://www.ibm.com/developerworks/java/library/j-scala01228.html functional features] that are not available in object-oriented languages like Java. In the [http://www.scala-lang.org/node/25 overview] of Scala available on its homepage, Scala is briefly described:

<blockquote>
[Scala] smoothly integrates features of object-oriented and functional languages, enabling Java and other programmers to be more productive. Code sizes are typically reduced by a factor of two to three when compared to an equivalent Java application."
</blockquote>
How does Scala allow code sizes to be reduced so much? It uses sophisticated type inferencing to reduce type signature redundancy, allows for functional programming constructs to be used, and provides syntax for oft-used programming idioms. Essentially, it takes the lessons learned from decades of functional and object-oriented programming experience and rolls them into a modern hybrid language that can make full use legacy Java code.

Scala is representative of an entire class of hybrid object/functional languages like OCaml, F# and Fan, and therefore makes a good language for use in the examples in this article. The intent is not to present highly technical examples, but rather to give readers an impression of how hybrid languages increase expressive power over their single-paradigm counterparts.

==Case Classes==
Idiomatic object-oriented programming involves encapsulation of data, as previously discussed. In older object-oriented languages, this required defining internal data values, and then providing necessary get and set methods to access and/or modify those values. Here is an example a class in Java that provides only get methods for some (immutable) values it holds. It includes all the methods that ''should'' be included in such a class, including a toString, equals and hashCode method. Note that is an error if such methods are ''not'' included in structural Java classes, which is why I include them here.

public class UserData {
private final String firstName;
private final String lastName;
private final Integer age;
public UserData(String firstName, String lastName, Integer age) {
this.firstName = firstName;
this.lastName = lastName;
this.age = age;
}
public String getFirstName() {
return this.firstName;
}
public String getLastName() {
return this.lastName;
}
public Integer getAge() {
return this.age;
}
@Override
public boolean equals(Object obj) {
if (obj == null) {
return false;
}
if (getClass() != obj.getClass()) {
return false;
}
final UserData other = (UserData) obj;
if ((this.firstName == null) ? (other.firstName != null) : !this.firstName.equals(other.firstName)) {
return false;
}
if ((this.lastName == null) ? (other.lastName != null) : !this.lastName.equals(other.lastName)) {
return false;
}
if (this.age != other.age && (this.age == null || !this.age.equals(other.age))) {
return false;
}
return true;
}
@Override
public int hashCode() {
int hash = 7;
hash = 19 * hash + (this.firstName != null ? this.firstName.hashCode() : 0);
hash = 19 * hash + (this.lastName != null ? this.lastName.hashCode() : 0);
hash = 19 * hash + (this.age != null ? this.age.hashCode() : 0);
return hash;
}
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("UserData[firstName: ");
sb.append(this.firstName);
sb.append(" lastName: ");
sb.append(this.lastName);
sb.append(" age: ");
sb.append(this.age);
sb.append("]");
return sb.toString();
}
}

In Scala, ''all'' the functionality of the above class can be expressed with:

case class UserData(val firstName: String, val lastName: String, val age: Int)

To reiterate, the version in Scala actually does include a constructor, accessor methods, three fields that can only be set once, equals and hashCode methods (comparing the structural equality of the two instances of the class), as well a meaningful toString method which prints the fields.

There are numerous other benefits in using case classes, including automatic destructuring in pattern matching. We will discuss these features in the next section.

This feature by itself vastly reduces both development and maintenance burden for developers. Classes in Scala are defined in lines, rather than entire files. All the potential errors that could creep into that code are removed, and the ''intent'' of the developer is very clear.

==Destructuring Binds and Pattern Matching==
Lisp, one of the earliest hybrid languages, offered primarily functional features with object-orientation built on top (in a system called CLOS). One piece of functionality written with Common Lisp's metaprogramming facility was the ability to execute [http://www.ai.mit.edu/projects/iiip/doc/CommonLISP/HyperSpec/Body/mac_destructuring-bind.html destructuring binds], which are a powerful way of checking for a particular type ([http://en.wikipedia.org/wiki/Pattern_matching pattern matching]) and simultaneously extracting values from the inside of that type to use them in some computation. In the spirit of Common Lisp, Scala also offers destructuring binds and pattern matching. Let's take a look at what they can do for us.

Let us suppose we want to make use of our UserData class, defined above. We want to find all users with ages over 18 and store their names in a database. If we were to write a method that would simply do the database store for a single user, it might look like this:

public void storeName(UserData user) {
Integer age = user.getAge();
if (age > 18) {
recordToDatabase(user.lastName, user.firstName);
}
}

In Scala, this would be a trivial pattern match, with a destructuring bind to capture the fields inside the UserData (in this case, we bind them to f, l and a):

def storeName(user:UserData) = user match {
case UserData(f, l, a) if a > 18 => recordToDatabase(l, a)
}

In this case, we don't get an enourmous savings in terms of the number of lines of code used, but we gain tremendously in expressive power. Let's say we wanted to do the same thing, but not include users named "Bob". In Java:

public void storeName(UserData user) {
String firstName = user.getFirstName();
if (firstName != "Bob") {
Integer age = user.getAge();
if (age > 18) {
recordToDatabase(user.lastName, user.firstName);
}
}
}

And now in Scala:

def storeName(user:UserData) = user match {
case UserData(f, l, a) if a > 18 && f != "Bob" => recordToDatabase(l, a)
}

Hopefully this provides a little bit of insight into how destructuring can improve the expressiveness of your code. A more in depth discussion on pattern matching and binding can be be found in [http://www.codecommit.com/blog/scala/scala-for-java-refugees-part-4 Part 4] of Code Commit's series "Scala For Java Refugees".

==List Comprehension==
In imperative languages (including both procedural and object-oriented languages), it is common to loop very often, either with a for loop or a while loop. Hybrid languages allow for this, and also incorporate more abstract operations on structures seen in functional programming.

For example, suppose we wanted to take in a structure containing a bunch of UserData objects, and return a list of strings, containing the last name, a comma, and then the first name of each user.

In Java, this might look like this:

public ArrayList<String> toStrings(ArrayList<UserData> users) {
ArrayList<String> returnedList = new ArrayList<String>();
for (UserData u : users) {
returnedList.add(u.getLastName() + ", " + u.firstName);
}
return returnedList;
}

In the seven lines of code, only the method declaration and the add to the new list really have anything to do with the business logic. In Scala, that boiler plate can be avoided:

def toStrings(users: List[UserData]) = users.map(u => u.lastName + ", " + u.firstName)

This method definition is so short that it is arguable we shouldn't even define the method, and should simply use the map operation inline:

users.map(u => u.lastName + ", " + u.firstName)

Why is the definition here so short? Because the hybrid language gives us two new constructs that are useful in a great variety of situations: first-class functions, and the map operation.

# First, we define a function that takes in an instance of UserData and returns a String that is simply the concatenation of the user's last name, a comma, and the user's first name.
# Next, we pass that function to the map function, which then:
#* Takes an instance of UserData from the list called users
#* Passes that instance into the function, getting back a String
#* Appends the resultant String to a list that will be returned to the caller

The map operation goes through the entire list (users) and applies the function to each element, collects the results, and returns them. In essence, the map operation handles all the looping, and the code in conceptually a lot simpler.

This is a small demonstration of how functional languages and object-oriented languages an combine their strengths. We retain all the encapsulation of the object-oriented approach (although u.lastName and u.firstName appear to be fields, they are in fact accessor methods), but we also have the power of higher abstraction levels from the functional world (in this case, the map operation).

==Lazy Evaluation==
The final feature I'd like to touch upon is lazy evaluation. One of the many implications of lazy evaluation is that we can now program using infinite data structures; we define a way in which deeper parts of the data structure are calculated from the existing parts, and only lazily evaluate parts of the structure as they are accessed. This allows us to express algorithms quite concisely. This can be used in a variety of cases like random number generation, methods of successive approximation (like Newton's Method), fractal calculations, and generation of infinite series, as seen in the numerical methods or, more simply, the Fibonacci sequence. Because it is so well known, I will use the Fibonacci sequence as an example here. First, in Java:

public long fib(int k) {
if (k <= 2) {
return 1;
} else {
return fib(k-1) + fib(k-2);
}
}

This is a short, inefficient, recursive solution. It doesn't cache answers, either in a single call or across calls, which means it performs a huge amount of redundant computation. So it has a number of problems, but it is concise.

In Scala, we can remedy all those problems and remain concise using a [http://www.scala-lang.org/docu/files/api/scala/Stream.html Stream], a lazily evaluated form of a List:

val fibs: Stream[Int] = Stream(0,1) append fibs.zip(fibs.drop(1)).map(x => x._1 + x._2)

This definition is concise, offers automatic memoization and is thread-safe. To add those features to the Java code would require 20 lines of additional code at a minimum. It returns a Stream that can be queried for the kth Fibonacci number in the same way as the fib method defined in Java could, but calculates the 92rd Fibonacci in a fraction of a second.

=Conclusion=
Unfortunately, this article barely scratches the surface of the topic. There are decades of research and experience that have gone into modern programming languages, and the way in which they blend various programming paradigms blurs what were once quite distinct borders in the landscape of programming languages. But, that blurring has allowed these modern languages to offer programmers a bigger set of tools that aren't merely an amalgamation of features from every language, but a carefully crafted blend of features that enhance the expressiveness of these languages while not substantially increasing the syntax or API surface area.

=Glossary=

; Dynamic Dispatch
: The ability of a language to determine at runtime which implementation of a method should be executed. In object-oriented languages, this is usually on the basis of the object's class.

; Encapsulation
: The technique of enclosing the data and behavior of an object that are artifacts of its implementation, exposing only behaviors (and data) needed to satisfy its external contract.

; Immutability
: The property of an object that disallows the object from being changed after it is constructed. Immutability is often desireable in applications where the object will be used in highly parallel environments (e.g. many threads, over a network, etc.)

; Polymorphism
: Literally, "many forms"; the technique of using multiple implementations of the same contract (or interface) to enable compenents of a piece of software to be interchanged easily.

; Recursion
: A methodology for defining an algorithm or data structure in terms of itself. Often involves a direct self-referential call with a regressing value that is checked before the recursive call is performed, thus terminating the recursion.

=Further Reading=
If you want to know more about hybrid languages, its best to choose one (or a few!) and read about what they offer. If you're familiar with Java, or C#, take a look at the [http://www.scala-lang.org/node/104 tour of Scala] or perhaps some of the [http://www.fandev.org/doc/docIntro/StartHere.html features of Fan].

There are also a few major dynamically typed hybrid languages. Chief among these is [http://python.org Python], which has several implementations in [http://python.org C], [http://jython.org/ Java] and [http://codespeak.net/pypy/dist/pypy/doc/ Python](!). [http://ruby-lang.org Ruby] is also a newer hybrid language, originating in Japan, but was made famous worldwide because of its [http://rubyonrails.org/ Rails] web programming framework that was possible in large part due to its hybrid nature. It also has a [http://jruby.org/ Java implementation]. Finally, if you're working on the JVM an want a hybrid, dynamically-typed language with syntax that is close to Java's, [http://groovy.codehaus.org/ Groovy] is your best bet.

If you're very interested in performance, Common Lisp may have something to offer you, and there are [http://www.sbcl.org/ several] [http://www.cons.org/cmucl/ performant] [http://clisp.cons.org/ implementations]. If you want to learn more about why hybrid languages are so powerful, Paul Graham's book [http://www.paulgraham.com/onlisp.html On Lisp] explains why. If you really care about using the power of the JVM and are doing concurrent programming, a very modern lisp called [http://clojure.org Clojure] will be very interesting.

CSC/ECE 517 Fall 2009/wiki2 6 rp

2009-10-14T05:41:33Z

7r3ad: /* Recursion */

=Topic=

While Smalltalk and Java were instrumental in bringing object-oriented programming into the mainstream, the 1990s also saw the development of hybrid languages that supported multiple programming paradigms, often combining procedural, object-oriented and functional approaches. Discuss the development and design considerations that went into languages like OCaml, Scala, F# and Fan, and how they build upon an object-oriented foundation to offer languages that offer type safety while maintaining brevity and expressive power.

=Introduction=

There are many ways to classify programming languages: on the basis of static or dynamic typing, type safety, high or low levels of abstraction, and by programming paradigm.

In this article, the focus is on programming paradigms, which can loosely be thought of as defining the atomic units a language offers as building block with which to build programs. There are three primary paradigms in use today:

* [http://en.wikipedia.org/wiki/Procedural_programming Procedural]
* [http://en.wikipedia.org/wiki/Object-oriented_programming Object-Oriented]
* [http://en.wikipedia.org/wiki/Declarative_programming Declarative]

Declarative languages span a wide array of programming styles. For simplicity in this article, we will focus on [http://en.wikipedia.org/wiki/Functional_programming functional] languages, which are an important subset of declarative languages.

Many languages provide only one of the paradigms to their users. [http://www.engin.umd.umich.edu/CIS/course.des/cis400/fortran/fortran.html FORTRAN], [http://www.engin.umd.umich.edu/CIS/course.des/cis400/cobol/cobol.html COBOL], [http://en.wikipedia.org/wiki/Pascal_%28programming_language%29 Pascal], [http://cm.bell-labs.com/cm/cs/who/dmr/chist.html C] and [http://en.wikipedia.org/wiki/BASIC BASIC] are all procedural, [http://www.engin.umd.umich.edu/CIS/course.des/cis400/simula/simula.html Simula], [http://www.smalltalk.org/main/ Smalltalk]] and [http://www.eiffel.com/developers/design_by_contract.html Eiffel] are object-oriented and [http://haskell.org/ Haskell] and [http://en.wikipedia.org/wiki/ML_%28programming_language%29 ML] are functional. These languages provide a single paradigm for programming, which limits programmers to the particular set of constructs available in that model.

The three paradigms evolved somewhat independently and offer unique constructs with which to solve programming problems. Some languages are multi-paradigm, however, and allow a programmer to use the tools most fitting for the problem at hand, sometimes mixing and matching freely within a single program. The original language of this type is Lisp, which dates back to the mid-1950s. In the last 20 years, many other hybrid languages have emerged, often derivatives of existing languages. C++ is derived from C, and offers both procedural and object-oriented approaches. [http://java.sun.com Java], one of the most widely used languages today, offers both procedural and object-oriented paradigms as well. [http://caml.inria.fr/ OCaml] is derived from ML, and offers functional and object-oriented styles. There are many others that have become popular in recent years, like [http://python.org Python] and [http://www.ruby-lang.org/en/ Ruby].

In this article, our goal is to examine what these hybrid languages offer above and beyond strictly object-oriented languages. In particular, we will examine the features of object-oriented languages and functional languages, and how they have been blended in a modern hybrid language called [http://scala-lang.org Scala].

=Features of Object Oriented Languages=
The key construct provided by object-oriented languages is the ''object'', which bundles the data and behavior together into a cohesive unit.

==Encapsulation==
Encapsulation is the technique of rolling behavior and data into an object that exhibits (and is handled in terms of) a particular behavior, rather than a particular composition. This technique allows the internals of an object to remain hidden from external entities, which in turn enables the object to modify its implementation over time while providing the same external behaviors.

For example, encapsulation would allow a class to add logging functionality without affecting other classes' collaboration with it. Any feature that is solely an implementation concern (speeding up a sorting algorithm, checking inputs for invalid data, changing the way resource errors are handled, etc.) can be evolved and modified over time within the object without breaking functionality elsewhere in the program that relies on the object in question.

==Dependency Inversion==

One of the major benefits of focusing on the ''behavior'' of objects rather than their ''implementation'' is that the behavior aspects can be well defined and captured in an interface. This allows code that once would rely on an unstable implementation to instead shift its dependency onto a stable interface, and have the implementation then implement the interface. This process is known as ''dependency inversion'', because of the way in which it alter the dependency structure of the code.

For example, let us say we have a web server that makes use of a logging facility to log information to disk. In this case, the web server depends on the logging facility:

[[Image:server-logger.png]]

Later, it becomes apparent that the web server also want to be able to log to other destinations. To facilitate this, we introduce a ''Logger'' interface, and make have the web server depend on that, so as to insulate it from new types of loggers that may be introduced. This allows us to modify both the server and the loggers in isolation, having them both depend on the interface rather than each other, essentially reversing, or ''inverting'' the dependency diagram.

[[Image:server-logger-invert.png]]

In this diagram, the behavior of the logger is well-defined and stable, and is captured in the interface represented by the yellow box. The blue boxes are classes that are implementations, and are insulated from one another by the interface, allowing them to vary independently without breaking the program as a whole. This is an example of the robustness that the object-oriented approach lends to a program through use of encapsulation.

==Polymorphism and Dynamic Dispatch==

The object-oriented approach of thinking in terms of behavior lends itself to have multiple implementations of a single behavior. This allows the behavior (or contract) to have "many forms", and is the source of the term "polymorphism".

As an example, we can see this is the case of the logger above. To the web server, a logger is simply an object with which logs can be stored. There are many possible implementations; we could use the file logger or the network logger as seen above, but we could also implement a console logger or a database logger. Essentially, this means that the web server could call a method to log information without any knowledge of exactly what kind of object it was calling. The raises the question of how (and when) a programming language decides which log method to call. Is it compiled in, or is it determined at runtime?

The answer is that it is determined at runtime. This type of late binding, called ''dynamic dispatch'', allows a program to remain flexible even after it is deployed, permitting end-users to determine what kind of logging functionality they want be passing in various implementations of the logger interface when the web server is run, even implementations that were written ''after'' the web server was written and deployed!

The major theme here is that the object-oriented approach of favoring encapsulation has many effects that ripple throughout the design process, almost all of which allow programmers to reduce the brittleness of their software by delaying commitment to particular implementations.

=Features of Functional Languages=

Much like object-oriented languages, functional languages offer a dominant paradigm that has far-reaching consequences in software design. For object-oriented languages, that element is encapsulation, and for functional languages, it is that functions are first-class entities, which simply means that functions are treated just like any other value in the language. This allows them to be passed as parameters, delayed, composed, invoked, and returned from other functions. But what is a function?

A function's most notable trait is that it is free of ''side-effects'', or state changes to the program that occur as a result of its execution. We could say a lot about side effects, but the general rule is that a function will always return the same value given the same input. This means that functions are ''stateless''. Therefore, entities like random number generators and loggers are not functional, because they either store state or have some effect that is not related to the value they return. Another way to think of functions is that they are completely defined in terms of their input and output.

From this simple feature flows many characteristic language features. We will discuss them in turn.

==Immutability==
Maybe the most noticeable feature (or restriction) to programmers of languages that are not functional, [http://en.wikipedia.org/wiki/Immutable_object immutability] is one of the hallmarks of a functional language. Most non-functional languages allow ''assignment'', or the ability to assign new values to variables as the program runs. In functional programming, a value is declared only once and then never changes. This feature of of the language flows out of the notion that functions have no side-effects, and is often viewed as more of a restriction than a feature.

The power of immutability comes from the fact that programs that fully utilize immutability are much simpler than those that do not, making them amenable to automated analysis by a computer. Computers can then prove various properties about function programs, like concurrent behavior (presence or absence of deadlock/livelock), memory usage, and what within what bounds various values in the program will lie.

==Higher Order Functions==

Higher order functions are simply functions that accept or return other functions as values. This is made possible because functions are treated as first-class entities, and allows very expressive implementations of many algorithms to be written.

There are several hallmark higher order functions: map, reduce, fold left/right and filter are a few examples. Going into the intricacies of each is beyond the scope of this article, but Abelson and Sussman's seminal [http://mitpress.mit.edu/sicp/ Structure and Interpretation of Computer Programs] has an [http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-12.html#%_sec_1.3.1 excellent treatment] of the subject.

==Recursion==

Programmers that are new to functional programming often balk at the notion that values cannot change over time (as variables do in imperative languages). If values cannot change, how can we execute loops?

Let us examine the example of [http://en.wikipedia.org/wiki/Peano_axioms#Arithmetic Peano Arithmetic], which is a simple technique of adding two numbers together by successively decrementing one number while incrementing the other, until the number being decremented is zero. The procedural approach would simply use a loop:

public int add(int a, int b) {
while (a > 0) {
a--;
b++;
}
return b;
}

This is a straight-forward implementation of Peano Arthmetic, but you'll notice that both a and b change over time. How can implement Peano Arthimetic in a functional language?

The answer lies in recursion, where values are immutable, and loops are implemented as successive calls to the current function with new arguments. The avoids the complexity of having values change over time while offering all the power of the loops we often see in imperative languages (for...each, do...while, etc.) Going back to our example, this is what the same function would look like using recursion:

public int add(int a, int b) {
if (a==0) { return b; }
return add(a-1, b+1);
}

In this case, the values for a and b do not change over time, but rather new versions of a and b a created in each stack frame as the method successively calls itself. This has several advantages, perhaps the most important of which is that the recursive version of the add method does not modify the values passed into it, but rather allocates new values for use in each successive call.

A deep treatment of these language features is beyond the scope of this article, but again, Abelson and Sussman have [http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.1 addressed] the topic at some length in their book.

==Delayed (Lazy) Evaluation==
An extremely powerful feature of functional programming that is enabled by immutability is ''lazy evaluation''. This simply means that expressions can be defined, even recursively, and are not computed until the values that would result from that computation are needed. This is possible because values in functional programs don't change over time, which means expressions can be evaluated at any point in time as needed.

Take an imperative expression like this (in Java):

int i = 4;
int j = i + 3;
i++;

If you evaluate these expressions in order, j will be equal to 7, but if you were to delay the evaluation of j until after the third line, j would be equal to 8. This is a very simple example of how variables that change over time require expressions be evaluated in a particular order to maintain the correctness of the program. Functional programming explicitly disallows the third line, and therefore enables the value of j to be calculated only when it is needed. The implications of this are significant, as we'll see in the next section.

=Hybrid Object-Oriented/Functional Languages=

To programmers of languages like SmallTalk, Simula and Java, many of the features provided in functional languages will seem foreign or strange. But, as discussed, there are significant advantages to the functional approach for certain types of programs. While the object-oriented paradigm has proven itself to be very useful, many modern languages have sought to integrate functional features as well to increase the expressiveness and power of the language. One such language is Scala, which, like Java, runs on the Java Virtual Machine (JVM), and is thus shares Java's libraries and portability while offering many [http://www.ibm.com/developerworks/java/library/j-scala01228.html functional features] that are not available in object-oriented languages like Java. In the [http://www.scala-lang.org/node/25 overview] of Scala available on its homepage, Scala is briefly described:

<blockquote>
[Scala] smoothly integrates features of object-oriented and functional languages, enabling Java and other programmers to be more productive. Code sizes are typically reduced by a factor of two to three when compared to an equivalent Java application."
</blockquote>
How does Scala allow code sizes to be reduced so much? It uses sophisticated type inferencing to reduce type signature redundancy, allows for functional programming constructs to be used, and provides syntax for oft-used programming idioms. Essentially, it takes the lessons learned from decades of functional and object-oriented programming experience and rolls them into a modern hybrid language that can make full use legacy Java code.

Scala is representative of an entire class of hybrid object/functional languages like OCaml, F# and Fan, and therefore makes a good language for use in the examples in this article. The intent is not to present highly technical examples, but rather to give readers an impression of how hybrid languages increase expressive power over their single-paradigm counterparts.

==Case Classes==
Idiomatic object-oriented programming involves encapsulation of data, as previously discussed. In older object-oriented languages, this required defining internal data values, and then providing necessary get and set methods to access and/or modify those values. Here is an example a class in Java that provides only get methods for some (immutable) values it holds. It includes all the methods that ''should'' be included in such a class, including a toString, equals and hashCode method. Note that is an error if such methods are ''not'' included in structural Java classes, which is why I include them here.

public class UserData {
private final String firstName;
private final String lastName;
private final Integer age;
public UserData(String firstName, String lastName, Integer age) {
this.firstName = firstName;
this.lastName = lastName;
this.age = age;
}
public String getFirstName() {
return this.firstName;
}
public String getLastName() {
return this.lastName;
}
public Integer getAge() {
return this.age;
}
@Override
public boolean equals(Object obj) {
if (obj == null) {
return false;
}
if (getClass() != obj.getClass()) {
return false;
}
final UserData other = (UserData) obj;
if ((this.firstName == null) ? (other.firstName != null) : !this.firstName.equals(other.firstName)) {
return false;
}
if ((this.lastName == null) ? (other.lastName != null) : !this.lastName.equals(other.lastName)) {
return false;
}
if (this.age != other.age && (this.age == null || !this.age.equals(other.age))) {
return false;
}
return true;
}
@Override
public int hashCode() {
int hash = 7;
hash = 19 * hash + (this.firstName != null ? this.firstName.hashCode() : 0);
hash = 19 * hash + (this.lastName != null ? this.lastName.hashCode() : 0);
hash = 19 * hash + (this.age != null ? this.age.hashCode() : 0);
return hash;
}
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("UserData[firstName: ");
sb.append(this.firstName);
sb.append(" lastName: ");
sb.append(this.lastName);
sb.append(" age: ");
sb.append(this.age);
sb.append("]");
return sb.toString();
}
}

In Scala, ''all'' the functionality of the above class can be expressed with:

case class UserData(val firstName: String, val lastName: String, val age: Int)

To reiterate, the version in Scala actually does include a constructor, accessor methods, three fields that can only be set once, equals and hashCode methods (comparing the structural equality of the two instances of the class), as well a meaningful toString method which prints the fields.

There are numerous other benefits in using case classes, including automatic destructuring in pattern matching. We will discuss these features in the next section.

This feature by itself vastly reduces both development and maintenance burden for developers. Classes in Scala are defined in lines, rather than entire files. All the potential errors that could creep into that code are removed, and the ''intent'' of the developer is very clear.

==Destructuring Binds and Pattern Matching==
Lisp, one of the earliest hybrid languages, offered primarily functional features with object-orientation built on top (in a system called CLOS). One piece of functionality written with Common Lisp's metaprogramming facility was the ability to execute [http://www.ai.mit.edu/projects/iiip/doc/CommonLISP/HyperSpec/Body/mac_destructuring-bind.html destructuring binds], which are a powerful way of checking for a particular type ([http://en.wikipedia.org/wiki/Pattern_matching pattern matching]) and simultaneously extracting values from the inside of that type to use them in some computation. In the spirit of Common Lisp, Scala also offers destructuring binds and pattern matching. Let's take a look at what they can do for us.

Let us suppose we want to make use of our UserData class, defined above. We want to find all users with ages over 18 and store their names in a database. If we were to write a method that would simply do the database store for a single user, it might look like this:

public void storeName(UserData user) {
Integer age = user.getAge();
if (age > 18) {
recordToDatabase(user.lastName, user.firstName);
}
}

In Scala, this would be a trivial pattern match, with a destructuring bind to capture the fields inside the UserData (in this case, we bind them to f, l and a):

def storeName(user:UserData) = user match {
case UserData(f, l, a) if a > 18 => recordToDatabase(l, a)
}

In this case, we don't get an enourmous savings in terms of the number of lines of code used, but we gain tremendously in expressive power. Let's say we wanted to do the same thing, but not include users named "Bob". In Java:

public void storeName(UserData user) {
String firstName = user.getFirstName();
if (firstName != "Bob") {
Integer age = user.getAge();
if (age > 18) {
recordToDatabase(user.lastName, user.firstName);
}
}
}

And now in Scala:

def storeName(user:UserData) = user match {
case UserData(f, l, a) if a > 18 && f != "Bob" => recordToDatabase(l, a)
}

Hopefully this provides a little bit of insight into how destructuring can improve the expressiveness of your code. A more in depth discussion on pattern matching and binding can be be found in [http://www.codecommit.com/blog/scala/scala-for-java-refugees-part-4 Part 4] of Code Commit's series "Scala For Java Refugees".

==List Comprehension==
In imperative languages (including both procedural and object-oriented languages), it is common to loop very often, either with a for loop or a while loop. Hybrid languages allow for this, and also incorporate more abstract operations on structures seen in functional programming.

For example, suppose we wanted to take in a structure containing a bunch of UserData objects, and return a list of strings, containing the last name, a comma, and then the first name of each user.

In Java, this might look like this:

public ArrayList<String> toStrings(ArrayList<UserData> users) {
ArrayList<String> returnedList = new ArrayList<String>();
for (UserData u : users) {
returnedList.add(u.getLastName() + ", " + u.firstName);
}
return returnedList;
}

In the seven lines of code, only the method declaration and the add to the new list really have anything to do with the business logic. In Scala, that boiler plate can be avoided:

def toStrings(users: List[UserData]) = users.map(u => u.lastName + ", " + u.firstName)

This method definition is so short that it is arguable we shouldn't even define the method, and should simply use the map operation inline:

users.map(u => u.lastName + ", " + u.firstName)

This is a small demonstration of how functional languages and object-oriented languages an combine their strengths. We retain all the encapsulation of the object-oriented approach (although u.lastName and u.firstName appear to be fields, they are in fact accessor methods), but we also have the power of higher abstraction levels from the functional world (in this case, the map operation).

==Lazy Evaluation==
The final feature I'd like to touch upon is lazy evaluation. One of the many implications of lazy evaluation is that we can now program using infinite data structures; we define a way in which deeper parts of the data structure are calculated from the existing parts, and only lazily evaluate parts of the structure as they are accessed. This allows us to express algorithms quite concisely. This can be used in a variety of cases like random number generation, methods of successive approximation (like Newton's Method), fractal calculations, and generation of infinite series, as seen in the numerical methods or, more simply, the Fibonacci sequence. Because it is so well known, I will use the Fibonacci sequence as an example here. First, in Java:

public long fib(int k) {
if (k <= 2) {
return 1;
} else {
return fib(k-1) + fib(k-2);
}
}

This is a short, inefficient, recursive solution. It doesn't cache answers, either in a single call or across calls, which means it performs a huge amount of redundant computation. So it has a number of problems, but it is concise.

In Scala, we can remedy all those problems and remain concise using a [http://www.scala-lang.org/docu/files/api/scala/Stream.html Stream], a lazily evaluated form of a List:

val fibs: Stream[Int] = Stream(0,1) append fibs.zip(fibs.drop(1)).map(x => x._1 + x._2)

This definition is concise, offers automatic memoization and is thread-safe. To add those features to the Java code would require 20 lines of additional code at a minimum. It returns a Stream that can be queried for the kth Fibonacci number in the same way as the fib method defined in Java could, but calculates the 92rd Fibonacci in a fraction of a second.

=Conclusion=
Unfortunately, this article barely scratches the surface of the topic. There are decades of research and experience that have gone into modern programming languages, and the way in which they blend various programming paradigms blurs what were once quite distinct borders in the landscape of programming languages. But, that blurring has allowed these modern languages to offer programmers a bigger set of tools that aren't merely an amalgamation of features from every language, but a carefully crafted blend of features that enhance the expressiveness of these languages while not substantially increasing the syntax or API surface area.

=Glossary=

; Dynamic Dispatch
: The ability of a language to determine at runtime which implementation of a method should be executed. In object-oriented languages, this is usually on the basis of the object's class.

; Encapsulation
: The technique of enclosing the data and behavior of an object that are artifacts of its implementation, exposing only behaviors (and data) needed to satisfy its external contract.

; Immutability
: The property of an object that disallows the object from being changed after it is constructed. Immutability is often desireable in applications where the object will be used in highly parallel environments (e.g. many threads, over a network, etc.)

; Polymorphism
: Literally, "many forms"; the technique of using multiple implementations of the same contract (or interface) to enable compenents of a piece of software to be interchanged easily.

; Recursion
: A methodology for defining an algorithm or data structure in terms of itself. Often involves a direct self-referential call with a regressing value that is checked before the recursive call is performed, thus terminating the recursion.

=Further Reading=
If you want to know more about hybrid languages, its best to choose one (or a few!) and read about what they offer. If you're familiar with Java, or C#, take a look at the [http://www.scala-lang.org/node/104 tour of Scala] or perhaps some of the [http://www.fandev.org/doc/docIntro/StartHere.html features of Fan].

There are also a few major dynamically typed hybrid languages. Chief among these is [http://python.org Python], which has several implementations in [http://python.org C], [http://jython.org/ Java] and [http://codespeak.net/pypy/dist/pypy/doc/ Python](!). [http://ruby-lang.org Ruby] is also a newer hybrid language, originating in Japan, but was made famous worldwide because of its [http://rubyonrails.org/ Rails] web programming framework that was possible in large part due to its hybrid nature. It also has a [http://jruby.org/ Java implementation]. Finally, if you're working on the JVM an want a hybrid, dynamically-typed language with syntax that is close to Java's, [http://groovy.codehaus.org/ Groovy] is your best bet.

If you're very interested in performance, Common Lisp may have something to offer you, and there are [http://www.sbcl.org/ several] [http://www.cons.org/cmucl/ performant] [http://clisp.cons.org/ implementations]. If you want to learn more about why hybrid languages are so powerful, Paul Graham's book [http://www.paulgraham.com/onlisp.html On Lisp] explains why. If you really care about using the power of the JVM and are doing concurrent programming, a very modern lisp called [http://clojure.org Clojure] will be very interesting.

CSC/ECE 517 Fall 2009/wiki2 6 rp

2009-10-14T05:29:47Z

7r3ad: /* Polymorphism and Dynamic Dispatch */

=Topic=

While Smalltalk and Java were instrumental in bringing object-oriented programming into the mainstream, the 1990s also saw the development of hybrid languages that supported multiple programming paradigms, often combining procedural, object-oriented and functional approaches. Discuss the development and design considerations that went into languages like OCaml, Scala, F# and Fan, and how they build upon an object-oriented foundation to offer languages that offer type safety while maintaining brevity and expressive power.

=Introduction=

There are many ways to classify programming languages: on the basis of static or dynamic typing, type safety, high or low levels of abstraction, and by programming paradigm.

In this article, the focus is on programming paradigms, which can loosely be thought of as defining the atomic units a language offers as building block with which to build programs. There are three primary paradigms in use today:

* [http://en.wikipedia.org/wiki/Procedural_programming Procedural]
* [http://en.wikipedia.org/wiki/Object-oriented_programming Object-Oriented]
* [http://en.wikipedia.org/wiki/Declarative_programming Declarative]

Declarative languages span a wide array of programming styles. For simplicity in this article, we will focus on [http://en.wikipedia.org/wiki/Functional_programming functional] languages, which are an important subset of declarative languages.

Many languages provide only one of the paradigms to their users. [http://www.engin.umd.umich.edu/CIS/course.des/cis400/fortran/fortran.html FORTRAN], [http://www.engin.umd.umich.edu/CIS/course.des/cis400/cobol/cobol.html COBOL], [http://en.wikipedia.org/wiki/Pascal_%28programming_language%29 Pascal], [http://cm.bell-labs.com/cm/cs/who/dmr/chist.html C] and [http://en.wikipedia.org/wiki/BASIC BASIC] are all procedural, [http://www.engin.umd.umich.edu/CIS/course.des/cis400/simula/simula.html Simula], [http://www.smalltalk.org/main/ Smalltalk]] and [http://www.eiffel.com/developers/design_by_contract.html Eiffel] are object-oriented and [http://haskell.org/ Haskell] and [http://en.wikipedia.org/wiki/ML_%28programming_language%29 ML] are functional. These languages provide a single paradigm for programming, which limits programmers to the particular set of constructs available in that model.

The three paradigms evolved somewhat independently and offer unique constructs with which to solve programming problems. Some languages are multi-paradigm, however, and allow a programmer to use the tools most fitting for the problem at hand, sometimes mixing and matching freely within a single program. The original language of this type is Lisp, which dates back to the mid-1950s. In the last 20 years, many other hybrid languages have emerged, often derivatives of existing languages. C++ is derived from C, and offers both procedural and object-oriented approaches. [http://java.sun.com Java], one of the most widely used languages today, offers both procedural and object-oriented paradigms as well. [http://caml.inria.fr/ OCaml] is derived from ML, and offers functional and object-oriented styles. There are many others that have become popular in recent years, like [http://python.org Python] and [http://www.ruby-lang.org/en/ Ruby].

In this article, our goal is to examine what these hybrid languages offer above and beyond strictly object-oriented languages. In particular, we will examine the features of object-oriented languages and functional languages, and how they have been blended in a modern hybrid language called [http://scala-lang.org Scala].

=Features of Object Oriented Languages=
The key construct provided by object-oriented languages is the ''object'', which bundles the data and behavior together into a cohesive unit.

==Encapsulation==
Encapsulation is the technique of rolling behavior and data into an object that exhibits (and is handled in terms of) a particular behavior, rather than a particular composition. This technique allows the internals of an object to remain hidden from external entities, which in turn enables the object to modify its implementation over time while providing the same external behaviors.

For example, encapsulation would allow a class to add logging functionality without affecting other classes' collaboration with it. Any feature that is solely an implementation concern (speeding up a sorting algorithm, checking inputs for invalid data, changing the way resource errors are handled, etc.) can be evolved and modified over time within the object without breaking functionality elsewhere in the program that relies on the object in question.

==Dependency Inversion==

One of the major benefits of focusing on the ''behavior'' of objects rather than their ''implementation'' is that the behavior aspects can be well defined and captured in an interface. This allows code that once would rely on an unstable implementation to instead shift its dependency onto a stable interface, and have the implementation then implement the interface. This process is known as ''dependency inversion'', because of the way in which it alter the dependency structure of the code.

For example, let us say we have a web server that makes use of a logging facility to log information to disk. In this case, the web server depends on the logging facility:

[[Image:server-logger.png]]

Later, it becomes apparent that the web server also want to be able to log to other destinations. To facilitate this, we introduce a ''Logger'' interface, and make have the web server depend on that, so as to insulate it from new types of loggers that may be introduced. This allows us to modify both the server and the loggers in isolation, having them both depend on the interface rather than each other, essentially reversing, or ''inverting'' the dependency diagram.

[[Image:server-logger-invert.png]]

In this diagram, the behavior of the logger is well-defined and stable, and is captured in the interface represented by the yellow box. The blue boxes are classes that are implementations, and are insulated from one another by the interface, allowing them to vary independently without breaking the program as a whole. This is an example of the robustness that the object-oriented approach lends to a program through use of encapsulation.

==Polymorphism and Dynamic Dispatch==

The object-oriented approach of thinking in terms of behavior lends itself to have multiple implementations of a single behavior. This allows the behavior (or contract) to have "many forms", and is the source of the term "polymorphism".

As an example, we can see this is the case of the logger above. To the web server, a logger is simply an object with which logs can be stored. There are many possible implementations; we could use the file logger or the network logger as seen above, but we could also implement a console logger or a database logger. Essentially, this means that the web server could call a method to log information without any knowledge of exactly what kind of object it was calling. The raises the question of how (and when) a programming language decides which log method to call. Is it compiled in, or is it determined at runtime?

The answer is that it is determined at runtime. This type of late binding, called ''dynamic dispatch'', allows a program to remain flexible even after it is deployed, permitting end-users to determine what kind of logging functionality they want be passing in various implementations of the logger interface when the web server is run, even implementations that were written ''after'' the web server was written and deployed!

The major theme here is that the object-oriented approach of favoring encapsulation has many effects that ripple throughout the design process, almost all of which allow programmers to reduce the brittleness of their software by delaying commitment to particular implementations.

=Features of Functional Languages=

Much like object-oriented languages, functional languages offer a dominant paradigm that has far-reaching consequences in software design. For object-oriented languages, that element is encapsulation, and for functional languages, it is that functions are first-class entities, which simply means that functions are treated just like any other value in the language. This allows them to be passed as parameters, delayed, composed, invoked, and returned from other functions. But what is a function?

A function's most notable trait is that it is free of ''side-effects'', or state changes to the program that occur as a result of its execution. We could say a lot about side effects, but the general rule is that a function will always return the same value given the same input. This means that functions are ''stateless''. Therefore, entities like random number generators and loggers are not functional, because they either store state or have some effect that is not related to the value they return. Another way to think of functions is that they are completely defined in terms of their input and output.

From this simple feature flows many characteristic language features. We will discuss them in turn.

==Immutability==
Maybe the most noticeable feature (or restriction) to programmers of languages that are not functional, [http://en.wikipedia.org/wiki/Immutable_object immutability] is one of the hallmarks of a functional language. Most non-functional languages allow ''assignment'', or the ability to assign new values to variables as the program runs. In functional programming, a value is declared only once and then never changes. This feature of of the language flows out of the notion that functions have no side-effects, and is often viewed as more of a restriction than a feature.

The power of immutability comes from the fact that programs that fully utilize immutability are much simpler than those that do not, making them amenable to automated analysis by a computer. Computers can then prove various properties about function programs, like concurrent behavior (presence or absence of deadlock/livelock), memory usage, and what within what bounds various values in the program will lie.

==Higher Order Functions==

Higher order functions are simply functions that accept or return other functions as values. This is made possible because functions are treated as first-class entities, and allows very expressive implementations of many algorithms to be written.

There are several hallmark higher order functions: map, reduce, fold left/right and filter are a few examples. Going into the intricacies of each is beyond the scope of this article, but Abelson and Sussman's seminal [http://mitpress.mit.edu/sicp/ Structure and Interpretation of Computer Programs] has an [http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-12.html#%_sec_1.3.1 excellent treatment] of the subject.

==Recursion==

Programmers that are new to functional programming often balk at the notion that values cannot change over time (as variables do in imperative languages). If values cannot change, how can we execute loops?

The answer lies in recursion, where values are immutable, and loops are implemented as successive calls to the current function with new arguments. The avoids the complexity of having values change over time while offering all the power of the loops we often see in imperative languages (for...each, do...while, etc.) Again, a deep treatment of these language features is beyond the scope of this article, but again, Abelson and Sussman have [http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.1 addressed] the topic at some length in their book.

==Delayed (Lazy) Evaluation==
An extremely powerful feature of functional programming that is enabled by immutability is ''lazy evaluation''. This simply means that expressions can be defined, even recursively, and are not computed until the values that would result from that computation are needed. This is possible because values in functional programs don't change over time, which means expressions can be evaluated at any point in time as needed.

Take an imperative expression like this (in Java):

int i = 4;
int j = i + 3;
i++;

If you evaluate these expressions in order, j will be equal to 7, but if you were to delay the evaluation of j until after the third line, j would be equal to 8. This is a very simple example of how variables that change over time require expressions be evaluated in a particular order to maintain the correctness of the program. Functional programming explicitly disallows the third line, and therefore enables the value of j to be calculated only when it is needed. The implications of this are significant, as we'll see in the next section.

=Hybrid Object-Oriented/Functional Languages=

To programmers of languages like SmallTalk, Simula and Java, many of the features provided in functional languages will seem foreign or strange. But, as discussed, there are significant advantages to the functional approach for certain types of programs. While the object-oriented paradigm has proven itself to be very useful, many modern languages have sought to integrate functional features as well to increase the expressiveness and power of the language. One such language is Scala, which, like Java, runs on the Java Virtual Machine (JVM), and is thus shares Java's libraries and portability while offering many [http://www.ibm.com/developerworks/java/library/j-scala01228.html functional features] that are not available in object-oriented languages like Java. In the [http://www.scala-lang.org/node/25 overview] of Scala available on its homepage, Scala is briefly described:

<blockquote>
[Scala] smoothly integrates features of object-oriented and functional languages, enabling Java and other programmers to be more productive. Code sizes are typically reduced by a factor of two to three when compared to an equivalent Java application."
</blockquote>
How does Scala allow code sizes to be reduced so much? It uses sophisticated type inferencing to reduce type signature redundancy, allows for functional programming constructs to be used, and provides syntax for oft-used programming idioms. Essentially, it takes the lessons learned from decades of functional and object-oriented programming experience and rolls them into a modern hybrid language that can make full use legacy Java code.

Scala is representative of an entire class of hybrid object/functional languages like OCaml, F# and Fan, and therefore makes a good language for use in the examples in this article. The intent is not to present highly technical examples, but rather to give readers an impression of how hybrid languages increase expressive power over their single-paradigm counterparts.

==Case Classes==
Idiomatic object-oriented programming involves encapsulation of data, as previously discussed. In older object-oriented languages, this required defining internal data values, and then providing necessary get and set methods to access and/or modify those values. Here is an example a class in Java that provides only get methods for some (immutable) values it holds. It includes all the methods that ''should'' be included in such a class, including a toString, equals and hashCode method. Note that is an error if such methods are ''not'' included in structural Java classes, which is why I include them here.

public class UserData {
private final String firstName;
private final String lastName;
private final Integer age;
public UserData(String firstName, String lastName, Integer age) {
this.firstName = firstName;
this.lastName = lastName;
this.age = age;
}
public String getFirstName() {
return this.firstName;
}
public String getLastName() {
return this.lastName;
}
public Integer getAge() {
return this.age;
}
@Override
public boolean equals(Object obj) {
if (obj == null) {
return false;
}
if (getClass() != obj.getClass()) {
return false;
}
final UserData other = (UserData) obj;
if ((this.firstName == null) ? (other.firstName != null) : !this.firstName.equals(other.firstName)) {
return false;
}
if ((this.lastName == null) ? (other.lastName != null) : !this.lastName.equals(other.lastName)) {
return false;
}
if (this.age != other.age && (this.age == null || !this.age.equals(other.age))) {
return false;
}
return true;
}
@Override
public int hashCode() {
int hash = 7;
hash = 19 * hash + (this.firstName != null ? this.firstName.hashCode() : 0);
hash = 19 * hash + (this.lastName != null ? this.lastName.hashCode() : 0);
hash = 19 * hash + (this.age != null ? this.age.hashCode() : 0);
return hash;
}
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("UserData[firstName: ");
sb.append(this.firstName);
sb.append(" lastName: ");
sb.append(this.lastName);
sb.append(" age: ");
sb.append(this.age);
sb.append("]");
return sb.toString();
}
}

In Scala, ''all'' the functionality of the above class can be expressed with:

case class UserData(val firstName: String, val lastName: String, val age: Int)

To reiterate, the version in Scala actually does include a constructor, accessor methods, three fields that can only be set once, equals and hashCode methods (comparing the structural equality of the two instances of the class), as well a meaningful toString method which prints the fields.

There are numerous other benefits in using case classes, including automatic destructuring in pattern matching. We will discuss these features in the next section.

This feature by itself vastly reduces both development and maintenance burden for developers. Classes in Scala are defined in lines, rather than entire files. All the potential errors that could creep into that code are removed, and the ''intent'' of the developer is very clear.

==Destructuring Binds and Pattern Matching==
Lisp, one of the earliest hybrid languages, offered primarily functional features with object-orientation built on top (in a system called CLOS). One piece of functionality written with Common Lisp's metaprogramming facility was the ability to execute [http://www.ai.mit.edu/projects/iiip/doc/CommonLISP/HyperSpec/Body/mac_destructuring-bind.html destructuring binds], which are a powerful way of checking for a particular type ([http://en.wikipedia.org/wiki/Pattern_matching pattern matching]) and simultaneously extracting values from the inside of that type to use them in some computation. In the spirit of Common Lisp, Scala also offers destructuring binds and pattern matching. Let's take a look at what they can do for us.

Let us suppose we want to make use of our UserData class, defined above. We want to find all users with ages over 18 and store their names in a database. If we were to write a method that would simply do the database store for a single user, it might look like this:

public void storeName(UserData user) {
Integer age = user.getAge();
if (age > 18) {
recordToDatabase(user.lastName, user.firstName);
}
}

In Scala, this would be a trivial pattern match, with a destructuring bind to capture the fields inside the UserData (in this case, we bind them to f, l and a):

def storeName(user:UserData) = user match {
case UserData(f, l, a) if a > 18 => recordToDatabase(l, a)
}

In this case, we don't get an enourmous savings in terms of the number of lines of code used, but we gain tremendously in expressive power. Let's say we wanted to do the same thing, but not include users named "Bob". In Java:

public void storeName(UserData user) {
String firstName = user.getFirstName();
if (firstName != "Bob") {
Integer age = user.getAge();
if (age > 18) {
recordToDatabase(user.lastName, user.firstName);
}
}
}

And now in Scala:

def storeName(user:UserData) = user match {
case UserData(f, l, a) if a > 18 && f != "Bob" => recordToDatabase(l, a)
}

Hopefully this provides a little bit of insight into how destructuring can improve the expressiveness of your code. A more in depth discussion on pattern matching and binding can be be found in [http://www.codecommit.com/blog/scala/scala-for-java-refugees-part-4 Part 4] of Code Commit's series "Scala For Java Refugees".

==List Comprehension==
In imperative languages (including both procedural and object-oriented languages), it is common to loop very often, either with a for loop or a while loop. Hybrid languages allow for this, and also incorporate more abstract operations on structures seen in functional programming.

For example, suppose we wanted to take in a structure containing a bunch of UserData objects, and return a list of strings, containing the last name, a comma, and then the first name of each user.

In Java, this might look like this:

public ArrayList<String> toStrings(ArrayList<UserData> users) {
ArrayList<String> returnedList = new ArrayList<String>();
for (UserData u : users) {
returnedList.add(u.getLastName() + ", " + u.firstName);
}
return returnedList;
}

In the seven lines of code, only the method declaration and the add to the new list really have anything to do with the business logic. In Scala, that boiler plate can be avoided:

def toStrings(users: List[UserData]) = users.map(u => u.lastName + ", " + u.firstName)

This method definition is so short that it is arguable we shouldn't even define the method, and should simply use the map operation inline:

users.map(u => u.lastName + ", " + u.firstName)

This is a small demonstration of how functional languages and object-oriented languages an combine their strengths. We retain all the encapsulation of the object-oriented approach (although u.lastName and u.firstName appear to be fields, they are in fact accessor methods), but we also have the power of higher abstraction levels from the functional world (in this case, the map operation).

==Lazy Evaluation==
The final feature I'd like to touch upon is lazy evaluation. One of the many implications of lazy evaluation is that we can now program using infinite data structures; we define a way in which deeper parts of the data structure are calculated from the existing parts, and only lazily evaluate parts of the structure as they are accessed. This allows us to express algorithms quite concisely. This can be used in a variety of cases like random number generation, methods of successive approximation (like Newton's Method), fractal calculations, and generation of infinite series, as seen in the numerical methods or, more simply, the Fibonacci sequence. Because it is so well known, I will use the Fibonacci sequence as an example here. First, in Java:

public long fib(int k) {
if (k <= 2) {
return 1;
} else {
return fib(k-1) + fib(k-2);
}
}

This is a short, inefficient, recursive solution. It doesn't cache answers, either in a single call or across calls, which means it performs a huge amount of redundant computation. So it has a number of problems, but it is concise.

In Scala, we can remedy all those problems and remain concise using a [http://www.scala-lang.org/docu/files/api/scala/Stream.html Stream], a lazily evaluated form of a List:

val fibs: Stream[Int] = Stream(0,1) append fibs.zip(fibs.drop(1)).map(x => x._1 + x._2)

This definition is concise, offers automatic memoization and is thread-safe. To add those features to the Java code would require 20 lines of additional code at a minimum. It returns a Stream that can be queried for the kth Fibonacci number in the same way as the fib method defined in Java could, but calculates the 92rd Fibonacci in a fraction of a second.

=Conclusion=
Unfortunately, this article barely scratches the surface of the topic. There are decades of research and experience that have gone into modern programming languages, and the way in which they blend various programming paradigms blurs what were once quite distinct borders in the landscape of programming languages. But, that blurring has allowed these modern languages to offer programmers a bigger set of tools that aren't merely an amalgamation of features from every language, but a carefully crafted blend of features that enhance the expressiveness of these languages while not substantially increasing the syntax or API surface area.

=Glossary=

; Dynamic Dispatch
: The ability of a language to determine at runtime which implementation of a method should be executed. In object-oriented languages, this is usually on the basis of the object's class.

; Encapsulation
: The technique of enclosing the data and behavior of an object that are artifacts of its implementation, exposing only behaviors (and data) needed to satisfy its external contract.

; Immutability
: The property of an object that disallows the object from being changed after it is constructed. Immutability is often desireable in applications where the object will be used in highly parallel environments (e.g. many threads, over a network, etc.)

; Polymorphism
: Literally, "many forms"; the technique of using multiple implementations of the same contract (or interface) to enable compenents of a piece of software to be interchanged easily.

; Recursion
: A methodology for defining an algorithm or data structure in terms of itself. Often involves a direct self-referential call with a regressing value that is checked before the recursive call is performed, thus terminating the recursion.

=Further Reading=
If you want to know more about hybrid languages, its best to choose one (or a few!) and read about what they offer. If you're familiar with Java, or C#, take a look at the [http://www.scala-lang.org/node/104 tour of Scala] or perhaps some of the [http://www.fandev.org/doc/docIntro/StartHere.html features of Fan].

There are also a few major dynamically typed hybrid languages. Chief among these is [http://python.org Python], which has several implementations in [http://python.org C], [http://jython.org/ Java] and [http://codespeak.net/pypy/dist/pypy/doc/ Python](!). [http://ruby-lang.org Ruby] is also a newer hybrid language, originating in Japan, but was made famous worldwide because of its [http://rubyonrails.org/ Rails] web programming framework that was possible in large part due to its hybrid nature. It also has a [http://jruby.org/ Java implementation]. Finally, if you're working on the JVM an want a hybrid, dynamically-typed language with syntax that is close to Java's, [http://groovy.codehaus.org/ Groovy] is your best bet.

If you're very interested in performance, Common Lisp may have something to offer you, and there are [http://www.sbcl.org/ several] [http://www.cons.org/cmucl/ performant] [http://clisp.cons.org/ implementations]. If you want to learn more about why hybrid languages are so powerful, Paul Graham's book [http://www.paulgraham.com/onlisp.html On Lisp] explains why. If you really care about using the power of the JVM and are doing concurrent programming, a very modern lisp called [http://clojure.org Clojure] will be very interesting.

CSC/ECE 517 Fall 2009/wiki2 6 rp

2009-10-14T05:25:09Z

7r3ad: Added glossary.

=Topic=

While Smalltalk and Java were instrumental in bringing object-oriented programming into the mainstream, the 1990s also saw the development of hybrid languages that supported multiple programming paradigms, often combining procedural, object-oriented and functional approaches. Discuss the development and design considerations that went into languages like OCaml, Scala, F# and Fan, and how they build upon an object-oriented foundation to offer languages that offer type safety while maintaining brevity and expressive power.

=Introduction=

There are many ways to classify programming languages: on the basis of static or dynamic typing, type safety, high or low levels of abstraction, and by programming paradigm.

In this article, the focus is on programming paradigms, which can loosely be thought of as defining the atomic units a language offers as building block with which to build programs. There are three primary paradigms in use today:

* [http://en.wikipedia.org/wiki/Procedural_programming Procedural]
* [http://en.wikipedia.org/wiki/Object-oriented_programming Object-Oriented]
* [http://en.wikipedia.org/wiki/Declarative_programming Declarative]

Declarative languages span a wide array of programming styles. For simplicity in this article, we will focus on [http://en.wikipedia.org/wiki/Functional_programming functional] languages, which are an important subset of declarative languages.

Many languages provide only one of the paradigms to their users. [http://www.engin.umd.umich.edu/CIS/course.des/cis400/fortran/fortran.html FORTRAN], [http://www.engin.umd.umich.edu/CIS/course.des/cis400/cobol/cobol.html COBOL], [http://en.wikipedia.org/wiki/Pascal_%28programming_language%29 Pascal], [http://cm.bell-labs.com/cm/cs/who/dmr/chist.html C] and [http://en.wikipedia.org/wiki/BASIC BASIC] are all procedural, [http://www.engin.umd.umich.edu/CIS/course.des/cis400/simula/simula.html Simula], [http://www.smalltalk.org/main/ Smalltalk]] and [http://www.eiffel.com/developers/design_by_contract.html Eiffel] are object-oriented and [http://haskell.org/ Haskell] and [http://en.wikipedia.org/wiki/ML_%28programming_language%29 ML] are functional. These languages provide a single paradigm for programming, which limits programmers to the particular set of constructs available in that model.

The three paradigms evolved somewhat independently and offer unique constructs with which to solve programming problems. Some languages are multi-paradigm, however, and allow a programmer to use the tools most fitting for the problem at hand, sometimes mixing and matching freely within a single program. The original language of this type is Lisp, which dates back to the mid-1950s. In the last 20 years, many other hybrid languages have emerged, often derivatives of existing languages. C++ is derived from C, and offers both procedural and object-oriented approaches. [http://java.sun.com Java], one of the most widely used languages today, offers both procedural and object-oriented paradigms as well. [http://caml.inria.fr/ OCaml] is derived from ML, and offers functional and object-oriented styles. There are many others that have become popular in recent years, like [http://python.org Python] and [http://www.ruby-lang.org/en/ Ruby].

In this article, our goal is to examine what these hybrid languages offer above and beyond strictly object-oriented languages. In particular, we will examine the features of object-oriented languages and functional languages, and how they have been blended in a modern hybrid language called [http://scala-lang.org Scala].

=Features of Object Oriented Languages=
The key construct provided by object-oriented languages is the ''object'', which bundles the data and behavior together into a cohesive unit.

==Encapsulation==
Encapsulation is the technique of rolling behavior and data into an object that exhibits (and is handled in terms of) a particular behavior, rather than a particular composition. This technique allows the internals of an object to remain hidden from external entities, which in turn enables the object to modify its implementation over time while providing the same external behaviors.

For example, encapsulation would allow a class to add logging functionality without affecting other classes' collaboration with it. Any feature that is solely an implementation concern (speeding up a sorting algorithm, checking inputs for invalid data, changing the way resource errors are handled, etc.) can be evolved and modified over time within the object without breaking functionality elsewhere in the program that relies on the object in question.

==Dependency Inversion==

One of the major benefits of focusing on the ''behavior'' of objects rather than their ''implementation'' is that the behavior aspects can be well defined and captured in an interface. This allows code that once would rely on an unstable implementation to instead shift its dependency onto a stable interface, and have the implementation then implement the interface. This process is known as ''dependency inversion'', because of the way in which it alter the dependency structure of the code.

For example, let us say we have a web server that makes use of a logging facility to log information to disk. In this case, the web server depends on the logging facility:

[[Image:server-logger.png]]

Later, it becomes apparent that the web server also want to be able to log to other destinations. To facilitate this, we introduce a ''Logger'' interface, and make have the web server depend on that, so as to insulate it from new types of loggers that may be introduced. This allows us to modify both the server and the loggers in isolation, having them both depend on the interface rather than each other, essentially reversing, or ''inverting'' the dependency diagram.

[[Image:server-logger-invert.png]]

In this diagram, the behavior of the logger is well-defined and stable, and is captured in the interface represented by the yellow box. The blue boxes are classes that are implementations, and are insulated from one another by the interface, allowing them to vary independently without breaking the program as a whole. This is an example of the robustness that the object-oriented approach lends to a program through use of encapsulation.

==Polymorphism and Dynamic Dispatch==

The object-oriented approach of thinking in terms of behavior lends itself to have multiple implementations of a single behavior. We can see this is the case of the logger above. To the web server, a logger is simply an object with which logs can be stored. There are many possible implementations; we could use the file logger or the network logger as seen above, but we could also implement a console logger or a database logger. Essentially, this means that the web server could call a method to log information without any knowledge of exactly what kind of object it was calling. The raises the question of how (and when) a programming language decides which log method to call. Is it compiled in, or is it determined at runtime?

The answer is that it is determined at runtime. This type of ''late binding'' allows a program to remain flexible even after it is deployed, permitting end-users to determine what kind of logging functionality they want be passing in various implementations of the logger interface when the web server is run, even implementations that were written ''after'' the web server was written and deployed! This kind of flexibility is a result of ''polymorphism'', which simply means that the an interface (like the logger interface in our example) can have ''many forms'', or implementations. The way the language determines which one to invoke is through ''dynamic dispatch'', which is essentially a lookup table maintained as the program runs that maps calls to methods like logging to the implementations specified.

The major theme here is that the object-oriented approach of favoring encapsulation has many effects that ripple throughout the design process, almost all of which allow programmers to reduce the brittleness of their software by delaying commitment to particular implementations.

=Features of Functional Languages=

Much like object-oriented languages, functional languages offer a dominant paradigm that has far-reaching consequences in software design. For object-oriented languages, that element is encapsulation, and for functional languages, it is that functions are first-class entities, which simply means that functions are treated just like any other value in the language. This allows them to be passed as parameters, delayed, composed, invoked, and returned from other functions. But what is a function?

A function's most notable trait is that it is free of ''side-effects'', or state changes to the program that occur as a result of its execution. We could say a lot about side effects, but the general rule is that a function will always return the same value given the same input. This means that functions are ''stateless''. Therefore, entities like random number generators and loggers are not functional, because they either store state or have some effect that is not related to the value they return. Another way to think of functions is that they are completely defined in terms of their input and output.

From this simple feature flows many characteristic language features. We will discuss them in turn.

==Immutability==
Maybe the most noticeable feature (or restriction) to programmers of languages that are not functional, [http://en.wikipedia.org/wiki/Immutable_object immutability] is one of the hallmarks of a functional language. Most non-functional languages allow ''assignment'', or the ability to assign new values to variables as the program runs. In functional programming, a value is declared only once and then never changes. This feature of of the language flows out of the notion that functions have no side-effects, and is often viewed as more of a restriction than a feature.

The power of immutability comes from the fact that programs that fully utilize immutability are much simpler than those that do not, making them amenable to automated analysis by a computer. Computers can then prove various properties about function programs, like concurrent behavior (presence or absence of deadlock/livelock), memory usage, and what within what bounds various values in the program will lie.

==Higher Order Functions==

Higher order functions are simply functions that accept or return other functions as values. This is made possible because functions are treated as first-class entities, and allows very expressive implementations of many algorithms to be written.

There are several hallmark higher order functions: map, reduce, fold left/right and filter are a few examples. Going into the intricacies of each is beyond the scope of this article, but Abelson and Sussman's seminal [http://mitpress.mit.edu/sicp/ Structure and Interpretation of Computer Programs] has an [http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-12.html#%_sec_1.3.1 excellent treatment] of the subject.

==Recursion==

Programmers that are new to functional programming often balk at the notion that values cannot change over time (as variables do in imperative languages). If values cannot change, how can we execute loops?

The answer lies in recursion, where values are immutable, and loops are implemented as successive calls to the current function with new arguments. The avoids the complexity of having values change over time while offering all the power of the loops we often see in imperative languages (for...each, do...while, etc.) Again, a deep treatment of these language features is beyond the scope of this article, but again, Abelson and Sussman have [http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.1 addressed] the topic at some length in their book.

==Delayed (Lazy) Evaluation==
An extremely powerful feature of functional programming that is enabled by immutability is ''lazy evaluation''. This simply means that expressions can be defined, even recursively, and are not computed until the values that would result from that computation are needed. This is possible because values in functional programs don't change over time, which means expressions can be evaluated at any point in time as needed.

Take an imperative expression like this (in Java):

int i = 4;
int j = i + 3;
i++;

If you evaluate these expressions in order, j will be equal to 7, but if you were to delay the evaluation of j until after the third line, j would be equal to 8. This is a very simple example of how variables that change over time require expressions be evaluated in a particular order to maintain the correctness of the program. Functional programming explicitly disallows the third line, and therefore enables the value of j to be calculated only when it is needed. The implications of this are significant, as we'll see in the next section.

=Hybrid Object-Oriented/Functional Languages=

To programmers of languages like SmallTalk, Simula and Java, many of the features provided in functional languages will seem foreign or strange. But, as discussed, there are significant advantages to the functional approach for certain types of programs. While the object-oriented paradigm has proven itself to be very useful, many modern languages have sought to integrate functional features as well to increase the expressiveness and power of the language. One such language is Scala, which, like Java, runs on the Java Virtual Machine (JVM), and is thus shares Java's libraries and portability while offering many [http://www.ibm.com/developerworks/java/library/j-scala01228.html functional features] that are not available in object-oriented languages like Java. In the [http://www.scala-lang.org/node/25 overview] of Scala available on its homepage, Scala is briefly described:

<blockquote>
[Scala] smoothly integrates features of object-oriented and functional languages, enabling Java and other programmers to be more productive. Code sizes are typically reduced by a factor of two to three when compared to an equivalent Java application."
</blockquote>
How does Scala allow code sizes to be reduced so much? It uses sophisticated type inferencing to reduce type signature redundancy, allows for functional programming constructs to be used, and provides syntax for oft-used programming idioms. Essentially, it takes the lessons learned from decades of functional and object-oriented programming experience and rolls them into a modern hybrid language that can make full use legacy Java code.

Scala is representative of an entire class of hybrid object/functional languages like OCaml, F# and Fan, and therefore makes a good language for use in the examples in this article. The intent is not to present highly technical examples, but rather to give readers an impression of how hybrid languages increase expressive power over their single-paradigm counterparts.

==Case Classes==
Idiomatic object-oriented programming involves encapsulation of data, as previously discussed. In older object-oriented languages, this required defining internal data values, and then providing necessary get and set methods to access and/or modify those values. Here is an example a class in Java that provides only get methods for some (immutable) values it holds. It includes all the methods that ''should'' be included in such a class, including a toString, equals and hashCode method. Note that is an error if such methods are ''not'' included in structural Java classes, which is why I include them here.

public class UserData {
private final String firstName;
private final String lastName;
private final Integer age;
public UserData(String firstName, String lastName, Integer age) {
this.firstName = firstName;
this.lastName = lastName;
this.age = age;
}
public String getFirstName() {
return this.firstName;
}
public String getLastName() {
return this.lastName;
}
public Integer getAge() {
return this.age;
}
@Override
public boolean equals(Object obj) {
if (obj == null) {
return false;
}
if (getClass() != obj.getClass()) {
return false;
}
final UserData other = (UserData) obj;
if ((this.firstName == null) ? (other.firstName != null) : !this.firstName.equals(other.firstName)) {
return false;
}
if ((this.lastName == null) ? (other.lastName != null) : !this.lastName.equals(other.lastName)) {
return false;
}
if (this.age != other.age && (this.age == null || !this.age.equals(other.age))) {
return false;
}
return true;
}
@Override
public int hashCode() {
int hash = 7;
hash = 19 * hash + (this.firstName != null ? this.firstName.hashCode() : 0);
hash = 19 * hash + (this.lastName != null ? this.lastName.hashCode() : 0);
hash = 19 * hash + (this.age != null ? this.age.hashCode() : 0);
return hash;
}
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("UserData[firstName: ");
sb.append(this.firstName);
sb.append(" lastName: ");
sb.append(this.lastName);
sb.append(" age: ");
sb.append(this.age);
sb.append("]");
return sb.toString();
}
}

In Scala, ''all'' the functionality of the above class can be expressed with:

case class UserData(val firstName: String, val lastName: String, val age: Int)

To reiterate, the version in Scala actually does include a constructor, accessor methods, three fields that can only be set once, equals and hashCode methods (comparing the structural equality of the two instances of the class), as well a meaningful toString method which prints the fields.

There are numerous other benefits in using case classes, including automatic destructuring in pattern matching. We will discuss these features in the next section.

This feature by itself vastly reduces both development and maintenance burden for developers. Classes in Scala are defined in lines, rather than entire files. All the potential errors that could creep into that code are removed, and the ''intent'' of the developer is very clear.

==Destructuring Binds and Pattern Matching==
Lisp, one of the earliest hybrid languages, offered primarily functional features with object-orientation built on top (in a system called CLOS). One piece of functionality written with Common Lisp's metaprogramming facility was the ability to execute [http://www.ai.mit.edu/projects/iiip/doc/CommonLISP/HyperSpec/Body/mac_destructuring-bind.html destructuring binds], which are a powerful way of checking for a particular type ([http://en.wikipedia.org/wiki/Pattern_matching pattern matching]) and simultaneously extracting values from the inside of that type to use them in some computation. In the spirit of Common Lisp, Scala also offers destructuring binds and pattern matching. Let's take a look at what they can do for us.

Let us suppose we want to make use of our UserData class, defined above. We want to find all users with ages over 18 and store their names in a database. If we were to write a method that would simply do the database store for a single user, it might look like this:

public void storeName(UserData user) {
Integer age = user.getAge();
if (age > 18) {
recordToDatabase(user.lastName, user.firstName);
}
}

In Scala, this would be a trivial pattern match, with a destructuring bind to capture the fields inside the UserData (in this case, we bind them to f, l and a):

def storeName(user:UserData) = user match {
case UserData(f, l, a) if a > 18 => recordToDatabase(l, a)
}

In this case, we don't get an enourmous savings in terms of the number of lines of code used, but we gain tremendously in expressive power. Let's say we wanted to do the same thing, but not include users named "Bob". In Java:

public void storeName(UserData user) {
String firstName = user.getFirstName();
if (firstName != "Bob") {
Integer age = user.getAge();
if (age > 18) {
recordToDatabase(user.lastName, user.firstName);
}
}
}

And now in Scala:

def storeName(user:UserData) = user match {
case UserData(f, l, a) if a > 18 && f != "Bob" => recordToDatabase(l, a)
}

Hopefully this provides a little bit of insight into how destructuring can improve the expressiveness of your code. A more in depth discussion on pattern matching and binding can be be found in [http://www.codecommit.com/blog/scala/scala-for-java-refugees-part-4 Part 4] of Code Commit's series "Scala For Java Refugees".

==List Comprehension==
In imperative languages (including both procedural and object-oriented languages), it is common to loop very often, either with a for loop or a while loop. Hybrid languages allow for this, and also incorporate more abstract operations on structures seen in functional programming.

For example, suppose we wanted to take in a structure containing a bunch of UserData objects, and return a list of strings, containing the last name, a comma, and then the first name of each user.

In Java, this might look like this:

public ArrayList<String> toStrings(ArrayList<UserData> users) {
ArrayList<String> returnedList = new ArrayList<String>();
for (UserData u : users) {
returnedList.add(u.getLastName() + ", " + u.firstName);
}
return returnedList;
}

In the seven lines of code, only the method declaration and the add to the new list really have anything to do with the business logic. In Scala, that boiler plate can be avoided:

def toStrings(users: List[UserData]) = users.map(u => u.lastName + ", " + u.firstName)

This method definition is so short that it is arguable we shouldn't even define the method, and should simply use the map operation inline:

users.map(u => u.lastName + ", " + u.firstName)

This is a small demonstration of how functional languages and object-oriented languages an combine their strengths. We retain all the encapsulation of the object-oriented approach (although u.lastName and u.firstName appear to be fields, they are in fact accessor methods), but we also have the power of higher abstraction levels from the functional world (in this case, the map operation).

==Lazy Evaluation==
The final feature I'd like to touch upon is lazy evaluation. One of the many implications of lazy evaluation is that we can now program using infinite data structures; we define a way in which deeper parts of the data structure are calculated from the existing parts, and only lazily evaluate parts of the structure as they are accessed. This allows us to express algorithms quite concisely. This can be used in a variety of cases like random number generation, methods of successive approximation (like Newton's Method), fractal calculations, and generation of infinite series, as seen in the numerical methods or, more simply, the Fibonacci sequence. Because it is so well known, I will use the Fibonacci sequence as an example here. First, in Java:

public long fib(int k) {
if (k <= 2) {
return 1;
} else {
return fib(k-1) + fib(k-2);
}
}

This is a short, inefficient, recursive solution. It doesn't cache answers, either in a single call or across calls, which means it performs a huge amount of redundant computation. So it has a number of problems, but it is concise.

In Scala, we can remedy all those problems and remain concise using a [http://www.scala-lang.org/docu/files/api/scala/Stream.html Stream], a lazily evaluated form of a List:

val fibs: Stream[Int] = Stream(0,1) append fibs.zip(fibs.drop(1)).map(x => x._1 + x._2)

This definition is concise, offers automatic memoization and is thread-safe. To add those features to the Java code would require 20 lines of additional code at a minimum. It returns a Stream that can be queried for the kth Fibonacci number in the same way as the fib method defined in Java could, but calculates the 92rd Fibonacci in a fraction of a second.

=Conclusion=
Unfortunately, this article barely scratches the surface of the topic. There are decades of research and experience that have gone into modern programming languages, and the way in which they blend various programming paradigms blurs what were once quite distinct borders in the landscape of programming languages. But, that blurring has allowed these modern languages to offer programmers a bigger set of tools that aren't merely an amalgamation of features from every language, but a carefully crafted blend of features that enhance the expressiveness of these languages while not substantially increasing the syntax or API surface area.

=Glossary=

; Dynamic Dispatch
: The ability of a language to determine at runtime which implementation of a method should be executed. In object-oriented languages, this is usually on the basis of the object's class.

; Encapsulation
: The technique of enclosing the data and behavior of an object that are artifacts of its implementation, exposing only behaviors (and data) needed to satisfy its external contract.

; Immutability
: The property of an object that disallows the object from being changed after it is constructed. Immutability is often desireable in applications where the object will be used in highly parallel environments (e.g. many threads, over a network, etc.)

; Polymorphism
: Literally, "many forms"; the technique of using multiple implementations of the same contract (or interface) to enable compenents of a piece of software to be interchanged easily.

; Recursion
: A methodology for defining an algorithm or data structure in terms of itself. Often involves a direct self-referential call with a regressing value that is checked before the recursive call is performed, thus terminating the recursion.

=Further Reading=
If you want to know more about hybrid languages, its best to choose one (or a few!) and read about what they offer. If you're familiar with Java, or C#, take a look at the [http://www.scala-lang.org/node/104 tour of Scala] or perhaps some of the [http://www.fandev.org/doc/docIntro/StartHere.html features of Fan].

There are also a few major dynamically typed hybrid languages. Chief among these is [http://python.org Python], which has several implementations in [http://python.org C], [http://jython.org/ Java] and [http://codespeak.net/pypy/dist/pypy/doc/ Python](!). [http://ruby-lang.org Ruby] is also a newer hybrid language, originating in Japan, but was made famous worldwide because of its [http://rubyonrails.org/ Rails] web programming framework that was possible in large part due to its hybrid nature. It also has a [http://jruby.org/ Java implementation]. Finally, if you're working on the JVM an want a hybrid, dynamically-typed language with syntax that is close to Java's, [http://groovy.codehaus.org/ Groovy] is your best bet.

If you're very interested in performance, Common Lisp may have something to offer you, and there are [http://www.sbcl.org/ several] [http://www.cons.org/cmucl/ performant] [http://clisp.cons.org/ implementations]. If you want to learn more about why hybrid languages are so powerful, Paul Graham's book [http://www.paulgraham.com/onlisp.html On Lisp] explains why. If you really care about using the power of the JVM and are doing concurrent programming, a very modern lisp called [http://clojure.org Clojure] will be very interesting.

CSC/ECE 517 Fall 2009/wiki2 6 rp

2009-10-12T06:55:59Z

7r3ad:

=Author's Note=
Apologies. This has been here since 9 October, but I was editing under the wrong account. I made a change with the correct account, but it was a whitespace change that apparently didn't stick in a way that Expertiza picked up. I have just gone in and made a non-whitespace change, and things seem to be working now. I'm very sorry for taking so long to get this to appear.

=Topic=

While Smalltalk and Java were instrumental in bringing object-oriented programming into the mainstream, the 1990s also saw the development of hybrid languages that supported multiple programming paradigms, often combining procedural, object-oriented and functional approaches. Discuss the development and design considerations that went into languages like OCaml, Scala, F# and Fan, and how they build upon an object-oriented foundation to offer languages that offer type safety while maintaining brevity and expressive power.

=Introduction=

There are many ways to classify programming languages: on the basis of static or dynamic typing, type safety, high or low levels of abstraction, and by programming paradigm.

In this article, the focus is on programming paradigms, which can loosely be thought of as defining the atomic units a language offers as building block with which to build programs. There are three primary paradigms in use today:

* [http://en.wikipedia.org/wiki/Procedural_programming Procedural]
* [http://en.wikipedia.org/wiki/Object-oriented_programming Object-Oriented]
* [http://en.wikipedia.org/wiki/Declarative_programming Declarative]

Declarative languages span a wide array of programming styles. For simplicity in this article, we will focus on [http://en.wikipedia.org/wiki/Functional_programming functional] languages, which are an important subset of declarative languages.

Many languages provide only one of the paradigms to their users. [http://www.engin.umd.umich.edu/CIS/course.des/cis400/fortran/fortran.html FORTRAN], [http://www.engin.umd.umich.edu/CIS/course.des/cis400/cobol/cobol.html COBOL], [http://en.wikipedia.org/wiki/Pascal_%28programming_language%29 Pascal], [http://cm.bell-labs.com/cm/cs/who/dmr/chist.html C] and [http://en.wikipedia.org/wiki/BASIC BASIC] are all procedural, [http://www.engin.umd.umich.edu/CIS/course.des/cis400/simula/simula.html Simula], [http://www.smalltalk.org/main/ Smalltalk]] and [http://www.eiffel.com/developers/design_by_contract.html Eiffel] are object-oriented and [http://haskell.org/ Haskell] and [http://en.wikipedia.org/wiki/ML_%28programming_language%29 ML] are functional. These languages provide a single paradigm for programming, which limits programmers to the particular set of constructs available in that model.

The three paradigms evolved somewhat independently and offer unique constructs with which to solve programming problems. Some languages are multi-paradigm, however, and allow a programmer to use the tools most fitting for the problem at hand, sometimes mixing and matching freely within a single program. The original language of this type is Lisp, which dates back to the mid-1950s. In the last 20 years, many other hybrid languages have emerged, often derivatives of existing languages. C++ is derived from C, and offers both procedural and object-oriented approaches. [http://java.sun.com Java], one of the most widely used languages today, offers both procedural and object-oriented paradigms as well. [http://caml.inria.fr/ OCaml] is derived from ML, and offers functional and object-oriented styles. There are many others that have become popular in recent years, like [http://python.org Python] and [http://www.ruby-lang.org/en/ Ruby].

In this article, our goal is to examine what these hybrid languages offer above and beyond strictly object-oriented languages. In particular, we will examine the features of object-oriented languages and functional languages, and how they have been blended in a modern hybrid language called [http://scala-lang.org Scala].

=Features of Object Oriented Languages=
The key construct provided by object-oriented languages is the ''object'', which bundles the data and behavior together into a cohesive unit.

==Encapsulation==
Encapsulation is the technique of rolling behavior and data into an object that exhibits (and is handled in terms of) a particular behavior, rather than a particular composition. This technique allows the internals of an object to remain hidden from external entities, which in turn enables the object to modify its implementation over time while providing the same external behaviors.

For example, encapsulation would allow a class to add logging functionality without affecting other classes' collaboration with it. Any feature that is solely an implementation concern (speeding up a sorting algorithm, checking inputs for invalid data, changing the way resource errors are handled, etc.) can be evolved and modified over time within the object without breaking functionality elsewhere in the program that relies on the object in question.

==Dependency Inversion==

One of the major benefits of focusing on the ''behavior'' of objects rather than their ''implementation'' is that the behavior aspects can be well defined and captured in an interface. This allows code that once would rely on an unstable implementation to instead shift its dependency onto a stable interface, and have the implementation then implement the interface. This process is known as ''dependency inversion'', because of the way in which it alter the dependency structure of the code.

For example, let us say we have a web server that makes use of a logging facility to log information to disk. In this case, the web server depends on the logging facility:

[[Image:server-logger.png]]

Later, it becomes apparent that the web server also want to be able to log to other destinations. To facilitate this, we introduce a ''Logger'' interface, and make have the web server depend on that, so as to insulate it from new types of loggers that may be introduced. This allows us to modify both the server and the loggers in isolation, having them both depend on the interface rather than each other, essentially reversing, or ''inverting'' the dependency diagram.

[[Image:server-logger-invert.png]]

In this diagram, the behavior of the logger is well-defined and stable, and is captured in the interface represented by the yellow box. The blue boxes are classes that are implementations, and are insulated from one another by the interface, allowing them to vary independently without breaking the program as a whole. This is an example of the robustness that the object-oriented approach lends to a program through use of encapsulation.

==Polymorphism and Dynamic Dispatch==

The object-oriented approach of thinking in terms of behavior lends itself to have multiple implementations of a single behavior. We can see this is the case of the logger above. To the web server, a logger is simply an object with which logs can be stored. There are many possible implementations; we could use the file logger or the network logger as seen above, but we could also implement a console logger or a database logger. Essentially, this means that the web server could call a method to log information without any knowledge of exactly what kind of object it was calling. The raises the question of how (and when) a programming language decides which log method to call. Is it compiled in, or is it determined at runtime?

The answer is that it is determined at runtime. This type of ''late binding'' allows a program to remain flexible even after it is deployed, permitting end-users to determine what kind of logging functionality they want be passing in various implementations of the logger interface when the web server is run, even implementations that were written ''after'' the web server was written and deployed! This kind of flexibility is a result of ''polymorphism'', which simply means that the an interface (like the logger interface in our example) can have ''many forms'', or implementations. The way the language determines which one to invoke is through ''dynamic dispatch'', which is essentially a lookup table maintained as the program runs that maps calls to methods like logging to the implementations specified.

The major theme here is that the object-oriented approach of favoring encapsulation has many effects that ripple throughout the design process, almost all of which allow programmers to reduce the brittleness of their software by delaying commitment to particular implementations.

=Features of Functional Languages=

Much like object-oriented languages, functional languages offer a dominant paradigm that has far-reaching consequences in software design. For object-oriented languages, that element is encapsulation, and for functional languages, it is that functions are first-class entities, which simply means that functions are treated just like any other value in the language. This allows them to be passed as parameters, delayed, composed, invoked, and returned from other functions. But what is a function?

A function's most notable trait is that it is free of ''side-effects'', or state changes to the program that occur as a result of its execution. We could say a lot about side effects, but the general rule is that a function will always return the same value given the same input. This means that functions are ''stateless''. Therefore, entities like random number generators and loggers are not functional, because they either store state or have some effect that is not related to the value they return. Another way to think of functions is that they are completely defined in terms of their input and output.

From this simple feature flows many characteristic language features. We will discuss them in turn.

==Immutability==
Maybe the most noticeable feature (or restriction) to programmers of languages that are not functional, [http://en.wikipedia.org/wiki/Immutable_object immutability] is one of the hallmarks of a functional language. Most non-functional languages allow ''assignment'', or the ability to assign new values to variables as the program runs. In functional programming, a value is declared only once and then never changes. This feature of of the language flows out of the notion that functions have no side-effects, and is often viewed as more of a restriction than a feature.

The power of immutability comes from the fact that programs that fully utilize immutability are much simpler than those that do not, making them amenable to automated analysis by a computer. Computers can then prove various properties about function programs, like concurrent behavior (presence or absence of deadlock/livelock), memory usage, and what within what bounds various values in the program will lie.

==Higher Order Functions==

Higher order functions are simply functions that accept or return other functions as values. This is made possible because functions are treated as first-class entities, and allows very expressive implementations of many algorithms to be written.

There are several hallmark higher order functions: map, reduce, fold left/right and filter are a few examples. Going into the intricacies of each is beyond the scope of this article, but Abelson and Sussman's seminal [http://mitpress.mit.edu/sicp/ Structure and Interpretation of Computer Programs] has an [http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-12.html#%_sec_1.3.1 excellent treatment] of the subject.

==Recursion==

Programmers that are new to functional programming often balk at the notion that values cannot change over time (as variables do in imperative languages). If values cannot change, how can we execute loops?

The answer lies in recursion, where values are immutable, and loops are implemented as successive calls to the current function with new arguments. The avoids the complexity of having values change over time while offering all the power of the loops we often see in imperative languages (for...each, do...while, etc.) Again, a deep treatment of these language features is beyond the scope of this article, but again, Abelson and Sussman have [http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.1 addressed] the topic at some length in their book.

==Delayed (Lazy) Evaluation==
An extremely powerful feature of functional programming that is enabled by immutability is ''lazy evaluation''. This simply means that expressions can be defined, even recursively, and are not computed until the values that would result from that computation are needed. This is possible because values in functional programs don't change over time, which means expressions can be evaluated at any point in time as needed.

Take an imperative expression like this (in Java):

int i = 4;
int j = i + 3;
i++;

If you evaluate these expressions in order, j will be equal to 7, but if you were to delay the evaluation of j until after the third line, j would be equal to 8. This is a very simple example of how variables that change over time require expressions be evaluated in a particular order to maintain the correctness of the program. Functional programming explicitly disallows the third line, and therefore enables the value of j to be calculated only when it is needed. The implications of this are significant, as we'll see in the next section.

=Hybrid Object-Oriented/Functional Languages=

To programmers of languages like SmallTalk, Simula and Java, many of the features provided in functional languages will seem foreign or strange. But, as discussed, there are significant advantages to the functional approach for certain types of programs. While the object-oriented paradigm has proven itself to be very useful, many modern languages have sought to integrate functional features as well to increase the expressiveness and power of the language. One such language is Scala, which, like Java, runs on the Java Virtual Machine (JVM), and is thus shares Java's libraries and portability while offering many [http://www.ibm.com/developerworks/java/library/j-scala01228.html functional features] that are not available in object-oriented languages like Java. In the [http://www.scala-lang.org/node/25 overview] of Scala available on its homepage, Scala is briefly described:

<blockquote>
[Scala] smoothly integrates features of object-oriented and functional languages, enabling Java and other programmers to be more productive. Code sizes are typically reduced by a factor of two to three when compared to an equivalent Java application."
</blockquote>
How does Scala allow code sizes to be reduced so much? It uses sophisticated type inferencing to reduce type signature redundancy, allows for functional programming constructs to be used, and provides syntax for oft-used programming idioms. Essentially, it takes the lessons learned from decades of functional and object-oriented programming experience and rolls them into a modern hybrid language that can make full use legacy Java code.

Scala is representative of an entire class of hybrid object/functional languages like OCaml, F# and Fan, and therefore makes a good language for use in the examples in this article. The intent is not to present highly technical examples, but rather to give readers an impression of how hybrid languages increase expressive power over their single-paradigm counterparts.

==Case Classes==
Idiomatic object-oriented programming involves encapsulation of data, as previously discussed. In older object-oriented languages, this required defining internal data values, and then providing necessary get and set methods to access and/or modify those values. Here is an example a class in Java that provides only get methods for some (immutable) values it holds. It includes all the methods that ''should'' be included in such a class, including a toString, equals and hashCode method. Note that is an error if such methods are ''not'' included in structural Java classes, which is why I include them here.

public class UserData {
private final String firstName;
private final String lastName;
private final Integer age;
public UserData(String firstName, String lastName, Integer age) {
this.firstName = firstName;
this.lastName = lastName;
this.age = age;
}
public String getFirstName() {
return this.firstName;
}
public String getLastName() {
return this.lastName;
}
public Integer getAge() {
return this.age;
}
@Override
public boolean equals(Object obj) {
if (obj == null) {
return false;
}
if (getClass() != obj.getClass()) {
return false;
}
final UserData other = (UserData) obj;
if ((this.firstName == null) ? (other.firstName != null) : !this.firstName.equals(other.firstName)) {
return false;
}
if ((this.lastName == null) ? (other.lastName != null) : !this.lastName.equals(other.lastName)) {
return false;
}
if (this.age != other.age && (this.age == null || !this.age.equals(other.age))) {
return false;
}
return true;
}
@Override
public int hashCode() {
int hash = 7;
hash = 19 * hash + (this.firstName != null ? this.firstName.hashCode() : 0);
hash = 19 * hash + (this.lastName != null ? this.lastName.hashCode() : 0);
hash = 19 * hash + (this.age != null ? this.age.hashCode() : 0);
return hash;
}
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("UserData[firstName: ");
sb.append(this.firstName);
sb.append(" lastName: ");
sb.append(this.lastName);
sb.append(" age: ");
sb.append(this.age);
sb.append("]");
return sb.toString();
}
}

In Scala, ''all'' the functionality of the above class can be expressed with:

case class UserData(val firstName: String, val lastName: String, val age: Int)

To reiterate, the version in Scala actually does include a constructor, accessor methods, three fields that can only be set once, equals and hashCode methods (comparing the structural equality of the two instances of the class), as well a meaningful toString method which prints the fields.

There are numerous other benefits in using case classes, including automatic destructuring in pattern matching. We will discuss these features in the next section.

This feature by itself vastly reduces both development and maintenance burden for developers. Classes in Scala are defined in lines, rather than entire files. All the potential errors that could creep into that code are removed, and the ''intent'' of the developer is very clear.

==Destructuring Binds and Pattern Matching==
Lisp, one of the earliest hybrid languages, offered primarily functional features with object-orientation built on top (in a system called CLOS). One piece of functionality written with Common Lisp's metaprogramming facility was the ability to execute [http://www.ai.mit.edu/projects/iiip/doc/CommonLISP/HyperSpec/Body/mac_destructuring-bind.html destructuring binds], which are a powerful way of checking for a particular type ([http://en.wikipedia.org/wiki/Pattern_matching pattern matching]) and simultaneously extracting values from the inside of that type to use them in some computation. In the spirit of Common Lisp, Scala also offers destructuring binds and pattern matching. Let's take a look at what they can do for us.

Let us suppose we want to make use of our UserData class, defined above. We want to find all users with ages over 18 and store their names in a database. If we were to write a method that would simply do the database store for a single user, it might look like this:

public void storeName(UserData user) {
Integer age = user.getAge();
if (age > 18) {
recordToDatabase(user.lastName, user.firstName);
}
}

In Scala, this would be a trivial pattern match, with a destructuring bind to capture the fields inside the UserData (in this case, we bind them to f, l and a):

def storeName(user:UserData) = user match {
case UserData(f, l, a) if a > 18 => recordToDatabase(l, a)
}

In this case, we don't get an enourmous savings in terms of the number of lines of code used, but we gain tremendously in expressive power. Let's say we wanted to do the same thing, but not include users named "Bob". In Java:

public void storeName(UserData user) {
String firstName = user.getFirstName();
if (firstName != "Bob") {
Integer age = user.getAge();
if (age > 18) {
recordToDatabase(user.lastName, user.firstName);
}
}
}

And now in Scala:

def storeName(user:UserData) = user match {
case UserData(f, l, a) if a > 18 && f != "Bob" => recordToDatabase(l, a)
}

Hopefully this provides a little bit of insight into how destructuring can improve the expressiveness of your code. A more in depth discussion on pattern matching and binding can be be found in [http://www.codecommit.com/blog/scala/scala-for-java-refugees-part-4 Part 4] of Code Commit's series "Scala For Java Refugees".

==List Comprehension==
In imperative languages (including both procedural and object-oriented languages), it is common to loop very often, either with a for loop or a while loop. Hybrid languages allow for this, and also incorporate more abstract operations on structures seen in functional programming.

For example, suppose we wanted to take in a structure containing a bunch of UserData objects, and return a list of strings, containing the last name, a comma, and then the first name of each user.

In Java, this might look like this:

public ArrayList<String> toStrings(ArrayList<UserData> users) {
ArrayList<String> returnedList = new ArrayList<String>();
for (UserData u : users) {
returnedList.add(u.getLastName() + ", " + u.firstName);
}
return returnedList;
}

In the seven lines of code, only the method declaration and the add to the new list really have anything to do with the business logic. In Scala, that boiler plate can be avoided:

def toStrings(users: List[UserData]) = users.map(u => u.lastName + ", " + u.firstName)

This method definition is so short that it is arguable we shouldn't even define the method, and should simply use the map operation inline:

users.map(u => u.lastName + ", " + u.firstName)

This is a small demonstration of how functional languages and object-oriented languages an combine their strengths. We retain all the encapsulation of the object-oriented approach (although u.lastName and u.firstName appear to be fields, they are in fact accessor methods), but we also have the power of higher abstraction levels from the functional world (in this case, the map operation).

==Lazy Evaluation==
The final feature I'd like to touch upon is lazy evaluation. One of the many implications of lazy evaluation is that we can now program using infinite data structures; we define a way in which deeper parts of the data structure are calculated from the existing parts, and only lazily evaluate parts of the structure as they are accessed. This allows us to express algorithms quite concisely. This can be used in a variety of cases like random number generation, methods of successive approximation (like Newton's Method), fractal calculations, and generation of infinite series, as seen in the numerical methods or, more simply, the Fibonacci sequence. Because it is so well known, I will use the Fibonacci sequence as an example here. First, in Java:

public long fib(int k) {
if (k <= 2) {
return 1;
} else {
return fib(k-1) + fib(k-2);
}
}

This is a short, inefficient, recursive solution. It doesn't cache answers, either in a single call or across calls, which means it performs a huge amount of redundant computation. So it has a number of problems, but it is concise.

In Scala, we can remedy all those problems and remain concise using a [http://www.scala-lang.org/docu/files/api/scala/Stream.html Stream], a lazily evaluated form of a List:

val fibs: Stream[Int] = Stream(0,1) append fibs.zip(fibs.drop(1)).map(x => x._1 + x._2)

This definition is concise, offers automatic memoization and is thread-safe. To add those features to the Java code would require 20 lines of additional code at a minimum. It returns a Stream that can be queried for the kth Fibonacci number in the same way as the fib method defined in Java could, but calculates the 92rd Fibonacci in a fraction of a second.

=Conclusion=
Unfortunately, this article barely scratches the surface of the topic. There are decades of research and experience that have gone into modern programming languages, and the way in which they blend various programming paradigms blurs what were once quite distinct borders in the landscape of programming languages. But, that blurring has allowed these modern languages to offer programmers a bigger set of tools that aren't merely an amalgamation of features from every language, but a carefully crafted blend of features that enhance the expressiveness of these languages while not substantially increasing the syntax or API surface area.

=Further Reading=
If you want to know more about hybrid languages, its best to choose one (or a few!) and read about what they offer. If you're familiar with Java, or C#, take a look at the [http://www.scala-lang.org/node/104 tour of Scala] or perhaps some of the [http://www.fandev.org/doc/docIntro/StartHere.html features of Fan].

There are also a few major dynamically typed hybrid languages. Chief among these is [http://python.org Python], which has several implementations in [http://python.org C], [http://jython.org/ Java] and [http://codespeak.net/pypy/dist/pypy/doc/ Python](!). [http://ruby-lang.org Ruby] is also a newer hybrid language, originating in Japan, but was made famous worldwide because of its [http://rubyonrails.org/ Rails] web programming framework that was possible in large part due to its hybrid nature. It also has a [http://jruby.org/ Java implementation]. Finally, if you're working on the JVM an want a hybrid, dynamically-typed language with syntax that is close to Java's, [http://groovy.codehaus.org/ Groovy] is your best bet.

If you're very interested in performance, Common Lisp may have something to offer you, and there are [http://www.sbcl.org/ several] [http://www.cons.org/cmucl/ performant] [http://clisp.cons.org/ implementations]. If you want to learn more about why hybrid languages are so powerful, Paul Graham's book [http://www.paulgraham.com/onlisp.html On Lisp] explains why. If you really care about using the power of the JVM and are doing concurrent programming, a very modern lisp called [http://clojure.org Clojure] will be very interesting.

CSC/ECE 517 Fall 2009/wiki2 6 rp

2009-10-12T06:55:44Z

7r3ad:

-Author's Note=
Apologies. This has been here since 9 October, but I was editing under the wrong account. I made a change with the correct account, but it was a whitespace change that apparently didn't stick in a way that Expertiza picked up. I have just gone in and made a non-whitespace change, and things seem to be working now. I'm very sorry for taking so long to get this to appear.

=Topic=

While Smalltalk and Java were instrumental in bringing object-oriented programming into the mainstream, the 1990s also saw the development of hybrid languages that supported multiple programming paradigms, often combining procedural, object-oriented and functional approaches. Discuss the development and design considerations that went into languages like OCaml, Scala, F# and Fan, and how they build upon an object-oriented foundation to offer languages that offer type safety while maintaining brevity and expressive power.

=Introduction=

There are many ways to classify programming languages: on the basis of static or dynamic typing, type safety, high or low levels of abstraction, and by programming paradigm.

In this article, the focus is on programming paradigms, which can loosely be thought of as defining the atomic units a language offers as building block with which to build programs. There are three primary paradigms in use today:

* [http://en.wikipedia.org/wiki/Procedural_programming Procedural]
* [http://en.wikipedia.org/wiki/Object-oriented_programming Object-Oriented]
* [http://en.wikipedia.org/wiki/Declarative_programming Declarative]

Declarative languages span a wide array of programming styles. For simplicity in this article, we will focus on [http://en.wikipedia.org/wiki/Functional_programming functional] languages, which are an important subset of declarative languages.

Many languages provide only one of the paradigms to their users. [http://www.engin.umd.umich.edu/CIS/course.des/cis400/fortran/fortran.html FORTRAN], [http://www.engin.umd.umich.edu/CIS/course.des/cis400/cobol/cobol.html COBOL], [http://en.wikipedia.org/wiki/Pascal_%28programming_language%29 Pascal], [http://cm.bell-labs.com/cm/cs/who/dmr/chist.html C] and [http://en.wikipedia.org/wiki/BASIC BASIC] are all procedural, [http://www.engin.umd.umich.edu/CIS/course.des/cis400/simula/simula.html Simula], [http://www.smalltalk.org/main/ Smalltalk]] and [http://www.eiffel.com/developers/design_by_contract.html Eiffel] are object-oriented and [http://haskell.org/ Haskell] and [http://en.wikipedia.org/wiki/ML_%28programming_language%29 ML] are functional. These languages provide a single paradigm for programming, which limits programmers to the particular set of constructs available in that model.

The three paradigms evolved somewhat independently and offer unique constructs with which to solve programming problems. Some languages are multi-paradigm, however, and allow a programmer to use the tools most fitting for the problem at hand, sometimes mixing and matching freely within a single program. The original language of this type is Lisp, which dates back to the mid-1950s. In the last 20 years, many other hybrid languages have emerged, often derivatives of existing languages. C++ is derived from C, and offers both procedural and object-oriented approaches. [http://java.sun.com Java], one of the most widely used languages today, offers both procedural and object-oriented paradigms as well. [http://caml.inria.fr/ OCaml] is derived from ML, and offers functional and object-oriented styles. There are many others that have become popular in recent years, like [http://python.org Python] and [http://www.ruby-lang.org/en/ Ruby].

In this article, our goal is to examine what these hybrid languages offer above and beyond strictly object-oriented languages. In particular, we will examine the features of object-oriented languages and functional languages, and how they have been blended in a modern hybrid language called [http://scala-lang.org Scala].

=Features of Object Oriented Languages=
The key construct provided by object-oriented languages is the ''object'', which bundles the data and behavior together into a cohesive unit.

==Encapsulation==
Encapsulation is the technique of rolling behavior and data into an object that exhibits (and is handled in terms of) a particular behavior, rather than a particular composition. This technique allows the internals of an object to remain hidden from external entities, which in turn enables the object to modify its implementation over time while providing the same external behaviors.

For example, encapsulation would allow a class to add logging functionality without affecting other classes' collaboration with it. Any feature that is solely an implementation concern (speeding up a sorting algorithm, checking inputs for invalid data, changing the way resource errors are handled, etc.) can be evolved and modified over time within the object without breaking functionality elsewhere in the program that relies on the object in question.

==Dependency Inversion==

One of the major benefits of focusing on the ''behavior'' of objects rather than their ''implementation'' is that the behavior aspects can be well defined and captured in an interface. This allows code that once would rely on an unstable implementation to instead shift its dependency onto a stable interface, and have the implementation then implement the interface. This process is known as ''dependency inversion'', because of the way in which it alter the dependency structure of the code.

For example, let us say we have a web server that makes use of a logging facility to log information to disk. In this case, the web server depends on the logging facility:

[[Image:server-logger.png]]

Later, it becomes apparent that the web server also want to be able to log to other destinations. To facilitate this, we introduce a ''Logger'' interface, and make have the web server depend on that, so as to insulate it from new types of loggers that may be introduced. This allows us to modify both the server and the loggers in isolation, having them both depend on the interface rather than each other, essentially reversing, or ''inverting'' the dependency diagram.

[[Image:server-logger-invert.png]]

In this diagram, the behavior of the logger is well-defined and stable, and is captured in the interface represented by the yellow box. The blue boxes are classes that are implementations, and are insulated from one another by the interface, allowing them to vary independently without breaking the program as a whole. This is an example of the robustness that the object-oriented approach lends to a program through use of encapsulation.

==Polymorphism and Dynamic Dispatch==

The object-oriented approach of thinking in terms of behavior lends itself to have multiple implementations of a single behavior. We can see this is the case of the logger above. To the web server, a logger is simply an object with which logs can be stored. There are many possible implementations; we could use the file logger or the network logger as seen above, but we could also implement a console logger or a database logger. Essentially, this means that the web server could call a method to log information without any knowledge of exactly what kind of object it was calling. The raises the question of how (and when) a programming language decides which log method to call. Is it compiled in, or is it determined at runtime?

The answer is that it is determined at runtime. This type of ''late binding'' allows a program to remain flexible even after it is deployed, permitting end-users to determine what kind of logging functionality they want be passing in various implementations of the logger interface when the web server is run, even implementations that were written ''after'' the web server was written and deployed! This kind of flexibility is a result of ''polymorphism'', which simply means that the an interface (like the logger interface in our example) can have ''many forms'', or implementations. The way the language determines which one to invoke is through ''dynamic dispatch'', which is essentially a lookup table maintained as the program runs that maps calls to methods like logging to the implementations specified.

The major theme here is that the object-oriented approach of favoring encapsulation has many effects that ripple throughout the design process, almost all of which allow programmers to reduce the brittleness of their software by delaying commitment to particular implementations.

=Features of Functional Languages=

Much like object-oriented languages, functional languages offer a dominant paradigm that has far-reaching consequences in software design. For object-oriented languages, that element is encapsulation, and for functional languages, it is that functions are first-class entities, which simply means that functions are treated just like any other value in the language. This allows them to be passed as parameters, delayed, composed, invoked, and returned from other functions. But what is a function?

A function's most notable trait is that it is free of ''side-effects'', or state changes to the program that occur as a result of its execution. We could say a lot about side effects, but the general rule is that a function will always return the same value given the same input. This means that functions are ''stateless''. Therefore, entities like random number generators and loggers are not functional, because they either store state or have some effect that is not related to the value they return. Another way to think of functions is that they are completely defined in terms of their input and output.

From this simple feature flows many characteristic language features. We will discuss them in turn.

==Immutability==
Maybe the most noticeable feature (or restriction) to programmers of languages that are not functional, [http://en.wikipedia.org/wiki/Immutable_object immutability] is one of the hallmarks of a functional language. Most non-functional languages allow ''assignment'', or the ability to assign new values to variables as the program runs. In functional programming, a value is declared only once and then never changes. This feature of of the language flows out of the notion that functions have no side-effects, and is often viewed as more of a restriction than a feature.

The power of immutability comes from the fact that programs that fully utilize immutability are much simpler than those that do not, making them amenable to automated analysis by a computer. Computers can then prove various properties about function programs, like concurrent behavior (presence or absence of deadlock/livelock), memory usage, and what within what bounds various values in the program will lie.

==Higher Order Functions==

Higher order functions are simply functions that accept or return other functions as values. This is made possible because functions are treated as first-class entities, and allows very expressive implementations of many algorithms to be written.

There are several hallmark higher order functions: map, reduce, fold left/right and filter are a few examples. Going into the intricacies of each is beyond the scope of this article, but Abelson and Sussman's seminal [http://mitpress.mit.edu/sicp/ Structure and Interpretation of Computer Programs] has an [http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-12.html#%_sec_1.3.1 excellent treatment] of the subject.

==Recursion==

Programmers that are new to functional programming often balk at the notion that values cannot change over time (as variables do in imperative languages). If values cannot change, how can we execute loops?

The answer lies in recursion, where values are immutable, and loops are implemented as successive calls to the current function with new arguments. The avoids the complexity of having values change over time while offering all the power of the loops we often see in imperative languages (for...each, do...while, etc.) Again, a deep treatment of these language features is beyond the scope of this article, but again, Abelson and Sussman have [http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.1 addressed] the topic at some length in their book.

==Delayed (Lazy) Evaluation==
An extremely powerful feature of functional programming that is enabled by immutability is ''lazy evaluation''. This simply means that expressions can be defined, even recursively, and are not computed until the values that would result from that computation are needed. This is possible because values in functional programs don't change over time, which means expressions can be evaluated at any point in time as needed.

Take an imperative expression like this (in Java):

int i = 4;
int j = i + 3;
i++;

If you evaluate these expressions in order, j will be equal to 7, but if you were to delay the evaluation of j until after the third line, j would be equal to 8. This is a very simple example of how variables that change over time require expressions be evaluated in a particular order to maintain the correctness of the program. Functional programming explicitly disallows the third line, and therefore enables the value of j to be calculated only when it is needed. The implications of this are significant, as we'll see in the next section.

=Hybrid Object-Oriented/Functional Languages=

To programmers of languages like SmallTalk, Simula and Java, many of the features provided in functional languages will seem foreign or strange. But, as discussed, there are significant advantages to the functional approach for certain types of programs. While the object-oriented paradigm has proven itself to be very useful, many modern languages have sought to integrate functional features as well to increase the expressiveness and power of the language. One such language is Scala, which, like Java, runs on the Java Virtual Machine (JVM), and is thus shares Java's libraries and portability while offering many [http://www.ibm.com/developerworks/java/library/j-scala01228.html functional features] that are not available in object-oriented languages like Java. In the [http://www.scala-lang.org/node/25 overview] of Scala available on its homepage, Scala is briefly described:

<blockquote>
[Scala] smoothly integrates features of object-oriented and functional languages, enabling Java and other programmers to be more productive. Code sizes are typically reduced by a factor of two to three when compared to an equivalent Java application."
</blockquote>
How does Scala allow code sizes to be reduced so much? It uses sophisticated type inferencing to reduce type signature redundancy, allows for functional programming constructs to be used, and provides syntax for oft-used programming idioms. Essentially, it takes the lessons learned from decades of functional and object-oriented programming experience and rolls them into a modern hybrid language that can make full use legacy Java code.

Scala is representative of an entire class of hybrid object/functional languages like OCaml, F# and Fan, and therefore makes a good language for use in the examples in this article. The intent is not to present highly technical examples, but rather to give readers an impression of how hybrid languages increase expressive power over their single-paradigm counterparts.

==Case Classes==
Idiomatic object-oriented programming involves encapsulation of data, as previously discussed. In older object-oriented languages, this required defining internal data values, and then providing necessary get and set methods to access and/or modify those values. Here is an example a class in Java that provides only get methods for some (immutable) values it holds. It includes all the methods that ''should'' be included in such a class, including a toString, equals and hashCode method. Note that is an error if such methods are ''not'' included in structural Java classes, which is why I include them here.

public class UserData {
private final String firstName;
private final String lastName;
private final Integer age;
public UserData(String firstName, String lastName, Integer age) {
this.firstName = firstName;
this.lastName = lastName;
this.age = age;
}
public String getFirstName() {
return this.firstName;
}
public String getLastName() {
return this.lastName;
}
public Integer getAge() {
return this.age;
}
@Override
public boolean equals(Object obj) {
if (obj == null) {
return false;
}
if (getClass() != obj.getClass()) {
return false;
}
final UserData other = (UserData) obj;
if ((this.firstName == null) ? (other.firstName != null) : !this.firstName.equals(other.firstName)) {
return false;
}
if ((this.lastName == null) ? (other.lastName != null) : !this.lastName.equals(other.lastName)) {
return false;
}
if (this.age != other.age && (this.age == null || !this.age.equals(other.age))) {
return false;
}
return true;
}
@Override
public int hashCode() {
int hash = 7;
hash = 19 * hash + (this.firstName != null ? this.firstName.hashCode() : 0);
hash = 19 * hash + (this.lastName != null ? this.lastName.hashCode() : 0);
hash = 19 * hash + (this.age != null ? this.age.hashCode() : 0);
return hash;
}
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("UserData[firstName: ");
sb.append(this.firstName);
sb.append(" lastName: ");
sb.append(this.lastName);
sb.append(" age: ");
sb.append(this.age);
sb.append("]");
return sb.toString();
}
}

In Scala, ''all'' the functionality of the above class can be expressed with:

case class UserData(val firstName: String, val lastName: String, val age: Int)

To reiterate, the version in Scala actually does include a constructor, accessor methods, three fields that can only be set once, equals and hashCode methods (comparing the structural equality of the two instances of the class), as well a meaningful toString method which prints the fields.

There are numerous other benefits in using case classes, including automatic destructuring in pattern matching. We will discuss these features in the next section.

This feature by itself vastly reduces both development and maintenance burden for developers. Classes in Scala are defined in lines, rather than entire files. All the potential errors that could creep into that code are removed, and the ''intent'' of the developer is very clear.

==Destructuring Binds and Pattern Matching==
Lisp, one of the earliest hybrid languages, offered primarily functional features with object-orientation built on top (in a system called CLOS). One piece of functionality written with Common Lisp's metaprogramming facility was the ability to execute [http://www.ai.mit.edu/projects/iiip/doc/CommonLISP/HyperSpec/Body/mac_destructuring-bind.html destructuring binds], which are a powerful way of checking for a particular type ([http://en.wikipedia.org/wiki/Pattern_matching pattern matching]) and simultaneously extracting values from the inside of that type to use them in some computation. In the spirit of Common Lisp, Scala also offers destructuring binds and pattern matching. Let's take a look at what they can do for us.

Let us suppose we want to make use of our UserData class, defined above. We want to find all users with ages over 18 and store their names in a database. If we were to write a method that would simply do the database store for a single user, it might look like this:

public void storeName(UserData user) {
Integer age = user.getAge();
if (age > 18) {
recordToDatabase(user.lastName, user.firstName);
}
}

In Scala, this would be a trivial pattern match, with a destructuring bind to capture the fields inside the UserData (in this case, we bind them to f, l and a):

def storeName(user:UserData) = user match {
case UserData(f, l, a) if a > 18 => recordToDatabase(l, a)
}

In this case, we don't get an enourmous savings in terms of the number of lines of code used, but we gain tremendously in expressive power. Let's say we wanted to do the same thing, but not include users named "Bob". In Java:

public void storeName(UserData user) {
String firstName = user.getFirstName();
if (firstName != "Bob") {
Integer age = user.getAge();
if (age > 18) {
recordToDatabase(user.lastName, user.firstName);
}
}
}

And now in Scala:

def storeName(user:UserData) = user match {
case UserData(f, l, a) if a > 18 && f != "Bob" => recordToDatabase(l, a)
}

Hopefully this provides a little bit of insight into how destructuring can improve the expressiveness of your code. A more in depth discussion on pattern matching and binding can be be found in [http://www.codecommit.com/blog/scala/scala-for-java-refugees-part-4 Part 4] of Code Commit's series "Scala For Java Refugees".

==List Comprehension==
In imperative languages (including both procedural and object-oriented languages), it is common to loop very often, either with a for loop or a while loop. Hybrid languages allow for this, and also incorporate more abstract operations on structures seen in functional programming.

For example, suppose we wanted to take in a structure containing a bunch of UserData objects, and return a list of strings, containing the last name, a comma, and then the first name of each user.

In Java, this might look like this:

public ArrayList<String> toStrings(ArrayList<UserData> users) {
ArrayList<String> returnedList = new ArrayList<String>();
for (UserData u : users) {
returnedList.add(u.getLastName() + ", " + u.firstName);
}
return returnedList;
}

In the seven lines of code, only the method declaration and the add to the new list really have anything to do with the business logic. In Scala, that boiler plate can be avoided:

def toStrings(users: List[UserData]) = users.map(u => u.lastName + ", " + u.firstName)

This method definition is so short that it is arguable we shouldn't even define the method, and should simply use the map operation inline:

users.map(u => u.lastName + ", " + u.firstName)

This is a small demonstration of how functional languages and object-oriented languages an combine their strengths. We retain all the encapsulation of the object-oriented approach (although u.lastName and u.firstName appear to be fields, they are in fact accessor methods), but we also have the power of higher abstraction levels from the functional world (in this case, the map operation).

==Lazy Evaluation==
The final feature I'd like to touch upon is lazy evaluation. One of the many implications of lazy evaluation is that we can now program using infinite data structures; we define a way in which deeper parts of the data structure are calculated from the existing parts, and only lazily evaluate parts of the structure as they are accessed. This allows us to express algorithms quite concisely. This can be used in a variety of cases like random number generation, methods of successive approximation (like Newton's Method), fractal calculations, and generation of infinite series, as seen in the numerical methods or, more simply, the Fibonacci sequence. Because it is so well known, I will use the Fibonacci sequence as an example here. First, in Java:

public long fib(int k) {
if (k <= 2) {
return 1;
} else {
return fib(k-1) + fib(k-2);
}
}

This is a short, inefficient, recursive solution. It doesn't cache answers, either in a single call or across calls, which means it performs a huge amount of redundant computation. So it has a number of problems, but it is concise.

In Scala, we can remedy all those problems and remain concise using a [http://www.scala-lang.org/docu/files/api/scala/Stream.html Stream], a lazily evaluated form of a List:

val fibs: Stream[Int] = Stream(0,1) append fibs.zip(fibs.drop(1)).map(x => x._1 + x._2)

This definition is concise, offers automatic memoization and is thread-safe. To add those features to the Java code would require 20 lines of additional code at a minimum. It returns a Stream that can be queried for the kth Fibonacci number in the same way as the fib method defined in Java could, but calculates the 92rd Fibonacci in a fraction of a second.

=Conclusion=
Unfortunately, this article barely scratches the surface of the topic. There are decades of research and experience that have gone into modern programming languages, and the way in which they blend various programming paradigms blurs what were once quite distinct borders in the landscape of programming languages. But, that blurring has allowed these modern languages to offer programmers a bigger set of tools that aren't merely an amalgamation of features from every language, but a carefully crafted blend of features that enhance the expressiveness of these languages while not substantially increasing the syntax or API surface area.

=Further Reading=
If you want to know more about hybrid languages, its best to choose one (or a few!) and read about what they offer. If you're familiar with Java, or C#, take a look at the [http://www.scala-lang.org/node/104 tour of Scala] or perhaps some of the [http://www.fandev.org/doc/docIntro/StartHere.html features of Fan].

There are also a few major dynamically typed hybrid languages. Chief among these is [http://python.org Python], which has several implementations in [http://python.org C], [http://jython.org/ Java] and [http://codespeak.net/pypy/dist/pypy/doc/ Python](!). [http://ruby-lang.org Ruby] is also a newer hybrid language, originating in Japan, but was made famous worldwide because of its [http://rubyonrails.org/ Rails] web programming framework that was possible in large part due to its hybrid nature. It also has a [http://jruby.org/ Java implementation]. Finally, if you're working on the JVM an want a hybrid, dynamically-typed language with syntax that is close to Java's, [http://groovy.codehaus.org/ Groovy] is your best bet.

If you're very interested in performance, Common Lisp may have something to offer you, and there are [http://www.sbcl.org/ several] [http://www.cons.org/cmucl/ performant] [http://clisp.cons.org/ implementations]. If you want to learn more about why hybrid languages are so powerful, Paul Graham's book [http://www.paulgraham.com/onlisp.html On Lisp] explains why. If you really care about using the power of the JVM and are doing concurrent programming, a very modern lisp called [http://clojure.org Clojure] will be very interesting.

CSC/ECE 517 Fall 2009/wiki2 6 rp

2009-10-12T06:52:58Z

7r3ad:

=Topic=

While Smalltalk and Java were instrumental in bringing object-oriented programming into the mainstream, the 1990s also saw the development of hybrid languages that supported multiple programming paradigms, often combining procedural, object-oriented and functional approaches. Discuss the development and design considerations that went into languages like OCaml, Scala, F# and Fan, and how they build upon an object-oriented foundation to offer languages that offer type safety while maintaining brevity and expressive power.

=Introduction=

There are many ways to classify programming languages: on the basis of static or dynamic typing, type safety, high or low levels of abstraction, and by programming paradigm.

In this article, the focus is on programming paradigms, which can loosely be thought of as defining the atomic units a language offers as building block with which to build programs. There are three primary paradigms in use today:

* [http://en.wikipedia.org/wiki/Procedural_programming Procedural]
* [http://en.wikipedia.org/wiki/Object-oriented_programming Object-Oriented]
* [http://en.wikipedia.org/wiki/Declarative_programming Declarative]

Declarative languages span a wide array of programming styles. For simplicity in this article, we will focus on [http://en.wikipedia.org/wiki/Functional_programming functional] languages, which are an important subset of declarative languages.

Many languages provide only one of the paradigms to their users. [http://www.engin.umd.umich.edu/CIS/course.des/cis400/fortran/fortran.html FORTRAN], [http://www.engin.umd.umich.edu/CIS/course.des/cis400/cobol/cobol.html COBOL], [http://en.wikipedia.org/wiki/Pascal_%28programming_language%29 Pascal], [http://cm.bell-labs.com/cm/cs/who/dmr/chist.html C] and [http://en.wikipedia.org/wiki/BASIC BASIC] are all procedural, [http://www.engin.umd.umich.edu/CIS/course.des/cis400/simula/simula.html Simula], [http://www.smalltalk.org/main/ Smalltalk]] and [http://www.eiffel.com/developers/design_by_contract.html Eiffel] are object-oriented and [http://haskell.org/ Haskell] and [http://en.wikipedia.org/wiki/ML_%28programming_language%29 ML] are functional. These languages provide a single paradigm for programming, which limits programmers to the particular set of constructs available in that model.

The three paradigms evolved somewhat independently and offer unique constructs with which to solve programming problems. Some languages are multi-paradigm, however, and allow a programmer to use the tools most fitting for the problem at hand, sometimes mixing and matching freely within a single program. The original language of this type is Lisp, which dates back to the mid-1950s. In the last 20 years, many other hybrid languages have emerged, often derivatives of existing languages. C++ is derived from C, and offers both procedural and object-oriented approaches. [http://java.sun.com Java], one of the most widely used languages today, offers both procedural and object-oriented paradigms as well. [http://caml.inria.fr/ OCaml] is derived from ML, and offers functional and object-oriented styles. There are many others that have become popular in recent years, like [http://python.org Python] and [http://www.ruby-lang.org/en/ Ruby].

In this article, our goal is to examine what these hybrid languages offer above and beyond strictly object-oriented languages. In particular, we will examine the features of object-oriented languages and functional languages, and how they have been blended in a modern hybrid language called [http://scala-lang.org Scala].

=Features of Object Oriented Languages=
The key construct provided by object-oriented languages is the ''object'', which bundles the data and behavior together into a cohesive unit.

==Encapsulation==
Encapsulation is the technique of rolling behavior and data into an object that exhibits (and is handled in terms of) a particular behavior, rather than a particular composition. This technique allows the internals of an object to remain hidden from external entities, which in turn enables the object to modify its implementation over time while providing the same external behaviors.

For example, encapsulation would allow a class to add logging functionality without affecting other classes' collaboration with it. Any feature that is solely an implementation concern (speeding up a sorting algorithm, checking inputs for invalid data, changing the way resource errors are handled, etc.) can be evolved and modified over time within the object without breaking functionality elsewhere in the program that relies on the object in question.

==Dependency Inversion==

One of the major benefits of focusing on the ''behavior'' of objects rather than their ''implementation'' is that the behavior aspects can be well defined and captured in an interface. This allows code that once would rely on an unstable implementation to instead shift its dependency onto a stable interface, and have the implementation then implement the interface. This process is known as ''dependency inversion'', because of the way in which it alter the dependency structure of the code.

For example, let us say we have a web server that makes use of a logging facility to log information to disk. In this case, the web server depends on the logging facility:

[[Image:server-logger.png]]

Later, it becomes apparent that the web server also want to be able to log to other destinations. To facilitate this, we introduce a ''Logger'' interface, and make have the web server depend on that, so as to insulate it from new types of loggers that may be introduced. This allows us to modify both the server and the loggers in isolation, having them both depend on the interface rather than each other, essentially reversing, or ''inverting'' the dependency diagram.

[[Image:server-logger-invert.png]]

In this diagram, the behavior of the logger is well-defined and stable, and is captured in the interface represented by the yellow box. The blue boxes are classes that are implementations, and are insulated from one another by the interface, allowing them to vary independently without breaking the program as a whole. This is an example of the robustness that the object-oriented approach lends to a program through use of encapsulation.

==Polymorphism and Dynamic Dispatch==

The object-oriented approach of thinking in terms of behavior lends itself to have multiple implementations of a single behavior. We can see this is the case of the logger above. To the web server, a logger is simply an object with which logs can be stored. There are many possible implementations; we could use the file logger or the network logger as seen above, but we could also implement a console logger or a database logger. Essentially, this means that the web server could call a method to log information without any knowledge of exactly what kind of object it was calling. The raises the question of how (and when) a programming language decides which log method to call. Is it compiled in, or is it determined at runtime?

The answer is that it is determined at runtime. This type of ''late binding'' allows a program to remain flexible even after it is deployed, permitting end-users to determine what kind of logging functionality they want be passing in various implementations of the logger interface when the web server is run, even implementations that were written ''after'' the web server was written and deployed! This kind of flexibility is a result of ''polymorphism'', which simply means that the an interface (like the logger interface in our example) can have ''many forms'', or implementations. The way the language determines which one to invoke is through ''dynamic dispatch'', which is essentially a lookup table maintained as the program runs that maps calls to methods like logging to the implementations specified.

The major theme here is that the object-oriented approach of favoring encapsulation has many effects that ripple throughout the design process, almost all of which allow programmers to reduce the brittleness of their software by delaying commitment to particular implementations.

=Features of Functional Languages=

Much like object-oriented languages, functional languages offer a dominant paradigm that has far-reaching consequences in software design. For object-oriented languages, that element is encapsulation, and for functional languages, it is that functions are first-class entities, which simply means that functions are treated just like any other value in the language. This allows them to be passed as parameters, delayed, composed, invoked, and returned from other functions. But what is a function?

A function's most notable trait is that it is free of ''side-effects'', or state changes to the program that occur as a result of its execution. We could say a lot about side effects, but the general rule is that a function will always return the same value given the same input. This means that functions are ''stateless''. Therefore, entities like random number generators and loggers are not functional, because they either store state or have some effect that is not related to the value they return. Another way to think of functions is that they are completely defined in terms of their input and output.

From this simple feature flows many characteristic language features. We will discuss them in turn.

==Immutability==
Maybe the most noticeable feature (or restriction) to programmers of languages that are not functional, [http://en.wikipedia.org/wiki/Immutable_object immutability] is one of the hallmarks of a functional language. Most non-functional languages allow ''assignment'', or the ability to assign new values to variables as the program runs. In functional programming, a value is declared only once and then never changes. This feature of of the language flows out of the notion that functions have no side-effects, and is often viewed as more of a restriction than a feature.

The power of immutability comes from the fact that programs that fully utilize immutability are much simpler than those that do not, making them amenable to automated analysis by a computer. Computers can then prove various properties about function programs, like concurrent behavior (presence or absence of deadlock/livelock), memory usage, and what within what bounds various values in the program will lie.

==Higher Order Functions==

Higher order functions are simply functions that accept or return other functions as values. This is made possible because functions are treated as first-class entities, and allows very expressive implementations of many algorithms to be written.

There are several hallmark higher order functions: map, reduce, fold left/right and filter are a few examples. Going into the intricacies of each is beyond the scope of this article, but Abelson and Sussman's seminal [http://mitpress.mit.edu/sicp/ Structure and Interpretation of Computer Programs] has an [http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-12.html#%_sec_1.3.1 excellent treatment] of the subject.

==Recursion==

Programmers that are new to functional programming often balk at the notion that values cannot change over time (as variables do in imperative languages). If values cannot change, how can we execute loops?

The answer lies in recursion, where values are immutable, and loops are implemented as successive calls to the current function with new arguments. The avoids the complexity of having values change over time while offering all the power of the loops we often see in imperative languages (for...each, do...while, etc.) Again, a deep treatment of these language features is beyond the scope of this article, but again, Abelson and Sussman have [http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.1 addressed] the topic at some length in their book.

==Delayed (Lazy) Evaluation==
An extremely powerful feature of functional programming that is enabled by immutability is ''lazy evaluation''. This simply means that expressions can be defined, even recursively, and are not computed until the values that would result from that computation are needed. This is possible because values in functional programs don't change over time, which means expressions can be evaluated at any point in time as needed.

Take an imperative expression like this (in Java):

int i = 4;
int j = i + 3;
i++;

If you evaluate these expressions in order, j will be equal to 7, but if you were to delay the evaluation of j until after the third line, j would be equal to 8. This is a very simple example of how variables that change over time require expressions be evaluated in a particular order to maintain the correctness of the program. Functional programming explicitly disallows the third line, and therefore enables the value of j to be calculated only when it is needed. The implications of this are significant, as we'll see in the next section.

=Hybrid Object-Oriented/Functional Languages=

To programmers of languages like SmallTalk, Simula and Java, many of the features provided in functional languages will seem foreign or strange. But, as discussed, there are significant advantages to the functional approach for certain types of programs. While the object-oriented paradigm has proven itself to be very useful, many modern languages have sought to integrate functional features as well to increase the expressiveness and power of the language. One such language is Scala, which, like Java, runs on the Java Virtual Machine (JVM), and is thus shares Java's libraries and portability while offering many [http://www.ibm.com/developerworks/java/library/j-scala01228.html functional features] that are not available in object-oriented languages like Java. In the [http://www.scala-lang.org/node/25 overview] of Scala available on its homepage, Scala is briefly described:

<blockquote>
[Scala] smoothly integrates features of object-oriented and functional languages, enabling Java and other programmers to be more productive. Code sizes are typically reduced by a factor of two to three when compared to an equivalent Java application."
</blockquote>
How does Scala allow code sizes to be reduced so much? It uses sophisticated type inferencing to reduce type signature redundancy, allows for functional programming constructs to be used, and provides syntax for oft-used programming idioms. Essentially, it takes the lessons learned from decades of functional and object-oriented programming experience and rolls them into a modern hybrid language that can make full use legacy Java code.

Scala is representative of an entire class of hybrid object/functional languages like OCaml, F# and Fan, and therefore makes a good language for use in the examples in this article. The intent is not to present highly technical examples, but rather to give readers an impression of how hybrid languages increase expressive power over their single-paradigm counterparts.

==Case Classes==
Idiomatic object-oriented programming involves encapsulation of data, as previously discussed. In older object-oriented languages, this required defining internal data values, and then providing necessary get and set methods to access and/or modify those values. Here is an example a class in Java that provides only get methods for some (immutable) values it holds. It includes all the methods that ''should'' be included in such a class, including a toString, equals and hashCode method. Note that is an error if such methods are ''not'' included in structural Java classes, which is why I include them here.

public class UserData {
private final String firstName;
private final String lastName;
private final Integer age;
public UserData(String firstName, String lastName, Integer age) {
this.firstName = firstName;
this.lastName = lastName;
this.age = age;
}
public String getFirstName() {
return this.firstName;
}
public String getLastName() {
return this.lastName;
}
public Integer getAge() {
return this.age;
}
@Override
public boolean equals(Object obj) {
if (obj == null) {
return false;
}
if (getClass() != obj.getClass()) {
return false;
}
final UserData other = (UserData) obj;
if ((this.firstName == null) ? (other.firstName != null) : !this.firstName.equals(other.firstName)) {
return false;
}
if ((this.lastName == null) ? (other.lastName != null) : !this.lastName.equals(other.lastName)) {
return false;
}
if (this.age != other.age && (this.age == null || !this.age.equals(other.age))) {
return false;
}
return true;
}
@Override
public int hashCode() {
int hash = 7;
hash = 19 * hash + (this.firstName != null ? this.firstName.hashCode() : 0);
hash = 19 * hash + (this.lastName != null ? this.lastName.hashCode() : 0);
hash = 19 * hash + (this.age != null ? this.age.hashCode() : 0);
return hash;
}
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("UserData[firstName: ");
sb.append(this.firstName);
sb.append(" lastName: ");
sb.append(this.lastName);
sb.append(" age: ");
sb.append(this.age);
sb.append("]");
return sb.toString();
}
}

In Scala, ''all'' the functionality of the above class can be expressed with:

case class UserData(val firstName: String, val lastName: String, val age: Int)

To reiterate, the version in Scala actually does include a constructor, accessor methods, three fields that can only be set once, equals and hashCode methods (comparing the structural equality of the two instances of the class), as well a meaningful toString method which prints the fields.

There are numerous other benefits in using case classes, including automatic destructuring in pattern matching. We will discuss these features in the next section.

This feature by itself vastly reduces both development and maintenance burden for developers. Classes in Scala are defined in lines, rather than entire files. All the potential errors that could creep into that code are removed, and the ''intent'' of the developer is very clear.

==Destructuring Binds and Pattern Matching==
Lisp, one of the earliest hybrid languages, offered primarily functional features with object-orientation built on top (in a system called CLOS). One piece of functionality written with Common Lisp's metaprogramming facility was the ability to execute [http://www.ai.mit.edu/projects/iiip/doc/CommonLISP/HyperSpec/Body/mac_destructuring-bind.html destructuring binds], which are a powerful way of checking for a particular type ([http://en.wikipedia.org/wiki/Pattern_matching pattern matching]) and simultaneously extracting values from the inside of that type to use them in some computation. In the spirit of Common Lisp, Scala also offers destructuring binds and pattern matching. Let's take a look at what they can do for us.

Let us suppose we want to make use of our UserData class, defined above. We want to find all users with ages over 18 and store their names in a database. If we were to write a method that would simply do the database store for a single user, it might look like this:

public void storeName(UserData user) {
Integer age = user.getAge();
if (age > 18) {
recordToDatabase(user.lastName, user.firstName);
}
}

In Scala, this would be a trivial pattern match, with a destructuring bind to capture the fields inside the UserData (in this case, we bind them to f, l and a):

def storeName(user:UserData) = user match {
case UserData(f, l, a) if a > 18 => recordToDatabase(l, a)
}

In this case, we don't get an enourmous savings in terms of the number of lines of code used, but we gain tremendously in expressive power. Let's say we wanted to do the same thing, but not include users named "Bob". In Java:

public void storeName(UserData user) {
String firstName = user.getFirstName();
if (firstName != "Bob") {
Integer age = user.getAge();
if (age > 18) {
recordToDatabase(user.lastName, user.firstName);
}
}
}

And now in Scala:

def storeName(user:UserData) = user match {
case UserData(f, l, a) if a > 18 && f != "Bob" => recordToDatabase(l, a)
}

Hopefully this provides a little bit of insight into how destructuring can improve the expressiveness of your code. A more in depth discussion on pattern matching and binding can be be found in [http://www.codecommit.com/blog/scala/scala-for-java-refugees-part-4 Part 4] of Code Commit's series "Scala For Java Refugees".

==List Comprehension==
In imperative languages (including both procedural and object-oriented languages), it is common to loop very often, either with a for loop or a while loop. Hybrid languages allow for this, and also incorporate more abstract operations on structures seen in functional programming.

For example, suppose we wanted to take in a structure containing a bunch of UserData objects, and return a list of strings, containing the last name, a comma, and then the first name of each user.

In Java, this might look like this:

public ArrayList<String> toStrings(ArrayList<UserData> users) {
ArrayList<String> returnedList = new ArrayList<String>();
for (UserData u : users) {
returnedList.add(u.getLastName() + ", " + u.firstName);
}
return returnedList;
}

In the seven lines of code, only the method declaration and the add to the new list really have anything to do with the business logic. In Scala, that boiler plate can be avoided:

def toStrings(users: List[UserData]) = users.map(u => u.lastName + ", " + u.firstName)

This method definition is so short that it is arguable we shouldn't even define the method, and should simply use the map operation inline:

users.map(u => u.lastName + ", " + u.firstName)

This is a small demonstration of how functional languages and object-oriented languages an combine their strengths. We retain all the encapsulation of the object-oriented approach (although u.lastName and u.firstName appear to be fields, they are in fact accessor methods), but we also have the power of higher abstraction levels from the functional world (in this case, the map operation).

==Lazy Evaluation==
The final feature I'd like to touch upon is lazy evaluation. One of the many implications of lazy evaluation is that we can now program using infinite data structures; we define a way in which deeper parts of the data structure are calculated from the existing parts, and only lazily evaluate parts of the structure as they are accessed. This allows us to express algorithms quite concisely. This can be used in a variety of cases like random number generation, methods of successive approximation (like Newton's Method), fractal calculations, and generation of infinite series, as seen in the numerical methods or, more simply, the Fibonacci sequence. Because it is so well known, I will use the Fibonacci sequence as an example here. First, in Java:

public long fib(int k) {
if (k <= 2) {
return 1;
} else {
return fib(k-1) + fib(k-2);
}
}

This is a short, inefficient, recursive solution. It doesn't cache answers, either in a single call or across calls, which means it performs a huge amount of redundant computation. So it has a number of problems, but it is concise.

In Scala, we can remedy all those problems and remain concise using a [http://www.scala-lang.org/docu/files/api/scala/Stream.html Stream], a lazily evaluated form of a List:

val fibs: Stream[Int] = Stream(0,1) append fibs.zip(fibs.drop(1)).map(x => x._1 + x._2)

This definition is concise, offers automatic memoization and is thread-safe. To add those features to the Java code would require 20 lines of additional code at a minimum. It returns a Stream that can be queried for the kth Fibonacci number in the same way as the fib method defined in Java could, but calculates the 92rd Fibonacci in a fraction of a second.

=Conclusion=
Unfortunately, this article barely scratches the surface of the topic. There are decades of research and experience that have gone into modern programming languages, and the way in which they blend various programming paradigms blurs what were once quite distinct borders in the landscape of programming languages. But, that blurring has allowed these modern languages to offer programmers a bigger set of tools that aren't merely an amalgamation of features from every language, but a carefully crafted blend of features that enhance the expressiveness of these languages while not substantially increasing the syntax or API surface area.

=Further Reading=
If you want to know more about hybrid languages, its best to choose one (or a few!) and read about what they offer. If you're familiar with Java, or C#, take a look at the [http://www.scala-lang.org/node/104 tour of Scala] or perhaps some of the [http://www.fandev.org/doc/docIntro/StartHere.html features of Fan].

There are also a few major dynamically typed hybrid languages. Chief among these is [http://python.org Python], which has several implementations in [http://python.org C], [http://jython.org/ Java] and [http://codespeak.net/pypy/dist/pypy/doc/ Python](!). [http://ruby-lang.org Ruby] is also a newer hybrid language, originating in Japan, but was made famous worldwide because of its [http://rubyonrails.org/ Rails] web programming framework that was possible in large part due to its hybrid nature. It also has a [http://jruby.org/ Java implementation]. Finally, if you're working on the JVM an want a hybrid, dynamically-typed language with syntax that is close to Java's, [http://groovy.codehaus.org/ Groovy] is your best bet.

If you're very interested in performance, Common Lisp may have something to offer you, and there are [http://www.sbcl.org/ several] [http://www.cons.org/cmucl/ performant] [http://clisp.cons.org/ implementations]. If you want to learn more about why hybrid languages are so powerful, Paul Graham's book [http://www.paulgraham.com/onlisp.html On Lisp] explains why. If you really care about using the power of the JVM and are doing concurrent programming, a very modern lisp called [http://clojure.org Clojure] will be very interesting.

CSC/ECE 517 Fall 2009/wiki2 6 rp

2009-10-11T18:11:41Z

7r3ad:

=Topic=

While Smalltalk and Java were instrumental in bringing object-oriented programming into the mainstream, the 1990s also saw the development of hybrid languages that supported multiple programming paradigms, often combining procedural, object-oriented and functional approaches. Discuss the development and design considerations that went into languages like OCaml, Scala, F# and Fan, and how they build upon an object-oriented foundation to offer languages that offer type safety while maintaining brevity and expressive power.

=Introduction=

There are many ways to classify programming languages: on the basis of static or dynamic typing, type safety, high or low levels of abstraction, and by programming paradigm.

In this article, the focus is on programming paradigms, which can loosely be thought of as defining the atomic units a language offers as building block with which to build programs. There are three primary paradigms in use today:

* [http://en.wikipedia.org/wiki/Procedural_programming Procedural]
* [http://en.wikipedia.org/wiki/Object-oriented_programming Object-Oriented]
* [http://en.wikipedia.org/wiki/Declarative_programming Declarative]

Declarative languages span a wide array of programming styles. For simplicity in this article, we will focus on [http://en.wikipedia.org/wiki/Functional_programming functional] languages, which are an important subset of declarative languages.

Many languages provide only one of the paradigms to their users. [http://www.engin.umd.umich.edu/CIS/course.des/cis400/fortran/fortran.html FORTRAN], [http://www.engin.umd.umich.edu/CIS/course.des/cis400/cobol/cobol.html COBOL], [http://en.wikipedia.org/wiki/Pascal_%28programming_language%29 Pascal], [http://cm.bell-labs.com/cm/cs/who/dmr/chist.html C] and [http://en.wikipedia.org/wiki/BASIC BASIC] are all procedural, [http://www.engin.umd.umich.edu/CIS/course.des/cis400/simula/simula.html Simula], [http://www.smalltalk.org/main/ Smalltalk]] and [http://www.eiffel.com/developers/design_by_contract.html Eiffel] are object-oriented and [http://haskell.org/ Haskell] and [http://en.wikipedia.org/wiki/ML_%28programming_language%29 ML] are functional. These languages provide a single paradigm for programming, which limits programmers to the particular set of constructs available in that model.

The three paradigms evolved somewhat independently and offer unique constructs with which to solve programming problems. Some languages are multi-paradigm, however, and allow a programmer to use the tools most fitting for the problem at hand, sometimes mixing and matching freely within a single program. The original language of this type is Lisp, which dates back to the mid-1950s. In the last 20 years, many other hybrid languages have emerged, often derivatives of existing languages. C++ is derived from C, and offers both procedural and object-oriented approaches. [http://java.sun.com Java], one of the most widely used languages today, offers both procedural and object-oriented paradigms as well. [http://caml.inria.fr/ OCaml] is derived from ML, and offers functional and object-oriented styles. There are many others that have become popular in recent years, like [http://python.org Python] and [http://www.ruby-lang.org/en/ Ruby].

In this article, our goal is to examine what these hybrid languages offer above and beyond strictly object-oriented languages. In particular, we will examine the features of object-oriented languages and functional languages, and how they have been blended in a modern hybrid language called [http://scala-lang.org Scala].

=Features of Object Oriented Languages=
The key construct provided by object-oriented languages is the ''object'', which bundles the data and behavior together into a cohesive unit.

==Encapsulation==
Encapsulation is the technique of rolling behavior and data into an object that exhibits (and is handled in terms of) a particular behavior, rather than a particular composition. This technique allows the internals of an object to remain hidden from external entities, which in turn enables the object to modify its implementation over time while providing the same external behaviors.

For example, encapsulation would allow a class to add logging functionality without affecting other classes' collaboration with it. Any feature that is solely an implementation concern (speeding up a sorting algorithm, checking inputs for invalid data, changing the way resource errors are handled, etc.) can be evolved and modified over time within the object without breaking functionality elsewhere in the program that relies on the object in question.

==Dependency Inversion==

One of the major benefits of focusing on the ''behavior'' of objects rather than their ''implementation'' is that the behavior aspects can be well defined and captured in an interface. This allows code that once would rely on an unstable implementation to instead shift its dependency onto a stable interface, and have the implementation then implement the interface. This process is known as ''dependency inversion'', because of the way in which it alter the dependency structure of the code.

For example, let us say we have a web server that makes use of a logging facility to log information to disk. In this case, the web server depends on the logging facility:

[[Image:server-logger.png]]

Later, it becomes apparent that the web server also want to be able to log to other destinations. To facilitate this, we introduce a ''Logger'' interface, and make have the web server depend on that, so as to insulate it from new types of loggers that may be introduced. This allows us to modify both the server and the loggers in isolation, having them both depend on the interface rather than each other, essentially reversing, or ''inverting'' the dependency diagram.

[[Image:server-logger-invert.png]]

In this diagram, the behavior of the logger is well-defined and stable, and is captured in the interface represented by the yellow box. The blue boxes are classes that are implementations, and are insulated from one another by the interface, allowing them to vary independently without breaking the program as a whole. This is an example of the robustness that the object-oriented approach lends to a program through use of encapsulation.

==Polymorphism and Dynamic Dispatch==

The object-oriented approach of thinking in terms of behavior lends itself to have multiple implementations of a single behavior. We can see this is the case of the logger above. To the web server, a logger is simply an object with which logs can be stored. There are many possible implementations; we could use the file logger or the network logger as seen above, but we could also implement a console logger or a database logger. Essentially, this means that the web server could call a method to log information without any knowledge of exactly what kind of object it was calling. The raises the question of how (and when) a programming language decides which log method to call. Is it compiled in, or is it determined at runtime?

The answer is that it is determined at runtime. This type of ''late binding'' allows a program to remain flexible even after it is deployed, permitting end-users to determine what kind of logging functionality they want be passing in various implementations of the logger interface when the web server is run, even implementations that were written ''after'' the web server was written and deployed! This kind of flexibility is a result of ''polymorphism'', which simply means that the an interface (like the logger interface in our example) can have ''many forms'', or implementations. The way the language determines which one to invoke is through ''dynamic dispatch'', which is essentially a lookup table maintained as the program runs that maps calls to methods like logging to the implementations specified.

The major theme here is that the object-oriented approach of favoring encapsulation has many effects that ripple throughout the design process, almost all of which allow programmers to reduce the brittleness of their software by delaying commitment to particular implementations.

=Features of Functional Languages=

Much like object-oriented languages, functional languages offer a dominant paradigm that has far-reaching consequences in software design. For object-oriented languages, that element is encapsulation, and for functional languages, it is that functions are first-class entities, which simply means that functions are treated just like any other value in the language. This allows them to be passed as parameters, delayed, composed invoked, and returned from other functions. But what is a function?

A function's most notable trait is that it is free of ''side-effects'', or state changes to the program that occur as a result of its execution. We could say a lot about side effects, but the general rule is that a function will always return the same value given the same input. This means that functions are ''stateless''. Therefore, entities like random number generators and loggers are not functional, because they either store state or have some effect that is not related to the value they return. Another way to think of functions is that they are completely defined in terms of their input and output.

From this simple feature flows many characteristic language features. We will discuss them in turn.

==Immutability==
Maybe the most noticeable feature (or restriction) to programmers of languages that are not functional, [http://en.wikipedia.org/wiki/Immutable_object immutability] is one of the hallmarks of a functional language. Most non-functional languages allow ''assignment'', or the ability to assign new values to variables as the program runs. In functional programming, a value is declared only once and then never changes. This feature of of the language flows out of the notion that functions have no side-effects, and is often viewed as more of a restriction than a feature.

The power of immutability comes from the fact that programs that fully utilize immutability are much simpler than those that do not, making them amenable to automated analysis by a computer. Computers can then prove various properties about function programs, like concurrent behavior (presence or absence of deadlock/livelock), memory usage, and what within what bounds various values in the program will lie.

==Higher Order Functions==

Higher order functions are simply functions that accept or return other functions as values. This is made possible because functions are treated as first-class entities, and allows very expressive implementations of many algorithms to be written.

There are several hallmark higher order functions: map, reduce, fold left/right and filter are a few examples. Going into the intricacies of each is beyond the scope of this article, but Abelson and Sussman's seminal [http://mitpress.mit.edu/sicp/ Structure and Interpretation of Computer Programs] has an [http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-12.html#%_sec_1.3.1 excellent treatment] of the subject.

==Recursion==

Programmers that are new to functional programming often balk at the notion that values cannot change over time (as variables do in imperative languages). If values cannot change, how can we execute loops?

The answer lies in recursion, where values are immutable, and loops are implemented as successive calls to the current function with new arguments. The avoids the complexity of having values change over time while offering all the power of the loops we often see in imperative languages (for...each, do...while, etc.) Again, a deep treatment of these language features is beyond the scope of this article, but again, Abelson and Sussman have [http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.1 addressed] the topic at some length in their book.

==Delayed (Lazy) Evaluation==
An extremely powerful feature of functional programming that is enabled by immutability is ''lazy evaluation''. This simply means that expressions can be defined, even recursively, and are not computed until the values that would result from that computation are needed. This is possible because values in functional programs don't change over time, which means expressions can be evaluated at any point in time as needed.

Take an imperative expression like this (in Java):

int i = 4;
int j = i + 3;
i++;

If you evaluate these expressions in order, j will be equal to 7, but if you were to delay the evaluation of j until after the third line, j would be equal to 8. This is a very simple example of how variables that change over time require expressions be evaluated in a particular order to maintain the correctness of the program. Functional programming explicitly disallows the third line, and therefore enables the value of j to be calculated only when it is needed. The implications of this are significant, as we'll see in the next section.

=Hybrid Object-Oriented/Functional Languages=

To programmers of languages like SmallTalk, Simula and Java, many of the features provided in functional languages will seem foreign or strange. But, as discussed, there are significant advantages to the functional approach for certain types of programs. While the object-oriented paradigm has proven itself to be very useful, many modern languages have sought to integrate functional features as well to increase the expressiveness and power of the language. One such language is Scala, which, like Java, runs on the Java Virtual Machine (JVM), and is thus shares Java's libraries and portability while offering many [http://www.ibm.com/developerworks/java/library/j-scala01228.html functional features] that are not available in object-oriented languages like Java. In the [http://www.scala-lang.org/node/25 overview] of Scala available on its homepage, Scala is briefly described:

<blockquote>
[Scala] smoothly integrates features of object-oriented and functional languages, enabling Java and other programmers to be more productive. Code sizes are typically reduced by a factor of two to three when compared to an equivalent Java application."
</blockquote>
How does Scala allow code sizes to be reduced so much? It uses sophisticated type inferencing to reduce type signature redundancy, allows for functional programming constructs to be used, and provides syntax for oft-used programming idioms. Essentially, it takes the lessons learned from decades of functional and object-oriented programming experience and rolls them into a modern hybrid language that can make full use legacy Java code.

Scala is representative of an entire class of hybrid object/functional languages like OCaml, F# and Fan, and therefore makes a good language for use in the examples in this article. The intent is not to present highly technical examples, but rather to give readers an impression of how hybrid languages increase expressive power over their single-paradigm counterparts.

==Case Classes==
Idiomatic object-oriented programming involves encapsulation of data, as previously discussed. In older object-oriented languages, this required defining internal data values, and then providing necessary get and set methods to access and/or modify those values. Here is an example a class in Java that provides only get methods for some (immutable) values it holds. It includes all the methods that ''should'' be included in such a class, including a toString, equals and hashCode method. Note that is an error if such methods are ''not'' included in structural Java classes, which is why I include them here.

public class UserData {
private final String firstName;
private final String lastName;
private final Integer age;
public UserData(String firstName, String lastName, Integer age) {
this.firstName = firstName;
this.lastName = lastName;
this.age = age;
}
public String getFirstName() {
return this.firstName;
}
public String getLastName() {
return this.lastName;
}
public Integer getAge() {
return this.age;
}
@Override
public boolean equals(Object obj) {
if (obj == null) {
return false;
}
if (getClass() != obj.getClass()) {
return false;
}
final UserData other = (UserData) obj;
if ((this.firstName == null) ? (other.firstName != null) : !this.firstName.equals(other.firstName)) {
return false;
}
if ((this.lastName == null) ? (other.lastName != null) : !this.lastName.equals(other.lastName)) {
return false;
}
if (this.age != other.age && (this.age == null || !this.age.equals(other.age))) {
return false;
}
return true;
}
@Override
public int hashCode() {
int hash = 7;
hash = 19 * hash + (this.firstName != null ? this.firstName.hashCode() : 0);
hash = 19 * hash + (this.lastName != null ? this.lastName.hashCode() : 0);
hash = 19 * hash + (this.age != null ? this.age.hashCode() : 0);
return hash;
}
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("UserData[firstName: ");
sb.append(this.firstName);
sb.append(" lastName: ");
sb.append(this.lastName);
sb.append(" age: ");
sb.append(this.age);
sb.append("]");
return sb.toString();
}
}

In Scala, ''all'' the functionality of the above class can be expressed with:

case class UserData(val firstName: String, val lastName: String, val age: Int)

To reiterate, the version in Scala actually does include a constructor, accessor methods, three fields that can only be set once, equals and hashCode methods (comparing the structural equality of the two instances of the class), as well a meaningful toString method which prints the fields.

There are numerous other benefits in using case classes, including automatic destructuring in pattern matching. We will discuss these features in the next section.

This feature by itself vastly reduces both development and maintenance burden for developers. Classes in Scala are defined in lines, rather than entire files. All the potential errors that could creep into that code are removed, and the ''intent'' of the developer is very clear.

==Destructuring Binds and Pattern Matching==
Lisp, one of the earliest hybrid languages, offered primarily functional features with object-orientation built on top (in a system called CLOS). One piece of functionality written with Common Lisp's metaprogramming facility was the ability to execute [http://www.ai.mit.edu/projects/iiip/doc/CommonLISP/HyperSpec/Body/mac_destructuring-bind.html destructuring binds], which are a powerful way of checking for a particular type ([http://en.wikipedia.org/wiki/Pattern_matching pattern matching]) and simultaneously extracting values from the inside of that type to use them in some computation. In the spirit of Common Lisp, Scala also offers destructuring binds and pattern matching. Let's take a look at what they can do for us.

Let us suppose we want to make use of our UserData class, defined above. We want to find all users with ages over 18 and store their names in a database. If we were to write a method that would simply do the database store for a single user, it might look like this:

public void storeName(UserData user) {
Integer age = user.getAge();
if (age > 18) {
recordToDatabase(user.lastName, user.firstName);
}
}

In Scala, this would be a trivial pattern match, with a destructuring bind to capture the fields inside the UserData (in this case, we bind them to f, l and a):

def storeName(user:UserData) = user match {
case UserData(f, l, a) if a > 18 => recordToDatabase(l, a)
}

In this case, we don't get an enourmous savings in terms of the number of lines of code used, but we gain tremendously in expressive power. Let's say we wanted to do the same thing, but not include users named "Bob". In Java:

public void storeName(UserData user) {
String firstName = user.getFirstName();
if (firstName != "Bob") {
Integer age = user.getAge();
if (age > 18) {
recordToDatabase(user.lastName, user.firstName);
}
}
}

And now in Scala:

def storeName(user:UserData) = user match {
case UserData(f, l, a) if a > 18 && f != "Bob" => recordToDatabase(l, a)
}

Hopefully this provides a little bit of insight into how destructuring can improve the expressiveness of your code. A more in depth discussion on pattern matching and binding can be be found in [http://www.codecommit.com/blog/scala/scala-for-java-refugees-part-4 Part 4] of Code Commit's series "Scala For Java Refugees".

==List Comprehension==
In imperative languages (including both procedural and object-oriented languages), it is common to loop very often, either with a for loop or a while loop. Hybrid languages allow for this, and also incorporate more abstract operations on structures seen in functional programming.

For example, suppose we wanted to take in a structure containing a bunch of UserData objects, and return a list of strings, containing the last name, a comma, and then the first name of each user.

In Java, this might look like this:

public ArrayList<String> toStrings(ArrayList<UserData> users) {
ArrayList<String> returnedList = new ArrayList<String>();
for (UserData u : users) {
returnedList.add(u.getLastName() + ", " + u.firstName);
}
return returnedList;
}

In the seven lines of code, only the method declaration and the add to the new list really have anything to do with the business logic. In Scala, that boiler plate can be avoided:

def toStrings(users: List[UserData]) = users.map(u => u.lastName + ", " + u.firstName)

This method definition is so short that it is arguable we shouldn't even define the method, and should simply use the map operation inline:

users.map(u => u.lastName + ", " + u.firstName)

This is a small demonstration of how functional languages and object-oriented languages an combine their strengths. We retain all the encapsulation of the object-oriented approach (although u.lastName and u.firstName appear to be fields, they are in fact accessor methods), but we also have the power of higher abstraction levels from the functional world (in this case, the map operation).

==Lazy Evaluation==
The final feature I'd like to touch upon is lazy evaluation. One of the many implications of lazy evaluation is that we can now program using infinite data structures; we define a way in which deeper parts of the data structure are calculated from the existing parts, and only lazily evaluate parts of the structure as they are accessed. This allows us to express algorithms quite concisely. This can be used in a variety of cases like random number generation, methods of successive approximation (like Newton's Method), fractal calculations, and generation of infinite series, as seen in the numerical methods or, more simply, the Fibonacci sequence. Because it is so well known, I will use the Fibonacci sequence as an example here. First, in Java:

public long fib(int k) {
if (k <= 2) {
return 1;
} else {
return fib(k-1) + fib(k-2);
}
}

This is a short, inefficient, recursive solution. It doesn't cache answers, either in a single call or across calls, which means it performs a huge amount of redundant computation. So it has a number of problems, but it is concise.

In Scala, we can remedy all those problems and remain concise using a [http://www.scala-lang.org/docu/files/api/scala/Stream.html Stream], a lazily evaluated form of a List:

val fibs: Stream[Int] = Stream(0,1) append fibs.zip(fibs.drop(1)).map(x => x._1 + x._2)

This definition is concise, offers automatic memoization and is thread-safe. To add those features to the Java code would require 20 lines of additional code at a minimum. It returns a Stream that can be queried for the kth Fibonacci number in the same way as the fib method defined in Java could, but calculates the 92rd Fibonacci in a fraction of a second.

=Conclusion=
Unfortunately, this article barely scratches the surface of the topic. There are decades of research and experience that have gone into modern programming languages, and the way in which they blend various programming paradigms blurs what were once quite distinct borders in the landscape of programming languages. But, that blurring has allowed these modern languages to offer programmers a bigger set of tools that aren't merely an amalgamation of features from every language, but a carefully crafted blend of features that enhance the expressiveness of these languages while not substantially increasing the syntax or API surface area.

=Further Reading=
If you want to know more about hybrid languages, its best to choose one (or a few!) and read about what they offer. If you're familiar with Java, or C#, take a look at the [http://www.scala-lang.org/node/104 tour of Scala] or perhaps some of the [http://www.fandev.org/doc/docIntro/StartHere.html features of Fan].

There are also a few major dynamically typed hybrid languages. Chief among these is [http://python.org Python], which has several implementations in [http://python.org C], [http://jython.org/ Java] and [http://codespeak.net/pypy/dist/pypy/doc/ Python](!). [http://ruby-lang.org Ruby] is also a newer hybrid language, originating in Japan, but was made famous worldwide because of its [http://rubyonrails.org/ Rails] web programming framework that was possible in large part due to its hybrid nature. It also has a [http://jruby.org/ Java implementation]. Finally, if you're working on the JVM an want a hybrid, dynamically-typed language with syntax that is close to Java's, [http://groovy.codehaus.org/ Groovy] is your best bet.

If you're very interested in performance, Common Lisp may have something to offer you, and there are [http://www.sbcl.org/ several] [http://www.cons.org/cmucl/ performant] [http://clisp.cons.org/ implementations]. If you want to learn more about why hybrid languages are so powerful, Paul Graham's book [http://www.paulgraham.com/onlisp.html On Lisp] explains why. If you really care about using the power of the JVM and are doing concurrent programming, a very modern lisp called [http://clojure.org Clojure] will be very interesting.

CSC/ECE 517 Fall 2009/wiki1a 5 rp

2009-09-18T22:46:44Z

7r3ad: /* Distributed Version Control */

=Introduction=

The defining characteristic of a version control system is its ability to track changes to a document, or set of documents, over many changes, or revisions. For the vast majority of applications, version control systems have focused on tracking plain text files, such as those used for programming source code, HTML documents, and various markup syntax.

The history of the development of version control tools can be roughly categorized into three main phases:

# Local Version Control
# Client-Server Version Control
# Distributed Version Control

This breakdown is focused on the mechanisms that underlays how data is ''shared'' and ''stored'' in a version control system. It should not be inferred from this structure that other attributes are not important to the history of developments of version control systems. There have been many advances in how:

* conflicts are recognized and merges are performed
* groups of logically coherent changes are tracked
* and how the data is represented within the repository

While these may seem to be three separate topics, we will see in the section on [[#Other Advances]] that they are in fact very closely related.

=Local Version Control=

The first version control systems (like [http://en.wikipedia.org/wiki/Source_Code_Control_System SCCS], 1972) focused on ''local version control''; that is, centralized computer systems that were used by many users, often at the same time. In such a system, there were often many users of the system and the ''repository'', or location in which the data was stored, was simply a directory on the server to which the users had access. Because of this use case, these systems focused on two main features:

* File version tracking
* File Checkout and Locking

We will address each of these fundamental features in turn.

==File Version Tracking==

The primary feature of these early systems was the ability to check in files at various points as they were altered, so that the history of changes made to files under version control was kept permanently. Thus, many users could alter many files over time, and the entire set of documents under version control at a given point in time could be recovered, preventing loss of valuable data, as well a providing a record of what users made changes to files over time.

==File Checkout and Locking==

Because many users in a shared system may desire to edit a file simultaneously, one of the first features developed for version control systems was the ability to ''check out'' and ''lock'' a file. When a user checks out a file, he or she reserves the right to be the sole editor of that file until it is checked back in to version control. Both SCCS and [http://www.gnu.org/software/rcs/ RCS] were designed for use in a shared environment and, as such, allowed files to be checked out and locked in this way. Other users could check out the file, but only to view it. Thus, the files were locked from editing by all but the user that had checked the file out most recently.

==Weaknesses of Local Version Control Systems==

These local systems had two primary problems.

First, they required that every user log into a single computer to edit or access the information in the repository. This often posed both performance and security risks, in addition to being cumbersome as networks became more prevalent.

Second, they restricted a particular file to having only one editor at any given time. The next development in version control, embodied by CVS, sought to address both of these problems.

=Networked Version Control: Client-Server=

As users moved away from logging into systems locally to make their changes to files, the need for a version control system that supported remote operations emerged. The natural way to implement such remote operations was as an extension of the existing system, and by far the most prominent manifestation of this philosophy was present in [http://www.nongnu.org/cvs/ CVS], the concurrent versions system, which was initially based on RCS and began development in 1984 and matured throughout the mid- to late-1980s. Version 1.0 was released under the [http://www.gnu.org/copyleft/gpl.html GNU GPL], a free software license, in the second half of 1990.

The main feature driving the development of CVS was the need for many users, each on his or her own machine, to be able to perform all the operations present in the original RCS, but over a network connection, and in a way that allowed for concurrent editing to take place. This led to the development of a client-server model of version control systems, in which one central server would contain the canonical version of the repository, and various clients could connect to the central server and perform file check outs and commits. This model is very similar to the original RCS model, but rather than requiring users of the system to log into the version control system locally, it allowed users to access and alter the contents of the repository over the network.

Although CVS supports locking in the same way RCS does, CVS was among the first version control systems to support a ''non-locking repository''. This system allowed for concurrent editing of files under version control, and generated the need to develop new features that addressed the resulting complexities. Chief among the new features introduced to handle these complexities were the notions of ''branching'' and ''merging''. This allowed CVS to offer a non-locking repository, which is why there is an emphasis on the "concurrent" portion of CVS's name "concurrent versions system".

==Branching and Merging==

Inherent in the notion of concurrent editing is the problem of how to reconcile conflicting changes to the same file. A ''conflict'' is essentially two or more changes made to the same file that it may be difficult to merge into a final file that contains both sets of changes. An example of a conflict would occur if two users both edited a file on line 49, one changing the word "blue" to "red", and the other changing the same word "blue" to "green". The first user would then commit his or her changes back to the repository, and when the second user committed changes, the version control system would detect that the repostory had changed since the second user had obtained the file (since the first user had made a change and then committed it). At that point, the version control system would detect a conflict, and prompt the two users to coordinate to resolve the conflict to determine what text should be on line 49.

The solution to this problem lies in allowing users of the version control system to ''branch'' a version of the repository and make (possibly many) changes to that branch independent of the changes occurring on the main branch of the repository, known as the ''trunk''. Once a logical set of changes was completed on a branch, that branch would then need to have its changes reconciled with the current state of the repository on the trunk. This process of reconciliation is known as merging.

This feature is critical in a multi-user client environment as it allows work to progress on multiple fronts simultaneously, only requiring that the files be merged once the users of the system are ready to reconcile changes with other users.

Along with development of mechanisms to allow this sort of concurrent access to the repository over the network, version control systems became more adept in the algorithms they used to detect conflicts and merge conflicts. This aspect of version control is discussed further in [[#Merge Algorithms]].

==Client-Server Beyond CVS==

Although CVS developed good approaches to solving many of these problems, it had many problems that gained attention when it became the most widely used version control system for open source development. An exhaustive list would be lengthy, but to mention a few might be illustrative.

* CVS doesn't provide ''atomic'' operations, which means that if there were a network failure during a commit, the repository could become corrupted.
* CVS does not version control directories or symbolic links, which means the repository is really a lossy copy of a developer's environment, sometimes resulting in failure to track changes accurately.
* CVS doesn't track what files were committed at the same time, so if you make a logical group of changes to several files and want to track the fact that those files were changed together, you can only only derive that information from log messages. CVS will not track it for you.
* CVS cannot track when files are renamed; rather, a rename of a file in CVS looks like the original file was deleted and a new file added, thus losing the file's history.
* Creating branches and managing the subsequent merges is slow and difficult.

In short, while CVS provided a whole host of new features and advanced the state of the art in version control, it left room for improvement. This resulted in a vast number of client-server version control systems entering the market following CVS. One of the latest and most notable of these is [http://subversion.tigris.org/ Subversion], which seeks to address all of the [http://subversion.tigris.org/features.html issues] mentioned above and a whole lot more.

=Distributed Version Control=

In the late 1990s, a new paradigm of development started to emerge with the development of new, proprietary version control systems. The first of these was [http://en.wikipedia.org/wiki/Sun_WorkShop_TeamWare Sun WorkShop TeamWare], the lead designer of which went on to found a new company, [http://www.bitkeeper.com/ BitMover], and develop the leading proprietary distributed version control system, BitKeeper. These were the first distributed version control systems.

''Distributed'' version control system (DVCS) took many of the advances seen in client-server version control systems and moved them into a less centralized architecture. Essentially, the original version control systems were completely centralized, requiring every user to locally log in to the server on which the repository was located. In client-server version control systems, the system was made slightly more distributed, allowing users to connect from across the network to the repository, copy files from the repository to other machines for editing, and then commit them back to the server when edits were complete. Distributed version control continues the trend of decentralization by putting an entire repository, complete with a history of changes and ability to support remote connections, on each user's machine.

One of the strengths of CVS is that it supports file locking even though the main advance it provides is a non-locking repository.. In the same way that CVS supports legacy locking work flows, so do distributed version control systems support the workflows usually associated with a centralized repository. The main improvement distributed version control systems offer, however, is they do not require a central server. There are three advantages to this decentralized approach.

First, it encourages creation of branches. Specifically, every time a user "checks out" a file or group of files, a new branch is created on that users machine. This is in stark contrast to the client-server model in which each time a branch is created, it is carefully planned and coordinated with other users of the system. Essentially, branching and merging in a centralized system is often difficult and slow, and in a DVCS, it is designed to be natural and fast.

Second, it allows users to commit their changes without disturbing other users of the system. In typical client-server work flows, the notion of a ''commit'' is tightly coupled to the notion of a ''merge'' with the code that is currently in the repository. Distributed version control decouples these two notions, allowing developers to commit freely, and merge with other users at a different time.

Third, because each user has an entire copy of the repository, all work is done ''locally'', which allows users to continue doing work even when they don't have access to the internet or to a particular server. Further, many useful operations which take a long time in a centralized system take an order of magnitude less time in a distributed system simply because the entire repository is local, and therefore no network latency is involved.

All of these changes are made possible as networks have become faster and the computers on which end users now work are often as powerful as the servers that would host a centralized repository. Thus, and the compute power has moved to the edge of the network, so too has the data in the repositories.

This treatment might make it seem as though DVCS approaches are strictly superior to centralized networked approaches to version control. In general, DVCS is considered to be an advancement of the state of the art, much as networked systems were considered superior to their local counterparts. However, one common use case for version control systems is inside the firewall of a corporation, where work is done on possible proprietary or even classified data. In such scenarios, there is often a strong desire, at least at the management level, to strongly control storage of the version controlled data. Sometimes, such control is mandated by the customer. In these cases, it may well be undesirable to have developers replicating data at will, and in places that are not well managed and controlled. In these circumstances, it often makes sense to use a more centralized approach simply because the possibility of uncontrolled copying of the data represents a security risk. Products like IBM's [http://www-01.ibm.com/software/awdtools/clearcase/ ClearCase] are designed to perform very centralized and controlled version control in such environments.

=Other Advances=

In addition to the evolution of the way version control systems allowed users to access, modify and share data in the repository, many advances have been made in the way changes are merged, tracked and stored.

==Merge Algorithms==

Merge algorithms are a good way to frame the many of the problems that arise in a concurrent development environment. It is therefore useful to start by discussing the issue of merge algorithms, even though relatively few advances have been made in recent years on the algorithms themselves.

There are really two kinds of merging algorithm:

* 2-way merge
* 3-way merge

2-way merge was developed first, so we will discuss it first.

===2-way Merge===

A [http://en.wikipedia.org/wiki/Merge_%28revision_control%29#Two-way_merge 2-way Merge] takes two files and compares them for differences, merges differences that do not conflict and identifies differences that conflict for human resolution. [http://en.wikipedia.org/wiki/Diff diff] is a very well-known utility for performing such comparisons and its [http://en.wikipedia.org/wiki/Diff#Algorithm algorithm] is based upon a procedure for finding the [http://en.wikipedia.org/wiki/Longest_common_subsequence_problem longest common subsequence] of text in the files to be compared. Methods for approaching this basic algorithm has gone largely unchanged since 1975, and the algorithm is used in both SCCS and RCS to create ''patches'' as a means of storing multiple versions of files under version control.

While the 2-way merge approach is a good start to manage concurrent modification to the same resource in a version control system, it became apparent that while the merge algorithm was sound, the version control system actually had much more information than the merge program did, and therefore there were many cases in which a merge was ''conceptually'' easy, but proved to be difficult in practice. In particular, given a knowledge of a ''common ancestor'' from which two files had both originated, a merge program could make more decisions autonomously, streamlining the merge process. Thus, 3-way merge was born.

===3-way Merge===

A [http://en.wikipedia.org/wiki/Merge_%28revision_control%29#Three-way_merge 3-way merge] is an approach to merging two differing files with reference to a third file that is a common ancestor of the two differing files. By comparing each of the differing files first to the ancestor, and then to each other, the merge program can merge conflicts without human intervention more often than is possible in a 2-way merge approach.

This advancement alone made branching a much less risky proposition for development teams, and allowed distributed version control systems (which place special emphasis on a branched development approach) viable in both small and large development teams. While both CVS and Subversion (and other modern client-server version control systems) made use of a 3-way merge approach, the newer distributed version control systems tracked groups of changes effectively, and represented the changes of sets of files as a directed acyclic graph ([http://en.wikipedia.org/wiki/Directed_acyclic_graph DAG]), making identification of ''useful'' common ancestors easier, and thus streamlining the merge process. We will discuss each of these features in turn.

==Tracking Groups of Changes==

An issue closely related to merge algorithms is the issue of exactly ''which'' files the version control system inputs into a the 3-way merge. In early client-server implementations, a file was the both the largest and smallest entity tracked by the version control system; that is, if several files were modified in support of a single logical change to e.g. a piece of software, those version control systems tracked changes to each individual file and had no tracking for the fact that a particular files changes were part of a larger entity (in this case, a group of files part of a single commit).

While the algorithms to perform textual merges improved when the switch was made from 2-way to 3-way merges, most modern improvements for end users in the area of merge stem from how the files input into the merge algorithm are selected. By tracking ''groups'' of changes, the version control system can make more effective decisions about which files to pick for merge, making the merge algorithms perform optimally.

The ability to track groups of changes most noticeably affects merging improvements in two ways.

First, even when changes are tracked in groups, sometimes a manual merge (one requiring user intervention) is required. However, because the version control system can match patterns across mulitple files, if a similar merge is needed later (i.e. the same feature needs to be merged into another branch or the same branch at a later time), the version control system can "remember" the steps the user took to merge in that change and apply them automatically. This feature has an enourmous impact on user productivity in practice.

Second, tracking groups of changes allows the version control system to use algorithms that take advantage of that additional knowledge to better select ancestors for a 3-way merge. The best way to understand this is to engage in a thought experiment.

Imagine that you have a common code base, the trunk, from which two branches, A and B, are created. Branch A has a set of changes (Set 1) applied to it. Branch B has a different set of changes applied to it (Set 2). Then, in another commit, Branch B has another set of changes applied to it (Set 3). At this point, the user wishes to merge the two branches. Let us also suppose that Set 1 and Set 2 are different sets of changes that ''do not conflict'' with one another. Finally, let us also suppose that changes in Set 1 and Set 3 ''do'' conflict.

In a legacy version control system, when the merge took place and some file were examined that was part of Set 1, 2 and 3, the version control system would pick the trunk as the ancestor of both versions of the file. This would mean all the changes from Set 1, 2 and 3 would be examined simultaneously, presenting a complicated picture.

In a modern version control system, the file with changes from Set 1 would be easily merged with the files with changes from Set 2. This new file would then be chosen as the ancestor and merged with Set 3. This approach vastly simplifies the merging process for both the computer and the user, but it requires that groups of changes be tracked together and applied individually.

==Repository Data Representation==

In most client-server (and local) version control implementations, the version control system tracks individual files. The implication of this approach is that the entire view of the data within the system is file-centric. CVS, for example, allows annotations, but only on a per-file basis. One of the major recent advancements (pioneered by Git) is the ability to track the entire repository as a single monolithic entity.

One of the results of this is that modern systems (usually DVCS) can track single blocks of text (like a single function in a computer program) across several files if it were moved. This allows users to focus on the actual data in the repository, rather than the files that hold the data. One of the most well known negative effects of the file-centric approach appeared in CVS in which file renames would appear in the repository as delete-create pairs, resulting in loss of version history.

Another result of decoupling data representation from the file system has already been mentioned: it allows groups of changes across multiple files to be tracked and associated. A related notion is the the change history that was traditionally represented as a line in most client-server systems is being represented as a DAG in more modern systems. The DAG is a more restricted data structure in some ways, but make many operations much simpler for the end user. The most notable example is when merging from a branch multiple times, a DAG can accurately represent what changes have been incorporated, whereas the traditional file-system oriented approach leaves it as an exercise for the user to re-merge the same changes over and over. This particular example is discussed in depth in Eric Sink's [http://www.ericsink.com/entries/merge_history.html article on merging].

=Wikis as an Extension to Version Control=

As use of the internet became more widespread and ''users'' of the web became some of its most important ''contributors'', concepts like the [http://en.wikipedia.org/wiki/Wiki Wiki] allowed users of a website to edit the website itself. Often, the website was just a collection of files (pages) being served, that visitors could create, modify and remove. One of the aspects of [http://c2.com/cgi/wiki?WikiCommunity WikiCommunity] is it is discussed on the original Wiki is the notion of a Wiki being open to change, and thus, Wikis tend to allow anonymous modifications to the wiki's pages. From this simple fact emerged the idea of saving previous versions of the wiki's pages.

So, taken loosely, Wikis are essentially web-enabled version control systems in which the users are anyone who visits the wiki. This participatory culture lends itself to a distributed model of information exchange, and yet most wikis are still using what amounts to a local or client-server version control system behind the scenes.

Looking to the future, it will be very interesting to see what can be done with wiki communities if they incorporate the important lessons learned from distributed version control systems.

The first (and only) example I have found of a community of users developing wiki-like content using distributed version control systems is [http://orgmode.org/worg/ Worg], a group of [http://www.gnu.org/software/emacs Emacs] [http://orgmode.org/ Org-Mode] users sharing information about the ways they use the Org-Mode software. Incidentally, Worg is itself a collection of Org-Mode files stored in [http://git-scm.com/ Git], one of the most prominent distributed version control systems.

=Further Reading=

For quick refreshers on [http://betterexplained.com/articles/a-visual-guide-to-version-control/ Version Control] and [http://betterexplained.com/articles/intro-to-distributed-version-control-illustrated/ Distributed Version Control], BetterExplained has excellent, concise articles.

Linus Torvalds, the creator and maintainer of both Linux kernel and Git, gave a entertaining and inforative [http://www.youtube.com/watch?v=4XpnKHJAok8&feature=player_embedded tech talk] at Google on version control and Git. A fabulous resource.

An excellent [http://www.ericsink.com/entries/merge_history.html entry] in Eric Sink's blog on how merge history and repostory representation are related.

IBM has an well-written [http://www.ibm.com/developerworks/java/library/j-subversion/index.html DeveloperWorks article] describing the ways is which Subversion improved upon CVS, along with some history of version control up until Subversion.

CSC/ECE 517 Fall 2009/wiki1a 5 rp

2009-09-18T22:46:09Z

7r3ad: /* Distributed Version Control */

=Introduction=

The defining characteristic of a version control system is its ability to track changes to a document, or set of documents, over many changes, or revisions. For the vast majority of applications, version control systems have focused on tracking plain text files, such as those used for programming source code, HTML documents, and various markup syntax.

The history of the development of version control tools can be roughly categorized into three main phases:

# Local Version Control
# Client-Server Version Control
# Distributed Version Control

This breakdown is focused on the mechanisms that underlays how data is ''shared'' and ''stored'' in a version control system. It should not be inferred from this structure that other attributes are not important to the history of developments of version control systems. There have been many advances in how:

* conflicts are recognized and merges are performed
* groups of logically coherent changes are tracked
* and how the data is represented within the repository

While these may seem to be three separate topics, we will see in the section on [[#Other Advances]] that they are in fact very closely related.

=Local Version Control=

The first version control systems (like [http://en.wikipedia.org/wiki/Source_Code_Control_System SCCS], 1972) focused on ''local version control''; that is, centralized computer systems that were used by many users, often at the same time. In such a system, there were often many users of the system and the ''repository'', or location in which the data was stored, was simply a directory on the server to which the users had access. Because of this use case, these systems focused on two main features:

* File version tracking
* File Checkout and Locking

We will address each of these fundamental features in turn.

==File Version Tracking==

The primary feature of these early systems was the ability to check in files at various points as they were altered, so that the history of changes made to files under version control was kept permanently. Thus, many users could alter many files over time, and the entire set of documents under version control at a given point in time could be recovered, preventing loss of valuable data, as well a providing a record of what users made changes to files over time.

==File Checkout and Locking==

Because many users in a shared system may desire to edit a file simultaneously, one of the first features developed for version control systems was the ability to ''check out'' and ''lock'' a file. When a user checks out a file, he or she reserves the right to be the sole editor of that file until it is checked back in to version control. Both SCCS and [http://www.gnu.org/software/rcs/ RCS] were designed for use in a shared environment and, as such, allowed files to be checked out and locked in this way. Other users could check out the file, but only to view it. Thus, the files were locked from editing by all but the user that had checked the file out most recently.

==Weaknesses of Local Version Control Systems==

These local systems had two primary problems.

First, they required that every user log into a single computer to edit or access the information in the repository. This often posed both performance and security risks, in addition to being cumbersome as networks became more prevalent.

Second, they restricted a particular file to having only one editor at any given time. The next development in version control, embodied by CVS, sought to address both of these problems.

=Networked Version Control: Client-Server=

As users moved away from logging into systems locally to make their changes to files, the need for a version control system that supported remote operations emerged. The natural way to implement such remote operations was as an extension of the existing system, and by far the most prominent manifestation of this philosophy was present in [http://www.nongnu.org/cvs/ CVS], the concurrent versions system, which was initially based on RCS and began development in 1984 and matured throughout the mid- to late-1980s. Version 1.0 was released under the [http://www.gnu.org/copyleft/gpl.html GNU GPL], a free software license, in the second half of 1990.

The main feature driving the development of CVS was the need for many users, each on his or her own machine, to be able to perform all the operations present in the original RCS, but over a network connection, and in a way that allowed for concurrent editing to take place. This led to the development of a client-server model of version control systems, in which one central server would contain the canonical version of the repository, and various clients could connect to the central server and perform file check outs and commits. This model is very similar to the original RCS model, but rather than requiring users of the system to log into the version control system locally, it allowed users to access and alter the contents of the repository over the network.

Although CVS supports locking in the same way RCS does, CVS was among the first version control systems to support a ''non-locking repository''. This system allowed for concurrent editing of files under version control, and generated the need to develop new features that addressed the resulting complexities. Chief among the new features introduced to handle these complexities were the notions of ''branching'' and ''merging''. This allowed CVS to offer a non-locking repository, which is why there is an emphasis on the "concurrent" portion of CVS's name "concurrent versions system".

==Branching and Merging==

Inherent in the notion of concurrent editing is the problem of how to reconcile conflicting changes to the same file. A ''conflict'' is essentially two or more changes made to the same file that it may be difficult to merge into a final file that contains both sets of changes. An example of a conflict would occur if two users both edited a file on line 49, one changing the word "blue" to "red", and the other changing the same word "blue" to "green". The first user would then commit his or her changes back to the repository, and when the second user committed changes, the version control system would detect that the repostory had changed since the second user had obtained the file (since the first user had made a change and then committed it). At that point, the version control system would detect a conflict, and prompt the two users to coordinate to resolve the conflict to determine what text should be on line 49.

The solution to this problem lies in allowing users of the version control system to ''branch'' a version of the repository and make (possibly many) changes to that branch independent of the changes occurring on the main branch of the repository, known as the ''trunk''. Once a logical set of changes was completed on a branch, that branch would then need to have its changes reconciled with the current state of the repository on the trunk. This process of reconciliation is known as merging.

This feature is critical in a multi-user client environment as it allows work to progress on multiple fronts simultaneously, only requiring that the files be merged once the users of the system are ready to reconcile changes with other users.

Along with development of mechanisms to allow this sort of concurrent access to the repository over the network, version control systems became more adept in the algorithms they used to detect conflicts and merge conflicts. This aspect of version control is discussed further in [[#Merge Algorithms]].

==Client-Server Beyond CVS==

Although CVS developed good approaches to solving many of these problems, it had many problems that gained attention when it became the most widely used version control system for open source development. An exhaustive list would be lengthy, but to mention a few might be illustrative.

* CVS doesn't provide ''atomic'' operations, which means that if there were a network failure during a commit, the repository could become corrupted.
* CVS does not version control directories or symbolic links, which means the repository is really a lossy copy of a developer's environment, sometimes resulting in failure to track changes accurately.
* CVS doesn't track what files were committed at the same time, so if you make a logical group of changes to several files and want to track the fact that those files were changed together, you can only only derive that information from log messages. CVS will not track it for you.
* CVS cannot track when files are renamed; rather, a rename of a file in CVS looks like the original file was deleted and a new file added, thus losing the file's history.
* Creating branches and managing the subsequent merges is slow and difficult.

In short, while CVS provided a whole host of new features and advanced the state of the art in version control, it left room for improvement. This resulted in a vast number of client-server version control systems entering the market following CVS. One of the latest and most notable of these is [http://subversion.tigris.org/ Subversion], which seeks to address all of the [http://subversion.tigris.org/features.html issues] mentioned above and a whole lot more.

=Distributed Version Control=

In the late 1990s, a new paradigm of development started to emerge with the development of new, proprietary version control systems. The first of these was [http://en.wikipedia.org/wiki/Sun_WorkShop_TeamWare Sun WorkShop TeamWare], the lead designer of which went on to found a new company, [http://www.bitkeeper.com/ BitMover], and develop the leading proprietary distributed version control system, BitKeeper. These were the first distributed version control systems.

''Distributed'' version control system (DVCS) took many of the advances seen in client-server version control systems and moved them into a less centralized architecture. Essentially, the original version control systems were completely centralized, requiring every user to locally log in to the server on which the repository was located. In client-server version control systems, the system was made slightly more distributed, allowing users to connect from across the network to the repository, copy files from the repository to other machines for editing, and then commit them back to the server when edits were complete. Distributed version control continues the trend of decentralization by putting an entire repository, complete with a history of changes and ability to support remote connections, on each user's machine.

One of the strengths of CVS is that it supports file locking even though the main advance it provides is a non-locking repository.. In the same way that CVS supports legacy locking work flows, so do distributed version control systems support the workflows usually associated with a centralized repository. The main improvement distributed version control systems offer, however, is they do not require a central server. There are three advantages to this decentralized approach.

First, it encourages creation of branches. Specifically, every time a user "checks out" a file or group of files, a new branch is created on that users machine. This is in stark contrast to the client-server model in which each time a branch is created, it is carefully planned and coordinated with other users of the system. Essentially, branching and merging in a centralized system is often difficult and slow, and in a DVCS, it is designed to be natural and fast.

Second, it allows users to commit their changes without disturbing other users of the system. In typical client-server work flows, the notion of a ''commit'' is tightly coupled to the notion of a ''merge'' with the code that is currently in the repository. Distributed version control decouples these two notions, allowing developers to commit freely, and merge with other users at a different time.

Third, because each user has an entire copy of the repository, all work is done ''locally'', which allows users to continue doing work even when they don't have access to the internet or to a particular server. Further, many useful operations which take a long time in a centralized system take an order of magnitude less time in a distributed system simply because the entire repository is local, and therefore no network latency is involved.

All of these changes are made possible as networks have become faster and the computers on which end users now work are often as powerful as the servers that would host a centralized repository. Thus, and the compute power has moved to the edge of the network, so too has the data in the repositories.

This treatment might make it seem as though DVCS approaches are strictly superior on centralized networked approaches to version control. In general, DVCS is considered to be an advancement of the state of the art, much as networked systems were considered superior to their local counterparts. However, one common use case for version control systems is inside the firewall of a corporation, where work is done on possible proprietary or even classified data. In such scenarios, there is often a strong desire, at least at the management level, to strongly control storage of the version controlled data. Sometimes, such control is mandated by the customer. In these cases, it may well be undesirable to have developers replicating data at will, and in places that are not well managed and controlled. In these circumstances, it often makes sense to use a more centralized approach simply because the possibility of uncontrolled copying of the data represents a security risk. Products like IBM's [http://www-01.ibm.com/software/awdtools/clearcase/ ClearCase] are designed to perform very centralized and controlled version control in such environments.

=Other Advances=

In addition to the evolution of the way version control systems allowed users to access, modify and share data in the repository, many advances have been made in the way changes are merged, tracked and stored.

==Merge Algorithms==

Merge algorithms are a good way to frame the many of the problems that arise in a concurrent development environment. It is therefore useful to start by discussing the issue of merge algorithms, even though relatively few advances have been made in recent years on the algorithms themselves.

There are really two kinds of merging algorithm:

* 2-way merge
* 3-way merge

2-way merge was developed first, so we will discuss it first.

===2-way Merge===

A [http://en.wikipedia.org/wiki/Merge_%28revision_control%29#Two-way_merge 2-way Merge] takes two files and compares them for differences, merges differences that do not conflict and identifies differences that conflict for human resolution. [http://en.wikipedia.org/wiki/Diff diff] is a very well-known utility for performing such comparisons and its [http://en.wikipedia.org/wiki/Diff#Algorithm algorithm] is based upon a procedure for finding the [http://en.wikipedia.org/wiki/Longest_common_subsequence_problem longest common subsequence] of text in the files to be compared. Methods for approaching this basic algorithm has gone largely unchanged since 1975, and the algorithm is used in both SCCS and RCS to create ''patches'' as a means of storing multiple versions of files under version control.

While the 2-way merge approach is a good start to manage concurrent modification to the same resource in a version control system, it became apparent that while the merge algorithm was sound, the version control system actually had much more information than the merge program did, and therefore there were many cases in which a merge was ''conceptually'' easy, but proved to be difficult in practice. In particular, given a knowledge of a ''common ancestor'' from which two files had both originated, a merge program could make more decisions autonomously, streamlining the merge process. Thus, 3-way merge was born.

===3-way Merge===

A [http://en.wikipedia.org/wiki/Merge_%28revision_control%29#Three-way_merge 3-way merge] is an approach to merging two differing files with reference to a third file that is a common ancestor of the two differing files. By comparing each of the differing files first to the ancestor, and then to each other, the merge program can merge conflicts without human intervention more often than is possible in a 2-way merge approach.

This advancement alone made branching a much less risky proposition for development teams, and allowed distributed version control systems (which place special emphasis on a branched development approach) viable in both small and large development teams. While both CVS and Subversion (and other modern client-server version control systems) made use of a 3-way merge approach, the newer distributed version control systems tracked groups of changes effectively, and represented the changes of sets of files as a directed acyclic graph ([http://en.wikipedia.org/wiki/Directed_acyclic_graph DAG]), making identification of ''useful'' common ancestors easier, and thus streamlining the merge process. We will discuss each of these features in turn.

==Tracking Groups of Changes==

An issue closely related to merge algorithms is the issue of exactly ''which'' files the version control system inputs into a the 3-way merge. In early client-server implementations, a file was the both the largest and smallest entity tracked by the version control system; that is, if several files were modified in support of a single logical change to e.g. a piece of software, those version control systems tracked changes to each individual file and had no tracking for the fact that a particular files changes were part of a larger entity (in this case, a group of files part of a single commit).

While the algorithms to perform textual merges improved when the switch was made from 2-way to 3-way merges, most modern improvements for end users in the area of merge stem from how the files input into the merge algorithm are selected. By tracking ''groups'' of changes, the version control system can make more effective decisions about which files to pick for merge, making the merge algorithms perform optimally.

The ability to track groups of changes most noticeably affects merging improvements in two ways.

First, even when changes are tracked in groups, sometimes a manual merge (one requiring user intervention) is required. However, because the version control system can match patterns across mulitple files, if a similar merge is needed later (i.e. the same feature needs to be merged into another branch or the same branch at a later time), the version control system can "remember" the steps the user took to merge in that change and apply them automatically. This feature has an enourmous impact on user productivity in practice.

Second, tracking groups of changes allows the version control system to use algorithms that take advantage of that additional knowledge to better select ancestors for a 3-way merge. The best way to understand this is to engage in a thought experiment.

Imagine that you have a common code base, the trunk, from which two branches, A and B, are created. Branch A has a set of changes (Set 1) applied to it. Branch B has a different set of changes applied to it (Set 2). Then, in another commit, Branch B has another set of changes applied to it (Set 3). At this point, the user wishes to merge the two branches. Let us also suppose that Set 1 and Set 2 are different sets of changes that ''do not conflict'' with one another. Finally, let us also suppose that changes in Set 1 and Set 3 ''do'' conflict.

In a legacy version control system, when the merge took place and some file were examined that was part of Set 1, 2 and 3, the version control system would pick the trunk as the ancestor of both versions of the file. This would mean all the changes from Set 1, 2 and 3 would be examined simultaneously, presenting a complicated picture.

In a modern version control system, the file with changes from Set 1 would be easily merged with the files with changes from Set 2. This new file would then be chosen as the ancestor and merged with Set 3. This approach vastly simplifies the merging process for both the computer and the user, but it requires that groups of changes be tracked together and applied individually.

==Repository Data Representation==

In most client-server (and local) version control implementations, the version control system tracks individual files. The implication of this approach is that the entire view of the data within the system is file-centric. CVS, for example, allows annotations, but only on a per-file basis. One of the major recent advancements (pioneered by Git) is the ability to track the entire repository as a single monolithic entity.

One of the results of this is that modern systems (usually DVCS) can track single blocks of text (like a single function in a computer program) across several files if it were moved. This allows users to focus on the actual data in the repository, rather than the files that hold the data. One of the most well known negative effects of the file-centric approach appeared in CVS in which file renames would appear in the repository as delete-create pairs, resulting in loss of version history.

Another result of decoupling data representation from the file system has already been mentioned: it allows groups of changes across multiple files to be tracked and associated. A related notion is the the change history that was traditionally represented as a line in most client-server systems is being represented as a DAG in more modern systems. The DAG is a more restricted data structure in some ways, but make many operations much simpler for the end user. The most notable example is when merging from a branch multiple times, a DAG can accurately represent what changes have been incorporated, whereas the traditional file-system oriented approach leaves it as an exercise for the user to re-merge the same changes over and over. This particular example is discussed in depth in Eric Sink's [http://www.ericsink.com/entries/merge_history.html article on merging].

=Wikis as an Extension to Version Control=

As use of the internet became more widespread and ''users'' of the web became some of its most important ''contributors'', concepts like the [http://en.wikipedia.org/wiki/Wiki Wiki] allowed users of a website to edit the website itself. Often, the website was just a collection of files (pages) being served, that visitors could create, modify and remove. One of the aspects of [http://c2.com/cgi/wiki?WikiCommunity WikiCommunity] is it is discussed on the original Wiki is the notion of a Wiki being open to change, and thus, Wikis tend to allow anonymous modifications to the wiki's pages. From this simple fact emerged the idea of saving previous versions of the wiki's pages.

So, taken loosely, Wikis are essentially web-enabled version control systems in which the users are anyone who visits the wiki. This participatory culture lends itself to a distributed model of information exchange, and yet most wikis are still using what amounts to a local or client-server version control system behind the scenes.

Looking to the future, it will be very interesting to see what can be done with wiki communities if they incorporate the important lessons learned from distributed version control systems.

The first (and only) example I have found of a community of users developing wiki-like content using distributed version control systems is [http://orgmode.org/worg/ Worg], a group of [http://www.gnu.org/software/emacs Emacs] [http://orgmode.org/ Org-Mode] users sharing information about the ways they use the Org-Mode software. Incidentally, Worg is itself a collection of Org-Mode files stored in [http://git-scm.com/ Git], one of the most prominent distributed version control systems.

=Further Reading=

For quick refreshers on [http://betterexplained.com/articles/a-visual-guide-to-version-control/ Version Control] and [http://betterexplained.com/articles/intro-to-distributed-version-control-illustrated/ Distributed Version Control], BetterExplained has excellent, concise articles.

Linus Torvalds, the creator and maintainer of both Linux kernel and Git, gave a entertaining and inforative [http://www.youtube.com/watch?v=4XpnKHJAok8&feature=player_embedded tech talk] at Google on version control and Git. A fabulous resource.

An excellent [http://www.ericsink.com/entries/merge_history.html entry] in Eric Sink's blog on how merge history and repostory representation are related.

IBM has an well-written [http://www.ibm.com/developerworks/java/library/j-subversion/index.html DeveloperWorks article] describing the ways is which Subversion improved upon CVS, along with some history of version control up until Subversion.

CSC/ECE 517 Fall 2009/wiki1a 5 rp

2009-09-11T06:42:05Z

7r3ad:

=Introduction=

The defining characteristic of a version control system is its ability to track changes to a document, or set of documents, over many changes, or revisions. For the vast majority of applications, version control systems have focused on tracking plain text files, such as those used for programming source code, HTML documents, and various markup syntax.

The history of the development of version control tools can be roughly categorized into three main phases:

# Local Version Control
# Client-Server Version Control
# Distributed Version Control

This breakdown is focused on the mechanisms that underlays how data is ''shared'' and ''stored'' in a version control system. It should not be inferred from this structure that other attributes are not important to the history of developments of version control systems. There have been many advances in how:

* conflicts are recognized and merges are performed
* groups of logically coherent changes are tracked
* and how the data is represented within the repository

While these may seem to be three separate topics, we will see in the section on [[#Other Advances]] that they are in fact very closely related.

=Local Version Control=

The first version control systems (like [http://en.wikipedia.org/wiki/Source_Code_Control_System SCCS], 1972) focused on ''local version control''; that is, centralized computer systems that were used by many users, often at the same time. In such a system, there were often many users of the system and the ''repository'', or location in which the data was stored, was simply a directory on the server to which the users had access. Because of this use case, these systems focused on two main features:

* File version tracking
* File Checkout and Locking

We will address each of these fundamental features in turn.

==File Version Tracking==

The primary feature of these early systems was the ability to check in files at various points as they were altered, so that the history of changes made to files under version control was kept permanently. Thus, many users could alter many files over time, and the entire set of documents under version control at a given point in time could be recovered, preventing loss of valuable data, as well a providing a record of what users made changes to files over time.

==File Checkout and Locking==

Because many users in a shared system may desire to edit a file simultaneously, one of the first features developed for version control systems was the ability to ''check out'' and ''lock'' a file. When a user checks out a file, he or she reserves the right to be the sole editor of that file until it is checked back in to version control. Both SCCS and [http://www.gnu.org/software/rcs/ RCS] were designed for use in a shared environment and, as such, allowed files to be checked out and locked in this way. Other users could check out the file, but only to view it. Thus, the files were locked from editing by all but the user that had checked the file out most recently.

==Weaknesses of Local Version Control Systems==

These local systems had two primary problems.

First, they required that every user log into a single computer to edit or access the information in the repository. This often posed both performance and security risks, in addition to being cumbersome as networks became more prevalent.

Second, they restricted a particular file to having only one editor at any given time. The next development in version control, embodied by CVS, sought to address both of these problems.

=Networked Version Control: Client-Server=

As users moved away from logging into systems locally to make their changes to files, the need for a version control system that supported remote operations emerged. The natural way to implement such remote operations was as an extension of the existing system, and by far the most prominent manifestation of this philosophy was present in [http://www.nongnu.org/cvs/ CVS], the concurrent versions system, which was initially based on RCS and began development in 1984 and matured throughout the mid- to late-1980s. Version 1.0 was released under the [http://www.gnu.org/copyleft/gpl.html GNU GPL], a free software license, in the second half of 1990.

The main feature driving the development of CVS was the need for many users, each on his or her own machine, to be able to perform all the operations present in the original RCS, but over a network connection, and in a way that allowed for concurrent editing to take place. This led to the development of a client-server model of version control systems, in which one central server would contain the canonical version of the repository, and various clients could connect to the central server and perform file check outs and commits. This model is very similar to the original RCS model, but rather than requiring users of the system to log into the version control system locally, it allowed users to access and alter the contents of the repository over the network.

Although CVS supports locking in the same way RCS does, CVS was among the first version control systems to support a ''non-locking repository''. This system allowed for concurrent editing of files under version control, and generated the need to develop new features that addressed the resulting complexities. Chief among the new features introduced to handle these complexities were the notions of ''branching'' and ''merging''. This allowed CVS to offer a non-locking repository, which is why there is an emphasis on the "concurrent" portion of CVS's name "concurrent versions system".

==Branching and Merging==

Inherent in the notion of concurrent editing is the problem of how to reconcile conflicting changes to the same file. A ''conflict'' is essentially two or more changes made to the same file that it may be difficult to merge into a final file that contains both sets of changes. An example of a conflict would occur if two users both edited a file on line 49, one changing the word "blue" to "red", and the other changing the same word "blue" to "green". The first user would then commit his or her changes back to the repository, and when the second user committed changes, the version control system would detect that the repostory had changed since the second user had obtained the file (since the first user had made a change and then committed it). At that point, the version control system would detect a conflict, and prompt the two users to coordinate to resolve the conflict to determine what text should be on line 49.

The solution to this problem lies in allowing users of the version control system to ''branch'' a version of the repository and make (possibly many) changes to that branch independent of the changes occurring on the main branch of the repository, known as the ''trunk''. Once a logical set of changes was completed on a branch, that branch would then need to have its changes reconciled with the current state of the repository on the trunk. This process of reconciliation is known as merging.

This feature is critical in a multi-user client environment as it allows work to progress on multiple fronts simultaneously, only requiring that the files be merged once the users of the system are ready to reconcile changes with other users.

Along with development of mechanisms to allow this sort of concurrent access to the repository over the network, version control systems became more adept in the algorithms they used to detect conflicts and merge conflicts. This aspect of version control is discussed further in [[#Merge Algorithms]].

==Client-Server Beyond CVS==

Although CVS developed good approaches to solving many of these problems, it had many problems that gained attention when it became the most widely used version control system for open source development. An exhaustive list would be lengthy, but to mention a few might be illustrative.

* CVS doesn't provide ''atomic'' operations, which means that if there were a network failure during a commit, the repository could become corrupted.
* CVS does not version control directories or symbolic links, which means the repository is really a lossy copy of a developer's environment, sometimes resulting in failure to track changes accurately.
* CVS doesn't track what files were committed at the same time, so if you make a logical group of changes to several files and want to track the fact that those files were changed together, you can only only derive that information from log messages. CVS will not track it for you.
* CVS cannot track when files are renamed; rather, a rename of a file in CVS looks like the original file was deleted and a new file added, thus losing the file's history.
* Creating branches and managing the subsequent merges is slow and difficult.

In short, while CVS provided a whole host of new features and advanced the state of the art in version control, it left room for improvement. This resulted in a vast number of client-server version control systems entering the market following CVS. One of the latest and most notable of these is [http://subversion.tigris.org/ Subversion], which seeks to address all of the [http://subversion.tigris.org/features.html issues] mentioned above and a whole lot more.

=Distributed Version Control=

In the late 1990s, a new paradigm of development started to emerge with the development of new, proprietary version control systems. The first of these was [http://en.wikipedia.org/wiki/Sun_WorkShop_TeamWare Sun WorkShop TeamWare], the lead designer of which went on to found a new company, [http://www.bitkeeper.com/ BitMover], and develop the leading proprietary distributed version control system, BitKeeper. These were the first distributed version control systems.

''Distributed'' version control system (DVCS) took many of the advances seen in client-server version control systems and moved them into a less centralized architecture. Essentially, the original version control systems were completely centralized, requiring every user to locally log in to the server on which the repository was located. In client-server version control systems, the system was made slightly more distributed, allowing users to connect from across the network to the repository, copy files from the repository to other machines for editing, and then commit them back to the server when edits were complete. Distributed version control continues the trend of decentralization by putting an entire repository, complete with a history of changes and ability to support remote connections, on each user's machine.

One of the strengths of CVS is that it supports file locking even though the main advance it provides is a non-locking repository.. In the same way that CVS supports legacy locking work flows, so do distributed version control systems support the workflows usually associated with a centralized repository. The main improvement distributed version control systems offer, however, is they do not require a central server. There are three advantages to this decentralized approach.

First, it encourages creation of branches. Specifically, every time a user "checks out" a file or group of files, a new branch is created on that users machine. This is in stark contrast to the client-server model in which each time a branch is created, it is carefully planned and coordinated with other users of the system. Essentially, branching and merging in a centralized system is often difficult and slow, and in a DVCS, it is designed to be natural and fast.

Second, it allows users to commit their changes without disturbing other users of the system. In typical client-server work flows, the notion of a ''commit'' is tightly coupled to the notion of a ''merge'' with the code that is currently in the repository. Distributed version control decouples these two notions, allowing developers to commit freely, and merge with other users at a different time.

Third, because each user has an entire copy of the repository, all work is done ''locally'', which allows users to continue doing work even when they don't have access to the internet or to a particular server. Further, many useful operations which take a long time in a centralized system take an order of magnitude less time in a distributed system simply because the entire repository is local, and therefore no network latency is involved.

All of these changes are made possible as networks have become faster and the computers on which end users now work are often as powerful as the servers that would host a centralized repository. Thus, and the compute power has moved to the edge of the network, so too has the data in the repositories.

=Other Advances=

In addition to the evolution of the way version control systems allowed users to access, modify and share data in the repository, many advances have been made in the way changes are merged, tracked and stored.

==Merge Algorithms==

Merge algorithms are a good way to frame the many of the problems that arise in a concurrent development environment. It is therefore useful to start by discussing the issue of merge algorithms, even though relatively few advances have been made in recent years on the algorithms themselves.

There are really two kinds of merging algorithm:

* 2-way merge
* 3-way merge

2-way merge was developed first, so we will discuss it first.

===2-way Merge===

A [http://en.wikipedia.org/wiki/Merge_%28revision_control%29#Two-way_merge 2-way Merge] takes two files and compares them for differences, merges differences that do not conflict and identifies differences that conflict for human resolution. [http://en.wikipedia.org/wiki/Diff diff] is a very well-known utility for performing such comparisons and its [http://en.wikipedia.org/wiki/Diff#Algorithm algorithm] is based upon a procedure for finding the [http://en.wikipedia.org/wiki/Longest_common_subsequence_problem longest common subsequence] of text in the files to be compared. Methods for approaching this basic algorithm has gone largely unchanged since 1975, and the algorithm is used in both SCCS and RCS to create ''patches'' as a means of storing multiple versions of files under version control.

While the 2-way merge approach is a good start to manage concurrent modification to the same resource in a version control system, it became apparent that while the merge algorithm was sound, the version control system actually had much more information than the merge program did, and therefore there were many cases in which a merge was ''conceptually'' easy, but proved to be difficult in practice. In particular, given a knowledge of a ''common ancestor'' from which two files had both originated, a merge program could make more decisions autonomously, streamlining the merge process. Thus, 3-way merge was born.

===3-way Merge===

A [http://en.wikipedia.org/wiki/Merge_%28revision_control%29#Three-way_merge 3-way merge] is an approach to merging two differing files with reference to a third file that is a common ancestor of the two differing files. By comparing each of the differing files first to the ancestor, and then to each other, the merge program can merge conflicts without human intervention more often than is possible in a 2-way merge approach.

This advancement alone made branching a much less risky proposition for development teams, and allowed distributed version control systems (which place special emphasis on a branched development approach) viable in both small and large development teams. While both CVS and Subversion (and other modern client-server version control systems) made use of a 3-way merge approach, the newer distributed version control systems tracked groups of changes effectively, and represented the changes of sets of files as a directed acyclic graph ([http://en.wikipedia.org/wiki/Directed_acyclic_graph DAG]), making identification of ''useful'' common ancestors easier, and thus streamlining the merge process. We will discuss each of these features in turn.

==Tracking Groups of Changes==

An issue closely related to merge algorithms is the issue of exactly ''which'' files the version control system inputs into a the 3-way merge. In early client-server implementations, a file was the both the largest and smallest entity tracked by the version control system; that is, if several files were modified in support of a single logical change to e.g. a piece of software, those version control systems tracked changes to each individual file and had no tracking for the fact that a particular files changes were part of a larger entity (in this case, a group of files part of a single commit).

While the algorithms to perform textual merges improved when the switch was made from 2-way to 3-way merges, most modern improvements for end users in the area of merge stem from how the files input into the merge algorithm are selected. By tracking ''groups'' of changes, the version control system can make more effective decisions about which files to pick for merge, making the merge algorithms perform optimally.

==Repository Data Representation==

In most client-server (and local) version control implementations, the version control system tracks individual files. The implication of this approach is that the entire view of the data within the system is file-centric. CVS, for example, allows annotations, but only on a per-file basis. One of the major recent advancements (pioneered by Git) is the ability to track the entire repository as a single monolithic entity.

One of the results of this is that modern systems (usually DVCS) can track single blocks of text (like a single function in a computer program) across several files if it were moved. This allows users to focus on the actual data in the repository, rather than the files that hold the data. One of the most well known negative effects of the file-centric approach appeared in CVS in which file renames would appear in the repository as delete-create pairs, resulting in loss of version history.

Another result of decoupling data representation from the file system has already been mentioned: it allows groups of changes across multiple files to be tracked and associated. A related notion is the the change history that was traditionally represented as a line in most client-server systems is being represented as a DAG in more modern systems. The DAG is a more restricted data structure in some ways, but make many operations much simpler for the end user. The most notable example is when merging from a branch multiple times, a DAG can accurately represent what changes have been incorporated, whereas the traditional file-system oriented approach leaves it as an exercise for the user to re-merge the same changes over and over. This particular example is discussed in depth in Eric Sink's [http://www.ericsink.com/entries/merge_history.html article on merging].

=Wikis as an Extension to Version Control=

As use of the internet became more widespread and ''users'' of the web became some of its most important ''contributors'', concepts like the [http://en.wikipedia.org/wiki/Wiki Wiki] allowed users of a website to edit the website itself. Often, the website was just a collection of files (pages) being served, that visitors could create, modify and remove. One of the aspects of [http://c2.com/cgi/wiki?WikiCommunity WikiCommunity] is it is discussed on the original Wiki is the notion of a Wiki being open to change, and thus, Wikis tend to allow anonymous modifications to the wiki's pages. From this simple fact emerged the idea of saving previous versions of the wiki's pages.

So, taken loosely, Wikis are essentially web-enabled version control systems in which the users are anyone who visits the wiki. This participatory culture lends itself to a distributed model of information exchange, and yet most wikis are still using what amounts to a local or client-server version control system behind the scenes.

Looking to the future, it will be very interesting to see what can be done with wiki communities if they incorporate the important lessons learned from distributed version control systems.

The first (and only) example I have found of a community of users developing wiki-like content using distributed version control systems is [http://orgmode.org/worg/ Worg], a group of [http://www.gnu.org/software/emacs Emacs] [http://orgmode.org/ Org-Mode] users sharing information about the ways they use the Org-Mode software. Incidentally, Worg is itself a collection of Org-Mode files stored in [http://git-scm.com/ Git], one of the most prominent distributed version control systems.

=Further Reading=

For quick refreshers on [http://betterexplained.com/articles/a-visual-guide-to-version-control/ Version Control] and [http://betterexplained.com/articles/intro-to-distributed-version-control-illustrated/ Distributed Version Control], BetterExplained has excellent, concise articles.

Linus Torvalds, the creator and maintainer of both Linux kernel and Git, gave a entertaining and inforative [http://www.youtube.com/watch?v=4XpnKHJAok8&feature=player_embedded tech talk] at Google on version control and Git. A fabulous resource.

An excellent [http://www.ericsink.com/entries/merge_history.html entry] in Eric Sink's blog on how merge history and repostory representation are related.

IBM has an well-written [http://www.ibm.com/developerworks/java/library/j-subversion/index.html DeveloperWorks article] describing the ways is which Subversion improved upon CVS, along with some history of version control up until Subversion.

CSC/ECE 517 Fall 2009/wiki1a 5 rp

2009-09-08T07:26:10Z

7r3ad:

=Introduction=

The defining characteristic of a version control system is its ability to track changes to a document, or set of documents, over many changes, or revisions. For the vast majority of applications, version control systems have focused on tracking plain text files, such as those used for programming source code, HTML documents, and various markup syntax.

The history of the development of version control tools can be roughly categorized into three main phases:

# Local Version Control
# Client-Server Version Control
# Distributed Version Control

This breakdown is focused on the mechanisms that underlays how data is ''shared'' and ''stored'' in a version control system. It should not be inferred from this structure that other attributes are not important to the history of developments of version control systems. There have been many advances in how:

* conflicts are recognized and merges are performed
* groups of logically coherent changes are tracked
* and how the data is represented within the repository

While these may seem to be three separate topics, we will see in the section on [[#Other Advances]] that they are in fact very closely related.

=Local Version Control=

The first version control systems (like [http://en.wikipedia.org/wiki/Source_Code_Control_System SCCS], 1972) focused on ''local version control''; that is, centralized computer systems that were used by many users, often at the same time. In such a system, there were often many users of the system and the ''repository'', or location in which the data was stored, was simply a directory on the server to which the users had access. Because of this use case, these systems focused on two main features:

* File version tracking
* File Checkout and Locking

We will address each of these fundamental features in turn.

==File Version Tracking==

The primary feature of these early systems was the ability to check in files at various points as they were altered, so that the history of changes made to files under version control was kept permanently. Thus, many users could alter many files over time, and the entire set of documents under version control at a given point in time could be recovered, preventing loss of valuable data, as well a providing a record of what users made changes to files over time.

==File Checkout and Locking==

Because many users in a shared system may desire to edit a file simultaneously, one of the first features developed for version control systems was the ability to ''check out'' and ''lock'' a file. When a user checks out a file, he or she reserves the right to be the sole editor of that file until it is checked back in to version control. Both SCCS and [http://www.gnu.org/software/rcs/ RCS] were designed for use in a shared environment and, as such, allowed files to be checked out and locked in this way. Other users could check out the file, but only to view it. Thus, the files were locked from editing by all but the user that had checked the file out most recently.

==Weaknesses of Local Version Control Systems==

These local systems had two primary problems.

First, they required that every user log into a single computer to edit or access the information in the repository. This often posed both performance and security risks, in addition to being cumbersome as networks became more prevalent.

Second, they restricted a particular file to having only one editor at any given time. The next development in version control, embodied by CVS, sought to address both of these problems.

=Networked Version Control: Client-Server=

As users moved away from logging into systems locally to make their changes to files, the need for a version control system that supported remote operations emerged. The natural way to implement such remote operations was as an extension of the existing system, and by far the most prominent manifestation of this philosophy was present in [http://www.nongnu.org/cvs/ CVS], the concurrent versions system, which was initially based on RCS and began development in 1984 and matured throughout the mid- to late-1980s. Version 1.0 was released under the [http://www.gnu.org/copyleft/gpl.html GNU GPL], a free software license, in the second half of 1990.

The main feature driving the development of CVS was the need for many users, each on his or her own machine, to be able to perform all the operations present in the original RCS, but over a network connection, and in a way that allowed for concurrent editing to take place. This led to the development of a client-server model of version control systems, in which one central server would contain the canonical version of the repository, and various clients could connect to the central server and perform file check outs and commits. This model is very similar to the original RCS model, but rather than requiring users of the system to log into the version control system locally, it allowed users to access and alter the contents of the repository over the network.

Although CVS supports locking in the same way RCS does, CVS was among the first version control systems to support a ''non-locking repository''. This system allowed for concurrent editing of files under version control, and generated the need to develop new features that addressed the resulting complexities. Chief among the new features introduced to handle these complexities were the notions of ''branching'' and ''merging''. This allowed CVS to offer a non-locking repository, which is why there is an emphasis on the "concurrent" portion of CVS's name "concurrent versions system".

==Branching and Merging==

Inherent in the notion of concurrent editing is the problem of how to reconcile conflicting changes to the same file. A ''conflict'' is essentially two or more changes made to the same file that it may be difficult to merge into a final file that contains both sets of changes. An example of a conflict would occur if two users both edited a file on line 49, one changing the word "blue" to "red", and the other changing the same word "blue" to "green". The first user would then commit his or her changes back to the repository, and when the second user committed changes, the version control system would detect that the repostory had changed since the second user had obtained the file (since the first user had made a change and then committed it). At that point, the version control system would detect a conflict, and prompt the two users to coordinate to resolve the conflict to determine what text should be on line 49.

The solution to this problem lies in allowing users of the version control system to ''branch'' a version of the repository and make (possibly many) changes to that branch independent of the changes occurring on the main branch of the repository, known as the ''trunk''. Once a logical set of changes was completed on a branch, that branch would then need to have its changes reconciled with the current state of the repository on the trunk. This process of reconciliation is known as merging.

This feature is critical in a multi-user client environment as it allows work to progress on multiple fronts simultaneously, only requiring that the files be merged once the users of the system are ready to reconcile changes with other users.

Along with development of mechanisms to allow this sort of concurrent access to the repository over the network, version control systems became more adept in the algorithms they used to detect conflicts and merge conflicts. This aspect of version control is discussed further in [[#Merge Algorithms]].

==Client-Server Beyond CVS==

Although CVS developed good approaches to solving many of these problems, it had many problems that gained attention when it became the most widely used version control system for open source development. An exhaustive list would be lengthy, but to mention a few might be illustrative.

* CVS doesn't provide ''atomic'' operations, which means that if there were a network failure during a commit, the repository could become corrupted.
* CVS does not version control directories or symbolic links, which means the repository is really a lossy copy of a developer's environment, sometimes resulting in failure to track changes accurately.
* CVS doesn't track what files were committed at the same time, so if you make a logical group of changes to several files and want to track the fact that those files were changed together, you can only only derive that information from log messages. CVS will not track it for you.
* CVS cannot track when files are renamed; rather, a rename of a file in CVS looks like the original file was deleted and a new file added, thus losing the file's history.
* Creating branches and managing the subsequent merges is slow and difficult.

In short, while CVS provided a whole host of new features and advanced the state of the art in version control, it left room for improvement. This resulted in a vast number of client-server version control systems entering the market following CVS. One of the latest and most notable of these is [http://subversion.tigris.org/ Subversion], which seeks to address all of the [http://subversion.tigris.org/features.html issues] mentioned above and a whole lot more.

=Distributed Version Control=

In the late 1990s, a new paradigm of development started to emerge with the development of new, proprietary version control systems. The first of these was [http://en.wikipedia.org/wiki/Sun_WorkShop_TeamWare Sun WorkShop TeamWare], the lead designer of which went on to found a new company, [http://www.bitkeeper.com/ BitMover], and develop the leading proprietary distributed version control system, BitKeeper. These were the first distributed version control systems.

''Distributed'' version control system (DVCS) took many of the advances seen in client-server version control systems and moved them into a less centralized architecture. Essentially, the original version control systems were completely centralized, requiring every user to locally log in to the server on which the repository was located. In client-server version control systems, the system was made slightly more distributed, allowing users to connect from across the network to the repository, copy files from the repository to other machines for editing, and then commit them back to the server when edits were complete. Distributed version control continues the trend of decentralization by putting an entire repository, complete with a history of changes and ability to support remote connections, on each user's machine.

One of the strengths of CVS is that it supports file locking even though the main advance it provides is a non-locking repository.. In the same way that CVS supports legacy locking work flows, so do distributed version control systems support the workflows usually associated with a centralized repository. The main improvement distributed version control systems offer, however, is they do not require a central server. There are three advantages to this decentralized approach.

First, it encourages creation of branches. Specifically, every time a user "checks out" a file or group of files, a new branch is created on that users machine. This is in stark contrast to the client-server model in which each time a branch is created, it is carefully planned and coordinated with other users of the system. Essentially, branching and merging in a centralized system is often difficult and slow, and in a DVCS, it is designed to be natural and fast.

Second, it allows users to commit their changes without disturbing other users of the system. In typical client-server work flows, the notion of a ''commit'' is tightly coupled to the notion of a ''merge'' with the code that is currently in the repository. Distributed version control decouples these two notions, allowing developers to commit freely, and merge with other users at a different time.

Third, because each user has an entire copy of the repository, all work is done ''locally'', which allows users to continue doing work even when they don't have access to the internet or to a particular server. Further, many useful operations which take a long time in a centralized system take an order of magnitude less time in a distributed system simply because the entire repository is local, and therefore no network latency is involved.

All of these changes are made possible as networks have become faster and the computers on which end users now work are often as powerful as the servers that would host a centralized repository. Thus, and the compute power has moved to the edge of the network, so too has the data in the repositories.

=Other Advances=

In addition to the evolution of the way version control systems allowed users to access, modify and share data in the repository, many advances have been made in the way changes are merged, tracked and stored.

==Merge Algorithms==

Merge algorithms are a good way to frame the many of the problems that arise in a concurrent development environment. It is therefore useful to start by discussing the issue of merge algorithms, even though relatively few advances have been made in recent years on the algorithms themselves.

There are really two kinds of merging algorithm:

* 2-way merge
* 3-way merge

2-way merge was developed first, so we will discuss it first.

===2-way Merge===

A [http://en.wikipedia.org/wiki/Merge_%28revision_control%29#Two-way_merge 2-way Merge] takes two files and compares them for differences, merges differences that do not conflict and identifies differences that conflict for human resolution. [http://en.wikipedia.org/wiki/Diff diff] is a very well-known utility for performing such comparisons and its [http://en.wikipedia.org/wiki/Diff#Algorithm algorithm] is based upon a procedure for finding the [http://en.wikipedia.org/wiki/Longest_common_subsequence_problem longest common subsequence] of text in the files to be compared. Methods for approaching this basic algorithm has gone largely unchanged since 1975, and the algorithm is used in both SCCS and RCS to create ''patches'' as a means of storing multiple versions of files under version control.

While the 2-way merge approach is a good start to manage concurrent modification to the same resource in a version control system, it became apparent that while the merge algorithm was sound, the version control system actually had much more information than the merge program did, and therefore there were many cases in which a merge was ''conceptually'' easy, but proved to be difficult in practice. In particular, given a knowledge of a ''common ancestor'' from which two files had both originated, a merge program could make more decisions autonomously, streamlining the merge process. Thus, 3-way merge was born.

===3-way Merge===

A [http://en.wikipedia.org/wiki/Merge_%28revision_control%29#Three-way_merge 3-way merge] is an approach to merging two differing files with reference to a third file that is a common ancestor of the two differing files. By comparing each of the differing files first to the ancestor, and then to each other, the merge program can merge conflicts without human intervention more often than is possible in a 2-way merge approach.

This advancement alone made branching a much less risky proposition for development teams, and allowed distributed version control systems (which place special emphasis on a branched development approach) viable in both small and large development teams. While both CVS and Subversion (and other modern client-server version control systems) made use of a 3-way merge approach, the newer distributed version control systems tracked groups of changes effectively, and represented the changes of sets of files as a directed acyclic graph ([http://en.wikipedia.org/wiki/Directed_acyclic_graph DAG]), making identification of ''useful'' common ancestors easier, and thus streamlining the merge process. We will discuss each of these features in turn.

==Tracking Groups of Changes==

An issue closely related to merge algorithms is the issue of exactly ''which'' files the version control system inputs into a the 3-way merge. In early client-server implementations, a file was the both the largest and smallest entity tracked by the version control system; that is, if several files were modified in support of a single logical change to e.g. a piece of software, those version control systems tracked changes to each individual file and had no tracking for the fact that a particular files changes were part of a larger entity (in this case, a group of files part of a single commit).

While the algorithms to perform textual merges improved when the switch was made from 2-way to 3-way merges, most modern improvements for end users in the area of merge stem from how the files input into the merge algorithm are selected. By tracking ''groups'' of changes, the version control system can make more effective decisions about which files to pick for merge, making the merge algorithms perform optimally.

==Repository Data Representation==

In most client-server (and local) version control implementations, the version control system tracks individual files. The implication of this approach is that the entire view of the data within the system is file-centric. CVS, for example, allows annotations, but only on a per-file basis. One of the major recent advancements (pioneered by Git) is the ability to track the entire repository as a single monolithic entity.

One of the results of this is that modern systems (usually DVCS) can track single blocks of text (like a single function in a computer program) across several files if it were moved. This allows users to focus on the actual data in the repository, rather than the files that hold the data. One of the most well known negative effects of the file-centric approach appeared in CVS in which file renames would appear in the repository as delete-create pairs, resulting in loss of version history.

Another result of decoupling data representation from the file system has already been mentioned: it allows groups of changes across multiple files to be tracked and associated. A related notion is the the change history that was traditionally represented as a line in most client-server systems is being represented as a DAG in more modern systems. The DAG is a more restricted data structure in some ways, but make many operations much simpler for the end user. The most notable example is when merging from a branch multiple times, a DAG can accurately represent what changes have been incorporated, whereas the traditional file-system oriented approach leaves it as an exercise for the user to re-merge the same changes over and over. This particular example is discussed in depth in Eric Sink's [http://www.ericsink.com/entries/merge_history.html article on merging].

=Wikis as an Extension to Version Control=

As use of the internet became more widespread and ''users'' of the web became some of its most important ''contributors'', concepts like the [http://en.wikipedia.org/wiki/Wiki Wiki] allowed users of a website to edit the website itself. Often, the website was just a collection of files (pages) being served, that visitors could create, modify and remove. One of the aspects of [http://c2.com/cgi/wiki?WikiCommunity WikiCommunity] is it is discussed on the original Wiki is the notion of a Wiki being open to change, and thus, Wikis tend to allow anonymous modifications to the wiki's pages. From this simple fact emerged the idea of saving previous versions of the wiki's pages.

So, taken loosely, Wikis are essentially web-enabled version control systems in which the users are anyone who visits the wiki. This participatory culture lends itself to a distributed model of information exchange, and yet most wikis are still using what amounts to a local or client-server version control system behind the scenes.

Looking to the future, it will be very interesting to see what can be done with wiki communities if they incorporate the important lessons learned from distributed version control systems.

The first (and only) example I have found of a community of users developing wiki-like content using distributed version control systems is [http://orgmode.org/worg/ Worg], a group of [http://www.gnu.org/software/emacs Emacs] [http://orgmode.org/ Org-Mode] users sharing information about the ways they use the Org-Mode software. Incidentally, Worg is itself a collection of Org-Mode files stored in [http://git-scm.com/ Git], one of the most prominent distributed version control systems.

=Further Reading=

For quick refreshers on [http://betterexplained.com/articles/a-visual-guide-to-version-control/ Version Control] and [http://betterexplained.com/articles/intro-to-distributed-version-control-illustrated/ Distributed Version Control], BetterExplained has excellent, concise articles.

Linus Torvalds, the creator and maintainer of both Linux kernel and Git, gave a entertaining and inforative [http://www.youtube.com/watch?v=4XpnKHJAok8&feature=player_embedded tech talk] at Google on version control and Git. A fabulous resource.

An excellent [http://www.ericsink.com/entries/merge_history.html entry] in Eric Sink's blog on how merge history and repostory representation are related.

IBM has an well-written [http://www.ibm.com/developerworks/java/library/j-subversion/index.html DeveloperWorks article] describing the ways is which Subversion improved upon CVS, along with some history of version control up until Subversion.

CSC/ECE 517 Fall 2009/wiki1a 5 rp

2009-09-08T05:37:16Z

7r3ad:

CSC/ECE 517 Fall 2009/wiki1a 5 rp

2009-09-07T18:41:33Z

7r3ad:

CSC/ECE 517 Fall 2009/wiki1a 5 rp

2009-09-07T09:33:52Z

7r3ad:

CSC/ECE 517 Fall 2009/wiki1a 5 rp

2009-09-07T05:48:56Z

7r3ad: Unfilling, since mediawiki doesn't like line breaks in a lot of its syntax

CSC/ECE 517 Fall 2009/wiki1a 5 rp

2009-09-07T05:46:08Z

7r3ad:

CSC/ECE 517 Fall 2009/wiki1a 5 rp

2009-09-07T05:44:18Z

7r3ad:

CSC/ECE 517 Fall 2009/wiki1a 5 rp

2009-09-07T05:42:28Z

7r3ad:

CSC/ECE 517 Fall 2009/wiki1a 5 rp

2009-09-07T00:05:23Z

7r3ad:

CSC/ECE 517 Fall 2009/wiki1a 5 rp

2009-09-06T21:16:15Z

7r3ad:

CSC/ECE 517 Fall 2009/wiki1a 5 rp

2009-09-06T17:51:48Z

7r3ad:

=History Of Version Control=

The defining characteristic of a version control system is its ability
to track changes to a document, or set of documents, over many
changes, or revisions. For the vast majority of applications, version
control systems have focused on tracking plain text files, such as
those used for programming source code, HTML documents, and various
markup syntax. Over the past 30 years or so, notions of how to
implement such systems have evolved and become more advanced.

==Local Version Control==

The first version control systems focused on local version control;
that is, centralized computer systems that were used by many users,
often at the same time. Because of this use case, these systems
focused on two main features:

* File Checkout and Locking
* File revision tracking

===File Checkout and Locking===

Because many users in a shared system may desire to edit a file
simultaneously, one of the first features developed for version
control systems was the ability to ''check out'' and ''lock'' a file.
When a user checks out a file, he or she reserves the right to be the
sole editor of that file until it is checked back in to revision
control. The first revision control systems designed for use in a
shared environment, such as [http://www.gnu.org/software/rcs/ RCS],
allowed files to be checked out and locked in this way. Other users
could check out the file, but only to view it. Thus, the files were
locked from editing by all but the user that had checked the file out
most recently.

===File Revision Tracking===

The primary feature of these early systems was the ability to check in
files at various points as they were altered, so that the history of
changes made to files under version control was kept permanently.
Thus, many users could alter many files over time, and the entire set
of documents under version control at a given point in time could be
recovered, preventing loss of valuable data, as well a providing a
record of what users made changes to files over time.

But, these local systems had two primary problems. First, they
required that every user log into a single computer to edit or access
the information in the repository. Second, they restricted a
particular file to having only one editor at any given time. The next
development in revision control, embodied by
[http://www.nongnu.org/cvs/ CVS], sought to address both of these
problems.

===Networked Revision Control: Client-Server===

As users moved away from logging into systems locally to make their
changes to files, the need for a revision control system that
supported remote operations emerged. The natural way to implement
such remote operations was as an extension of the existing system, and
by far the most prominent manifestation of this philosophy was present
in CVS, the concurrent versions system, which was initially based on
RCS.

The main feature driving the development of CVS was the need for many
users, each on his or her own machine, to be able to perform all the
operations present in the original RCS, but over a network connection,
and in a way that allowed for concurrent editting to take place. This
led to the development of a client-server model of revision control
systems, in which one central server would contain the canoncal
version of the repository, and various clients could connect to the
central server and perform file check outs and commits. This model is
very similar to the original RCS model, but rather than requiring
users of the system to log into the revision control system locally,
it allowed users to access and alter the contents of the repository
over the network.

Although CVS supports locking in the same way RCS does, CVS was among
the first version control systems to support a ''non-locking
repository''. This system allowed for concurrent editing of files
under revision control, and generated the need to develop new features
that addressed the resulting complexities. Chief among the new
features introduced to handle these complexities were the notions of
''branching'' and ''merging''. This allowed CVS to offer a
non-locking repository, which put the "concurrent" in CVS's
"concurrent versions system".

===Branching and Merging===

Inherent in the notion of concurrent editing is the problem of how to
reconcile conflicting changes to the same file. The solution to this
problem lay in allowing users of the revision control system to branch
a version of the repository and make (possibly many) changes to that
branch independent of the changes occurring on the main branch of the
repository, known as the trunk. Once a logical set of changes was
completed on a branch, that branch would then need to have its changes
reconciled with the current state of the repository on the trunk.
This process of reconciliation is known as merging.

This feature was critical in a multi-user client environment as it
allowed work to progress on multiple fronts simultaneously, only
requiring that the files be merged once the users of the system were
ready to reconcile changes with other users.

This approach presented two new problems, however.

First, the merging process was often difficult and time consuming,
leading many developers to avoid checking in their changes and merging
with other users because the merging process interrupted their normal
flow of work. Users were reluctant to create branches to relieve some
of this burden because branch operations in CVS were quite slow and
cumbersome.

Second, because many users checked in changes less frequently, much of
the current work on the repository was stored at the edges of the
network, that is, on the users' workstations, rather than in the
central server. Thus, while the central server may have been backed
up regularly and kept secure, a user's workstation could crash and
take hours, days or even weeks of work with it, and revision control
would have no record of any of the work that had been lost.

Both of these problems could be remedied by proper use of the revision
control system, but there were no technical measures that could be
taken to prevent such abuses. This left the market open for a
different approach to revision control.

==Distributed Revision Control==

CSC/ECE 517 Fall 2009/wiki1a 5 rp

2009-09-06T17:28:28Z

7r3ad:

=History Of Version Control=

The defining characteristic of a version control system is its ability
to track changes to a document, or set of documents, over many
changes, or revisions. For the vast majority of applications, version
control systems have focused on tracking plain text files, such as
those used for programming source code, HTML documents, and various
markup syntax. Over the past 30 years or so, notions of how to
implement such systems have evolved and become more advanced.

==Local Version Control==

The first version control systems focused on local version control;
that is, centralized computer systems that were used by many users,
often at the same time. Because of this use case, these systems
focused on two main features:

* File Checkout and Locking
* File revision tracking

===File Checkout and Locking===

Because many users in a shared system may desire to edit a file
simultaneously, one of the first features developed for version
control systems was the ability to check out and lock a file. When a
user checks out a file, he or she reserves the right to be the sole
editor of that file until it is checked back in to revision control.
The first revision control systems designed for use in a shared
environment, such as RCS, allowed files to be checked out and locked
in this way. Other users could check out the file, but only to view
it. Thus, the files were locked from editing by all but the user
that had checked the file out most recently.

===File Revision Tracking===

The primary feature of these early systems was the ability to check in
files at various points as they were altered, so that the history of
changes made to files under version control was kept permanently.
Thus, many users could alter many files over time, and the entire set
of documents under version control at a given point in time could be
recovered, preventing loss of valuable data, as well a providing a
record of what users made changes to files over time.

===Networked Revision Control: Client-Server===

As users moved away from logging into systems locally to make their
changes to files, the need for a revision control system that
supported remote operations emerged. The natural way to implement
such remote operations was as an extension of the existing system, and
by far the most prominent manifestation of this philosophy was present
in CVS, the concurrent versions system, which was initially based on
RCS.

The main feature driving the development of CVS was the need for many
users, each on his or her own machine, to be able to perform all the
operations present in the original RCS, but over a network connection.
This led to the development of a client-server model of revision
control systems, in which one central server would contain the
canoncal version of the repository, and various clients could connect
to the central server and perform file check outs and commits. This
model is very similar to the original RCS model, but rather than
requiring users of the system to log into the revision control system
locally, it allowed users to access and alter the contents of the
repository over the network.

The initial need to simply perform RCS-like operations over a network
led to a host of new problems associated with the concurrent editing
of files under revision control, and the need to develop new features
that addressed the resulting complexities. Chief among the new
features introduced to handle these complexities were the notions of
branching and merging.

===Branching and Merging===

Inherent in the notion of concurrent editing is the problem of how to
reconcile conflicting changes to the same file. The solution to this
problem lay in allowing users of the revision control system to branch
a version of the repository and make (possibly many) changes to that
branch independent of the changes occurring on the main branch of the
repository, known as the trunk. Once a logical set of changes was
completed on a branch, that branch would then need to have its changes
reconciled with the current state of the repository on the trunk.
This process of reconciliation is known as merging.

This feature was critical in a multi-user client environment as it
allowed work to progress on multiple fronts simultaneously, only
requiring that the files be merged once the users of the system were
ready to reconcile changes with other users.

This approach presented two new problems, however.

First, the merging process was often difficult and time consuming,
leading many developers to avoid checking in their changes and merging
with other users because the merging process interrupted their normal
flow of work. Users were reluctant to create branches to relieve some
of this burden because branch operations in CVS were quite slow and
cumbersome.

Second, because many users checked in changes less frequently, much of
the current work on the repository was stored at the edges of the
network, that is, on the users' workstations, rather than in the
central server. Thus, while the central server may have been backed
up regularly and kept secure, a user's workstation could crash and
take hours, days or even weeks of work with it, and revision control
would have no record of any of the work that had been lost.

Both of these problems could be remedied by proper use of the revision
control system, but there were no technical measures that could be
taken to prevent such abuses. This left the market open for a
different approach to revision control.

==Distributed Revision Control==

CSC/ECE 517 Fall 2009/wiki1a 5 rp

2009-09-05T22:51:10Z

7r3ad:

=History Of Version Control=

==Centralized Version Control==

===Local Version Control: RCS===

===The First Networked Version Control: CVS===

==Commercial Offerings==

===ClearCase===

===Perforce===