funcProg2

Information about funcProg2

Published on October 19, 2007

Author: Lindon

Source: authorstream.com

Content

Introduction to ML:  Introduction to ML CS 331 Principles of Programming Languages revised Spring 2003 Features of ML:  Features of ML A pure functional language serious programs can be written without using variables Widely accepted reasonable performance (claimed) can be compiled syntax not as arcane (or as simple) as LISP In these slides,:  In these slides, We use Standard ML of New Jersey Runs on PCs, Linux, and other flavors of UNIX Much of this material is based on Ullman’s book, Elements of ML Programming See the SML documentation at http://www.smlnj.org Running SML on linix.gl:  Running SML on linix.gl The SML processor is available at /afs/umbc.edu/users/n/i/nicholas/pub/331/smlnj.linux/bin or equivalently ~nicholas/../pub/331/smlnj.linux/bin Add this directory to your path, and do a rehash Then invoke sml from a shell prompt with the command sml Use control d to exit interpreter Hello, world in SML:  Hello, world in SML Standard ML of New Jersey, - print("Hello world\n"); Hello world val it = () : unit - Arithmetic in ML:  Arithmetic in ML Copy and paste the following text into a Standard ML window 2+2; (* note semicolon at end*) 3*4; 4/3; (* an error! *) 6 div 2; (* integer division *) 7 div 3; Declaring Constants:  Declaring Constants Constants are not exactly the same as variables they can be redefined, but existing uses of that constant (e.g. in function definitions) aren’t affected by such redefinition val freezingFahr = 32; Ints and Reals:  Ints and Reals Int.abs ~3; Int.sign ~3; Int.max (4, 7); Int.min (~2, 2); real(freezingFahr); Math.sqrt real(2); Math.sqrt(real(2)); Math.sqrt(real 3); Note ~ is unary minus min and max take just two input arguments, but that can be fixed! The real operator converts to real Parens can sometimes be omitted, but I don’t recommend it Slide9:  - Int.abs ~3; val it = 3 : int - Int.sign ~3; val it = ~1 : int - Int.max (4, 7); val it = 7 : int - Int.min (~2, 2); val it = ~2 : int - Math.sqrt real(2); stdIn:57.1-57.18 Error: operator and operand don't agree [tycon mismatch] operator domain: real operand: int -> real in expression: Math.sqrt real - Math.sqrt(real(2)); val it = 1.41421356237 : real - Math.sqrt(real 3); val it = 1.73205080757 : real Strings:  Strings Delimited by double quotes the caret mark ^ is used for string concatenation, e.g. “house”^”cat” \n is used for newline, as in C and C++ Comparison Operators:  Comparison Operators The usual <, >, <=, >= and <> are available For reals, = and <> are not available For reals a and b, a <= b andalso a>= b is an equality test The connectors “andalso” and “orelse” are logical operators with short-circuit evaluation If Then Else:  If Then Else If Then Else is an expression, not a control structure Example, if quotient, dividend and divisor are reals, we might have val quotient = if divisor > 0 then dividend/divisor else 0 Tuples:  Tuples Tuples are data items drawn from a Cartesian product type. Example: type fraction = int * int; val foo: fraction = (44,100); #1(foo); (* returns 44 *) #2(foo); (* returns 100 *) Tuples are of fixed size, e.g. 2 in this example Lists in ML:  Lists in ML Objects in a list must be of the same type [1,2,3]; [“dog”, “cat”, “moose”]; The empty list is written [] or nil Making Lists:  Making Lists The @ operator is used to concatenate two lists of the same type The :: operator makes a new list in which its first operand is the new first element of a list which is otherwise like the second operand. The functions hd and tl give the first element of the list, and the rest of the list, respectively List Operations:  List Operations - val list1 = [1,2,3]; val list1 = [1,2,3] : int list - val list2 = [3,4,5]; val list2 = [3,4,5] : int list - [email protected]; val it = [1,2,3,3,4,5] : int list - hd list1; val it = 1 : int - tl list2; val it = [4,5] : int list More List Operations:  More List Operations - val list1 = [1,2,3]; val list1 = [1,2,3] : int list - val list2 = [3,4,5]; val list2 = [3,4,5] : int list - 4::list1; val it = [4,1,2,3] : int list - val list3 = list1::list2; an error! - val [email protected]; val list3 = [1,2,3,3,4,5] : int list - length(list3); val length(list3) = 6 Strings and Lists:  Strings and Lists The explode function converts a string into a list of characters The implode function converts a list of characters into a string Examples: - explode("foo"); val it = [#"f",#"o",#"o"] : char list - implode [#"c",#"a",#"t"]; val it = "cat" : string - Heads and Tails:  Heads and Tails The cons operator :: takes an element and prepends it to a list of that same type. For example, the expression 1::[2,3] results in the list [1,2,3] What’s the value of [1,2]::[ [3,4], [5,6]] ? What’s the value of x::[], for any atom x? Declaring Functions:  Declaring Functions A function takes an input value and returns an output value ML will figure out the types Notes :  Notes ML is picky about not mixing types, such as int and real, in expressions The value of “it” is always the last value computed Function arguments don’t always need parentheses, but it doesn’t hurt to use them Types of arguments and results:  Types of arguments and results ML figures out the input and/or output types for simple expressions, constant declarations, and function declarations If the default isn’t what you want, you can specify the input and output types, e.g. fun divBy2 x:int = x div 2 : int; fun divideBy2 (y : real) = y / 2.0; divBy2 (5); divideBy2 (5.0); Two similar divide functions:  Two similar divide functions - fun divBy2 x:int = x div 2 : int; val divBy2 = fn : int -> int - fun divideBy2 (y : real) = y / 2.0; val divideBy2 = fn : real -> real - divBy2 (5); val it = 2 : int - divideBy2 (5.0); val it = 2.5 : real - Functions and Patterns:  Functions and Patterns Recall that min and max take just two arguments However, using the fact that, for example, min(a, b, c) = min(a, min(b, c)) Generalizing Min:  Generalizing Min An example of ML pattern matching the cons notation x::xs is both a binary constructor and a pattern cases aren’t supposed to overlap Note that lists of any size are supported but the elements are expected to be integers checking that the rest of the list is non-empty is critical - but why? Slide26:  (* Sample ML program - MinList *) (* Takes a list of integers as input, and returns a list with at most one element, i.e. the smallest element in the list *) fun MinList([]) = [] | MinList(x::xs) = if null(xs) then [x] else [Int.min(x,hd(MinList(xs)))]; MinList([]); MinList([1,2]); MinList([315, 41, 59, 265, 35, 897]); When we run MinList,…:  When we run MinList,… - use "MinList.sml"; [opening MinList.sml] val MinList = fn : int list -> int list val it = [] : int list val it = [1] : int list val it = [35] : int list val it = () : unit Building trees:  Building trees It’s easy to build recursive data types in ML Some examples follow Slide29:  (* Sample ML program - Abstract Syntax Trees *) (* Declare the ast datatype *) datatype ast = empty | leaf of int | node of string*ast*ast; fun traverse(empty) = print "empty tree" | traverse(leaf(n)) = (print (Int.toString(n)); print " ") | traverse(node(operator, left, right)) = ( traverse(left); print operator; traverse(right)); fun prefix(tree:ast) = (traverse(tree); print "\n"); prefix(empty); prefix(leaf(4)); prefix(node("*",node("+",leaf(5),leaf(3)),node("-",leaf(10),leaf(4)))); Two ways to count:  Two ways to count (* count from i to j *) fun countUp(i:int, j:int) = if i=j then print(" "^Int.toString(j)) else (countUp(i,j-1);print(" "^Int.toString(j))); (* count from i to j *) fun TcountUp(i:int, j:int) = if i=j then print(" "^Int.toString(j)^"\n") else (print(" "^Int.toString(i));TcountUp(i+1,j)); What about control structures?:  What about control structures? Well, there aren’t any in the usual (procedural) sense If then else, case, and iteration are all accomplished by evaluation of expressions Iteration vs. Recursion:  Iteration vs. Recursion (* note that F is a functional parameter *) fun loopIt(i:int,n:int,F) = if i = n then F(i) else let val dummy = F(i) val dummy2 = loopIt(i+1,n,F) in dummy2 (* any expression could be used *) end; The Print Function:  The Print Function print(“This string\n”); print(“2+2 is “^Int.toString(2+2)^”\n”); Expressions may be grouped with parentheses, e.g (print(“a”);print(“b”)) But the grouped expressions may not change the environment, so this is not the same as a block in a procedural language More About I/O:  More About I/O To access functions in the TextIO structure, open TextIO; To open a file openIn(“somefile”); The value returned is of type instream endOfStream(file:instream): bool inputN(file:instream,n:int):string input(file:stream):string (* whole file *) Matches and Functions:  Matches and Functions Example of match expression: val rec reverse = fn nil => nil| x::xs => reverse(xs) @ [x]; The rec keyword stands for “recursive”, which is necessary because the binding of reverse as a function name is not yet established Anonymous Functions:  Anonymous Functions Functions don’t have to have names, e.g. (fn x => x+1) (3) yields 4 Such functions can be passed as parameters, e.g. for use in the map or reduce functions, to be discussed later in this chapter. If Then Else = Case:  If Then Else = Case The familiar if E1 then E2 else E3 is equivalent to case E1 of true => E2 | false => E3 Example: if x<y then #”a” else #“b” is the same as case x<y of true => #”a” | false => #“b” (* note same types *) Exceptions:  Exceptions exception Foo and Bar; raise Foo; exception Foo of string; The handle clause matches exceptions with (hopefully) suitable actions Exceptions can be defined in let clauses Polymorphic Functions:  Polymorphic Functions If you don’t know the type in advance, or if it doesn’t matter, ‘a list matches a list of any type Example: fun listLen(x: ‘a list) = if x = nil then 0 else 1+listLen(tl(x)); Higher Order Functions:  Higher Order Functions Functions may be passed as parameters,e.g. fun trap(a,b,n,F)= if n <= 0 orelse b-a <= 0.0 then 0.0 else let val delta = (b-a)/real(n) in delta*(F(a)+F(a+delta))/2.0+ trap(a+delta,b,n-1,F) end; Higher-Order Function map:  Higher-Order Function map The map function map(F,[a1,a2,…,an]) produces the list [F(a1),F(a2),…,F(an)] The function may be defined (per Harper’s new ML book) fun map f nil = nil | map f (h::t) = (f h)::(map f t) Higher-Order Function reduce:  Higher-Order Function reduce The reduce function reduce(F,[a1,a2,…,an]) produces F(a1,F(a2,F(…,F(an-1, an)…))) The reduce function may be implemented as follows (from Ullman) exception EmptyList; fun reduce (F, nil) = raise EmptyList | reduce (F, [a]) = a | reduce (F, x::xs) = F(x, reduce(F,xs)); More on reduce:  More on reduce Harper gives a more general form of reduce fun reduce (unit, opn, nil) = unit | reduce (unit, opn, h::t) = opn(h, reduce (unit, opn, t)) Example: two ways to sum a list of numbers fun add_up nil = 0 | add_up(h::t) = h + add_up t or fun add_up alist = reduce (0, op +, alist) The op keyword allows + to be a parameter More on reduce:  More on reduce To avoid passing unit and opn as parameters that don’t change, again from Harper’s book, fun better_reduce (unit, opn, alist) = let fun red nil = unit | red (h::t) = opn(h, red t)) in red alist end We have less overhead by passing only those parameters that change More on reduce:  More on reduce “Staging” helps even more! Again from Harper fun staged_reduce (unit, opn) = let fun red nil = unit | red (h::t) = opn(h, red t)) in red end We can use staged_reduce on many lists, e.g. reduce(unit, opn, alist) is the same as (but slower than) staged_reduce(unit, opn) alist Higher-Order Function filter:  Higher-Order Function filter The filter function takes a predicate P and a list [a1,a2,…,an] and returns the sublist such that P is true for every element of the sublist To implement filter fun filter(P, nil) = nil | filter(P, x::xs) = if P x then x::filter(P,xs) else filter(P,xs) The ML Type System:  The ML Type System Basic types include int, real, string, char, bool, and others Tuple types, e.g. int*real*char Function types, e.g. int->bool Type constructors list and option int list char option Creating Names for Types:  Creating Names for Types type orderpair = int*int type finiteSequence = real list; and these can be parameterized Datatypes:  Datatypes Enumerated types, e.g. datatype berryType = raspberry | blueberry | blackberry; So then we can say, for example, val b:berryType = raspberry; Recursive Datatypes:  Recursive Datatypes Example: binary trees, where the values may be of some type ‘label: datatype ‘label btree = Empty | Node of ‘label * ‘label btree * ‘label btree val inBinary: int btree = Node(5,Node(1,Empty,Empty),Empty) ASTs Revisited:  (* Sample ML program - Abstract Syntax Trees *) (* Assume that terminalType and nonterminalType already known *) (* Declare the ast datatype *) datatype ast = empty | leaf of terminalType | node of nonterminalType*(ast list); fun traverse(empty) = print "empty tree" | traverse(leaf(t)) = (printTerminal t; print " ") | traverse(node(nt, []) = printNonterminal(nt) | traverse(node(nt, x::xs)) = (printNonterminal(nt); traverse(x); traverseList(xs)) and fun traverseList([]) = print “ “ | traverseList(x::xs) = (traverse(x); traverseList(xs)); ASTs Revisited Record Structures:  Record Structures Records are wrapped in curly braces, and fields are separated by commas Field names may be used to refer to specific elements of the record Record Example:  Record Example - type addressType = {street:string, city:string, zip:int}; type addressType = {city:string, street:string, zip:int} (note that SML sorted the fields alphabetically) - val umbc:addressType = {street="1000 Hilltop Circle", city="Baltimore",zip=21250}; val umbc = {city="Baltimore",street="1000 Hilltop Circle", zip=21250} : addressType - #city(umbc); val it = "Baltimore" : string Pattern Matching in Records:  Pattern Matching in Records Pattern matching works, as in x as {street=xstr,city=xcity,zip=xzip}::xs If we don’t care about all the fields, use an ellipsis, e.g. x as {street=xstr,…}::xs Or even x as {city,…} Arrays:  Arrays open Array; val zeroVector = array(100,0); sub(zeroVector,0) is zero, as is sub(zeroVector,99) update(zeroVector,2,3.14) changes the third element of the (now misnamed) zeroVector Case Studies:  Case Studies Hash tables Make an array of hash buckets, each bucket containing a simple list of values Triangularization of a matrix If the array has m rows and n columns, make an array of m elements, each element being an array of n elements.

