### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Programming Languages and Implementation CS 361

GPA 3.55

### View Full Document

## 14

## 0

## Popular in Course

## Popular in ComputerScienence

This 19 page Class Notes was uploaded by Kylee VonRueden on Wednesday September 30, 2015. The Class Notes belongs to CS 361 at Pace University - New York taught by Christelle Scharff in Fall. Since its upload, it has received 14 views. For similar materials see /class/217100/cs-361-pace-university-new-york in ComputerScienence at Pace University - New York.

## Reviews for Programming Languages and Implementation

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/30/15

Polymorphism 0 Default type Example fun fav avlav f is of type int int oTheabt fafuntnt warument f different types is called polymorphism Examples hd a list a fun idx x id a a What is the type of idid oFunt n that et t p m phm x N div mod lt lty gty gt andalso orelse not string concatenation Conversion type operators 0rd chr real sir floor ceiling round truncate Equality operators 0 Type variables whose values are restricted to be an equality type are distinguished by having names that begin with two quote marks rather then only he a 0 Examples equality type require operator domain 2 t Z operand real t real in expression 1 2 1 2 0 Functions allowing the polymorphism f tune 1 2 Q hd tl mil for lists ltgt Pattern mat hin and equality operator 0 Pattern matching permits us to design more general functions 0 Exampe Can we u e the fun t n rever e p e ously defined to reverse a list of reals No fun reverseL f L nil then nil else reversetlL 9 hdL val reverse fn a list gt a list But reverse can be used thanks to pattern matche ing fun reverse1nil nil I reverse1xL reverseL 9 X val reversei fn a list gt a list Curried functions 0 Until now we defined functions having only one pa rameter that is a tuple A curried function is a function having several parameters a list of pa rameters with no parentheses or commas o Exampe 1 map builtein function in SML is the curried version of apply The type of map is quota gt b gt quota list gt 39b list fun applyfL if Lgt then 1 else fhdLapplyftlL val apply fn b 3 a list gt b list Example 2 Let us consider the function 650 that computes av 30 is a real and y is an int eavp1 is the curried form of mop fun expx0 110 I expxy x 3 expxy 1 val exp fn real 3 int gt real fun e p1 1 0 I e pl 3 val expi fn real gt int gt real Let and Functions 0 One can use let in expressions to allow us to use common subexpressions o E amples un hun re hp wer real let val four x3x3x3x val twenty four3four3four3four3four in twenty3twenty3twenty3twenty3twenty end val hundredthpower fn real gt real fun fibn if n 0 orelse n 1 then 1 1 val n1 fibn1 val n2 fibn2 in n1 n2 end Partially instantiated functions 0 Curried functions are useful to construct new func tions by applying the function to arguments for some but not all of its parameters 0 E amples eavp1 30 is a function of type int gt real that come putes the powers of 30 eavp1 100 is a function of type int gt real that compute the powers of 100 Let and Pattern matching o In SML it is possible to split apart the values re turned by a function 0 Example fun fx XXX a f in a gt a 3 a 3 a val abc f3 val a 39 int val b 3 int val c 3 int The variable a is linked with 3 the variable b is linked with 3 and the variable c is linked with 3 val t f3 val t 333 int 3 int 3 int o This can be used in functions fun g nil 0 I gL l t e val abc fhdL 2 in a val g fn int list gt int gnil val it 0 int g467 t 8 int Datatypes SML has also a very powerful mechanism for define ing new types called datatypes A datatype definition involves A type constructor that is the name of the datatype One or more data constructors which are idene tifiers used as operators to build values belonge ing to a new datatype Functions having parameters of user defined datatypes are generally defined easily using pattern match ing Syntax datatype ltlist of type parametersgt ltidentifiergt first constructor expressiongt I ltsecond constructor expressiongt I ltlast constructor expressiongt User defined types 0 We can build new types in ML using old types u ng the product of types T1T2 function types T1 T2 list Examples type intpair int t int val it 57 int 3 int val it 57 intpair type funonint int gt int type intlist int list 0 Parametrized type definitions Syntax type ltlist of parametersgt ltidentifiergt lttype expressiongt Examples type a b relation a b list v l R 1223intintrelation 0 An enumerated datatype declaration consists of the keyword datatype a name for the datatype and a list of data constructors separated by 0 Examples datatype primary olor Red I lue datatype primarycolor Red I Blue I reen I Green datatype printercolor Yellow I Magenta I Cyan datatype printercolor Yellow I Magenta I Cyan datatype fruit Apple I Pear I Grape datatype fruit Apple I Grape I Pear datatype bin zero I one datatype bin one I zero fun isAppleX xApple val isApple fn fruit gt bool Constructors in datatype definitions and functions 0 Example datatype Nat Zero I Suc of Nat The constructors are Zero and Suc The construce tor Suc takes one parameter Zerc does not take parameters This datatype is recursive Nat is used in the rhs of its own definition 0 Define the Additi n of 2 Nats the multiplication f2 atthe ne nf ma att and from an int to a Nat curried forms fun pl 5 n Zero I plus n Sucp val lus fn Nat plus SucZero SucZero val it Suc Suc Zero t Sucplus n p gt N gt N fun times In Zero Zero I times In Sucp plus times n p n val times in N gt Nat gt Nat times SucZero SucZero a1 t Suc Zero Nat nary Search Trees A binary search tree is a binary tree where each node contains a key such that o All keys in the left subtree precede the key in the root 0 All keys in the right subtree succeed the key in the root 0 The left and right subtrees of the root are again binary search trees fun natint Zero 0 I natint Sucn natintn 4 1 val nat t fn a gt in natint Su Su Su Zero val it 3 fun intnat 0 Zero I intnat n Sucintnatn1 fn int Nat val it uc Suc Suc lei 0 Nat Binary Search Trees in SML The datatype constructor in SML permits us to define new data types like a BinaryTree aape aBinarTreebep I ht of a a BinaryTree a BinaryTree datatype a BinaryTree con ht a a Binaryfree a Binaryrree gt a BinaryTree con btempty a Binaryrree Each BinaryTree consists of a header bt a node value or key and left right subtrees both of which must be BinaryTrees The special case of a tree with no keys in it the empty tree is denoted btempty val Tree bt2btempty b1 3 btemp by b17b t6bt5btemptybtempty btempty bt8btemptybtempty val Tree bi 2btemptybt 3btemptybt it int Binary39I ree ook up an element in a binary search tree we must To I test the label of the root against our desired key and The lookup Function Tree Traversal in ML the recursively search the appropriate side39s subtree The search ends in failure whenever the subtree is btempty r t lookupTree6 val it true 39 val 1t false lookupTree8 va it true lookupbtempty6 val it false al E p quot quotbt bt fun 1 I 1f x r 0 else if x lt root then lookupleftx I else lookuprightx val lockup fn bool bool val Expression btuu btuu btuu btquot2quotbtemptybtempty btquot5quotbtemptybtempty ht btquot3quotbtemptybtempty btquot4quotbtemptybtempty btquotquot39 btquot1quotbtremptybtempty htquot6quotbtemptybtempty ressi n b quotquot string Binary ree u e p false lockupbtrootintleftrightxint then true Note how only the order of the recursive calls changes n the th ee t a e fun inorder btempty inorderbtroot aleftri inorderleft root gm inorderright int BinaryTree int gt bool fun preorder htempty J I preorder ht root a left r1ght preorderleft preorderright fun postorder htempty J I postorderbtroot aleftright postorderleft postorderright root in r erE pressi n val it u2uuuu5uuuusuuuu4uuuu1uuuu6u preorderExpression val it uuuuuuu2uusuuuu3uu4uuuuiuu6u postorderExpression val it u2uu5uuuu3uu4uuuuuu1uu6uuuuu These traversal functions could be easily modified to compute the value of the arithmetic tree instead ofjust returning the formula quotquot b b b Binary tree processing Inorder Traversals of Binary Search Trees datatype 3 BinaryTlquotSS lit empty I ht of a a BinaryTree a BinaryTree fun leftsubtree btempty btempty Why is an inforder traversal called in order I leftsubtree ht left J left fun rightsubtree btempty btempty I rightsubtree ltright right exception labeleastiLargument fun label btempty raise labelhasnilargument v 1 I label ht value Sample binary trees val Tree bt2btempty bt3btempty ht 7 ht 6 ht 5 btempty btempty btempty ht 8btemptybtempty Note that an inforder traversal of a binary search tree t a the e naphabet a d inorderTree val it 235678 int list val Treei bt3btemptybtempty val Tree2 bt5bt 1 btemptybtempty btempty val Tree ht 7 b btempty btempty bt12 temptybtempty val Tree4 btquot quot btquotquot btquotquotbtquot7 btemptybtempty b quotaquotb e p b e btquot5quotbtemptybtempty btquotex quot inorder ree ht quotquot bt quotaquot btlemptymtlempty preorder Tree ht quotbquot btempty btempty postorder Tree ht quot 3quot btempty btempty inorder Expres sion preorder Expresslon val Expression ht 4 postorderExpression ht u u ht 439 ht quot2quot btempty btempty btquot5quotbtemptybtempty bun b quot3quotb e p b e p btquot4quotbtemptybtempty bun btquot1quot btempty btempty btquot6quotbtlemptymtlempty lookup Tree 6 lookup Tree 1 lookup Tree 8 lookup Tree 9 lookup btlempty 6 if a gt a gt a arra uni 0 Array is a structure in SML that gives us the ability val appi int a gt unit gt a array int x to create and manipulate arrays int option gt unit The structure is opened using val foldli int a b gt b gt b gt a array t int t int option gt open Array val foldri int a b gt b gt b gt a array t int t 1nt optlon gt b opening Array val modifyi int t a a a array int t type a array a array int option gt unit type a vector a vector val maxLen int 0 Example val array 1nt a gt a array val tabulate int t int gt a gt a array val A array10 4 4 val fromList a list gt a array val A 4444444444 1nt array val length a array gt int V31 1 lengt A val sub array int gt a V31 1 10 1 t val update a array int t a gt unit val v sub e val extract a arra int int option gt a vector val v 4 1nt val copy d11nt dst a array 1en1nt option siint 2dateA 5 0 76 a array a1 1 4444404444I in arra un1 val copyVec d1 int dst a array1enint optionsiint src a vector gtun1t val app a gt unit gt a array gt unit val foldl a b gt b gt b gt a array gt b val foldr a b gt b gt b gt a array gt b 0 Aggregate structures where each component has 0 Exam e D 0 Functions over records type king name string born int fun 11vet1mekk1ng 1161100 born t crowned 1ntd1ed 1nt val 11vet1me fn klng gt 1nt livetime HenryV val HenryV a e quotHenri val 1t 35 1nt born 1387 crowned1413 died 1422 i o Accessing components in a record by pattern matching va1born x HenryV val x 13871n a by operators a1 b ear b rnHenr V val byear 1387 int Functional programming General features Thefunt ha a et f bd theme e fa te which less pious programmers regard as standard No reeassignment No sideeeffects When a value is assigned it does not change dure ing the execution of the program gt Property of referential transparency No global variable or instance of an object Recursion is the only method of repetition Pattern matching Strongly typed and type inference Ruleebased programming The focus is more on what is to be computed not how it should be computed No allocation of memory Very high level languages Function evaluation not assignment of variables is the basic concept for a programming paradigm that has been implemented in such functional pro gramming languages Programs are collections of function definitions The ba m de f mputat n the u e fthe definition and application of functions explicit and recursive The basic cycle of activity has three parts read input from the user evaluate it and print the computed value or an error message Why functional programming matters The key to understanding the importance of funce tional programming is to focus on what it adds rather than what it takes away Software becomes more and more complex It is important to structure it well Structured software is easy to write easy to debug easy to reuse Modular software is generally accepted to be the key to successful software Divideeandeconquer The ways in which the original problem can be divided up depends directly on the ways in which solutions can be quotgluedquot together New quotgluesquot are provided in functional programe ming Examples highereorder functions polye morphism abstract data type o The code is shorter clearer easy of understanding and there are no sideeeffects o Funt na p gammng pa an mp tant e n symbolic processing 0 Functional programming plays an important role in prototyping Much of a software product39s life is spent in spece ification design and maintenance and not in pro gramming Functional languages are superb for writing specifications which can actually be exee cuted and hence tested and debugged Such a specification then is the first prototype of the final program 0 Construction of more reliable software gt Correct ness Proof of the correctness easier than for imperatiye programs ompari on of fun tion implementation in ev eral FP languages 0 gna Mathemat f y y15 SML fun fxy xxy15 definebfi am a X SCheme a x y 15 gt gt to I x y Logo output xxy15 end Mathematica xy xxy15 function 0 1x Matlab oxxy 5 y Fun tional program g language SML CAML Erlang Haskell Miranda Scheme Logo Mathematica Matlab Functional Programming in the real world httpwwwresearchayayalabscomuserwadler realworld Industrial Erlang is a functional programming language used for implementing very large scale reale time concurrent industrial applications Used by Ericsson AnnoDomini a Year 2000 remediation for Cobol Shopcom Merchant System a an ecommerce database Combinators for financial derivatives The em p e HOL Iabe e Numerical applications XML Stylesheet transformations Natural language processing and speech recognition Network toolkits and applications Quicksort in Haskell 150 J qsort mics qsort 211551151 1 qsori eltsgreql afh t where eltsltx y y lt xs y lt x vahile 1 lt h eltsgreqx y y lt xs y gt 1 t ail Quicksort in C an and aEhi t qsort a 10 hi gt int an hi 10 1501 a lo l1 gt qsort a 11 hi int h 1 p t if 10 lt hi 10 II II II 1 h i p ahi do while 1 lt h scar am lt pgtgt 1 11 while h gt 1 sear ah gt pgtgt if 1 lt h t an al aEh Is functional programming hard to learn Functional programming does require a change in perspective which some programmers find had ButE n epeenentanngp grammers in Erlang is that most find the trane sition easy 7 provided they take the training need seriously rather than assuming that they can quotpick it up on the dayquot httpwwwhaskellorgaboutHaskeIIhtmI o The language ML Meta Languagequot was origie nally introduced in the 197039s as part of a theoe em d wa ntended f de b ing and implementing proof strategies Standard ML of New Jersey SML is an implementation of ML oTheeaeeten n fML nuentMLOb jective ML 0 httpcmbellelabscomcmcswhatsmlnj o Expressions values and simple types 0 Scope let local 0 Functions explicit recursive 0 Evaluation of functions 0 T pe tup e t 0 Operations on lists 0 Exceptions 0 Pattern matching 0 Highereorder functions 0 Mutualerecursion o Equality operators 0 u ed fun t n 0 Records arrays user defined types Running SML on matrix To start up SML enter sml at the unix prompt To leave SML enter CTRLeD To run an SML program foo enter sml lt foo at the unix prompt To run a program interactively in SML start up SML and type the SML expression usequotfooquot T nteatwthap gam n ML tpenane pression in response to the ML prompt 7 ML responds with the value and type of the expression rst SML example Not the Hello Worldquot program Here is a simple example 3 val it 3 2 int The first line contains the SML prompt followed by an expression typed in by the user and ended by a semicolon The second line is SML39s response indicating the value of the input expression and its type Interacting with S M L o SML has a number of builtin operators and data types 0 SML provides the standard arithmetic operators 32 val it 5 2 int sqrt20gt val it 1414213562137309 real 0 TheB aue true and falsea ea a abe a a are logical operators such as not negation andalso nun t n and relse d n t true val it false bool true andalso false val it false bool Binding Names to Values o In SML one can associate identifiers with values val three 3 a1 three 3 2 int and thereby establish a new value binding three val it 3 2 int 0 More complex expressions can also be used to bind values to names 32 val five int val five 5 0 Names can then be used in other expressions three 1 five i 8 39 Types in SML SML is a strongly typed language in that all welle formed expressions have a type that can be detere mined by examining the expression As part of the evaluation process SML determines the type of the output value Inference of type Simple types are real E amples 12 and 15912 15 x 1012 are reals int Examples 12 and 14 are integers 3 5 is an integer bool Examples true and nottme are booleans string Examples ninequot quotquot are strings Variables and environment A variable is represented by a name and a value The environment is a list of pairs variablemalue A new variable may be added to the environment using val ltvariablegt ltvaluegt Example Initial environment 2 p0 val val y 3 val z yx3 Environment p1 p0 301 y3 057 va 1 Environment p2 Pl 9712 Local environment 0 It is possible to create local variables inside a funce tion using let in end 0 Syntax let val ltvar1gt ltvallgt val ltvar2gt ltval2gt val ltvarngt ltvalngt n 1 ltexpressiongt end 0 Example 01 00 901 92 13 let val uxyg val vxyxval z1 in uzvx en val it 7 2 int stdIn1601 Error unbound variable or constructor u p2 01 m3 m3 11 before end p3 p1 after end If we apply double to an argument of the wrong type we get an error message double 2 o r r perat 1 an peran n t agree t n misma perat r ain int in expression double 20 o The user may also explicitly specify types 0 Example fun maxxintyzintzintgt if xgty andalso xgtzgt then x else if ygtz then y else 2 z i int int gt int II II val it 3 2 int The type of the function mow is int int int 9 int Defining Functions in SML is a lot of fun o The general form of a function definition in SML is fun identifier parameters expression 0 The type of a function is expressed using It is recursively defined by type of the parameter type of the re ult 0 Example fun doublex 2x val double In 2 int gt int declares d ube as a function from integers to intee The type of the function double is int int uble 222 val it 444 2 int The type of double222 is int Recursive Defin ons o The use of recursive definitions is a main charace teristic of functional programming languages 0 These languages strongly encourage the use of ref u naatutu e mnpefeenet iterative constructs such as whileeloops 0 Example fun factorialxgt if x0 then 1 else xfactorialx1gt val factorial In 2 int gt int The type of the function factorial is int 9 int The definition is used by SML to evaluate applica tions of the function to specific arguments factorial5gt val it 120 z factorial10gt val it 3628800 2 int int Greatest Common Divisor Evaluation of functions o SML parameter passing is callbyvalue o The calculation of the greatest common dwisor gcd of two positive integers can also be done recursively based on the following observations 1 get10141 n o How are recursive functions evaluated Eager evaluation is used in SML Eage e auat n Atem edu edt adata aue 239 galonvn godmvmy and Ge is normalized before it is passed as an argue 3 gaxmen gaxmnenv cm gt L ment to a function This has the benefit that if an argument is used twice or more in the function A possible de nition in SML is as follows body we avoid having to normalize it twice or more fun gcdmynhint if mn than n o The opposite of eager evaluation is lazy evalua else if mgtn then gcdmnngt tion else gcdmnmgt Lazy evaluation A term is not normalized unless the value is required This has the benefit that if a Val 05 in 1 int int 39gt int function argument is discarded we did not perform the normalization in vain as we would have in eager gcd1230gt evaluation val it 2 int gcd120gt o By need evaluation is like lazy evaluation except val it 1 2 int for a relatively small modification when an argue gcd1262357gt ment a ue demanded we n ma ze t the fi t va it 1 2 int time store the value away somewhere and if it gcd12556345gt is demanded again we use the use the normalized val it 5 1111 term which had being saved instead of normalizing it again Tuples in SML o SML provides two ways of defining data types that represent sequences 0 The components of a tuple can be accessed by ap plying the builtein function xi where i is a positive x1t1gt Tuples are fin te sequences where the length is val it 1 2 int arbitrary but fixed and the different components 31t2gt need not be of the same type val it 4 int Lists are finite sequences of elements of the a l 2i2gt 0 gt real int same type39 x2x2t2gtgt val it n 0 Some examples of tuples and the corresponding 83t3 WDQS are val it quotninequot 2 string val t1 1 2 gt Ifafun t nxi app ed t atupewth fewe than val t1 123 1 int 1m int icomponents an error results val 2 450 val t2 45o6gtgt int 1 real 1 int MRS a1 53 78 quotninequotgt Err r perat r an peran n t agree val t3 780quotninequot int 1 real 1 string The type of t is int 1 int 1 int The type of 2 is int a real int The type of 3 is int 1 real 1 string Lists n SML 0 Another builtin data structure to represent see auences in SML are lists 0 A list in SML is essentially a finite sequence of ob ects all of the same J 0 Note that the type is described In terms of a type variable a as a list of objects of type a Instantie Exammes39 ating the type variable by types such as int results 123 in different empty lists of corresponding types val it 123 2 int list truefalse true val it truefalsetrue bool list 123456 val it 123456 int list list The last example is a list of lists of integers in SML notation int list list oA bet na tmutbe fthe ametpe 12 rror operator and operand don t agree 0 The empty Ii t den ted b thef wng mb E val it z a list nil val it a list Operations on Lists 0 SML provides some predefined functions for manipe ulating lists 0 The function hd returns the first element of its are The types 0 the two fmaiom are as fouows gument list h 12313 val it In 2 a list gt a al it 1 2 nt 39 t1 haulymymng val it In 2 a list gt a list val it 12 2 int list Applying this function to the empty list will result in an exception error 0 The function tl removes the first element of its argument lists and returns the remaining list t1 1 23 val it 23 2 int list t1123 al it 3 int list list The application of this function to the empty list will also result in an error More List Operations Defining List Functions 0 Lists can be constructed by the binary function 2 read cons that adds its first argument to the front of the second argument 5 al it val it Again the 39 1 rror Recursion is particularly useful for defining list pro 0 cessing functions For example consider the problem of defining an 5 int list I SML function call It wheat that takes as argue 123 1111 list e tw t ft e ame t pe and etu n the z 3 4567 concatenated list 123 4567 int list list arguments must be of the right type What is the SML type of conceit For example the following applications ofthe funcs tion n at should yield the indicated responses concat12 3 gt 23 operator and operand don t agree 0 Lists can also be compared for equality val it 123 int list 12313233 concats12gt 1 it true bool al it 12 2 int list 1221 concat12gt a1 it false bool val i 12 int list t1 E val it true bool o In defining such list processing functions it is he eep n m nd that a e concatenation Of LiStS In designing a function for concatenating two lists X and y we thus distinguish two cases depending on the form of X I L D If X is an empty list then concatenating X with y yields just y the empt t If X is of the form X1X2 then concatenating X of the form Xy with y is a list of the form X1 2 where z is the results of concatenating X2 with y In fact we The empty list and z are the constructors of the can even be more Speci c by observing that X type hst hdXtlX For example 123 1 2 233 o This suggests the following recursive definition val it true bool fun concatxy if x then y else hdxgtconcattlxgtygt val concat In 2 a list a list gt a list 0 This seems to work at least on some eXamples concat1234s5gt val int list val it int list The resu t of concat 0 i5 Warning type vars not generalized because of value restriction are instantiated to dummy types X1X2 val it I X1 list 0 The following function has a similar recursive struce tue It double a theeement n t a gument t of integers fun doubleallLgt if L then E else 2hdL doublealltlL II II val doubleall In 2 int list gt int list doubleall 1357 val it 2631014 2 int list doubleall is of type int list int list Why More List Processing Func o Recursion often yields simple and natural definie tions of functions on lists 0 The following function computes the length of its argument list by distinguishing between the empty list the basis case and noneempty lists the general case fun lengthLgt if Lnilgt then 0 else 1lengthtlLgtgt II II val length In 2 a list gt int lengthE123 val it 3 2 int lengthEESJ 4 3 21 val it 4 2 int length val it 0 2 int The Reverse of a List o Concatenation of lists for which we gave a re cursive definition is actually a builtein operator in SML denoted by the symbol Q oWeueth peat nthef wngeu edef Inition of a function that produces the reverse of a list fun reverseLgt 391 L nil then nil else reversetlLgtgt 0 hdLgt II II al re erse In 2 a list gt a list reverse 123 val it 321 2 int list reverse nil stdIn3513512 Warning type vars not generalized 1 because of value restriction are instantia e to dummy types X1X2 val it J 2 X1 list Constructing Sublists oThe wn funtnem eall uene f its first argument from its second argument list fun removekym o A sublist of a list L is any list obtained by deleting if FED than 0 some ie zero or more elements from L else if xhdL then remove it tl L 0 For example 1 1 2 and 12 are all the else hdL removextlL sublists of 12 val remove In 2 a a a list gt a list 0 Let us design an SML function that constructs all sublists of a given list L The definition will be remove1 5311 recursive based on a case distinction as to whether al it 53 2 int list L is the empty list or not remove24242422gt val it 41141 int list o If L is noneempty it has a first element ac There 39 removemymns val 1 U 1 int list are two kinds of sublists those containing ac and 0 We use it as an auxiliary function in the definie those Qt Contammg 5039 tion of another function that removes all duplicate occurrences of elements from its argument list 0 For Instance In the above example we have sublists 1 and 12 on the one hand and J and 2 on fun removeduplL the other hand if L then else hd L z 2 remove hd L removedupl tl L II II 0 Note that there is a oneetosone correspondence be tween the two kinds of sublists and that each sub Val remve jupl I z a 115 39gt a 115 list of the latter kind is also a sublist of tlL Constructing Sublists continued 0 These observations lead to the following definition fun sublists L if L then nil else subliststlL 0 insertL h L sublists tl L o If we change the expression in the elseebranch to II II else insertL hd L sublists tl L al ublit In alit alitlit v s s s s s s 0 subliststlLgtgt 39 Sublists all sublists will still be generated but in a different stdIn8418411 Warning type vars not generalized order because of alue restriction are instantiated to dummy types X1X2 val it X1 list list sublists12 val it 2112 2 int list list sublists1 val it U 3 3 2 3 23 3 1 13 12 123 2 int list list sublists4321 val it U 1 3 2 3 21 3 3 31 32 3 2 1 0 Here Q denotes the builtein concatenation opera ation on lists and the function insertL inserts its first argument at the front of all elements in its sec ond argument which must be a list Its definition 395 left as an exercise 0 Declaration of an exception 0 Syntax 0 Many functions are partial they do not produce a exception lt name of the exception gt of lt type gt value for some of the possible arguments of the E l b function39s domain type It is essential that we be Kemp es able to catch such errors This IS done by generae exce tion Fo tions and handling of exceptions P 0 exception Alert of string exception Number of int 0 E ampe fp edefined e ept n n ML exception Tuple of intreal 5 div 0 uncaught exception Div The type of an exception is 0 Raising an exception hdnil S b uncaught exception Empty 0 yntaX raise lt name of the ewceptionlt parameters gt gt 0 Examples rai e Foo raise Alert stop raise Number5 raise Tuple15 0 Handling an exception 0 Syntax e pre ion handle match 0 Examples Design a function gnm that prints Division by 0quot in case m 0 using exceptions exception Division of int exception Division of int fun fnmgt if m 0 then raise Division0gt e se n val I In 2 int int gt int fun gnm fnmgt handle Division0gt gt print quotDivision by 0quot print quotnquot 0 Val g In 2 int int gt int

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I LOVE StudySoup!"

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.