Set as a function abstraction – Part 2

In Part 1 we saw how to define basic operation like union, intersection etc on Set in terms of its indicator function.

In this section we will see Universal quantification, Existential quantification , map and reduce operations.

Universal Quantification
p holds for all the values in Set s. Here there is a notion of value (till this function we were operating in an abstract space). The function abstraction Int => Boolean indicates whether an element is present in a set or not, so inorder to find the values of Set s we will have to iterate from -infinity to +infinity and apply p to each value, which is not at all possible and hence we are limiting our bound to a finite range from -1000 to +1000

 /**
   * The bounds for `forall` and `exists` are +/- 1000.
   */
  val bound = 1000

  /**
   * Returns whether all bounded integers within `s` satisfy `p`.
   */
  def forall(s: Set, p: Int => Boolean): Boolean = {

    def iter(e: Int): Boolean = {
      if (e > bound) true
      else if (contains(s,e) && !p(e)) false
      else iter(e + 1)
    }
    iter(-bound)
  }

p holds for all values in s if !p holds for at-least one value in s,
proof by contradiction

Existential Quantification
at-least one value in s satisfies p

 /**
   * Returns whether there exists a bounded integer within `s`
   * that satisfies `p`.
   */
    def exists(s: Set, p: Int => Boolean): Boolean = !forall(s, e => !p(e))

there exists a bounded integer within s that satisfies p if !p doesn’t satisfy for all values in s,
proof by contradiction.

map

 /**
   * Returns a set transformed by applying `f` to each element of `s`.
   */
    def map(s: Set, f: Int => Int): Set = {
      def iter(s: Set, acc: Set, e: Int): Set = {
        if(e > bound) acc
        else if(contains(s, e)) iter(s, union(acc, x => f(e) == x), e + 1)
        else iter(s, acc, e + 1)
      }

      iter(s, x => false, -bound)
    }

let s1 = [1,2,3] we want to square it and get s2 = [1, 4, 9].
indicator function for s1 = x => x == 1 || x == 2 || x == 3 and
for s2 = x => x == 1 || x == 4 || x == 9

so the function f = x => x * x, applying f on all values in s1 results in s2
there for s2 = x => x == f(1) || x == f(2) || x == f(3)

reduce
In addition to these functions, I have added the reduce function on set

def reduce(s: Set, f: (Int, Int) => Int ): Option[Int] = {

    @tailrec
    def loop(s: Set, acc: Int, e: Int): Int = {
      if(e > bound) {
        acc
      } else if(s(e)) {
        loop(s, f(acc, e), e + 1)
      } else {
        loop(s, acc, e + 1)
      }
    }

    @tailrec
    def getFirst(s: Set, e: Int): Option[Int] = {
      if(e > bound) {
        None
      } else if(s(e)) {
        Some(e)
      } else {
        getFirst(s, e + 1)
      }
    }

    val firstElem = getFirst(s, -bound)

    if(firstElem.isEmpty) {
      None
    } else {
      Some(loop(s, firstElem.get, firstElem.get + 1))
    }
  }
Advertisements

Set as a function abstraction – Part 1

I have been attending sessions on Scala at Hifx (taken by Sajith Bhai as part of our internal training programs). If I get it right the sessions started with Scala syntax and eventually moved towards functional thinking and functional apis on Scala collections, and as a exercise we were given an assignment to implement union, intersection, diff, filter, forall, exists, map on Set.

This was too abstract a task.
At first sight we would assume that this is a data structure problem. This will we torn away by the alias definition

type Set = Int => Boolean

. This is the signature of the characteristics or indicator function of the Set (Indicator_function_wiki) and this is all we will get for writing our implementation.

contains

def contains(s: Set, elem: Int): Boolean = s(elem)

this impl is given with the assignment. assume that s: Set = x => x > 4, then contains is s(elem) = elem => elem > 4.
So as the name suggests if we give an Set and an element to contains it will tell us whether the element is present in the Set.

Singleton Set

def singletonSet(elem: Int): Set = x => elem == x

Singleton set reuturns a Set abstraction which will be evaluated to true for a single element in the domain of the function.

singletonSet(1) == x => 1 == x, which will be true only for 1

union