Related presentations


Other presentations created by Lindon

Databases
16. 10. 2007
0 views

Databases

wolbring1
08. 05. 2008
0 views

wolbring1

Occupational Noise
08. 05. 2008
0 views

Occupational Noise

Paper22
07. 05. 2008
0 views

Paper22

malignant hyperthermia
02. 05. 2008
0 views

malignant hyperthermia

mastitis
02. 05. 2008
0 views

mastitis

Chapter 3 lecture
02. 05. 2008
0 views

Chapter 3 lecture

habil final
02. 05. 2008
0 views

habil final

BIOSEC PDR
02. 05. 2008
0 views

BIOSEC PDR

Steps to PDR
02. 05. 2008
0 views

Steps to PDR

ancient china
10. 10. 2007
0 views

ancient china

Latin America 07
22. 10. 2007
0 views

Latin America 07

Super3 ApplytheBig6toK 2
11. 10. 2007
0 views

Super3 ApplytheBig6toK 2

tutorial coco
12. 10. 2007
0 views

tutorial coco

c115c905
13. 10. 2007
0 views

c115c905

Marina PartIII
16. 10. 2007
0 views

Marina PartIII

Harrison EgyptianWebQuest
21. 10. 2007
0 views

Harrison EgyptianWebQuest

20040616 blair
02. 10. 2007
0 views

