Expertiza_Wiki - User contributions [en]

CSC/ECE 517 Fall 2014/final M1455 yaaa

2014-12-04T02:01:09Z

Aashetty: /* Implementation of the Final Requirements */

This wiki page contains design details for the project on [https://github.com/servo/servo/wiki/Replace-C-libraries-student-project Evaluate replacing C libraries with modern Rust equivalents] for the Mozilla research project [http://github.com/servo/servo/wiki/Design Servo].

== Background Information <ref>http://wiki.expertiza.ncsu.edu/index.php/CSC/ECE_517_Fall_2014/oss_M1455_asa</ref> ==

===Rust===
[http://www.rust-lang.org/ Rust] is a new programming language for developing reliable and efficient systems. It is designed to support concurrency and parallelism in building platforms that take full advantage of modern hardware. Its static type system is safe and expressive and it provides strong guarantees about isolation, concurrency execution and memory safety.
Rust combines powerful and flexible modern programming constructs with a clear performance model to make program efficiency predictable and manageable. One important way it achieves this is by allowing fine-grained control over memory allocation through contiguous records and stack allocation. This control is balanced with the absolute requirement of safety: Rust’s type system and runtime guarantee the absence of data races, buffer overflow, stack overflow or access to uninitialized or deallocated memory.

===Servo===
[http://en.wikipedia.org/wiki/Servo_%28layout_engine%29 Servo] is an experimental project to build a Web browser engine for a new generation of hardware: mobile devices, multi-core processors and high-performance GPUs.
Servo builds on top of Rust to provide a secure and reliable foundation. Rust’s lightweight task mechanism promises to allow fine-grained isolation between browser components, such as tabs and extensions, without the need for expensive runtime protection schemes, like operating system process isolation. Servo is not designed to create a full browser but is rather focused on creating a reliable and fast browser engine.

== Introduction ==
Servo currently depends on a lot of C libraries for image decoding. We wish to evaluate switching some of these to new Rust libraries. This project involves rewriting the code that uses these libraries as well as taking measurements before and after to determine the costs involved.

====Setup of Development Environment====
Servo is currently developed on 64bit OS X and 64bit Linux.

The steps needed to build on a Debian based 64 bit Linux machine are included below. The instructions for other platforms are available [https://github.com/servo/servo#prerequisites here].

* Install the prerequisite dependencies
<pre>
sudo apt-get install curl freeglut3-dev \
libfreetype6-dev libgl1-mesa-dri libglib2.0-dev xorg-dev \
msttcorefonts gperf g++ cmake python-virtualenv \
libssl-dev libglfw-dev
</pre>

* Clone and build servo repository
<pre>
git clone https://www.github.com/servo/servo
cd servo
./mach build
./mach run tests/html/about-mozilla.html
</pre>

== Architecture of system <ref>https://github.com/servo/servo/wiki/Design#task-supervision-diagram</ref> ==

=== Task Supervision Diagram ===

[[File:TaskSupervision.png]]

=== Task Communication Diagram ===

[[File:TaskCommunication.png]]

The above diagrams gives us an overview of the Servo's architecture.
*Each box represents a Rust task.
*Primary tasks are the ones which are represented by blue boxes.
*Gray boxes are for auxiliary tasks.
*White boxes are for worker tasks. Each such box represents several tasks, the precise number of which are decided by the workload.
*Supervisor relationships are shown by dashed lines.
*Communication channels are shown by solid lines.

The scope of our project is limited to changing the libraries used in the image decoding task shown above.

== Requirement analysis ==

Servo currently depends on a lot of C libraries, because Rust equivalents for these libraries did not exist when the project started. Our project is to evaluate switching some of these to new Rust libraries that have since been created. It involves rewriting the code that uses these libraries as well as taking measurements before and after to determine the costs involved.<ref>https://github.com/servo/servo/wiki/Replace-C-libraries-student-project</ref>

Initial step

Our [http://wiki.expertiza.ncsu.edu/index.php/CSC/ECE_517_Fall_2014/oss_M1455_asa initial step], implemented for the OSS project involved:
# Building Servo.
# Adding [http://doc.servo.org/util/time/fn.time.html timing code] to the image decoding implementation in the net crate.
# Rebuilding Servo.
# Reporting numbers for different kinds of images (i.e. PNG, JPEG, GIF).

Final Requirements

Our final project requirements are to:
* Build Servo and add code that reports (via the println! macro) the time required to decode images into displayable pixels.
* Add image decoding timing to the profiler.
* Import the [https://github.com/PistonDevelopers/freetype-rs freetype-rs] library to replace [https://github.com/servo/rust-freetype rust-freetype] in Servo, rewriting necessary code.<ref>https://github.com/servo/servo/issues/3369</ref> For this, we are to use [http://doc.crates.io/ Cargo], the dependency manager for Servo.
* Import the [https://github.com/PistonDevelopers/image rust-image] library to replace the [https://github.com/servo/rust-stb-image rust-stb-image] and [https://github.com/nothings/stb stb-image] libraries and rewrite the <code>load_from_memory</code> function which uses these libraries.<ref>https://github.com/servo/servo/issues/3368</ref>
* Report the timing differences for loading PNGs and non-PNGs on the same benchmarks. For this step, we are to consider profiling the result and optimizing the hotspots in rust-image.

== Implementation of the Final Requirements ==

1. Add Image Decoding time to the Profiler
To profile the time required by the load_from_memory to decode an image, we make a call to the profiler which outputs the time taken to decode on the console. To enable the profiler to do so, the following files were changed:
*image_cache_task.rs
*lib.rs
*time.rs
To invoke the profiler, we added a category under which to group the timings and passed a TimeProfilerChan (ie. a channel for communicating with the profiler task) to the ImageCacheTask::new method. On successfully building and running servo, we get the following image timings by profiler on the console:
<pre> ./mach run -p 1 https://optipng.sourceforge.net/pngtech/img/lena.html </pre>
[[File:Profiler.png]]

2. Imported the freetype-rs library to replace rust-freetype in Servo.
We replaced the currently used rust-freetype library with the freetype-rs library. To enable proper functioning of servo after importing the new library, following files were modified in the repository [https://github.com/PistonDevelopers/freetype-rs PistonDevelopers/freetype-rs]:
*Cargo.toml
*src/ffi.rs
*src/lib.rs
*src/lib.rs
*src/library.rs
*src/tt_os2.rs
These changes were committed and have been pulled by PistonDevelopers. Check the changes on [https://github.com/PistonDevelopers/freetype-rs/pull/70 pull request] for more info.

3. Imported the rust-image library to replace the rust-stb-image and stb-image libraries and rewrite the load_from_memory function which uses these libraries.
In order to import the new library we modified the following files files in the repository [https://github.com/ankit3005/servo]:
*Cargo.toml
*components/net/lib.rs
*components/net/image_cache_task.rs
*components/net/image/base.rs
*components/net/image/holder.rs
*components/gfx/render_context.rs
*components/gfx/lib.rs
*components/gfx/Cargo.toml
*components/gfx/display_list/mod.rs
*components/layout/display_list_builder.rs
*components/layout/lib.rs

4. Reported the timing differences for loading PNGs and non-PNGs on the same benchmarks.
Once the new image library was imported , passed in several test images to record the decoding timing for different images.
The timing was compared with the decoding time for images by passing in the same images to the servo build containing the C image library.

== Data and component design <ref>http://www.rust-ci.org/PistonDevelopers/piston/doc/image/index.html</ref>==

===Data Design===
The system entities that the project deals with is present in the image crate.

The structs and enums used to represent images are as below :

Structures
{| class = "wikitable"
|-
|ImageBuf
|An Image whose pixels are contained within a vector
|-
|Luma
|A type to hold a grayscale pixel
|-
|LumaA
|A type to hold a grayscale pixel with an alpha channel
|-
|MutPixels
|Mutable pixel iterator
|-
|Pixels
|Immutable pixel iterator
|-
|Rgb
|A type to hold an RGB pixel
|-
|Rgba
|A type to hold an RGB pixel with an alpha channel
|-
|SubImage
|A View into another image
|}

Enums
{| class="wikitable"
|-
|ColorType
|An enumeration over supported color types and their bit depths
|-
|DynamicImage
|A Dynamic Image
|-
|FilterType
|Available Sampling Filters
|-
|ImageError
|An enumeration of Image Errors
|-
|ImageFormat
|An enumeration of supported image formats. Not all formats support both encoding and decoding.
|}

===Component Design===

Rust image : It is an image processing library. This crate provides basic imaging processing functions and methods for converting to and from image formats.
All image processing functions provided operate on types that implement the GenericImage trait and return an ImageBuf. The details of other modules and traits included are :

Modules<ref>http://doc.rust-lang.org/guide.html#crates-and-modules</ref>
{| class="wikitable"
|-
|gif
|Decoding of GIF Images
|-
|imageops
|Image Processing Functions
|-
|jpeg
|Decoding and Encoding of JPEG Images
|-
|png
|Decoding and Encoding of PNG Images
|-
|ppm
|Encoding of portable pixmap Images
|-
|webp
|Decoding of Webp Images
|}

Traits<ref>http://rustbyexample.com/trait.html</ref>
{| class="wikitable"
|-
|GenericImage
|A trait for manipulating images.
|-
|ImageDecoder
|The trait that all decoders implement
|-
|MutableRefImage
|A trait for images that allow providing mutable references to pixels.
|-
|Pixel
|A trait that all pixels implement.
|}

Functions
{| class="wikitable"
|-
|load
|Create a new image from a Reader
|-
|load_from_memory
|Create a new image from a byte slice
|-
|open
|Open the image located at the path specified. The image's format is determined from the path's file extension
|}

== Design Principles ==

We are adhering to the following design principles for our implementation:

'''Open-Closed Principle'''<ref>http://en.wikipedia.org/wiki/Open/closed_principle</ref>

Although our task is to evaluate replacing C libraries with Rust libraries, we won't actually be modifying any existing functionality.

'''Interface Segregation Principle'''<ref>http://en.wikipedia.org/wiki/Interface_segregation_principle</ref>

The existing code is currently using the ''rust-freetype'' library for rendering fonts on the browser. We will be replacing this with the ''freetype-rs'' library, which divides the functionality offered by the former into smaller libraries which can be individually implemented instead of calling the entire library.

== Design Pattern==

We have implemented the Adapter Pattern in our Project:

When we updated the image library, the function load_from_memory() in base.rs had to be updated since the return from the updated function accepts a different set of parameters.
We implemented the Adapter pattern as a wrapper function over the new load_from_memory() function which performs the below functions:
1. Based on the file extension generate the ImageFormat Enum.
2. The return of the new function is a Result<DynamicImage>. This needs to be converted into a DynamicImage struct.
<pre>
pub fn load_from_memory(buffer: &[u8],ext: &str) -> Option<DynamicImage> {
if buffer.len() == 0 {
return None;
}
else {
//Retrieve the ImageFormat enum to be passed into the updated function
let image_type: Option< servo_image::ImageFormat > = get_format(ext);
if image_type == None
{
panic!("Image format not supported!");
}
else{
let new_image_type: servo_image::ImageFormat = image_type.unwrap();

//The updated function returns a Result<DynamicImage>
//below code resolves it to be returned by the wrapper function
let result = servo_image::load_from_memory(buffer,new_image_type);
if result.is_ok() {
let v = result.unwrap();
return Some(v);
}
else {
return None;
}
}
}
}

</pre>

==Flowchart describing Project Implementation==
[[File:Flowchart_final_M1455.JPG]]

== UML diagrams ==

===Class Diagram===
[[File:Class_diagram_M1455.JPG]]

== Proposed Test Cases ==

The project does not plan to add new functionality.
The test-cases we propose to run are will ensure that tasks that could be performed with the older C libraries can be executed.

The following test cases are proposed.

# Render different webpages with different fonts. Ensure the text renders correctly
# Render images of different formats (png, jpeg, bmp, gif) of different resolutions. Ensure that the images are rendered correctly.
# Record time taken to render and compare against time taken by the older libraries, for both image and text.

== References ==
<references/>

== See Also ==
[http://wiki.expertiza.ncsu.edu/index.php/CSC/ECE_517_Fall_2014/oss_M1455_asa Initial Step Details]

CSC/ECE 517 Fall 2014/final M1455 yaaa

2014-12-04T01:57:11Z

Aashetty: /* Implementation of the Final Requirements */

This wiki page contains design details for the project on [https://github.com/servo/servo/wiki/Replace-C-libraries-student-project Evaluate replacing C libraries with modern Rust equivalents] for the Mozilla research project [http://github.com/servo/servo/wiki/Design Servo].

== Background Information <ref>http://wiki.expertiza.ncsu.edu/index.php/CSC/ECE_517_Fall_2014/oss_M1455_asa</ref> ==

===Rust===
[http://www.rust-lang.org/ Rust] is a new programming language for developing reliable and efficient systems. It is designed to support concurrency and parallelism in building platforms that take full advantage of modern hardware. Its static type system is safe and expressive and it provides strong guarantees about isolation, concurrency execution and memory safety.
Rust combines powerful and flexible modern programming constructs with a clear performance model to make program efficiency predictable and manageable. One important way it achieves this is by allowing fine-grained control over memory allocation through contiguous records and stack allocation. This control is balanced with the absolute requirement of safety: Rust’s type system and runtime guarantee the absence of data races, buffer overflow, stack overflow or access to uninitialized or deallocated memory.

===Servo===
[http://en.wikipedia.org/wiki/Servo_%28layout_engine%29 Servo] is an experimental project to build a Web browser engine for a new generation of hardware: mobile devices, multi-core processors and high-performance GPUs.
Servo builds on top of Rust to provide a secure and reliable foundation. Rust’s lightweight task mechanism promises to allow fine-grained isolation between browser components, such as tabs and extensions, without the need for expensive runtime protection schemes, like operating system process isolation. Servo is not designed to create a full browser but is rather focused on creating a reliable and fast browser engine.

== Introduction ==
Servo currently depends on a lot of C libraries for image decoding. We wish to evaluate switching some of these to new Rust libraries. This project involves rewriting the code that uses these libraries as well as taking measurements before and after to determine the costs involved.

====Setup of Development Environment====
Servo is currently developed on 64bit OS X and 64bit Linux.

The steps needed to build on a Debian based 64 bit Linux machine are included below. The instructions for other platforms are available [https://github.com/servo/servo#prerequisites here].

* Install the prerequisite dependencies
<pre>
sudo apt-get install curl freeglut3-dev \
libfreetype6-dev libgl1-mesa-dri libglib2.0-dev xorg-dev \
msttcorefonts gperf g++ cmake python-virtualenv \
libssl-dev libglfw-dev
</pre>

* Clone and build servo repository
<pre>
git clone https://www.github.com/servo/servo
cd servo
./mach build
./mach run tests/html/about-mozilla.html
</pre>

== Architecture of system <ref>https://github.com/servo/servo/wiki/Design#task-supervision-diagram</ref> ==

=== Task Supervision Diagram ===

[[File:TaskSupervision.png]]

=== Task Communication Diagram ===

[[File:TaskCommunication.png]]

The above diagrams gives us an overview of the Servo's architecture.
*Each box represents a Rust task.
*Primary tasks are the ones which are represented by blue boxes.
*Gray boxes are for auxiliary tasks.
*White boxes are for worker tasks. Each such box represents several tasks, the precise number of which are decided by the workload.
*Supervisor relationships are shown by dashed lines.
*Communication channels are shown by solid lines.

The scope of our project is limited to changing the libraries used in the image decoding task shown above.

== Requirement analysis ==

Servo currently depends on a lot of C libraries, because Rust equivalents for these libraries did not exist when the project started. Our project is to evaluate switching some of these to new Rust libraries that have since been created. It involves rewriting the code that uses these libraries as well as taking measurements before and after to determine the costs involved.<ref>https://github.com/servo/servo/wiki/Replace-C-libraries-student-project</ref>

Initial step

Our [http://wiki.expertiza.ncsu.edu/index.php/CSC/ECE_517_Fall_2014/oss_M1455_asa initial step], implemented for the OSS project involved:
# Building Servo.
# Adding [http://doc.servo.org/util/time/fn.time.html timing code] to the image decoding implementation in the net crate.
# Rebuilding Servo.
# Reporting numbers for different kinds of images (i.e. PNG, JPEG, GIF).

Final Requirements

Our final project requirements are to:
* Build Servo and add code that reports (via the println! macro) the time required to decode images into displayable pixels.
* Add image decoding timing to the profiler.
* Import the [https://github.com/PistonDevelopers/freetype-rs freetype-rs] library to replace [https://github.com/servo/rust-freetype rust-freetype] in Servo, rewriting necessary code.<ref>https://github.com/servo/servo/issues/3369</ref> For this, we are to use [http://doc.crates.io/ Cargo], the dependency manager for Servo.
* Import the [https://github.com/PistonDevelopers/image rust-image] library to replace the [https://github.com/servo/rust-stb-image rust-stb-image] and [https://github.com/nothings/stb stb-image] libraries and rewrite the <code>load_from_memory</code> function which uses these libraries.<ref>https://github.com/servo/servo/issues/3368</ref>
* Report the timing differences for loading PNGs and non-PNGs on the same benchmarks. For this step, we are to consider profiling the result and optimizing the hotspots in rust-image.

== Implementation of the Final Requirements ==

1. Add Image Decoding time to the Profiler
To profile the time required by the load_from_memory to decode an image, we make a call to the profiler which outputs the time taken to decode on the console. To enable the profiler to do so, the following files were changed:
*image_cache_task.rs
*lib.rs
*time.rs
To invoke the profiler, we added a category under which to group the timings and passed a TimeProfilerChan (ie. a channel for communicating with the profiler task) to the ImageCacheTask::new method. On successfully building and running servo, we get the following image timings by profiler on the console:
<pre> ./mach run -p 1 https://optipng.sourceforge.net/pngtech/img/lena.html </pre>
[[File:Profiler.png]]

2. Imported the freetype-rs library to replace rust-freetype in Servo.
We replaced the currently used rust-freetype library with the freetype-rs library. To enable proper functioning of servo after importing the new library, following files were modified in the repository [https://github.com/PistonDevelopers/freetype-rs PistonDevelopers/freetype-rs]:
*Cargo.toml
*src/ffi.rs
*src/lib.rs
*src/lib.rs
*src/library.rs
*src/tt_os2.rs
These changes were committed and have been pulled by PistonDevelopers. Check the changes on [https://github.com/PistonDevelopers/freetype-rs/pull/70 pull request] for more info.

3. Imported the rust-image library to replace the rust-stb-image and stb-image libraries and rewrite the load_from_memory function which uses these libraries.
In order to import the new library we modified the following files files in the repository []:
*Cargo.toml
*components/net/lib.rs
*components/net/image_cache_task.rs
*components/net/image/base.rs
*components/net/image/holder.rs
*components/gfx/render_context.rs
*components/gfx/lib.rs
*components/gfx/Cargo.toml
*components/gfx/display_list/mod.rs
*components/layout/display_list_builder.rs
*components/layout/lib.rs

4. Reported the timing differences for loading PNGs and non-PNGs on the same benchmarks.

== Data and component design <ref>http://www.rust-ci.org/PistonDevelopers/piston/doc/image/index.html</ref>==

===Data Design===
The system entities that the project deals with is present in the image crate.

The structs and enums used to represent images are as below :

Structures
{| class = "wikitable"
|-
|ImageBuf
|An Image whose pixels are contained within a vector
|-
|Luma
|A type to hold a grayscale pixel
|-
|LumaA
|A type to hold a grayscale pixel with an alpha channel
|-
|MutPixels
|Mutable pixel iterator
|-
|Pixels
|Immutable pixel iterator
|-
|Rgb
|A type to hold an RGB pixel
|-
|Rgba
|A type to hold an RGB pixel with an alpha channel
|-
|SubImage
|A View into another image
|}

Enums
{| class="wikitable"
|-
|ColorType
|An enumeration over supported color types and their bit depths
|-
|DynamicImage
|A Dynamic Image
|-
|FilterType
|Available Sampling Filters
|-
|ImageError
|An enumeration of Image Errors
|-
|ImageFormat
|An enumeration of supported image formats. Not all formats support both encoding and decoding.
|}

===Component Design===

Rust image : It is an image processing library. This crate provides basic imaging processing functions and methods for converting to and from image formats.
All image processing functions provided operate on types that implement the GenericImage trait and return an ImageBuf. The details of other modules and traits included are :

Modules<ref>http://doc.rust-lang.org/guide.html#crates-and-modules</ref>
{| class="wikitable"
|-
|gif
|Decoding of GIF Images
|-
|imageops
|Image Processing Functions
|-
|jpeg
|Decoding and Encoding of JPEG Images
|-
|png
|Decoding and Encoding of PNG Images
|-
|ppm
|Encoding of portable pixmap Images
|-
|webp
|Decoding of Webp Images
|}

Traits<ref>http://rustbyexample.com/trait.html</ref>
{| class="wikitable"
|-
|GenericImage
|A trait for manipulating images.
|-
|ImageDecoder
|The trait that all decoders implement
|-
|MutableRefImage
|A trait for images that allow providing mutable references to pixels.
|-
|Pixel
|A trait that all pixels implement.
|}

Functions
{| class="wikitable"
|-
|load
|Create a new image from a Reader
|-
|load_from_memory
|Create a new image from a byte slice
|-
|open
|Open the image located at the path specified. The image's format is determined from the path's file extension
|}

== Design Principles ==

We are adhering to the following design principles for our implementation:

'''Open-Closed Principle'''<ref>http://en.wikipedia.org/wiki/Open/closed_principle</ref>

Although our task is to evaluate replacing C libraries with Rust libraries, we won't actually be modifying any existing functionality.

'''Interface Segregation Principle'''<ref>http://en.wikipedia.org/wiki/Interface_segregation_principle</ref>

The existing code is currently using the ''rust-freetype'' library for rendering fonts on the browser. We will be replacing this with the ''freetype-rs'' library, which divides the functionality offered by the former into smaller libraries which can be individually implemented instead of calling the entire library.

== Design Pattern==

We have implemented the Adapter Pattern in our Project:

When we updated the image library, the function load_from_memory() in base.rs had to be updated since the return from the updated function accepts a different set of parameters.
We implemented the Adapter pattern as a wrapper function over the new load_from_memory() function which performs the below functions:
1. Based on the file extension generate the ImageFormat Enum.
2. The return of the new function is a Result<DynamicImage>. This needs to be converted into a DynamicImage struct.
<pre>
pub fn load_from_memory(buffer: &[u8],ext: &str) -> Option<DynamicImage> {
if buffer.len() == 0 {
return None;
}
else {
//Retrieve the ImageFormat enum to be passed into the updated function
let image_type: Option< servo_image::ImageFormat > = get_format(ext);
if image_type == None
{
panic!("Image format not supported!");
}
else{
let new_image_type: servo_image::ImageFormat = image_type.unwrap();

//The updated function returns a Result<DynamicImage>
//below code resolves it to be returned by the wrapper function
let result = servo_image::load_from_memory(buffer,new_image_type);
if result.is_ok() {
let v = result.unwrap();
return Some(v);
}
else {
return None;
}
}
}
}

</pre>

==Flowchart describing Project Implementation==
[[File:Flowchart_final_M1455.JPG]]

== UML diagrams ==

===Class Diagram===
[[File:Class_diagram_M1455.JPG]]

== Proposed Test Cases ==

The project does not plan to add new functionality.
The test-cases we propose to run are will ensure that tasks that could be performed with the older C libraries can be executed.

The following test cases are proposed.

# Render different webpages with different fonts. Ensure the text renders correctly
# Render images of different formats (png, jpeg, bmp, gif) of different resolutions. Ensure that the images are rendered correctly.
# Record time taken to render and compare against time taken by the older libraries, for both image and text.

== References ==
<references/>

== See Also ==
[http://wiki.expertiza.ncsu.edu/index.php/CSC/ECE_517_Fall_2014/oss_M1455_asa Initial Step Details]

CSC/ECE 517 Fall 2014/final M1455 yaaa

2014-12-03T05:09:37Z

Aashetty: /* Design Pattern */

This wiki page contains design details for the project on [https://github.com/servo/servo/wiki/Replace-C-libraries-student-project Evaluate replacing C libraries with modern Rust equivalents] for the Mozilla research project [http://github.com/servo/servo/wiki/Design Servo].

== Background Information <ref>http://wiki.expertiza.ncsu.edu/index.php/CSC/ECE_517_Fall_2014/oss_M1455_asa</ref> ==

===Rust===
[http://www.rust-lang.org/ Rust] is a new programming language for developing reliable and efficient systems. It is designed to support concurrency and parallelism in building platforms that take full advantage of modern hardware. Its static type system is safe and expressive and it provides strong guarantees about isolation, concurrency execution and memory safety.
Rust combines powerful and flexible modern programming constructs with a clear performance model to make program efficiency predictable and manageable. One important way it achieves this is by allowing fine-grained control over memory allocation through contiguous records and stack allocation. This control is balanced with the absolute requirement of safety: Rust’s type system and runtime guarantee the absence of data races, buffer overflow, stack overflow or access to uninitialized or deallocated memory.

===Servo===
[http://en.wikipedia.org/wiki/Servo_%28layout_engine%29 Servo] is an experimental project to build a Web browser engine for a new generation of hardware: mobile devices, multi-core processors and high-performance GPUs.
Servo builds on top of Rust to provide a secure and reliable foundation. Rust’s lightweight task mechanism promises to allow fine-grained isolation between browser components, such as tabs and extensions, without the need for expensive runtime protection schemes, like operating system process isolation. Servo is not designed to create a full browser but is rather focused on creating a reliable and fast browser engine.

== Introduction ==
Servo currently depends on a lot of C libraries for image decoding. We wish to evaluate switching some of these to new Rust libraries. This project involves rewriting the code that uses these libraries as well as taking measurements before and after to determine the costs involved.

====Setup of Development Environment====
Servo is currently developed on 64bit OS X and 64bit Linux.

The steps needed to build on a Debian based 64 bit Linux machine are included below. The instructions for other platforms are available [https://github.com/servo/servo#prerequisites here].

* Install the prerequisite dependencies
<pre>
sudo apt-get install curl freeglut3-dev \
libfreetype6-dev libgl1-mesa-dri libglib2.0-dev xorg-dev \
msttcorefonts gperf g++ cmake python-virtualenv \
libssl-dev libglfw-dev
</pre>

* Clone and build servo repository
<pre>
git clone https://www.github.com/servo/servo
cd servo
./mach build
./mach run tests/html/about-mozilla.html
</pre>

== Architecture of system <ref>https://github.com/servo/servo/wiki/Design#task-supervision-diagram</ref> ==

=== Task Supervision Diagram ===

[[File:TaskSupervision.png]]

=== Task Communication Diagram ===

[[File:TaskCommunication.png]]

The above diagrams gives us an overview of the Servo's architecture.
*Each box represents a Rust task.
*Primary tasks are the ones which are represented by blue boxes.
*Gray boxes are for auxiliary tasks.
*White boxes are for worker tasks. Each such box represents several tasks, the precise number of which are decided by the workload.
*Supervisor relationships are shown by dashed lines.
*Communication channels are shown by solid lines.

The scope of our project is limited to changing the libraries used in the image decoding task shown above.

== Requirement analysis ==

Servo currently depends on a lot of C libraries, because Rust equivalents for these libraries did not exist when the project started. Our project is to evaluate switching some of these to new Rust libraries that have since been created. It involves rewriting the code that uses these libraries as well as taking measurements before and after to determine the costs involved.<ref>https://github.com/servo/servo/wiki/Replace-C-libraries-student-project</ref>

Initial step

Our [http://wiki.expertiza.ncsu.edu/index.php/CSC/ECE_517_Fall_2014/oss_M1455_asa initial step], implemented for the OSS project involved:
# Building Servo.
# Adding [http://doc.servo.org/util/time/fn.time.html timing code] to the image decoding implementation in the net crate.
# Rebuilding Servo.
# Reporting numbers for different kinds of images (i.e. PNG, JPEG, GIF).

Final Requirements

Our final project requirements are to:
* Build Servo and add code that reports (via the println! macro) the time required to decode images into displayable pixels.
* Add image decoding timing to the profiler.
* Import the [https://github.com/PistonDevelopers/freetype-rs freetype-rs] library to replace [https://github.com/servo/rust-freetype rust-freetype] in Servo, rewriting necessary code.<ref>https://github.com/servo/servo/issues/3369</ref> For this, we are to use [http://doc.crates.io/ Cargo], the dependency manager for Servo.
* Import the [https://github.com/PistonDevelopers/image rust-image] library to replace the [https://github.com/servo/rust-stb-image rust-stb-image] and [https://github.com/nothings/stb stb-image] libraries and rewrite the <code>load_from_memory</code> function which uses these libraries.<ref>https://github.com/servo/servo/issues/3368</ref>
* Report the timing differences for loading PNGs and non-PNGs on the same benchmarks. For this step, we are to consider profiling the result and optimizing the hotspots in rust-image.

== Data and component design <ref>http://www.rust-ci.org/PistonDevelopers/piston/doc/image/index.html</ref>==

===Data Design===
The system entities that the project deals with is present in the image crate.

The structs and enums used to represent images are as below :

Structures
{| class = "wikitable"
|-
|ImageBuf
|An Image whose pixels are contained within a vector
|-
|Luma
|A type to hold a grayscale pixel
|-
|LumaA
|A type to hold a grayscale pixel with an alpha channel
|-
|MutPixels
|Mutable pixel iterator
|-
|Pixels
|Immutable pixel iterator
|-
|Rgb
|A type to hold an RGB pixel
|-
|Rgba
|A type to hold an RGB pixel with an alpha channel
|-
|SubImage
|A View into another image
|}

Enums
{| class="wikitable"
|-
|ColorType
|An enumeration over supported color types and their bit depths
|-
|DynamicImage
|A Dynamic Image
|-
|FilterType
|Available Sampling Filters
|-
|ImageError
|An enumeration of Image Errors
|-
|ImageFormat
|An enumeration of supported image formats. Not all formats support both encoding and decoding.
|}

===Component Design===

Rust image : It is an image processing library. This crate provides basic imaging processing functions and methods for converting to and from image formats.
All image processing functions provided operate on types that implement the GenericImage trait and return an ImageBuf. The details of other modules and traits included are :

Modules<ref>http://doc.rust-lang.org/guide.html#crates-and-modules</ref>
{| class="wikitable"
|-
|gif
|Decoding of GIF Images
|-
|imageops
|Image Processing Functions
|-
|jpeg
|Decoding and Encoding of JPEG Images
|-
|png
|Decoding and Encoding of PNG Images
|-
|ppm
|Encoding of portable pixmap Images
|-
|webp
|Decoding of Webp Images
|}

Traits<ref>http://rustbyexample.com/trait.html</ref>
{| class="wikitable"
|-
|GenericImage
|A trait for manipulating images.
|-
|ImageDecoder
|The trait that all decoders implement
|-
|MutableRefImage
|A trait for images that allow providing mutable references to pixels.
|-
|Pixel
|A trait that all pixels implement.
|}

Functions
{| class="wikitable"
|-
|load
|Create a new image from a Reader
|-
|load_from_memory
|Create a new image from a byte slice
|-
|open
|Open the image located at the path specified. The image's format is determined from the path's file extension
|}

== Design Principles ==

We are adhering to the following design principles for our implementation:

'''Open-Closed Principle'''<ref>http://en.wikipedia.org/wiki/Open/closed_principle</ref>

Although our task is to evaluate replacing C libraries with Rust libraries, we won't actually be modifying any existing functionality.

'''Interface Segregation Principle'''<ref>http://en.wikipedia.org/wiki/Interface_segregation_principle</ref>

The existing code is currently using the ''rust-freetype'' library for rendering fonts on the browser. We will be replacing this with the ''freetype-rs'' library, which divides the functionality offered by the former into smaller libraries which can be individually implemented instead of calling the entire library.

== Design Pattern==

We have implemented the Adapter Pattern in our Project:

When we updated the image library, the function load_from_memory() in base.rs had to be updated since the return from the updated function accepts a different set of parameters.
We implemented the Adapter pattern as a wrapper function over the new load_from_memory() function which performs the below functions:
1. Based on the file extension generate the ImageFormat Enum.
2. The return of the new function is a Result<DynamicImage>. This needs to be converted into a DynamicImage struct.
<pre>
pub fn load_from_memory(buffer: &[u8],ext: &str) -> Option<DynamicImage> {
if buffer.len() == 0 {
return None;
}
else {
//Retrieve the ImageFormat enum to be passed into the updated function
let image_type: Option< servo_image::ImageFormat > = get_format(ext);
if image_type == None
{
panic!("Image format not supported!");
}
else{
let new_image_type: servo_image::ImageFormat = image_type.unwrap();

//The updated function returns a Result<DynamicImage>
//below code resolves it to be returned by the wrapper function
let result = servo_image::load_from_memory(buffer,new_image_type);
if result.is_ok() {
let v = result.unwrap();
return Some(v);
}
else {
return None;
}
}
}
}

</pre>

==Flowchart describing Project Implementation==
[[File:Flowchart_final_M1455.JPG]]

== UML diagrams ==

===Class Diagram===
[[File:Class_diagram_M1455.JPG]]

== Proposed Test Cases ==

The project does not plan to add new functionality.
The test-cases we propose to run are will ensure that tasks that could be performed with the older C libraries can be executed.

The following test cases are proposed.

# Render different webpages with different fonts. Ensure the text renders correctly
# Render images of different formats (png, jpeg, bmp, gif) of different resolutions. Ensure that the images are rendered correctly.
# Record time taken to render and compare against time taken by the older libraries, for both image and text.

== References ==
<references/>

== See Also ==
[http://wiki.expertiza.ncsu.edu/index.php/CSC/ECE_517_Fall_2014/oss_M1455_asa Initial Step Details]

CSC/ECE 517 Fall 2014/final M1455 yaaa

2014-12-03T04:58:52Z

Aashetty: /* Design Principles */

This wiki page contains design details for the project on [https://github.com/servo/servo/wiki/Replace-C-libraries-student-project Evaluate replacing C libraries with modern Rust equivalents] for the Mozilla research project [http://github.com/servo/servo/wiki/Design Servo].

== Background Information <ref>http://wiki.expertiza.ncsu.edu/index.php/CSC/ECE_517_Fall_2014/oss_M1455_asa</ref> ==

===Rust===
[http://www.rust-lang.org/ Rust] is a new programming language for developing reliable and efficient systems. It is designed to support concurrency and parallelism in building platforms that take full advantage of modern hardware. Its static type system is safe and expressive and it provides strong guarantees about isolation, concurrency execution and memory safety.
Rust combines powerful and flexible modern programming constructs with a clear performance model to make program efficiency predictable and manageable. One important way it achieves this is by allowing fine-grained control over memory allocation through contiguous records and stack allocation. This control is balanced with the absolute requirement of safety: Rust’s type system and runtime guarantee the absence of data races, buffer overflow, stack overflow or access to uninitialized or deallocated memory.

===Servo===
[http://en.wikipedia.org/wiki/Servo_%28layout_engine%29 Servo] is an experimental project to build a Web browser engine for a new generation of hardware: mobile devices, multi-core processors and high-performance GPUs.
Servo builds on top of Rust to provide a secure and reliable foundation. Rust’s lightweight task mechanism promises to allow fine-grained isolation between browser components, such as tabs and extensions, without the need for expensive runtime protection schemes, like operating system process isolation. Servo is not designed to create a full browser but is rather focused on creating a reliable and fast browser engine.

== Introduction ==
Servo currently depends on a lot of C libraries for image decoding. We wish to evaluate switching some of these to new Rust libraries. This project involves rewriting the code that uses these libraries as well as taking measurements before and after to determine the costs involved.

====Setup of Development Environment====
Servo is currently developed on 64bit OS X and 64bit Linux.

The steps needed to build on a Debian based 64 bit Linux machine are included below. The instructions for other platforms are available [https://github.com/servo/servo#prerequisites here].

* Install the prerequisite dependencies
<pre>
sudo apt-get install curl freeglut3-dev \
libfreetype6-dev libgl1-mesa-dri libglib2.0-dev xorg-dev \
msttcorefonts gperf g++ cmake python-virtualenv \
libssl-dev libglfw-dev
</pre>

* Clone and build servo repository
<pre>
git clone https://www.github.com/servo/servo
cd servo
./mach build
./mach run tests/html/about-mozilla.html
</pre>

== Architecture of system <ref>https://github.com/servo/servo/wiki/Design#task-supervision-diagram</ref> ==

=== Task Supervision Diagram ===

[[File:TaskSupervision.png]]

=== Task Communication Diagram ===

[[File:TaskCommunication.png]]

The above diagrams gives us an overview of the Servo's architecture.
*Each box represents a Rust task.
*Primary tasks are the ones which are represented by blue boxes.
*Gray boxes are for auxiliary tasks.
*White boxes are for worker tasks. Each such box represents several tasks, the precise number of which are decided by the workload.
*Supervisor relationships are shown by dashed lines.
*Communication channels are shown by solid lines.

The scope of our project is limited to changing the libraries used in the image decoding task shown above.

== Requirement analysis ==

Servo currently depends on a lot of C libraries, because Rust equivalents for these libraries did not exist when the project started. Our project is to evaluate switching some of these to new Rust libraries that have since been created. It involves rewriting the code that uses these libraries as well as taking measurements before and after to determine the costs involved.<ref>https://github.com/servo/servo/wiki/Replace-C-libraries-student-project</ref>

Initial step

Our [http://wiki.expertiza.ncsu.edu/index.php/CSC/ECE_517_Fall_2014/oss_M1455_asa initial step], implemented for the OSS project involved:
# Building Servo.
# Adding [http://doc.servo.org/util/time/fn.time.html timing code] to the image decoding implementation in the net crate.
# Rebuilding Servo.
# Reporting numbers for different kinds of images (i.e. PNG, JPEG, GIF).

Final Requirements

Our final project requirements are to:
* Build Servo and add code that reports (via the println! macro) the time required to decode images into displayable pixels.
* Add image decoding timing to the profiler.
* Import the [https://github.com/PistonDevelopers/freetype-rs freetype-rs] library to replace [https://github.com/servo/rust-freetype rust-freetype] in Servo, rewriting necessary code.<ref>https://github.com/servo/servo/issues/3369</ref> For this, we are to use [http://doc.crates.io/ Cargo], the dependency manager for Servo.
* Import the [https://github.com/PistonDevelopers/image rust-image] library to replace the [https://github.com/servo/rust-stb-image rust-stb-image] and [https://github.com/nothings/stb stb-image] libraries and rewrite the <code>load_from_memory</code> function which uses these libraries.<ref>https://github.com/servo/servo/issues/3368</ref>
* Report the timing differences for loading PNGs and non-PNGs on the same benchmarks. For this step, we are to consider profiling the result and optimizing the hotspots in rust-image.

== Data and component design <ref>http://www.rust-ci.org/PistonDevelopers/piston/doc/image/index.html</ref>==

===Data Design===
The system entities that the project deals with is present in the image crate.

The structs and enums used to represent images are as below :

Structures
{| class = "wikitable"
|-
|ImageBuf
|An Image whose pixels are contained within a vector
|-
|Luma
|A type to hold a grayscale pixel
|-
|LumaA
|A type to hold a grayscale pixel with an alpha channel
|-
|MutPixels
|Mutable pixel iterator
|-
|Pixels
|Immutable pixel iterator
|-
|Rgb
|A type to hold an RGB pixel
|-
|Rgba
|A type to hold an RGB pixel with an alpha channel
|-
|SubImage
|A View into another image
|}

Enums
{| class="wikitable"
|-
|ColorType
|An enumeration over supported color types and their bit depths
|-
|DynamicImage
|A Dynamic Image
|-
|FilterType
|Available Sampling Filters
|-
|ImageError
|An enumeration of Image Errors
|-
|ImageFormat
|An enumeration of supported image formats. Not all formats support both encoding and decoding.
|}

===Component Design===

Rust image : It is an image processing library. This crate provides basic imaging processing functions and methods for converting to and from image formats.
All image processing functions provided operate on types that implement the GenericImage trait and return an ImageBuf. The details of other modules and traits included are :

Modules<ref>http://doc.rust-lang.org/guide.html#crates-and-modules</ref>
{| class="wikitable"
|-
|gif
|Decoding of GIF Images
|-
|imageops
|Image Processing Functions
|-
|jpeg
|Decoding and Encoding of JPEG Images
|-
|png
|Decoding and Encoding of PNG Images
|-
|ppm
|Encoding of portable pixmap Images
|-
|webp
|Decoding of Webp Images
|}

Traits<ref>http://rustbyexample.com/trait.html</ref>
{| class="wikitable"
|-
|GenericImage
|A trait for manipulating images.
|-
|ImageDecoder
|The trait that all decoders implement
|-
|MutableRefImage
|A trait for images that allow providing mutable references to pixels.
|-
|Pixel
|A trait that all pixels implement.
|}

Functions
{| class="wikitable"
|-
|load
|Create a new image from a Reader
|-
|load_from_memory
|Create a new image from a byte slice
|-
|open
|Open the image located at the path specified. The image's format is determined from the path's file extension
|}

== Design Principles ==

We are adhering to the following design principles for our implementation:

'''Open-Closed Principle'''<ref>http://en.wikipedia.org/wiki/Open/closed_principle</ref>

Although our task is to evaluate replacing C libraries with Rust libraries, we won't actually be modifying any existing functionality.

'''Interface Segregation Principle'''<ref>http://en.wikipedia.org/wiki/Interface_segregation_principle</ref>

The existing code is currently using the ''rust-freetype'' library for rendering fonts on the browser. We will be replacing this with the ''freetype-rs'' library, which divides the functionality offered by the former into smaller libraries which can be individually implemented instead of calling the entire library.

== Design Pattern==

We have implemented the Adapter Pattern in our Project:

When we updated the image library, the function load_from_memory() in base.rs had to be updated since the return from the updated function accepts a different set of parameters.
We implemented the Adapter pattern as a wrapper function over the new load_from_memory() function which performs the below functions:
1. Based on the file extension generate the ImageFormat Enum.
2. The return of the new function is a Result<DynamicImage>. This needs to be converted into a DynamicImage struct.
<pre>
pub fn load_from_memory(buffer: &[u8],ext: &str) -> Option<DynamicImage> {
if buffer.len() == 0 {
return None;
}
else {
//let new_image_type: servo_image::ImageFormat = servo_image::ImageFormat::PNG;

let image_type: Option< servo_image::ImageFormat > = get_format(ext);
if image_type == None
{
panic!("Image format not supported!");
}
else{
let new_image_type: servo_image::ImageFormat = image_type.unwrap();

let result = servo_image::load_from_memory(buffer,new_image_type);
if result.is_ok() {
let v = result.unwrap();
return Some(v);
}
else {
return None;
}
}
}
}

</pre>

==Flowchart describing Project Implementation==
[[File:Flowchart_final_M1455.JPG]]

== UML diagrams ==

===Class Diagram===
[[File:Class_diagram_M1455.JPG]]

== Proposed Test Cases ==

The project does not plan to add new functionality.
The test-cases we propose to run are will ensure that tasks that could be performed with the older C libraries can be executed.

The following test cases are proposed.

# Render different webpages with different fonts. Ensure the text renders correctly
# Render images of different formats (png, jpeg, bmp, gif) of different resolutions. Ensure that the images are rendered correctly.
# Record time taken to render and compare against time taken by the older libraries, for both image and text.

== References ==
<references/>

== See Also ==
[http://wiki.expertiza.ncsu.edu/index.php/CSC/ECE_517_Fall_2014/oss_M1455_asa Initial Step Details]

CSC/ECE 517 Fall 2014/final M1455 yaaa

2014-11-11T23:40:41Z

Aashetty: /* Component Design */

CSC/ECE 517 Fall 2014/final M1455 yaaa

2014-11-11T23:39:26Z

Aashetty: /* Component Design */

CSC/ECE 517 Fall 2014/final M1455 yaaa

2014-11-11T23:37:13Z

Aashetty: /* Data and component design */

CSC/ECE 517 Fall 2014/final M1455 yaaa

2014-11-11T23:08:25Z

Aashetty: /* UML diagrams */

CSC/ECE 517 Fall 2014/oss M1455 asa

2014-10-29T02:29:45Z

Aashetty: /* References */

== EVALUATE REPLACING C IMAGE & FONT LIBRARIES WITH RUST EQUIVALENTS ==
In this wiki we represent the steps followed in order to implement the taskes assigned under the the above OSS Mozilla Project.
It required us to make changes to the Servo code base.

== Introduction to Rust==
Rust is a new programming language for developing reliable and efficient systems. It's designed to support concurrency and parallelism in building platforms that take full advantage of modern hardware. Its static type system is safe and expressive and it provides strong guarantees about isolation, concurrency execution and memory safety.

Rust combines powerful and flexible modern programming constructs with a clear performance model to make program efficiency predictable and manageable. One important way it achieves this is by allowing fine-grained control over memory allocation through contiguous records and stack allocation. This control is balanced with the absolute requirement of safety: Rust’s type system and runtime guarantee the absence of data races, buffer overflow, stack overflow or access to uninitialized or deallocated memory.

== Introduction to Servo==
Servo is an experimental project to build a Web browser engine for a new generation of hardware: mobile devices, multi-core processors and high-performance GPUs. With Servo, we are rethinking the browser at every level of the technology stack — from input parsing to page layout to graphics rendering — to optimize for power efficiency and maximum parallelism.

Servo builds on top of Rust to provide a secure and reliable foundation. Memory safety at the core of the platform ensures a high degree of assurance in the browser’s trusted computing base. Rust’s lightweight task mechanism also promises to allow fine-grained isolation between browser components, such as tabs and extensions, without the need for expensive runtime protection schemes, like operating system process isolation.

== Aim ==
The aim of our project is display the time required by the decode function to decode images of different formats, e.g, jpeg, bmp, png, gif.

== Steps of Implementation ==
We implemented the following steps on our linux machine: 

'''• Build Servo''' 
1. We first need to clone the servo repository from git using the following command: 
<pre>
git clone https://www.github.com/servo/servo 
</pre>
 
[[File:Screen1M1455.png]]

 
Now we have a local copy of the servo codebase.
 
 

2. We build the servo using 
./mach build 
[[File:Shraddha1455.png]]

 

Building servo basically compiling the code along withthe dependent libraries. 
3. Once our servo is built, we have to run a test in order to ensure the build was successful. This is done using the below command 
./mach run url 

[[File:M1455_3.png]] 
[[File:M1455_4.png]]

The above output shows that the html page was successfully launched by the servo browser. Thus proving that the build was successful.
 
 
'''• Add timing code''' 
Once the initial step is completed, our next task was to add timing code around the code block which performed decoding of images.
The decoding of images is performed in the https://github.com/servo/servo/blob/master/components/net/image_cache_task.rs rust file.

1. In image_cache_task.rs , we have a fn decode which calls the load_from_memory fn in base.rs. 
2. Image decoding is implemented in this load_from_memory function. 
3. So we added the timing code arround this function call in imacge_cache_task.rs 
4. precise_time_ns() gives us the current time. 
5. So we added it before the call to get the start time of decoding and after the call to get the end time. 
6. Difference of the two gave us the decoding time, which can be printed on command line. 
<pre>let start_time=precise_time_ns();
let image = load_from_memory(data.as_slice());
let end_time=precise_time_ns();.
let required_time=(end_time-start_time) as f64/1000000f64;</pre>

'''• Rebuild Servo''' 
Once we made the above changes, we now need to rebuild the servo code base. For this we again follow the same steps as described in the build servo section.

== Run Tests ==
We tested images with different file formats and resolution using ./mach run image_url. 
[[File:M1455_5.png]] 
You can see the decoding time values reported for the different images on the command line.
 
Further the tabulated results are reported below:
 

== References ==
https://www.mozilla.org/en-US/research/projects/

== Further Reading==
https://people.mozilla.org/~roc/Samsung/MozillaRustAndServo.pdf

CSC/ECE 517 Fall 2014/oss M1455 asa

2014-10-29T02:28:43Z

Aashetty: /* Run Tests */

CSC/ECE 517 Fall 2014/oss M1455 asa

2014-10-29T02:28:12Z

Aashetty: /* Introduction */

CSC/ECE 517 Fall 2014/oss M1455 asa

2014-10-29T02:20:30Z

Aashetty: /* Steps of Implementation */

== EVALUATE REPLACING C IMAGE & FONT LIBRARIES WITH RUST EQUIVALENTS ==
In this wiki we represent the steps followed in order to implement the taskes assigned under the the above OSS Mozilla Project.
It required us to make changes to the Servo code base.

== Introduction ==
Servo is an experimental web browser layout engine being developed by Mozilla Research for new generation hardware.
The project has a symbiotic relationship with the Rust programming language, in which it is being developed. Rust is a new programming language for developing reliable and efficient systems.

Servo currently depends on a lot of C libraries, because Rust equivalents did not exist when the project started.
We want to evaluate switching some of these to new Rust libraries that have been created.
This project involves rewriting the code that uses these libraries as well as taking measurements before and after to determine the costs involved.

== Aim ==
The aim of our project is display the time required by the decode function to decode images of different formats, e.g, jpeg, bmp, png, gif.

== Steps of Implementation ==
We implemented the following steps on our linux machine: 

'''• Build Servo''' 
1. We first need to clone the servo repository from git using the following command: 
<pre>
git clone https://www.github.com/servo/servo 
</pre>
 
[[File:Screen1M1455.png]]

 
Now we have a local copy of the servo codebase.
 
 

2. We build the servo using 
./mach build 
[[File:bs14.png]]

 

Building servo basically compiling the code along withthe dependent libraries. 
3. Once our servo is built, we have to run a test in order to ensure the build was successful. This is done using the below command 
./mach run url 

[[File:M1455_3.png]] 
[[File:M1455_4.png]]

The above output shows that the html page was successfully launched by the servo browser. Thus proving that the build was successful.
 
 
'''• Add timing code''' 
Once the initial step is completed, our next task was to add timing code around the code block which performed decoding of images.
The decoding of images is performed in the https://github.com/servo/servo/blob/master/components/net/image_cache_task.rs rust file.

1. In image_cache_task.rs , we have a fn decode which calls the load_from_memory fn in base.rs. 
2. Image decoding is implemented in this load_from_memory function. 
3. So we added the timing code arround this function call in imacge_cache_task.rs 
4. precise_time_ns() gives us the current time. 
5. So we added it before the call to get the start time of decoding and after the call to get the end time. 
6. Difference of the two gave us the decoding time, which can be printed on command line. 
<pre>let start_time=precise_time_ns();
let image = load_from_memory(data.as_slice());
let end_time=precise_time_ns();.
let required_time=(end_time-start_time) as f64/1000000f64;</pre>

'''• Rebuild Servo''' 
Once we made the above changes, we now need to rebuild the servo code base. For this we again follow the same steps as described in the build servo section.

== Run Tests ==
We tested images with different file formats and resolution using ./mach run image_url. 
[[File:M1455_5.png]] 
You can see the decoding time values reported for the different images on the command line.
 
Further the tabulated results are reported below:

CSC/ECE 517 Fall 2014/oss M1455 asa

2014-10-29T02:18:35Z

Aashetty: /* Run Tests */

== EVALUATE REPLACING C IMAGE & FONT LIBRARIES WITH RUST EQUIVALENTS ==
In this wiki we represent the steps followed in order to implement the taskes assigned under the the above OSS Mozilla Project.
It required us to make changes to the Servo code base.

== Introduction ==
Servo is an experimental web browser layout engine being developed by Mozilla Research for new generation hardware.
The project has a symbiotic relationship with the Rust programming language, in which it is being developed. Rust is a new programming language for developing reliable and efficient systems.

Servo currently depends on a lot of C libraries, because Rust equivalents did not exist when the project started.
We want to evaluate switching some of these to new Rust libraries that have been created.
This project involves rewriting the code that uses these libraries as well as taking measurements before and after to determine the costs involved.

== Aim ==
The aim of our project is display the time required by the decode function to decode images of different formats, e.g, jpeg, bmp, png, gif.

== Steps of Implementation ==
We implemented the following steps on our linux machine: 

'''• Build Servo''' 
1. We first need to clone the servo repository from git using the following command: 
<pre>
git clone https://www.github.com/servo/servo 
</pre>
 
[[File:Screen1M1455.png]]

 
Now we have a local copy of the servo codebase.
 
 

2. We build the servo using 
./mach build 
[[File:buildservo1455.png]]

 

Building servo basically compiling the code along withthe dependent libraries. 
3. Once our servo is built, we have to run a test in order to ensure the build was successful. This is done using the below command 
./mach run url 

[[File:M1455_3.png]] 
[[File:M1455_4.png]]

The above output shows that the html page was successfully launched by the servo browser. Thus proving that the build was successful.
 
 
'''• Add timing code''' 
Once the initial step is completed, our next task was to add timing code around the code block which performed decoding of images.
The decoding of images is performed in the https://github.com/servo/servo/blob/master/components/net/image_cache_task.rs rust file.

1. In image_cache_task.rs , we have a fn decode which calls the load_from_memory fn in base.rs. 
2. Image decoding is implemented in this load_from_memory function. 
3. So we added the timing code arround this function call in imacge_cache_task.rs 
4. precise_time_ns() gives us the current time. 
5. So we added it before the call to get the start time of decoding and after the call to get the end time. 
6. Difference of the two gave us the decoding time, which can be printed on command line. 
<pre>let start_time=precise_time_ns();
let image = load_from_memory(data.as_slice());
let end_time=precise_time_ns();
let required_time=(end_time-start_time) as f64/1000000f64;</pre>

'''• Rebuild Servo''' 

== Run Tests ==
We tested images with different file formats and resolution using ./mach run image_url. 
[[File:M1455_5.png]] 
You can see the decoding time values reported for the different images on the command line.
 
Further the tabulated results are reported below:

CSC/ECE 517 Fall 2014/oss M1455 asa

2014-10-29T02:17:55Z

Aashetty: /* Run Tests */

== EVALUATE REPLACING C IMAGE & FONT LIBRARIES WITH RUST EQUIVALENTS ==
In this wiki we represent the steps followed in order to implement the taskes assigned under the the above OSS Mozilla Project.
It required us to make changes to the Servo code base.

== Introduction ==
Servo is an experimental web browser layout engine being developed by Mozilla Research for new generation hardware.
The project has a symbiotic relationship with the Rust programming language, in which it is being developed. Rust is a new programming language for developing reliable and efficient systems.

Servo currently depends on a lot of C libraries, because Rust equivalents did not exist when the project started.
We want to evaluate switching some of these to new Rust libraries that have been created.
This project involves rewriting the code that uses these libraries as well as taking measurements before and after to determine the costs involved.

== Aim ==
The aim of our project is display the time required by the decode function to decode images of different formats, e.g, jpeg, bmp, png, gif.

== Steps of Implementation ==
We implemented the following steps on our linux machine: 

'''• Build Servo''' 
1. We first need to clone the servo repository from git using the following command: 
<pre>
git clone https://www.github.com/servo/servo 
</pre>
 
[[File:Screen1M1455.png]]

 
Now we have a local copy of the servo codebase.
 
 

2. We build the servo using 
./mach build 
[[File:buildservoM1455.png]]

 

Building servo basically compiling the code along withthe dependent libraries. 
3. Once our servo is built, we have to run a test in order to ensure the build was successful. This is done using the below command 
./mach run url 

[[File:M1455_3.png]] 
[[File:M1455_4.png]]

The above output shows that the html page was successfully launched by the servo browser. Thus proving that the build was successful.
 
 
'''• Add timing code''' 
Once the initial step is completed, our next task was to add timing code around the code block which performed decoding of images.
The decoding of images is performed in the https://github.com/servo/servo/blob/master/components/net/image_cache_task.rs rust file.

1. In image_cache_task.rs , we have a fn decode which calls the load_from_memory fn in base.rs. 
2. Image decoding is implemented in this load_from_memory function. 
3. So we added the timing code arround this function call in imacge_cache_task.rs 
4. precise_time_ns() gives us the current time. 
5. So we added it before the call to get the start time of decoding and after the call to get the end time. 
6. Difference of the two gave us the decoding time, which can be printed on command line. 
<pre>let start_time=precise_time_ns();
let image = load_from_memory(data.as_slice());
let end_time=precise_time_ns();
let required_time=(end_time-start_time) as f64/1000000f64;</pre>

'''• Rebuild Servo''' 

== Run Tests ==
We tested images with different file formats and resolution using ./mach run image_url. 
[[File:M1455_5.png]] 
You can see the decoding time values reported for the different images on the command line.
These are the results we got:

CSC/ECE 517 Fall 2014/oss M1455 asa

2014-10-29T02:15:21Z

Aashetty: /* Steps of Implementation */

CSC/ECE 517 Fall 2014/oss M1455 asa

2014-10-29T02:14:50Z

Aashetty: /* Steps of Implementation */

CSC/ECE 517 Fall 2014/oss M1455 asa

2014-10-29T02:05:39Z

Aashetty: /* Steps of Implementation */

CSC/ECE 517 Fall 2014/oss M1455 asa

2014-10-29T02:04:52Z

Aashetty: /* Steps of Implementation */

CSC/ECE 517 Fall 2014/oss M1455 asa

2014-10-29T01:51:11Z

Aashetty: /* Steps of Implementation */

CSC/ECE 517 Fall 2014/oss M1455 asa

2014-10-29T01:27:51Z

Aashetty: /* Steps of Implementation */

CSC/ECE 517 Fall 2014/oss M1455 asa

2014-10-29T01:27:30Z

Aashetty: /* Steps of Implementation */

CSC/ECE 517 Fall 2014/oss M1455 asa

2014-10-29T01:27:00Z

Aashetty: /* Steps of Implementation */

CSC/ECE 517 Fall 2014/oss M1455 asa

2014-10-29T01:26:21Z

Aashetty: /* Steps of Implementation */

CSC/ECE 517 Fall 2014/oss M1455 asa

2014-10-29T01:25:31Z

Aashetty: /* Steps of Implementation */

CSC/ECE 517 Fall 2014/oss M1455 asa

2014-10-29T01:18:39Z

Aashetty: /* Steps of Implementation */

CSC/ECE 517 Fall 2014/oss M1455 asa

2014-10-29T01:17:02Z

Aashetty: /* Steps of Implementation */

File:Build servo.png

2014-10-29T01:16:28Z

Aashetty: uploaded a new version of "File:Build servo.png"

CSC/ECE 517 Fall 2014/oss M1455 asa

2014-10-29T01:06:36Z

Aashetty: /* EVALUATE REPLACING C IMAGE & FONT LIBRARIES WITH RUST EQUIVALENTS */

CSC/ECE 517 Fall 2014/oss M1455 asa

2014-10-29T01:05:24Z

Aashetty: /* EVALUATE REPLACING C IMAGE & FONT LIBRARIES WITH RUST EQUIVALENTS */

== EVALUATE REPLACING C IMAGE & FONT LIBRARIES WITH RUST EQUIVALENTS ==
In this wiki we represent the steps followed in order to implement the taskes assigned under the the above OSS Mozilla Project.

== Introduction ==
Servo is an experimental web browser layout engine being developed by Mozilla Research for new generation hardware.
The project has a symbiotic relationship with the Rust programming language, in which it is being developed. Rust is a new programming language for developing reliable and efficient systems.

Servo currently depends on a lot of C libraries, because Rust equivalents did not exist when the project started.
We want to evaluate switching some of these to new Rust libraries that have been created.
This project involves rewriting the code that uses these libraries as well as taking measurements before and after to determine the costs involved.

== Aim ==
The aim of our project is display the time required by the decode function to decode images of different formats, e.g, jpeg, bmp, png, gif.

== Steps of Implementation ==
We implemented the following steps on our linux machine: 

'''• Build Servo''' 
1. We first need to clone the servo repository using the following command: 
git clone https://www.github.com/servo/servo 
[[File:Git clone.png]] 
Now we have a local copy of the servo codebase.
 
 

2. We build the servo using 
./mach build 

[[File:build_servo.png]] 
 

3. Once our servo is built, we can run it using a test url 
./mach run url 

[[File:test_command.png]] 
[[File:test_op.png]] 
 
'''• Add timing code''' 
1. In image_cache_task.rs , we have a fn decode which calls the load_from_memory fn in base.rs. 
2. Image decoding is implemented in this load_from_memory function. 
3. So we added the timing code arround this function call in imacge_cache_task.rs 
4. precise_time_ns() gives us the current time. 
5. So we added it before the call to get the start time of decoding and after the call to get the end time. 
6. Difference of the two gave us the decoding time, which can be printed on command line. 
<pre>let start_time=precise_time_ns();
let image = load_from_memory(data.as_slice());
let end_time=precise_time_ns();
let required_time=(end_time-start_time) as f64/1000000f64;</pre>
 
 
'''• Rebuild Servo''' 

== Run Tests == 
We tested images with different file formats and resolution using ./mach run image_url. 
[[File:code_op.png]] 
These are the results we got:

CSC/ECE 517 Fall 2014/oss M1455 asa

2014-10-29T01:03:12Z

Aashetty:

== EVALUATE REPLACING C IMAGE & FONT LIBRARIES WITH RUST EQUIVALENTS ==
In this wiki we represent the steps involved in our OSS Mozilla Project using Rust Programming Language.

== Introduction ==
Servo is an experimental web browser layout engine being developed by Mozilla Research for new generation hardware.
The project has a symbiotic relationship with the Rust programming language, in which it is being developed. Rust is a new programming language for developing reliable and efficient systems.

Servo currently depends on a lot of C libraries, because Rust equivalents did not exist when the project started.
We want to evaluate switching some of these to new Rust libraries that have been created.
This project involves rewriting the code that uses these libraries as well as taking measurements before and after to determine the costs involved.

== Aim ==
The aim of our project is display the time required by the decode function to decode images of different formats, e.g, jpeg, bmp, png, gif.

== Steps of Implementation ==
We implemented the following steps on our linux machine: 

'''• Build Servo''' 
1. We first need to clone the servo repository using the following command: 
git clone https://www.github.com/servo/servo 
[[File:Git clone.png]] 
Now we have a local copy of the servo codebase.
 
 

2. We build the servo using 
./mach build 

[[File:build_servo.png]] 
 

3. Once our servo is built, we can run it using a test url 
./mach run url 

[[File:test_command.png]] 
[[File:test_op.png]] 
 
'''• Add timing code''' 
1. In image_cache_task.rs , we have a fn decode which calls the load_from_memory fn in base.rs. 
2. Image decoding is implemented in this load_from_memory function. 
3. So we added the timing code arround this function call in imacge_cache_task.rs 
4. precise_time_ns() gives us the current time. 
5. So we added it before the call to get the start time of decoding and after the call to get the end time. 
6. Difference of the two gave us the decoding time, which can be printed on command line. 
<pre>let start_time=precise_time_ns();
let image = load_from_memory(data.as_slice());
let end_time=precise_time_ns();
let required_time=(end_time-start_time) as f64/1000000f64;</pre>
 
 
'''• Rebuild Servo''' 

== Run Tests == 
We tested images with different file formats and resolution using ./mach run image_url. 
[[File:code_op.png]] 
These are the results we got:

CSC/ECE 517 Fall 2014/oss M1455 asa

2014-10-26T23:56:32Z

Aashetty: /* Steps of Implementation */

''' EVALUATE REPLACING C IMAGE & FONT LIBRARIES WITH RUST EQUIVALENTS '''
In this wiki we represent the steps involved in our OSS Mozilla Project using Rust Programming Language.

== Introduction ==
Servo is an experimental web browser layout engine being developed by Mozilla Research for new generation hardware.
The project has a symbiotic relationship with the Rust programming language, in which it is being developed. Rust is a new programming language for developing reliable and efficient systems.

Servo currently depends on a lot of C libraries, because Rust equivalents did not exist when the project started.
We want to evaluate switching some of these to new Rust libraries that have been created.
This project involves rewriting the code that uses these libraries as well as taking measurements before and after to determine the costs involved.

== Aim ==
The aim of our project is display the time required by the decode function to decode images of different formats, e.g, jpeg, bmp, png, gif.

== Steps of Implementation ==
We implemented the following steps on our linux machine: 

'''• Build Servo''' 
1. We first need to clone the servo repository using the following command: 
git clone https://www.github.com/servo/servo 
[[File:Git clone.png]] 
Now we have a local copy of the servo codebase.
 
 

2. We build the servo using 
./mach build 

[[File:build_servo.png]] 
 

3. Once our servo is built, we can run it using a test url 
./mach run url 

[[File:test_command.png]] 
[[File:test_op.png]] 
 
'''• Add timing code''' 
1. In image_cache_task.rs , we have a fn decode which calls the load_from_memory fn in base.rs. 
2. Image decoding is implemented in this load_from_memory function. 
3. So we added the timing code arround this function call in imacge_cache_task.rs 
4. precise_time_ns() gives us the current time. 
5. So we added it before the call to get the start time of decoding and after the call to get the end time. 
6. Difference of the two gave us the decoding time, which can be printed on command line. 
let start_time=precise_time_ns();
let image = load_from_memory(data.as_slice());
let end_time=precise_time_ns();
let required_time=(end_time-start_time) as f64/1000000f64;

CSC/ECE 517 Fall 2014/oss M1455 asa

2014-10-26T23:56:13Z

Aashetty: /* Steps of Implementation */

''' EVALUATE REPLACING C IMAGE & FONT LIBRARIES WITH RUST EQUIVALENTS '''
In this wiki we represent the steps involved in our OSS Mozilla Project using Rust Programming Language.

== Introduction ==
Servo is an experimental web browser layout engine being developed by Mozilla Research for new generation hardware.
The project has a symbiotic relationship with the Rust programming language, in which it is being developed. Rust is a new programming language for developing reliable and efficient systems.

Servo currently depends on a lot of C libraries, because Rust equivalents did not exist when the project started.
We want to evaluate switching some of these to new Rust libraries that have been created.
This project involves rewriting the code that uses these libraries as well as taking measurements before and after to determine the costs involved.

== Aim ==
The aim of our project is display the time required by the decode function to decode images of different formats, e.g, jpeg, bmp, png, gif.

== Steps of Implementation ==
We implemented the following steps on our linux machine: 

'''• Build Servo''' 
1. We first need to clone the servo repository using the following command: 
git clone https://www.github.com/servo/servo 
[[File:Git clone.png|thumb]] 
Now we have a local copy of the servo codebase.
 
 

2. We build the servo using 
./mach build 

[[File:build_servo.png]] 
 

3. Once our servo is built, we can run it using a test url 
./mach run url 

[[File:test_command.png|thumb]] 
[[File:test_op.png]] 
 
'''• Add timing code''' 
1. In image_cache_task.rs , we have a fn decode which calls the load_from_memory fn in base.rs. 
2. Image decoding is implemented in this load_from_memory function. 
3. So we added the timing code arround this function call in imacge_cache_task.rs 
4. precise_time_ns() gives us the current time. 
5. So we added it before the call to get the start time of decoding and after the call to get the end time. 
6. Difference of the two gave us the decoding time, which can be printed on command line. 
let start_time=precise_time_ns();
let image = load_from_memory(data.as_slice());
let end_time=precise_time_ns();
let required_time=(end_time-start_time) as f64/1000000f64;

CSC/ECE 517 Fall 2014/oss M1455 asa

2014-10-26T23:55:45Z

Aashetty: /* Steps of Implementation */

''' EVALUATE REPLACING C IMAGE & FONT LIBRARIES WITH RUST EQUIVALENTS '''
In this wiki we represent the steps involved in our OSS Mozilla Project using Rust Programming Language.

== Introduction ==
Servo is an experimental web browser layout engine being developed by Mozilla Research for new generation hardware.
The project has a symbiotic relationship with the Rust programming language, in which it is being developed. Rust is a new programming language for developing reliable and efficient systems.

Servo currently depends on a lot of C libraries, because Rust equivalents did not exist when the project started.
We want to evaluate switching some of these to new Rust libraries that have been created.
This project involves rewriting the code that uses these libraries as well as taking measurements before and after to determine the costs involved.

== Aim ==
The aim of our project is display the time required by the decode function to decode images of different formats, e.g, jpeg, bmp, png, gif.

== Steps of Implementation ==
We implemented the following steps on our linux machine: 

'''• Build Servo''' 
1. We first need to clone the servo repository using the following command: 
git clone https://www.github.com/servo/servo 
[[File:Git clone.png]] 
Now we have a local copy of the servo codebase.
 
 

2. We build the servo using 
./mach build 

[[File:build_servo.png]] 
 

3. Once our servo is built, we can run it using a test url 
./mach run url 

[[File:test_command.png|thumb]] 
[[File:test_op.png]] 
 
'''• Add timing code''' 
1. In image_cache_task.rs , we have a fn decode which calls the load_from_memory fn in base.rs. 
2. Image decoding is implemented in this load_from_memory function. 
3. So we added the timing code arround this function call in imacge_cache_task.rs 
4. precise_time_ns() gives us the current time. 
5. So we added it before the call to get the start time of decoding and after the call to get the end time. 
6. Difference of the two gave us the decoding time, which can be printed on command line. 
let start_time=precise_time_ns();
let image = load_from_memory(data.as_slice());
let end_time=precise_time_ns();
let required_time=(end_time-start_time) as f64/1000000f64;

CSC/ECE 517 Fall 2014/oss M1455 asa

2014-10-26T23:53:02Z

Aashetty: /* Steps of Implementation */

''' EVALUATE REPLACING C IMAGE & FONT LIBRARIES WITH RUST EQUIVALENTS '''
In this wiki we represent the steps involved in our OSS Mozilla Project using Rust Programming Language.

== Introduction ==
Servo is an experimental web browser layout engine being developed by Mozilla Research for new generation hardware.
The project has a symbiotic relationship with the Rust programming language, in which it is being developed. Rust is a new programming language for developing reliable and efficient systems.

Servo currently depends on a lot of C libraries, because Rust equivalents did not exist when the project started.
We want to evaluate switching some of these to new Rust libraries that have been created.
This project involves rewriting the code that uses these libraries as well as taking measurements before and after to determine the costs involved.

== Aim ==
The aim of our project is display the time required by the decode function to decode images of different formats, e.g, jpeg, bmp, png, gif.

== Steps of Implementation ==
We implemented the following steps on our linux machine: 
 
'''• Build Servo''' 
1. We first need to clone the servo repository using the following command: 
git clone https://www.github.com/servo/servo 
[[File:Git clone.png]] 
Now we have a local copy of the servo codebase.
 
 

2. We build the servo using 
./mach build 

[[File:build_servo.png]] 
 

3. Once our servo is built, we can run it using a test url 
./mach run url 

[[File:test_command.png]] 
[[File:test_op.png]] 
 
'''• Add timing code''' 
1. In image_cache_task.rs , we have a fn decode which calls the load_from_memory fn in base.rs. 
2. Image decoding is implemented in this load_from_memory function. 
3. So we added the timing code arround this function call in imacge_cache_task.rs
4. precise_time_ns() gives us the current time.
5. So we added it before the call to get the start time of decoding and after the call to get the end time.
6. Difference of the two gave us the decoding time, which can be printed on command line.
let start_time=precise_time_ns();
let image = load_from_memory(data.as_slice());
let end_time=precise_time_ns();
let required_time=(end_time-start_time) as f64/1000000f64;

CSC/ECE 517 Fall 2014/oss M1455 asa

2014-10-26T23:51:54Z

Aashetty: /* Steps of Implementation */

''' EVALUATE REPLACING C IMAGE & FONT LIBRARIES WITH RUST EQUIVALENTS '''
In this wiki we represent the steps involved in our OSS Mozilla Project using Rust Programming Language.

== Introduction ==
Servo is an experimental web browser layout engine being developed by Mozilla Research for new generation hardware.
The project has a symbiotic relationship with the Rust programming language, in which it is being developed. Rust is a new programming language for developing reliable and efficient systems.

Servo currently depends on a lot of C libraries, because Rust equivalents did not exist when the project started.
We want to evaluate switching some of these to new Rust libraries that have been created.
This project involves rewriting the code that uses these libraries as well as taking measurements before and after to determine the costs involved.

== Aim ==
The aim of our project is display the time required by the decode function to decode images of different formats, e.g, jpeg, bmp, png, gif.

== Steps of Implementation ==
We implemented the following steps on our linux machine: 
 
'''• Build Servo''' 
1. We first need to clone the servo repository using the following command: 
git clone https://www.github.com/servo/servo 
[[File:Git clone.png]] 
Now we have a local copy of the servo codebase.
 
 

2. We build the servo using 
./mach build 

[[File:build_servo.png|center|300x300px|]] 
 

3. Once our servo is built, we can run it using a test url 
./mach run url 

[[File:test_command.png]] 
[[File:test_op.png]] 
 
'''• Add timing code''' 
1. In image_cache_task.rs , we have a fn decode which calls the load_from_memory fn in base.rs. 
2. Image decoding is implemented in this load_from_memory function. 
3. So we added the timing code arround this function call in imacge_cache_task.rs
4. precise_time_ns() gives us the current time.
5. So we added it before the call to get the start time of decoding and after the call to get the end time.
6. Difference of the two gave us the decoding time, which can be printed on command line.
let start_time=precise_time_ns();
let image = load_from_memory(data.as_slice());
let end_time=precise_time_ns();
let required_time=(end_time-start_time) as f64/1000000f64;

File:Code op.png

2014-10-26T23:36:24Z

Aashetty:

File:Test op.png

2014-10-26T23:31:08Z

Aashetty:

File:Test command.png

2014-10-26T23:30:42Z

Aashetty:

File:Build servo.png

2014-10-26T23:28:11Z

Aashetty:

File:Git clone.png

2014-10-26T23:25:36Z

Aashetty:

CSC/ECE 517 Fall 2014/oss M1455 asa

2014-10-26T23:00:31Z

Aashetty: Created page with "'''''' Evaluate replacing C image & font libraries with Rust equivalents '''''''''Bold text'''"

'''''' Evaluate replacing C image & font libraries with Rust equivalents '''''''''Bold text'''

CSC/ECE 517 Fall 2014

2014-10-26T22:50:13Z

Aashetty:

*[[CSC/ECE_517_Fall_2014/sample_page]]
*[[CSC/ECE_517_Fall_2014/ch1a 22 as]]
*[[CSC/ECE 517 Fall 2014/ch1a 19 mx]]
*[[CSC/ECE 517 Fall 2014/ch1a 3 zq]]
*[[CSC/ECE 517 Fall 2014/ch1a 4 lf]]
*[[CSC/ECE 517 Fall 2014/ch1a 4 wl]]
*[[CSC/ECE 517 Fall 2014/ch1a a7 ch]]
*[[CSC/ECE 517 Fall 2014/ch1a 25 rs]]
*[[CSC/ECE 517 Fall 2014/ch1a 25 jf]]
*[[CSC/ECE 517 Fall 2014/ch1a 8 os]]
*[[CSC/ECE 517 Fall 2014/ch1a 8 sn]]
*[[CSC/ECE 517 Fall 2014/ch1a 15 gs]]
*[[CSC/ECE 517 Fall 2014/ch1a 10 hu]]
*[[CSC/ECE 517 Fall 2014/ch1a 20 kv]]
*[[CSC/ECE 517 Fall 2014/ch1a 21 as]]
*[[CSC/ECE 517 Fall 2014/ch1a 24 sa]]
*[[CSC/ECE 517 Fall 2014/ch1a 26 sn]]
*[[CSC/ECE 517 Fall 2014/ch1a 6 rl]]
*[[CSC/ECE 517 Fall 2014/ch1a 2 ss]]
*[[CSC/ECE 517 Fall 2014/ch1a 16 av]]
*[[CSC/ECE 517 Fall 2014/ch1a 1 rm]]
*[[CSC/ECE 517 Fall 2014/ch1a 1 sj]]
*[[CSC/ECE 517 Fall 2014/ch1a 23 ss]]
*[[CSC/ECE 517 Fall 2014/ch1a 20 rn]]
*[[CSC/ECE 517 Fall 2014/ch1a 22 sp]]
*[[CSC/ECE 517 Fall 2014/ch1a 26 gn]]

*[[CSC/ECE 517 Fall 2014/ch1a 13 va]]
*[[CSC/ECE 517 Fall 2014/ch1a 9 aa]]
*[[CSC/ECE 517 Fall 2014/ch1a 9 kn]]
*[[CSC/ECE 517 Fall 2014/ch1a 11 ap]]
*[[CSC/ECE 517 Fall 2014/ch1a 25 ks]]
*[[CSC/ECE 517 Fall 2014/ch1a 7 kz]]
*[[CSC/ECE_517_Fall_2014/ch1a_6_bn]]
*[[CSC/ECE_517_Fall_2014/ch1a 10 zz]]
*[[CSC/ECE_517_Fall_2014/ch1a 16 va]]
*[[CSC/ECE_517_Fall_2014/ch1a F1415 rv]]
*[[CSC/ECE_517_Fall_2014/ch1a_3_cp]]
*[[CSC/ECE 517 Fall 2014/ch1b 26 sa]]
*[[CSC/ECE_517_Fall_2014/ch1b_28_cg]]
*[[CSC/ECE_517_Fall_2014/ch1b 29 ry]]
*[[CSC/ECE_517_Fall_2014/ch1b 30 cs]]
*[[CSC/ECE_517_Fall_2014/ch1b_33_jy]]
*[[CSC/ECE_517_Fall_2014/ch1b_27_js]]
*[[CSC/ECE 517 Fall 2014/oss E1465 oak]]
*[[CSC/ECE 517 Fall 2014/oss_M1456_kdv]]
*[[CSC/ECE 517 Fall 2014/oss_E1456_akk]]
*[[CSC/ECE_517_Fall_2014/oss_M1455_asa]]

CSC/ECE 517 Fall 2014/ch1a 9 aa

2014-09-25T21:21:55Z

Aashetty: /* Further reading */

= 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 [http://en.wikipedia.org/wiki/Declarative_programming declarative programming] paradigm. One key feature in a functional language is the concept of [http://en.wikipedia.org/wiki/First-class_function 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 [http://en.wikipedia.org/wiki/Imperative_programming 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.<ref>http://en.wikipedia.org/wiki/Functional_programming</ref>
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 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<ref>http://en.wikibooks.org/wiki/Computer_Programming/Functional_programming</ref> =
===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.

<pre>
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);
</pre>

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<ref>http://www.haskell.org/haskellwiki/Functional_programming</ref>===
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. [http://en.wikipedia.org/wiki/Lazy_evaluation 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:
<pre>
String s1 = somewhatLongOperation1();
String s2 = somewhatLongOperation2();
String s3 = concatenate(s1, s2);
</pre>

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===
[http://www.cs.utah.edu/~germain/PPS/Topics/recursion.html Recursion] is heavily used in functional programming as it is the canonical and often the only way to iterate. Functional language implementations will often include tail call optimization to ensure that heavy recursion does not consume excessive memory.

===Pattern Matching<ref>http://c2.com/cgi/wiki?PatternMatching</ref>===
In the context of pure functional languages, [http://en.wikipedia.org/wiki/Pattern_matching Pattern Matching] is a dispatch mechanism: choosing which variant of a function is the correct one to call. Example:
<pre>
factorial(0) ::= 1
factorial(n) ::= n * factorial(n-1)
</pre>
The function has been given two definitions. Which is used for dispatch when a call is made will depend, in this case, on whether the actual parameter pattern matches 0 or not. The matching is not limited to constants; in general, functions have a [http://en.wikipedia.org/wiki/Type_signature TypeSignature] used for matching. [http://en.wikipedia.org/wiki/Currying Currying] is integrated into this mechanism.
1.Pattern matching is the compiler's ability to compare both the form and the content of two expressions. It is used in two ways:
All or part of a data structure may be assigned to one or several variables in a single expression.
2.A function may have several definitions (clauses), according to the form and/or content of its arguments. This second use is usually combined with the first to initialize the variables that will be used in the clause.
In both these uses, a pattern match has the additional benefit of making an assertion about the form and/or content of a variable.

===Closures===
Passing functions around in impure languages is a little bit different than doing it in the confines of lambda calculus and requires support for an interesting feature often referred to as [https://www.princeton.edu/~achaney/tmve/wiki100k/docs/Closure_(computer_science).html lexical closure]. Let's take a look at some sample code. Remember, in this case variables aren't final and functions can refer to variables outside of their scope:
<pre>
Function makePowerFn(int power) {
int powerFn(int base) {
return pow(base, power);
}
return powerFn;
}
Function square = makePowerFn(2);
square(3); // returns 9
</pre>

The function makePowerFn returns a function that takes a single argument and raises it to a certain power. What happens when we try to evaluate square(3)? The variable power isn't anywhere in scope of powerFn because makePowerFn has returned and its stack is long gone. How can square work, then? The language must, somehow, store the value of power somewhere for square to work. What if we create another function, cube, that raises something to the third power? The runtime must now store two copies of power, one for each function we generated using makePowerFn. The phenomenon of storing these values is called a closure.

= Comparison between Functional Programming and OOP <ref>http://wiki.expertiza.ncsu.edu/index.php/CSC/ECE_517_Fall_2013/ch1_1w25_aras</ref> =
Let us compare both the programming paradigms with respect to several disctinction attributes.
{| class="wikitable" border="1"
! scope="col" | Point of Comparison
! scope="col" | Functional Languages
! scope="col" | Object-Oriented Languages
|-
|
* Primary focus
| Functional programming emphasizes on functions that produce results which depend only on their inputs and not on the program state - i.e. pure mathematial functions. || Focus on identifying and''' representing the problem in terms of an 'object'''' which has its own data, sub-routines and state. Different objects in the problem interact by sending messages to each other and thus result in change in its internal state. The final state and values of the objects refer to the solution. It is '''data-centric'''.
|-
|
* Problem Solving Approach
| Primarily''' Top-down''' design || '''Identification and design of necessary objects'''. Close to being 'better models of the way the world works'.
|-
|
* Program Flow
| '''Often sequential''' with program having single point of entry and exit. || '''Complex''' program flow. Can sometimes depend on the internal state of the objects.
|-
|
* Modularity
| '''Limited modularity'''. Program is divided into modules or per say procedures independent of each other but are constrained due to uniqueness to that particular problem. || '''Extremely modular''' due to the presence of objects which contain their own data and sub-routines.
|-
|
* Data Protection/Hiding
| '''No concept of data-hiding'''. Variables local to one method cannot be accessed by other method. But, Global variables can be accessed anywhere within the program. || One of the main fundamentals of O-O languages.''' Access specifiers''' like 'public', 'private' and 'protected' dictate the rules of data-hiding. Data which is private is confined to one object and cannot be directly changed by any other method except its own. This places the responsibility of managing data with the object itself This is called as ownership. Thus, data can be accessed ( read/write/modified )''' only''' through the object's own interfaces.
|-
|
* Ease of Understanding
|'''Smaller programs''' are '''easy to understand''' but as the program increases in size; understanding the code becomes more and more difficult. || '''Easy to understand''' due to its real world-like design and flow.
|-
|
* Reuse of Code
| '''Very Limited or no''' code re-usability. ||'''Highly re-usable code''' as the code developed can be easily modified or extended to suit a problem's need.
|-
|
* Support for declaring new data types/classes
|'''Difficult '''due to limited in-built functionality. || '''Easily possible''' due to the concept of classes. Generic classes can be built as per the required specifications.
|-
|
* Efficiency
| '''Efficient''' for solving '''small''' problems. || '''Efficient''' for solving '''large problems''' which have a complex structure and require complex data-types, abstraction and data-security.
|-
|
* Maintenance
| Maintenance is''' easy for smaller programs''' but can consume''' a-lot of effort for larger program''' size as it requires the programmer to know and understand the dependencies of every module in the program. This makes it difficult to debug and test the program. ||'''Extremely simple''' as O-O languages aim for high modularity. Secondly, programmer is not concerned with the details of how the data is stored and represented. Thirdly, they also tend to keep low coupling which makes it easy to debug and test different modules in the program.
|-
|
* Extensibility
| '''Less Extensible''' as modules developed need to be re-organised and re-structured heavily in order to meet different needs. || '''High extensibility''' is one of the most important advantages of OOP. Code can be easily modified and 'plugged-in' to a different program. Methods can be exteneded due to many properties such as polymorphism, inheritance and support for multiple inheritance through interfaces.
|-
|
* Flexibility
| '''Less flexible.''' Sometimes, certain problems do not fit into the 'top-down design' approach. || '''High flexibility.''' The modelling of problems into world-like objects makes it easy to solve any practical problem.
|-
|
* Examples
| [http://en.wikipedia.org/wiki/Haskell_%28programming_language%29 Haskell], [http://en.wikipedia.org/wiki/Scala_%28programming_language%29 Scala], [http://en.wikipedia.org/wiki/Erlang_%28programming_language%29 Erlang] || [http://en.wikipedia.org/wiki/C%2B%2B C++], [http://en.wikipedia.org/wiki/Java_(programming_language) Java], [http://en.wikipedia.org/wiki/Ruby_(programming_language) Ruby], [http://en.wikipedia.org/wiki/Python_(programming_language) Python].
|}

= Scala : An overview <ref>http://docs.scala-lang.org/tutorials/scala-for-java-programmers.html</ref>=
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.
<pre>
object HelloWorld
{
def main(args: Array[String])
{
println("Hello, world!")
}
}
</pre>
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 <ref>http://www.scala-lang.org/old/node/104</ref>=
===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 ([http://docs.oracle.com/javase/7/docs/ 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 [http://www.eclipse.org/documentation/ Eclipse],[https://netbeans.org/kb/ Netbeans] and [http://www.jetbrains.com/idea/ 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 <ref>http://www.codecommit.com/blog/scala/scala-for-java-refugees-part-3</ref>=
===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 and return types. Scala does allow for different visibilities on not just methods, but any members.
For example:
<pre>
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)
}
}
</pre>

Scala provides the 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:
<pre>
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)
</pre>

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

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

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

===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:
<pre>
list map { x => sqrt(x) }

can be written more concisely as

list map { sqrt(_) }
</pre>

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

===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:
<pre>
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;
}
}
</pre>

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:

<pre>
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
}
}
</pre>
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.

<pre>

trait Book
{
def title:String
def title_=(n:String):Unit

def computePrice = title.length * 10
}

</pre>

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 our CollegeStudent example in Scala without redundancy or fear of paradox:
<pre>
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 {
// ...
}

</pre>

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

= References =
<references />

= Further reading =
# [http://vimeo.com/20293743 Video to learn about Scala]
# [http://docs.scala-lang.org/tutorials/ Scala Documentation]
# [http://shipilev.net/blog/2014/java-scala-divided-we-fail/#_analyzing_bottlenecks Java vs. Scala]
# [http://www.cs.uku.fi/~mnykanen/FOH/lectures1.pdf Salient Features of Functional Programming]
# [https://www.cs.rpi.edu/research/pdf/10-04.pdf Comparison of Object-oriented and Functional Programming]
# [http://en.wikibooks.org/wiki/Object_Oriented_Programming features of Object oriented programming]

CSC/ECE 517 Fall 2014/ch1a 9 aa

2014-09-25T21:15:10Z

Aashetty: /* Scala interoperates with Java and .NET */

CSC/ECE 517 Fall 2014/ch1a 9 aa

2014-09-25T21:14:24Z

Aashetty: /* Scala interoperates with Java and .NET */

= 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 [http://en.wikipedia.org/wiki/Declarative_programming declarative programming] paradigm. One key feature in a functional language is the concept of [http://en.wikipedia.org/wiki/First-class_function 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 [http://en.wikipedia.org/wiki/Imperative_programming 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.<ref>http://en.wikipedia.org/wiki/Functional_programming</ref>
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 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<ref>http://en.wikibooks.org/wiki/Computer_Programming/Functional_programming</ref> =
===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.

<pre>
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);
</pre>

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<ref>http://www.haskell.org/haskellwiki/Functional_programming</ref>===
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. [http://en.wikipedia.org/wiki/Lazy_evaluation 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:
<pre>
String s1 = somewhatLongOperation1();
String s2 = somewhatLongOperation2();
String s3 = concatenate(s1, s2);
</pre>

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===
[http://www.cs.utah.edu/~germain/PPS/Topics/recursion.html Recursion] is heavily used in functional programming as it is the canonical and often the only way to iterate. Functional language implementations will often include tail call optimization to ensure that heavy recursion does not consume excessive memory.

===Pattern Matching<ref>http://c2.com/cgi/wiki?PatternMatching</ref>===
In the context of pure functional languages, [http://en.wikipedia.org/wiki/Pattern_matching Pattern Matching] is a dispatch mechanism: choosing which variant of a function is the correct one to call. Example:
<pre>
factorial(0) ::= 1
factorial(n) ::= n * factorial(n-1)
</pre>
The function has been given two definitions. Which is used for dispatch when a call is made will depend, in this case, on whether the actual parameter pattern matches 0 or not. The matching is not limited to constants; in general, functions have a [http://en.wikipedia.org/wiki/Type_signature TypeSignature] used for matching. [http://en.wikipedia.org/wiki/Currying Currying] is integrated into this mechanism.
1.Pattern matching is the compiler's ability to compare both the form and the content of two expressions. It is used in two ways:
All or part of a data structure may be assigned to one or several variables in a single expression.
2.A function may have several definitions (clauses), according to the form and/or content of its arguments. This second use is usually combined with the first to initialize the variables that will be used in the clause.
In both these uses, a pattern match has the additional benefit of making an assertion about the form and/or content of a variable.

===Closures===
Passing functions around in impure languages is a little bit different than doing it in the confines of lambda calculus and requires support for an interesting feature often referred to as [https://www.princeton.edu/~achaney/tmve/wiki100k/docs/Closure_(computer_science).html lexical closure]. Let's take a look at some sample code. Remember, in this case variables aren't final and functions can refer to variables outside of their scope:
<pre>
Function makePowerFn(int power) {
int powerFn(int base) {
return pow(base, power);
}
return powerFn;
}
Function square = makePowerFn(2);
square(3); // returns 9
</pre>

The function makePowerFn returns a function that takes a single argument and raises it to a certain power. What happens when we try to evaluate square(3)? The variable power isn't anywhere in scope of powerFn because makePowerFn has returned and its stack is long gone. How can square work, then? The language must, somehow, store the value of power somewhere for square to work. What if we create another function, cube, that raises something to the third power? The runtime must now store two copies of power, one for each function we generated using makePowerFn. The phenomenon of storing these values is called a closure.

= Comparison between Functional Programming and OOP <ref>http://wiki.expertiza.ncsu.edu/index.php/CSC/ECE_517_Fall_2013/ch1_1w25_aras</ref> =
Let us compare both the programming paradigms with respect to several disctinction attributes.
{| class="wikitable" border="1"
! scope="col" | Point of Comparison
! scope="col" | Functional Languages
! scope="col" | Object-Oriented Languages
|-
|
* Primary focus
| Functional programming emphasizes on functions that produce results which depend only on their inputs and not on the program state - i.e. pure mathematial functions. || Focus on identifying and''' representing the problem in terms of an 'object'''' which has its own data, sub-routines and state. Different objects in the problem interact by sending messages to each other and thus result in change in its internal state. The final state and values of the objects refer to the solution. It is '''data-centric'''.
|-
|
* Problem Solving Approach
| Primarily''' Top-down''' design || '''Identification and design of necessary objects'''. Close to being 'better models of the way the world works'.
|-
|
* Program Flow
| '''Often sequential''' with program having single point of entry and exit. || '''Complex''' program flow. Can sometimes depend on the internal state of the objects.
|-
|
* Modularity
| '''Limited modularity'''. Program is divided into modules or per say procedures independent of each other but are constrained due to uniqueness to that particular problem. || '''Extremely modular''' due to the presence of objects which contain their own data and sub-routines.
|-
|
* Data Protection/Hiding
| '''No concept of data-hiding'''. Variables local to one method cannot be accessed by other method. But, Global variables can be accessed anywhere within the program. || One of the main fundamentals of O-O languages.''' Access specifiers''' like 'public', 'private' and 'protected' dictate the rules of data-hiding. Data which is private is confined to one object and cannot be directly changed by any other method except its own. This places the responsibility of managing data with the object itself This is called as ownership. Thus, data can be accessed ( read/write/modified )''' only''' through the object's own interfaces.
|-
|
* Ease of Understanding
|'''Smaller programs''' are '''easy to understand''' but as the program increases in size; understanding the code becomes more and more difficult. || '''Easy to understand''' due to its real world-like design and flow.
|-
|
* Reuse of Code
| '''Very Limited or no''' code re-usability. ||'''Highly re-usable code''' as the code developed can be easily modified or extended to suit a problem's need.
|-
|
* Support for declaring new data types/classes
|'''Difficult '''due to limited in-built functionality. || '''Easily possible''' due to the concept of classes. Generic classes can be built as per the required specifications.
|-
|
* Efficiency
| '''Efficient''' for solving '''small''' problems. || '''Efficient''' for solving '''large problems''' which have a complex structure and require complex data-types, abstraction and data-security.
|-
|
* Maintenance
| Maintenance is''' easy for smaller programs''' but can consume''' a-lot of effort for larger program''' size as it requires the programmer to know and understand the dependencies of every module in the program. This makes it difficult to debug and test the program. ||'''Extremely simple''' as O-O languages aim for high modularity. Secondly, programmer is not concerned with the details of how the data is stored and represented. Thirdly, they also tend to keep low coupling which makes it easy to debug and test different modules in the program.
|-
|
* Extensibility
| '''Less Extensible''' as modules developed need to be re-organised and re-structured heavily in order to meet different needs. || '''High extensibility''' is one of the most important advantages of OOP. Code can be easily modified and 'plugged-in' to a different program. Methods can be exteneded due to many properties such as polymorphism, inheritance and support for multiple inheritance through interfaces.
|-
|
* Flexibility
| '''Less flexible.''' Sometimes, certain problems do not fit into the 'top-down design' approach. || '''High flexibility.''' The modelling of problems into world-like objects makes it easy to solve any practical problem.
|-
|
* Examples
| [http://en.wikipedia.org/wiki/Haskell_%28programming_language%29 Haskell], [http://en.wikipedia.org/wiki/Scala_%28programming_language%29 Scala], [http://en.wikipedia.org/wiki/Erlang_%28programming_language%29 Erlang] || [http://en.wikipedia.org/wiki/C%2B%2B C++], [http://en.wikipedia.org/wiki/Java_(programming_language) Java], [http://en.wikipedia.org/wiki/Ruby_(programming_language) Ruby], [http://en.wikipedia.org/wiki/Python_(programming_language) Python].
|}

= Scala : An overview <ref>http://docs.scala-lang.org/tutorials/scala-for-java-programmers.html</ref>=
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.
<pre>
object HelloWorld
{
def main(args: Array[String])
{
println("Hello, world!")
}
}
</pre>
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 <ref>http://www.scala-lang.org/old/node/104</ref>=
===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 ([http://docs.oracle.com/javase/7/docs/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 [http://www.eclipse.org/documentation/ Eclipse],[https://netbeans.org/kb/ Netbeans] and [http://www.jetbrains.com/idea/ 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 <ref>http://www.codecommit.com/blog/scala/scala-for-java-refugees-part-3</ref>=
===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 and return types. Scala does allow for different visibilities on not just methods, but any members.
For example:
<pre>
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)
}
}
</pre>

Scala provides the 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:
<pre>
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)
</pre>

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

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

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

===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:
<pre>
list map { x => sqrt(x) }

can be written more concisely as

list map { sqrt(_) }
</pre>

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

===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:
<pre>
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;
}
}
</pre>

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:

<pre>
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
}
}
</pre>
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.

<pre>

trait Book
{
def title:String
def title_=(n:String):Unit

def computePrice = title.length * 10
}

</pre>

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 our CollegeStudent example in Scala without redundancy or fear of paradox:
<pre>
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 {
// ...
}

</pre>

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

= References =
<references />

= Further reading =
# [http://vimeo.com/20293743 Video to learn about Scala]
# [http://docs.scala-lang.org/tutorials/ Scala Documentation]
# [http://shipilev.net/blog/2014/java-scala-divided-we-fail/#_analyzing_bottlenecks Java vs. Scala]
# [http://www.cs.uku.fi/~mnykanen/FOH/lectures1.pdf Salient Features of Functional Programming]
# [https://www.cs.rpi.edu/research/pdf/10-04.pdf Comparison of Object-oriented and Functional Programming]

CSC/ECE 517 Fall 2014/ch1a 9 aa

2014-09-25T21:13:34Z

Aashetty: /* Similarities between Scala and Java */

= 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 [http://en.wikipedia.org/wiki/Declarative_programming declarative programming] paradigm. One key feature in a functional language is the concept of [http://en.wikipedia.org/wiki/First-class_function 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 [http://en.wikipedia.org/wiki/Imperative_programming 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.<ref>http://en.wikipedia.org/wiki/Functional_programming</ref>
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 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<ref>http://en.wikibooks.org/wiki/Computer_Programming/Functional_programming</ref> =
===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.

<pre>
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);
</pre>

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<ref>http://www.haskell.org/haskellwiki/Functional_programming</ref>===
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. [http://en.wikipedia.org/wiki/Lazy_evaluation 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:
<pre>
String s1 = somewhatLongOperation1();
String s2 = somewhatLongOperation2();
String s3 = concatenate(s1, s2);
</pre>

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===
[http://www.cs.utah.edu/~germain/PPS/Topics/recursion.html Recursion] is heavily used in functional programming as it is the canonical and often the only way to iterate. Functional language implementations will often include tail call optimization to ensure that heavy recursion does not consume excessive memory.

===Pattern Matching<ref>http://c2.com/cgi/wiki?PatternMatching</ref>===
In the context of pure functional languages, [http://en.wikipedia.org/wiki/Pattern_matching Pattern Matching] is a dispatch mechanism: choosing which variant of a function is the correct one to call. Example:
<pre>
factorial(0) ::= 1
factorial(n) ::= n * factorial(n-1)
</pre>
The function has been given two definitions. Which is used for dispatch when a call is made will depend, in this case, on whether the actual parameter pattern matches 0 or not. The matching is not limited to constants; in general, functions have a [http://en.wikipedia.org/wiki/Type_signature TypeSignature] used for matching. [http://en.wikipedia.org/wiki/Currying Currying] is integrated into this mechanism.
1.Pattern matching is the compiler's ability to compare both the form and the content of two expressions. It is used in two ways:
All or part of a data structure may be assigned to one or several variables in a single expression.
2.A function may have several definitions (clauses), according to the form and/or content of its arguments. This second use is usually combined with the first to initialize the variables that will be used in the clause.
In both these uses, a pattern match has the additional benefit of making an assertion about the form and/or content of a variable.

===Closures===
Passing functions around in impure languages is a little bit different than doing it in the confines of lambda calculus and requires support for an interesting feature often referred to as [https://www.princeton.edu/~achaney/tmve/wiki100k/docs/Closure_(computer_science).html lexical closure]. Let's take a look at some sample code. Remember, in this case variables aren't final and functions can refer to variables outside of their scope:
<pre>
Function makePowerFn(int power) {
int powerFn(int base) {
return pow(base, power);
}
return powerFn;
}
Function square = makePowerFn(2);
square(3); // returns 9
</pre>

The function makePowerFn returns a function that takes a single argument and raises it to a certain power. What happens when we try to evaluate square(3)? The variable power isn't anywhere in scope of powerFn because makePowerFn has returned and its stack is long gone. How can square work, then? The language must, somehow, store the value of power somewhere for square to work. What if we create another function, cube, that raises something to the third power? The runtime must now store two copies of power, one for each function we generated using makePowerFn. The phenomenon of storing these values is called a closure.

= Comparison between Functional Programming and OOP <ref>http://wiki.expertiza.ncsu.edu/index.php/CSC/ECE_517_Fall_2013/ch1_1w25_aras</ref> =
Let us compare both the programming paradigms with respect to several disctinction attributes.
{| class="wikitable" border="1"
! scope="col" | Point of Comparison
! scope="col" | Functional Languages
! scope="col" | Object-Oriented Languages
|-
|
* Primary focus
| Functional programming emphasizes on functions that produce results which depend only on their inputs and not on the program state - i.e. pure mathematial functions. || Focus on identifying and''' representing the problem in terms of an 'object'''' which has its own data, sub-routines and state. Different objects in the problem interact by sending messages to each other and thus result in change in its internal state. The final state and values of the objects refer to the solution. It is '''data-centric'''.
|-
|
* Problem Solving Approach
| Primarily''' Top-down''' design || '''Identification and design of necessary objects'''. Close to being 'better models of the way the world works'.
|-
|
* Program Flow
| '''Often sequential''' with program having single point of entry and exit. || '''Complex''' program flow. Can sometimes depend on the internal state of the objects.
|-
|
* Modularity
| '''Limited modularity'''. Program is divided into modules or per say procedures independent of each other but are constrained due to uniqueness to that particular problem. || '''Extremely modular''' due to the presence of objects which contain their own data and sub-routines.
|-
|
* Data Protection/Hiding
| '''No concept of data-hiding'''. Variables local to one method cannot be accessed by other method. But, Global variables can be accessed anywhere within the program. || One of the main fundamentals of O-O languages.''' Access specifiers''' like 'public', 'private' and 'protected' dictate the rules of data-hiding. Data which is private is confined to one object and cannot be directly changed by any other method except its own. This places the responsibility of managing data with the object itself This is called as ownership. Thus, data can be accessed ( read/write/modified )''' only''' through the object's own interfaces.
|-
|
* Ease of Understanding
|'''Smaller programs''' are '''easy to understand''' but as the program increases in size; understanding the code becomes more and more difficult. || '''Easy to understand''' due to its real world-like design and flow.
|-
|
* Reuse of Code
| '''Very Limited or no''' code re-usability. ||'''Highly re-usable code''' as the code developed can be easily modified or extended to suit a problem's need.
|-
|
* Support for declaring new data types/classes
|'''Difficult '''due to limited in-built functionality. || '''Easily possible''' due to the concept of classes. Generic classes can be built as per the required specifications.
|-
|
* Efficiency
| '''Efficient''' for solving '''small''' problems. || '''Efficient''' for solving '''large problems''' which have a complex structure and require complex data-types, abstraction and data-security.
|-
|
* Maintenance
| Maintenance is''' easy for smaller programs''' but can consume''' a-lot of effort for larger program''' size as it requires the programmer to know and understand the dependencies of every module in the program. This makes it difficult to debug and test the program. ||'''Extremely simple''' as O-O languages aim for high modularity. Secondly, programmer is not concerned with the details of how the data is stored and represented. Thirdly, they also tend to keep low coupling which makes it easy to debug and test different modules in the program.
|-
|
* Extensibility
| '''Less Extensible''' as modules developed need to be re-organised and re-structured heavily in order to meet different needs. || '''High extensibility''' is one of the most important advantages of OOP. Code can be easily modified and 'plugged-in' to a different program. Methods can be exteneded due to many properties such as polymorphism, inheritance and support for multiple inheritance through interfaces.
|-
|
* Flexibility
| '''Less flexible.''' Sometimes, certain problems do not fit into the 'top-down design' approach. || '''High flexibility.''' The modelling of problems into world-like objects makes it easy to solve any practical problem.
|-
|
* Examples
| [http://en.wikipedia.org/wiki/Haskell_%28programming_language%29 Haskell], [http://en.wikipedia.org/wiki/Scala_%28programming_language%29 Scala], [http://en.wikipedia.org/wiki/Erlang_%28programming_language%29 Erlang] || [http://en.wikipedia.org/wiki/C%2B%2B C++], [http://en.wikipedia.org/wiki/Java_(programming_language) Java], [http://en.wikipedia.org/wiki/Ruby_(programming_language) Ruby], [http://en.wikipedia.org/wiki/Python_(programming_language) Python].
|}

= Scala : An overview <ref>http://docs.scala-lang.org/tutorials/scala-for-java-programmers.html</ref>=
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.
<pre>
object HelloWorld
{
def main(args: Array[String])
{
println("Hello, world!")
}
}
</pre>
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 <ref>http://www.scala-lang.org/old/node/104</ref>=
===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 [http://www.eclipse.org/documentation/ Eclipse],[https://netbeans.org/kb/ Netbeans] and [http://www.jetbrains.com/idea/ 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 <ref>http://www.codecommit.com/blog/scala/scala-for-java-refugees-part-3</ref>=
===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 and return types. Scala does allow for different visibilities on not just methods, but any members.
For example:
<pre>
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)
}
}
</pre>

Scala provides the 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:
<pre>
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)
</pre>

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

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

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

===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:
<pre>
list map { x => sqrt(x) }

can be written more concisely as

list map { sqrt(_) }
</pre>

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

===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:
<pre>
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;
}
}
</pre>

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:

<pre>
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
}
}
</pre>
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.

<pre>

trait Book
{
def title:String
def title_=(n:String):Unit

def computePrice = title.length * 10
}

</pre>

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 our CollegeStudent example in Scala without redundancy or fear of paradox:
<pre>
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 {
// ...
}

</pre>

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

= References =
<references />

= Further reading =
# [http://vimeo.com/20293743 Video to learn about Scala]
# [http://docs.scala-lang.org/tutorials/ Scala Documentation]
# [http://shipilev.net/blog/2014/java-scala-divided-we-fail/#_analyzing_bottlenecks Java vs. Scala]
# [http://www.cs.uku.fi/~mnykanen/FOH/lectures1.pdf Salient Features of Functional Programming]
# [https://www.cs.rpi.edu/research/pdf/10-04.pdf Comparison of Object-oriented and Functional Programming]

CSC/ECE 517 Fall 2014/ch1a 9 aa

2014-09-25T21:12:24Z

Aashetty: /* Similarities between Scala and Java */

= 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 [http://en.wikipedia.org/wiki/Declarative_programming declarative programming] paradigm. One key feature in a functional language is the concept of [http://en.wikipedia.org/wiki/First-class_function 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 [http://en.wikipedia.org/wiki/Imperative_programming 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.<ref>http://en.wikipedia.org/wiki/Functional_programming</ref>
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 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<ref>http://en.wikibooks.org/wiki/Computer_Programming/Functional_programming</ref> =
===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.

<pre>
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);
</pre>

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<ref>http://www.haskell.org/haskellwiki/Functional_programming</ref>===
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. [http://en.wikipedia.org/wiki/Lazy_evaluation 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:
<pre>
String s1 = somewhatLongOperation1();
String s2 = somewhatLongOperation2();
String s3 = concatenate(s1, s2);
</pre>

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===
[http://www.cs.utah.edu/~germain/PPS/Topics/recursion.html Recursion] is heavily used in functional programming as it is the canonical and often the only way to iterate. Functional language implementations will often include tail call optimization to ensure that heavy recursion does not consume excessive memory.

===Pattern Matching<ref>http://c2.com/cgi/wiki?PatternMatching</ref>===
In the context of pure functional languages, [http://en.wikipedia.org/wiki/Pattern_matching Pattern Matching] is a dispatch mechanism: choosing which variant of a function is the correct one to call. Example:
<pre>
factorial(0) ::= 1
factorial(n) ::= n * factorial(n-1)
</pre>
The function has been given two definitions. Which is used for dispatch when a call is made will depend, in this case, on whether the actual parameter pattern matches 0 or not. The matching is not limited to constants; in general, functions have a [http://en.wikipedia.org/wiki/Type_signature TypeSignature] used for matching. [http://en.wikipedia.org/wiki/Currying Currying] is integrated into this mechanism.
1.Pattern matching is the compiler's ability to compare both the form and the content of two expressions. It is used in two ways:
All or part of a data structure may be assigned to one or several variables in a single expression.
2.A function may have several definitions (clauses), according to the form and/or content of its arguments. This second use is usually combined with the first to initialize the variables that will be used in the clause.
In both these uses, a pattern match has the additional benefit of making an assertion about the form and/or content of a variable.

===Closures===
Passing functions around in impure languages is a little bit different than doing it in the confines of lambda calculus and requires support for an interesting feature often referred to as [https://www.princeton.edu/~achaney/tmve/wiki100k/docs/Closure_(computer_science).html lexical closure]. Let's take a look at some sample code. Remember, in this case variables aren't final and functions can refer to variables outside of their scope:
<pre>
Function makePowerFn(int power) {
int powerFn(int base) {
return pow(base, power);
}
return powerFn;
}
Function square = makePowerFn(2);
square(3); // returns 9
</pre>

The function makePowerFn returns a function that takes a single argument and raises it to a certain power. What happens when we try to evaluate square(3)? The variable power isn't anywhere in scope of powerFn because makePowerFn has returned and its stack is long gone. How can square work, then? The language must, somehow, store the value of power somewhere for square to work. What if we create another function, cube, that raises something to the third power? The runtime must now store two copies of power, one for each function we generated using makePowerFn. The phenomenon of storing these values is called a closure.

= Comparison between Functional Programming and OOP <ref>http://wiki.expertiza.ncsu.edu/index.php/CSC/ECE_517_Fall_2013/ch1_1w25_aras</ref> =
Let us compare both the programming paradigms with respect to several disctinction attributes.
{| class="wikitable" border="1"
! scope="col" | Point of Comparison
! scope="col" | Functional Languages
! scope="col" | Object-Oriented Languages
|-
|
* Primary focus
| Functional programming emphasizes on functions that produce results which depend only on their inputs and not on the program state - i.e. pure mathematial functions. || Focus on identifying and''' representing the problem in terms of an 'object'''' which has its own data, sub-routines and state. Different objects in the problem interact by sending messages to each other and thus result in change in its internal state. The final state and values of the objects refer to the solution. It is '''data-centric'''.
|-
|
* Problem Solving Approach
| Primarily''' Top-down''' design || '''Identification and design of necessary objects'''. Close to being 'better models of the way the world works'.
|-
|
* Program Flow
| '''Often sequential''' with program having single point of entry and exit. || '''Complex''' program flow. Can sometimes depend on the internal state of the objects.
|-
|
* Modularity
| '''Limited modularity'''. Program is divided into modules or per say procedures independent of each other but are constrained due to uniqueness to that particular problem. || '''Extremely modular''' due to the presence of objects which contain their own data and sub-routines.
|-
|
* Data Protection/Hiding
| '''No concept of data-hiding'''. Variables local to one method cannot be accessed by other method. But, Global variables can be accessed anywhere within the program. || One of the main fundamentals of O-O languages.''' Access specifiers''' like 'public', 'private' and 'protected' dictate the rules of data-hiding. Data which is private is confined to one object and cannot be directly changed by any other method except its own. This places the responsibility of managing data with the object itself This is called as ownership. Thus, data can be accessed ( read/write/modified )''' only''' through the object's own interfaces.
|-
|
* Ease of Understanding
|'''Smaller programs''' are '''easy to understand''' but as the program increases in size; understanding the code becomes more and more difficult. || '''Easy to understand''' due to its real world-like design and flow.
|-
|
* Reuse of Code
| '''Very Limited or no''' code re-usability. ||'''Highly re-usable code''' as the code developed can be easily modified or extended to suit a problem's need.
|-
|
* Support for declaring new data types/classes
|'''Difficult '''due to limited in-built functionality. || '''Easily possible''' due to the concept of classes. Generic classes can be built as per the required specifications.
|-
|
* Efficiency
| '''Efficient''' for solving '''small''' problems. || '''Efficient''' for solving '''large problems''' which have a complex structure and require complex data-types, abstraction and data-security.
|-
|
* Maintenance
| Maintenance is''' easy for smaller programs''' but can consume''' a-lot of effort for larger program''' size as it requires the programmer to know and understand the dependencies of every module in the program. This makes it difficult to debug and test the program. ||'''Extremely simple''' as O-O languages aim for high modularity. Secondly, programmer is not concerned with the details of how the data is stored and represented. Thirdly, they also tend to keep low coupling which makes it easy to debug and test different modules in the program.
|-
|
* Extensibility
| '''Less Extensible''' as modules developed need to be re-organised and re-structured heavily in order to meet different needs. || '''High extensibility''' is one of the most important advantages of OOP. Code can be easily modified and 'plugged-in' to a different program. Methods can be exteneded due to many properties such as polymorphism, inheritance and support for multiple inheritance through interfaces.
|-
|
* Flexibility
| '''Less flexible.''' Sometimes, certain problems do not fit into the 'top-down design' approach. || '''High flexibility.''' The modelling of problems into world-like objects makes it easy to solve any practical problem.
|-
|
* Examples
| [http://en.wikipedia.org/wiki/Haskell_%28programming_language%29 Haskell], [http://en.wikipedia.org/wiki/Scala_%28programming_language%29 Scala], [http://en.wikipedia.org/wiki/Erlang_%28programming_language%29 Erlang] || [http://en.wikipedia.org/wiki/C%2B%2B C++], [http://en.wikipedia.org/wiki/Java_(programming_language) Java], [http://en.wikipedia.org/wiki/Ruby_(programming_language) Ruby], [http://en.wikipedia.org/wiki/Python_(programming_language) Python].
|}

= Scala : An overview <ref>http://docs.scala-lang.org/tutorials/scala-for-java-programmers.html</ref>=
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.
<pre>
object HelloWorld
{
def main(args: Array[String])
{
println("Hello, world!")
}
}
</pre>
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 <ref>http://www.scala-lang.org/old/node/104</ref>=
===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 [http://www.jetbrains.com/idea/ 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 <ref>http://www.codecommit.com/blog/scala/scala-for-java-refugees-part-3</ref>=
===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 and return types. Scala does allow for different visibilities on not just methods, but any members.
For example:
<pre>
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)
}
}
</pre>

Scala provides the 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:
<pre>
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)
</pre>

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

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

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

===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:
<pre>
list map { x => sqrt(x) }

can be written more concisely as

list map { sqrt(_) }
</pre>

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

===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:
<pre>
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;
}
}
</pre>

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:

<pre>
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
}
}
</pre>
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.

<pre>

trait Book
{
def title:String
def title_=(n:String):Unit

def computePrice = title.length * 10
}

</pre>

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 our CollegeStudent example in Scala without redundancy or fear of paradox:
<pre>
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 {
// ...
}

</pre>

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

= References =
<references />

= Further reading =
# [http://vimeo.com/20293743 Video to learn about Scala]
# [http://docs.scala-lang.org/tutorials/ Scala Documentation]
# [http://shipilev.net/blog/2014/java-scala-divided-we-fail/#_analyzing_bottlenecks Java vs. Scala]
# [http://www.cs.uku.fi/~mnykanen/FOH/lectures1.pdf Salient Features of Functional Programming]
# [https://www.cs.rpi.edu/research/pdf/10-04.pdf Comparison of Object-oriented and Functional Programming]

CSC/ECE 517 Fall 2014/ch1a 9 aa

2014-09-25T21:08:27Z

Aashetty: /* Pattern Matchinghttp://c2.com/cgi/wiki?PatternMatching */

= 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 [http://en.wikipedia.org/wiki/Declarative_programming declarative programming] paradigm. One key feature in a functional language is the concept of [http://en.wikipedia.org/wiki/First-class_function 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 [http://en.wikipedia.org/wiki/Imperative_programming 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.<ref>http://en.wikipedia.org/wiki/Functional_programming</ref>
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 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<ref>http://en.wikibooks.org/wiki/Computer_Programming/Functional_programming</ref> =
===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.

<pre>
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);
</pre>

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<ref>http://www.haskell.org/haskellwiki/Functional_programming</ref>===
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. [http://en.wikipedia.org/wiki/Lazy_evaluation 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:
<pre>
String s1 = somewhatLongOperation1();
String s2 = somewhatLongOperation2();
String s3 = concatenate(s1, s2);
</pre>

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===
[http://www.cs.utah.edu/~germain/PPS/Topics/recursion.html Recursion] is heavily used in functional programming as it is the canonical and often the only way to iterate. Functional language implementations will often include tail call optimization to ensure that heavy recursion does not consume excessive memory.

===Pattern Matching<ref>http://c2.com/cgi/wiki?PatternMatching</ref>===
In the context of pure functional languages, [http://en.wikipedia.org/wiki/Pattern_matching Pattern Matching] is a dispatch mechanism: choosing which variant of a function is the correct one to call. Example:
<pre>
factorial(0) ::= 1
factorial(n) ::= n * factorial(n-1)
</pre>
The function has been given two definitions. Which is used for dispatch when a call is made will depend, in this case, on whether the actual parameter pattern matches 0 or not. The matching is not limited to constants; in general, functions have a [http://en.wikipedia.org/wiki/Type_signature TypeSignature] used for matching. [http://en.wikipedia.org/wiki/Currying Currying] is integrated into this mechanism.
1.Pattern matching is the compiler's ability to compare both the form and the content of two expressions. It is used in two ways:
All or part of a data structure may be assigned to one or several variables in a single expression.
2.A function may have several definitions (clauses), according to the form and/or content of its arguments. This second use is usually combined with the first to initialize the variables that will be used in the clause.
In both these uses, a pattern match has the additional benefit of making an assertion about the form and/or content of a variable.

===Closures===
Passing functions around in impure languages is a little bit different than doing it in the confines of lambda calculus and requires support for an interesting feature often referred to as [https://www.princeton.edu/~achaney/tmve/wiki100k/docs/Closure_(computer_science).html lexical closure]. Let's take a look at some sample code. Remember, in this case variables aren't final and functions can refer to variables outside of their scope:
<pre>
Function makePowerFn(int power) {
int powerFn(int base) {
return pow(base, power);
}
return powerFn;
}
Function square = makePowerFn(2);
square(3); // returns 9
</pre>

The function makePowerFn returns a function that takes a single argument and raises it to a certain power. What happens when we try to evaluate square(3)? The variable power isn't anywhere in scope of powerFn because makePowerFn has returned and its stack is long gone. How can square work, then? The language must, somehow, store the value of power somewhere for square to work. What if we create another function, cube, that raises something to the third power? The runtime must now store two copies of power, one for each function we generated using makePowerFn. The phenomenon of storing these values is called a closure.

= Comparison between Functional Programming and OOP <ref>http://wiki.expertiza.ncsu.edu/index.php/CSC/ECE_517_Fall_2013/ch1_1w25_aras</ref> =
Let us compare both the programming paradigms with respect to several disctinction attributes.
{| class="wikitable" border="1"
! scope="col" | Point of Comparison
! scope="col" | Functional Languages
! scope="col" | Object-Oriented Languages
|-
|
* Primary focus
| Functional programming emphasizes on functions that produce results which depend only on their inputs and not on the program state - i.e. pure mathematial functions. || Focus on identifying and''' representing the problem in terms of an 'object'''' which has its own data, sub-routines and state. Different objects in the problem interact by sending messages to each other and thus result in change in its internal state. The final state and values of the objects refer to the solution. It is '''data-centric'''.
|-
|
* Problem Solving Approach
| Primarily''' Top-down''' design || '''Identification and design of necessary objects'''. Close to being 'better models of the way the world works'.
|-
|
* Program Flow
| '''Often sequential''' with program having single point of entry and exit. || '''Complex''' program flow. Can sometimes depend on the internal state of the objects.
|-
|
* Modularity
| '''Limited modularity'''. Program is divided into modules or per say procedures independent of each other but are constrained due to uniqueness to that particular problem. || '''Extremely modular''' due to the presence of objects which contain their own data and sub-routines.
|-
|
* Data Protection/Hiding
| '''No concept of data-hiding'''. Variables local to one method cannot be accessed by other method. But, Global variables can be accessed anywhere within the program. || One of the main fundamentals of O-O languages.''' Access specifiers''' like 'public', 'private' and 'protected' dictate the rules of data-hiding. Data which is private is confined to one object and cannot be directly changed by any other method except its own. This places the responsibility of managing data with the object itself This is called as ownership. Thus, data can be accessed ( read/write/modified )''' only''' through the object's own interfaces.
|-
|
* Ease of Understanding
|'''Smaller programs''' are '''easy to understand''' but as the program increases in size; understanding the code becomes more and more difficult. || '''Easy to understand''' due to its real world-like design and flow.
|-
|
* Reuse of Code
| '''Very Limited or no''' code re-usability. ||'''Highly re-usable code''' as the code developed can be easily modified or extended to suit a problem's need.
|-
|
* Support for declaring new data types/classes
|'''Difficult '''due to limited in-built functionality. || '''Easily possible''' due to the concept of classes. Generic classes can be built as per the required specifications.
|-
|
* Efficiency
| '''Efficient''' for solving '''small''' problems. || '''Efficient''' for solving '''large problems''' which have a complex structure and require complex data-types, abstraction and data-security.
|-
|
* Maintenance
| Maintenance is''' easy for smaller programs''' but can consume''' a-lot of effort for larger program''' size as it requires the programmer to know and understand the dependencies of every module in the program. This makes it difficult to debug and test the program. ||'''Extremely simple''' as O-O languages aim for high modularity. Secondly, programmer is not concerned with the details of how the data is stored and represented. Thirdly, they also tend to keep low coupling which makes it easy to debug and test different modules in the program.
|-
|
* Extensibility
| '''Less Extensible''' as modules developed need to be re-organised and re-structured heavily in order to meet different needs. || '''High extensibility''' is one of the most important advantages of OOP. Code can be easily modified and 'plugged-in' to a different program. Methods can be exteneded due to many properties such as polymorphism, inheritance and support for multiple inheritance through interfaces.
|-
|
* Flexibility
| '''Less flexible.''' Sometimes, certain problems do not fit into the 'top-down design' approach. || '''High flexibility.''' The modelling of problems into world-like objects makes it easy to solve any practical problem.
|-
|
* Examples
| [http://en.wikipedia.org/wiki/Haskell_%28programming_language%29 Haskell], [http://en.wikipedia.org/wiki/Scala_%28programming_language%29 Scala], [http://en.wikipedia.org/wiki/Erlang_%28programming_language%29 Erlang] || [http://en.wikipedia.org/wiki/C%2B%2B C++], [http://en.wikipedia.org/wiki/Java_(programming_language) Java], [http://en.wikipedia.org/wiki/Ruby_(programming_language) Ruby], [http://en.wikipedia.org/wiki/Python_(programming_language) Python].
|}

= Scala : An overview <ref>http://docs.scala-lang.org/tutorials/scala-for-java-programmers.html</ref>=
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.
<pre>
object HelloWorld
{
def main(args: Array[String])
{
println("Hello, world!")
}
}
</pre>
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 <ref>http://www.scala-lang.org/old/node/104</ref>=
===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 <ref>http://www.codecommit.com/blog/scala/scala-for-java-refugees-part-3</ref>=
===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 and return types. Scala does allow for different visibilities on not just methods, but any members.
For example:
<pre>
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)
}
}
</pre>

Scala provides the 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:
<pre>
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)
</pre>

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

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

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

===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:
<pre>
list map { x => sqrt(x) }

can be written more concisely as

list map { sqrt(_) }
</pre>

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

===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:
<pre>
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;
}
}
</pre>

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:

<pre>
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
}
}
</pre>
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.

<pre>

trait Book
{
def title:String
def title_=(n:String):Unit

def computePrice = title.length * 10
}

</pre>

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 our CollegeStudent example in Scala without redundancy or fear of paradox:
<pre>
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 {
// ...
}

</pre>

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

= References =
<references />

= Further reading =
# [http://vimeo.com/20293743 Video to learn about Scala]
# [http://docs.scala-lang.org/tutorials/ Scala Documentation]
# [http://shipilev.net/blog/2014/java-scala-divided-we-fail/#_analyzing_bottlenecks Java vs. Scala]
# [http://www.cs.uku.fi/~mnykanen/FOH/lectures1.pdf Salient Features of Functional Programming]
# [https://www.cs.rpi.edu/research/pdf/10-04.pdf Comparison of Object-oriented and Functional Programming]

CSC/ECE 517 Fall 2014/ch1a 9 aa

2014-09-25T20:47:28Z

Aashetty: /* Closures */

= 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 [http://en.wikipedia.org/wiki/Declarative_programming declarative programming] paradigm. One key feature in a functional language is the concept of [http://en.wikipedia.org/wiki/First-class_function 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 [http://en.wikipedia.org/wiki/Imperative_programming 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.<ref>http://en.wikipedia.org/wiki/Functional_programming</ref>
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 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<ref>http://en.wikibooks.org/wiki/Computer_Programming/Functional_programming</ref> =
===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.

<pre>
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);
</pre>

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<ref>http://www.haskell.org/haskellwiki/Functional_programming</ref>===
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. [http://en.wikipedia.org/wiki/Lazy_evaluation 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:
<pre>
String s1 = somewhatLongOperation1();
String s2 = somewhatLongOperation2();
String s3 = concatenate(s1, s2);
</pre>

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===
[http://www.cs.utah.edu/~germain/PPS/Topics/recursion.html Recursion] is heavily used in functional programming as it is the canonical and often the only way to iterate. Functional language implementations will often include tail call optimization to ensure that heavy recursion does not consume excessive memory.

===Pattern Matching<ref>http://c2.com/cgi/wiki?PatternMatching</ref>===
In the context of pure functional languages, Pattern Matching is a dispatch mechanism: choosing which variant of a function is the correct one to call. Example:
<pre>
factorial(0) ::= 1
factorial(n) ::= n * factorial(n-1)
</pre>
The function has been given two definitions. Which is used for dispatch when a call is made will depend, in this case, on whether the actual parameter pattern matches 0 or not. The matching is not limited to constants; in general, functions have a [http://en.wikipedia.org/wiki/Type_signature TypeSignature] used for matching. [http://en.wikipedia.org/wiki/Currying Currying] is integrated into this mechanism.
1.Pattern matching is the compiler's ability to compare both the form and the content of two expressions. It is used in two ways:
All or part of a data structure may be assigned to one or several variables in a single expression.
2.A function may have several definitions (clauses), according to the form and/or content of its arguments. This second use is usually combined with the first to initialize the variables that will be used in the clause.
In both these uses, a pattern match has the additional benefit of making an assertion about the form and/or content of a variable.

===Closures===
Passing functions around in impure languages is a little bit different than doing it in the confines of lambda calculus and requires support for an interesting feature often referred to as [https://www.princeton.edu/~achaney/tmve/wiki100k/docs/Closure_(computer_science).html lexical closure]. Let's take a look at some sample code. Remember, in this case variables aren't final and functions can refer to variables outside of their scope:
<pre>
Function makePowerFn(int power) {
int powerFn(int base) {
return pow(base, power);
}
return powerFn;
}
Function square = makePowerFn(2);
square(3); // returns 9
</pre>

The function makePowerFn returns a function that takes a single argument and raises it to a certain power. What happens when we try to evaluate square(3)? The variable power isn't anywhere in scope of powerFn because makePowerFn has returned and its stack is long gone. How can square work, then? The language must, somehow, store the value of power somewhere for square to work. What if we create another function, cube, that raises something to the third power? The runtime must now store two copies of power, one for each function we generated using makePowerFn. The phenomenon of storing these values is called a closure.

= Comparison between Functional Programming and OOP <ref>http://wiki.expertiza.ncsu.edu/index.php/CSC/ECE_517_Fall_2013/ch1_1w25_aras</ref> =
Let us compare both the programming paradigms with respect to several disctinction attributes.
{| class="wikitable" border="1"
! scope="col" | Point of Comparison
! scope="col" | Functional Languages
! scope="col" | Object-Oriented Languages
|-
|
* Primary focus
| Functional programming emphasizes on functions that produce results which depend only on their inputs and not on the program state - i.e. pure mathematial functions. || Focus on identifying and''' representing the problem in terms of an 'object'''' which has its own data, sub-routines and state. Different objects in the problem interact by sending messages to each other and thus result in change in its internal state. The final state and values of the objects refer to the solution. It is '''data-centric'''.
|-
|
* Problem Solving Approach
| Primarily''' Top-down''' design || '''Identification and design of necessary objects'''. Close to being 'better models of the way the world works'.
|-
|
* Program Flow
| '''Often sequential''' with program having single point of entry and exit. || '''Complex''' program flow. Can sometimes depend on the internal state of the objects.
|-
|
* Modularity
| '''Limited modularity'''. Program is divided into modules or per say procedures independent of each other but are constrained due to uniqueness to that particular problem. || '''Extremely modular''' due to the presence of objects which contain their own data and sub-routines.
|-
|
* Data Protection/Hiding
| '''No concept of data-hiding'''. Variables local to one method cannot be accessed by other method. But, Global variables can be accessed anywhere within the program. || One of the main fundamentals of O-O languages.''' Access specifiers''' like 'public', 'private' and 'protected' dictate the rules of data-hiding. Data which is private is confined to one object and cannot be directly changed by any other method except its own. This places the responsibility of managing data with the object itself This is called as ownership. Thus, data can be accessed ( read/write/modified )''' only''' through the object's own interfaces.
|-
|
* Ease of Understanding
|'''Smaller programs''' are '''easy to understand''' but as the program increases in size; understanding the code becomes more and more difficult. || '''Easy to understand''' due to its real world-like design and flow.
|-
|
* Reuse of Code
| '''Very Limited or no''' code re-usability. ||'''Highly re-usable code''' as the code developed can be easily modified or extended to suit a problem's need.
|-
|
* Support for declaring new data types/classes
|'''Difficult '''due to limited in-built functionality. || '''Easily possible''' due to the concept of classes. Generic classes can be built as per the required specifications.
|-
|
* Efficiency
| '''Efficient''' for solving '''small''' problems. || '''Efficient''' for solving '''large problems''' which have a complex structure and require complex data-types, abstraction and data-security.
|-
|
* Maintenance
| Maintenance is''' easy for smaller programs''' but can consume''' a-lot of effort for larger program''' size as it requires the programmer to know and understand the dependencies of every module in the program. This makes it difficult to debug and test the program. ||'''Extremely simple''' as O-O languages aim for high modularity. Secondly, programmer is not concerned with the details of how the data is stored and represented. Thirdly, they also tend to keep low coupling which makes it easy to debug and test different modules in the program.
|-
|
* Extensibility
| '''Less Extensible''' as modules developed need to be re-organised and re-structured heavily in order to meet different needs. || '''High extensibility''' is one of the most important advantages of OOP. Code can be easily modified and 'plugged-in' to a different program. Methods can be exteneded due to many properties such as polymorphism, inheritance and support for multiple inheritance through interfaces.
|-
|
* Flexibility
| '''Less flexible.''' Sometimes, certain problems do not fit into the 'top-down design' approach. || '''High flexibility.''' The modelling of problems into world-like objects makes it easy to solve any practical problem.
|-
|
* Examples
| [http://en.wikipedia.org/wiki/Haskell_%28programming_language%29 Haskell], [http://en.wikipedia.org/wiki/Scala_%28programming_language%29 Scala], [http://en.wikipedia.org/wiki/Erlang_%28programming_language%29 Erlang] || [http://en.wikipedia.org/wiki/C%2B%2B C++], [http://en.wikipedia.org/wiki/Java_(programming_language) Java], [http://en.wikipedia.org/wiki/Ruby_(programming_language) Ruby], [http://en.wikipedia.org/wiki/Python_(programming_language) Python].
|}

= Scala : An overview <ref>http://docs.scala-lang.org/tutorials/scala-for-java-programmers.html</ref>=
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.
<pre>
object HelloWorld
{
def main(args: Array[String])
{
println("Hello, world!")
}
}
</pre>
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 <ref>http://www.scala-lang.org/old/node/104</ref>=
===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 <ref>http://www.codecommit.com/blog/scala/scala-for-java-refugees-part-3</ref>=
===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 and return types. Scala does allow for different visibilities on not just methods, but any members.
For example:
<pre>
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)
}
}
</pre>

Scala provides the 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:
<pre>
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)
</pre>

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

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

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

===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:
<pre>
list map { x => sqrt(x) }

can be written more concisely as

list map { sqrt(_) }
</pre>

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

===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:
<pre>
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;
}
}
</pre>

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:

<pre>
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
}
}
</pre>
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.

<pre>

trait Book
{
def title:String
def title_=(n:String):Unit

def computePrice = title.length * 10
}

</pre>

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 our CollegeStudent example in Scala without redundancy or fear of paradox:
<pre>
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 {
// ...
}

</pre>

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

= References =
<references />

= Further reading =
# [http://vimeo.com/20293743 Video to learn about Scala]
# [http://docs.scala-lang.org/tutorials/ Scala Documentation]
# [http://shipilev.net/blog/2014/java-scala-divided-we-fail/#_analyzing_bottlenecks Java vs. Scala]
# [http://www.cs.uku.fi/~mnykanen/FOH/lectures1.pdf Salient Features of Functional Programming]
# [https://www.cs.rpi.edu/research/pdf/10-04.pdf Comparison of Object-oriented and Functional Programming]

CSC/ECE 517 Fall 2014/ch1a 9 aa

2014-09-25T20:46:34Z

Aashetty: /* Recursion */

= 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 [http://en.wikipedia.org/wiki/Declarative_programming declarative programming] paradigm. One key feature in a functional language is the concept of [http://en.wikipedia.org/wiki/First-class_function 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 [http://en.wikipedia.org/wiki/Imperative_programming 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.<ref>http://en.wikipedia.org/wiki/Functional_programming</ref>
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 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<ref>http://en.wikibooks.org/wiki/Computer_Programming/Functional_programming</ref> =
===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.

<pre>
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);
</pre>

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<ref>http://www.haskell.org/haskellwiki/Functional_programming</ref>===
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. [http://en.wikipedia.org/wiki/Lazy_evaluation 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:
<pre>
String s1 = somewhatLongOperation1();
String s2 = somewhatLongOperation2();
String s3 = concatenate(s1, s2);
</pre>

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===
[http://www.cs.utah.edu/~germain/PPS/Topics/recursion.html Recursion] is heavily used in functional programming as it is the canonical and often the only way to iterate. Functional language implementations will often include tail call optimization to ensure that heavy recursion does not consume excessive memory.

===Pattern Matching<ref>http://c2.com/cgi/wiki?PatternMatching</ref>===
In the context of pure functional languages, Pattern Matching is a dispatch mechanism: choosing which variant of a function is the correct one to call. Example:
<pre>
factorial(0) ::= 1
factorial(n) ::= n * factorial(n-1)
</pre>
The function has been given two definitions. Which is used for dispatch when a call is made will depend, in this case, on whether the actual parameter pattern matches 0 or not. The matching is not limited to constants; in general, functions have a [http://en.wikipedia.org/wiki/Type_signature TypeSignature] used for matching. [http://en.wikipedia.org/wiki/Currying Currying] is integrated into this mechanism.
1.Pattern matching is the compiler's ability to compare both the form and the content of two expressions. It is used in two ways:
All or part of a data structure may be assigned to one or several variables in a single expression.
2.A function may have several definitions (clauses), according to the form and/or content of its arguments. This second use is usually combined with the first to initialize the variables that will be used in the clause.
In both these uses, a pattern match has the additional benefit of making an assertion about the form and/or content of a variable.

===Closures===
Passing functions around in impure languages is a little bit different than doing it in the confines of lambda calculus and requires support for an interesting feature often referred to as lexical closure. Let's take a look at some sample code. Remember, in this case variables aren't final and functions can refer to variables outside of their scope:
<pre>
Function makePowerFn(int power) {
int powerFn(int base) {
return pow(base, power);
}
return powerFn;
}
Function square = makePowerFn(2);
square(3); // returns 9
</pre>

The function makePowerFn returns a function that takes a single argument and raises it to a certain power. What happens when we try to evaluate square(3)? The variable power isn't anywhere in scope of powerFn because makePowerFn has returned and its stack is long gone. How can square work, then? The language must, somehow, store the value of power somewhere for square to work. What if we create another function, cube, that raises something to the third power? The runtime must now store two copies of power, one for each function we generated using makePowerFn. The phenomenon of storing these values is called a closure.

= Comparison between Functional Programming and OOP <ref>http://wiki.expertiza.ncsu.edu/index.php/CSC/ECE_517_Fall_2013/ch1_1w25_aras</ref> =
Let us compare both the programming paradigms with respect to several disctinction attributes.
{| class="wikitable" border="1"
! scope="col" | Point of Comparison
! scope="col" | Functional Languages
! scope="col" | Object-Oriented Languages
|-
|
* Primary focus
| Functional programming emphasizes on functions that produce results which depend only on their inputs and not on the program state - i.e. pure mathematial functions. || Focus on identifying and''' representing the problem in terms of an 'object'''' which has its own data, sub-routines and state. Different objects in the problem interact by sending messages to each other and thus result in change in its internal state. The final state and values of the objects refer to the solution. It is '''data-centric'''.
|-
|
* Problem Solving Approach
| Primarily''' Top-down''' design || '''Identification and design of necessary objects'''. Close to being 'better models of the way the world works'.
|-
|
* Program Flow
| '''Often sequential''' with program having single point of entry and exit. || '''Complex''' program flow. Can sometimes depend on the internal state of the objects.
|-
|
* Modularity
| '''Limited modularity'''. Program is divided into modules or per say procedures independent of each other but are constrained due to uniqueness to that particular problem. || '''Extremely modular''' due to the presence of objects which contain their own data and sub-routines.
|-
|
* Data Protection/Hiding
| '''No concept of data-hiding'''. Variables local to one method cannot be accessed by other method. But, Global variables can be accessed anywhere within the program. || One of the main fundamentals of O-O languages.''' Access specifiers''' like 'public', 'private' and 'protected' dictate the rules of data-hiding. Data which is private is confined to one object and cannot be directly changed by any other method except its own. This places the responsibility of managing data with the object itself This is called as ownership. Thus, data can be accessed ( read/write/modified )''' only''' through the object's own interfaces.
|-
|
* Ease of Understanding
|'''Smaller programs''' are '''easy to understand''' but as the program increases in size; understanding the code becomes more and more difficult. || '''Easy to understand''' due to its real world-like design and flow.
|-
|
* Reuse of Code
| '''Very Limited or no''' code re-usability. ||'''Highly re-usable code''' as the code developed can be easily modified or extended to suit a problem's need.
|-
|
* Support for declaring new data types/classes
|'''Difficult '''due to limited in-built functionality. || '''Easily possible''' due to the concept of classes. Generic classes can be built as per the required specifications.
|-
|
* Efficiency
| '''Efficient''' for solving '''small''' problems. || '''Efficient''' for solving '''large problems''' which have a complex structure and require complex data-types, abstraction and data-security.
|-
|
* Maintenance
| Maintenance is''' easy for smaller programs''' but can consume''' a-lot of effort for larger program''' size as it requires the programmer to know and understand the dependencies of every module in the program. This makes it difficult to debug and test the program. ||'''Extremely simple''' as O-O languages aim for high modularity. Secondly, programmer is not concerned with the details of how the data is stored and represented. Thirdly, they also tend to keep low coupling which makes it easy to debug and test different modules in the program.
|-
|
* Extensibility
| '''Less Extensible''' as modules developed need to be re-organised and re-structured heavily in order to meet different needs. || '''High extensibility''' is one of the most important advantages of OOP. Code can be easily modified and 'plugged-in' to a different program. Methods can be exteneded due to many properties such as polymorphism, inheritance and support for multiple inheritance through interfaces.
|-
|
* Flexibility
| '''Less flexible.''' Sometimes, certain problems do not fit into the 'top-down design' approach. || '''High flexibility.''' The modelling of problems into world-like objects makes it easy to solve any practical problem.
|-
|
* Examples
| [http://en.wikipedia.org/wiki/Haskell_%28programming_language%29 Haskell], [http://en.wikipedia.org/wiki/Scala_%28programming_language%29 Scala], [http://en.wikipedia.org/wiki/Erlang_%28programming_language%29 Erlang] || [http://en.wikipedia.org/wiki/C%2B%2B C++], [http://en.wikipedia.org/wiki/Java_(programming_language) Java], [http://en.wikipedia.org/wiki/Ruby_(programming_language) Ruby], [http://en.wikipedia.org/wiki/Python_(programming_language) Python].
|}

= Scala : An overview <ref>http://docs.scala-lang.org/tutorials/scala-for-java-programmers.html</ref>=
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.
<pre>
object HelloWorld
{
def main(args: Array[String])
{
println("Hello, world!")
}
}
</pre>
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 <ref>http://www.scala-lang.org/old/node/104</ref>=
===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 <ref>http://www.codecommit.com/blog/scala/scala-for-java-refugees-part-3</ref>=
===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 and return types. Scala does allow for different visibilities on not just methods, but any members.
For example:
<pre>
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)
}
}
</pre>

Scala provides the 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:
<pre>
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)
</pre>

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

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

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

===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:
<pre>
list map { x => sqrt(x) }

can be written more concisely as

list map { sqrt(_) }
</pre>

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

===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:
<pre>
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;
}
}
</pre>

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:

<pre>
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
}
}
</pre>
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.

<pre>

trait Book
{
def title:String
def title_=(n:String):Unit

def computePrice = title.length * 10
}

</pre>

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 our CollegeStudent example in Scala without redundancy or fear of paradox:
<pre>
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 {
// ...
}

</pre>

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

= References =
<references />

= Further reading =
# [http://vimeo.com/20293743 Video to learn about Scala]
# [http://docs.scala-lang.org/tutorials/ Scala Documentation]
# [http://shipilev.net/blog/2014/java-scala-divided-we-fail/#_analyzing_bottlenecks Java vs. Scala]
# [http://www.cs.uku.fi/~mnykanen/FOH/lectures1.pdf Salient Features of Functional Programming]
# [https://www.cs.rpi.edu/research/pdf/10-04.pdf Comparison of Object-oriented and Functional Programming]