### Create a StudySoup account

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

Already have a StudySoup account? Login here

# FIRST S W 1

UT

GPA 3.75

### View Full Document

## 14

## 0

## Popular in Course

## Popular in Social Work

This 101 page Class Notes was uploaded by Mr. Kianna Bogan on Sunday September 6, 2015. The Class Notes belongs to S W 1 at University of Texas at Austin taught by Staff in Fall. Since its upload, it has received 14 views. For similar materials see /class/181528/s-w-1-university-of-texas-at-austin in Social Work at University of Texas at Austin.

## Popular in Social Work

## Reviews for FIRST

### 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/06/15

Shape Matching ShapeBased Recognition 0 Humans can recognize many objects based on shape alone 0 Fundamental cue for many object categories 0 Invariant to photometric variation Slide from Pedro Felzenszwalb Shapes vs Intensity Values Similar to a human in terms of shape but very different in terms of pixel values images frum Eleiungie at ai Applications 0 Shape retrieval Recognizing object categories 0 Fingerprintidentification 0 Optical Character Recognition OCR quot a M o I ecu Ia r bio I og y Geometric Transformations 0 Often in matching images are allowed to undergo some geometric transformation 0 Related but not identical shapes can be deformed into alignment using simple coordinate transformations 0 Find the transformations of one image that produce good matches to the other image l 699 d c 39 39 39 t 39 39 h g 39 Jam 39 y I I 56 age 3 0 r 39 V m0 SIT 39 0 39 leg a 39 39 5 39ef 3009 85 a 999 3 39 gt 5 v 40 39 f 3339 t 39 gt emgOe 39fgg3939fojo f v 3399 9 95 5 39 39 39 w 39 S i 6393 13539 v I is 39 r 99 9 O V 9 o 3 2quot 39 I 1 V V 0 A j oquot 39 39 39 Vs t w V A A s Images from Belongie et al Biological Shape 0 D Arcy Thompson On Growth and Form 1917 0 studied transformations between shapes of organisms 0 1 2 3 4 5 Fig 177 Human skull Fig 179 Skull of chimpanzee Fig 180 Skull of baboon Slide from Belongie et al Related Problems Shape representation and decomposition Finding a set of correspondences between shapes Transforming one shape into another Measuring the similarity between shapes Shape localization and model alignment Finding a shape similar to a model in a cluttered image Slide from Pedro FeiZenSZWaib References 0 Shape Matching and Object Recognition Using Shape Contexts by S Belongie J Malik and J Puzicha Transactions on Pattern Analysis and Machine Intelligence PAMI 2002 O Recognizing Objects in Adversarial Clutter Breaking a Visual CAPTCHA by G Mori and J Malik in Proceedings IEEE Computer Vision and Pattern Recognition CVPR 2003 0 Using the InnerDistance for Classification of Articulated Shapes by H Ling and D Jacobs Proceedings ofthe IEEE Conference on Computer Vision and Pattern Recognition CVPR 2005 0 Comparing Images Using the Hausdorff Distance by D Huttenlocher G Klanderman and W Rucklidge Transactions on Pattern Analysis and Machine Intelligence PAMI 1993 O A BoundaryFragmentModel for Object Detection by A Opelt A Pinz and A Zisserman Proceedings ofthe European Conference on Computer Vision ECCV 2006 O Hierarchical Matching of Deformable Shapes by P Felzenszwalb and J Schwartz in Proceedings ofthe IEEE Conference on Computer Vision and Pattern Recognition 2007 Hausdorff 39 Distance ou lne 0 Shape Distance and Correspondence 0 Shape Context 0 Inner Distance 0 Hierarchical Approach 0 Hierarchical Matching 0 Machine Learning Approach 0 Boundary Fragment Model Comparing Images Using the Hausdorff Distance 1993 D Huttenlocher G Klanderman and W Rugklidge Hausdorff 39 Distance oveWIew 0 Use Hausdorff distance to compare images to a model 0 Fast and simple approach 0 Tolerant of small position errors 0 Model is only allowed to translate with respect to the image 0 Can be extended to allow rotation and scale 3quotstfo Hausdorff Distance Istance 0 A means of determining the resemblance of one point set to another Examines the fraction of points in one set that lie near points in the other set HA B maxh A B hB A h AB max min da aEA bEB Example Given two sets of points A and B find hAB Example a 2 a1 Compute the distance C between 31 and each bl 0 b3 b Keep the shortest a 2 31 o b3 l b Example Do the same for 32 a2 10 Q x b 3 o Example Find the largest of these two distances 57 Example This is NAB Example This is hBA a 2 a1 0 Q O b3 b 1 Example HAB maxhABhBA 2 1 Q I O b3 b1 Example This is HAB a 2 a1 0 Q O b3 b 1 ausdm Generalization Distance 0 Hausdorff distance is very sensitive to even one outlier in A or B 0 Use kth ranked distance instead of the maximal distance 0 Match if hk A B lt 6 0 k is how many points of the model need to be near points of the image 0 6 is how near these points need to be aEA hk A B kth gig 101 E0 Hausdm Distance Transforms Distance 0 Processing can be sped up by probing a precomputed Voronoi surface 0 A Voronoi surface defines the distance from any location in B to the nearest point 7 0 Can be efficiently computed using dynamic programming in linear time Hausdorff Distance Example Matching Hausdorff Distance Example Matching Shape Context Outline 0 Shape Distance and Correspondence 0 Hausdorff Distance gt 0 Inner Distance 0 Hierarchical Approach 0 Hierarchical Matching 0 Machine Learning Approach 0 Boundary Fragment Model Shape ei ntext Shape Matching and Object Recognition Using Shape Contexts 2002 S Belongie J Malik and J Puzicha Shape Context Overview 1 Solve for correspondences between points on the two shapes Using shape contexts 2 Use the correspondences to estimate an aligning transform Using regularized thinplate splines 3 Compute the distance between the two shapes Shape Context Related Work Deformable Templates O The Representation and Matching of Pictorial Structures by Fischler amp Elschlager 1973 I Structural image restoration through deformable templates by Grenander et al 1991 O Deformable Templates for Face Recognition by Yuille 1991 O Distortion invariant object recognition in the dynamic linkarchitecture by von der Malsburg 1993 Slide from Belongie et al Shape Context Sampling Points 0 A shape is represented by a set of points sampled from the edges of the object 0 l l III 9 9 e h n I I I II Shape Context LogPolar Histograms Count the number of points inside each bin Count 4 Count 12 shuenum Ee ungte em Example Shape Contexts Ion r C mages from Be ongwe et 5 Shape Context Point Correspondences 0 Compute matching costs Cpipj using Chi Squared distance lKhik hjk2 Zi 1 009171939 5 h k hj k k1 Minimize the total cost of matching such that matching is 1to1 H W 20 Packed Jonker amp Volgenant 1987 Slide from Belongie et al Example Point Correspondences 1quot a m 11 3 d 22 3 21 M 51 v4 urnm fixWm 32 Thin Plate Spline Model 0 The name thin plate spline refers to a physical analogy involving the bending of a thin sheet of metal 0 The 2D generalization of the 1 D cubic spline 0 Contains the affine model as a special case Shape Context Minimizing Bend Energy 0 The Thin Plate Spline interpolation has the form n rm a1awwayyZwiUllwmi wyl i1 global affine transform local nonlineamansformations where U 739 7392log r2 0 Select a and w to minimize the bend energy 2 2 2 2 2 2 IfR2 265y 2 Z y dxdy Shape Context Example Matching and Transformation a Bvxm Myquot 39 a MM ea Lifak o w 1K w Maggy a m 2 so so m 54 w b X Images from Belongie et al Shape Context Terms in Similarity Score 0 Shape Context difference 116 0 Local Image appearance difference Due 0 Orientation 0 Graylevel correlation in Gaussian window 0 many more possible 0 Bending energy Dbe 133C 16 Dac 03 D56 5011 Shape Context Results Query Similarity Scores amp 0086 0108 0109 0066 0073 0077 A A 32 A 0046 0107 0114 7 0 7 W W 0117 0121 t 1 f 0096 0147 Images from Belongie et al Inner Distance ouuine 0 Shape Distance and Correspondence 0 Hausdorff Distance 0 Shape Context WM 3 5 gt r L r v 0 Hierarchical Approach 0 Hierarchical Matching 0 Machine Learning Approach 0 Boundary Fragment Model Miner Digtamg Using the InnerDistance for Classification of Articulated Shapes 2005 H Ling and D Jacobs Inner Distance overView 0 Its difficult to capture the part structure of complex shapes with existing shape matching methods 0 Replace euclidean distance with the inner distance Insensitive to shape articulations 0 Often more discriminative for complex shapes 0 An extension to shape contexts 032 Model of Articulated Objects 1An object can be decomposed into a number of parts 2 Junctions between parts are relatively small with respect to the parts they connect 3 Articulation on the object is rigid with respect to any part but can be nonrigid on the junctions 4 An object that has been articulated can be articulated back to its original form Images 39om Ling and Jacobs Inner Distance The InnerDistance 0 The length of the shortest path between landmark points within the shape silhouette 0 For convex shapes the innerdistance reduces to the Euclidean distance InnerDistance changes only due do deformations of the junctions Images from Ling and Jacobs Inner Distance InnerDistance vs Euclidean Distance Images from Ling and Jacobs Inner Distance Computing the InnerDistance 1 Build a graph on the sampled points For each pair of points xy 1 If line segment between them existed entirely within the object 2 Build an edge connecting x and y with weight w HIE yll 2 Apply a shortest path algorithm on the graph nner 39 igtance Example Inner Distance nner 39 igtme Example Inner Distance nner 39 igtme Example Inner Distance nner 39 igtme Example Inner Distance nner 39 igtme Example Inner Distance nner 39 igtme Example Inner Distance Inner Distance Example Inner Distance Inner Distance Example Inner Distance Inner Distance Example Inner Distance Inner Distance An Extension to Shape Contexts I Redefine the bins with innerdistance 0 Euclidean distance is replaced directly with the innerdistance Images from Ling and Jacobs 022 Results MPEG7 dataset Algorithm CSS Visual Parts SC m 7544 7645 7651 Alorithm Curve Edit Gen Model IDSC m 7817 8003 3540 Shape Outline Tree 0 Shape Distance and Correspondence 0 Hausdorff Distance 0 Shape Context 0 Inner Distance 0 Hierarchical Approach gt 0 Machine Learning Approach 0 Boundary Fragment Model Hierarchical Matching of Deformable Shapes 2007 P Felzenszwalb and J Schwartz Shape Overview Tree Use hierarchical representation to capture shape information at multiple levels of resolution 0 Capture global properties by compositing adjacent curve matches Shape Local vs Coarse Features a b Images from Felzenszwalb and Schwartz Tree Shape The ShapeTree Tree Images from Felzenszwalb and Schwartz Shape Bookstein Coordinates Tree 0 Encode the relative positions of 3 points as a point in the plane 0 A simple way to represent the relative location of a midpoint in the shape tree 0 Given 3 points there exists a unique similarity transformation which maps P1 to 05 0 P2 to 05 0 0 P3 to the Bookstein coordinate Shape Tree Relative Locations B x I l A c 050 050 0 Bookstein coordinates for representing B AC 0 There exists a unique similarity transformation T taking Ato 05 0 Cto050 0 We are interested in TB Slide from Felzenszwalb and Schwartz Shape Deformation model Tree 0 Independently perturb relative locations stored in a shapetree 0 Reconstructed curve is perceptually similar to original 0 Local and global properties are preserved kt IIIII Images from Felzenszwalb and Schwartz Shape Tree Distance Between Curves 0 Given curves A and B 0 Can t compare shapetrees for A and B built separately 0 Fix shapetree for A and look for map from points in A to points in B that doesn t deform the shape tree much 0 Efficient C nm3 DP algorithm where n lAlam IBI Slide from Felzenszwalb and Schwartz Shape Tree Recognition Results Swedish Leaf Dataset 15 species with 75 examples each Nearest Neighbor Classification l Algorithm lShapeTreelInnerDistancelShape Contextl l Score l 9628 l 9413 l 8812 i O l l0 t MPEG7 Dataset Bullseye Score mm Score 8770 8540 l Algorithm l Curve Edit lShape Contextl l Score l 7814 l 7651 i Shape Tree Matching in Cluttered Images 0 Given Mth39e model curve and C the set of curves in the image 0 Use DP to match each curve in C to every subcurve of M 0 Running time is linear on total length of image contours and cubic in the length of the model 0 Stitch partial matchings together to form longer matchings 0 Use compositional rule Shape Compositional Rule Tree If llq r lt T compose Matchab pq and Matchbc rs Matchabpq 1 Matchbcrs W b m Matchacps wl w2 bla7 C 7 Slide from Felzenszwalb and Schwartz Shape Treg Example Detection Contours Detection Images from Felzenszwalb and Schwartz Results Model Images from Felzenszwalb and Schwartz Boundary Fragment OUtline Model 0 Shape Distance and Correspondence 0 Hausdorff Distance 0 Shape Context 0 Inner Distance Hierarchical Approach 0 Hierarchical Matching 0 Machine Learning Approach Emundai y Walngth Mmde A BoundaryFragmentModel for Object Detection 2006 A Opelt A Pinz and A Zisserman Boundary Fragment overVieW Model 0 Object class detection using object boundaries instead of salient image features 0 A learning technique to extract discriminating boundary fragments Use boosting to select discriminative combinations of boundary fragments weak detectors to form a strong detector oundary Fragment Learning Boundary Fragments Model 0 Given 0 A training image set with the object delineated by a bounding box 0 A validation image set labeled with whether the object is absent or present and the object s centroid 0 From the edges of the training images identify fragments that 0 Discriminate objects from the target category from other objects 0 Give a precise estimate of the object centroid mmmmmm Boundary Fragment Example Model Good Boundary Fragment Estimated Centroid Correct Centroid Wages rrum Open at a Estimated Centroid Correct Centroid Wages rrum Open at a Boundary Fragment Weak Detectors Model 0 A weak detector is composed of k typically 2 or 3 boundary fragments 0 Detection should occur when 0 The k fragments match the image edges 0 The centroids concur 0 For positive images the centroid estimate agrees with the true object centroid TWO boundaw Matthin on lhe ed eima e fragments 92537 a g 9 16a 4 J72quot Overlapofcenlmid predic ons C C 739 A similarities of matche Matching ber the edge image 3925b r gt as Q r Images from Opelt et al Boundmy Fragment Strong Detector Modd 0 Given weak detectors h1 0 Using AdaBoost 0 In each round find the weak detector that obtains the best detection results on the current weighting T H I 2 Sign h2 I mm i1 Example Detection and Segmentation All Matched Centroid Voting on Boundary Fragments Subset of Fragments g Original Image Detection and Backprojected Segmentation Maximum Images from Open el al Example Detection and Localization A ZJW W 5 a c fhlg M l w n a W Lja 527 Images from Opell el al Boundary Fragment ReSUItS Model ROC Error Rate Algorithm BFM 12 22 25 2 3 14 26 28 carsrear 050 880 890 2140 310 230 180 980 airplanes 260 630 1110 340 450 1030 1710 560 Detection Error Algorithm BFM 18 carsrear 225 610 Bli aakzing Recognizing Objects in Adversarial Clutter Breaking a Visual CAPTCHA 2003 G Mori and J Malik 331 What is a CAPTCHA Definition Completely Automated Public Turing test to tell Computers and Humans Apart Used to prevent automated SPAM Also to read books Breaking CAPTCHA Applications of CAPTCHAs Preventing blog SPAM Protecting web site registration Protecting email addresses from scrapers Preventing dictionary attacks Online polling Blocking search engines Blocking email SPAM Human Assisted OCR Roughly 60 million CAPTCHAs are solved by humans every day Equivalent to about 150000 hours of work Why not use these CAPTCHAs for hard OCR tasks mewhdmRWIM l l l l l l l l quotw aged pnlkm al sociely were distinguished Imwquot 3333 Why Break a CAPTCHA 0 CAPTCHAs help prevent SPAM 0 They also offer challenges to the Al community 0 A winwin situation 0 If the CAPTCHA is not broken then SPAM is blocked 0 If it is broken then an Al problem has been solved Breaking CAPTCHA Approach 1 0 Detect letters using the Shape Context approach 0 Extended so that the SC includes the dominant tangential direction of the edges in each bin I I 0 Form a directed acyclic graph of the letters to find candidate words 0 Choose the most likely word based on the average deformable match cost of the individual letters rice profit I lwvl Images 39om Mori and Malik Breaking CAPTCHA Approach 2 0 For harder CAPTCHAs matching on letter sized regions is to difficult m ak 0 Match on groups of letters instead Jaiigp ram weer mil mm co 39 1 r0 u 39 Images from Mori and Malik Breaking CAPTCHA Example EZGimpy rice weight rice weigh join sock ijeyv eli join mam jewelr space quots39p39exampe mine canvas Images 39om Mon39 and Malik Example 3 Word CAPTCHA QYQJE meg Tm Men Wm future key have sharp round long sudden apple oven with true sponge Images from Mori and MaJik Discussion Points 0 How can shape matching be made more robust to clutter What applications are not suitable for shape matching Which are 0 How can methods like Shape Context take advantage of available training data 0 How can appearance and shape features be best combined 0 What other hard Al problems can be used as CAPTCHAs The STrucTure of Typed Programming Languages ChapTer 1 conTinued C5386L Programming Languages Dr Greg Lavender DeparTmenT of CompuTer Sciences The UniversiTy of Texas aT AusTin l l El H l C53E6L meoe Th 5mmquot of Typcd Programming Languagcs Chopra 1 com SemanTics of The Core Language The purpose of a welldesigned synTax is To guide The programmer39s understanding of The semanTics leading To correcT programs buT we need more Than JusT inTuiTive undersTanding Core imperaTive programming language locaTions and numerals represenT Themselves expressions represenT inTegers and booleans commands represenT sTaTe TransformaTions DenoTaTional semanTics is one wa To formalize The semanTics of a language whaT is The meaning of each legal synTacTic phrase a denoTaTional semanTics maps wellTyped derivaTion Trees To Their maThemaTical meanings E1 E2comm 31 A14 l l El l l l C53E6L meoe Th Structure of Typed Programming Languages Chapter 1 com iLl Semantic domains amp operations Bool false true not Bool gt Bool notfalse true nottrue false equalbool Bool Bool gt Bool equalbool mn m n Int oo1 0 1oo plus Int Int gt Int plusmn m n equalintInt Int gt Bool equalint mn mn Location loc i gt 0 Store ltn1n2nmgt n in Int 1 lt i lt m m gt0 lookupLocation Store gt Int update Location Int StoregtStore if Bool Store StoregtStore iftrues1s2s1 WM iffalses1s2s2 l l El l l l C53E6L meoe Th Structure of Typed Programming Languages Chapter 1 com iLl Semantics of the Core Language A denotational semantics is a recursive definition that maps welltyped derivation trees to their mathematical functional meanings Bool is a semantic domain with two values true and false two semantic functions in a sugared A calculus not logical negation equalbool boolean equality Int is the set of integers addition and equality functions gint 2 where g is a numeral and 2 is an integer Location is a set of labeled locations lociintloc loci an AM l l El H l C53E6L meoe Th 5mmquot of Typcd Programming Languagcs Chopra 1 com The STore An absTracTion over locaTions and values semanTics for lvalues and rvalues sTore is a linear sTorage vecTor lookup funcTion ookupocj ltn1 n2 nj nmgt n ifj gt m ookupocj ltn1 nmgt 0 updaTe funcTion updateocj n ltn1n2njnmgt ltn1n2nnmgt ifj gt m updateocjltn1nmgt ltn1nmgt The if operaTion selecTs a sTore based on a boolean expression evaluaTion an AM 5 El l l l CSSB6L meoe Th 5mmquot of Typld Programming Languagls Chqnu 1 com Compos iT i onal SemanTics The meaning of a wellTyped program is a recursive equaTion using H for L E we compuTe The meaning of This command using a semanTic equaTion along wiTh a Typing rule The Typing rule indicaTes The composiTional elemenTs of The rhs of The equaTion Lintoc Eintexp L E comm Lintoc Eintexp an A14 9 ELM 1 CSSB6L meoe Th Structure of Typed Programming Languages Chapm 1 com ReferenTial Transparency semanTic definiTions are referenTiallx TransparenT if Two phrases have The same meaning They can be subsTiTuTed for one anoTher plusplus234 plus54 an AM ELM 1 CSSB6L meoe Th Structure of Typed Programming Languages Chapm 1 com SemanT ic equaTions Command LEcomms updateLintloc Eintexpss C1C2oomms C2comm C1oomms if E then C1 else C2 ficomms if Ebooexps ClcommsC2comms whieEdoC o comm s ws where ws if Ebooexps wCcomms s skipcomms s Expression Nint ookupLintocs plusE1intexpsE2intexps not Ebooexps equalboolE1boolexps E2booexps equalintE1intexps E2intexps Location Ioc intloc Ioc Numeral nint n an AM El l l l CSSB6L meoe Th 5mmquot of Typld Programming Languagls Chqnu 1 com Semantics of Expressions Semantics of an expression is dependent on the store given the initial storage vector lt345gt example 1 loc1intexplt345gt lookuploc1intloclt345gt 3 example 2 loc11intexplt345gt plusloc1intloclt345gt 1intexplt345gt plus31int plus31 4 31 A14 El l l l CSSB6L meoe Th 5mmquot of Typld Programming Languagls Chqnu 1 com Semantics of Commands Semantics of a command is dependent on the store a command changes the stare into a new one example 39 locg loc1 1commlt345gt updateloc3intlocloc11intexplt345gtlt34l5gt updateloc34lt34l5gt 344 31 A14 l l El l l l C53E6L meoe Th Stmcmn of Typcd Programming Languagcs Chapul 1 com Command ComposiTion meaning of command sequencing is funcTion composmon of The corresponding denoTaTIons C1C2comms CZcommC1comms example loc3 loc11 if loc30 Then loc21 else skipcommlt345gt if loc3 0 Then loc2 1 else skipcomm loc3 loc11commlt345gt if loc3 0 Then loc2 1 else skipcommlt344gt ifloc30boolexplt344gtloc21commlt344gt skipcommlt344gt if false loc2 1commlt344gt skipcommlt344gt skipcommlt344gt lt344gt 3mm 11 El l l l CSSB6L meoe Th 5mmquot of Typld Programming Languagls Chqnu 1 com iLl The While loop iTeraTion and recursion presenT a challenge in semanTics whaT is required is a way To represenT a self referenTial objecT in The semanTic domain one way To do This is To consider a special semanTic funcTion ThaT incremenTally approximaTes or converges To The final value of The iTeraTionrecursion eg we can Think of a recursive facTorial program as denoTing a facTorial funcTion ThaT on each recursion approaches The limiT of The funcTion in a maThemaTical sense by evaluaTing iTself repeaTedly unTil some TerminaTing condiTion 3mm 12 l l El H l CSSB6L meoe Th 5mmquot of Typld Programming Languagls Chqnu 1 com iLl The w funcTIon This funcTion is acTually a family of funcTions ThaT approximaTe an answer by unfolding like unrolling a loop w0s boTTom 39 W1S if Eb 6XPS WoCC mmSS w2s if Eboolexps w1Ccomms s wi1s if Eboolexps wiCcommss for all sTore vecTors s and s39 ws 539 iff There is some k gt0 suchT ThaT wks s39 wks 539 implies wJs s39 for all j gt k Le a TerminaTion condiTion an AM l l El H l CSSB6L meoe Th 5mmquot of Typld Programming Languagls Chqnu 1 com iLl While semanTIcs Example while loc1 0 do loc1 loc11commlt00gt wlt00gt if locleboolexpltOOgtwloc1loc11 commlt00gt lt00gt if True woc1oc11commltOO lt00gt wloc1oc11commltOOgt wlt10gt if loc120boolegtltplt10gt wloc1loc11commlt10gt lt10gt lt10gt an oquuT sTore is produced by W in a finiTe number of k unfoldings unTiI wk produces The same oquuT sTore for an inpuT sTore and Then The loop TerminaTes ie w reaches a fixed poinT where wlt10gt lt10gt refer back To The fixed poinT version of Kleene39s recursion Theorem an AM 31 A14 CSSB6L meoe Th 5mmquot of Typld Programming Languagls Chqnu 1 com OperaTional semanTics semanTics of operaTional sTeps required To evaluaTe a program operaTional semanTics are helpful in consTrucTing an inTerpreTer for a language for example we could implemenT all of The semanTic funcTions as procedures in an inTerpreTer augmenTed wiTh an environmenT for looking up and and updaTing variables locaTions wiTh sTorage values in RA The goal Then is To reduce a program To some value iTs normal form by a sTepbysTep evaluaTion of each synTacTic phrase according To The Type rules and The semanTic equaTions C53E6L meoe Th 5mmquot of Typcd Programming Languagcs Chopra 1 com An inTerpreTer FirsT read aprogram and do lexical analysis and parsmg InTo an InTernal form eg an absTracT synTax Tree Have an eval procedure ThaT can reduce an valid expressmn In The language To ITs norma form for each expression The eval procedure applies The semanTic funcTion for ThaT ex ression using The currenT sTaTe of The inTerpre er as The sTore PrinT ouT The resulT of The expression RepeaT for The nexT expression This is called a ReadEvalPrinT Loop InTerpreTer 31 A14 El l l l CSSB6L meoe Th 5mmquot of Typld Programming Languagls chap 1 com CompuTaTion sTeps A compuTaTion is a sequence of sTeps p0 gt p1 gt gt pn39n gt O we say pO gt pquot in zero or more sTeps if pquot is a value TerminaTe The compuTaTion for Bool True and false are values for InT numerals are values for LocaTion every loci is a value for STore every ni in a vecTor is a value so a vecTor is a value recall ThaT expressions and commands produce new sTores for The core imperaTive language a program is some phrase Ccomms0 sTarTing wiTh The iniTial sTore s0 3mm 11 El l l l CSSB6L meoe Th 5mmquot of Typld Programming Languagls chap 1 com Desired OperaTional ProperTies sub iecT reducTion if p has an underlying Type 17 and p gt p39 Then p39 has Type quotC soundness if p has The underlying maThemaTical meaning m and p gt p39 Then p39 has The same meaning m sTrong Typing if p is wellTyped and p gt p39 Then p39 has no operaToroperand Type errors compuTaTional adequacy The meaning m of a program p is a proper meaning iff There is a value n such ThaT p gt v and v has meaning m 3mm 1

### 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

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### 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.