Basic types, definitions, and functions

Basic Data Types

Type inference

• Types of identifiers are inferred, not declared
• A distinguishing feature of OCaml
• Reconciles the flexibility of untyped languages with the safety of typed languages
• A very rich type system
• Polymorphic types provide additional flexibility

Integers

• Type: int
• Values: $-2^{62}$ to $2^{62}-1$ (on 64-bit architectures)
• Arithmetic operators: +, -, *, /
• Calculations are performed modulo $2^{63}$
• / is the integer division: 7/2 = 3
• mod is integer remainder: 7 mod 2 = 1

Booleans

• Type: bool
• Values: true and false
• Boolean operators: &&, ||, not
• Comparision operators: <, >, =, <=, >=
• Negation is not; and unlike other programming languages, ! is wrong
• Conjunction is &&; "&" used to be supported but has been removed from OCaml
• Conjunction is &&; "and" has a different meaning
• We can only compare values of the same type
• 5.0 > "hello";; $\rightarrow$ Error
• (7.56 <= 8e32) && (6>-3);; $\rightarrow$ true

Exercise: Boolean operations

• Select valid expressions that evaluate to false
• !true $\rightarrow$ ! isn't a negation operator
• !!false $\rightarrow$ ! isn't a negation operator
• not true
• not not false $\rightarrow$ not is a unary function
• not (not false)
• Select the syntactically valid expressions that do not use deprecated operators
• true and false $\rightarrow$ and has a completely different meaning
• true && false
• true & false $\rightarrow$ deprecated
• false or false $\rightarrow$ deprecated
• false | false $\rightarrow$ ! has a completely different meaning
• true || false
• What is result of compiling and evalutating: false and true? $\rightarrow$ Syntax error
• What is result of compiling and evalutating: not false || true? $\rightarrow$ true
• What is result of compiling and evalutating: 1<2 && 2<>3? $\rightarrow$ true (<> means "not equals")
• What is result of compiling and evalutating: true>false? $\rightarrow$ true
• What is result of compiling and evalutating: 1=true? $\rightarrow$ Type error
• What is result of compiling and evalutating: 1<2<3? $\rightarrow$ Type error (comparision between bool and int: true<3)
• What is result of compiling and evalutating: true=1 && not (3=4)? $\rightarrow$ Type error
• What is result of compiling and evalutating: false<=0 && 3<=4? $\rightarrow$ Type error
• What is result of compiling and evalutating: true<>false && 3<>4? $\rightarrow$ Type error
• What is result of compiling and evalutating: true=1 && not (3=4)? $\rightarrow$ Type error
• What is result of compiling and evalutating: not (true>=false) || 3=4? $\rightarrow$ false
• What is result of compiling and evalutating: (not true)>=false || 3=4? $\rightarrow$ true
• What is result of compiling and evalutating: not true>=false || 3=4? $\rightarrow$ true
• What is result of compiling and evalutating: 1=2=true? $\rightarrow$ false
• What is result of compiling and evalutating: false=1=2? $\rightarrow$ Type error

More data types

Floating-point arithmetic

• Type: float
• Values: Must be written with a decimal point, or exponential, or both
• Operations: +., -., *., /.
• Functions: sqrt, sin, cos, ceil, floor
• Floating-point constants must indicate that they are not integers, by using a decimal point or exponent
• Floating-point operations must be written with a dot (.)

Conversion between types

• Basic types are disjoint: no value belongs to two different basic types
• No implicit conversion between types
• Explicit conversion operations
• Background: Implicit conversion would not go well with type inference

Conversion of floating-point to integer

• Conversion functions in both directions
• float_of_int: int $\rightarrow$ float
• int_of_float: float $\rightarrow$ int
• Function application: write the name of the function followed by the argument
• Use paranthesis only when necessary to denote structure

Characters

• Type: char
• Values: 256 characters, numbered from 0 to 255
• Can be written like 'a', '\087', etc.
• Conversion functions
• Char.chr: int $\rightarrow$ char
• Char.code: char $\rightarrow$ int
• Char.code 'A';; $\rightarrow$ int = 65

Strings

• Type: String
• Values: Character strings, written like "Hello, World!"
• Operator ^ is used for string concatenation
• Many functions like:
• String.length: string $\rightarrow$ int
• int_of_string: string $\rightarrow$ int
• float_of_string: string $\rightarrow$ float
• Strings, Characters, Floats, Booleans, Integers are all disjoint
• We must use explicit conversion functions
• Positions in string are numbered from 0 to its length minus 1
• String.get "abcdef" 1;; $\rightarrow$ char = 'b'

Exercise: Floating-point constants

• 1.5 *. 1e3 $\rightarrow$ 1500.

• 1.5 *. 1000. $\rightarrow$ 1500.

• 1.5 *. 1000 $\rightarrow$ Type error

