[Compiler] Inside My Implementation of the Jack Compiler

A compiler would take a program written in a high level language and translate the instruction to the instruction for a Virtual Machine(VM).

#Modules
A compiler has the following modules
0. Tokenizer
1. Parser
2. Symbol table generator
3. VM code generator

# Implementation Detail
0. Tokenizer
A language defines its basic building blocks (tokens). These basic building blocks contains comment structure, keywords, symbols, identifier logic,  literals(integer, string etc). A parser would take a program and generate stream of tokens as defined by a given language.

The tokenizer gives the following apis
i. hasMoreTokens()
ii. advance()
iii. getCurrentToken()

Algorithm:
i. Load given program in to memory
ii. Remove all the comments
iii. Add a space where 2 tokens are joined (eg. convert 5; to 5 <Space> ;)
iv. Look for a character
             if (character != ")
                curIndex = i
                j = index of next space
                subString = extract(i, j)
                using regular expression, check if the subString is a proper token, if so store in a list raise                     an exception otherwise
            if (character == ")
                look for next " and extract the substring and store in the token list


1. Parser
Uses a tokenizer and checks if the token sequence is in harmony with the grammar of the language.

Implementation:
Lets consider rule for class
class   >>>
    'class' identifer '{'
              classVarDec*
              subroutineDec*
     '}'

A set of function related to each grammar construct and bunch of helper function helped me writing the parser module.
Example:
For the rule above, I wrote the following method in the parser

void CompileClass(){
  keyword(CLASS);
  identifier();
  symbol('{');
  classVarDec_zero_more();
  subroutineDec_zero_more();
  symbol('}');  
}
Here compileClass is the method related to the grammar rule and classVarDec_zero_more() is a helper function.
the method symbol(char) was implemented as follows

void symbol(s)
  curTok = tokenizer.getCurrentToken();
  if(curTok.type != SYMBOL)
    raise exception
   
  if(curTok.val != s)
    raise exception
 
  tokenizer.advance()
end

2. Symbol Table
A symbol table is used to translate a variable declared in a high level language to a (segment, offset) pair of a virtual machine. Symbol table is divided in two spaces, one for variables declared in class level another one for subroutine level

API
i. define(varName, kind(static, field etc), type(String, CustomClass etc))
  called when a variable declaratrion is encountered
ii. startMethodLevelSymbolTable()
  called when a method declaration is encountered
iii. getInfo(varName)
  used to resolve a variable name encountered

An instance of symbol table needs to be added on the parser. As the parser process any variable declaration, an entry needs to be created in the symbol table.

3. VM Code generator
A VM Code generator needs to be augmented within the parser. As the parser parses through a given source code, a VM Code Generator would gather context and when appropriate will generate proper VM Code. This module keeps an eye on the following cases
i. Function declartion handling
A VM only cares about subroutines. A compiler needs to translate and write all the subroutines in a output file. To resolve name collision, when a subroutine subRot is encountered in class MyClass, the VM code generator would give the subroutine the name "MyClass.subRot". Here is how it deals with different subroutine types.

#Static
Observes how many local variables declared in the static method (lets call it n) and then generate the following code
function  MyClass.subRot n

#Construtor
Observes how many local variables are declared(localCount) from parser and how many fields the MyClass has(fieldCount) from symbol table. Then generates the following code-

function MyClass.new localCount
  call Memory.Alloc(fieldCount)
  pop pointer 0 //pointer 0 is used for current object also known as this
 
#Method
A method implicitly expects the object to act on as its first argument. It observes how many local variables are declared(localCount) from parser then generates the following code-

function MyClass.subRot localCount+1
  push arg 0
  pop pointer 0 //sets this pointer
 
The above code essentially sets this pointer to the object on which the method is called.

# Variable declaration
Create an entry in appropraite space of the symbol table with proper context.

# Expressions
An expression is evaluated and is value is pushed to stack.
## for an int value, generate -> push value.
## True -> generate -> push -1 //notice -1 means 11111... in memory
## False, null -> push 0
## "ab" generate the following
  call Memory.alloc 3 //3 characters in the string
  call String.appendChar 97 //ascii value of 'a'
  call String.appendChar 98
## variable, a variable is resolved using the symbol table. For example, lets say a variable var was declared in a method and it was the 2nd variable. So this variable exists in local segemnt's 2nd index. it will be resolved as following
  push local 2
A variable declared in a class, or declared as staic or declared as an argument would resolved with a proper segment and a proper offset.
 
## binary operator, an expression with the form (exp1 op exp1) is translated in the following way
  evaluate exp1 //exp1's value would be on top of the stack
  evaluate exp2
  op //apply the operator on the top two values of the stack
 
## unary operator, op exp
  evalute exp
  op
 
## for a method call myMethod(1, 2) of class MyClass, the following code will be generated
  push pointer 0 //push this object's reference to stack
  push constant 1
  push constant 2
  call MyClass.myMethod 3 //3 is the number of arguments the caller has passed to the function
 
## To translate a call of myObj.myMethod(1,2) using the symbol table, Code generator module finds its type lets say MyClass. Then it generates the following-
  push myObj //pseudo code, myObj needs to be resolved using symbol table as described earlier.
  push 1
  push 2
  call MyClass.myMethod 3
 
## To translate a static method MyClass.myStatic(1,2) the Code generator does not have to push any objects reference as the first argument. Other than that, it produces VM code as following the logic earlier.

## Access array index, myObj[exp] is translated as follows
  evaluate exp
  push segment offset //myObj variable's segment offset
  add
  pop pointer 1 //set that pointer (pointer 1), with the address of myObj[exp]
  push that 0 // push the value of myObj[exp] to stack

# Statements
## return : Every subroutine is expected to produce a result and push it to the stack.
return; is translated as
  push constant 0
  return
 
return exp; is translated as -
  evaluate exp //the value of exp will be on top of the stack
  return
 
## method call. A method call statement, do myMethodCall(1,2); would be translated as follows
  generate code for myMethodCall(1,2) discussed in the Expression section
  pop temp 0 // discard the value generated by the function as it will not be used
 
## assignment
  ### let var = exp; using symbol table first finds segment, offset of the var. Then the following code gets generated
    evaluate exp
    pop segment offset
   
  ### let var[exp1] = exp2
    evaluate exp2
    evaluate exp1
    push segment offset
    add
    pop pointer 1
    pop that 0
   
## If else
  if(cond) { stmts1 } else { stmts2 } is translated as follows
 
  if-goto IF-TRUE
  goto IF-FALSE
  label IF-TRUE
 
  generate code for stmts1
 
  goto IF-END
  label IF-FALSE
 
  generate code for stmts2
 
  label IF-END

## while
  while(cond) { stmts } is translated as follows
 
  label WHILE-BEGIN
  evaluate cond
  not
  if-goto WHILE-END
 
  generate code for stmts
 
  goto WHILE-BEGIN
  label END

Conclusion:
To build a compiler from the scratch, start with the tokenizer module. Build parser module with the the help of tokenizer. Write symbol table module and integrate it to the Parser. Write VM Code generator module, then augment it to the Parser module; also add proper context capturing code in the Parser module.

Reference:
0. My compiler implementation
1. Elements of computing: Building a modern computer from the first principle
2. A modern compiler generation in Java
3. Stanford Compiler course by Dr. Alex Aiken
4. GATE lecture on Compilers by RavindraBabu

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