DAVID J. MALAN: Detta är CS50 och detta är början på veckan fyra. Och pojke, är Volkswagen i problem allt på grund av programvara. Låt oss ta en titt. [VIDEOAVSPELNING] -Cars, De smartaste tecken i Fast and Furious filmer. Denna vecka tyska automaker Volkswagen befann sig i mitten av en skandal potentiellt kriminella proportioner. 

-Volkswagen Är stärkande för miljarder i böter, eventuella åtal för sina chefer, som företaget apologizes för riggning 11 miljoner bilar hjälpa det slog utsläppsproven. 

-Vissa Dieslar var utformad med avancerad programvara att använda information, inklusive positionen av styrningen och fordonet hastighet för att bestämma bilen var genomgår tester utsläpp. Under denna omständighet, motorn skulle minska giftiga utsläpp. Men bilen var riggad att kringgå att när den körs. Utsläppen ökade 10 till 40 gånger högre än acceptabla EPA nivåer. 

[END SPELA] 

DAVID J. MALAN: Så låt oss ta en titt på denna och se exakt hur detta skulle kunna genomföras och hur detta skulle kunna påverka så många bilar som detta. Så i min hand här är pressen släpp som utfärdades av EPA-- Miljö Protection Agency som är den amerikanska tillsynsmyndighet som hanterar miljöfrågor, och sedan själva rättsligt meddelande som var skicka till Volkswagen bara några dagar sedan. 

Så EPA skriver och beskriver nu offentligt, en sofistikerad programvara algoritmen på vissa Volkswagen fordon upptäcker när bilen genomgår testning officiella utsläpps och vänder hela utsläpp kontrollerar på endast under testet. Effektiviteten av dessa fordon föroreningar kontrollutsläppsenheter är kraftigt minskas under all normal körning situationer. Detta resulterar i bilar som uppfyller standarder i laboratoriet eller provning station, men under normal drift avger kväve oxides-- eller NOx-- vid upp till 40 gånger standarden. Den egenproducerad programvara Volkswagen är ett citat unquote, manipulationsanordning, enligt definitionen i Clean Air Act i USA. 

De går med att säga att EPA och en annan byrå avslöjade manipulationsanordning programvaran efter oberoende analys av forskare vid West Virginia University. NOx föroreningar bidrar till kvävedioxid, marknära ozon, och fina partiklar. Exponering för dessa föroreningar har kopplats med ett brett spektrum av allvarliga hälsoeffekter, inklusive ökad astma attacker och andra luftvägs sjukdomar som kan vara tillräckligt allvarliga att skicka människor till sjukhuset. Exponering för ozon och partiklar har också förknippats med tidig dödsfall på grund av andningsrelaterad eller kardiovaskulär relaterade effekter. Barn, äldre, personer med tidigare existerande respiratorisk sjukdom är särskilt utsatta för hälsoeffekter av dessa föroreningar. 

Det räcker det vill säga, det är ganska allvarligt. Och låt oss gå vidare för att läsa bara en utdrag och sedan tar vi en titt på de underliggande implikationer av detta i samband med en bil. Specifikt Volkswagen tillverkat och monterat programvara i den s.k. elektronisk styrning module-- eller ECM-- av dessa fordon som avkända när fordonet testas för överensstämmelse med normer EPA utsläpps. Baserat på olika ingångar inklusive positionen av ratten, fordon hastighet, varaktighet av motorns drift och barometertryck, dessa ingångar exakt spårade parametrar av den federala testförfarandet används för utsläppsprovning för EPA certifiering ändamål. 

Under EPA: s utsläppsprovet, fordonets ECM programvara sprang programvara som producerade resultat kompatibla utsläpp. Vid alla andra tider, fordonets ECM programvara körde en separat väg kalibrering som minskade effektiviteten av övergripande avgasreningssystemet, specifikt selektiv katalytisk minskning av mager-NOx trap-- som vi får se om ett ögonblick. Som ett resultat, utsläpp av NOx ökas med en faktor av 10 till 40 gånger ovanför EPA kompatibla nivåer beroende på vilken typ av arbetscykeln. 

Så vad detta egentligen innebär, och källkoden till programmet körs på Volkswagens har inte ännu inte offentliggjorts, är att, på ett effektivt sätt, detta motsvarigheten är någonstans där inne Volkswagen kod. Om du håller på att testas, och om bilen detekterar vissa miljöfaktorer liknande ratten läge eller rörelse eller avsaknaden av bilen eller ett antal andra faktorer som för närvarande är en hypotes att vara en del av denna formel, de helt enkelt slå på kontrollerar hela utsläpp. Med andra ord, de börjar avger mindre av föroreningar. 

Else, i varje annan situation när det inte upptäcks vara i laboratoriet, de gör bara inte. Och så du kan förenkla detta i mer betong pseudokod med något så här. Om hjulen vänder men ratten är inte suggestiva att bilen är på vissa typ av roterande cylinder men i något slags lagret som testas, sedan beter sig som den EPA skulle vilja att ni. Annars inte. Så låt oss ta en titt på en kort video som tar en titt på vad konsekvenserna är av detta faktiskt mekaniskt. 

[VIDEOAVSPELNING] 

-Sista Fredag ​​EPA meddelade att vissa Volkswagen Audi mellan 2009 och i år använde en s.k. manipulationsanordning att komma runt lagar utsläpps utformade för att hålla luften ren. Men vad betyder det exakt? 

Tja, moderna bilar har dussintals av datorer inuti dem. Och några av dessa datorer hjälpa till att samordna de funktioner av motorn för optimal prestanda samtidigt se att det inte finns alltför mycket skräp kommer ut ur avgasröret. De har faktiskt arbetat detta sätt under flera decennier nu. I grund och botten, varje del av en modern bils motor har en sensor eller styrenhet på den, och dessa datorer läser i uppgifter tusentals gånger per sekund gör justeringar som förhållandet mellan bränsle och luft som kommer in i cylindrarna. 

Dessa fusk Volkswagen och Audi-modeller är dieslar, och dieselmotorer har ett mer verkligen viktigt dator kontrollerade parametrar, som är mängden oförbränt bränsle kommer in i avgaserna. Nu låter illa. Låter inte som du vill oförbränt bränsle som går in i avgaserna. Men i fallet med en diesel, har du något kallas en NOx-fälla som är en enhet som absorberar och fällor för kväveoxider som är föroreningar som skulle annars gå ut i atmosfären. Och effekten av den NOx-fällan är förstärkt med oförbränt bränsle. Så en manipulationsanordning är ett speciellt program inuti dessa datorer som kan göra det ser ut bilen uppfyller utsläpps standarder även när det inte gör det. Volkswagen hade ett problem på sina händer. Dess dieselmotorer var kända för att få bra bränsleekonomi, men NOx-fällan fungerar bara bra när mer bränsle används. Så bilen skulle upptäcka, använder denna manipulationsanordning, när det var att få ett utsläpp testet, skulle det använder mer bränsle, göra NOx-fällan fungerar bra, utsläpp skulle vara bra. Men sedan får du på vägen, enheten stängs, du bränner mindre bränsle men du lägger så mycket som 40 gånger fler föroreningar i atmosfären. Men hur heck gjorde bilen vet att det var testas för överensstämmelse utsläpp? EPA säger att det var en sofistikerad system som kontrolleras saker som rattläge, hastighet, hur länge motorn var på, och till och med det atmosfäriska trycket. Med andra ord fanns det inget sätt detta var oavsiktlig eftersom programvaran var utformade mycket noga för att upptäcka ett officiellt avgasprovet. Det är några ganska allvarliga bedrägeri och det är varför Volkswagen är i sådana allvarliga problem. I själva verket, deras VD, Martin Winter, bara avgick. 

