CSC/ECE 517 Fall 2014/ch1a 9 aa

From Expertiza_Wiki
Revision as of 21:48, 17 September 2014 by Aashetty (talk | contribs)
Jump to navigation Jump to search

What is Functional Programming?

In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids changing state and mutable data. The programming is done with the use of expressions, that is, it is a declarative programming paradigm. One key feature in a functional language is the concept of first-class functions. The idea is that you can pass functions as parameters to other functions and return them as values. Also, the output value of a function depends only on the arguments that are input to the function, unlike in imperative programming languages. Eliminating side effects, i.e. changes in state that do not depend on the function inputs, can make it much easier to understand and predict the behaviour of a program, which is one of the key motivations for the development of functional programming. Some examples of functional programming languages: Common Lisp Scheme Erlang Haskell

What is Object Oriented Programming?

Object-oriented programming (OOP) is based upon the concept of real world "objects". These objects have data fields called attributes that describe the object and some procedures associated with them called methods. Object-oriented programming takes the view that what we really care about are the objects we want to manipulate rather than the logic required to manipulate them.

Some examples of object oriented programming languages are: Simula Smalltalk C++ Java C#

Features of Functional Programming

Higher-order functions:

Higher-order functions (HOFs) are functions that take other functions as their arguments. A basic example of a HOF is map which takes a function and a list as its arguments, applies the function to all elements of the list, and returns the list of its results. Higher-order functions are very useful for refactoring code and reduce the amount of repetition. Let’s see an example of a higher order function that receives a message, transforms it in various ways, and forwards it to another server. 

class MessageHandler {
    	void handleMessage(Message msg, Function getClientCode) {
        	// ...
        	Message msg1 = msg.setClientCode(getClientCode());
        	// ...
        
        	sendMessage(msg1);
    	}
    
    	// ...
	}

	String getClientCodeOne() {
    	return "ABCD_123";
	}

	String getClientCodeTwo() {
    	return "123_ABCD";
	}

	MessageHandler handler = new MessageHandler();
	handler.handleMessage(someMsg, getClientCodeOne);

Here, we see that we have created no new types and no class hierarchy. We simply pass appropriate functions as a parameter. We don't restrict ourselves to class hierarchies: we can pass new functions at runtime and change them at any time with a much higher degree of granularity with less code.

Purity

Some functional languages allow expressions to yield actions in addition to return values. These actions are called side effects to emphasize that the return value is the most important outcome of a function (as opposed to the case in imperative programming). Languages that prohibit side effects are called pure. Even though some functional languages are impure they often contain a pure subset that is also useful as a programming language. It is usually beneficial to write a significant part of a functional program in a purely functional fashion and keep the code involving state and I/O to the minimum as impure code is more prone to errors.

Immutable data

Purely functional programs typically operate on immutable data. Instead of altering existing values, altered copies are created and the original is preserved. Since the unchanged parts of the structure cannot be modified, they can often be shared between the old and new copies, which saves memory.

Referential transparency

Pure computations yield the same value each time they are invoked. This property is called referential transparency and makes possible to conduct equational reasoning on the code. For instance if y = f x and g = h y y then we should be able to replace the definition of g with g = h (f x) (f x) and get the same result; only the efficiency might change.


Lazy evaluation

Since pure computations are referentially transparent they can be performed at any time and still yield the same result. This makes it possible to defer the computation of values until they are needed, that is, to compute them lazily. Lazy evaluation avoids unnecessary computations and allows, for example, infinite data structures to be defined and used. Let’s take a look at the following piece of code: 

String s1 = somewhatLongOperation1();
String s2 = somewhatLongOperation2();
String s3 = concatenate(s1, s2);

