[Big Data] Hadoop Core

Hadoop in Layman's term
Lets say you have file that contains name of all the people who lives in your apartment complex. You want to see how many people has same name as yours. You write a program that reads the file and outputs how many people has same name as yours. Now, lets say you want to know how many people in your city has same name as yours. The data is too big to fit in a single computer. So you get some 20 computers and connect them which forms a cluster. You install Hadoop on the cluster. Now, you start writing name of the people of your city in a file in Hadoop File System (HDFS) which in turn starts breaking your data into small chunks and writes into your 20 computers. You keep appending the file until you have written all the names of your city. Now, you submit the program that you previously have written for a single computer to find the count of name match on Hadoop. Hadoop takes your program, and asks your 20 computers to run the program parallelly. Hadoop then asks your 20 computers to aggregate and provide you the result.

Some terms:
node: a small computer capable of storing data and do processing on the data
cluster: combination of lots of node

Hadoop provides 2 functionalities.
0. Distributed fault tolerant data storage (hdfs)
1. Batch processing on stored data (map-reduce)

# HDFS
hdfs is a Unix like distributed file system. It splits large files into small blocks and stores them in different nodes. hdfs stores each block by default 3 times in 3 separate nodes to provide safety of the data in case of a node failure.

## Services
0. many data nodes: these service is run on those nodes that stores data. send heart beat and block information to master node. clients connects to data nodes to read/write data.
1. master name node: stores meta data about which data block is stored in which data node. guides client to write/read data to/from appropriate data node
2. check point node: creates check point for the name node. this is not a hot back up for master name node.

## How hdfs works
Write
0. client connect to name node and asks which data nodes to write data to
1. name node gives data node address to client
2. client connects to data nodes and writes data to data nodes
3. data nodes takes action to replicate data to other data nodes guided by name node

Read
0. client connects to name node and asks which data nodes to read from
1. name node gives data node addresses
2. client connects to data nodes and read data
3. in case of a datanode failure, client reads the data block from another data node guided by name node


# MapReduce
Clients want to process data stored in hdfs. A client submits a "Job" to MapReduce that MapReduce runs across diffrent nodes in the cluster.

## Services
0. Job tracker: master service to monitor jobs. A job is ran as many tasks in several nodes distributedly. retries failed task attempts. Schedules incoming jobs from different clients.
1. Task tracker: runs on the same physical machine as the data node. several tasks executed in a distributed system accomplishes the Job that a client submits. A task has one or more attempts. Sends heartbeat and task status to job tracker. It runs on its own JVM on a datanode.

## How Mapreduce works
0. Clients submits job to job tracker
1. Job tracker assigns tasks to task trackers that are close to the data blocks.
2. Task trackers executes tasks. and writes the result to hdfs with replication
3. if a task tracker fails, job tracker assigns the task to another task tracker


# YARN
Abstract framework for distributed processing. MapReduce is a concrete YARN application. It divides duty of the Job Tracker into Application master, Resource manager. Task tracker acts as a node manager, which have "Containers" on which a map or reduce task can be executed. Number of containers on a node is configurable.


## Map Reduce
Data processing a is done in 2 phases.
0. Map phase: apply map function on input key value pairs to generate intermediate key value pairs. group intermediate key value pairs by intermediate keys. each group will contain one key and one or more values.
Components used during map phase:
a. InputFormat: Reads file line by line.
b. RecordReader: Reads input key, value pair from a line using InputFormat.
c. Mapper: Contains map function to apply on input key, value pairs and produces intermediate key, value pairs.
d. Combiner: Performs a local reduction on intermediate key, value pair.
e. Partitioner: Decides which intermediate key, value should go to which partition.

1. Reduce phase: apply reduce function on grouped intermediate key value pairs.
Components of reduce phase
a. Shuffle: Decides on which partition this reducer should operate on.
b. Sort: Sorts data on a single partition by key.
c. Reducer: given an intermediate key and a set of values, performs reduce operation and produces output key value pair.
d. RecordWriter: used to store one key, value pair.
f. OutputFormat: creates the record writer and writes content of the RecordWriter.

Component used by both phase:
WritableInterface: specifies how to read/write data to/from a file. Integer data is written as IntWritable, read as IntWritable.

Misc Notes
0. A map-reduce job can contain only one mapper job and only one reducer job. So a job such as word counter can be created. To create MR jobs pipeline, framework such as Crunch can be used.
1. You can append data on a hdfs file. There is no way to modify existing content of a file stored in HDFS.
1. Hadoop Streaming: Executing shell, python etc. script as jobs. Example:
hadoop jar hadoop-streaming.jar -input input -output outputdir
-mapper org.apache.hadoop.mapreduce.Mapper -reduce /bin/wc



Reference:
0. hadoop just the basics - slides
1. hadoop just the basics - youtube video

