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

SML syntax and functional programming concepts

Expression
All the expression from 1 and below must be used in a function.

0. Function
A function would take zero or more parameters and will always return a value.
fun foo () = 3
fun sqr (x, y, z) = x + y + z
A function always takes a parameter, either in the form of tuple or currying (discussed later).

1. let
A let expression lets extend the current environment by letting the creation of variables and functions. has to be used inside a function. example
fun foo (x) = let y = x * x in y end

2. if then else 
An if then else construct has to always return a value. the type of the value must be same from each of the branch. has to be used inside a function. example:
if x = 3 then true else false

3. pattern matching
Given a value, takes the branch that matches the data type of the value. example:
case exp of
    [] => NONE
   | Some x => do something

Environment
0. Extending environment
Any time a variable, function is declared, current environment is extended by a new binding.
| y = 3 | z = 5| x = 5  <=== current environment
val p = 3
| y = 3 | z = 5| x = 5| p =3  <=== updated environment
A new variable can be introduced from a pattern matching expression. Example:
case lst of
 x :: xs => do something (* :: is the append function which is declared as infix *)

1. Shadowing

introducing a new binding does not override a value in the environment, rather a new entry is created and from that scope new entry's value is used.
| y = 3 | z = 5| x = 5  <=== current environment
val y = 3
| y = 3 | z = 5| x = 5| y =3  <=== updated environment

2. Closure
Combination of a function and a pointer of the environment is closure.
Example:
val y =3
val z = 5
fun foo = z + 3
val z = 5
val y = 3
val closure = foo
closure has the instruction pointer of the function foo and the following pointer of the environment
| y = 3 | z = 5| z= 5| y =3  <=== updated environment

                    ^

  <======  | | to get a value of a variable, closure will start from the pointer and go left.

Datatype and Accessing data
0. Record, Tuple
Records are created dynamically. They can have any number of fields in them.
Example: {first="isaac", middle="buddha", last="christ"}
A type can be given a name. Example
type set = { insert : int -> set, member : int -> bool, size : unit -> int }

1. List
Lists are immutable. An insertion or deletion would always cause a new list to be created with desired elements.
Example:
[] is empty list
"a" :: [] (* insert an element at the head *)
["1, 2, 3, 4] @ [5, 6, 7, 8] (* append operator *)

2. Custom data type
datatype myType = StudentInfo of string * string | Grade of int

val myInfo = StudentInfo ("isaac", "christ").
Datatypes can be pattern matched.

Modular Programming
It can be think of like a Java package. Gives client visibility of enough information so that they can import the library in their code and use it. Best practice is to provide just enough information so that a client executes the given program with minimum risk.
Example:
signature MATHLIB =
sig
    val fact : int -> int
    val half_pi : real
    val doubler : int -> int
end

structure MyMathLib :> MATHLIB =struct
     fun fact x = if x=0 then 1 else x * fact (x - 1)
     val half_pi = Math.pi / 2.0
     fun doubler y = y + y
end

Mutability
Variables can be mutated through reference.
val x = ref 7 (* the memory location x points to holds the value 7 *)
val y = x (* y points to same memory location as x does *)
val z = ref 7 (* the memory location z points to holds 7 *)
val _ = x := 20 (* := operator is for assigning value, := operator returns unit *)
val p = !x (* retrieve content of x, p get 20*)
val q = !y (* q has 20 *)
val r = !z (* r has 7 *)

Misc

0. Higher order function

functions that can take another function and return a function as a return value.

1. Anonymous function
functions that does not have names.
fun foo bar x = bar x
val v = foo (fn (x) => x+1) 1

2. Currying
Curried functions always takes 1 argument and returns either a value or another function. Curried functions use closure to access variables it uses. Curried functions can be called with less arguments.

3. Tail recursion
A recursive call where the caller just returns the value the callee returns without applying any application on the callee's returned value. more can be seen [1].

4. Syntactic sugar
Certain language features that lets a programmer do a certain task with less amount of typing.
Example:
fun f = fn (x) => (fn (y) => (fn (z) => x + y + z))
f can be written using syntactic sugar fun x y z = x + y + z

5. map, filter, fold
these functions are applied on a list.
map => converts each item of the list to something else (* convert degree list to celcius list *)
filter => returns a list where every item meets a certain criteria (* get students who passed *)
fold => returns value that depicts certain attribute of a list (* get sum of the values of a list *)

6. value restriction
Because of mutability, it might be possible to assign value with wrong type on a variable. The value would not be shadowed rather overwritten. Initially, if we say we are able to say we would be storing a polymorphic data in a certain memory location, then later we might try to assign wrong type values in that memory location.
Example:
val r = ref NONE (* system does not which type will go where r is pointing to *)
(* type of r is given ?.X1 option ref type *)
r := SOME "abc" (* trying to assign string *)
r := SOME 1        (* trying to assign int *)
To prevent this, the variable declaration must have a concrete type, otherwise system will give r a type to make r not usable anymore.
That's why we cannot do the following
val funhandle =  map (fn (x) => (x, 1))

The following works, as it have concrete type
val r : int option ref = ref NONE;

Value restriction is introduced only for mutability or ref type. This restriction is generalized because many times the compiler cannot tell about a type. One case being types introduced through modular programs.

Reference:
[0] https://www.coursera.org/learn/programming-languages
[1] http://www.saifulabu.me/2017/11/tail-recursion.html