Programming Language History PDF

제 1 장. 서론  학습목표 프로그래밍언어의 간단한 역사, 추상화, 패러다임, 언어정의 및 번역에 대한 날카로운 시각 함양  PL과 관련된 여러 가지 배경지식에 대해서 정리해 봅시다 PL 왜 공부하나?  Why we study programming languages? – How we communicate influences how we think – How...

제 1 장. 서론  학습목표 프로그래밍언어의 간단한 역사, 추상화, 패러다임, 언어정의 및 번역에 대한 날카로운 시각 함양  PL과 관련된 여러 가지 배경지식에 대해서 정리해 봅시다 PL 왜 공부하나?  Why we study programming languages? – How we communicate influences how we think – How we program computers influences how we think about computation  Basic principles and concepts of PLs are part of the fundamental body of knowledge of computer science – The study of these principles is essential to programmers and computer scientists 2 3 PL의 기원  PL: notation for communicating to computer what we want it to do  Before mid 1940s, computer operators set switches to adjust the internal wiring of a computer to perform the requested tasks 4 PL의 기원  PLs allowed computer users to solve problems without having to reconfigure hardware  Machine Language and the First Stored Programs – John von Neumann: computers should be permanently hardwired with a small set of general-purpose operations, and operators input a series of binary codes into memory to solve more specific problems 5 Machine Language 6 Machine Language  Each line of code has 16 bits (binary digits) – Represents either a single instruction or a single data value  Program execution begins with the first line of code – Code is fetched from memory, decoded (interpreted), and executed  Control then moves to the next line of code and continues until a halt instruction is reached  Opcode: the first 4 bits of a line of code – Indicates the type of operation to be performed  Next 12 bits contain code for the instruction’s operands  Operand codes are either the numbers of machine registers or addresses of other data or instructions in memory  Machine language programming was tedious and error prone 7 Assembly Language (1/3)  Assembly language: a set of mnemonic symbols for instruction codes and memory locations – Example: LD R1, FIRST  Assembler: a program that translates the symbolic assembly language code to binary machine code  Loader: a program that loads the machine code into computer memory  Input devices: – Keypunch machine – Card reader 8 Assembly Language (2/3) 9 Assembly Language (3/3)  Mnemonic symbols were an improvement over binary machine codes but still had shortcomings – Lacks abstraction of conventional mathematical notation – Each type of computer hardware architecture has its own machine language instruction set and requires its own dialect of assembly language  Assembly languages first appeared in the 1950s and are still used today for low-level system tools or for hand-optimization 10 FORTRAN and Algebraic Notation  FORTRAN: FORmula TRANslation language – Developed by John Backus in the early 1950s – Reflected the architecture of a particular type of machine – Lacked the structured control statements and data structures of later high-level languages  Popular with scientists and engineers for its support for algebraic notation and floating-point numbers 11 The ALGOL Family (1/2)  ALGOL: ALGOrithmic Language released in 1960 – Provided a standard notation for computer scientists to publish algorithms in journals – Included structured control statements for sequencing (begin-end blocks), loops (for loop), and selection (if and if-else statements) – Supported different numeric types – Introduced the array structure – Supported procedures, including recursive procedures  ALGOL achieved machine independence with the requirement for an ALGOL compiler with each type of hardware  Compiler: translates programming language statements into machine code 12 The ALGOL Family (2/2)  ALGOL was the first language to receive a formal specification or definition – Included a grammar that defined its features for both programmers and for compiler writers  Large number of high-level languages descended from ALGOL, including: – Pascal: language for teaching programming in the 1970s – Ada: for embedded applications of US Dept. of Defense 13 Computation without von Neumann Architecture (1/2)  High-level languages still echoed the underlying architecture of the von Neumann model of a machine – Memory area for programs and data are stored – Separate CPU that sequentially executes instructions fetched from memory  Progress in language abstraction and hardware performance ran into separate roadblocks: – Hardware began to reach the limits of improvements predicted by Moore’s Law, leading to the multi-core approach – Single-processor model of computation cannot be easily mapped into new architecture of multiple CPUs executing in parallel – Large programs were difficult to debug and correct 14 Computation without von Neumann Architecture (2/2)  Solution: languages need not be based on a particular model of hardware but need only to support models of computation suitable for styles of problem solving  Lambda calculus: computational model developed by mathematician Alonzo Church – Based on the theory of recursive functions  Lisp: programming language that uses the functional model of computation  Other languages modeled on non-von Neumann models of computing that lend themselves to parallel processing include: – A formal logic model with automatic theorem proving – A model involving the interaction of objects via message passing 15 Abstractions for Human Readability  Two aspects of the abstraction process – Hiding the details – Showing the important parts  Two types of PL abstractions – Data abstraction: simplify behavior and attributes of data for humans (ex: numbers, character strings, search trees) – Control abstraction: simplify properties of the transfer of control (ex: loops, conditional statements, procedure calls)  Abstraction levels (amount of information contained or hidden) – Basic abstraction: collect the most localized machine information – Structured abstraction: collect intermediate information about the structure of a program – Unit abstraction: collect large-scale information in a program 16 Data: Basic Abstraction  Basic data abstraction: hides internal representation of data values – Variables: use of symbolic names to hide computer memory locations containing data values – Data types: names given to kinds of data values – Declaration: process of giving a variable a name and a data type – ex) Standard mathematical operations, such as addition and multiplication 17 Data: Structured Abstraction  Data structure: collects related data values into a single unit – Hides component parts but can be constructed from parts, and parts can be accessed and modified – ex 1) Employee record contains name, address, phone, salary (different data types) – ex 2) Array: sequence of individually indexed items with the same data type – ex 3) Text file: a sequence of characters for transfer to and from an external storage device 18 Data: Unit Abstraction  Unit abstraction: often associated with abstract data type – A set of data values and the operations on those values  Separates the interface from the implementation – Interface: set of operations available to the user – Implementation: internal representation of values and operations  Examples: – Module in ML, Haskell, and Python – Package in Lisp, Ada, and Java – Class mechanism in object-oriented languages  Unit abstraction also provides reusability – Typically, components are entered into a library and become the basis for library mechanisms – Interoperability allows combination of units  API: gives information about the resource’s components 19 Control: Basic Abstraction  Basic control abstraction: statements that combine a few machine instructions into an abstract statement that is easier to understand  Syntactic sugar: a mechanism that allows you to replace a complex notation with a simpler, shorthand notation – ex) x += 10 instead of x = x + 10 20 Control: Structured Abstraction  Structured control abstraction: divide a program into groups of instructions nested within tests that govern their execution – Help to express the logic of primary control structures of sequencing, selection, and iteration  ex: branch instructions, iterator, procedure, runtime environment, function, recursion, higher-order functions 21 Control: Unit Abstraction  Unit: a stand-alone collection of procedures providing logically related services to other parts of a program – Allows a program to be understood as a whole without needing to know the details of the services provided by the unit  Thread: separately executed control paths within the Java system  Process: other programs executing outside the Java system  Task: mechanism in Ada for parallel execution 22 Programming Paradigms  Imperative paradigm: a language with three properties – Sequence of statements that represent commands – Use of variables representing memory locations – Use of assignment to change the values of variables – von Neumann bottleneck  Functional paradigm – based on the abstract notion of functions in lambda calculus  Logic paradigm – based on symbolic logic in mathematical deduction – Both function and logic make it easier to determine if a program will execute correctly  Object-oriented paradigm – Reusable code that operates in a way to mimic behaviors of real- world objects 23 Imperative Programming Example function gcd (u, v: in integer) return integer is y, t, z: integer; begin z := u; y := v; loop exit when y = 0; t := y; y := z mod y; z := t; end loop; return z; end gcd; 24 OO Programming Example (1/2) import java.io.*; 메모리 할당 및 초기화 constructor class IntWithGcd { public IntWithGcd( int val ) { value = val; } public int getValue() { return value; } access method public int gcd ( int v ) gcd method { int z = value; int y = v; while ( y != 0 ) { int t = y; y = z % y; z = t; } return z; } private int value; field } encapsulation & information hiding 25 OO Programming Example (2/2) class GcdProg { public static void main (String args[]) { System.out.println("Input two integers:"); BufferedReader in = new BufferedReader( new InputStreamReader(System.in)); try { IntWithGcd x = new IntWithGcd(Integer.parseInt(in.readLine())); int y = Integer.parseInt(in.readLine()); System.out.print("The gcd of " + x.getValue() + " and " + y + " is "); System.out.println(x.gcd(y)); } catch ( Exception e ) { System.out.println(e); System.exit(1); } } } 26 Functional Programming  A computation is an evaluation of functions – applicative languages  Functional languages – value-oriented – neither variables nor assignments are allowed – no loops because control variables cannot be defined  Theoretical property from recursive function theory Turing completeness can be achieved from: – integer values – arithmetic functions – a mechanism for defining new functions using existing functions, selections, and recursions 27 Functional Programming Example (define (gcd u v) (if (= v 0) u function gcd (gcd v (modulo u v)))) (define (euclid) ; sequential! (display "enter two integers:") (newline) ; goes to next line on screen (let ((u (read)) (v (read))) (display "the gcd of ") (display u) gcd driver (display " and ") (display v) (display " is ") (display (gcd u v)) (newline))) 28 Logic Programming  A computation is a proof – declarative languages  Logic languages – a program consists of a set of assertion which are to be true – the underlying system determines the control flow – very-high-level languages 29 Logic Programming Example gcd(U, V, U) :- V = 0. gcd(U, V, X) :- not(V = 0), Y is U mod V, gcd(V, Y, X). 30 Language Definition  Formal language definition provides benefits: – Helps to allow you to reason mathematically about programs – Promotes standardization for machine or implementation independence – Defines program behavior and interaction – Ensures discipline when a language is designed  A language is defined by – syntax: structure of a program – semantics: meaning (execution) of a program 31 Language Defining Methods  Syntax definition – Tokens: the language’s words Includes keywords, identifiers, symbols for operations, special punctuation symbols, etc. – Lexical structure: structure of the language’s words Similar to spelling in natural languages Regular expression – Context-free grammar ::= if () [else ]  Semantics definition – Difficult to provide a comprehensive description of meaning in all contexts – Formal methods operational, denotational and axiomatic semantics  No generally accepted formal method 32 Language Translator  Language translator – accepts a program in a language and executes it – also called a language processor  Two types of language translators – Interpreter: executes a program directly – Compiler: produces an equivalent program in a form suitable for execution – pseudo-interpreter (hybrid translator) 33 Interpreter Source Code input INTERPRETER output 34 Compiler Source Target COMPILER Code Code further translation (assembler or linker) Executable Code processor input output (real machine) 35 Pseudo-Interpreter Source Intermediate COMPILER Code Code INTERPRETER input output (virtual machine) 36 Error Handling  Kinds of Errors – syntax errors: the program is not well-formed – semantic errors static semantic errors: detected during compilation time (say, incompatible types) dynamic semantic errors: detected during run-time (say, division-by-zero) – logic errors: only the programmer knows this kind of errors  Most translators support some kinds of debugging tools 37 Sample Errors (Java) public int gcd ( int v# )  lexical error { int z = value  syntax error: missing ; y = v;  static semantic error: y undefined while ( y >= 0 )  dynamic semantic: division by zero { int t = y; y = z % y; z = t; } return y;  logic error: should return t } 38 Future of PLs  In the 1960s, computer scientists wanted a single universal programming language to meet all needs  In the late 1970s and early 1980s, they wanted specification languages that would allow users to define the needs and then generate the system – This is what logic programming languages attempt to do  Programming has not become obsolete – New languages will arise to support new technologies that arise  Relative popularity of programming languages since 2000, based on number of posts on newsgroups: 39 Future of PLs 40 Discussion Topics  What are some of the benefits of formally defining a programming language? Is it possible to mathematically prove the behavior of a program?  Do you think that programming will eventually become obsolete? Will artificial intelligence lead to its demise? Why or why not? 41 Exercises 추천  1.4: abstraction에 대한 이해  1.8: programming paradigm에 대한 이해  1.19: programming error에 대한 이해 42