In an imperative language the order of evaluation would be clear. Because each function may affect or depend on an external state it would be necessary to execute them in order: first somewhatLongOperation1, then somewhatLongOperation2, followed by concatenate. Not so in functional languages. somewhatLongOperation1 and somewhatLongOperation2 can be executed concurrently because we're guaranteed no function affects or depends on global state. But what if we don't want to run the two concurrently, do we need to run them in order? The answer is no. We only need to run these operations when another function depends on s1 and s2. We don't even have to run them before concatenate is called - we can delay their evaluation until they're required within concatenate. If we replace concatenate with a function that has a conditional and uses only one of its two parameters we may never evaluate one of the parameters at all!

Recursion

Scala : An overview

Scala is an object-functional programming and scripting language generallly used in software applications. Scala has full support for functional programming (including currying, pattern matching,algebraic data types,lazy evaluation,tail recursion,immutability, etc.) and a very strong static type system. This allows programs written in Scala to be very concise and thus smaller in size than most general purpose programming languages. Many of Scala's design decisions were inspired by criticism over the shortcomings of Java.

Scala source code is intended to be compiled to Java bytecode, so that the resulting executable code runs on a Java virtual machine. Java libraries can be used directly in Scala code, and vice versa. 

object HelloWorld 
{
   def main(args: Array[String]) 
  {
    println("Hello, world!")
  }
}

This program consists of one method called main which takes the command line arguments, an array of strings, as parameter; the body of this method consists of a single call to the predefined method println with the greeting as argument. The main method does not return a value (it is a procedure method). Therefore, it is not necessary to declare a return type. Such a declaration introduces what is commonly known as a singleton object, that is a class with a single instance. The declaration above thus declares both a class called HelloWorld and an instance of that class, also called HelloWorld. This instance is created on demand, the first time it is used. Notice that the main method is not declared as static (like in Java) here. This is because static members (methods or fields) do not exist in Scala. Rather than defining static members, the Scala programmer declares these members in singleton objects.

Features of Scala

Scala is object-oriented

Scala is a pure object-oriented language in the sense that every value is an object. Types and behavior of objects are described by classes and traits. Classes are extended by subclassing and a flexible mixin-based composition mechanism as a clean replacement for multiple inheritance.

Scala is functional

Scala is also a functional language in the sense that every function is a value. Scala provides a lightweight syntax for defining anonymous functions, it supports higher-order functions, it allows functions to be nested, and supports currying. Scala's classes and its built-in support for pattern matching model algebraic types used in many functional programming languages. Furthermore, Scala's notion of pattern matching naturally extends to the processing of XML data with the help of right-ignoring sequence patterns. In this context, sequence comprehensions are useful for formulating queries. These features make Scala ideal for developing applications like web services.

Scala is statically typed

Scala is equipped with an expressive type system that enforces statically that abstractions are used in a safe and coherent manner. In particular, the type system supports: generic classes, variance annotations, upper and lower type bounds, inner classes and abstract types as object members, compound types, explicitly typed self references, views, and polymorphic methods.

Scala is extensible

In practice, the development of domain-specific applications often requires domain-specific language extensions. Scala provides a unique combination of language mechanisms that make it easy to smoothly add new language constructs in form of libraries: any method may be used as an infix or postfix operator, and closures are constructed automatically depending on the expected type (target typing). A joint use of both features facilitates the definition of new statements without extending the syntax and without using macro-like meta-programming facilities.

Scala interoperates with Java and .NET

Scala is designed to interoperate well with the popular Java 2 Runtime Environment (JRE). In particular, the interaction with the mainstream object-oriented Java programming language is as smooth as possible. Scala has the same compilation model (separate compilation, dynamic class loading) like Java and allows access to thousands of existing high-quality libraries.Support for the .NET Framework (CLR) is also available.

Similarities between Scala and Java

1) Both are JVM based language, Scala produce same byte code as Java and runs on Java Virtual Machine. Similar to Java compiler javac, Scala has a compiler scalac, which compiles Scala code into byte code. At this level, all JVM language like Groovy,JRuby, Scala becomes equals to Java, because they use same memory space, type system and run inside same JVM.

2) You can call Scala from Java and Java from Scala, it offers seems less integration. Moreover, you can reuse existing application code and open source Java libraries in Scala.