Så vad händer härnäst? Tja, om du är en av de halv miljon diesel Jettas, Beatles, Golfs, Passats, eller Audi A3s åstadkommes, Den goda nyheten är är att din bil är fortfarande säker att köra. Du behöver inte lägga undan tills Volkswagen utfärdar ett återkallande. Men någon gång de är förmodligen kommer att ha att uppdatera programvaran i bilen. När det händer du kanske får färre miles per tank. Advokater redan utväxling för grupptalan så ägare kan bli kompenserad någon gång i framtiden. Men det kommer inte att hända någon gång snart. 

[END SPELA] DAVID J. MALAN: Så detta faktiskt väcker en intressant större bild fråga att lita på. Höger? Alla av oss har iPhone eller Androids eller något i våra fickor troligtvis dessa dagar, eller bärbara datorer på våra varv som är kör mjukvara gjord av Apple och Microsoft och klasar av andra företag. Men hur vet vi att vad dessa program gör är faktiskt vad dessa företag säger att de gör? 

Till exempel, som är att säga att varje gång du ringa ett samtal på din iPhone eller Android-telefon eller liknande, att det telefonnumret är inte heller att överföras till något företag server på grund av något program du har skriftligt, oavsett om det är drifts själva systemet som iOS eller Android, eller för att du har hämtat en tredje part app som på något sätt lyssnar allt du skriver in eller allt du faktiskt säger. Hur vet du det, när ni kör Clang Eller Lägg till kompilera egen programvara i CS50, hur gör du det CS50 egen personal, med hjälp av CS50 biblioteket har inte varit att logga varje sträng du någonsin fått eller varje tum du någonsin fått? Tja, kan du säkert se på källkoden för något som CS50 biblioteket, du kunde titta på källkoden för Linux operativsystem körs på CS50 IDE. Men en fantastisk presentation gavs igen 1984 i mottagandet av Turing Award av en mycket berömd datavetare känd as-- namnges Ken Thompson som fick turingpriset som är en slags datavetenskap s Nobelpriset, om ni så vill, för hans arbete på ett operativsystem kallat Unix, som är mycket lik i ande vad vi använder som är Linux. Och frågan frågade han i sitt tacktal, huvudsakligen om ramen för åratal av diskussioner om tillit och säkerhet, var detta. I vilken utsträckning bör ett förtroende en uttalande om att en program-- en bit av software-- är fri från trojanska hästar? Kanske är det viktigare att lita de personer som skrev programvaran. 

Och i själva verket har vi länkat till föredrag som han gav när det godtog denna utmärkelse på 80-talet på CS50 hemsida under Föreläsningar sida för idag. För vad du ser är att han faktiskt ger ett ganska enkelt exempel på hur även en kompilator som Clang eller vad kompilatorer andra har använt i tidigare, vad händer om inbäddade i kompilatorn vi själva använder är lite om villkor att väsentligen säger, om du märker att denna kod använder getString funktion eller getInt funktion, gå vidare och sätta en bakdörr eller en trojansk häst så att detta program har nu några nollor och de som gör något skadligt. Logga alla dina tangenttryckningar, ladda upp dessa data till viss server, eller egentligen vad som helst. 

Och vad Ken Thompson fortsätter med att göra i sitt tal är att visa att även om du har tillgång till källan kod för en kompilator som uppsåtligt kan göra detta, det spelar ingen roll eftersom Det är det här hönan och ägget verklighet av det förflutna många år vari kompilatorer används för att kompilera själva. Med andra ord, vägen tillbaka när någon hade att ha skrivit den första kompilatorn. Och därefter, när som helst de har uppdaterat en kompilator genom att ändra dess källkod, att lägga till funktioner och kompilera det för människor som oss att använda, ja, de använder den gamla version av kompilatorn att sammanställa nya version av kompilatorn. Och om du tar en titt på tal som han gav, ser du att eftersom i nämnda cirkularitet du faktiskt kan ha fel eller Trojanska hästar inbäddade i programvara vi använder. Och även om du tittar på källkoden för dessa program, Det kanske inte ens vara uppenbart eftersom knep är faktiskt i vissa äldre version av en kompilator som sedan dess har varit injicera hotet i vår mjukvara. 

Vilket är bara att säga, vi verkligen kan inte och bör inte förtroende programvara som körs på våra bärbara datorer eller telefoner eller valfritt antal platser. Och i själva verket senare i den här terminen när Vi börjar prata om webbprogrammering och faktiskt börja bygga webbapplikationer själva, vi pratar om dessa hot och andra. Nu kanske du har undrat och märkte att det fanns en liten liten Darth Vader i klipp som The Verge visade det om Volkswagen. Om du aldrig sett, jag trodde vi skulle lätta stämningen eftersom det är allt mycket deprimerande och skrämmande. Jag kommer att se tillbaka på Super Bowl 2011 när en kommersiell med Volkswagen-- och detta nästan gör dem sympatisk igen-- sändes för första gången på TV. Det är 60 andra klippet som jag tror att du kommer att njuta av. [VIDEOAVSPELNING] [MUSIK - tema från "Star Wars"] [Hunden skäller] [Bil startar] [END SPELA] DAVID J. MALAN: Ja. Jag var bara kontroll. Bilen är på listan över kränkningar. Okej. Så vi titta på några pseudokod för en stund sedan. Och här är en större utdrag av pseudokod kod att vi har sett ett par gånger hittills. Och låt oss använda detta är en möjlighet nu att införa en ny programmering teknik som vi gjorde se algoritm förra veckan när vi tittat på merge sort. Men låt oss formalisera den och se hur vi kan använda den i faktiska koden, och sedan ska vi använda denna teknik på vägen mest sannolikt att lösa vissa andra problem. 

Så det här var en av de första programmen vi någonsin skrev, om än i pseudokod kod. Och vad detta program tillät oss att göra kursen var att hitta Mike Smith i en telefonbok. Och lägg märke till särskilt linjer åtta och 11 som hade denna Go To uttalande. Och i själva verket, vissa språk, C bland dem, faktiskt har en uttalande som är bokstavligen gå till som låter dig hoppa till en viss linje. Det är allmänt ogillande eftersom Det kan vara mycket lätt missbrukas och du kan börja hoppa din program överallt i motsats till att använda den typ av logik och styrflödet att vi har använt hittills med bara loopar och villkor och liknande. 

