PowerPoint PresentationMenuFavorite Programming LanguagesMost Hated PLExperience of Students in this ClassPartner PreferenceCan class go over time?Technical QuestionsWhy taking this class?Next: Computability and Universal Programming LanguagesComputabilityTuring MachineUniversal Turing MachineSlide 14Not everything is computableSlide 16Is a language universal?Elements of LanguageSlide 19Means of CombinationDescribing Means of CombinationBNFBNF ExampleSlide 24SchemeSlide 26Mini-Scheme PrimitivesSlide 28Slide 29Slide 30Mini-SchemeMeans of AbstractionAbstracting ProceduresMultiple ArgumentsCurryingaddtriaddChargeLecture 2: SchremeDavid Evanshttp://www.cs.virginia.edu/~evansCS655: Programming LanguagesUniversity of VirginiaComputer ScienceAvailable within the network will be functions and services to which you subscribe on a regular basis and others that you call for when you need them. In the former group will be investment guidance, tax counseling, selective dissemination of information in your field of specialization, announcement of cultural, sport, and entertainment events that fit your interests, etc. In the latter group will be dictionaries, encyclopedias, indexes, catalogues, editing programs, teaching programs, testing programs, programming systems, data bases, and – most important – communication, display, and modeling programs. All these will be – at some late date in the history of networking - systematized and coherent; you will be able to get along in one basic language up to the point at which you choose a specialized language for its power or terseness.J. C. R. Licklider and Robert W. Taylor,The Computer as a Communication Device, April 196823 Jan 2001 CS 655: Lecture 2 2Menu•Registration Survey Results–My Answers•Universal Languages•Stuff Languages are Made Of•Scheme•Infinitely many different functions23 Jan 2001 CS 655: Lecture 2 3Favorite Programming LanguagesC 41/3C++ 21/3Java 21/3Perl 1My answer:–For getting work done: C (with LCLint)–For reading other people’s code: CLU–For fun: FL, Scheme23 Jan 2001 CS 655: Lecture 2 4Most Hated PLCOBOL 2Perl 2 (also favorite)Java 1Lisp 1None 4My answer:For asthetics, readability: APLFor teaching intro CS courses: C++For writing big systems: Lisp23 Jan 2001 CS 655: Lecture 2 5Experience of Students in this ClassC++ (38 years), C (36), BASIC (29), Pascal (21), various assemblies (12), Java (9), Perl (5), FORTRAN (4), Python (2½), Ada (2), Lisp dialects (1½), COBOL (1), Smalltalk (½)•Algol60 direct successors = 106•Pre-Algol languages = 46•Completely object-oriented languages = ½–But O-O doesn’t really mean anything•Pure functional languages = 0–Python is close (but has globals and state)23 Jan 2001 CS 655: Lecture 2 6Partner PreferenceAssigned Randomly 4Choose Your Own4No Clear Preference 223 Jan 2001 CS 655: Lecture 2 7Can class go over time?No problem 10Problem 0One said, “but if I am bored and you keep me there I will be really annoyed and glare at you”.23 Jan 2001 CS 655: Lecture 2 8Technical Questions•Used higher-order procedures:–No: 4 A little: 3 Yes: 3•Wrote function that returned infinitely many possible different functions–No: 10 (some used tables of function pointers)•Fixed points: find x where f(x) = x–Gets really interesting when x is a function!23 Jan 2001 CS 655: Lecture 2 9Why taking this class?23 Jan 2001 CS 655: Lecture 2 10Next: Computability and Universal Programming Languages23 Jan 2001 CS 655: Lecture 2 11Computability•A programming language is universal if it can express all computable functions.•A function is “computable” if there exists an algorithm that computes it.•An algorithm is a computational procedure that takes a finite number of steps.•What’s a computational procedure?23 Jan 2001 CS 655: Lecture 2 12Turing MachineInfinitely long tapeTape head can:- Read symbol from tape- Write symbol on tape- Move tape left or right one square- Change its own state (finite state machine) 23 Jan 2001 CS 655: Lecture 2 13Universal Turing Machine•Universal Turing Machine is a Turing machine that can simulate any other Turing machine•Input (start state on tape) contains both a description of a Turing Machine (i.e., a program) and its input•Yes, there really are such things–Hopefully you will see it in CS66023 Jan 2001 CS 655: Lecture 2 14Computability•A computational procedure is something that can be described by a Turing Machine•A language is universal if it can express:all algorithms = all finite computational procedures = all Turing machines = one Universal Turing Machine23 Jan 2001 CS 655: Lecture 2 15Not everything is computable•Halting Problem – will a Turing Machine halt?•Suppose we could compute it:(define (halts? P) ...)returns true if P halts, false otherwise.23 Jan 2001 CS 655: Lecture 2 16(define contradicts-halts(if (halts? contradict-halts) (loop-forever) #t))If contradict-halts halts, it loops forever;If contradict-halts doesn’t halt, value is true.Yikes! halts? must not exisit!Note: this is not a proof. (proof in 650) Perhaps it is if that doesn’t exist.Based on Duane Boning,http://sicp.ai.mit.edu/Fall-1999/lectures/lec25/6001-12-9-99-computability.ppt23 Jan 2001 CS 655: Lecture 2 17Is a language universal?•How can we prove a language is universal?–Produce a program that implements a Universal Turing Machine in the language (usually this is pretty easy)•How can we prove a language is not universal?–Prove that it cannot express the function of some Turing Machine23 Jan 2001 CS 655: Lecture 2 18Elements of Language23 Jan 2001 CS 655: Lecture 2 19Elements of Language•(Almost?) All Languages have:–Primitives–Means of combination•English:–Primitives = words (?)•e.g., “Floccipoccinihilipilification” (the act of rendering useless)–Means of combination•e.g., Sentence = Subject Verb Object23 Jan 2001 CS 655: Lecture 2 20Means of Combination•Allow us to say infinitely many things with a finite number of primitives–In English, words aren’t really primitives (linguists call the primitives morphemes – smallest units of meaning)–Means of Combination work on word parts:Antifloccipoccinihilipilification (the act of not rendering useless)Antifloccipoccinihilipilificationator (one who does the act of not rendering useless)23 Jan 2001 CS 655: Lecture 2 21Describing Means of Combination•BNF (Backus Naur