Early Programming Languages and Implementation Methods
FORTRAN
FORTRAN: FORmula TRANslation; scientific computing (arrays, loops, floats); Ideas – compiled code for speed; DO loop; subprograms; formatted I/O. Legacy: foundation of scientific programming.
ALGOL 60
ALGOL 60: ALGOrithmic Language; first machine-independent language; Introduced: block structure, recursion, BNF, format types, compound statements (begin…end); Legacy: basis for imperative languages.
COBOL
COBOL: COmmon Business-Oriented Language; business/data processing; English-like syntax, records, hierarchical data, nested selection, macro facility. Legacy: dominated business apps; still used today.
PL/I
PL/I: designed to unify scientific and business use; combined ALGOL’s structure, FORTRAN’s computation, COBOL’s I/O; Added: exceptions, pointers, array sections; Legacy: inspired later languages, but was large and complex.
ALGOL 68
ALGOL 68: orthogonal design: few simple primitives and powerful combination rules; Introduced: user-defined data types, references, and dynamic arrays; Legacy: influenced Pascal, C, and Ada; difficult to implement.
Compilation Implementation Method
Compilation Implementation Method: programs are translated into machine language (including JIT systems); Use: large commercial applications.
Pure Implementation Method (Interpretation)
Pure Implementation Method: programs are interpreted by another program known as an interpreter; one instruction at a time is processed. Use: small programs or when efficiency is not an issue; slow execution, requires more space.
Hybrid Implementation Method
Hybrid Implementation Method: compromise between compilation and pure implementation methods. Use: small/medium systems when efficiency is not the first concern. Perl programs are partially compiled to detect errors before interpretation. Initial implementations of Java were hybrid; the intermediate form (byte code) provides portability to any machine that has a byte-code interpreter and a runtime system (together, these are called the Java Virtual Machine).
JIT Method
JIT Method: translate programs into an intermediate language; compile intermediate language of subprograms into machine code. Use: Java platform.
Reliability vs. Cost of Execution
Reliability versus Cost of Execution: Java demands references to array elements be checked for proper indexing: this leads to higher execution costs.
Readability vs. Writability
Readability versus Writability: APL has powerful operators and symbols, allowing complex operations to be written compactly, which leads to low readability.
Writability vs. Reliability
Writability versus Reliability: C++ pointers are powerful and flexible, but also unreliable.
Von Neumann Architecture
Languages were designed based on the Von Neumann architecture – data and programs stored in memory; memory is separate from CPU; instructions and data are pipelined from memory to CPU.
Von Neumann Bottleneck
Von Neumann Bottleneck: connection speed between a computer’s memory and its processor – determines computer speed {Connection Speed = bottleneck}.
Programming Paradigms
Imperative: variables, assignment statements and iteration {Java, C, C++}.
Functional: main means of computation is by applying mathematical functions (Racket).
Logic: rule-based (Prolog). Markup: extended to support some programming (JSTL, XSLT).
Lexical Analyzer
Lexical Analyzer: collects characters into lexemes and identifies tokens.
- Lowest-level syntax analysis (detects syntactical errors).
- Pattern Matcher: attempts to find substrings that match specific patterns in an input string (lexemes).
- Each call to a lexical analyzer returns a single lexeme and its token.
- Skip comments and white space outside lexemes; insert lexemes for user-defined constructs.
- Insert lexemes for user-defined names in the symbol table.
EBNF to BNF Conversion
EBNF -> BNF: 1. Optional parts in []. 2. Alternative parts in (). 3. {} – indicates that the enclosed part can be repeated indefinitely or left out altogether.
Precedence and Associativity
Precedence: lower in a parse tree means higher precedence.
Associativity: Left – <expr> -> <expr> + const | const; Right – <expr> -> const + <expr> | const.
Functional Programming
Functional Programming: no variables; recursion over iteration; lambda functions; higher-order functions: one that either takes functions as parameters or yields a function as a result.
f o g or apply-to-all
Tail Recursion
Tail Recursion: a recursive call that is the last operation in a function.