3) Major Java programming IDE like Eclipse, Netbeans and InetelliJ supports Scala.

4) One more similarity between Scala and Java is that both are Object Oriented, Scala goes one steps further and also supports functional programming paradigm, which is one of it's core strength.


Scala vs JAVA

Syntactic flexibility

Scala has a very powerful and flexible syntax as it relates to methods, both declaration and invocation. In Java you can create methods with different visibilities, modifiers andreturn types.Scala does allow for different visibilities on not just methods, but any members. For example: 

class Person {
  private var name = "Daniel Spiewak"
  val ssn = 1234567890    // public constant field
 
  def firstName() = splitName()(0)   // public method
 
  private def splitName() = name.split(" ")    // private method
 
  protected def guessAge() = {
    import Math._
    round(random * 20)
  }
}

Scala provides he option to import into a specific scope.The import statement within guessAge()is much like a Java static import statement which only provides access to the Math members within theguessAge() method. So we couldn’t just make a call to round() from within the splitName() method. Scala access modifiers are also quite a bit more powerful than Java’s. For example,protected by default limits access to only subclasses, unlike Java which also allows access to other classes in the same package.

Unified type system

Java makes a sharp distinction between primitive types (e.g. int and boolean) and reference types (any class). Only reference types are part of the inheritance scheme, deriving from java.lang.Object. In Scala, however, all types inherit from a top-level class Any, whose immediate children are AnyVal(value types, such as Int and Boolean) andAnyRef (reference types, as in Java). This means that the Java distinction between primitive types and boxed types (e.g. int vs. Integer) is not present in Scala; boxing and unboxing is completely transparent to the user.

For-expressions

Instead of the Java "foreach" loops for looping through an iterator, Scala has a much more powerful concept of for-expressions. These are similar to list comprehensions in languages such as Haskell, or a combination of list comprehensions and generator expressions in Python. For-expressions using the yield keyword allow a new collection to be generated by iterating over an existing one, returning a new collection of the same type. They are translated by the compiler into a series of map,flatMap and filter calls. Where yield is not used, the code approximates to an imperative-style loop, by translating to foreach. A simple example is: 

val s = for (x <- 1 to 25 if x*x > 50) yield 2*x
The result of running it is the following vector:
Vector(16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50)

Everything is an expression

Unlike C or Java, Scala makes no distinction between statements and expressions. All statements are in fact expressions that evaluate to some value. Functions that would be declared as returning void in Java, and statements like while that logically do not return a value, are in Scala considered to return the type Unit, which is a singleton type, with only one object of that type. 

// Java:
int hexDigit = x >= 10 ? x + 'A' - 10 : x + '0';

//Scala: 
val hexDigit = if (x >= 10) x + 'A' - 10 else x + '0'

Type inference

Due to type inference, the type of variables, function return values, and many other expressions can typically be omitted, as the compiler can deduce it. Examples are val x = "foo" (for an immutable, constant variable or immutable object) or var x = 1.5 (for a variable whose value can later be changed). Type inference in Scala is essentially local.

Anonymous functions

In Scala, functions are objects, and a convenient syntax exists for specifying anonymous functions. An example is the expression x => x < 2, which specifies a function with a single parameter, that compares its argument to see if it is less than 2.

An even shorter form of anonymous function uses placeholder variables: For example: 

list map { x => sqrt(x) }

can be written more concisely as

list map { sqrt(_) }

Immutability

Scala enforces a distinction between immutable (unmodifiable, read-only) variables, whose value cannot be changed once assigned, and mutable variables, which can be changed. A similar distinction is made between immutable and mutable objects. The distinction must be made when a variable is declared: Immutable variables are declared with val while mutable variables use var.

Tail recursion