Men vi kan förenkla denna algoritm i pseudokod kod enligt följande. I stället för detta iterativa eller looping tillvägagångssätt där vi hålla tillbaka och tillbaka och tillbaka till linje tre, varför inte vi bara typ av punt och mer brukar säga i linje sju och 10, bara ersätta de två par rader med, else if Smith är tidigare i boken vi ska söka för Mike i vänstra halvan av boken. Else if Smith är senare i bok, söka efter Mike i höger halv boken. Och märker redan cirkularitet. Höger? Jag letar efter Mike telefonboken och sedan Jag slog så småningom kanske line sju eller kanske ledningen 10 och min undervisning till mig själv är att söka för Mike i hälften av telefonboken. Nå, hur gör jag söker efter Mike? Jag är i mitten av söka efter Mike, varför du slags skicka mig i en cirkel? Men det är OK eftersom det är händer med storleken på problemet, som det står skrivet i linje 7 och 10? Vi är inte bara säga sökning för Mike, söka efter Mike. Vi är särskilt säga vad? Sök efter honom i den vänstra halvan av den högra halv som är effektivt halv storlek av problemet. Så det är OK att vi är typ av engagera sig i denna cirkel, Detta cirkelresonemang, eftersom åtminstone är vi vilket gör problemet mindre och mindre. Och så småningom vi ska nå det så kallade referensscenariot där Vi har bara en sida left-- som vår volontär förra veckan did-- vi hade en sida vänster och sedan gör vi inte måste fortsätta söka efter Mike Smith eftersom han är antingen på den sidan eller han inte. 

Så hur kan vi genomföra denna idé, detta slags cirkel i själva koden? Tja, kan vi utnyttja en teknik som är allmänt känd som rekursion. Och vi har sett detta i pseudokod för merge sort förra veckan. Minns att detta var den pseudokod för merge sort. Det är utan tvekan ännu enklare än bubbla eller urval eller insättningssortering bara i termer av enkelhet med vilken du kan uttrycka det. 

Men det beror på vi slags cirkulärt sade söka efter något genom att söka efter det igen. Men vi söker antingen på den vänstra halv eller den högra halv och sedan så småningom vi är sammanslagning i det här fallet. Men även här, med dessa två sorteringslinjer, vi återigen har detta tanken på rekursion. Och konkret vad detta innebär, i samband med en algoritm, är att en algoritm är rekursiv om det använder eller kallar sig. 

Eller med avseende på C, är en funktion recursive-- en funktion som kallas foo är rekursiv om foo, någonstans i dess källkod, anropar funktionen foo själv. Och det är illa om alla foo någonsin gör är kalla sig om och om igen. Det är OK om foo stannar så småningom, liksom merge sort, genom att säga, vänta en minut, om detta problem är super liten, till exempel, eller fann jag honom som jag söker, bara tillbaka. Inte rekursivt, inte cykliskt kalla mig igen. 

Och så låt oss ta en titt på hur detta kan faktiskt fungera. Så jag kommer att gå vidare och öppna upp två källa kodexempel här. En av som kallas sigma 0. Och det är inte alls rekursiv, men låt oss ta En titt på vad det här programmet gör. Jag har avskalade ut alla synpunkter från det men alla av källkoden på CS50: s webbplats har synpunkter om så du vill läsa igenom den igen senare. Och låt oss göra ett par av sanity kontrollerar här. 

Så på toppen av denna kod, vi har inkludera CS50.h. Vad gör detta? Varför är det här? I rimlig lekmannaspråk. Vad gör den? Yeah. 

PUBLIK: Så att getInt funktionen fungerar. 

DAVID J. MALAN: Så det den getInt funktionen fungerar. Eftersom insidan av denna fil, CS50.h, vilket vi får se snart i fråga om källkoden, har en massa funktioner declared-- getInt, getString, och ett gäng mot andra, och om vi faktiskt har att Inkludera linje, kompilatorn Clang är inte kommer att veta att den existerar. Och samma sak gäller för linje två där int definieras printf, som är en funktion vi fortsätta att använda en hel del. Nu verkar linje fyra lite funky eftersom det är bara en liner. Det har fått ett semikolon, inte lockigt hängslen, ingen kod inne i den. Men vad gjorde vi kallar den här saken i veckor tidigare? Yeah. Så en prototyp. Och varför har vi en prototyp som verkar att vara lite överflödig vanligtvis eftersom vi vanligtvis se funktionen igen senare i filen, eller hur? Så varför vi have-- du bara skrapa huvudet men jag tar det. Yeah. 

PUBLIK: [OHÖRBAR] funktion efter huvud. DAVID J. MALAN: Exakt. Så att kompilatorn känner dig så småningom kommer att definiera eller genomföra som fungerar efter huvud, förmodligen. Så Clang och mest kompilatorer är typ av dum och de ska bara veta vad du säger dem. Och om du vill använda en funktion som kallas sigma, du bättre lär kompilatorn att den existerar i förväg. 

Nu, huvud själv, även även om det är ett gäng linjer, är ganska bekant förhoppningsvis nu. Det har fått en gör while-slinga vars syfte i livet här tydligen är att få en positivt heltal från användaren. Och bara hålla tjat honom eller henne tills de samarbetar. Sedan i linje 16 Jag har ett intressant samtal. IntAnswer. Som på den vänstra sidan sidan ger mig en Int vilket kan store-- kallas Answer-- som kommer att lagra, som synes, returvärdet för sigma. Så sigma är bara en godtyckligt men meningsfullt namn att jag har gett till en funktion vars syfte i livet är att ta en argument-- vi kallar det N i detta case-- och bara ta summan av det antal plus varje positivt tal som är mindre än det. 

Så om jag klarar av antalet 2 sigma, jag vill lägga till två plus ett plus 0-- inte 0-- så det ger mig tre. Om jag passera i 3 till sigma, jag vill har 3 plus 2 plus 1, vilket ger mig sex. Och så vidare. Så det lägger bara upp alla tal mindre än eller lika med det. 

Nu, här nere jag bara gå att skriva ut svaret. Så som en snabb kontroll sanity, låt oss göra sigma 0-- punkt snedstreck sigma 0-- och låt mig skriva in 2. Och jag verkligen få 3. Låt mig skriva in 3. Jag får faktiskt sex. Och om någon kan göra matten snabbt, om jag gör 50 vad ska jag få? 

PUBLIK: [OHÖRBAR]. DAVID J. MALAN: Tja, nej. Men 1275 som är ganska nära. Så detta är ett resultat av att göra 50 plus 49 plus 48 plus 47 plus 46 hela vägen ner till ett. Så det är allt sigma gör. Men låt oss se hur vi har genomfört det nu. Så här nere är själva funktionen. Och det verkar inte ha något att göra med rekursion ännu. I själva verket använder vi en old school teknik. Jag initiera en variabel som heter summa till noll, då jag har en foreloop här, och jag förklarar en Int kallas Jag, sätta det lika med 1-- även om jag kunde ställa in den lika med noll, men eftersom jag gör dessutom vem bryr sig om det är noll eller ett. Det kommer att ha någon effekt. 