• 1.5 *. "1e3" $\rightarrow$ Type error

• 1.5 * 1000. $\rightarrow$ Type error

• 1.5e3 $\rightarrow$ 1500.

• 1000. +. 500. /. 2. $\rightarrow$ 1250.

• 1.5e3 <= 1500. && 1500 <= 1500 && false <= true $\rightarrow$ true

• 1500 < 1500.1 $\rightarrow$ Type error

• floor 1500.1 = 1500 $\rightarrow$ Type error

• 10. /. 3. *. 3. $\rightarrow$ 10.

• sqrt 16. +. 9. $\rightarrow$ 13.

Expressions

Expressions

• Expressions compute values
• Expressions play a prime role in functional programming
• Very rich language of expressions

Exercise: Boolean expressions

• 1. <> 2.5 && 3 <> 4 $\rightarrow$ true
• 1 <= int_of_float 2.5 && 3. <= floor 3.5 $\rightarrow$ true
• not 1. = 2. || not 3 = 4 $\rightarrow$ Type error (there should be brackets as not (1. = 2.))
• 1 <= 2.5 && 3 <= 4.5 $\rightarrow$ Type error

Conditional expressions

• if ... then ... else is an expression, not an instruction
• type is the type of expressions in the then and else, which must be the same
• Pitfall: default value in case of a missing else

Exercise: Conditional expressions

• if 1=2 then "abc" else "def";; $\rightarrow$ def
• if 1=2 then 3 else 4.5;; $\rightarrow$ Type error
• if (1<>2) then 3 else 4;; $\rightarrow$ 3
• if 1 then 2 else 3;; $\rightarrow$ Type error
• if 1=2 then 34 else "56";; $\rightarrow$ Type error
• if 1<"2" then 3.4 else 5.6;; $\rightarrow$ Type error
• if "Amazone" < "Amour" then 3.4 else 5.6;; $\rightarrow$ 3.4
• if 0 then 1 else 2;; $\rightarrow$ Type error
• 1 + (if 2=3 then 4. else 5.) $\rightarrow$ Type error
• if (if 1=2 then 3 else 4)<>5 then 6 else 7;; $\rightarrow$ 6
• if 1<>2 then (if 3<>4 then 6 else 7) else 8;; $\rightarrow$ 6
• 1 + (if 2=3 then 4 else 5) $\rightarrow$ 6
• if 1<>2 then if 3=4 then 'a' else 'b' else 'c' $\rightarrow$ b
• if 1=2 then (if 3=4 then 'a' else 'b') else (if 'c'<>'d' then 'e' else 'f') $\rightarrow$ e
• if 1=2 then if 3=4 then 5 else 6 else if 'a'<>'b' then 'c' else 'd' $\rightarrow$ b


In [3]:

if 1<2 then 6+7 else 67/23;;

(if 6=3+3 then 3<4 else 8>7) && 67.8>33.1;;

if (if 1=1 then 2=2 else 4.0>3.2) then 2<3 else 3<2;;




Out[3]:

- : int = 13

Out[3]:

- : bool = true

Out[3]:

- : bool = true




In [4]:

if 6=8 then 1 else 77.5;; (* Error *)




Out[4]:

File "[4]", line 1, characters 19-23:
Error: This expression has type float but an expression was expected of type
int
Characters 19-23:
if 6=8 then 1 else 77.5;; (* Error *)
^^^^



Function application

• The type of a function with n arguments is: type-arg_1 -> type-arg_2 -> ... -> type-arg_n -> type-result
• To apply a function f to n arguments: f exp_1 .. exp_n


In [1]:

String.get;;
String.get (string_of_int 65) (int_of_string "0");;




Out[1]:

- : string -> int -> char = <fun>

Out[1]:

- : char = '6'



Expression pitfalls

• Local definitions can be used to cut large expressions into pieces
• Functions may be under-supplied with arguments
• f(e1, e2) is not an application of f to two arguments
• The operator for checking equality of values is "="

Polymorphic operators

• Operators have an infix syntax, like (3+5)*5
• Operators like functions, always have a type: + : int -> int-> int
• Some operators have polymorphic type: > : 'a -> 'a -> bool
• Polymorphic types contain type variables indicated by an initial quote
• 'a reads alpha, 'b reads beta
• Type variables can be instantiated by any type

Definitions

Global definitions

• Give names to values
• Global definitions are effective for the rest of the toplevel session
• Syntax: let name = expression
• There is no separate declaration of identifier
• Once set, the value of an identifier never changes
• Once defined, an identifier can be used in expressions

Local definitions

• Naming with a delimited scope
• Syntax: let name = exp1 in exp2
• Here, the scope of name is exp2
• A local definition may temporarily hide a more global one


In [8]:

let x = 4+5 in 2*x;;
x;; (* Error *)




