KNOWLEDGE REP MEBI 550
Popular in Course
verified elite notetaker
Popular in Medical Education And Biomedical Informatics
This 40 page Class Notes was uploaded by Marguerite Quigley on Wednesday September 9, 2015. The Class Notes belongs to MEBI 550 at University of Washington taught by Ira Kalet in Fall. Since its upload, it has received 26 views. For similar materials see /class/192263/mebi-550-university-of-washington in Medical Education And Biomedical Informatics at University of Washington.
Reviews for KNOWLEDGE REP
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/09/15
Data abstraction example patient records A patient record could be structured as a list consisting of a name address telephone numbers date of birth diagnosis primary physician simone jones 1234 boylston street home 206234 5678 seattle wa 98102 work 425 432 8765 pruritis of the palm angela a aardvark md 10 11 1978 For each item we define an accessor name pt first name first patient pt first name pt family name pt second name pt address pt second pt street address pt first address pt city pt second address pt Accessors can do some work defun phone number pt ampoptional type let numbers third pt second if type assoc type numbers first numbers defun birth date pt fourth pt defun print nice date day month year format nil quotNA NA NAquot day month name month year defun month name m I quotJANH H FEBquot quotMARquot quotAPRquot quotMAYquot quotJUNquot Hquot quotAUGquot quotSEPquot quotOCTquot quotNOVquot quotDECquot l m defun formatted birth date pt let date birth date pt print nice date first date second date third date Constructors hide details also This is a simple constructor defun make patient ampkey name address city state zip home phone work phone birthdate diagnosis physician list name list address city state zip list list home home phone list work work phone birthdate diagnosis physician It would be used as follows setq patient 34 make patient name ira kalet address NN146A UWMC City seattle birthdate 27 4 1944 work phone 206 598 4107 diagnosis delirium instructosis physician i curem md Accessors can be used as lookup functions To search a list of patients patient db by patients family name use the previously defined familyname function find kalet patient db key family name Of course this finds only the first such occurrence Later we will write a patient lookup function that returns all occurrences and selects by first name also Recursion If find were not part of Common Lisp we could write it If thing is in the list junk the function returns it Otherwise it returns nil defun my find thing junk cond null junk nil first junk thing eql thing my find thing rest junk t How could this be improved How could it be generalized defun my find thing junk ampkey test eql key identity null junk nil cond funcall test thing funcall key first junk first junk rest junk t my find thing test test key key Recursion examples The Fibonacci function is Fn Fn 1 Fn 2 defun fibonacci n if or n O n 1 l fibonacci n 1 fibonacci n 2 The following solves the Tower of Hanoi moving n disks from tower a to tower b via tower C defun hanoi n a b C if n 1 move a b progn hanoi n l a C b move a b hanoi n l C b a The move function can just print a message defun move a b format t quotMoving disk from S to NS quot a b A template for recursive functions All recursive functions follow the same general form 1 Check if you are done 2 Handle the base or simple case 3 Recursiver handle the rest defun ltfn namegt argl arg2 cond null arg2 ltsome resultgt lttestgt argl first arg2 ltsimple resultgt t ltrecursive expressiongt Recursive and iterative processes defun my reverse S if s append my reverse rest S list first S defun another reverse S reverse iter s nil defun reverse iter S accum if null S accum reverse iter rest S cons first S accum The Factorial Function l The factorial function computes nl ie the product of the first n integers Here is how it looks in Common Lisp defun factorial n quotfor any integer n returns nquot if n0 1 n factorial l n and here is a tailrecursive version defun factorial n quottail recursive returns nquot fact iter n 1 defun fact iter n accum if n O accum fact iter l n n accum The Factorial Function in C In C you need a main to use it interactively include ltStdiohgt main int n scanfquotdquot ampn printfquotn dnquot factorialn for any small integer n returns n long factorialint n int i p p l for i1 ilt n i ppi return p The Factorial Function a java version Here is how the factorial function would look in java taken from Java in a Nutshell by David Flanagan with end of line comments omitted This program computes factorial of a number public class Factorial public Static void mainString args int input IntegerparseIntargsO double result factorialinput Systemoutprintlnresult public Static double factorialint x if xlt 0 return 00 double fact 10 whilex gt l fact fact x xx 1 return fact Transforming procedures Often it is useful to have a function that takes a list and applies a transfor mation to each element of a list Such functions all take the same shape defun lttransform fngt s if null s nil cons lttransform eltgt first 5 lttransform fngt rest S In place of lttransform fngt put the name of yourfunction and for lttransform eltgt put the name of the function that works on a single element Transforming procedure for DNA replication An example of a procedure to map a DNA strand represented by a list of symbols repre senting bases A T G C defun dna copy input if null input nil cons dna comp first input dna copy rest input The dna comp function just changes A to T and G to C and vice versa defun dna comp x cond eql x g c eql x 39c g eql x a t eql x t a t error quotyour dna is screwyquot DNA replication example dna copy takes a single strand and makes a complementary strand by transforming each element and assembling a new list as it goes gt dna copy g g c a t t t a a g a c c CCGTAAATTCTGG We can get the same effect with the mapcar function gt mapcar dna comp g g c a t t t a a g a c c CCGTAAATTCTGG Functions as arguments funcall and apply call other functions This allows functions to be passed as argu ments to other functions funcall can only be used with functions that have a known fixed number of arguments When the number of arguments may vary you can use apply It works on a list of arguments gt funcall 3 4 5 12 gt apply 3 4 5 12 gt setf list of lists a b c foo bar one two three A B C FOO BAR ONE TWO THREE gt apply append list of lists A B C FOO BAR ONE TWO THREE mapcar can be faked If mapcar were not part of Common Lisp you could write your own version defun fake mapcar fn s if null s nil cons funcall fn first 5 fake mapcar fn rest s As you find that other cliches are needed but not built in you should define them and then use your defined function just as if it were there to begin with More examples of cliches Sometimes you would like to apply a predicate like and or or to another predicate func tion on a list of items eg to to check if every element of a list is a number but apply and mapcar numberp my list won t work because and is a macro not a function Instead you could just use recursion to handle this defun check if all numbers list if null list t and numberp first list Check if all numbers rest list This pattern occurs so often that several functions were added to Common Lisp every some notany and notevery Just as with mapcar you could define your own version if it were not included defun my every fn list if null list t and funcall fn first list my every fn rest list More on anonymous functions Anywhere that a named function is needed an anonymous function can be used Instead of gt mapcar dna comp g g C a t t t a a g a C C CCGTAAATTCTGG we can get the same effect with gt mapcar lambda x cond eql x g C eql x c g eql x a t eql x t a t error quotyour dna is screwyquot g g c a t t t a a g a c C CCGTAAATTCTGG Using local state Anonymous functions are just right when you want the function to use something from the local environment The find patient function matches for both first and last name from the patient database defun find patient first name family name patient list first remove if not lambda x and eql first name first name x eql family name family name x patient list More on using local state The mapcar function maps a function over a list of data Imagine a function mapfun that does just the opposite mapping a piece of data over a list of functions gt mapfun a b C list length reverse first rest listp 3 CBA A BC T It can be defined as follows using mapcar defun mapfun item fns mapcar lambda x funcall x item fns Here too the anonymous function is essential since it uses local state Local state an example from Prism In the Prism pen plotter output code graphic primitives are sorted by color before drawing to minimize the time spent on changing the pens copy list since sort is destructive setf foreground sort copy list foreground lambda cl c2 lt pen number cl plt pen number c2 plt key color mapcar lambda x draw x plt foreground Functions really as data defun bank account balance quotreturns a bank account function Starting the account with the given balancequot lambda action amount case action deposit setf balance balance amount withdraw setf balance balance amount BANK ACCOUNT gt setf my account bank account 50000 ltCLOSURE 5463733gt gt setf your account bank account 80000 ltCLOSURE 5463733gt gt funcall my account deposit 22000 7200 gt funcall your account deposit 60000 14000 gt funcall my account withdraw 7500 6450 gt funcall your account withdraw 7500 13250 Caching results buys huge efficiency Any function can be memoized or turned into a version that caches results for later lookup defun memo fn quotReturns a memoized version of fnquot let table make haSh table lambda x multiple value bind val found gethash x table if found val setf gethash x table funcall fn x and replace the symbol s function definition with the memoized version defun memoize fn name quotReplaces global definition of fn name with a memoized versionquot setf symbol function fn name memo symbol function fn name Iteration While recursion can solve any problem that needs repetition it is often more convenient to have direct iteration constructs Several are built into Common Lisp simple iteration over a list dolist simple iteration some fixed number of times with a counting variable dot imes general iteration with stepping of multiple local variables do indefinite iteration loop simple sequencing progn and progl Short forms dolist The dolist macro iterates over lists Here s a function to print all the citations for a given author from a simple bibliographic database defun print cites author biblist format t quotBib entries for author A quot author dolist entry biblist format t quotJournal A Title A quot second entry third entry Short forms dotimes The dotimes macro repeats a computation for some number of times stepping a local variable from O to one less than the count defun print cubes n format t quotThe first A cubes quot n format t quot N N3 quot dotimes i n format t quot3D 6D quot 1 i expt 1 i 3 The do macro The do macro provides a very flexible and powerful iteration form defun factorial n do j n j 1 fact 1 j fact j 0 fact no body The do macro A more complex example adapted from Prism do collim info collim info np COlumn len 1 length edge list collim info width 2 np rdt base height round np ht 2 np off column len leaf pairs leaf pair map collim info rest leaf pairs x1 6 np rdt base 4 np off xr 8 np rdt base 5 np off np off y height 390 1 i i column len Llt1 IIIl push Sl make textline width height left leaf tlns np The loop macro repeats indefinitely An example of input from a sonic digitizer defun digitize contour pts update mag x0 y0 let xcm ycm status loop multiple value setq status xcm ycm digitize point case status point push list xcm x0 mag ycm yO mag pts delete last setf pts rest pts delete all setf pts nil funcall update pts if eq status done return pts The program feature progn progn returns the value of the last expression evaluated though often no value is needed if new progn unless setf unless setf unless setf unless setf setf unless setf progn poly nearly equal x old x new x old x new poly nearly equal y old y new y old y new poly nearly equal 2 old 2 new 2 old 2 new string name old name new name old name new sl label button old name old eq display color old display color new display color old display color new coll delete element old point coll slzdelete button rest assoc old pt alist pt pan scr Another sequencer progl progl returns the value of the rst expression evaluated The remaining expressions are evaluated for additional side effects if polyznearly equal it 2 pt epsilon progl make point quotquot x x pt y y pt 2 z esll id mark id pe esll we want the new point but we increment the counter after creating it incf mark id pe esll More on setf setf can assign a value to a symbol gt setf foo 6 6 gt foo 6 For this setq is more efficient But setf can do much more It can assign a value to a place gt setq foo a very short list A VERY SHORT LIST gt setf third foo long LONG gt foo A VERY LONG LIST This is a destructive operation the list is changed and therefore the value of foo is changed indirecty Valid place names for use with setf first aref svref rest nth fill pointer second elt symbol value third get symbol function fourth gethash documentation andsoomtmtotenthaswe ascmnMnmkmsoffirstandrestcarand cdrand w rdmhmsupUJ mrofmwxmnmhm mlofa0rd kecaddror cddadr Arrays In Common Lisp the array data type provides efficiency and clarity when dealing with regular arrays of data A medical image is a good example of an array Arrays usually have fixed dimensions specified by a list of dimensions make array creates an array object gt setf image 6 make array 512 512 initial element 0 2AO O O O J Array access is done with aref The aref function is the accessor for array elements gt aref image 6 234 167 1079 and setf works with aref to update array entries gt setf aref image 6 234 167 334 334 gt aref image 6 234 167 334 Arrays can provide efficiency setq foo make array 512 512 dotimes i 512 dotimes j 512 setf aref foo i j 00 dotimes i 512 dotimes j 512 if aref foo i j 00 setf aref foo i j list ira i j setf aref foo j i foo An array element can be any lisp object defvar pdp cells make array 15 9 initial contents button quotDelete Panelquot nil button quotComputequot nil nil button type momentary nil nil label quotBeamsquot nil nil nil nil nil nil left arrow nil nil nil fg color slzred label quotquot label quotquot label quotquot label quotquot right arrow nil nil nil fg color slred the monitor units row label quotPointsquot nil button quotAll fracquot nil nil button type momentary A AAA AAAAM label quotMUquot number nil 00 100000 number nil 00 100000 number nil 00 100000 number nil 00 100000 nil zup arrow nil nil nil fg color slzred nil label quotDosequot nil nil nil nil nil nil ten rows of point doses I I zlabel quotquot nil number nil 00 100000 nil number nil 00 100000 number nil 00 100000 number nil 00 100000 number nil 00 100000 nil Array dimensions can be determined at runtime To find out the dimensions of an array object there are two related func tions array dimension gives a specified dimension gt array dimension image 6 O 512 gt array dimension image 6 l 512 array dimensions returns a list of all the dimensions of the array gt array dimensions image 6 512 512 But setf can not be used with either of these functions Vectors One dimensional arrays are called vectors The vector function makes a vector with its arguments as initial contents gt vector foo 5 6 ira FOO 5 6 IRA For vectors there is a faster accessor function svref gt setf test vector foo 5 6 ira FOO 5 6 IRA gt svref test 3 IRA An image processing example defun map image map image ampoptional result quotmap image map image ampoptional result returns an array of pixels from image by composing image array with the gray map If the result array is provided it is reused otherwise a new array is createdquot simple array clxpixel 1 map simple array clxpixel 2 result simple array unsigned byte l6 2 image declare type type type let x dim array dimension image 1 y dim array dimension image 0 temparray or result make array list y dim x dim element type case image bits per pixel 8 unsigned byte 8 l6 unsigned byte 16 32 unsigned byte 32 declare type fixnum x dim y dim dotimes j y dim declare type fixnum j dotimes i x dim declare type fixnum i setf aref temparray j i aref map aref image j i temparray
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'