Functional programming languages commonly provide tail call optimization to allow for extensive use of recursion without stack overflow problems. Limitations in Java bytecode complicate tail call optimization on the JVM. In general, a function that calls itself with a tail call can be optimized, but mutually recursive functions cannot. Trampolines have been suggested as a workaround.[24] Trampoline support has been provided by the Scala library with the object scala.util.control.TailCalls since Scala 2.8.0 (released July 14, 2010).[25]

Pattern Matching

pattern matching in Scala is really a lot like Java’s switch/case construct.  So in Java, one might write something like this: 

public boolean checkPrime(int number) {
    // checks if a number between 1 and 10 is prime
    switch (number) {
        case 1: return true;
        case 2: return true;
        case 3: return true;
        case 5: return true;
        case 7: return true;
 
        default: return false;
    }
}

One of the major limitations of switch/case in Java is that it can only be used on primitives.  You can’t use switch/case to test a String, for example (a need which arises more often than one would think).  In fact, the most complex type testable within switch/case is the Enum, and even this is just being reduced to its ordinal values under the surface The designers of Scala chose not to include this “feature” in their new language.Instead, they implemented a “new” concept called pattern matching.At a basic level, it allows algorithms which are very similar to the checkPrime(int) example: 

def checkPrime(number:Int):Boolean = {
  number match {
    case 1 => return true
    case 2 => return true
    case 3 => return true
    case 5 => return true
    case 7 => return true
 
    case _ => return false
  }
}

The biggest difference which likely jumps out at you is the lack of a default statement.Instead, we see the return of Scala’s ubiquitous wildcard character, the underscore. Literally read, this example means: match the value within number; in the case that it is 1, return true; in the case that it is 2, return true; …; for any previously unmatched value, return false. Scala case statements can’t “overflow” into each-other (causing multiple matches) like Java’s can, so even if we weren’t returning values, the algorithm would still be safe.

Traits

Java’s designers recognized the need for multiple typing (e.g. CollegeStudent is both a Student and a Worker), but they wanted to avoid the issues associated with inheriting conflicting method definitions along multiple paths.  Their solution was to design the interface mechanism, a feature which allows multiple typing without the complications of multiple inheritance.  Scala recognizes that interfaces have their issues.  So rather than blinding creating a reimplementation of the same problems found in either Java or C++, Scala takes a new approach.  Inspired by a combination of Java’s interfaces and Ruby’s mixins, the designers of Scala have created the trait construct. 


trait Book 
{
  def title:String
  def title_=(n:String):Unit
 
  def computePrice = title.length * 10
}

Scala’s traits are quite nice in that they can not only define abstract members, but also full method definitions. At the same time, they allow inheriting classes to inherit from more than one trait. They pass on their type information and implementations to their children, as well as enforcing the abstract members. At first glance, this seems like it would be just as bad as straight-up multiple inheritance, but it turns out the problems have been mitigated in some very clever ways. Traits are actually mixins, not true parent classes. Any non-abstract trait members are actually included in the inheriting class, as in physically part of the class.Well, not physically, but you get the picture.It’s as if the compiler performs a cut-and-paste with the non-abstract members and inserts them into the inheriting class.This means that there’s no ambiguity in the inheritance path, meaning no diamond problem. We can rewrite ourCollegeStudent example in Scala without redundancy or fear of paradox: 

abstract class Person {
  def schedule:Schedule
}
 
trait Student extends Person {
  private var classSchedule:Schedule = ...
 
  override def schedule = classSchedule
 
  def learn() = {...}
}
 
trait Worker extends Person {
  private var workSchedule:Schedule = ...
 
  override def schedule = workSchedule
 
  def work() = {...}
}
 
class CollegeStudent(school:School, company:Company) extends Student with Worker {
  // ...
}

Now if we make a call to the schedule method on an instance of CollegeStudent, the compiler knows that we’re referring to the implementation of schedule in the Worker trait.  This is because Worker was mixed in after theStudent trait.  

Retrieved from "https://wiki.expertiza.ncsu.edu/index.php?title=CSC/ECE_517_Fall_2014/ch1a_9_aa&oldid=86155"