Så jag iteration så länge jag är mindre än eller lika med m, vilket är argumentet som antogs i. Och då jag bara hålla uppräkning I. Och insikt av slingan allt jag gör gör summa plus lika I. Och det är avsiktligt. Jag vill inte göra, i detta fall som summan plus plus. Jag vill verkligen lägga det aktuella värdet av I vilket blir bara större och större och större för att den löpande stämmer. 

Och då jag återvänder summan. Och så svaret blir värdet summan. Och då jag skriva ut den. Så det finns en möjlighet här, dock att sådan förenkling denna kod begrepps och vilken typ av slaget ett är tänka i termer av den enkelhet trots att det tar ett tag att sortera av förstå varför detta är kraftfull i dessa små exempel. Här är sigma en-- så andra version av denna kod. Allt upp topp är identiska så samma berättelse gäller som tidigare. Men nu ska vi titta på genomförandet av sigma som Jag har reducerats till bara dessa lines-- fyra rader kod, verkligen, plus några klamrar och blanktecken. 

Men vad gör jag? Om m är mindre än eller lika med noll, jag behöver typ av hantera det super enkelt fall. Och om du lämnar mig noll eller något negativt vilket är bara konstigt, Jag kommer bara att godtyckligt men genomgående retur noll. Jag vill inte att denna sak att få in några konstiga oändliga slinga på grund av ett negativt värde. Så jag säger bara, om du ger mig noll eller mindre, jag återvänder noll. 

Men det är bra eftersom det är som enda sida av telefonboken som är kvar. Jag bita av ett mycket specifikt problem och inte kräver något rekursivt. Men i linje 31, vilken jag verkar göra? De parenteser bara hålla saker, förhoppningsvis, lite tydligare. Men allt jag gör är att jag är återvända m-- oavsett du lämnar mig-- plus Värdet av m-- ledsen, plus värdet av sigma m minus 1. Så vad betyder det? Om du ger mig siffran 3 som indata, det svar jag vill komma i slutändan är 6 eftersom tre plus två plus en ger mig sex. Men hur gör jag tänker på hur denna kod körs? Första gången jag kallar sigma och jag passerar i värdet 3, det är som att säga på en bit papper, här är värdet 3 och jag har klarat detta som sigma. 3 är naturligtvis inte mindre än 0 så IF villkor gäller inte. Den andra gör. Så vad ska jag göra? Jag vill återvända m, som är 3, plus sigma m minus 1. Så låt mig hålla reda på detta. Jag kommer att sätta detta papper ned. Och vilket värde, att vara klart, jag kommer att passera i sigma vid denna tidpunkt i historien? Vilket nummer? 2, eller hur? 3 minus 1 är 2. Så jag behöver bara lite papperslapp här. Så nu sigma är att få kallas igen. Och jag har medvetet lagt ner det eftersom det är ungefär som pausa den versionen av berättelsen för nu är jag fokuserad på signalen av m minus ett. Så m var 3, m minus 1 är 2. Så här är två som jag har gått. 2 är naturligtvis inte mindre än 0 så att fallet inte gäller. Annars jag återvänder m, som är sak, plus sigma vilket värde? Så om sigma av 1-- eftersom m är just nu två så 2 minus 1 är en. Så nu har jag bara värdet 1. Jag passerar bara antalet 1 till funktionen sigma-- eller själv här-- så en är uppenbarligen inte mindre än noll, fortfarande inte gäller. 

Else avkastning 1 plus sigma av vad? 0. Så låt mig bara ihåg att. Jag återkommer till det senare. Nu ska jag gå vidare och jota minska antalet 0 eftersom det är mitt argument eller parameter. Jag passerade siffran 0 och slutligen denna process för att bara upprepa mig annons nauseum inte upphör eftersom det jag omedelbart göra när jag ser detta 0? Jag återvänder noll. Så nu har du att spola tillbaka historien. 

Om jag nu går bakåt i tiden, Vad var det senaste sak Jag gjorde om du var bokstavligen en video spolar tillbaka? Jag kommer att ta upp den senaste 1 och det ger mig en plus 0 är 1. Om jag håller bakåt av historia, som kommer att ge mig 2 plus det löpande värdet, vilket är 1. Så det är tre. Och sedan kommer jag att hålla omrullningen. När jag först lägga ner numret 3-- så 3 plus 3 ger mig sex. 

Och nu, om du har lindas video fram till denna punkt, detta var mycket första fråga jag. När passerade 3, vad är sigma 3? Det är i själva verket 6, summan av alla dessa bitar av papper. Så om det tar ett tag att linda ditt sinne kring, det är bra. Men anser att det var en little-- det var mycket medveten om att jag staplade dessa siffror ovanpå varandra. Det är ungefär som att ha en memory-- en post i tid, som en skrubber i en video, att jag verkligen kan spola tillbaka in. Och vi kommer att komma tillbaka till som metafor i bara lite. 

Men först, visar det sig att det finns en hel del nördar och roliga människor, Jag antar på Google. Skulle någon som är mycket bra på att googla sinne kommer upp för ett ögonblick och hjälpa mig att söka efter något? Mycket, mycket låg nyckeln. Någon som är aldrig komma upp innan, kanske. OK. Yeah? Kom igen. Kom ner. Vad heter du? 

SAM: Sam. 

DAVID J. MALAN: Sam, kom ner. Detta är samma. Trevligt att träffas. Hallå. Kom över. Så allt jag vill att du gör, om du kan, Sam, här är Google. Kan du söka efter termen rekursion? Förstör inte. 

Och nu let's-- ja. OK Klicka på den. Bättre klickar du på den. Ahh, få det. Nej? OK. Så låt oss göra ett par andra. Inte så mycket närstående akademiskt här, men du har någonsin sökt Google för anagram? 

SAM: Nej 

David J. MALAN: OK. Sök efter anagram istället för rekursion. Vad sägs om snett. Du någonsin sökte efter sned? Nu är det här en lite svårt att se men förhoppningsvis everything's-- OK. Det är bara du och jag njuta av detta. OK. 

Så till sist, detta one's-- det är lite sned. Nu gör ett fat rulle. Underbart. Okej. Stort tack till Sam. Här får du. Tack. 

Så vad som händer i alla av dessa fåniga exempel? Så egentligen, under huven på Googles miljontals rader kod tydligen är några dum IF förhållanden som är väsentligen kontrollera om användaren har skrev i denna fras, göra något som antagligen tog en icke-triviala mängd tid att genomföra bara vara underhållande på detta sätt. Men det är allt det kokar ned till under huven. Men, naturligtvis, rekursion är mer av geekier exempel bland de speciella trick. Och säkert finns det andra där ute samt att vi kanske inte ens upptäckt ännu. 