20040616 blair

Consumer Health Compl
06. 12. 2007
0 views

Consumer Health Compl

599 Introduction
10. 10. 2007
0 views

599 Introduction

orizon2010
23. 10. 2007
0 views

orizon2010

Saul Hahn
25. 10. 2007
0 views

Saul Hahn

Guide to the Match 2007 FINAL
30. 10. 2007
0 views

Guide to the Match 2007 FINAL

U Fix It Workshop
07. 11. 2007
0 views

U Fix It Workshop

015 parker
19. 10. 2007
0 views

015 parker

yun MPLS
30. 10. 2007
0 views

yun MPLS

11029 2003
20. 11. 2007
0 views

11029 2003

Great Grains
21. 11. 2007
0 views

Great Grains

II homology
10. 10. 2007
0 views

II homology

basel
15. 10. 2007
0 views

basel

miele
03. 10. 2007
0 views

miele

pres4 7
31. 12. 2007
0 views

pres4 7

piero messina
04. 01. 2008
0 views

piero messina

ASBESTOS AWARENESS
04. 01. 2008
0 views

ASBESTOS AWARENESS

osmoregulation2
10. 10. 2007
0 views

osmoregulation2

Clim Application Water
07. 01. 2008
0 views

Clim Application Water

Accountability Foster
07. 01. 2008
0 views

