Early legal code babylonian algorithma rectangular cistern height

CMSC 330: Organization of Programming Languages

A Brief History of Programming Languages

• Historically influential in ancient western world

• Cuneiform writing system, written on clay tablets

A Babylonian Algorithm

A [rectangular] cistern.

Take half of 50 and square it, obtaining 10, 25.

Add 8, 20, and you get 8, 30, 25
The square root is 2, 55.

More About Algorithms

• Euclid’s Algorithm (Alexandria, Egypt, 300 BC) – Appeared in Elements
• Sel – Computes gcd of two integers
let rec gcd a b =
if b = 0 then a else gcd b (a mod b)

– But no one knew what it was until much later!

• Estimated construction in 150-100 BC

– Partially built a Difference Engine

§ A mechanical calculator for computing polynomials

The Analytical Engine (1837)

• Babbage described plans for an Analytical Engine– Digital, programmable using punch cards
– Included branching, looping, arithmetic, and storage– Memory would store 1000 numbers w/ 500 digits each– Language similar to assembly language
– Powered by steam engine

– Corresponded with Babbage from 1833 onward
– In 1843, translated Italian mathematician L. Menabrea's memoir on Babbages proposed Analytical Engine – Appended notes on how to program the Analytical Engine to calculate Bernoulli numbers
– Recognized by historians as 1stpublished program– Making her worlds 1stprogrammer

• 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 undecidable

– Dissertation work advised by Church at Princeton– Formulated the Turing machine (~1936)
A general abstract computer → DFA + infinite 1D tape
•Σ – 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 algorithm

• But no one knew about his results, so not influential

• Harvard Mark I (1944)
– Aiken, IBM
– Electronic, used relays

ENIAC early photo

• Early computers could be programmedby 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

		Eckert and Mauchly

– 06 = abs, 20 = sqrt, 03 = assignment– But needed to translate by hand

Punch Card Programming

FORTRAN Parsing Example

• Blanks dont matter in FORTRAN
– And identifiers can have numbers in them
• Consider parsing the following two statements