Så ta en titt, eller överväga nu följande program, och definitivt ta någon av dessa på väg ut. Jag kommer att gå vidare och öppna upp ett program som är kommer att försöka byta två värden. Men innan vi åker dit, låt oss göra detta. Skulle vi kunna få en mer volontär, tror jag? Vill du volontär? Nej? Kom upp. Kom upp. Okej. Så ditt namn är vad? 

LAUREN: Lauren. 

DAVID J. MALAN: Lauren. Kom upp, Lauren. Så Lauren håller på att utmanade här enligt följande. Trevligt att träffas. Så Lauren här har framför av sina två tomma koppar. Och vi har några apelsin juice och mjölk och vi kommer att gå vidare och göra följande. Vi kommer bara att fylla detta. Några uns av mjölk över här och låt oss fylla en liten apelsinjuice hit. 

Och framför allt av dessa publiken, byta de båda värdena för dessa koppar. Sätt apelsinjuice i mjölken cup och mjölken i apelsinjuice koppen. Hur skulle du göra detta om du var på hem och hade tillgång till andra förnödenheter? LAUREN: Lägg den i en kopp. David J. MALAN: OK. Så låt oss ta en tillfällig variabel, om vi kommer. Och gå vidare nu och genomföra denna samma swapping procedur. Så bra. Vi har lagt EGT i den tillfälliga variabel, mjölk i EUT variabeln, och nu den temporära variabeln in i mjölkvariabel. OK. Så mycket bra gjort hittills. Så visar det sig out-- konstatera att trodde för bara ett ögonblick. Här, bara nörd det upp lite, det här skulle vara den motsvarande C-kod att vi bara genomförs. Vi hade två ingångar, a och b, som båda som vi bara kan säga enkelhet är int s. Och lägg märke till här, om jag vill byta värdena för två variabler, a och b, vi verkligen behöver en mellanhand, en temporär variabel, en tillfällig kopp, in i vilken pour ett av värdena så att vi har en platshållare för det. Men då koden är exakt som Lauren här genomförs. 

Nu, bara för att få en lite galnare, visar sig att du kan göra detta utan en temporär variabel. För att göra detta på rätt sätt, men vi kommer att ha att fuska med viss kemi. Vi har några extra koppar här. Så det närmaste som ser som mjölk och vatten perhaps-- eller mjölk och OJ-- är att vi har en del vatten, så vi kommer att fylla detta en upp med några uns av rent vatten. Det är nog för mycket. Yeah. Det är definitivt för mycket. Håll på en sekund. 

Och nu har vi olja, vilket, som jag minns från högstadiet kemi klass, förhoppningsvis det inte blandas med vatten. Men det slags slags ser ut som mjölk och EGT. Så nu, utan att använda en temporär variabel, kan du byta dessa två värden? Så oljor går i vattnet koppen, vatten går in i oljekoppen. LAUREN: Inga andra koppar? DAVID J. MALAN: Inga andra koppar. Och jag har faktiskt inte testat detta innan år så jag vet inte om detta kommer att faktiskt arbetar kemiskt. Det var inte tänkt att ske. Är det att fungera? Okej. Så separera? God. Nu fick vi få vatten i den andra koppen. Smartare kemi koncentratorer kunde förmodligen göra detta bättre än mig. 

LAUREN: Vattnet är på botten. 

David J. MALAN: Den water-- som var vad är nyckeln sista gången vi gjorde detta. Du måste göra det i rätt ordning. Yeah. Det är ok. Så nu har vi två koppar olja. OK. Det är ok. Men kemiskt om detta fungerat än jag-- 

LAUREN: Detta är vatten. 

DAVID J. MALAN: Det är mestadels vatten. Okej. Men det är fortfarande samma kopp som tidigare. Så häll det-- prova det där borta. OK. Detta är en bra användning av lektionstid idag. OK. Så nu we-- trevligt. Ungefär. Okej. Så mycket bra. Tack till Lauren. Väldigt bra gjort. 

Så bara för att blåsa era sinnen, och detta är kanske något att spela med om du vill i CS50 ID, Du kan i själva verket, byta två variabler utan att använda en temporär heltal. Och detta är motsvarande C-koden. Och om du minns från förra Onsdag, införde vi, om kortfattat, några nya aktörer i C och gör någon ihåg vad den lilla morot symbol är den lilla trekantiga symbol på tangentbordet representerar? Vad bitvis operatör? 

PUBLIK: EXOR. 

David J. MALAN: EXOR. Exklusiv Or. Så om du vill, bara för skojs skull på hem, för att ge a och b två godtyckliga värden som alla eight-- och jag skulle välja ett åtta bitars värde. Om du gör detta med 32 bitar, du mycket snabbt uttråkad. Men bara ge en ett åttabitars värde som är vad, ett eller två, och ge b ett liknande värde. Och sedan använda definitionen av XOR från förra onsdagen, tillämpa detta bit för bit, var och en av dessa åtta bitar i varje av a och b, och sedan göra det exakt per denna kod. Och det är inte fel vad du ser här på skärmen. Det kokar verkligen ner till tre XOR-operationer och något magiskt en och b kommer att utbyta positioner utan att förlora någon information. 

Så att oljan och vatten tricket är den närmast verkliga världen inkarnation Jag kunde tänka på att efterlikna det. Men det är säkert lättare att använda en temporär variabel, som i detta fall här. Och även detta är en möjlighet att säga, Även denna typ av mikro optimering, som en datavetare skulle säga, medan ganska kul att skryta om hur du gjorde detta utan som att byta med en extra variabel, Det är inte så övertygande. Eftersom att spara 32 bitar, som i fallet med en verklig int, är inte så övertygande på ett system där du kanske använder tiotals megabyte eller ännu mer sådan minnes dessa dagar. Och faktiskt, när vi får till ett senare problem set och du implementerar spell checker och du utmanas att göra det med detta så litet RAM och så litet tid som möjligt på computer-- du fortfarande har en vecka för att genomföra det-- du have-- kommer du att utmanas att minimera dessa resurser. Och det är egentligen den enda föran denna termin där du kommer att uppmuntras att raka av även de finaste prestanda kostar annars. 

Så Vad-- hur kan vi se detta i själva koden? Låt mig gå vidare nu och öppna upp ett exempel som avsiktligt kallas Ingen Swap eftersom den inte i själva verket byta variablerna som du faktiskt kan förvänta sig. Så låt oss ta en titt. Här är ett program som inte har någon CS50 bibliotek pågår, bara standard I / O. Nu har vi en prototyp för swap där uppe som just betyder det måste fastställas senare. Och här är huvud. 

Jag godtyckligt x och y, respektive, värdena en och två bara för att de är små och lätt att tänka på. Och då har jag bara en massa printfs där jag har en sanity check. x är ett och y är 2 är förmodligen vad dessa printfs kommer att säga. Så ingen magi hittills. 