[Book Take Away] The Zen Programmer

Buddha
Siddhartha Gautama, A prince from Nepal born 500 years before christ. At age of 26, he learns about death, distress and disease. He left his house to find the remedy of this basic problems. In his journey, he understood four noble truth that expresses reality of pain. He found eightfold path that would minimize pain of a human-being. He is known as the first "Buddha" which means awakened.

# Buddhism
Teachings of the first Buddha. In Buddhism there is no God.

## Four noble truth
0. There exists dissatisfaction.
1. Root cause of dissatisfaction is desire, hatred and wrong thoughts.
2. If the root causes are gone, pain will seize.
3. Eight-fold path helps eliminate root cause.

## Eight-fold path to nirvana
Eight-fold paths are not commandments. These can be considered more as "Best Practices".

0. Right view: Understand four noble truth. See things without prejudice. There is no correct or wrong view. Right view can be considered as absence of any view.
1. Right intention: Right intention means acting without any desire. Right intention is absence of any intention.
2. Right speech: Right speech is no speech or amount of speech that is absolutely necessary.
3. Right action: Right action is no action or action that have minimum possible impact.
4. Right livelihood: Right livelihood is no livelihood or a livelihood with minimum possible impact to surroundings.
5. Right effort: An effort where mind(thought) is constantly monitored.
6. Right mindfulness: Leading life with full attention on body and mind.
7. Right concentration: Keeping balance between chaos and tranquility of mind.

## Zen Buddhism
A sect of Buddhism. Not thinking about anything is Zen. Once this mind-clearing technique is mastered, everything such as walking, standing, sitting or eating becomes Zen practice.

Some Zen terms:
### Hell: Situation a person creates for oneself and surroundings through wrong thoughts and action.
### Ghost: The thoughts that keep desiring good looking sexual partner or comfortable belongings.
Zen does not give a person something. Zen does not make one happy. Zen does not tell a person do something good. Zen is about clearing unnecessary stuffs, keeping mind and dwelling empty. Zen acknowledge there is by default pain and dissatisfaction. Zen teaches to minimize pain.

Why Zen programming?
A programmers day is a combination of the following
0. overtime
1. ambitious requirements
2. wrong team
3. high expectation
4. not dealing with life
5. motivation by threat
6. changing requirement
7. greed
8. comparison with others
9. burn out
so on and so forth. Dealing with so many chaos is not easy. A programmer will need a way to deal with all these stresses. Zen can help her with these problems.

The nature of mind
# Chaos and rational thinking: Chaotic thoughts increases dissatisfaction. Rational thinking sees everything as the same and decreases desire. Chaos in mind needs to kept under control by minimizing chaos making actions and thoughts. Chaotic thinking is sometimes good for creativity yet it needs to be under check.

# Associative thinking: A process of mind's drifting with a hint. Example: you think about apple, next your mind thinks automatically about mac book and Steve jobs.

Zen Practices
Ki:  (Breath and vitality) Breathing mindfully.

Kizen: Keeping chaos and rational thinking in balance and being mindful about associative thinking.

Task breakdown: A larger task needs to be broken on smaller chunks.

Reflection: Every once on a while focus on what you are thinking and what you are doing.

Focus time: Set aside a time slot for uninterrupted work.

Email check: Set aside a less productive hours for non-pressing email.

Chair relaxation: Every once in a while, while sitting on the chair, focus on breathing.

Walking relaxation: Walking while being fully aware of the surrounding.

Sleep: If you are tired take a nap. Go to your car if necessary.

Work without holiday: If you work mindfully, following the above practice, everyday you'll feel you are in holiday.

Drink Tea: Be mindful about every step of making a cup of tea. Observe every sip. There should not be any other thoughts other than you and your cup of tea.

Clean: Keep your desk clean. There will be less things to get distracted with.

Defeat mind monkey: Do not roam around websites. Clear desk mindfully. Mindful work helps defeat mind monkey.

Take break: Take a real holiday. Stay away from computers. In work you focus more on mind. Focus more on body when in holiday.

Todo list: Make a weekly list of tasks. It is important how many tasks you accomplished rather than how much time you put (Saif disagrees with this).

Two minute rule: If you are in middle of something and another task comes from another source. If the task is non-pressing and can be done in 2 minutes, switch from original task, otherwise write the task down in your todo list and keep doing the original task.

Pomodoro principle: Break your task in 25 minutes slots(1 Pomodoro). Take 5 minutes break after each Pomodoro. After 5 consecutive Pomodoros, take 30 minutes break.

Chain: Take a calendar. Put a X mark on the calendar as you have done the work you want to do regularly. Try to make a chain of Xs. Try your best not to break the chain..

Personalized Kanban: Use your wall and sticky notes to make your own personalized Kanban. In one section, put works you want to do. In another section put the works that are in progress. Don't clutter in progress with too many tasks. (More than four are too many).