Out[8]:

- : int = 18

Out[8]:

File "[8]", line 2, characters 0-1:
Error: Unbound value x
Characters 21-22:
x;; (* Error *)
^




In [12]:

let x = 17;;

x;;

let y = x+1 in y/3;;

let x = 4 in
let y = x+1 in
let x = 2*y in x
;;

let x = 4 in
(let x = 17 in x+1) + x
;;




Out[12]:

val x : int = 17

Out[12]:

- : int = 17

Out[12]:

- : int = 6

Out[12]:

- : int = 10

Out[12]:

- : int = 22



Simultaneous definitions

• let x = e : e is evaluated wrt the value bindings before the let
• let x1 = e1 and x2 = e2 : both expressions are evaluated wrt the value bindings before the let
• The above let binding is same as let x2 = e2 and x1 = e1
• Works with both global and local definitions


In [14]:

let x = 1;;

(* sequential definitions *)
let x = 2 in
let y = x+1 in  (* y = 2+1 *)
x*y           (* 2*3 *)
;;

(* simultaneous definitions *)
let x = 2 and
y = x+1 in      (* y = 1+1 *)
x*y           (* 2*2 *)
;;




Out[14]:

val x : int = 1

Out[14]:

- : int = 6

Out[14]:

- : int = 4



Exercise: Definitions



In [45]:

(* Integer identifiers
*
* Suppose a variable x exists and is an integer.
* Define a variable x_power_8 that uses 3 multiplications
* to calculate x power of 8. The only function you're allowed
* to call is the * operator.
*)

(* The given prelude *)
let a = Random.int 9 + 1;;

let x_power_8 x =
let x1 = x*x in
let x2 = x1*x1 in
x2*x2
;;

x_power_8 a;;

(* Alternate recursive solution using 1 multiplication only *)
let x_power_8_rec n =
let rec aux idx =
if idx = 8
then
1
else
n * aux(idx+1)
in
aux 0
;;

x_power_8_rec a;;




Out[45]:

val a : int = 7

Out[45]:

val x_power_8 : int -> int = <fun>

Out[45]:

- : int = 5764801

Out[45]:

val x_power_8_rec : int -> int = <fun>

Out[45]:

- : int = 5764801




In [47]:

(* String identifiers
*
* Suppose that a variable word exists and is a string.
* Define a variable sentence that uses 5 string concatenations
* to create a string containing 9 times word, separated by commas
*)

let word = "foo";;

let x =
word ^ ",";;

let sentence =
let x1 = x ^ x ^ x in
let x2 = x1 ^ x1 in
x2 ^ x1
;;




Out[47]:

val word : string = "foo"

Out[47]:

val x : string = "foo,"

Out[47]:

val sentence : string = "foo,foo,foo,foo,foo,foo,foo,foo,foo,"



Functions

Defining functions

• Global definition of a function with one argument: let f x = exp
• Local definition of a function with one argument: let f x = exp1 in exp2
• Scoping rules as before: local definitions hide more global ones
• Application of function named f to expression e: f e
• Parantheses indicate structure of expressions


In [16]:

let f x = x+1;;  (* global definition *)

f 17;;

let g y = 2*y in   (* local definition *)
g 42
;;




Out[16]:

val f : int -> int = <fun>

Out[16]:

- : int = 18

Out[16]:

- : int = 84




In [17]:

f f 1;;




Out[17]:

File "[17]", line 1, characters 0-1:
Error: This function has type int -> int
It is applied to too many arguments; maybe you forgot a ;'.
Characters 0-1:
f f 1;;
^




In [18]:

f (f 1);;




Out[18]:

- : int = 3



Lexical scoping

• Lexical scoping: Identifier used in the definition of a function refers to the identifier visible at the moment of function definition
• Dynamic scoping: Visible at the moment of function invocation


In [22]:

(* with local definition *)
let f x = x+1 in
let g y = f (f y) in
let f x = 2*x in
g 5
;;

(* with global definitions *)
let f x = x+1;;
let g y = f (f y);;
let f x = 2*x;;
g 5;;




File "[22]", line 4, characters 8-9:
Warning 26: unused variable f.

Out[22]:

- : int = 7

Out[22]:

val f : int -> int = <fun>

Out[22]:

val g : int -> int = <fun>

Out[22]:

val f : int -> int = <fun>

Out[22]:

- : int = 7



Identifiers are not variables

• An identifier may be hidden by a new definition for the same name
• Not to be confused with changing value of a variable
• Static binding can give us indirect access to an otherwise hidden identifier


In [34]:

(* Lexical scoping *)
let a = 1;;
let f x = x+a;;
f 2;;

let a = 73;;
f 2;;




Out[34]:

val a : int = 1

Out[34]:

val f : int -> int = <fun>

Out[34]:

- : int = 3