Då kommer jag att hävda med ut def, byta dot dot dot. Jag kommer att kalla swap funktionen, passerar x och y. Och låt oss anta nu att swap genomförs exakt eftersom det var en stund sedan med en temporär variabel. Och så jag hävdar djärvt, bytte. x är nu detta och y är nu att. Men filen, naturligtvis, kallas Ingen Swap. Så låt oss faktiskt se vad som händer. Om jag sammanställer ingen swap och sedan do ./noswap, x är 1, y är 2. Byta bytte. x är 1, y är 2. Så det verkar faktiskt vara bristfällig även men swap-- låt oss rulla ned now-- genomförs exakt per kod föreslog jag för en stund sedan. Så vi kommer inte att få lust med XOR grejer nu. Även detta bör fungera lika som med mjölk och EGT, men det verkar inte fungera. 

Så låt oss göra det igen. Jag kanske bara inte kördes det rätt. Så låt oss köra Ingen Swap igen. Kanske jag-- nr. Så det är bara inte fungerar. Så låt oss göra en liten sanity check. Låt mig gå vidare här i Swap och bara lägga till, vänta en minut, a är% i / n och låt oss plug-in värdet av en. Eftersom jag verkligen vill för att se vad som händer. Och faktiskt, är detta en felsökning teknik som du kan använda i kontorstid eller hemma redan, besläktad med den första halvan av Dan Armendariz video i PSET3 där vi introducerade tryck def som en rekommenderad teknik, åtminstone för enkla fall. Låt mig gå vidare och kör make ingen swap igen, ./noswap. 

Intressant. Så märker vad som verkar vara sant. X är ett, y är 2, men en är 2 när b är 1. Så de två på något sätt fick bytte men x och y inte får växlas. Så för att vara tydlig, vad händer är, här uppe har jag x och y och de är variabler lokala i omfattningen av huvud, jag passerar x och y att byta. Nu, swap, som en separat funktion, är att ringa sina argument eller dess parametrar något man vill. Foo eller bar eller x eller y eller a eller b. Bara för att klargöra att de är inte är identiska med x och y i sig, Jag har sagt a och b. Men vi kan kalla dem vad vi vill. 

Och så det ser ut swap förs vidare x-- AKA en-- och det är får passera y-- AKA f. På något sätt dessa tre linjer är byta dessa värden exakt som Lauren gjorde med mjölk och EGT. Men när vi skriver ut värdena, a och b är verkligen byta men x och y har ingen förändring av dem. Minns att x och y är här uppe. 

Så att vi kan se detta via en annan teknik också. Och även detta är en teknik inbäddade i problem som trede. Låt oss gå vidare och göra detta i CS50-ID om du inte redan har gjort. På höger sida är vi har den här fliken Debugger. Och om du öppnar upp denna, det finns en del svårbegripliga uppgifter som kastas på dig från början. Men låt oss retas detta dem riktigt snabbt. 

Så en, ser du lokala variabler. Det visade sig att bygga in CS50 IDE, och en hel del programmeringsmiljöer mer allmänt är en avlusare. Ett verktyg som låter dig visuellt se vad som händer inne i ditt program utan att behöva tillgripa tillsätta printfs och sammanställa och köra och lägga printf s och sammanställa och kör, som redan i kontorstid eller hemma, är förmodligen bli ganska tråkiga. 

Så här, i ett ögonblick, vi är kommer att se i realtid värdena för våra lokala variabler. Vi kommer även att kunna sätta vad som kallas brytpunkter som finns möjligheter i mitt program för att pausa bearbetning på visst kodrad att jag är nyfiken på. Höger? Dessa program körs i en bråkdels sekund. Det är typ av trevligt för oss långsammare människor att kunna pausa, ta en stund, se vad som händer runt en viss kodrad utan programmet plöjning igenom den och helt avslutad. Så en brytpunkter kommer att tillåta oss att bryta och pausa vid en viss punkt. 

Anropsstacken är ett finare sätt att säger vilka funktioner finns för närvarande kallas just nu. Main alltid kallas först. Men om huvud kallar en Funktionen kallas Swap, vi faktiskt kommer att se ut torn av funktioner som har varit kallas i omvänd kronologisk ordning. Så låt oss se det. 

Jag kommer att zooma ut. Jag kommer att gå tillbaka till min kod. Och bara för att jag vill ha att vara pedantisk här, Jag kommer att gå vidare och klicka precis till vänster om linjen fem. Och det skapar en röd prick. Och lägg märke på höger sida att debugger vet, hej, Jag sa bara en brytpunkt på noswap.c linje fem, särskilt vid denna kodrad. Så debugger vet att jag har begärt att nästa gång Jag kör mitt program det paus utförande det snarare än bara kör hela supersnabb. 

Så nu ska jag klicka Debug knappen högst upp på IDE och det kommer att göra följande. Det kommer att öppna en initialt något skrämmande ser andra terminal window-- fjärrfelsökning från värd för ett sådant och such-- och vi ska återkomma till vad allt vad det innebär inom kort. Men vad som är viktigt just nu det vill säga att red dot drabbades, debugger har medvetet pausas execution-- inte på den linjen i sig utan på den första raden av faktiska koden i denna funktion. Och det är därför linje sju är nu gulmarkerad. 

Och nu ska vi ta en titt på höger sida. Det ser ut, som standard, fint nog, x har vilket värde? 0. Och y har vilket värde? Noll. Och det är som kan förväntas i den mening att x och y-- att gula line-- har inte utförs än. Så x bör inte ha värdet 1. Det kan ha något annat värde, en så kallad skräpvärdet. Och vi fick tur att det är noll vid denna tidpunkt, i huvudsak. 

Så nu finns det bara ett fåtal knappar vi behöver bry om när felsökning på det här sättet. Lägg märke till här, har vi en Play-knappen. Och om vi spelar eller slå återupptas, det är bara kommer att gå igenom resten av programmet eller tills den träffar en annan brytpunkt. Men jag har inte satt någon annan brytpunkter så det är bara kommer att köra till slutet. Denna typ av besegrar Syftet med att peta runt. 

Så istället, jag bryr mig om dessa ikoner till höger. Och om jag hovrar över dem, som ni bör också, ser du lite tips-- verktygstips. Detta är steg över. Nu det betyder inte att hoppa Följande kodrad. Det betyder bara köra den och flytta till nästa, gå vidare till nästa, gå vidare till nästa. Med andra ord, genom den knappen, kan jag gå genom min kod ett steg i taget. Rad för rad, bokstavligen. Nu, till höger om att det finns en annan att vi får se på bara ett ögonblick. Detta är den så kallade Step Into ikon som är kommer att låta mig dyka in i en annan funktion. Men låt oss se detta på bara ett ögonblick. Så jag kommer att klicka kliva över. Och nu märker, när jag klickar den här knappen uppe till höger, hålla ögonen ungefär under Lokal Variabler och se vad som händer med x. x är nu ett eftersom gul linje har nu verk och vi har gått vidare till linjen 8. Och på bara ett ögonblick y förhoppningsvis bli 2. 

