CS 3363 Ullman Ch 3

CS 3363 Organization of Programming Languages: 

CS 3363 Organization of Programming Languages Istvan Jonyer Ullman Chapter 3

Chapter 3:Defining Functions: 

Chapter 3: Defining Functions Functions are defined in the format fun andlt;identifierandgt; (andlt;parameter listandgt;) = andlt;expressionandgt;; Example: Upper (convert lower case to upper case) fun upper(c) = chr(ord(c)-32); val upper = fn : char  char Meaning of system response upper: name of function fn: it is a function (not ‘fun’, but ‘fn’) char  char : char input, returns char

Declaring Function Types: 

Declaring Function Types Notice: Our function did not have a type declaration fun upper(c) = chr(ord(c)-32); How does ML know that it should be char? What is the type here: fun square(x) = x * x; can be real and int By default, ML uses int val square = fn : int  int If we want real we must specify it: fun square(x:real) = x * x; val square = fn : real  real

Alternatively…: 

Alternatively… We could declare x as real as fun square(x) = (x:real) * x; val square = fn : real  real Note: We need the () around x:real fun square(x) = x:real * x; Error: unbound type constructor: x : has lower precedence than * ML will try to construct a type from 'real * x', since it knows real is type, and complains that x is not

Function Application: 

Function Application Example for square pi * square(radius); val it = 50.25 : real Parentheses are not required pi * square radius; val it = 50.25 : real ML applies a function to an expression F E Multiple arguments can be given using tuples exponent(x, 2) Currying (covered in chapter 5) exponent x 2

Function’s Precedence: 

Function’s Precedence Functions have the highest precedence square 4.0+3.0 val it = 19.0 : real; (not 49.0!) Evaluated as (square 4.0) + 3.0 Parenthesize: square (4.0+3.0) val it = 49.0 : real;

Multiple Arguments: 

Multiple Arguments 'Parameters' used in function definitions (formal) 'Arguments' are passed to functions (actual) Example, using tuples fun min3 (a:int, b, c) = if aandlt;b then if aandlt;c then a else c else if bandlt;c then b else c; val min3 = fn : int * int * int  int

Tuples as Arguments: 

Tuples as Arguments The argument was a tuple of 3 elements we can assign this to an identifier, and pass the identifier val t = (2,1,3); min3 t; or: min3(t); val it = 1: int

Referencing Externals: 

Referencing Externals Externals are visible to a function if they were declared before the function val x = 3; fun addx(a) = a + x; val x = 10; addx(2); val it = 5 : int In C, we would expect 12 Only ‘val x = 3;’ is visible to addx()

Environment: 

Environment

Recursive Functions: 

Recursive Functions ML allows recursive and mutually recursive definition of functions Encourages recursion in place of iteration Recursive definition of functions consist of Basis base case (trivial case) to solve Inductive step Non-base cases are reduced towards base case Example: Reversing a list fun reverse (L) = if L = nil then nil (* base case *) else reverse(tl(L)) @ [hd(L)]; (* induction *) val reverse = fn : ‘a list  ‘a list

Example: reverse [1,2,3]: 

Example: reverse [1,2,3] Trace execution of reverse([1,2,3]) [1,2,3] is associated with L (parameter) L is not nil, so reverse(tl(L)) is called reverse([2,3]) [2,3] is associated with L L is not nil, so reverse(tl(L)) is called reverse([3]) [3] is associated with L L is not nil, so reverse(tl(L)) is called reverse([]) [] is associated with L L is nil, so reverse returns nil reverses return: nil; []@[3]; [3]@[2]; [3,2]@[1]; [3,2,1]

Mutual Recursion: 

Mutual Recursion Functions are defined in terms of each other Example: Get alternate elements of list fun take(L) = if L = nil then nil else hd(L) :: skip(tl(L)) fun skip(L) = if L = nil then nil else take(tl(L)); Incorrect: Take cannot see skip skip is defined after take

Defining Mutual Recursion: 

