Expertiza_Wiki - User contributions [en]

CSC/ECE 517 Fall 2009/wiki2 6 rp

2009-10-10T00:53:50Z

Rpdillon: /* Further Reading */

=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-10T00:52:30Z

Rpdillon:

=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, that has only one implementation, 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. 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-10T00:34:56Z

Rpdillon: /* Introduction */

CSC/ECE 517 Fall 2009/wiki2 6 rp

2009-10-10T00:34:06Z

Rpdillon: /* Introduction */

=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. 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.

=Further Reading=

CSC/ECE 517 Fall 2009/wiki2 6 rp

2009-10-10T00:16:39Z

Rpdillon: /* Delayed (Lazy) Evaluation */

=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:

* Procedural
* Object-Oriented
* Declarative

Declarative languages span a wide array of programming styles. For simplicity in this article, we will focus on functional languages, which are an important subset of declarative languages.

Many languages provide only one of the paradigms to their users. FORTRAN, COBOL, Pascal, C and BASIC are all procedural, Simula, Smalltalk and Eiffel are object-oriented and Haskell and 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. Java, one of the most widely used languages today, offers both procedural and object-oriented paradigms as well. OCaml is derived from ML, and offers functional and object-oriented styles. There are many others that have become popular in recent years.

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 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.

=Further Reading=

CSC/ECE 517 Fall 2009/wiki2 6 rp

2009-10-10T00:14:49Z

Rpdillon:

=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:

* Procedural
* Object-Oriented
* Declarative

Declarative languages span a wide array of programming styles. For simplicity in this article, we will focus on functional languages, which are an important subset of declarative languages.

Many languages provide only one of the paradigms to their users. FORTRAN, COBOL, Pascal, C and BASIC are all procedural, Simula, Smalltalk and Eiffel are object-oriented and Haskell and 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. Java, one of the most widely used languages today, offers both procedural and object-oriented paradigms as well. OCaml is derived from ML, and offers functional and object-oriented styles. There are many others that have become popular in recent years.

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 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 the 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.

=Further Reading=

File:Server-logger-invert.png

2009-10-10T00:14:17Z

Rpdillon:

File:Server-logger.png

2009-10-10T00:14:03Z

Rpdillon:

CSC/ECE 517 Fall 2009/wiki2 6 rp

2009-10-10T00:08:32Z

Rpdillon:

=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:

* Procedural
* Object-Oriented
* Declarative

Declarative languages span a wide array of programming styles. For simplicity in this article, we will focus on functional languages, which are an important subset of declarative languages.

Many languages provide only one of the paradigms to their users. FORTRAN, COBOL, Pascal, C and BASIC are all procedural, Simula, Smalltalk and Eiffel are object-oriented and Haskell and 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. Java, one of the most widely used languages today, offers both procedural and object-oriented paradigms as well. OCaml is derived from ML, and offers functional and object-oriented styles. There are many others that have become popular in recent years.

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 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:

+----------------+ +----------------+
| | | |
| Web | depends | File |
| Server *----------->| Logger |
| | on | |
| cBLU | | cBLU |
+----------------+ +----------------+

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.

+---------------+
| |
+-----* File |
+-------------+ /-------------\ | | Logger |
| | | |<----+ | cBLU |
| Web *----->| Logger | +---------------+
| Server | | |
| cBLU | | cYEL |<----+ +---------------+
+-------------+ \-------------/ | | |
+-----* Network |
| Logger |
| cBLU |
+---------------+

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 the 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.

=Further Reading=

CSC/ECE 517 Fall 2009/wiki2 6 rp

2009-10-10T00:05:25Z

Rpdillon: /* Introduction */

=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:

* Procedural
* Object-Oriented
* Declarative

Declarative languages span a wide array of programming styles. For simplicity in this article, we will focus on functional languages, which are an important subset of declarative languages.

Many languages provide only one of the paradigms to their users. FORTRAN, COBOL, Pascal, C and BASIC are all procedural, Simula, Smalltalk and Eiffel are object-oriented and Haskell and 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. Java, one of the most widely used languages today, offers both procedural and object-oriented paradigms as well. OCaml is derived from ML, and offers functional and object-oriented styles. There are many others that have become popular in recent years.

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 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:

+----------------+ +----------------+
| | | |
| Web | depends | File |
| Server *----------->| Logger |
| | on | |
| cBLU | | cBLU |
+----------------+ +----------------+

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.

+---------------+
| |
+-----* File |
+-------------+ /-------------\ | | Logger |
| | | |<----+ | cBLU |
| Web *----->| Logger | +---------------+
| Server | | |
| cBLU | | cYEL |<----+ +---------------+
+-------------+ \-------------/ | | |
+-----* Network |
| Logger |
| cBLU |
+---------------+

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 the 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.

=Further Reading=

CSC/ECE 517 Fall 2009/wiki2 6 rp

2009-10-10T00:05:02Z

Rpdillon:

=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:

* Procedural
* Object-Oriented
* Declarative

Declarative languages span a wide array of programming styles. For simplicity in this article, we will focus on functional languages, which are an important subset of declarative languages.

Many languages provide only one of the paradigms to their users. FORTRAN, COBOL, Pascal, C and BASIC are all procedural, Simula, Smalltalk and Eiffel are object-oriented and Haskell and 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. Java, one of the most widely used languages today, offers both procedural and object-oriented paradigms as well. OCaml is derived from ML, and offers functional and object-oriented styles. There are many others that have become popular in recent years.

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 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:

+----------------+ +----------------+
| | | |
| Web | depends | File |
| Server *----------->| Logger |
| | on | |
| cBLU | | cBLU |
+----------------+ +----------------+

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.

+---------------+
| |
+-----* File |
+-------------+ /-------------\ | | Logger |
| | | |<----+ | cBLU |
| Web *----->| Logger | +---------------+
| Server | | |
| cBLU | | cYEL |<----+ +---------------+
+-------------+ \-------------/ | | |
+-----* Network |
| Logger |
| cBLU |
+---------------+

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 the 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.

=Further Reading=

CSC/ECE 517 Fall 2009/wiki1a 5 rp

2009-09-12T08:50:54Z

Rpdillon:

=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.

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-12T08:49:49Z

Rpdillon:

=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.

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-12T08:23:28Z

Rpdillon:

=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.