Nu, ingenting som intressant händer för lite. Allt detta är är printf. Och lägg märke till, enligt min sekundära terminal fönstret ser jag produktionen av utskrifts def. Och nu har jag att göra en beslut som programmerare. Jag kan kliva över denna linje av kod, verkställer det, men inte få veta vad som finns inuti. Eller jag kan faktiskt kliva in det och gå inne i Swap själv. Så låt oss göra det senare. 

Låt mig gå vidare och klicka inte Step Over men Step Into. Observera, helt plötsligt fönstret ändras för att markera den första kodrad i Swap. Det är linje 21. Och nu, vad är typ av funky är att om man tittar hit, som väntat, ett komma b är 1 och 2, respektive. Varför är temp 32767? Erinrar om att temp, likt den tomma koppen för en stund sedan, förklaras här på ledningen 21. Varför 32,000- Jag menar, varför är det bara några konstiga värde? Yeah? 

PUBLIK: Det är inte initieras. 

DAVID J. MALAN: Det är inte initierats. Så vår dator alltid har fysiskt minne. Det har alltid fysiskt RAM. Och det finns alltid noll s och en är där, eller hur? Eftersom vi använder vår dator hela dagen lång, du använder CS50 IDE eller servrarna hela dagen lång. Så att RAM antingen har några nollor eller någon har eller några nollor och ettor. Oavsett huruvida du inte använder dem. Du kan inte bara ha tomt utrymmen där du vill ha bitar. De är antingen nollor och ettor. 

Så visar det sig att temp, eftersom Vi har inte initierats det ännu, Vi har dessa 32 bitar, men de har inte initierats till några kända värden. Så vad de var mest nyligen använt for-- dem 32 bits-- vi bara ser artefakter av vissa tidigare användning av de särskilt 32 bitar. Så fort jag klickar Step Over dock, Puh är temp kommer att få värdet 1. Och om jag gör det igen, är en kommer att ges värdet 2 och sedan b kommer att ges värdet 1. 

Så vad är trevligt nu på denna punkt i historien är att debugger är visar mig, super långsamt i min egen takt, vad delstaten Swap är. Men märker på toppen här, meddelande att anropsstacken faktiskt har två lager till det. Nu den som är markerad som Swap, om jag klickar på Main i stället, Lägg märke till hur de lokala variablerna ändras eftersom utvecklaren kan bara hopp runt och gå in i någon annan omfattning. Så även om vi gör allt detta arbeta och korrekt byta a och b, om jag går fram och tillbaka mellan Swap där a är 2 och b är 1 och Main, har huvud påverkats alls? Nej. Så vad är takeaway här? Tja, visar det sig att varje gång du kallar en funktion som Swap, och du passerar det argument, vad du passerar till Swap-funktionen i detta fall är en kopia av dessa argument. Så om x och y vardera respektive 32 bitar, vad Swap blir är två nya lokala variabler, eller argument, kallas en och b-- men de är godtyckliga names-- men mönstret för nollor och ettor insidan av a och b är uppradade för att vara identisk med x och y men de är inte samma sak som x och y. 

Det är som om huvud har på sin bit av papper nummer 1 och 2 för x och y, och sedan när det händer att papper till Pendla, Swap blir mycket snabbt sin egen penna, skriver ned 1 och 2 på eget pappersark, händer tillbaka den ursprungliga xy till Main och sedan gör sitt eget sak med a och b. Och det är nu super viktigt eftersom detta har icke-triviala implikationer för att faktiskt skriva korrekt kod eftersom det verkar vi inte kan byta två variabler. 

Jag har skrivit en korrekt Swap funktion. Vi har infört den med Lauren som en korrekt växlingsfunktion i verkligheten, men tydligen inget av detta frågor om du inte kan faktiskt byta två värden permanent. Så vi behöver en annan väg att faktiskt komma åt detta, och vi måste kunna faktiskt lösa detta problem. Och det visar out-- och vi ska komma tillbaka till just denna bild innan long-- detta är ett sätt att du kanske göra din dators minne. Det är bara en rektangel. Du kan dra den något antal sätt men det är bekvämt att rita det som en rektangel av följande skäl. 

Vi kommer att börja idag och framöver talar om den så kallade stack. Och stapeln är bara en bit av RAM-- en bit av memory-- som fungerar att ha tillgång till när de kallas. Och så visar det sig att åtmin allra längst ner på denna stack är där alla huvud lokala variabler och org C och org V och allt det där kommer att gå som standard. Och om huvud Parlamentet någon annan funktion som Swap, Tja, är Swap kommer att få en annan skikt av minne upp ovanför. 

Och så bara för att ge dig en snabb ytlig bild av detta, om jag går över här-- och låt mig spegla detta på overhead som well-- vad som verkligen har jag, om vi bryr oss bara om nedre delen av denna bild för nu, är att när jag kör ett program och Main anropas, Huvud ges en bit av RAM i min dator som är längst ner i denna så kallade stack. Och jag kommer att dra det avsiktligt som en fyrkant. Så det är som 32 bitar eller fyra byte. Och om detta huvudfunktion har ett variabel som heter x till ett värde av 1 och den har en variabel som heter y med värdet 2, som är som att ta denna flisa av minne som Huvud har givits av den operativa systemet och dela upp det så att den första lokala variabeln går här, den andra går här, och det är det. 

När huvud kallar Swap, Pendla får sin egen bit av minne att vi kommer att dra ut så här från operativsystemet, och det kommer att få sin egna lokala variabler baserade på vår implementering tidigare med lokala variabler en och B som initialt få värdena 1 och 2. Men sedan, så snart Växla koden körs, och Lauren faktiskt swappar EGT och mjölk, vad som händer? Nåväl, denna 2 blir 1, detta 1 blir en 2, och, förresten, Det finns en temp variabel som är att vara använde den hela tiden som så småningom går iväg. Men det spelar ingen roll hur mycket arbete du gör i denna linje of-- i denna minnesutrymme, x och y är helt orörd. 

Så vi behöver något sätt att ge Swap och funktioner som det hemlig tillgång, om ni så vill, till funktioner like-- till minnet som x och y. Så låt oss ta en titt på ett exempel som hjälper oss se exakt vad som varit pågår hela tiden. Jag kommer att gå vidare och öppna upp Jämför Zero. Och jag kommer att stänga vår debugger, jag kommer att stänga denna skrämmande ser meddelandet den bara säger, vänta en minut, du är i mitten felsökning. Jag kommer att dölja den här fliken här bara för att gå tillbaka till enkelhet. Så oroa dig inte om GDB dödas. Det betyder bara att programmet har blivit sluta, medvetet i det här fallet, av mig. 

Och nu Jämför Zero gör detta. Jag använder CS50 biblioteket i standard I / O. Jag har en huvuduppgift som först säger, säga något, och får en sträng. Sedan säger det igen och får en annan sträng. Och lägg märke till att dessa två strängar kallas s och t, ​​respektive. Och nu detta program Jämför Noll, dess syfte i livet, det är tänkt att berätta för mig, jag skriver samma sak? Och så jag ska tillbaka till vecka ett. Jag använder min lika lika operatör vilket är den kvalitetsoperatör. Inte uppdraget operatör, likhetsoperatorn. Jag bara jämföra s och t. 

