New version page

Compiling Techniques

Upgrade to remove ads

This preview shows page 1-2-3-4-25-26-27-51-52-53-54 out of 54 pages.

Save
View Full Document
Premium Document
Do you want full access? Go Premium and unlock all 54 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 54 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 54 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 54 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 54 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 54 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 54 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 54 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 54 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 54 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 54 pages.
Access to all documents
Download any document
Ad free experience

Upgrade to remove ads
Unformatted text preview:

More MLTodayListsSlide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11List ProcessingSlide 13Slide 14Slide 15ML is all about functionsAnonymous functionsSlide 18Slide 19Slide 20Another way to write a functionSlide 22Yet another way to write a functionYet another way to create a type errorParametric PolymorphismSlide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41What is the type of map?Slide 43Slide 44ML ModulesStructuresSlide 47Slide 48Slide 49SignaturesInformation hidingSignature AscriptionOther thingsLast ThingsMore MLCompiling TechniquesDavid WalkerTodayMore data structureslistsMore functionsMore modulesListsLists are created withnil (makes empty list)head :: tail (makes a longer list) 5 :: nil : int listelementlist of elementsListsLists are created withnil (makes empty list)head :: tail (makes a longer list) 4 :: (5 :: nil) : int listelementlist of elementsListsLists are created withnil (makes empty list)head :: tail (makes a longer list) 3 :: 4 :: (5 :: nil) : int listelementlist of elementsListsLists are created with3 :: (4 :: (5 :: nil)) : int list3 :: 4 :: 5 :: nil : int list(true, 1) :: (false, 2) :: nil : (bool * int) list(3 :: nil) :: (2 :: nil) :: nil : (int list) listListsLists:3 :: [] : int list 3 :: [4, 5] : int list[true] : bool lista different wayof writing “nil”a different wayof writing a listListsBad List:[4]::3;???ListsBad List:[4]::3;stdIn:1.1-2.2 Error: operator and operand don't agree [literal] operator domain: int list * int list list operand: int list * int in expression: (4 :: nil) :: 3ListsBad List:[true, 5];???ListsBad List:[true, 5];stdIn:17.1-17.9 Error: operator and operand don't agree [literal] operator domain: bool * bool list operand: bool * int list in expression: true :: 3 :: nilList ProcessingFunctions over lists are usually defined by pattern matching on the structure of a listHint: often, the structure of a function isguided by the type of the argument (recall eval)fun length l = case l of nil => 0 l _ :: l => 1 + (length l)List Processingfun map f l = case l of nil => [] l x :: l => (f x) :: (map f l)What does it do?Two arguments f and lList Processingfun map f l = case l of nil => [] l x :: l => (f x) :: (map f l)applies the function f to every element in the list- fun add1 x = x + 1;- map add1 [1,2,3]; > val it = [2,3,4] : int listList Processingfun fold f a l = case l of nil => a l x :: l => f (fold f a l) x another incredibly useful functionwhat does it do? use it to write map.ML is all about functionsThere are many different ways to define functions!I almost always use “fun f x = ...”When I am only going to use a function once and it is not recursive, I write an anonymous function:(fn x => ...)Anonymous functionsval n = 3val isValue = (fn t => case t of Bool _ => true | t => false)binds a variable (n)to a value (3)binds a variable(isValue)to the anonymous function valuefn keywordintroducesanonymousfunAnonymous functionsfun map f l = case l of nil => [] l x :: l => (f x) :: (map f l)fun addlist x l = map (fn y => y + x) lanonymous functionsAnonymous functionstype ifun = int -> int val intCompose : ifun * ifun -> ifun = ...fun add3 x = intCompose ((fn x => x + 2), (fn y => y + 1)) xa pair of anonymous functionsa type definition (very convenient)Anonymous functionstype ifun = int -> int val intCompose : ifun * ifun -> ifun = fn (f,g) => (fn x => f (g x))fun add3 x = intCompose ((fn x => x + 2), (fn y => y + 1)) xresult is a function!argument is pair of functionspatternmatchagainstargAnother way to write a functionfun f x = ........ can be written as:val f = (fn x => ......)provided the function is not recursive;f does not appear in ........Another way to write a functionfun f x = ....can always be written as:val rec f = (fn x => ...f can be used here...)keyword rec declares a recursive function valueYet another way to write a functionfun isValue Num n = true | isValue (Bool b) = true | isValue (_) = falseThis is just an abbreviation forfun isValue t = case t of Num n => true | Bool b => true | _ => falseYet another way to create a type errorfun isValue 0 = true | isValue (Bool b) = true | isValue (_) = falseex.sml:9.1-11.29 Error: parameter or result constraints of clauses don't agree [literal] this clause: term -> 'Z previous clauses: int -> 'Z in declaration: isValue = (fn 0 => true | Bool b => true | _ => false)Parametric PolymorphismFunctions like compose work on objects of many different typesval compose = fn f => fn g => fn x => f (g x)compose (fn x => x + 1) (fn x => x + 2)compose not (fn x => x < 17)Parametric PolymorphismFunctions like compose work on objects of many different typesval compose = fn f => fn g => fn x => f (g x)compose not (fn x => x < 17)compose (fn x => x < 17) notBAD!!Parametric PolymorphismFunctions like compose work on objects of many different typesval compose = fn f => fn g => fn x => f (g x)compose: (‘a -> ‘b) -> (‘c -> ‘a) -> (‘c -> ‘b)Note: type variables are written with ‘a type variablestands forany typeParametric PolymorphismFunctions like compose work on objects of many different typescompose: (‘a -> ‘b) -> (‘c -> ‘a) -> (‘c -> ‘b)compose: (int -> ‘b) -> (‘c -> int) -> (‘c -> ‘b)can be used as if it had the type:Parametric PolymorphismFunctions like compose work on objects of many different typescompose: (‘a -> ‘b) -> (‘c -> ‘a) -> (‘c -> ‘b)compose: ((int * int) -> ‘b) -> (‘c -> (int * int)) -> (‘c -> ‘b)can be used as if it had the type:Parametric PolymorphismFunctions like compose work on objects of many different typescompose: (‘a -> ‘b) -> (‘c -> ‘a) -> (‘c -> ‘b)compose: (unit -> int) -> (int -> unit) -> (int -> int)can be used as if it had the type:Parametric Polymorphismcompose not : ??compose : (‘a -> ‘b) -> (‘c -> ‘a) -> (‘c -> ‘b)not : bool -> boolParametric Polymorphismcompose not : ??compose : (‘a -> ‘b) -> (‘c -> ‘a) -> (‘c -> ‘b)not : bool -> booltype of compose’s argument must equalthe type of not:bool -> bool == (‘a -> ‘b)Parametric Polymorphismcompose not : ??compose : (‘a -> ‘b) -> (‘c -> ‘a) -> (‘c -> ‘b)not : bool ->


Download Compiling Techniques
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Compiling Techniques and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Compiling Techniques 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?