Lecture 2 Schreme Available 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 1968 CS655 Programming Languages University of Virginia David Evans Computer Science http www cs virginia edu evans Menu Registration Survey Results My Answers Universal Languages Stuff Languages are Made Of Scheme Infinitely many different functions 23 Jan 2001 CS 655 Lecture 2 2 Favorite Programming Languages C C Java Perl My answer 41 3 21 3 21 3 1 For getting work done C with LCLint For reading other people s code CLU For fun FL Scheme 23 Jan 2001 CS 655 Lecture 2 3 Most Hated PL COBOL 2 Perl 2 also favorite Java 1 Lisp 1 None 4 My answer For asthetics readability APL For teaching intro CS courses C For writing big systems Lisp 23 Jan 2001 CS 655 Lecture 2 4 Experience of Students in this Class C 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 5 Partner Preference Assigned Randomly Choose Your Own4 No Clear Preference 23 Jan 2001 CS 655 Lecture 2 4 2 6 Can class go over time No problem 10 Problem 0 One 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 7 Technical 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 8 Why taking this class 23 Jan 2001 CS 655 Lecture 2 9 Next Computability and Universal Programming Languages 23 Jan 2001 CS 655 Lecture 2 10 Computability 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 11 Turing Machine Tape head can Read symbol from tape Write symbol on tape Move tape left or right one square Change its own state finite state machine Infinitely long tape 23 Jan 2001 CS 655 Lecture 2 12 Universal 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 CS660 23 Jan 2001 CS 655 Lecture 2 13 Computability 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 Machine 23 Jan 2001 CS 655 Lecture 2 14 Not 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 15 Based on Duane Boning http sicp ai mit edu Fall 1999 lectures lec25 6001 12 9 99 computability ppt 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 23 Jan 2001 CS 655 Lecture 2 16 Is 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 Machine 23 Jan 2001 CS 655 Lecture 2 17 Elements of Language 23 Jan 2001 CS 655 Lecture 2 18 Elements 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 Object 23 Jan 2001 CS 655 Lecture 2 19 Means 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 20 Describing Means of Combination BNF Backus Naur Form non terminal replacement Terminals are primitives in the language don t appear on left hand side Alternatives non terminal replacement1 replacement2 short for non terminal replacement1 non terminal replacement2 23 Jan 2001 CS 655 Lecture 2 21 BNF John Backus FORTRAN manual described syntax using verbose English not a formal notation Member of Algol60 committee introduced formal notation for syntax Influential in development of functional languages FP FL Turing Lecture Normal Peter Naur Donald Knuth s suggestion Chair of Algol60 committee 23 Jan 2001 CS 655 Lecture 2 22 BNF Example Sentence NP VP NP Noun VP Verb Noun Dave Scheme Verb rocks sucks Could this language be a universal programming language 23 Jan 2001 CS 655 Lecture 2 23 BNF Example Sentence NP VP NP Noun Noun and NP VP Verb Noun Dave Scheme Verb rocks sucks We can express infinitely many things with a tiny language With the right meaning function this could be a universal programming language 23 Jan 2001 CS 655 Lecture 2 24 Scheme 23 Jan 2001 CS 655 Lecture 2