/**
   * Returns the union of the two given sets,
   * the sets of all elements that are in either `s` or `t`.
   */
    def union(s: Set, t: Set): Set = (x: Int) => contains(s, x) || contains(t, x)

the sets of all elements that are in either `s` or `t`.
let s = x => x % 3 == 0
let t = x => x % 5 == 0
then union = x => x % 3 == 0 || x => x % 5 == 0
(This is equivalent to the logical connective OR in predicate logic)

intersection

/**
   * Returns the intersection of the two given sets,
   * the set of all elements that are both in `s` and `t`.
   */
    def intersect(s: Set, t: Set): Set = (x: Int) => contains(s, x) && contains(t, x)

(This is equivalent to the logical connective AND in predicate logic)
let s = x => x % 3 == 0
let t = x => x % 5 == 0
then intersection = x => x % 3 == 0 && x => x % 5 == 0

diff

/**
   * Returns the difference of the two given sets,
   * the set of all elements of `s` that are not in `t`.
   */
    def diff(s: Set, t: Set): Set = (x: Int) => contains(s, x) && !contains(t, x)

Self explanatory I guess 😉

filter

/**
   * Returns the subset of `s` for which `p` holds.
   */
    def filter(s: Set, p: Int => Boolean): Set = intersect(s, p)

Considering p as another Set we could easily take the intersection and find the filtered result

Scala Notes – Partial Functions

A partial function is a unary function which doesn’t require all the values of the domain. It should be a sub type of PartialFunction trait (PartialFunction).

Syntax example:

val statusMessage: PartialFunction[Int, String] = {
  case 200 => "Okay"
  case 400 => "Prob"
}

statusMessage.isDefinedAt(200) //can be used to check whether the value 200 is included in the domain.

statusMessage(400) // Prob
statusMessage(100) // Match error 

Lambda Calculus – Notes 1

Lambda calculus consist of 3 things, variables, function abstractions and function application. Alpha renaming and Beta reduction are two operations which we can do on Lambda terms

Example
lambda x. x
here x is a variable
lambda x. x is a function abstraction

(lambda x. x) y is a function application

since lambda calculus treats lambdas or functions as first class citizens the variable can be another lambda abstraction in a function application, which means (lambda x. lambda y. x + y ) lambda z is a valid lambda application.

Expressing Natural numbers in lambda calculus

0 -> lambda f.lambda x. x

this statement means 0 a way of writing zero, how would I put it, a way of expressing nothingness in decimal number system is expressed as lambda abstraction lambda f.lambda x. x in lambda calculus.

1 -> lambda f.lambda x.f(x)
1 in decimal system is represented as a single function application over x in the lambda expression.

2 -> two times the application of function
-> lambda f.lambda x.f(f(x))

we can derive n natural numbers by Peano’s arithmetic

1 -> successor of 0
2 -> successor of 1

so we need a way of representing the function successor (which would be applying one more function on x than its predecessor)

successor -> lambda n.lambda f.lambda x.f(n(f, x))

1 -> successor 0
-> lambda n.lambda f.lambda x.f(n(f, x)) (lambda f.lambda x. x)
-> since the lambda abstraction and variable value contains conflicting variable names
we will do alpha renaming on the value
-> lambda n.lambda f.lambda x.f(n(f, x)) (lambda g.lambda y. y)
-> lambda f.lambda x.f(lambda g.lambda y.y (f, x))
-> lambda f.lambda x.f(x) == 1

now lets define a plus function, successor was just incrementing 1 to its param, in lambda calculus terms it was applying one more function on the inner lambda’s param. In case of addition say we want to add 1 to 2 so we want to get lambda f.lambda x.f(x) + lambda f.lambda x.f(f(x)) = lambda f.lambda x.f(f(f(x)))
so the plus function adds n function application to the second lambda if we want to add n + _.

