
By Joe Morrison, Kalani Thielen | Article Rating: |
|
May 23, 2008 02:00 PM EDT | Reads: |
27,972 |
sum 1:[2, 3, 4, 5]
1 + sum [2, 3, 4, 5]
1 + sum 2:[3, 4, 5]
1 + 2 + sum [3, 4, 5]
1 + 2 + sum 3:[4, 5]
1 + 2 + 3 + sum [4, 5]
1 + 2 + 3 + sum 4:[5]
1 + 2 + 3 + 4 + sum [5]
1 + 2 + 3 + 4 + sum 5:[]
1 + 2 + 3 + 4 + 5 + sum []
1 + 2 + 3 + 4 + 5 + 0
Having made each step of the computation explicit, the derivation of the final result is clear. What’s more, we can be certain that each step in the above derivation completely describes the computation, as we’ve given up the possibility of implicit “side effects” happening between steps. You can imagine that if the “sum” function had a side-effect (like updating the input list) this simple two-line example would become much more difficult to understand.
Because a functional program implies that you can always substitute a function call with its result, there are two very important things that our compiler can do to help us without any effort on our part. The first is that, according to the principle of referential transparency, the compiler can substitute the final result for the call to “sum” at compile-time, without changing the behavior of the program. This has the effect, in our example, of doing no runtime computation at all!
In more realistic cases, the compiler may not be able to compute the entire function ahead of time, but with this principle as a guide it can still simplify the inevitable runtime computation by partially evaluating as much of it as possible at compile-time. The second thing the compiler can do is to perform the final computation in parallel where possible. Given some simple properties of the functions involved (in this case, the fact that a + b + c = a + (b + c) = (a + b) + c), the compiler could easily generate code to compute the final sum as (with concurrent evaluation denoted by parentheses):
1 + 2 + 3 + 4 + 5 + 0
(1 + 2) + (3 + 4) + (5 + 0)
3 + 7 + 5
(3 + 7) + (5)
10 + 5
(10 + 5)
15
Remarkably, the compiler can (given just these few reasonable assumptions) produce a very specialized, efficient executable from our compact functional program. The key to passing all of this complexity off to the compiler is that we go out of our way to leave the compiler as many implementation options as possible. To summarize this viewpoint: functional programs describe what is to be computed, allowing functional compilers to decide how to compute it. Unnecessary complexity creeps into software projects where these problems of what and how are intermixed.
Introduction to Scala
A good way for Java programmers to experiment with
functional programming concepts is to give Scala a try. Scala is an interesting
programming language first released in 2003 by Martin Odersky, a computer science
professor at the Swiss Federal Institute of Technology, and one of the
designers of Java generics. Scala is a multi-paradigm language, smoothly
integrating features of both object-oriented and functional languages. Most
importantly it is fully interoperable with Java. It compiles to JVM bytecodes
(i.e., standard .class files), Java libraries can be used freely in Scala
programs, and it is possible to inherit from Java classes and implement Java
interfaces directly in Scala. An Eclipse plug-in is even available.
Installation Instructions via the Eclipse Plug-in
If you’re an Eclipse user, it’s easy to get started with
Scala by installing the Scala Eclipse Plug-in. You don’t even have to install
Scala first. Just select:
Help -> Software Updates -> Find and Install -> Search for new features to install
and create a new remote site called “Scala Plugin Update Site” with this URL:
http://scala-lang.org/downloads/scala-plugin
Install the feature Scala Plugin UpdateSite. If you get an error that package org.eclipse.pde.runtime is missing, then go back to:
Help -> Software Updates -> Find and Install -> Search for new features to install
and select The Eclipse Project Updates, expand the category corresponding to your version of Eclipse, and select the Eclipse Plugin Development Environment. Install it and restart Eclipse. That plug-in includes the required org.eclipse.pde.runtime package, so once it’s installed you should be able to install the Scala plug-in.
If you are not an Eclipse user, you can install Scala the traditional way, starting from this URL:
http://www.scala-lang.org/downloads/index.html
Once you’ve installed Scala, create a new Scala Project.
Create a package called com.lab49.example and within it create a Scala Object
called
package com.lab49.example;
object Main {
def main(args: Array[String]) {
println(“Hello, world!”)
}
}
Select Run as Scala Application. If it displays Hello, world then congratulations! You have just written your first Scala application.
Now let’s try rewriting the sum function in Scala:
package com.lab49.example;
object Main {
def sum (l: List[Int]): Int = {
l match {
case Nil => 0
case ::(x,xs)
=> x + sum(xs)
}
}
def main(args:
Array[String]) {
println
(sum(List(1, 2, 3, 4, 5)));
}
}
This is slightly more verbose, but similar in spirit to the two-line Haskell example we started with. The Haskell version didn’t declare a package, enclosing class, or Main function, so a fair comparison is to look at only the sum function that is six lines long in Scala and includes type declarations. Note the pattern-matching syntax, for example, the use of :: to match a list and split the head node from the remaining nodes. This is an example of a nice Scala feature called case classes that lets you write pattern-matching case statements for your own classes as well as built-in ones.
Note that it’s not the objective of this paper to be a Scala tutorial. There are already many of those on the Web. But we want to introduce Scala because it provides excellent support for functional programming, fits well with the Java technology stack, and is gaining momentum in the Java community.
Published May 23, 2008 Reads 27,972
Copyright © 2008 SYS-CON Media, Inc. — All Rights Reserved.
Syndicated stories and blog feeds, all rights reserved by the author.
More Stories By Joe Morrison
Joe Morrison is a managing consultant at Lab49, and has over 20 years of experience leading engineering teams in designing and building complex network-based applications. His projects have ranged from distributed object research at Verizon Laboratories, to value chain management software at Benchmarking Partners in Boston, to in-the-trenches SOA projects for financial services firms in New York. Joe holds a BMath degree in computer science from the University of Waterloo, and a master's degree in computer science from MIT. He is a regular blogger on http://blog.lab49.com/.
More Stories By Kalani Thielen
Kalani Thielen is a Lab49 technology consultant, working in the financial services industry. Prior to joining Lab49 in 2006, he worked for six years developing products for the publishing, advertising, and communications industries. As a specialist in programming language theory, his present work focuses on the development and certification of compilers for bond pricing and trading languages.
![]() Feb. 20, 2019 10:30 AM EST |
By Pat Romanski Feb. 20, 2019 08:00 AM EST |
By Zakia Bouachraoui Feb. 20, 2019 05:00 AM EST |
By Yeshim Deniz Feb. 20, 2019 04:15 AM EST |
By Zakia Bouachraoui ![]() Feb. 19, 2019 04:15 PM EST |
By Yeshim Deniz ![]() Feb. 18, 2019 07:45 AM EST |
By Zakia Bouachraoui Feb. 17, 2019 05:00 PM EST |
By Elizabeth White ![]() Feb. 16, 2019 04:45 PM EST Reads: 14,062 |
By Roger Strukhoff Feb. 14, 2019 05:00 PM EST |
By Elizabeth White Feb. 13, 2019 08:15 PM EST |