Accountability Foster

145 9 new
07. 01. 2008
0 views

145 9 new

Fundraising AWNY2007
28. 09. 2007
0 views

Fundraising AWNY2007

VanBorm
12. 10. 2007
0 views

VanBorm

608uetic
24. 10. 2007
0 views

608uetic

SwissBCH
18. 10. 2007
0 views

SwissBCH

the superstring adventure
15. 10. 2007
0 views

the superstring adventure

winton
23. 10. 2007
0 views

winton

El Mozote
26. 02. 2008
0 views

El Mozote

don cote flh env conf
20. 03. 2008
0 views

don cote flh env conf

Shyama Bijapurkar
26. 03. 2008
0 views

Shyama Bijapurkar

Session 8 Meteorological Hazards
03. 10. 2007
0 views

Session 8 Meteorological Hazards

RiseofBigBusiness
27. 02. 2008
0 views

RiseofBigBusiness

4550ch16
11. 04. 2008
0 views

4550ch16

bbhh107 presentation
26. 11. 2007
0 views

bbhh107 presentation

Arbitragepresentation
16. 04. 2008
0 views

Arbitragepresentation

holiday 2007
17. 04. 2008
0 views

holiday 2007

class8n4
22. 04. 2008
0 views

class8n4

mindful habits
11. 03. 2008
0 views

