计算机语言系统课件

计算机语言系统MU!OutlineNuclearWeaponsQuestionsfromLecture1NotesFormalSystemsMIU-systemLanguagesSchemeMegabytesvs.MegatonsComputing:30,000,000timesincreaseinpowersince1969Nuclearweapons?TsarBomba50Megatonexplosion,islandinArcticSea,1961IfNuclearWeaponsfollowedMoore’sLaw(摩尔定律)...30M*50Megatons=1.5Teratons1MegatonTNT =4.184*1015Joules1.5TeratonsTNT=6.3*1021JoulesEnergyfromSuntoEarth =4x1018Joules/YearOnebombtoday~alltheenergytoreachtheEarthfromtheSunsince400ADActualNuclearWeapons（核武器发展）Hiroshima(12kt),Nagasaki(20kt)FirstH-Bomb(10Mt)TsarBomba(largestever)B83(1.2Mt),largestincurrentlyactivearsenal

Ifittakes60secondstocomputeaphotomosaicforProblemSet1todayonatypicalPC,estimatehowlongitwilltakeCS150studentsin2010tocomputethesamephotomosaic?Howlongwillittakein2013?

>(/(*(-20102007)12)18)2>(/60(*22))15>(/(*(-20132007)12)18)4>(/60(*2222))15/4>(exact->inexact(/60(*2222)))3.75Differenceinyears*12=numberofmonthsNumberofmonths/18=numberofdoublingsaccordingtoMoore’sLaw60secondstoday,2doublingsby201015secondsin201060secondstoday,4doublingsby20133.75secondsin2013Realitycheck:Moore’s“law”isjustan“observation”.We’llseeonereasonlatertodaywhyitwon’tcontinueforever.

Arethereanynon-recursivenaturallanguages?Whatwouldhappentoasocietythatspokeone?Notforhumansatleast.Theywouldrunoutoforiginalthingstosay.ChimpsandDolphinsareabletolearnnon-recursive“languages”(somelinguistsarguetheyarenotreally“languages”),butonlyhumanscanlearnrecursivelanguages.RunningoutofIdeas“Itsallbeensaidbefore.” Eventuallytrueforanon-recursivelanguage. Nevertrueforarecursivelanguage. Thereisalwayssomethingoriginallefttosay!ProductionSystems

（规约系统）ProductionSystemsSetofsymbolsPrimitivesSetofrulesformanipulatingsymbolsHofstadter:RulesofProduction,RulesofInferenceAlso:RulesofCombinationTheMIUSystemSymbols:M,I,URulesofProduction:RuleI:IfyouhaveastringendinginI,youcanaddaUattheend.RuleII:SupposeyouhaveMx.ThenyoumayaddMxxtoyourcollection.RuleIII:IfIII

occursinoneofthestringsinyourcollectionyoumaymakeanewstringwithUinplaceofIII.RuleIV:IfUUoccursinsideoneofyourstrings,youcandropit.MIUSystemExampleStartwithMUI,produceMIURulesofProduction:RuleI:IfyouhaveastringendinginI,youcanaddaUattheend.RuleII:SupposeyouhaveMx.ThenyoumayaddMxxtoyourcollection.RuleIII:IfIII

occursinoneofthestringsinyourcollectionyoumaymakeanewstringwithUinplaceofIII.RuleIV:IfUUoccursinsideoneofyourstrings,youcandropit.LanguagesWhatisalanguage?Webster:

Asystematicmeansofcommunicatingideasorfeelingsbytheuseofconventionalizedsigns,sounds,gestures,ormarkshavingunderstoodmeanings.Linguist’sDefinition

Adescriptionofpairs(S,M),whereSstandsforsound,oranykindofsurfaceforms,andMstandsformeaning. AtheoryoflanguagemustspecifythepropertiesofSandM,andhowtheyarerelated.(CharlesYang)LanguagesandFormalSystems

Whatisthedifferencebetweenaformalsystemandalanguage?Withalanguage,thesurfaceformshavemeaning.Caveat:computerscientistsoftenuselanguagetomeanjustasetofsurfaceforms.Whatarelanguagesmadeof?Primitives(almostalllanguageshavethese)ThesimplestsurfaceformswithmeaningMeansofCombination(alllanguageshavethese)LikeRulesofProductionforFormalSystemsWaystomakenewsurfaceformsfromonesyoualreadyhaveMeansofAbstraction(allpowerfullanguageshavethese)WaystousesimplesurfaceformstorepresentcomplicatedonesDoesEnglishhavethese?PrimitivesWords(?)e.g.,“antifloccipoccinihilipilification”–notaprimitiveMorphemes–smallestunitsofmeaninge.g.,anti-(“opposite”)Meansofcombinatione.g.,Sentence::=Subject

Verb

ObjectPreciserules,butnottheonesyoulearnedingrammarschoolEndingasentencewithaprepositionissomethingupwithwhichwewillnotput.WinstonChurchillDoesEnglishhavethese?MeansofabstractionPronouns:she,he,it,they,which,etc.Confusingsincetheydon’talwaysmeanthesamething,itdependsonwheretheyareused. The“these”intheslidetitleisanabstractionforthethreeelementsoflanguageintroduced2slidesago. The“they”intheconfusingsentenceisanabstractionforpronouns.Howshouldwedescribelanguages?BackusNaurForm

（BN范式）symbol::=replacement Wecanreplacesymbolwithreplacement

nonterminal–symbolthatappearsonleftsideofrule terminals–symbolthatneverappearsontheleftsideofaruleA::=BmeansanywhereyouhaveanA,youcanreplaceitwithaB.BNFExample

Sentence::=NPVerb NP::=Noun Noun::=Dave

Noun::=Scheme Verb::=rocks

Verb::=sucksHowmanydifferentthingscanweexpresswiththislanguage?Whataretheterminals?Dave,Scheme,rocks,sucks4,butonly2aretrue.BNFExample

Sentence::=NPVerb NP::=Noun NP::=NounandNP Noun::=Dave

Noun::=Scheme Verb::=rocks

Verb::=