Out[34]:

val a : int = 73

Out[34]:

- : int = 3



Exercise: Functions



In [1]:

(*
* Simple functions: integer
*)

let multiple_of n d =
if n mod d = 0 then true else false
;;

multiple_of 2 10;;

let integer_square_root n =
int_of_float (sqrt (float_of_int n))
;;

integer_square_root 16;;




Out[1]:

val multiple_of : int -> int -> bool = <fun>

Out[1]:

- : bool = false

Out[1]:

val integer_square_root : int -> int = <fun>

Out[1]:

- : int = 4




In [4]:

(*
* Simple functions: string
*)

let last_character str =
String.get str ((String.length str)-1)
;;

last_character "ANI";;

let string_of_bool truth =
if truth then "true" else "false"
;;

string_of_bool false;;




Out[4]:

val last_character : string -> char = <fun>

Out[4]:

- : char = 'I'

Out[4]:

val string_of_bool : bool -> string = <fun>

Out[4]:

- : string = "false"



Recursion

Recursive functions

• Functions that are defined by calling itself on smaller arguments
• Natural on recursively defined data structures
• Example: $fact(n) = \begin{cases} 1 & if x=1 \\ n \times fact(n-1) & if x>1 \end{cases}$

Recursive definitions in OCaml

• A priory, the use of f in a definition of f refers to the previous value of f
• The keyword rec changes this, and allows us to define a function by recursion


In [36]:

(* Stupid recursion *)
let x = 1;;
let x = x+1;;
x;;

let f x = x+1;;
let f x = f (f x);;
f 1;;

(* Recursive recursion *)
let rec fact n =
if n <= 1 then 1 else n*fact(n-1)
;;

fact 10;;




Out[36]:

val x : int = 1

Out[36]:

val x : int = 2

Out[36]:

- : int = 2

Out[36]:

val f : int -> int = <fun>

Out[36]:

val f : int -> int = <fun>

Out[36]:

- : int = 3

Out[36]:

val fact : int -> int = <fun>

Out[36]:

- : int = 3628800



Mutually recursive functions

• Generalization of direct recursion
• Several functions are defined by calling each other on smaller arguments
• Natural on mutually recursive data structures


In [40]:

let rec even x =
if x=0 then true else odd(x-1)
and
odd x =
if x=0 then false else even(x-1)
;;

even 17;;
even 24;;
odd 10;;
odd 15;;




Out[40]:

val even : int -> bool = <fun>
val odd : int -> bool = <fun>

Out[40]:

- : bool = false

Out[40]:

- : bool = true

Out[40]:

- : bool = false

Out[40]:

- : bool = true



Exercise: Recursion



In [26]:

(*
* Greatest Common Divisor
*)

let rec gcd m n =
if n=0
then
m
else
gcd n (m mod n)
;;

gcd 35 42;;

(*
* Multiple of
*)

let multiple_of n d = n mod d = 0;;

multiple_of 10 2;;

(*
* Multiple upto: int -> int -> bool
* Takes two non-negative integers n and r, and tells whether n admits
* at least one divisor between 2 and r, inclusive
*)

let rec multiple_upto n r =
if r=1
then
false
else
if multiple_of n r
then
true
else
multiple_upto n (r-1)
;;

multiple_upto 7 6;;

(*
* Is Prime?
*)

let is_prime n =
not (multiple_upto n (n-1))
;;

is_prime 37;;
is_prime 16;;




Out[26]:

val gcd : int -> int -> int = <fun>

Out[26]:

- : int = 7

Out[26]:

val multiple_of : int -> int -> bool = <fun>

Out[26]:

- : bool = true

Out[26]:

val multiple_upto : int -> int -> bool = <fun>

Out[26]:

- : bool = false

Out[26]:

val is_prime : int -> bool = <fun>

Out[26]:

- : bool = true

Out[26]:

- : bool = false




In [27]:

(*
* Consolidated is_prime function
*)

let is_prime n =
let multiple_of n d =
n mod d = 0
in
let rec multiple_upto n r =
if r=1
then
false
else
if multiple_of n r
then
true
else
multiple_upto n (r-1)
in
not (multiple_upto n (n-1))
;;

is_prime 17;;




Out[27]:

val is_prime : int -> bool = <fun>

Out[27]:

- : bool = true




In [35]:

(*
* Alternate version of multiple upto
* The function counts till root of the number for finding multiples
*)

let multiple_upto n r =
let rec aux idx =
if idx > int_of_float (sqrt (float_of_int r))
then
false
else
if n mod idx = 0
then
true
else
aux (idx+1)
in
aux 2
;;

multiple_upto 7 6;;
multiple_upto 8 7;;




Out[35]:

val multiple_upto : int -> int -> bool = <fun>

Out[35]:

- : bool = false

Out[35]:

- : bool = true

`