mindful habits

PraesentationAchtonl ine
07. 10. 2007
0 views

PraesentationAchtonl ine

12 Project02 05
04. 10. 2007
0 views

12 Project02 05

Balschmiter
05. 10. 2007
0 views

Balschmiter

DARPA NoD
08. 10. 2007
0 views

DARPA NoD

308
02. 05. 2008
0 views

308

200606INRIADREIen
13. 03. 2008
0 views

200606INRIADREIen

Organigrama actualizado 01
22. 10. 2007
0 views

Organigrama actualizado 01

Japan Outlook
25. 03. 2008
0 views

Japan Outlook

Inferring Main Ideas New
15. 10. 2007
0 views

Inferring Main Ideas New

Nutrients
07. 03. 2008
0 views

Nutrients

secession
17. 10. 2007
0 views

secession

L5PresentationFive
19. 10. 2007
0 views

L5PresentationFive

JIGSAW
23. 11. 2007
0 views

JIGSAW

fall
02. 11. 2007
0 views

fall

holland poodles
16. 11. 2007
0 views

holland poodles

niimoto
09. 10. 2007
0 views

niimoto

comment to Itai
07. 04. 2008
0 views

comment to Itai

L24 Sartorius
04. 01. 2008
0 views

L24 Sartorius

Power Point Final
02. 11. 2007
0 views

Power Point Final

Prof Thomas Meyer
17. 10. 2007
0 views

Prof Thomas Meyer

Bauer
15. 11. 2007
0 views

Bauer

PBritton
10. 04. 2008
0 views

PBritton

AST5220 2 print
15. 10. 2007
0 views

AST5220 2 print

PRESENTATIONISAAC
01. 11. 2007
0 views

PRESENTATIONISAAC

Willits FIA Program News 2007
08. 10. 2007
0 views

Willits FIA Program News 2007

15 Tauchi
09. 10. 2007
0 views

15 Tauchi

hedberg
19. 10. 2007
0 views

hedberg

Analyst briefing condenced
19. 10. 2007
0 views

Analyst briefing condenced

28 C4 avispachaquetaamar
24. 10. 2007
0 views

28 C4 avispachaquetaamar