Defining Mutual Recursion fun take(L) = if L = nil then nil else hd(L) :: skip(tl(L)) and skip(L) = if L = nil then nil else take(tl(L)); ML will delay binding skip until end of definition take([1,2,3,4,5]); val it = [1,3,5] : int list

In General…: 

In General… Any number of mutually recursive functions can be defined: fun andlt;definition of 1st functionandgt; and andlt;definition of 2nd functionandgt; and … and andlt;definition of nth functionandgt;;

How ML deduces types: 

How ML deduces types All operands of arithmetic operators must agree. (a+b)*2.0  a and b must be real All operands of comparisons must agree. aandlt;20  a must be an int In the if-then-else conditional, the consequents must have the same type. if (aandlt;b) then 2.0 else a  a and b must be real Arguments to functions must agree with parameters type, if declared. Functions may return known types. If all else fails, the default type is used (int).

Patterns in Function Definition: 

Patterns in Function Definition We may specify patterns as function parameters (formals) E.g.: x::xs (cons: first and rest of list) will match to any list argument fist of list will be assigned to x rest of list will be assigned to xs Multiple pattern are defined using | Example: reverse fun reverse(nil) = nil | reverse(x::xs) = reverse(xs)@[x]

Another Example: 

Another Example fun take nil = nil | take (x::xs) = x :: skip xs and skip nil = nil | skip (y::ys) = take ys;

Aliasing in Parameters: 

Aliasing in Parameters It is possible to give both an identifier and a pattern to parameters andlt;identifierandgt; as andlt;patternandgt; Example fun merge (nil, M) = M | merge (L, nil) = L | merge (L as x::xs, M as y::ys) = if x andlt; y then x::merge(xs, M) else y::merge(L,ys); val merge = fn : int list * int list  int list

Anonymous Variables: 

Anonymous Variables We can use wildcards in parameter lists at times we don’t care about some of the parameters use _ for anonymous variables fun pow(_, 0) = 1.0 | pow(x:real, i:int) = if odd(i) then x * pow(x, i div 2) * pow(x, i div 2) else pow(x, i div 2) * pow(x, i div 2); Anything to the power of 0 is 1

More Patterns: 

More Patterns So far we have seen nil, 0 x::xs, or x::y::xs Others list of lists fun sumLists(nil) = 0 | sumLists(nil::YS) = sumLists(YS) | sumLists((x::xs)::YS) = x+ sumLists(xs::YS); val sumLists = fn : int list list  int More patterns are discussed in chapter 5

How ML Matches Patterns: 

How ML Matches Patterns ML first decomposes patterns and expressions to trees, then matches the trees Decompose (x::y::zs, w) Remember: ‘::’ is right associative First, top-most constructor: (,) has 2 components: x::y::zs, and w Then x::y::zs treated as (x::(y::zs)) (right associative) Decompose ([1,2,3,4],5)

Tree of (x::y::zs, w): 

Tree of (x::y::zs, w) Match pattern ([1,2,3,4],5) (,) :: w x :: y zs (,) :: 5 1 :: 2 :: 3 :: 4 nil

let: 

let We can introduce local variables to functions using let val andlt;variableandgt; = andlt;expressionandgt; … in andlt;expressionandgt; end

Effect of let on Environment: 

Effect of let on Environment

Example: 

Example Raise x to the 100th power fun hundredthPower(x:real) = let val four = x*x*x*x; val twenty = four*four*four*four*four in twenty*twenty*twenty*twenty*twenty end; fun hundredthPower(x:real) = let val x = x*x*x*x; val x = x*x*x*x*x in x*x*x*x*x end;

Effect of let on Environment: 

Effect of let on Environment

Splitting Return Values: 

Splitting Return Values What if a function returns a tuple? e.g.: (3,4,5) val retVal = f(… Need to access elements of tuple as val a = #1(retVal) val b = #2(retVal) val c = #3(retVal) Better way: val (a,b,c) = f(… Values in tuple are assigned to a, b, and c

CS 3363 Organization of Programming Languages: 

CS 3363 Organization of Programming Languages End of Lecture