plus -> lambda n.lambda m.lambda f.lambda x.m(f, n(f, x))
1 plus 2
-> lambda n.lambda m.lambda f.lambda x.m(f, n(f, x)) (lambda f.lambda x.f(x), lambda f.lambda x.f(f(x)))
alpha renaming
-> lambda n.lambda m.lambda f.lambda x.m(f, n(f, x)) (lambda g.lambda y.g(y), lambda h.lambda z.h(h(z)))
-> lambda f.lambda x.lambda g.lambda y.g(y)(f, lambda h.lambda z.h(h(z))(f, x))
-> lambda f.lambda x.lambda g.lambda y.g(y)(f, f(f(x))
-> lambda f.lambda x.f(f(f(x))) == 3

Tail call optimisation in Scala – Have a look into Java byte code

Let’s see a power function

def power(x:Int, n:Int): Long = {

  @tailrec
  def loop(x:Int, n:Int, acc:Long): Long = {
    if(n >= 2)
      loop(x, n-1, acc * x)
    else
      acc
  }

  loop(x, n, x)
}

power(2, 3)

The power function calculates the value of x^n, this is achieved by a recursive function loop. If a function is tail recursive, which means if the last expression of the function’s body is a recursive call or has recursive calls as leaf nodes (if you consider the AST), then the compiler will optimise the function by converting it to do the execute iteratively (optimisation here is the removal of additional stack frames required while execution). The inner function loop here is a tail recursive call (@tailrec will ensure that the loop method is tail recursive, if the compiler cannot optimise it, it will throw error at compile time).

Inorder to compile the code snippet and see the bytecode lets wrap the function in a class.

Power.scala

import scala.annotation.tailrec

/**
  * Created by sarath on 17/06/17.
  */
object Power {

  def power(x:Int, n:Int): Long = {

    @tailrec
    def loop(x:Int, n:Int, acc:Long): Long = {
      if(n >= 2)
        loop(x, n-1, acc * x)
      else
        acc
    }

    loop(x, n, x)
  }

  def main(args: Array[String]): Unit = {
    println(power(2, 3))
  }

}

Let’s compile the code

for a single Power.scala source code the compiler has generated two class files Power.class and Power$.class

Let’s inspect the byte code of Power.class

the power method is where we want to look into

public static long power(int, int);
    Code:
       0: getstatic     #16                 // Field Power$.MODULE$:LPower$;
       3: iload_0
       4: iload_1
       5: invokevirtual #22                 // Method Power$.power:(II)J
       8: lreturn

This method is just invoking another power method of same signature inside the Power$.class, so let’s see the byte code of Power$.class

Compiled from "Power.scala"
public final class Power$ {
  public static final Power$ MODULE$;

  public static {};
    Code:
       0: new           #2                  // class Power$
       3: invokespecial #12                 // Method "<init>":()V
       6: return

  public long power(int, int);
    Code:
       0: aload_0
       1: iload_1
       2: iload_2
       3: iload_1
       4: i2l
       5: invokespecial #18                 // Method loop$1:(IIJ)J
       8: lreturn

  public void main(java.lang.String[]);
    Code:
       0: getstatic     #29                 // Field scala/Predef$.MODULE$:Lscala/Predef$;
       3: aload_0
       4: iconst_2
       5: iconst_3
       6: invokevirtual #31                 // Method power:(II)J
       9: invokestatic  #37                 // Method scala/runtime/BoxesRunTime.boxToLong:(J)Ljava/lang/Long;
      12: invokevirtual #41                 // Method scala/Predef$.println:(Ljava/lang/Object;)V
      15: return

  private final long loop$1(int, int, long);
    Code:
       0: iload_2
       1: iconst_2
       2: if_icmplt     19
       5: iload_1
       6: iload_2
       7: iconst_1
       8: isub
       9: lload_3
      10: iload_1
      11: i2l
      12: lmul
      13: lstore_3
      14: istore_2
      15: istore_1
      16: goto          0
      19: lload_3
      20: lreturn

  private Power$();
    Code:
       0: aload_0
       1: invokespecial #46                 // Method java/lang/Object."<init>":()V
       4: aload_0
       5: putstatic     #48                 // Field MODULE$:LPower$;
       8: return
}

The method public long power(int, int) is the one being invoked from Power.class. Now the interesting part comes.

In the source code we have made use of an inner tail recursive function loop to do the computation, as there is no notion of inner functions in Java, loop has been transformed in to the function private final long loop$1(int, int, long) by the Scala compiler, and this loop$1 is being invoked at line number 32 from power method.

private final long loop$1(int, int, long);
    Code:
       0: iload_2
       1: iconst_2
       2: if_icmplt     19
       5: iload_1
       6: iload_2
       7: iconst_1
       8: isub
       9: lload_3
      10: iload_1
      11: i2l
      12: lmul
      13: lstore_3
      14: istore_2
      15: istore_1
      16: goto          0
      19: lload_3
      20: lreturn

at first look one thing is clear there is no self invocation and there is a goto (loops are implemented using jumps in jvm)

Let’s closely inspect the method

iload_2 – pushes the 3rd element from the local variable array to the operand stack
iconst_2 – pushes integer constant 2 to operand stack
if_icmplt 19 – comparison operator less than, if true jump to 19
iload_1 – pushes the 1st element from the local variable array to the operand stack
iload_2 – pushes the 2nd element from the local variable array to the operand stack
iconst_1 – pushes integer constant 1 to operand stack
isub – pops two elements from stack and do subtraction (2nd element of stack – 1st element of stack)
iload_3 – pushes the 3rd element from the local variable array to the operand stack
iload_1 – pushes the 1st element from the local variable array to the operand stack
i2l – pop from op-stack convert to long push it back
lmul – pop last two multiply push the result back
lstore_3 – pop the result and store it back to local variable array pos 3 – mutating the accumulator
istore_2 – pop from stack and store it at pos 2 – mutating n
istore_1 – pop from stack and store it at pos 1 – mutating x
goto 0 – jump to inst 0 – offsetting the execution engine
lload_3 – load the long value from 3rd pos of local variable array
lreturn – return pop the long value from the operand stack and return from the function

so basically they have converted the body of loop as it is and removed the function call by mutating the local variables and using goto to repeatedly execute the body.

Edit: Power function shown here is incorrect, the condition inside loop should be n >= 1 and while calling loop acc should be passed as 1.

Reflections in Golang

What is reflection?

Reflection is the capability provided by a language runtime to structurally analyze the data and code, manipulate and generate the data & code and dynamically direct the execution flow.

How is reflection possible??

Inorder to reflect on the data and code the meta data should be available at runtime and the only possibility of this in a compiled language is that the compiler will be baking the required meta information(Example: name and type of data, function names and signature, meta information of the source code etc..) while compiling the code. (Interpreted languages has the AST available at runtime). Once this info is available at runtime, its easy to provide it to the user using the reflection APIs provided by the language.

Why reflection??

David John Wheeler, a famous computer scientist has quoted that “All problems in computer science can be solved by adding another level of indirection”. Reflection brings this indirection from a program execution point of view, and there are quite a lot of examples out there in Java and .Net world which builds different levels of abstractions that solves many software design problems using reflection. One example I have seen in Golang is the json encoding and decoding utilities which accept any value and convert it to json and also builds given structures from json (I have just started learning Go).

An Example in Golang

I golang reflection is restricted to structural analysis, creation of data (only applicable on settable types) and dynamic method invocation

Refer the api doc for more details on the api.
This is just a demonstration

package main

import (
	"fmt"
	"reflect"
	//"unsafe"
)

type Contact struct {
	id    uint32 `myTag1:"asd", myTag2:"ff", das`
	Name  string
	Phone string
}

type InterFaceA interface {
	A() string
}

type InterFaceB interface {
	B() string
}

func (c *Contact) A() string {
	return fmt.Sprintf("%#v", *c)
}

func (c Contact) B() string {
	return fmt.Sprintf("%#v", c)
}

func main() {
	StructuralAnalysis()
	DataCreationAndCodeInvocation()
}

func StructuralAnalysis() {
	contactPtr := &Contact{id: 1, Name: "Sarath", Phone: "1233"}

	//Obtaining reflect.Value on the pointer
	contactValuePtr := reflect.ValueOf(contactPtr)

	//Obtaining reflect.Type from the Value
	//It holds the Type obj of Pointer
	typPtr := contactValuePtr.Type()
	fmt.Printf("TypePtrReflect: %#v\n", typPtr)
	//Obtaining reflect.Type of the real struct
	//It holds the real structure of the struct
	typ := typPtr.Elem()
	fmt.Printf("TypeReflect: %#v\n", typ)

	//Logging the meta information
	for i := 0; i < typ.NumField(); i++ {
		tag := typ.Field(i).Tag
		//Get FieldByName is also avaialble
		fieldType := typ.Field(i)
		fmt.Printf("Field--> %#v\n", fieldType)
		//Need reflect.Value to access the real values
		fieldValue := contactValuePtr.Elem().Field(i)

		//Check for the applicability of 2nd Law of reflection
		if(fieldValue.CanInterface()) {
			//2nd Law of reflection Value --> Interface
			fmt.Printf("Field Value--> %#v\n",fieldValue.Interface())
		} else {
			fmt.Println("Field " + fieldType.Name + " is not exported")
		}

               //Reading the annotations on fields
		fmt.Printf("Tag--> myTag1:%#v, myTag2:%#v, das:%#v\n",
			tag.Get("myTag1"), tag.Get("myTag2"), "" != tag.Get("das"))
	}

	//Logging the methods on ptr
	for i := 0; i < typPtr.NumMethod(); i++ {
		fmt.Printf("Methods: %#v\n", typPtr.Method(i))
	}

	//Logging the methods on value
	for i := 0; i < typ.NumMethod(); i++ {
		fmt.Printf("Methods: %#v\n", typ.Method(i))
	}
}

func DataCreationAndCodeInvocation() {

	//Creates a Value out of the given data (Value holds a pointer to the data)
	contactPtrValue := reflect.New(reflect.TypeOf(Contact{}))

	//Need to call Elem otherwise the value will work on pointer and which is not what we want
	//We need to work on the data. (Or in other words we will be reflecting on the pointer if
	//we are not calling the Elem().)
	contactValue := contactPtrValue.Elem()

	//Getting a field and setting the same
	nameFld := contactValue.FieldByName("Name")
	nameFld.SetString("Dummy Contact")

	phoneFld:= contactValue.FieldByName("Phone")
	phoneFld.SetString("987544")

	//I know it upfront that this field is not settable
	//If we dont know whether a field is setttable or not use CanSet always
	idFld := contactValue.FieldByName("id")
	canSet := idFld.CanSet()
	if canSet {
		idFld.SetUint(100)
	} else {
		//The below mentioned code is not possible
		// Refer: https://groups.google.com/d/msg/golang-nuts/ppGGazd9KXI/iARA-HD8ppwJ
		//fmt.Println(idFld.Type().Name() + " is not settable")
		//fmt.Println("Switching to set via pointer")
		//idPtrMem := unsafe.Pointer(contactValue.UnsafeAddr())
		//idPtr := (**uint32)(idPtrMem)
		//**idPtr = (uint32(100))
		//**idPtrMem = (uint32(100))
		//fmt.Printf("value cannot be set if not exported\n")
	}

	//Getting the Methods binded to the contact value object and invoking it
	{
		fmt.Println("Calling InterfaceB->B() on Value")
		//intrFc := contactValue.Interface()
		methBOnValue, _ := contactValue.Type().MethodByName("B")
		//Need to pass the struct instance even though the signature says
		// none in InterfaceB->B(). That's how the struct is available as the
		//local variable in methods
		values := methBOnValue.Func.Call([]reflect.Value{contactValue})
		fmt.Printf("%#v\n", values[0].String())

		fmt.Println("Calling InterfaceA->A() on Value")
		methAOnValue, exists := contactValue.Type().MethodByName("A")
		if exists {
			values = methAOnValue.Func.Call([]reflect.Value{contactPtrValue})
			fmt.Printf("%#v\n", values[0].String())
		} else {
			fmt.Println("InterfaceA->A() doesn't exist on Value obj")
		}
	}


	//Getting the Methods binded to the contact pointer and invoking it
	{
		fmt.Println("Calling InterfaceA->A() on Ptr")
		methAOnPtr, _ := contactPtrValue.Type().MethodByName("A")
		//Need to pass the struct instance even though the signature says
		// none in InterfaceB->B(). That's how the struct is available as the
		//local variable in methods
		valuesA := methAOnPtr.Func.Call([]reflect.Value{contactPtrValue})
		fmt.Printf("%#v\n", valuesA[0].String())

		fmt.Println("Calling InterfaceB->B() on Ptr")
		methBOnPtr, _ := contactPtrValue.Type().MethodByName("B")
		//Need to pass the struct instance even though the signature says
		// none in InterfaceB->B(). That's how the struct is available as the
		//local variable in methods
		valuesB := methBOnPtr.Func.Call([]reflect.Value{contactPtrValue})
		fmt.Printf("%#v\n", valuesB[0].String())
	}



}

ContactManager – A rest API and its data access layer in Golang

A model of our contact table represented in structs.

package model

type Contact struct {
	Id int64 `json:"id, omitempty"`
	Name string `json:"name"`
	Phone string `json:"phone"`
}

Data access layer

package dal

import(
	"fmt"
	"database/sql"
	_ "github.com/mattn/go-sqlite3"
	"contactmgr-persis/model"
)


type ContactRepo interface {
	Create() int64
	GetAll() []*model.Contact
}

type ContactRepoSqlite struct {}

func (repo *ContactRepoSqlite) Create(c *model.Contact) int64 {
	db, err := sql.Open("sqlite3", "./contactmgr.db")
	checkErr(err)

	defer db.Close()

	stmt, err := db.Prepare("insert into contact (name, phone) values(?,?)")
	checkErr(err)

	res, err := stmt.Exec(c.Name, c.Phone)
	checkErr(err)

	defer stmt.Close()

	id, err := res.LastInsertId()
	checkErr(err)

	fmt.Printf("Record inserted. Id :%v \n", id)

	c.Id = id
	return id;
}

func (repo *ContactRepoSqlite) GetAll() []*model.Contact {
	db, err := sql.Open("sqlite3", "./contactmgr.db")
	checkErr(err)

	defer db.Close()

	checkErr(err)
	rows, err := db.Query("select * from contact")

	contacts := make([]*model.Contact, 0)

	for rows.Next() {
		contact := &model.Contact{}
		err := rows.Scan(&contact.Id, &contact.Name, &contact.Phone)
		checkErr(err)
		contacts = append(contacts, contact)
	}

	defer rows.Close()

	return contacts

}

func checkErr(err error) {
	if nil != err {
		panic(err)
	}
}

func init() {
	db, err := sql.Open("sqlite3", "./contactmgr.db")
	checkErr(err)

	defer db.Close()

	createStmt := "create table if not exists contact(" +
		"id integer primary key autoincrement, " +
		"name text not null," +
		"phone text not null)"
	stmt, err := db.Prepare(createStmt)
	checkErr(err)

        defer stmt.Close()

	_, err = stmt.Exec()
	checkErr(err)

}

Hope you have noticed that our project name is contactmgr-persis and we have two packages model and dal.

Also this project should be under $GOPATH/src.

Now for API we have another project contactmgr-api in the above mentioned path

API main package

package main

import(
	"net/http"
	"os"
	"fmt"
	"strings"
	"encoding/json"
	"contactmgr-persis/model"
	"contactmgr-persis/dal"
)

func main(){
	fmt.Println(os.Args[1])
	http.HandleFunc("/contact", func(w http.ResponseWriter, r *http.Request) {
		if strings.EqualFold("GET", r.Method) {
			encoder := json.NewEncoder(w)
			w.WriteHeader(http.StatusCreated)
			contactRepo := &dal.ContactRepoSqlite{}
			encoder.Encode(contactRepo.GetAll())
		} else if strings.EqualFold("POST", r.Method) {
			decoder := json.NewDecoder(r.Body)
			var contact model.Contact
			decoder.Decode(&contact)
			fmt.Printf("%#v", contact)
			contactRepo := &dal.ContactRepoSqlite{}
			contactRepo.Create(&contact)
			fmt.Fprintf(w, fmt.Sprintf(":%#v", contact))
		} else {
			w.WriteHeader(http.StatusMethodNotAllowed)
			return
		}
	})

	http.HandleFunc("/", func(w http.ResponseWriter, r *http.Request) {
		if strings.EqualFold("GET", r.Method) {
			fmt.Fprintf(w, "Hello, Web")
		} else {
			w.WriteHeader(http.StatusNotFound)
		}
	})

	http.ListenAndServe(fmt.Sprintf(":%v",os.Args[1]), nil)
}

Inorder to run the project do go install on contactmgr-persis and then go build on contactmgr-api then run the api application by giving the port as program argument. Ex : ./contactmgr-api 8080

Edit : do a go get github.com/mattn/go-sqlite3 and go install for the same to get the sqlite driver