Don't become an extremist: Keep a healthy balance of work and rest.

Frequently made complains:
0. Others don't treat me well: There will always be someone who treats nice, there will be someone who does not treat others so nice. Accept it.

1. I deserve it: What we think we deserve (such as costly phones) endup in earth's cheapest dumping ground(poor countries of Africa). Beware of what you think you deserve.

2. I had bad childhood: Many people probably had worse childhood than you had, yet they were able to go through it and did what they wanted to do in life. So bad childhood should not be a complain once you are aware of it. Stop leaving in past, act properly now.

3. I know it better: We don't know what will bring good or bad for us. Most of the time everything ends up being the same anyway.

Things to remember:
0. It's your life: No matter what happens to you, it is still your life. Don't forget that every day is a good day.

1. No ego: Some attributes that we think represents us, such as good look, attractive figure, knowledge, money etc are actually pretty volatile. Attaching these things to self might cause more pain when these things go away.

2. Ego makes you do things: You keep doing those things that you think the world thinks of you.

3. Ego-less programming: You are not your work. Your work can be made better with the help of others feedback. Take reviews to your work constructively.

4. Shut up: Only speak up if you absolutely have to. Don't waste your collegue's time with unnecessary chit-chat.

Zen is hard work
Zen is done with body and mind. Do your daily chores with your body and mind.

Career: Sometimes your career path might take you to the path which might not be the best for you. Feel free to say no to such promotions.

Taking care of body is important: You will regret when you are old if you don't take care of your body today.

Learn: Everything changes. Don't stop the room for improvement and learning.

Beware of environment: Know what is in your surroundings and know how to connect the gaps through learning.

Theory needs practice: What you learn, you need to practice them.

Don't become job title addict.

Calm down: In order to see things clearly, you need to calm down.

Keep the beginner mindset: Always look at things through a beginner's eye. Don't have an experts mindset. Being an Expert means a lot of ego. Beware that you can be wrong have the beginner's mindset.

Work being aware: Know what is needed, what help is available, have some preplanning of work.

Karma:
  Good karma that does something good.
  Bad karma is something that does something bad.
  Karma always backfires, a good or bad karma might end up causing troubles and pains. So, strive on no karma.

Code karma: Good code karma is coding with praise in mind. Bad karma is coding without care. Strive to avoid both good and bad code karma. Code with being aware, do only the much that needs to be done.

Buddha Programmer
A person who maintains calm mood and clear sight is a Buddha programmer. She sees good things in her colleagues and speaks up about bad things. She does not look for followers or worshipers. She does not have desire for greatness. She practices for the sake of practice, works for the sake of work, nothing else.

On being a student
0. Listen, learn what your teacher wants to teach you.
1. Keep respect, do your research, come up with short concise and easy to understand question for your teacher.
2. Don't go after your teachers job.
3. If your teacher has some fault, talk with her first.
4. You must give loyalty, honesty and commitment as you are receiving valuable knowledge from your teacher.

On being a teacher
0. Give advice sparingly, only if asked for.
1. Remember people learn on their own, give them time to figure things out by themselves. Only help/answer if a question is asked.
2. If a student becomes less engaged or unwilling to learn from you, simply stop being her teacher, be a colleague.

Best student-teacher relationship is when a teacher becomes a student and student become a teacher.

Hungry ghost
The people who work for recognition, gets angry if something desired is not met.

# Ignorance
There will be hungry ghosts and it is necessary to ignore them.

# Confrontation
If there are only a few hungry ghosts in your team and you have at least the same authority as they have and there is no other option, confront. Know that things will worsen and chaos would increase.

# Manipulation
Identify hungry ghosts who are after you. Find what they want. Do your work and give them recognition.

Incompetence
It's hard to find a truly incompetent person. It's likely that the person is not in right position.

Zennify your project

# As a team leader: Take care of your team. Before someone gets to your teammate, they should get through you.

# Path of ruin: If leaders work with anger,they send anger to his associates. Which goes down the hierarchy. Eventually these falls to the family members at the bottom.

# It's never that bad: People work out of fear, forgetting being mindful of actual outcome of losing job. It's never that bad. A few months will be tough. This is a part of life, no one can expect sunshine and rainbow all the time. For sunshine, night is necessary; for rainbow rain necessary.

# Laugh when desperate: Stop taking yourself seriously. You are just a guy, working on some company. Take things easily. Mindfully try to understand the situation. Think of an action. Do as much as you can. Know failure occurs often, accept it and learn from it. Don't get desperate when failure occurs.

