Selected Topics CSE 891
Popular in Course
Popular in Computer Science and Engineering
This 58 page Class Notes was uploaded by Donnell Kertzmann on Saturday September 19, 2015. The Class Notes belongs to CSE 891 at Michigan State University taught by Staff in Fall. Since its upload, it has received 14 views. For similar materials see /class/207420/cse-891-michigan-state-university in Computer Science and Engineering at Michigan State University.
Reviews for Selected Topics
Report this Material
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/19/15
Case Study CSE 891 Forensic Odontology Hong Chen Carrie Jackson Outlines History and status of forensic odontology Dental Anatomy Main applications Comparison to other forensic biometrics Famous Cases Computer aided forensic odontology Definition Forensic odontology is the application of dental principles to legal issues Applications Individual Identification Mass Disaster Identification Bite mark analysis Dental Malpractice History 66 AD Lollia Paulina s body identified Casualty ID in Revolutionary War 1849 Vienna Opera House fire Dental identification evidence first admitted in US court system Training No specific training required to practice Most are practicing dentists Undergraduate education Dental school Possible specialized training Admittance into professional groups 32 teeth 4 tooth types Incisors Canines Premolars Molars Dentition molars E 12 E premolars 3 canines 4 iwncisms lower jaw OrientationSize Root Structure 31 upper jaw Tooth Composition Molar 1 ELDEMTIH Id alum mmtun If 39 I EMEHTUM 11 39i CEMEMTU M mvmmn mm Puma umm UEAMEHT Dental Restorations 0 Crowns 0 Fillings Root canal Bndge Extractions Individuality of Teeth Many combinations of restorations SizeOrientation can vary greatly Variable numbers of teeth Variable root structure m kh rquot NILE IllHim mull m m libsm ynll m Main Applications Individual Identification Mass Disaster Identification Bite mark Analysis lden ca on Postmortem description is generated Radiographs taken Possible identities known Yes Comparison to antemortem data Match strength determined No Biological profile generated The Universal System Each tooth has a specific number Each surface of the V 341 teeth are classified 356 Uri mgr Notes extractions 3 quot 2 2 23 22 239 2 399 w fillings orientation etc PmMAm on BMW 1mm TOP A 8 C D E F G H l J Primary dentition noted with upper case gergjmijr T S R 0 PO N M L K BOTTOM letters lden ca on Postmortem description is generated Radiographs taken Possible identities known Yes Comparison to antemortem data Match strength determined No Biological profile generated Age Determination I 2 w 39 u m m n o m 0 m w m m n u n a m u h e m rm 6 H m m m m w M m n A M 3 N mu F n w n m w w M m m m 39 M m n m m m 9 5a m M Mr S n m Age Determination Chart Ages ut39 Lmpnun tor Deciduqu md Prrmancnl Dcntmun Tooth r Maxillarv il Mandibular Deciduous Denrumn gcnlra mcxsor 7 5 mu r 110 Zaicml musor 9 mo 39 11m camnc 8 mu 30 um rst molar 14 mo 12 mn ccnnd mom quot14 m0 0 mm Permuncm Denn on antral mmsor Literal muzsor 78 yr 3 r C JIHHL llllr lZHH rst premoiar 10 11 T lHll yr sccond Drcmolar 1012 lllIgtT rst molar sccand molar mird malar Mass Disaster Identification Completed in the same manner as individual identification Organization of antemortem and postmortem data is essential Large scale problems can occur Mass Disaster Dental ID Teams Postmortem Team Generates dental profile and radiographs Antemortem Team Collectsorganizes antemortem data Records Comparison Team Compares postmortem and antemortem data Bite mark analysis Can be used to link a suspect to a crime Impressions left on food skin or other items left at a scene Impression Variation Each dentition can produce variable impressions Change based on pressure and surface of contact Impressions from the same dentition Analysis Bite marks are photographed with a scale Bite marks on skin are taken over repeated intervals Casts of impression are taken Impression traced onto transparencies Casts of suspects teeth are taken Comparison between suspect cast and bite mark Comparison to Other Forensic Biometrics Dental DNA Fingerprint R b it t DECSEEEEEioi High Mid Low Accuracy Mid High High Time Short Long Short Enroll Rate Low High Low 39 Strgment Mid High Mid reqUIred Famous Cases Bite mark analysis Iden ca on Dental Programs National Dental Program In 1997 The Criminal Justice Information Services Division CJIS of the FBI created a dental task force DTF 0 State Dental Program Three states Maryland Washington and California Best Collectors of Dental Records gt10 TOTAL EASES WITH PERIEENT CASES CASES DENTAL WIIH DENTAL quota39u39y39oming 45 13 288 Idaho 170 31 131 ll mpshire TIE 13 171 Florid 5306 13 Washington 2152 126 1xterm mm 72 1 25 Maine 13938 12 I alontana 131 39 105 Cases Ted Bundy The most famous bite mark case The bite mark was 0 Transparent overlays Wax bite exemplar the body of a Victim superimposed Cases 911 oAt ground zero among 973 victims identified in the first year with only one method about 20 of victims were identified using dental records Cases Asian Tsunami Around midMarch of some 800 identified bodies 90 were identified by dental records If you post pictures of your loved ones on the bulleting boardsweb boards choose picture with a broad smile so that front teeth can be seen A better approach is to post dental Xray films and leave emailphone number of the dentist Tsunami Relief website A forensic expert examines a lm of the teeth of a tsunami Victim in Phuket of Thailand on Jan 11 2005 Computer Aided Forensic Odontology 3D Bite mark analysis Automatic dental code matching OdontoSearch Automatic dental identification system Bite mark Analysis Using 3D Scans DentalPrint 3D scans of dental casts are used to 7 generate overlays quot using various pressure and deviation Bitemark Analysis Using 30 Scans DentalPrint The overlays are compared with the photograph of the bite markst Matching Using Dental Codes CAPMI WinD 14 15 15 12 21 20 1E 13 1 39X Eli 1 MEI 1E MUD 13 399 EU 31 21 quotaquot 22 quotvquot 23 39v39 24 quotvquot 1 r 2 4 5 III III OdontoSearch Different people may have the same dental codes In the past the strength of a match between a PM dental code and an AM dental code is based on the clinical experience of the dentist OdontoSearch provides an objective means of assessing the frequency of occurrence for a dental code OdontoSearch TABLE 6 322 ren nmsg vquanr fawnpangms am me Damiigrf IS C39OHS39 dam wnh on mom39s mmquot premoh n s Det a39ii39eJ rSEiiiIVS with ONLY MOLARS and PrimI OI39ARS N19422 E gt Dental Pattern Universal Charting M posterior teeth 2 V V V V V mum E V V 39I V V V V E i Numhar re ght 1 l 0 39 V V v 39V39 V v v v v V V39v v V 0 v v v v K V V V V v39 V gtltgtltZ 4 T lt r4 ltlt ltlt v A O V I 5 1 3 036 f 12928 3656 4 Automatic Dental Identification System Matching Distance 2757 Imposter Genuine image has a smaller matching distance than the imposter image Images with smaller distance are included in the candidate list Feature Extraction Atlas Registration l Summary History and status of forensic odontology Dental Anatomy Main applications Comparison to other forensic biometrics Famous Cases Computer aided forensic odontology References Adams B The diversity of adult dental patterns in the United States and the implications for personal identification J Forensic Sci 2003 483 Adams B Establishing personal identification based on specific patterns of missing filled and unrestored teeth J Forensic Sci 2003 483 Anguita C DentalPrint 20 Department of Forensic Medicine and Forensic Odontology software engineering department 2003 27 Feb 2005 lthttpwwwugresstelladentalprintfilesDentalPrintDocpdfgt Bowers C Arguments on the individuality of human teeth 22 Feb 2005 lthttpforensictowebhomebitemarksgt Bowers C Johansen R Digital imaging methods as an aid in dental identification of human remains J Forensic Sci 2002 4723543 59 Brannon R Connick C The role of the dental hygienist in mass disasters J Forensic Sci 2000 452381383 Brannon R Kessler H Problems in massdisaster determination a retrospective review J Forensic Sci 1999 441123127 Central Identification Laboratory at JPAC the world s largest forensic laboratory Joint POWMIA Accounting Command 26 Feb 2005 lthttpwwwjpacpacommilCILOdontologyhtmgt Fahmy G et al Automated Dental Identification System ADIS 30 Jan 2005 lthttpdgrcorgdg02004discpresentationshealthfahmypdfgt Forms functions and functionals in Lisp Functions and forms Typical to use the word function impreciser and use it to refer to forms such as y x Let be an expression that stands for a function oftwo arguments 7 should make sense to talkabout ZS 7 But y x2 3 not conventional notationl Church refers to expression such as y2 x as a form Forms can be used to specify functions ifwe can determine correspondence between variables in the form and the ordered list of arguments Lambda notation Church s l notation used to promote a form into a function Example 1x y y x is a function oftwo parameters 1xyy2x3 4 19 Lisp distinguishes functions and forms and provides facility for defining functions Distinction necessary for thinking about higherorder functions Lambda expression List with following syntax lambda lambdailist body where lambdailist is a list of symbols and bodyis a sequence of 0 or more forms Points to note Lambda expressions are not functions they are not even forms mbda expressions are said to name the function objects they specify similar to how the symbol names the binary comparison for equality Retrieving functions from names There are many contexts in which we will want to retrieve a function object from its name Eg ifwe want to pass a function as a parameter to another function Why might we want to do this Lisp provides special syntax 7 name returns the function named by name This syntax is often applied to names that are lambda expressions Calling a function object The function funcall is used to apply a function to one or more arguments Example funcall 39 2 2 To see difference between function object and its name try running funcall 2 2 Functions from lambda expressions Example sstf square 1ambda x x x Such a function can then be called by funcall square 3 9 Note setf or set eld function modifies the envrronment to associate its rst argument with its second Akin to setting a global variable Functionals Lisp can treat functions as data Functions can be arguments to other functions Functions can be constructed and returned Functions that manipulate other functions are called higherorder functions or functionals Example Function arguments Example Fnction that takes a function and a list as arguments and constructs new list by applying function argument to each element of list Simple de nition of the mapcar functional defun mapcar f 1 cond null 1 nil t cons funcall f car 1 mapcar f cdr 1 Application of mapcar mapcar oddp 391 2 3 4 5 gtT NIL T NIL T More general version ofmapcar takes multiple lists as arguments provided the function object takes multiple arguments Eg mapcar 39 391 2 3 393 2 1 gt NIL T NIL Example Returning a function What does this function do defun f 39 lambda x y funcall g y x Answer Takes binary function and returns new binary function that reverses arguments Example funcall f 39 2 3 1 Currying functions Suppose we have a situation where a complicated function has two arguments 7 First argument is expensive to compute but needs recomputation oniy rareiy 7 second argument is cneap to compute out cnanges on every function invocation For ef ciency we d like to construct a specialized function every time the rst argument chan es 7 Specialized function would have already evaluated first argument an t us e a unaryrunction tnat is appiied oniy to second argumen 7 Process knovvn as currying arteriogician Haskell Curry Currying example We can de ne a general function that curries an arbitrary binary function un currytamary t x u39 lambda y uncan t x y Exam le sec aan2 currybinary 39 2 uncan m2 3 2 5 Aside C39unying is a mt39class prugramming idium in functiuna languages such as Haskell Function calls Procedure calling and parameter passing pose subtle semantic challenges Callbyvalue vs callby name in Algol60 Identity declarations and proceduring in Algol68 How does Lisp de ne the semantics of procedure calls and parameter passing Let s explore the question by way of example Function evaluation In general a Functlon definition comprises Declaration of El ormore formalargumenls Definition of a function body wnicn may reference tne formal arguments and pusslbly uthervarlables as Well a Functlon call comprises Narnan of a function to call and List of actualargumen s Functioncall evaluation generally involves a Evaluatan actual arguments e substituting actual arguments for formal arguments in tne body Argument evaluation order Three general questions we might ask about the evaluation of arguments in a function call 1 What happens ifwe substitute the argument expression into the formal instead of its value 2 In what order should arguments be evaluated 3 What happens with recursion Review exercise Do any of these issues look I ke something we ve seen in other languages Argument evaluation order Two major strategies for choosing the order with which to evaluate arguments Appfestive order Evaluate the actual arguments rst for the formal arguments in the function body Evaluate argument expressions only when needed Common Lisp uses applicative order but actual arguments can be quoted to suppress evaluation Argumentevaluation example Consider the Lisp de nition de un square x x 0 Using applicativeorder evaluation we get squa e 5 2 square 7 2 k 7 7 2 49 Using normalorder evaluation we get square 2 5 k 2 5 2 5 49 Notice 7 Applicatiyeoroer evaluatlon tends to be more efficient as argument forms are computed only once 7 Normaleorder evaluatlorl l5 safer however Metaprogramming in Lisp Objectives for today Understand the use of macros to improve the user level syntax of complex functions and forms Brief introduction to the key ideas and techniques of metaprogramming Further understand how the basic primitives of Lisp programming are implemented Motivating example Suppose we want to define a function that will print a special value when invoked with a positive paramter ie we would like whenpositive 2 print 39alarm ALARM ALARM whenpositive 3 print 39alam L Definition with bug Suppose we de ne the function as follows defun whenpositive numb r sult w en plusp number result Then whenpositive 3 print 39alam Incorrect value printed NIL iCorrsct Value returned Question How could we rede ne with defun this function to have the desired behavior Answer Definition without bug defun whenpositive x f when plusp x funcall f x But note we must now invoke with whenpositive 3 39lalllbda x Print 39alam Orwors defun alarm x rim alam p whenpositive 3 alarlln Assessment of defun solution Awkward userlevel syntax Must either create a separate function eg alarm that is then another global function to maintain or Wrap the form to execute in a lambda expression Must design function to apply the argument function to he argument value just in case some context might require it Macros Function from forms to forms When called computes new form to be evaluated in place ofthe macro call Sometimes called a macro expansion Important for writing good code Enable code that is elegant at user level but translated to more complex forms prior to evaluation Lots of predefined macros un g def Users may de ne macros using de fmacro Formal Syntax K Stirewalt CSE 891 Fall 2004 Definitions Programming language set ofstrings possibly in nite Lexicalproperties what are the basic words in the language The terms token an lexeme are o en used Syntax what is the structure ofwellformed programs Grammar description ofthe syntactic properties ofa language There may be more than one grammar for a single language Context sensitive properties also called static semantics what rules for legal programs exist that are dif cult or impossible to detect syntactically More definitions Semantics what is the meaning of a legal rogram This is typically expressed as the relationship between its inputs and outputs Runtime environment what abstract machine rograms assume exist Pragmatics extralinguistic content use to convey information to the compiler for example to indicate opportunities for optimization Phrasestructured grammars Grammars in computer science described by a series of rewrite rules 0L a 3 The string on can be rewritten with the string 3 Strings on and 3 include terminal and non terminal symbols Terminals comprise the basic symbols of the language Nonterminals are definitions describing sets of strings Classes of languages Grammars expressed this way are called phrasestructured grammars Constraints on the format of the rules engender different classes of languages To determine Whethera particular string is in a class some form of abstract machine is required Formal grammars G N 2 P S N nite set of nonterminal symbols 7 a llt a variables syntactic caleguries 2 nite set ofterminalsymbols N W 2 Q P nite subset of productions C N C x C c N o 2 valid symbols C valid Strings over those symbols 0 N o valid Strings Containing at least one nonrterminal S E N the sentence or start symbol Chomsky hierarchy Type 0 EN gt In no restrictions Turing machine recursively enumerable sets Type 1 EN gt a idol 2 lENw l right hand side at least he lelt hand side nondeterministic linear bounded automata subset ofthe recursive sets context sensitive languages Type 2 N gt In single nonterminal on the le hand side nondeterministic push down automata context 39ee langua es Type 3 N gt cM c right hand side has exactly one terminal and at mos one nonterminal nite state acceptors regular sets nl w o Lo Describing lexical properties Lexlcal analysls breaks a program lnto baslc umts e constants keywords operators varlables comments pun uatlun Some otner processan ls also pe orme e symbult construction constant evaluatlun and keyvvurd nasmng ln prlnclple context rree grammars could be used to descnoe tne lexlcalpropenl r language However contextfree parslng ls owl ln practlce lt ls pettertnan tnat bu stlll more costly tnan ls requlred to lexa program ln practlce Wnen comblned Wlth cnaracter lnput lexlcal analysls or programs domlnates compllatlon tlm Lexlcal propertles are descnoed Wlth regular expresslons and processed Wlth nmte state macmnes Backus Naur form Used for the de nition ofAlgol Nonterminals in angle brackets ltidenti ergt Lelthandside separated from right hand side by Three possibilities for right hand side 7 Nothlrlg l tne empty string 7 A sequence oftermlnals and nontermlnals a replacement 7 A series or replacements separated by is These are considered alternatlyes Suf cient to describe any context ee language Examples of BNF xpression gt lt term gt operator gtlt termgt si pie arithmetic expression gt lt adding operator gt lt termgt lt simple aritnm a llt llt lt aoo39 g operator gt l lt term gt actor gt l lt term gtlt multiplying operatorgt lt actor gt lt mulliptylng operator gt xl l actor gt lt primarygt l lt actorgt elt primaiygt lt primaiy gt lt u l lt var l lt on on esignatorgt l lt arithmetic expression gtl igneo nomhergt gt Extensions to BNF BNF suf cient for any contextfree grammar Various extensions simplify speci cation of programminglanguage grammars Each of extension can be described in terms of original BNF These do not change the class of languages de ned Collectively extensions are called EBNF extended BNF EBNF 1 Remove brackets from nonterminals Replace with a Terminal symbols enclosed in apostrophes Rules terminated with periods Parentheses for grouping Orthogonality of language features The ALGOL 68 experience llyou call me by name it s Veert but inou call me by value it s Worth 7 Nikiaus erlh when asked haw l0 preneunce his name What s in a name That which we call a rose by any other name would smell as sweet quot 7 Julie Contributions to programming New features that exceed those of ALGOL 60 Constant eclarations Userde ned data structures eg records unions Dynamic memory allocation Expressions on lefthand side of assignment operator Array slices Assignment statements are expressions hat return values Heavily influenced the design of the C language ALGOL 68 design goals Orthogonality of semantic machinery Motivated by ambiguities arising 39om feature composition in ALGOL 60 De ne a small number of semantic concepts that compose with one another in meaningful ways Formal de nition of syntax and semantics Static type mode checking Key distinctions Distinction between syntactic entities phrases and semantic entities values and actions Action is a process that constructs and manipulates es Phrase is the piece oftext a programmer writes Phrases are elaborated to perform actions Document organized around semantic entities in sharp contrast with ALGOL 60 report Key semantic distinctions Categories of entities in the language speci cation Hardware representations lett uns eci ed Internal objects opaque semantically meaningful External objects things the programmer can see or manipulate Example Values vs expressions Value Internal object represented by a bit pattern which is operated upon when program is elaborated Expression Phrase ie an external object hat yields a value What s in a name A value A set of values A memory location A set of memory locations ALGOL 68 makes fine distinctions between these roles which were not distinct in ALGOL 60 Values and identifiers Consider the ALGOL 60 declaration real x This declaration serves two purposes 7 o reserve a memory locatlon that can store values of type real and 7 To assoclate the ldenllflerxvvlth that locatlorl In ALGOL 6 hese purposes are seen as orthogonal and are treated separately 7 Memory locatlons are nardware representatlons of names vvhlch to other values 7 identifiers associated Wlth values vla lderlllly declaralluns a o lt a 3 a Q 9 Creation and use of names Names created by expressions called generators r Ioc u creates a local rlarne that refers to values of mode 7 local narnes correspondto locatlorls lrl autornatlc storage 7 global narnes correspond to locatlons allocated on the he p Assignation makes a name refer to another value 7 N E e N ls expresslon or rnode reru and Ean expresslon or rnode u r Eg1oc real 2 L2 7 Note narne refers to new value ldentlflerthatpossesses the narne does not then possess the new value Identity declarations De ne the value possessed by an identifier Syntactically s E where is a mode 5 an identi er and E an expression of mode 11 egrea1 pi 31415927 Note Not a variable declaration Eg assignation pi 314 is not meaningful More po werful as the value could be of any mode including a procedure Example Identity declaration ref real x 1 ca real is roughly equivalent to the ALGOL 60 declaration Question What is the ALGOL 68 equivalent of real x 2 Coercions Defn Languagede ned transformation of the mode of an expression into another mode Indicated by the context of an expr s ion Usually specifies an action for transforming a value of form mode into a value ofthe latter Examples Derelerencing an expression ofmode rent in a context that expects m y x z y wn rexandyofrnode re real Proceduring an expression in an identity declaration 13201 real p 3114 x Constructionapplication of routines Programmer constructs routine by writing suitable phrase preceded by list of formal parameters 7 E g b001 bool boo z t a then zue else I n e Denotatlon as above only way to construct a procedure Application 7 en routlne ls called pararneters are elaborated before the body of the routlrle ls elaborated 7 Actual pararneters bound to rorrnal pararneters uslng ldentlty declaratrons vvhlch are lntroduced to precede the body of the routlne pnor to elabor tlon e Advantage uch cleaner sernantlcs of procedure callsthan we saw for ALGOL 60 FP quotA larlable ln a proposlllon otloglc is after all nothrng out a token that characlenzes certarn argument places and operators as oelonglng together thus ll has the status eta mere auxrllary nohon that is reallylnappropnale to the constant eternal essence nflhe proposlllons Ufluglc 7 Moses Schorlflrlkel FP Funchonalprograrnrnlng programmlng Wltn tunctlons lrlstead or yanaoles Denne a tunctlon as a comblnatlon or others uslng yanous corntnnlng terms Thlrlkofthefurlctlorl belng denned as a set otnlters or plpes each tran storman its argument oplect lnto an output oplect Each tunctlon talltes a slngle argument oblect and produces a slngle oblect result The are no declaratlorls other than tunctlon dennltlons ln tactthere are no yanaoles You program With functlorls not yalues Programs should be read trom nght to left mathematlcal order except tor condltlonals The set or comolnlng torms ls llrnlted urlllke the kcalculus FP llllnols FP lrlterpreter Example FP function Def IP Cl 06 El TRANS and TRANS are functions on are combinin Inner product is the result of three operations on a of Input vectors First transpose the input pair ofvectors using T A S into avector o airs Then apply the multiplication operator using apply to a Iquot 1 to each pair ofthe vector producing a vector 0 results Finally add up the elements ofthe vector using INSERT 1 producing a scalar result IP SAM PLE EVALUATION IP2ltlt1 2 3gt lt5 5 4 4El1tEITRANSltlt1 2 3gtlt5 5 4 defofIP 4mrnmsltlt1 2 3gt lt5 5 4 defofcomposition 4mltlt1 5gt lt2 5gt lt3 4 quotdefofTRANS 4lt tlt1 5gt tlt2 5gt lt3 4 quotdefofnn 4lt5 10 12gt defor 4lt5 4lt1o 12 defofl 4lt5 4lt1o 4lt12gt defof 4lt5 4lt10 12 defofl 4lt5 22gt defof 2a defof Motivations Wurdaalaaallme programmlng unlt or tradltlonal programmlng is the assignment Statement tnat alters One varlable yon Neumann Bullsneak the archltectural llrnltatlons or early machlrles lead to the lmperatlye style or language Slngle accumulator data in memory lnstructlon fetch decode and xecute rograms are stath representatlons of dynamlc processes a Structured pro rammlng was a reactlon to thls on Use or names tor parameters engenders complex semantlcs tor argument passlng call by nameyalueletc Hard to reason about programs because or the yanety or teatures Backus 3 tiers of complexity Simply functional language fp no state limited names closed set offunctional forms simple substitution semantics algebraic laws no evalapply available to programmers Formal fp system ffp extensible set offunctional forms functions can be re resente o 39ects conversion from object representation to applicable form formal semantics Applicative state transition system ast ffp with the ition o a statet at can be modi ed with coarse grained operations An FP System A set of objects the data to be transformed A set of functions for computing the transforms builtin amp userde ned A set of combining forms fixed for the system A set of definitions for extending the set of functions The operation of application for combining objects and functions FP Objects Atoms numbers True and False characters LISP atoms 1 nil Sequences tuples elements are objects similarto LISP lists L quotbottomquot or quotundefinedquot f L is part of a sequence then the sequence itself is L This property is called strictness FP Functions Builtin or userdefined Map an object into another object Are strict L preserving f L Are applied to an object with the colon operatorf x where x is some object and not a name The user can define functions with Def recursion is allowed FP Builtin Functions Arithmetic List processing tl atom null reverse equals length apndl apndr rotl rotr tlr Selection 1 car 2 cadr 1r 2r Logical and or not Restructuring trans distl distr Identity id Iota integers up to Iota 5 lt1 2 3 4 5gt FP Functional Forms p xFalsegtg x L xltx xgt and ngtlgt Functional forms continued Truegt whepffx pxFalsegtX L Example Definitions Def last null El tl a 1 lastEltl null El tl a 1 last El tl Def sub1 El id Def er eq El id Q Def eq0a1llid Esub1 Def El iota FP Semantics To apply a function replace its use by the right hand side of its de nition Nonterminating executions yield L The semantics rely on the primitive functions and combining forms Hence it is better to think of an fp system instead of the fp system Semantics for the primitive functions and mbining forms were given informally in the paper FP Semantics To obtain the meaning of a functional application fx consider the following four possibilities 1 fis a primitive function 2 evaluate it immediately use the de nition ofthe form to o tain a new program and appl it e functional forms are de ned using McCarthy39s conditional expression fis a userde ned function 2 plug in the de nition for the occurrence 4 lfnone ofthe above 2 the result ofthe application is L N 3 HI 3 2 a nI E 3 U o Algebraic manipulation of programs fp s simple semantics enable program manipulations and optimi a ions These are expressed as algebraic laws For example the following law indicates how composition distributes on the right over construction f 9 El hx ghx def of composition f hx x gt def ofconstruction f El hx 9 El hxgt def of composition f El h 9 El hx def of construction Example laws pafgE pEhafEhgEh hEpafgpahElfhElg papafghpafh OLfEgOLfEIOLQ Lisp From J M McCarthy Recursive functions of symbolic expressions and their computation by machinequot Communications of the ACM 34 April 1960 Lisp List processing language Developed by J McCarthy in the late 19505 Focus on symbolic ratherthan numeric computation Heavily used in artificial intelligence Hardware implementations exist Key ideas Interpreted language Structure of interpreter is visible to programmers Data can be evaluated as code code can be manipulated as data Dynamic memory mgmt with garbage collection Conditional expressions Functionals ie functions that create functions Defined in terms of itself operational semantics Prefix notation Lisp has a concise syntax based on lists and prefix notation Function application represented as list in which rst element is function name and remaining elements are the arguments ie 3 4 gt 7 2490gt15 Straightforward extension to nested expressions 4538gt 15 Atoms Atoms are primitive data symbols or numbers Symbolic expressions ie Sexplessions de ned recursively in terms of atoms and dotted pairs An atomic symbol is an Sexpression eg A A numeral is an Sexpression eg 123 lfe1 and e2 are Sexpressions then so is e1 e2 CONS cell depiction Dotted pair can be thought of as a cons cell memory word containing pointers to two Sexpressions eg mac A B U V x Lists All data stored in the form of list structures Lists can be of arbitrary length Dynamically allocated as space is needed Simple and elegant garbagecollectors Represented as nonatomic dotted pairs whose second element is eventually NIL Example ABCDE A B CDE NIL List implementation IBM 704 machine word car Contents ofaddress register cdr Contents ofdecrement register A B Also called a CONS cell List address of a cons cell Exercise Draw CONScell representation of the list A B C D Sfunctlons on lists carL returns rst element of list L car Of an atom IS undefined CdI39L returns second element oflist L I e lISt you get after removingfirst element 7 cdr of an atom IS undefined cdrNlL NIL 7 thus empty list IS both an atom and a lISt consA B constructs a CONS cell with A as rst element econd result is a list if B is a list or NIL Sfunctions continued Properties carconsx y x cdrconsx y y conscarxcdr1x x provided x is not atomic This mechanism for defining primitives in terms ofone another is algebraic similar to axioms of abstract data types Sfunctions continued atomX returns T ifx is an atom NIL otherwise eqx y returns T is x and y are both atomic and the same symbol returns nil if both atoms are different undefined otherwise nuIx atomx eqx NIL cadrx carcdrx caddrfx carfcdrfcdrx Conditional expressions Problem How to represent control structures in Lisp Iteration accomplished using recursion Alternation requires a new language feature COND primitive takes a sequence of pairs as arguments each pair comprises a predicate and an expression Axiomatic semantics Categories of semantic mechanisms Operational semantics de nes a virtual machine for executing programs in the language Denotational semantics Program denotes a mathematical function Axiomatic semantics Program modeled as a set of invariant relationships that hold whenever the program is executed Axiomatic semantics Meaning of a program relation between its inputs and outputs specified by input assertions pieconditions and output assertions postconditions assertions are predicatelogic formulae atomic propositions are program variables Example assertion y 515 Where x and y are variables Axiomatic semantics cont Key ideas Formalize the meaning of each type of statement using a deductive system of axioms and inference rules Program can be proved correct by constructing a proof in this system even be synthesized 39om its axiomatic speci cation by searching for such a proof using the structure ofthe proofto construct the program Contr butions to programming Proofs of program correctness Notion of invariants to aid in documentation and understanding Hoare triples Assertions of the form where P amp Q are assertions and S is a statement Interpretation fP is true before execution of S and if S terminates then Q is true thereafter Example x5 Xx 1x6 Semantics of assignment Given an assignment of the form x E and a postcondition P Axiomatic definition of assignment is PxaE xE P Where P xaE is the consistent substitution of E for all occurrences ofx in P Example Theorem k5kk1k6 Proof Let P 2M 6 be the postcondition By the assignment axiom the pre condition must be Pk ak 1 Pkk12k162k5 Example Theorem agt0aa 1820 Proof Let P 2 a 20 be the postcondition Then the pre condition must be Pa a a 1 Pa aa 1 E a 1 20 Thus a 120 aa 1520 Note this is not exactly what we wanted Inference rules Sometimes a pre condition is strongerthan what is proved by applying the assignment axiom This is OK The following inference rule justi es replacing the proved precondition with the stronger one PgtQ QSR PSR strengtheane Example continued Strengthen precondition to finish proving agt0aa 1a20 from a 120 aa 1a20 Proof continued Note agt0 gt a21gt a 120 Thus agt0 gt a 120 Then apply pre condition strengthening rule Weakening postconditions It may also be useful to weaken a post condition The following rulejustifies such an action PSQ QgtR PSR WeakenPust Semantics of read and write O commands assume existence of input and output les We use IN and OUT to indicate contents of these les in asser ions Axiom for read INKL A PVaxj readv INL A P Axiom forwrite OUTLAEKAP writeE OUTLKAEKAP Semantics of sequencing Sequential composition of statements requires the postcondition of the first to establish the precondition of the second PSiQi Q52R P5752R sequence Semantics of conditionals The it command involves a choice between options PABS7Q Pi BSZQ PifB thenS7eIseSZendifQ ll39Else Semantics of conditionals cont When there is no else part the rule simplifies to PABSQ PA B gt Q PifB thenSendifQ innen Semantics of loops Proof rule organized around loop invariant Assertion which Musthold initiallvi lvlust hold after each executlorl of loop bodv arid Combined Witn em Condltlorl must lmpiy loop oosrconoition Captures the essence of computation in the loop Requires insight to deve op MB S I I whiIeBdoSendwhiIe Ii B lluupl Example N20 k f1 while k gt 0 do 1 end while IN Question What is the invariant Example continued C3nampdalexnvauant l2 Nlerwl A mo Observe By tabulatmg values we can a scovez a Value 7 15 JUVEU ant Example Setting up invariant Theorem Proof N20 N20 kNf1 NNAN20 fkN A k20 F kN A kgo 1kN A k20 f1 fkN A k20 Example Invariant preserved in body Theorem Proof IAkgt0 IAkgt0gt fkNlAkgt0gt k 1 fkk 1N kgt0 I ffk fk 1NAkgt0gt fk 1NA k 120 fkN A k20 E I Example Assertion after loop Proof IA kgt0 fklv A k20A ksO fklv A k0 flv A k0 fIv Guidelines for discovering invariant Loop invariant describes relationship among variables that does not change as loop ex 7 variaoies rnay cnangeyaiues but relationsnip rernainstne sarne Constructing table ofvalues for variables o en reveals a property that does not change Combining what has been computed wi h what has yet to be computed olten yields a constant Expression related to test B for the loop can usually be combined with assertion B to produce part of post condition Algol60 style blocks Block declarations take the form Block gt Deciaration begin Command end Declaration gt const identifier Expression identitier Type i procedure identitier is Block i procedure identitier identitier Type is Block Example declare const x iUi var y integer begin read y y x y write y rId Semantics of blocks Procedureconstant declarations pre processed For each declared constant cwith value N predicate Cons has a conjunct c N For each declared procedure p predicate Procs has a Coniunct Judip El vynere El istne body of y a coniunct parameterp F wnere Fistnerorrnal parameter or p it any Proof rule is PIDCS P ConstCQ PDbeginCendQ sequence Nonrecursive procedure calls Calling nonrecursive procedure with no parameter requires proving logical relation of assertions ound the execution of procedure body More precisely P B Q bodyproc B Cam PPr00Q Example procedure call dec are Hem pr cedure Square is Free is the assertion beg39quot x bodysquare x 39 x x x x x en Cons is the assertion true begin Thus we must show square DUIquuare x x x d i XAlrue squarexAN To apply CallO we must show XAlrUE x xtx xmw Calls with parameters Calling nonrecursive procedure with parameter requires binding actual parameter to formal in pre and postcondition More precisely P B Q bodyproc B parameterproc F C H PIF951P CE QIFeEI Example procedure call declare procedure increment step integer is begin x x step F mcs paramelerimcremenl slep end A undyilncremenl ix x slap 9939quot Csnsl E lrue incrementy rid We must show paramelerrincremenl slep A oodyimcremeni x x slep i Fwy Nilrue lncremenly X wa yN Proof By rule for procedure invocation with parameters we must show XMA stepN x39xstep XMN stepN Formal proof Paramefemncremerif seep mdynncremeni x xosfep x MAN mx x xea Amy was m parametemncremeni step ix May mm A mummy Wdlmuemenf x xosfep x MaiM N ix MAy m mine nmeenumnerenemi siep Integer I begin x xostep em begin inerenemiy em ix MONxv m Origin of Programming Languages Epoch Algol60 K Stirewalt CSE 891 Fall 2004 lam strongly of the opinion that great works have a quality which is lost in textbooks and thatthe reading of them is educationally very important Bertrand Russell circa 1937 Why study Algol60 Algol60 report itself Model for how to describe a Ian uage Separate treatment of syntax and semantics Formal approach to syntax and semantics Model for how to use notation and terminology in a technical paper Many features foreshadow future developments edurecallparameterpassing mechanisms s adow distinction between imperative and functional languages Ambiguities led to decades of language and compiler research Algol issues Formal syntax Control structures Scope of declarations Storage classes Static own automatic Type checking Parameter passing Call by value and by name Attempt at precise semantics Control structures 1 f then e1 se without endi f dangling e1 se Compound statement nesting Designational expressions and switches yield labels For loop whi a e to variable t ltfor7115tgt do 7 roar t comma separated net or lte1ementgt lte1emen gt antimet c expressxon i A step lt5 untn C i a mule gt Dangling else Algol has both if then and if then elee constructs Nested if statements are syntactically ambiguous e if B then if 82 then 3 else 82 Does 82 go with rst if or second Problem is solved in Algol68 and later languages by requiring an explicit termination statement eg fi or endif What s in a name A value A set of values A memory location A set of memory locations An essential decision that separates imperative from functional languages and places strict requirements on symbol table design Declaration Defn Syntactic construct tnat associates lrlforrnatlorl Witn a name e lnrormation Type modinapility storage class etc e E g nteger 3 There may be independent declarations of tne same name in different parts of tne program e Scope rulesdeterrnlrle nnicn declaratan applies nnen tne name appears in the text e Scope ofa declaration F39urtlurl or programto nnicn declaratan applies Related concepts e Blndlng Association ufa particular storage location to some name Dynamic counterpart of a declaration e visibility accessibility or a pinging Whether giyen storage location can be sse rom giyen line e tiretime F39urtlurl or prugrarn s execution Where a pinging nolds Alternatives Statlc autumatlc Lexical vs dynamic scoping a bestquot Lexicalscuplng wnen declaration 1 t r m associated Witn agiyen referencels Procedure e m 1 foundb searcnin Ward in tne et A begln of nested blocks Witnin tne program nteger m source code 9 p end 4 p end Dynamic scoping wnen declaration associated Witn a given refererlc i ma eb rcning up din tne set of nested contexts in tne execu lon environmen Parameter passing procedure call May be simple vana fx3 Actual argument Expression that appears within a ble Formal dummy argument Identi er used in procedure de nition as surrogate for actual rgument Eg procedure fa ints s a Parameter passing mechanisms Call by value Actual argument is evaluated when procedure call is made Computed value replaces all references to formal argument in called procedure Call by name Actual argument considered as its own procedure thunk Whenever value 0 corresponding actual argument is referenced the procedure is called and a value is computed Useful when actual argument is an expression Expression is recomputed on every reference Other mechanisms Call by reference Works for actual arguments that re boun o a storage location l values Address of storage location associated with formal argument Used in languages such as Fortran and later Java Supported In C Call by value return Works for lvalues Formal argument is a copy of the actual argument When procedure returns value of the formal argument copied back into actual argument Example of callbyname real procedure sumk 1 u ax value 1 u Question What is the effect of nteger k 1 u x sumi 1 m sumj 1 n Alij vm A problem With callbyname Semantics procedure swAPxy ree1 x e supp I 1 39 AU 39 N2 and we execute SWAPi Ai A erward i 2 Question How should one assign meaning to a programming language Answer Translate language constructs into something simpler but more precise Eg virtual machine instructions Eg mathematical constructs eg sets functions Eg simpler formal language e A calculus Eg show how to rewrite program that uses a complex feature into an equivalent that does not use the feature Rewrite semantics of proc calls Basic idea Replace procedure call with a new block that contains a modified body begln ltvaluerparamrdeclrlistgt fowl yr gt ltvaluerparamrin1trlistgt ltbodyrofrfoogt end Parameter passing rules For each formal argument f2 If f is a value parameter then Append to ltValueparamdec11ist tne declaration of a new varlable Append to ltValueparaminit1ist tne asslgnment statement 2 e Where ltegtlstne actual argument If f is a name parameter then Replace occurrences of tin ltbodyottoogtWlth 9 Apply systemath renamng to nandle confllcts Copying blocks Copying blocks continued Rule Create new copy of the block replacing Applying textual substitution instances of locallydeclared identifiers with fresh identi ers xltnlyltn2 to outer block begin integer x y begxn Integer x y begm 1ntzeger n1 n2 x o z z n11 n2 2 begin integer y begin 1ntzeger y begin 1ntzeger n2 1 xzyz1 gt 11 211 XWYJ 39 Yzy1 n2 1 y 1 en end prxn xy print xy end end end print n1n2 end Copying blocks continued Copying blocks continued Applying textual substitution n2 9 n3 Note this block behaves as expected to inner block begxn 1ntzeger n1 n2 111 o begxn 1ntzeger n1 n2 n 2 o t n t begxn 1ntzeger n1 n2 begin 1ntzeger 113 t t 11111121 n1 1111 begxn 1ntzeger n2 begxn Integer n3 n3 113 1 n1 n2 2 1 gt 111 113 1 n2 n21 n32n31 end prxnt n1n2 end end prim n1n2 end end prim n1n2 end Ambiguity side effects Ambiguity Incomplete function begxn 1ntzeger a 1nreger procedure xy L0 0f Djig bo ef ge begin Wnen control reaches L value x real x y doesx contalrl tne value rnreger x y Issue Order ln Wnlcn real procedure p 27 a z I z X1 D ramStO procedureswlth begin rnreger pmcemze 900 Side effects are evaluated p z 1 1ntzege x Example To get45 flr5t a 2 evaluatederlornlrla r 3 wnlcnylelos2ano prim a a 9a 9a and to sets a to 2 as a Slde effect
Are you sure you want to buy this material for
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'