Så låt oss faktiskt gå vidare och göra det. Och jag kommer att gå vidare och göra Jämför Zero. Jag kommer att göra ./comparezero. Och jag kommer att gå framåt och säga något som, låt oss göra mamma i gemener Och vad sägs om mamma i versaler. Och naturligtvis jag skriver olika saker. Okej. Det är att vänta. 

Låt oss köra den igen. Båda gångerna gör gemener, versaler. Det ser super identisk med mig. Enter. OK. Kanske är det bara konstigt eftersom det är inte gilla min grammatik. Så låt oss göra en kapital MOM, huvudstad MOM, identiska. Olika saker. 

Så varför är det? Tja, vad som faktiskt händer på under huven här? Så låt oss gå tillbaka över här bara ett ögonblick och fundera över vad getString är faktiskt gör. När du ringer getString, det är en funktion som vi själva skrev och det på något sätt blir en sekvens av tecken från användaren. Och låt oss anta att den första gång jag ringer getString, som ger mig en bit av minne som ser ut så här. Och om jag skrev i gemener m-o-m-- och vad som händer efter det? Bara en snabb sanity check. 

Omvänt snedstreck noll. Vi vet att. Och minns att vi spelade runt med Zamila namn och en massa andra namn när Rob var här ute på vad som händer inne i minnet. Så att historien är exakt samma. Detta är vad getString återvänder till mig. Nu, min kod för en stund sedan lagrats returvärdet för getString i en variabel som kallas s. Och sedan den andra gången jag kallade det, lagras den det i en variabel som heter t. 

Så om jag går hit, jag behöver att dra denna lokala variable-- och jag i allmänhet kommer att rita en sträng som bara-- vi ska kalla det s-- som ett litet torg här. Och nu, somehow-- hur fungerar mamma gå in i denna variabel s? Tja, vi måste gå tillbaka till första principer här. Vad getString faktiskt återvänder? 

Så visar det sig att M-O-M bakstreck noll, och vilket som helst antal andra strängar i minnet som Zamila och Rob eller Andy eller några andra, är naturligtvis i vår datorns RAM eller minne. Och RAM-minnet har like-- du har en gig RAM, två gig RAM, eller en miljard eller två miljard byte, eller kanske ännu mer i dessa dagar. Så låt oss anta, för dagens ändamål, att det spelar ingen roll hur vi nummer dem, men vi kan räkna varje av dessa miljarder euro eller två miljarder eller fyra miljarder byte. 

Och låt oss bara godtyckligt säga att Detta är den första tuggan, andra bite, tredje, fjärde. Jag medvetet inte använder noll för idag men vi ska återkomma till det. Så med andra ord, om detta är första gången jag använder programmet, Jag är bara att få tur och den första bett är på plats en sedan två sedan tre än fyra. Och om jag höll teckning, boxnumret två miljarder skulle vara vägen hit. 

Så vad tror du, då, GetString faktiskt återvänder? Det är inte återvänder M-O-M bakstreck noll i sig eftersom det tydligt får inte plats i lådan som jag har ritat. Så vad mer kan getString faktiskt åter alla dessa veckor? Svaret är på styrelsen här någonstans. Du kan inte montera M-O-M backslash noll, så vad kan vara meningsfullt i stället? Om du var tvungen att vara super smart, sätta på så kallade ingenjörs hatt, vad skulle du tillbaka? Vad är den minsta mängden information du kunde återvända som skulle fortfarande Låt dig hitta M-O-M i minnet? Yeah? 

PUBLIK: One. 

David J. MALAN: One. Och varför ett? PUBLIK: Eftersom det skulle berätta vart du ska gå [OHÖRBAR]. DAVID J. MALAN: Exakt. Jag bara kommer att återvända adressen av strängen som jag har fått. Adressen i denna fallet är platsen ett. Så vad som verkligen lagras i s-- och varje strängvariabel därmed far-- har just varit adressen för den sträng. 

Under tiden, om jag ringer GetString en andra gång och jag Skriv in bokstavligen samma thing-- M-O-M med lowercase-- M-O-M och en annan omvänt snedstreck noll, och nu kanske min programmets pågått under en längre tid så kanske detta är 10, är ​​denna plats 11, det är 12, detta är 13. De datorer som använder någon annan minne av någon anledning. Vad som nu går i mitt andra variabel i mitt program t? 10. Exakt. 

Och så när vi tittar på Källkoden till denna program där jag försöker bara att jämföra de två värdena, är s motsvarar lika med t, vad är det självklara mänskliga svaret? Bara nej eftersom en inte är lika 10. Och så ligger häri en möjlighet för oss verkligen att bara gå tillbaka till, igen, först principer och tänka på, ja, vad som händer under huven? Vi har pratat om bits och bytes och minne, men det är faktiskt bra att förstå eftersom när du ringer getString, även om vi tänker på det är åter M-O-M eller sträng mamma eller Andy eller Zamila eller liknande, tekniskt det är bara att returnera adressen av denna bit av minne. 

Men det är OK. För hur vet jag där strängen slutar? Om jag bara gett början? Tja, det omvända snedstrecket noll, eller hur? Precis i linjär tid jag kan skriva ut med tryck def M-O-M. Och så fort jag ser bakstreck noll, jag bryr mig inte där jag började, Jag vet redan underförstått där jag måste avsluta. 

Och så idag markerar beginning-- och Låt mig göra det dramatiskt eftersom vi gick igenom en massa problem för få dessa här utbildning wheels-- så idag stödhjul startar att komma ut och vi avslöjar vid least-- 

[Applåder] 

Det var väl värt resan till Target i morse, ja? Så now-- finns, visar det out, inget sådant som en sträng. String existerar inte. Det är en synonym som vi har haft insidan av CS50 biblioteket. Hädanefter kommer vi att börja ringa s och t inte strängar men char stjärnor. Och char stjärnan vi ska retas isär inom kort. Men detta är att säga, att även om vi fortsätter använder getString för nu, tekniskt jag borde vara att säga röding stjärna och röding stjärna. 

Och det visar sig vad det stjärn kommer att beteckna är något kallas en pekare eller en adress. Och faktiskt, en teaser för vad som väntar är detta 20 sekunders klipp från vår vän Nick Parlante vid Stanford som ganska länge sedan, tillbringar en löjligt lång tid, så gott jag kan berätta i hans kök eller sin källare, gör claymation införande till världen en karaktär som heter Binky som vi kommer införas nästa gång till pekare. Så här är en förhandsvisning av vad som komma skall. 

[VIDEOAVSPELNING] 

-Hey, Binky. Vakna. Det är dags för pekaren kul. 

-Vad är det? Lär dig mer om pekare? Åh, karamell. 

[END SPELA] DAVID J. MALAN: Och på att observera, Vi kommer att se dig på onsdag. Okej. Vem är dans? Kom igen. Vem är dans? Du vill att jag ska få det igång? Jag ska få det började. Woooo! 

LAUREN: Söt snygga Moses.