Ten rules of Zen programmer
0. Focus: Do one task with mindfulness at a time. When you are sleeping only sleep. When you are eating only eat. When you are thinking only think.
1. Keep mind clear: Need to clear mind of every temptation such as social network, emails, news and songs.
2. Keep beginner's mind: See things through a beginner's mind.
3. No ego: Remember you are not important. Do not get proud because you can do something well. Everyone is good at something. Do not attach an idea, a piece of code or appearance to "mine".
4. There is no career goal: Be aware of present moment. Mindfully learn, act, work, speak. Do not wait to go to a higher post. Do things with right intention and mindfulness now.
5. Shut up: Do not speak up if you do not have to. Do not waste others time.
6. Mindfulness, care and awareness: Listen to sign of your body. Take rest and breaks. Take care of your body. Remember, no work is beneath you. When some one gives you a task, do it with as much focus as possible. Block all thought of hatred towards the task.
7. There is no boss: If your authority is asking for tasks that is or might hurt your body(unhealthy overtimes), say no.
8. Do something else: Do a thing that is not related to computers.
9. There is nothing special: Remember there is nothing special, you are not special and you are not important. You are not special just because you can craft good code. No one cares who built the pyramid. Everything you posses today, you have to loose everything eventually. Everything will change, decay and go away. Remember this.

What now
Know that
  - Only you can help yourself.
  - Your feeling and thought shapes your reality.
  - You need time for silence and concentration.
  - Take ten minutes of silence and solitude everyday morning. Breathe the morning air.

Reference:
https://www.zenprogrammer.org/

Writing an interpreter for "X" in Racket

Interpreter vs Compiler

Let A, B and C are 3 programming languages. Then the Interpreter is a program written in B that executes a program written in A. The Compiler is a program written in B, which takes a program written in A and translates it to a program in C.

Example: add(2, 3) is a A statement. An interpreter would take this statement and produce 5. A compiler might produce a sequence of instructions such as,
mv r1, sp
addi sp, 1
mvi r1, 2
mv r2, sp
addi sp, 1
add r0, r1, r2
subi sp, 2

Goal: I have written an interpreter for language X in language Racket. The interpreter expects an AST built from a program written in A and evaluates the AST to a value.

Language X Description:
X is a functional language. It supports lexical scoping, higher order functions. Here are instruction types of the language X.

constants: 3
variables: var x = 3
if greater: ifgreater x y then e1 else e2
function: fun f(x) = x
lambda: \x => x
function call: f 5
let: let x = 3 in f(x) end
pair: (val1, val2)
empty pair: aunit
empty pair checker: isaunit?
fst: fst(p) produces val1
snd: snd(p) produces val2
add: add(v1, v2) produces v1+v2

A program in X is always an expression. Example program in X
let x = 3
 in let y = 3
   in let
    f = fn \t =>
         fn \s => add(s,t)
    in
     f x y
    end
   end
  end
 end

