Programming Languages CS 652
Popular in Course
Popular in ComputerScienence
verified elite notetaker
This 24 page Class Notes was uploaded by Michele Herzog on Thursday October 29, 2015. The Class Notes belongs to CS 652 at University of San Francisco taught by Staff in Fall. Since its upload, it has received 9 views. For similar materials see /class/231251/cs-652-university-of-san-francisco in ComputerScienence at University of San Francisco.
Reviews for Programming Languages
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/29/15
Intro Lisp Notes 1 Touretzky book available online there s a link to it on the course web page la web page resources 2 History Originally developed in the late 50s by John McCarthy Equally capable of numeric computation and symbolic computation Primarily adopted as an Al language Also used in AutoCAD Visio Emacs Yahoo Store etc ANSI standard developed in 1994 served to reunite different implemen tations 3 Implementations clisp cmucl allegro Using lisp With emacs 4 Basics of usage starting the interpreter 5 Functional programming a function maps a set of inputs to an output No side effects Can be treated as a black box Examples sqrt abs 6 Predicates A predicate is a special type of function Predicates map from inputs to true or false They are used to test conditions types equality etc Convention end With 7p7 eg numberp symbolp consp evenp oddp equal Not maps nonnil to nil and nil to t 7 data types 0 Numbers integers oating point numbers note on precision in lisp ratios fractions Symbols named after English words Any combination of letters and numbers Serve to represent some nonnumeric value t and nil special symbols quote M quotL a 3 Par Regular Expressions n r39vy39 ChrlS Brooks Department of Computer Sclence Unlverslty of San Franclsco 61 String methods String module has find count replace and split this works when you know the exact string you re looking for wkward when you have multiple occurrences or many different matches Doesn t deal well with case 1 63 Example says to only match occurrences at the end of a line What about cases where someone leaves off the street type Or cases where there s an apartment number after ROAD 1 1 1 BROAD i Still matches 1 1 1 BROAD ROAD Apt 3 Doesn t matc a re sub 39 bROADb39 RD s indicates word boundary needs to be escaped 60 Regular Expressions Often when you re working with strings or files you need to find replace or ignore strings or lines that match some sort of pattern Find lines containing img src Find strings that begin with a number Find strings that don t contain a number Replace all instances of strings beginning with CS with USF CS How can we do this in an automated way 62 Example Replace all instances of ROAD with RD sreplace ROAD RD What about 1 1 1 BROAD ROAD s 4 s 4replace ROAD RD Better but brittle and hard to read Need to know that ROAD resub ROAD s is the last four chars 64 Escaping in Strings front of t Otherwise Python thinks it s a control character for the following character eg t When you need to work with lots of backslashes you can use a raw string r bROADb 39 he character needs to be escaped by putting another in s2 No metacharacters are evaluated 65 Finding Sequences of Characters Find addresses that begin with 13 4s 4 Main St 44 Mulberry Lane 423 First St etc pat quot44 7 indicates beginning of the line 7 indicates 0 or 1 occurrence of the previous character rematch returns a Match object if there is a match None otherwise navammmoumvuvschm imamms WWW 67 An easier way to express repetition We can also use the nm syntax to match repetition 413 matches 13 4s at the beginning of the string We can rewrite the previous expression as p 413012 2013 navammmoumvuvschm imamms mmpr 69 Things to match on b word boundary d any digit D anything that s not a digit same as 09 w equivalent to AZa209 s whitespace S nonwhitespace mmmmpmsumeumums mmpr 66 More complex sequences Now let s suppose we need to find sequences that begin with 13 5s and can end with 01 02 or 2 followed by 13 zeros Start with our previous pattern 44 24 ending with 01 is 01 with 02 is 02 444o102 will match 401 44402 4402 etc Add 2007070 to parens 2147mm 02 20000 navamumvcmvlmschmrumwwmyn mmrm 68 Things to match on e matches any character xy match a range or set of characters abc will match a or b or c AZ will match ABC Z Can also tag the complement of a set abc will match any character except abor c mmnmmwscm emum mwp mm 6 10 Matching multiple occurrences 7 0 or 1 occurrences one or more occurrence quot 0 or more occurrences mn m to n occurrences m exactly m occurrences 7 after another multipleoccurrence matcher nongreedy eg ltgt mmnmmwscm emum mwp am ALA L 1 1 Programming Language Paradigms Performance and Profiling Chris Brooks Department of Computer Science University of San Francisco Department or Computer Science 7 University or San Francisco 7 p 17 100 Efficiency Issues o A danger in using very highlevel languages like Python is developing code that does not run efficiently o For example 5 Excessive copying and allocation of strings A Extra function calls A Not taking advantage of builtin optimized features 6 Let s look at some techniques for finding and fixing inefficient code Department of Computer Science University of San Francisco p2739 101 The development process e We can break the development process into stages a Develop a prototype using good design principles including modularity and abstraction A Instrument the prototype to locate performance bottlenecks a Isolate and replace bottlenecks testing for correctness as you go Department of Computer Science University of San Francisco p3739 102 Measuring efficiency 23 When we say efficiency usually we mean running time a We can also talk about space A Excessive space usage can lead to swapping poor performance a May make your program unusable on older machines 6 We can also talk about cost of development A From a business POV this is the real measure of efficiency how much do we have to pay to get a working product a Coding manhours are very expensive A Designarchitecture manhours are even more expensive This makes tools and languages that can do rapid prototyping very useful 103 Techniques for efficient programs Cache the results of previous computations when you can Use the simplest option you can Build strings as a list and use join at the end Test for identity ranther than equality Use dictionaries for searching union etc Use builtin sort and comparison function when you can map and filter are faster than for Use list comprehensions over map and filter if there are conditions or helper functions are needed Use reduce rather than an accumulator Department of Computer Science University of San Francisco p5739 104 Techniques for efficient programs Cache the results of previous computations when you can Bad def fib n 2 if n 1 or n 2 return 1 else return fibn l fib n 2 Department of Computer Science University of San Francisco p6739 105 Techniques for efficient programs Cache the results of previous computations when you can Good def fib2n cacheNone set up the cache initially if cache is None cache base case if n 1 or n 2 cachen 1 return 1 else if cache haskeyn return cachen else cachen fib2n l cache fib2n 2 return cachen cache Department of Computer Science University of San Francisco p7739 106 Techniques for efficient programs o Use the simplest option you can A If you need to find out whether a string starts with 8 use startsWith rather than a regular expression A If you need to check whether a string contains a letter use in rather than indexing the string o Don t do unnecessary work Department of Computer Science University of San Francisco p8739 107 Techniques for efficient programs Build strings as a list and use join at the end Bad for str in listofstrings result str Good result joinlistofstrings Join is called on the string that you want to separate items in the list Join is linear time repeated concatenation is quadratic Department of Computer Science University of San Francisco p9739 108 Techniques for efficient programs Test for identity ranther than equality Bad if x 1 None Good if x is not None identity just compares memory locations doesn t need to look at the actual data Department of Computer Science University of San Francisco p10739 109 Techniques for efficient programs Use dictionaries for searching union etc e To find items in common between two lists make one into a dictionary and then look for items from the second list in the dictionary A List lookup is linear time dictionary lookup is constant Department of Computer Science University of San Francisco p11739 1010 Techniques for efficient programs Use builtin sort and comparison function when you can It s often faster to reorder the list so that you can use the builtin compare function For example to sort from largest to smallest Bad ltsortlambda xy x gt y Good ltsort loreverse Sort runs much more slowly with a userprovided algorithm Department of Computer Science University of San Francisco p12739 1011 Techniques for efficient programs map and filter are faster than for a Iteration can be handled by the interpreter more efficiently Bad strings for d in data strings appendstrd Good strings mapstr data Let the interpreter manage looping no need to allocate and bind variables to Python objects Department of Computer Science University of San Francisco p13739 1012 Techniques for efficient programs Use list comprehensions over map and filter or loops if there are conditions or helper functions are needed Function calls in Python are very expensive Bad result for d in data if d gt O resultappendd Better result d for d in data if d gt 0 More work done in the interpreter rather than in Python Department of Computer Science University of San Francisco p14739 1013 Techniques for efficient programs Use reduce rather than an accumulator Same rationale avoid directly manipulating Python objects Bad product l for i in data product i Better from operator import add mul product reducemul data Department of Computer Science University of San Francisco p15739 1014 Profiling Profiling or instrumenting your code is a very useful way to find out where you are spending most of your time Remember Amdahl s Law Optimizing the already fast parts of your code will lead to the slow parts dominating runtime even more you will get diminishing returns to scale or spend your time fixing the parts that run slowly Department of Computer Science University of San Francisco p16739 1015 Profiling a The python profiler is very easy to use import profile profile run foo Department of Computer Science University of San Francisco p17739 1016 Saving a Profile Often you ll want to save a profile to look at later import profile pstats profilerun foo myprofile p pstats Stats myprofile p is an instance of the Stats class Department of Computer Science University of San Francisco p18739 1017 Saving a Profile c Useful methods for Stats include A printstatsn n indicates how many lines A sortstatsfied1 field2 field can be time cumulative calls etc a printcallers who called each of the functions A stripdirs remove beginning path info from display Department of Computer Science University of San Francisco p19739 def testl l I I for i in l 2 def test2 joinstri rangelOOOOO stri for i in rangelOOOOO 1018 Examples Department of Computer Science University of San Francisco p20l 1019 Examples def helperxy return X y def test3 maphelper rangelOOOOO rangelOOOOO def test4 X y for Xy in ziprangelOOOOO rangelOOOOO Department of Computer Science University of San Francisco p21l