/ 3_data-structures.org
3_data-structures.org
1 #+title: Data structures 2 #+author: Michael Raitza 3 #+subtitle: Barkhausen Institut, Dresden 4 #+options: ^:nil 5 #+startup: showall indent 6 #+property: header-args:uxntal :wrap src text :noweb yes 7 8 * Why structure data? (1) 9 10 Fundamental limit to computers (likely to everything) 11 12 *Information can only be produced linearly fast* 13 14 Strongly related to: space complexity of algorithms 15 16 For programming as a means to solve problems as fast as possible, structuring problems is 17 the fundamental purpose of programming and computer design 18 19 * Why structure data? (2) 20 21 *Speed* :: What data to access and what to ignore (i.e., /selection/) 22 23 *Understanding* :: What the data is supposed to mean 24 25 *Intent* :: How data is to be used. When it is (in-)valid 26 27 * Interpreting numbers as other numbers – negative numbers 28 29 Already seen the following number space in hexadecimal notation 30 #+begin_src text 31 0 1 1 2 32 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ -+ 33 0 1 2 3 4 5 6 7 8 9 a b c d e f 0 1 2 3 4 5 6 7 8 9 a b c d e f 0 34 too much, cut off ^ 35 #+end_src 36 37 Computers store numbers in *binary*! How many bits needed? 38 39 As numbers roll over at the end, we can see the scale as a closed ring... 40 41 ... and break the ring at any point to make it a scale 42 #+begin_src text 43 1 1 0 44 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 45 0 1 2 3 4 5 6 7 8 9 a b c d e f 0 1 2 3 4 5 6 7 8 9 a b c d e f 46 ^ stitched together 47 #+end_src 48 49 * Signed numbers 50 51 And now, we reinterpret some numbers 52 #+begin_src text 53 1 1 0 54 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 55 0 1 2 3 4 5 6 7 8 9 a b c d e f 0 1 2 3 4 5 6 7 8 9 a b c d e f 56 . . . . . . . . . . . . . 57 -16 -14 -12 -10 -9 -8 -7 -6 -5 -4 -3 -2 -1 (decimal) 58 #+end_src 59 60 Number system called *2's complement* 61 62 *Observations* 63 - numbers =00₁₆= – =0f₁₆= are positive 64 - numbers =10₁₆= – =1f₁₆= are negative → use leading =1= as number sign 65 - single 0 → =00₁₆= 66 - (almost) equal distribution between positive and negative numbers 67 - all hexadecimal numbers in same order as before 68 * 2's complement - subtraction 69 70 Meaning of subtraction on number scale for three numbers =x=, =y= and =z= 71 #+begin_src text 72 1 1 0 73 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 74 0 1 2 3 4 5 6 7 8 9 a b c d e f 0 1 2 3 4 5 6 7 8 9 a b c d e f 75 z x 76 |<- y --| 77 #+end_src 78 79 Two interpretations: 80 1) distance =y= between two numbers =x= and =z= on number scale 81 2) moves an (imagined) needle from =x= to =z= by the amount of =y= 82 83 If =x= is right of =z=, =y= is ...? → subtraction works from ... to ... 84 85 → src_uxntal{ADD SUB} work on signed and unsigned numbers alike 86 87 * 2's complement – multiplication 88 89 90 #+begin_src text 91 1 1 0 92 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 93 0 1 2 3 4 5 6 7 8 9 a b c d e f 0 1 2 3 4 5 6 7 8 9 a b c d e f 94 . . . . . . . . . . . . . 95 -16 -14 -12 -10 -9 -8 -7 -6 -5 -4 -3 -2 -1 (decimal) 96 #+end_src 97 98 Example: =-6 * -2 = 12= → =??₁₆ * ??₁₆ = ??₁₆= 99 100 *Try this now!* 101 102 #+begin_src uxntal :run bin 103 #.. ( x ) 104 #.. ( y ) 105 MUL ( correct value to our number space and print ) #1f AND #18 DEO 106 #+end_src 107 108 src_uxntal{MUL} works as well 109 110 * 2's complement – division 111 112 113 #+begin_src text 114 1 1 0 115 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 116 0 1 2 3 4 5 6 7 8 9 a b c d e f 0 1 2 3 4 5 6 7 8 9 a b c d e f 117 . . . . . . . . . . . . . 118 -16 -14 -12 -10 -9 -8 -7 -6 -5 -4 -3 -2 -1 (decimal) 119 #+end_src 120 121 Example: =-4 / -2 = 2= → =??₁₆ * ??₁₆ = ??₁₆= 122 123 *Try this now!* 124 125 #+begin_src uxntal :run bin 126 #1c 127 #1e 128 DIV #18 DEO 129 #+end_src 130 131 src_uxntal{DIV} needs correction! 132 133 * 2's complement – absolute value 134 135 136 #+begin_src text 137 1 1 0 138 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 139 0 1 2 3 4 5 6 7 8 9 a b c d e f 0 1 2 3 4 5 6 7 8 9 a b c d e f 140 . . . . . . . . . . . . . 141 -16 -14 -12 -10 -9 -8 -7 -6 -5 -4 -3 -2 -1 (decimal) 142 #+end_src 143 144 What is the absolute value of =-5₁₀= on the number scale? 145 146 #+begin_src uxntal 147 #1b ( extxract absolute value ) #18 DEO 148 #+end_src 149 150 * Interpreting numbers as letters 151 152 After numbers, most-used data structure (certainly most visible 🙂) 153 154 Letters and other characters are *encoded* as numbers and *decoded* to display a 155 representation 156 157 ASCII :: American Standard Code for Information Interchange (now part of UTF-8) 158 128 symbols (*How many bits?*) 159 160 UTF-8 :: Unicode Transformation Format 8-bits 161 ≈4 Billion possible symbols (≈2 Mio. in use) 162 163 ~M-x straight-use-package~ then enter =ascii-table= 164 ~M-x ascii-table~ 165 166 *Try this now!* 167 168 * Exercise – strings 169 170 Implement a program that asks the user for a number between 0 and 255. 171 172 Reject input that is not a number or larger than 255. 173 174 (Advanced) Accept input between -128 and 127. 175 176 Time: *30 minutes* 177 178 *Hint* 179 Use the ASCII table to find out how to convert digits from an ASCII string to a byte. 180 181 #+begin_src uxntal 182 ( code ) 183 #+end_src 184 185 * Arrays 186 187 Contiguously arranged sequence of identically shaped cells (or fields) 188 189 #+begin_src text 190 address x x+1 x+2 x+n-3 x+n-1 191 +----+----+----+ +----+----+----+ 192 content | | | | ··· | | | | 193 +----+----+----+ +----+----+----+ 194 ^ head cell 195 #+end_src 196 197 - Length =n= usually *implicitly* known 198 - Head cell =x= identifies the whole array 199 - Each cell has a fixed (and equal) size (№ of bytes) 200 201 ** Examples 202 Random Access Memory (our main memory) is an array of bytes 203 204 #+begin_src uxntal :run interactive 205 |020 @array/size 206 |040 @array/head $&size ( reserve &size bytes of memory ) 207 208 [ .array/head ] ( access the head, the 1st cell ) 209 [ #01 .array/head ADD ] ( access the 2nd cell ) 210 #+end_src 211 212 * Excursion: Loops 213 214 Loops: central fundamental pattern of computing 215 216 Even languages without loops /execute/ their programs as loops 217 218 Two fundamental loop types: 219 220 1) executing loop *for* a known number of times (/bounded loop/) 221 222 2) executing loop *while* a condition holds (/unbounded loop/) 223 224 Revisit [[file:2_computers.org::#for-loops][dotimes-up/-down loops]] for bounded loops 225 Revisit [[file:2_computers.org::#while-loops][Different types of word calls]] for unbounded loops 226 227 Time: *5 minutes* 228 229 *Try this now!* 230 231 *Discussion* 232 233 * Exercise – arrays 234 235 Implement an array and fill it with random numbers (bytes) 236 (use src_uxntal{rnd} from =<<lib.org:lib()>>=) 237 238 Ask the user for a number and a position and *insert* the new number in the array at the 239 position 240 241 Move all elements at or behind the position one position further (drop the last element) 242 243 Do the same for an array with shorts (two-byte numbers) 244 245 Time: *60 minutes* 246 247 *Hints* 248 1) Make a list of algorithm steps 249 2) Separate your code into many small functions each for a particular task 250 - user interaction 251 - array generation 252 - array mutation 253 #+begin_src uxntal 254 ( code ) 255 #+end_src