Designing Abstract Syntax Tree
We need to parse a program of X and represent the program using Racket data structructures and build an Abstract Syntax Tree.
Racket representation of X's constructs:
constant: (int 3)
variable: (var "x")
ifgreater: (ifgreater e1 e2 e3 e4) #if e1 and e2 evaluates to int and e1 > e2 then e3 gets evaluated else e4 gets evaluated.
function definition: (fun "f" "x" (var "x"))
lambda: (fun #f "x" (var "x")) ##lambda function, #f means the name field is false
function call: (call function arguments)
let: (mlet var-name e1 e2) # var-name is introduced in let, it's value is e1, var-name can be accessed from e2.
pair: (apair 2 3)
empty pair: (aunit)
empty pair checker: (isaunit e1) #evalutes e1, if it yields to (aunit) yields (int 1) else (int 0)
fst: (fst e)
snd: (snd e)
add: (add e1 e2)

Example AST:
(mlet "x" (int 3)
 (mlet "y" (int 3)
  (mlet "f" (fun #f "t"
        (fun #f "s" (add s t)))))
 (call (call (var "f") (var "x")) (var "y")))

Evaluation
Once we have AST we can proceed on evaluating it. We will need some more data structures and a few helper functions to do the evaluation.

Environment
To evaluate a program, the interpreter needs a table, that holds (binding-name, value) pairs. During evaluation of a X program, we can lookup this table to find value of a binding. We will call the table "environment".

Closure
To achieve lexical scoping, we will introduce closure. A closure is a pair (environment, function). Whenever a funtion is declared, we will take a snapshot of the current environment and produce a closure object with (environment, function).
Representation of closure (closure env function).

Values in Environment
Constant, pair, empty-pair and closure.

Evaluation Rules:
constant: (int 4) should return (int 4)
variable: If environemnt looks like
 ( ("x", (int 2)),
  ("f", (closure null (fun "f" "x" (add "x" (int 1)))))) then (var "x") would produce value (int 2).
apair: (apair e1 e2) would return (apair v1 v2) where e1 evaluates to v1 and e2 evalutes to v2.
aunit: (aunit) yields (aunit)
closure: (closure env f) yields (closure env f)

function: (fun "f" "x" (var "x")) yields to (closure env (fun "f" "x" (var "x"))) where current environment is env.
call:

ifgreater: (ifgreater e1 e2 e3 e4) if e1 => v1, e2 => v2  and v1 > v2 then yields to v3 => e3
     else yields to v4 where e4 => v4
isaunit: (isaunit e) yields (int 1) if e yields to (aunit)
           yields (int 0) otherwise
fst: (fst e) yields v1 if e yields to (v1, v2)
snd: (snd e) yields v2 if e yields to (v1, v2)
add: (add e1 e2) yields v3 where e1 yields v1, e2 yields v2, v3 = v1 + v2

call: (call (closure env f) e) evaluates to v where
 e=>v1
 new-env = (f.argument-name, v1) + env
 new-env => (f.fun-name, (closure env f)) + env if f is not a lambda
 evaluate(f.fun-expression, new-env) => v

mlet: (mlet var-name e1 e2) evulates to v where
 e1 => v1
 new-env = (var-name, v1) + env
 evaluate(e2, new-env) => v

Language Expansion using Macro:
Macro substitution is done by racket helper functions
(ifaunit e1 e2 e3) => (ifgreater isaunit(e1) (int 0) e2 e3)
(ifeq e1 e2 e3 e4) => (ifgreater e1 e2
            e3
            (ifgreater e2 e1 e3 e4))
(mlet* (list (var1 e2) (var2 e2)..) (en) ) : expands the following way
 (mlet var1 e2
  (mlet var2 e2
   (mlet var3 e3
    (en))))

(m-map m) takes a function m and returns a function that takes a list and returns a new list after applying m to each element of provided list and populating the new list with the value of function application:
 (fun "mapper-fn" "list"
  (apair (call (var "m") (fst (var "list"))) (call (var "mapper-fn") (snd (var "list"))))

Summary
The interpreter expects an AST built from parsing a X program and after macro substitution. We did not discuss parsing steps here. The interpreter maintains a table called environment as it goes through evaluating expressions in the AST.

Racket Syntax and more Functional Programming Concepts

Racket::
A minimal, strong and dynamically typed functional language. Racket uses lots of parenthesis to keep program structure proper instead of added keywords, that's why it is minimal syntax language.  It is dynamically typed because an invalid operation is not checked until the point of execution.

Expressions
a. let : creates local bindings.
Syntax: (let ([binding expression]...) (expression))
Example: (let ([x 1] [y 1] [z 2]) (add x y))

In let binding, the binding z does not have knowledge about local bindings x or y. The same can be said about the variable bindings x and y.
There are other bindings, let* and letrec that would extend the environment such that local binding x will have knowledge about other local bindings y or z.

b. if :
Syntax: (if e1 e2 e3)
If e1 evaluates to #f, e3 gets evaluted as the whole expression. For other cases, e2 gets evaluted. Notice that only e2 or e3 gets evaluated.
Example: (if (> a b) (+ a b) (- a b))

c. cond:
Syntax: (cond [e11 e12]  [e21 e22] [#t enn] )
If e11 returns #t then e12 gets evaluated. So on and so forth, if none of the eij gets evaluated then enn get evaluated as the resulting expression of the function.

d. lambda:
(lambda (param1 param2..) (expression))

e. begin:
(begin e1 e2 e3 ... en) a set of expressions e1, e2.. gets executed en is returned as result

Global bindings:
Syntax: (define binding expression)
Example: (define x 1) a global binding would extend current environment with the newly created binding. Binding works very much like letrec local binding, that means a new binding is accessible from a earlier binding. Which would refer that if duplicate bindings are allowed, an earlier binding would not know which one to use. To alleviate this, duplicate global bindings are not legal.

Variable declaration: (define x 1)
Function declaration: (define (add x y) (+ x y))

Function:
a. Currying
(define f
    (lambda (x)
         (lambda (y)
              (add x y))))

b. Function calling: Parenthesis are used to function calling.
Example: (f) would call function f. (add 2 3), would call the function add with 2 parameters.

Data Struct:
a. struct: 
Syntax: (struct datatype (field1 field2 ...))
Example:
declaration: (struct name (first last))
usage: (name "saif" "sidd")
When a struct is defined, current environment gets extended with some automatic functions. Here are examples:
name? :: if a value is of type name
name-first :: retrieves the value of the field "first"
name-last :: retrieves the value of the field "last"

b. list:
Syntax: (cons e1 (cons e2 (cons e3 null))) would create a list with 3 items after evaluating expressions, e1, e2 and e3.
List can be created using syntactic sugar: (list e1 e2 e3)

Empty is list called null.
list functions:
null? :: checks if a list is null
car :: retrieves head item of a list
cdr :: retrieves tail item of a list

eval function:
"eval" function lets Racket run another Racket program that was created dynamically during a program execution. Usually, languages that supports eval like functions, needs to interpreted language as interpreted languages don't needed to be compiled first and run later.

Mutability
variable mutation:
(define x 1)
(set! x 2) ;; changes value of x
list mutation:
mcons is used to build mutable list. Functions related to mutation,
mcar
mcdr
set-mcar!
set-mcdr!

Concepts
a. Laziness:
(define (f x y z) (...)) when the function is called (f e1 e2 e3), all the expressions e1, e2 and e3 will be evaluated. If we rewrite the function such that e1, e2 or e3 only gets executed when necessary, it is called lazy evaluation. This is done using thunks.

a. Thunk:
A zero argument function, that when executed evaluates some expression using lexical scoping.
If we call, f the following way
(f (lambda () (add a b)) e2 e3) then, the first expression consisting of lambda won't get executed.

b. Stream
A thunk that can be called infinitely to get next pair of data.
(define (one) (cons 1 (lambda () one)))
if the function one is called (one) it produces the pair (cons 1 (lambda () one)). The data can be retrieved using car, using cdr the stream function can be retrieved and called again.

Another example that produces numbers 1, 2, 3, 4 ....
(define (natural)
      (letrec ([f  (lambda (x) (cons x (lambda () f(+ x 1))))])  (f 1)) )

c. memoization:
Using mcons pair we can store result of a function evaluation.
(define a (mcons #f (lambda () (function))))
We need to check head of the mcons shell if it is #f that means the function was not evaluated, we go ahead and evaluate and return the result.
(if (mcar a)
     (mcar a)
     (begin (set-mcar! (m-cdr a))
                 (mcar a)))

d. Macro:
Macros are user defined syntactic sugar for extending a programming language. Racket has a superior macro system using closures.

Reference:
0. https://www.coursera.org/learn/programming-languages-part-b

Effective Java Extracts - Overriding Methods of Object Class

All ideas I have taken from the book Effective Java Joshua Bloch.

0. Overriding equal method

Usually overriding equals method is not recommended.

When an object x is being compared with another object y, equal method should maintain the following invariant

a. Reflexive - x.equals(x) should always be true
b. Symmetric: if x.equals(y) is true so should be y.equals(x)
c. Transitive: if x.equals(y) and y.equals(z) are true so should be x.equals(z)
d. Consistent: if x.equals(y) true, then it should remain true for any number of equals method calls given the criteria that determines object x and y's equality did not change.
f. Null is not an object: x.equals(null) should always be false

Consequence of violating the property:

If the above constraints are not met, then usage of an object collection might produce erroneous result.

     list = new List()
  list.add(x)

Reflexive property is not met:  x.equals(x) returns false. list.contain(x) will return false. which is untrue.

Symmetric property is not met: x.equals(y) is true while y.equals(x) is false . if we add list.add(y) and check list.contains(x) it will return false.

General guidelines
a. If it is the reference of the same object, equal should return true. Check this with == operator.
b. Check if the object is of same Class through instanceOf operator. This takes care of null check.
null instanceOf ClassType equals to false.
c. Compare fields first that are more likely to change.
d. Make sure the constraints are not violated.
e. Override hashCode method if equals is overridden. Otherwise map data structures will produce incorrect results as similar to the examples provided for lists cases above.

1. Override hashCode() when equals() is overridden

To insert and object to a hash-based collection (hash map, hash set), the collections at first calculates hashCode of the object, then based on hash code it stores the object to one of buckets. This means equal objects must return equal hashCodes, otherwise collections would end up looking into a wrong bucket where the desired object was not added. By overriding hashCode(), we can guarantee the constraint holds.

If fields that are used to compare object equality are not changed, subsequent calls to hashCode() should produce the same value.

An example on writing a good hashCode()

class TestClass{
field x; //used in object equality check
field y; //used in object equality check
field z;
int a;  //used in object equality check
int b; //used in object equality check

hashCode(){
base = 37; //this chosen as it is a odd prime
result = 17;
result = result * base + x.hashCode();
result = result * base + y.hashCode();
result = result * base + a;
result = result * base + b;
return result;
}
}

To do not be tempted to exclude a field's hashcode. For example, to getHashCode of a String only 16 characters in the beginning is taken then most of the urls will produce the same hashcode which will make a hashmap perform like a linked list.

Effective Java Extracts

I have documented for my learning purpose ideas from the book Effective Java [0] by Joshua Bloch. I have documented every idea with a minimal example. The book contains tons of valuable information that might be absent in this series of articles.

0. Prefer a Static Method instead of Constructors

Example:
public static Boolean valueOf(Boolean b){

return b? Boolean.TRUE : Boolean.FALSE

}

Advantages of static method to construct objects:

a. does not always create a new object

b. provides more information than constructor overloading
BigInt(prm1, prm2) //this constructor's purpose is to return a relative prime compared to static getRelativePrime(prm1, prm2) //static constructor has descriptive name

c. a subclass can be returned

Disadvantages

a. classes without public constructors cannot be subclassed

b. static object generator methods are hard to distinguish from other methods.
workaround, use well established static method names for object generation

- valueOf

- getInstance

1. Enforce Singleton Property with a Private Constructor

class Elvis{
  private final INSTANCE = new Elvis();
  private Elvis(){}
  public static getInstance(){ return INSTANCE; }
}

2. Prevent Instance Creation with Private Constructor

This tip is applicable for utility classes that only have collection of static methods, such as Math class.

class Math{
  private Math(){
    //constructor is private so not possible to create instance Math class
  }
}

3. Avoid Creating Duplicate Objects

//Don't do this

public void isBornOn90s(){
  calendar = Calendar.getinstance()
  calendar.setDate(1, 1, 1990)
  startDate = calender.getDate()
  calendar.setdate(12, 31, 1999)
  endDate = calendar.getDate()

  if(this.birthDate.after(startDate) && this.birthDate.before(endDate)) 
    return true 
  else return false
}

instead create those date objects as private member

Person{
  private startDate;
  private endDate;

  static{
    calendar = Calendar.getinstance()
    calendar.setDate(1, 1, 1990)
    startDate = calender.getDate()
    calendar.setdate(12, 31, 1999)
    endDate = calendar.getDate()
  }

  public void isBornOn90s(){
    return bithdate.after(startDate) && birthdate.before(endDate);
  }
}

4. Get rid of Objects that will not be Referenced Again

Memory leak is a situation when we keep storing objects that won't be referenced any more.

Stack{
  elements = new elements();

  push(item){
    //if no more space then allocate space and copy old items to new space
    //....
    elements[size++] = item
  }

  pop(){
    return elements[--size];
  }
}

The problematic line is in the pop method, it does not discards a popped item. The method needs to

be rewritten as the following

pop(){ res = elements[--size] elements[size] = null return res }

Good practices:

a. declare variables in narrowest possible scope so that scope discards the variable automatically.

b. set unnecessary reference to null.

5. Do not Use Finalzer methods
Every object has a finalize method, that is expected to be called when the 
object is being garbage collected. Problem is JVM does not guarantee that the
 "finalize" method will get called. So resources might never be released if 
 finalize methods are used.

//Don't do this
Class WrongWay{
  private resourceA, resourceB;

  //it is unknown if the following method will be called or not by GC
  finalize(){
    release resourceA
    release resourceB
  }
}

//Do this
class RightWay{
  private resourceA, resourceB;

  //provide method that acquires resources
  acquire(){
    acquireResource resourceA
    acquireResource resourceB
  }

  //provide method to release methods. Users should call this mehtod explicitly.
  release(){
    release resourceA
    release resourceB
  }
}

Almost always it is bad to use finalizers. It can be used to provide a safety 
net incase the users of the api forgets to call close method. Then another 
problem arises. From overridden finalize method, we will have to call 
super.finalize() explicitly otherwise that method won't get called. A better 
way is the following

class SafetyNetFinalize{
  private saftety = new Object{
    finalize(){
      SafetlyNetFinalize.this.finalize()
    }
  }
}

This works because the SafetyNetFinalize does not override finalize method, so
no fear that it's implementation forgets super.finalize() method

[0] Effective Java- Joshua Bloch amazon link.

λ calculus

Rules of the universe

0. Permitted keywords: Everything in lambda calculus is function. All the algorithms are represents with functions. There are only 2 keywords, λ and . needed to write a function. And that's it. Everything between λ and . are function arguments, everything after "." is the function body.
Example: λx.x+1 represents a function, that takes an argument x and returns x+1. Note that, x can be replaced by any other names.
A few notes
    a. A function can be written in such a way so that it always takes only 1 argument.
    Example: λxy.(x+y) can be written as, λx.(λy.(x+y)). If this function is applied to argument 3 4 then, the following happens
    (λx.(λy.(x+y))) 3 4 => (λy.(3 + y)) 4 => (3 + 4) => 7
    Writing a function such that it always takes only 1 argument is called function Currying (named after Haskell Curry).
 
    b. functions do not have names. We can say, a function A = λx.x+1, when we say the function does not have a name, we say from inside the function body, we do not know the name of function. So we cannot write a function, A = λx.A(x) because, from the function body we don't have access to names of the caller A.
 
    c. When we say fx we mean f is applied on x, f(x). ABCDE means A, B, C, D and E are functions and is applied the following way
    ((((AB)C)D)E)
    which means A is applied to B, the resulting function is applied to C so on and so forth.

1. Application and value substitution:
Example: A = λx.x+1; A3 means the function A is applied on the value 3. All the x s in the expression x+1 will be replaced by 3. This is expressed as [3/x](x+1) = 3 + 1 = 4

2. Reduction:
By application and substitution, a complex function might be reduced to small one.
Example: (λx.(λy.y))ts = s

Building Blocks of the Universe

Boolean value construction
0. True:
As stated earlier everything in the universe will be functions. The value True is represented as the following function
T : λ xy.x . Basically the true function takes 2 arguments and return the first argument.
1. False:
False, F is represented by the following function.
F : λ xy.y . This function takes 2 arguments and returns the second argument.

Boolean Operations
And, ^:
^ : λxy.xyF
Or, v:
v : λxy.xTy
Not, ¬:
¬ : λx.xFT

Arithmatic value construction
Integers:
0, 1, 2, .. n are all represented by functions that takes two arguments.
0: λfx.x This means the function 0 takes two arguments f and x and applies f on x zero times.
1: λfx.f(x) , 1 takes two arguments, f, x and applies f once to x
2: λfx.f(fx) , 2 takes two argument f, x and applies f twice on x
3: λfx.f(f(fx)) 3 takes two argumetns f,x and applies f three times on x.
so on and so forth
Pairs:
A pair holding two integers a and b is represented by the following function
p : λx.xab
Retrieve the first element from p, pT => (λx.xab)T => Tab => a
Retreive the second element p, pF => (λx.xab)F => Fab => b

Arithmetic Operations:
Successor:
S: λxyz.y(xyz)
Example: S0 => (λxyz.y(xyz))0 => λyz.y(0yz)
            => λyz.y((λfx.x)yz) => λyz.y(z)
            => λfx.f(x) [renaming variable y with f and z with x]
            => 1 [from definition of 1 function]

(+ a b):
+ : (λab.aSb)
Example: (+ 2 3) => 2S3 => (λfx.f(f(x)))S3 => S(S(3)) => S(4) => 5

Predecessor, P:
We want to know the predecessor of 3. Basic idea,
start with the pair holding (0,0) then convert it the following order
(0,0) -> (1, 0) -> (2, 1) -> (3, 2) -> take second element of the pair, which yields 2.
we need a function Φ, that would take a pair (n, n-1) and would generate (n+1, n)
Φ: λpz.z(S(pT)(pT)) => lets say pair , p holds (3, 2). new pair will hold (S(pT), (pT)) => (S(3), 3) => (4, 3)
We can define P: (λn.nΦ(λz.z00))F which means Φ is applied to the pair (0,0) for 3 times and the second element of the pair is taken in the end.

(- a b) :
- = (λab.bPa)
Example: (- 3 2) => 2 P 3 => P(P(3)) => P(2) => 1

Conditionals:
Conditional such as a == b, a >= b or a <= b etc can be expressed by function.
(>= a b):
a >= b check can be done with the following function 
>= : (λab.Z(- b a))

(== a b):
a == b check can be done with the following function 
== : (λab.( >= b a) ^ (>= a b))

Recursion:

The λ functions don't have name, so from inside the body it is not possible to call the * function. Recursive calls are made using Y combinator.

Y : (λ f  . (λ x .  (f (x x)) (λ x . f (x x))))

R is a function that needs to be called recursively. Then, Y is applied to R

YR = Y(R) = (λ x. (R (x x)) (λx. R (x x)))

= R ((λ x. (R (x x)) (λx. R (x x)))) [value substitution]

= R (YR) ...... 

= R(R(R(R....(YR))))

We can see that YR is being computed with computing R first, one return value of R is used to compute caller's value.

Example:

we want to compute (1+2+3+...+n)

R : (λrn.Zn0(+ n r((- n 1))))

R is a function that takes 2 arguments, n and r. 

In base case, n become 0. Zn returns T then T gets two arguments 0 and (+ n r((- n 1))). We know T always returns the first argument so in this case R will return 0.

if n > 0 then Zn returns F. F would return the second argument (+ n r((- n 1))), which means it would return n + r(n-1)

Example evaluation:

YR3 = R(YR)3

= (λnr.Zn0(+ n r((- n 1)))) (YR) 3

= Z 3 0 (+ 3 YR(- 3 1))

= Z 3 0 (+ 3 YR2)

= F 0  (+ 3 R(YR)2)

= (+ 3 (λnr.Zn0(+ n r((- n 1)))) (YR) 2)

..........

= (+ 3 (+ 2 (+ 1 0) ))

= 6

References
[0] computerphile video on lamda calc: https://www.youtube.com/watch?v=eis11j_iGMs
[1] Dason's slide: https://www.slideshare.net/g33ktalk/lambda-calculus-by-dustin
[2] friendly explanation: http://www.inf.fu-berlin.de/lehre/WS03/alpi/lambda.pdf
[3] Dustin's presentation: https://www.youtube.com/watch?v=E5DwIxGOu1E