CMSC 330: Organization of Programming LanguagesA Brief History of Programming LanguagesCMSC 330 2Babylon• Founded roughly 4000 years ago– Located near the Euphrates River, 56 mi south of Baghdad, Iraq• Historically influential in ancient western world • Cuneiform writing system, written on clay tablets– Some of those tablets survive to this day– Those from Hammurabi dynasty (1800-1600 BC) include mathematical calculations• (Also known for Code of Hammurabi, an early legal code)CMSC 330 3A Babylonian AlgorithmA [rectangular] cistern.The height is 3, 20, and a volume of 27, 46, 40 has been excavated.The length exceeds the width by 50.You should take the reciprocal of the height, 3, 20, obtaining 18.Multiply this by the volume, 27, 46, 40, obtaining 8, 20.Take half of 50 and square it, obtaining 10, 25.Add 8, 20, and you get 8, 30, 25The square root is 2, 55.Make two copies of this, adding [25] to the one and subtracting from the other.You find that 3, 20 [i.e., 3 1/3] is the length and 2, 30 [i.e., 2 1/2] is the width.This is the procedure.– Donald E. Knuth, Ancient Babylonian Algorithms, CACM July 1972The number n, m represents n*(60k) + m*(60k-1) for some kCMSC 330 4More about Algorithms• Euclid’s Algorithm (Alexandria, Egypt, 300 BC)– Appeared in Elements– Computes gcd of two integerslet rec gcd a b =if b = 0 then a else gcd b (a mod b)• Al-Khwarizmi (Baghdad, Iraq, 780-850 AD)– Al-Khwarizmi Concerning the Hindu Art of Reckoning– Translated into Latin (in 12th century?)• Author’s name rendered in Latin as algoritmi• Thus the word algorithmCMSC 330 5The Analytical Engine (Babbage)• Charles Babbage (1791-1871, London, England)– Developed a mechanical calculator, the Difference Engine– Like most developers, was overly eager so during 1830’s developed plans for the Analytical Engine• Never completely finished• But plans only discovered in 1937• Built in 1991 at the Science Museum of London– Included branching, looping, arithmetic, and storage– Programmed using punch cardsCMSC 330 6Alonzo Church (1903-1995)• Mathematician at Princeton Univ.• Three key contributions:– The lambda calculus (lectures in 1936, publ. 1941)– Church’s Thesis• All effective computation is expressed by recursive (decidable) functions– Church’s Theorem• First order logic is undecidableCMSC 330 7Alan Turing (1912 - 1954)• The father of modern computer science– Dissertation work advised by Church at Princeton– Formulated the Turing machine (~1936) (A more general form of abstract computer. We’ve already looked at simpler versions like DFA and PDA)• Σ – A finite alphabet•Q– a set of states•s ∊ Q – A start state•F ⊆ Q – The final states• δ : Q ×Σ→Q ×Σ×{L, R}– If δ(q, a) = (q', a', d), then if we’re in state q and see a on the tape, then replace it by a', move to state q', and move the position of the tape either left or right– A formal definition of a computable algorithmCMSC 330 8Other Early Computers• ABC (1939-1942)– Atanasoff and Berry Computer, at Iowa State Univ.– First electronic digital computer• As decided by a judge in 1973! (Invalidated ENIAC patent)• Z3 (1945)– Konrad Zuse, essentially isolated from everyone else– Used Plankalkül, a sophisticated programming lang.• But no one knew about his results, so not influentialCMSC 330 9Other Early Computers (cont’d)• Harvard Mark I (1944)– Aiken, IBM– Electronic, used relays• ENIAC (1946)– Electronic Numerical Integrator and Computer– Developed by Eckert and Mauchly at UPenn– Electronic, general purposes– Used vacuum tubes– For 30 years considered the “first” electronic computer until court case gave honor to ABC. Supposedly Eckert and Mauchley overheard Atanasoff discussing designs for ABC.CMSC 330 10The First Programming Languages• Early computers could be “programmed” by rewiring them for specific applications– Tedious, error prone• John von Neumann (1903-1957)– Three CS contributions (famous for lots of other stuff)• von Neumann machine – the way computers are built today–A stored program architecture» Program stored in memory as data, so can be modified– (Unclear that he actually invented this...)• “Conditional control transfer” – if and for statements– Allows for reusable code, like subroutines• Merge sort algorithmCMSC 330 11Pseudocodes (Assembly Interpreter)• Short Code (1949)– John Mauchly– Interpreted instructions• E.g., X0 = sqrt(abs(Y0)) becomes 00 X0 03 20 06 Y0–06= abs, 20 = sqrt, 03 = assignment– But needed to translate by hand• A-0 Compiler (1951; Grace Murray Hopper)– Translated symbolic code into machine code• Sounds like an assembler...– Assigned numbers to routines stored on tape• Which would then be retrieved and put in memoryCMSC 330 12FORTRAN (1954 - 1957)• FORmula TRANslator• Developed at IBM by John Backus et al– Aimed at scientific computation– Computers slow, small, unreliable• So FORTRAN needed to produce efficient code• Features (FORTRAN I)– Variable names (up to 6 chars)– Loops and Arithmetic Conditionals• IF (ICOUNT-1) 100, 200, 300– Formatted I/O– SubroutinesCMSC 330 13Writing FORTRAN Programs• Programs originally entered on punch cards– Note bevels on top-left corner for orientation– First five columns for comment mark or statement number– Each column represents one character – Letter: 2 punches: A=12,1 B=12,2 …, Z=0,9CMSC 330 14Punch Card Programming• Not interactive!– Feed the deck into the machine• Or give it to someone to put in– Eventually get back printout with code and output• Could take a couple of hours if machine busy• Student jobs typically took overnight to run (only to find a syntax error!)• Long test-debug cycle– Debugging by hand critical to not wasting time• Don’t want to wait several hours to find you made a typo• What happens if you drop your deck of cards?– Could put sequence number in corner for ordering– Hard to maintain this as you keep modifying programCMSC 330 15Example (FORTRAN 77)C A PROGRAM TO COMPUTE MULTIPLICATION TABLESPROGRAM TABLESDO 20 I = 2,12PRINT *,I,’ TIMES TABLE’DO 10 J = 1,1210 PRINT *,I,’ TIMES’,J,’ IS’,I*J20 CONTINUEENDSource: University of Strathclyde Computer Centre, Glasgow, ScotlandC = “comment”All-capsCols 1-6 forcommentor stmtlabelFor loop; I goes from 2 to 12in increments of 1End of
View Full Document
Unlocking...