CS 4337 Midterm 1 - Concise Review (Ch. 1-4)

Language categories

Natural human, constructed human, programming.

Orthogonality

Few constructs combine consistently with few exceptions.

John Backus

Computer scientist behind Fortran and BNF.

Noam Chomsky

Linguist associated with formal and context-free grammars.

Scientific applications

Fortran; floating-point calculations and arrays.

Business applications

COBOL; reports, decimals, and character data.

AI languages

Lisp (lists) and Prolog (logic).

Systems programming

Efficient, continuously used software; commonly C.

Web software

Markup, scripting, and general-purpose languages.

Embedded system

Computer dedicated to one purpose within a device.

Embedded-system examples

Refrigerator and Fitbit.

Embedded languages and architectures

Java, Python, C; MIPS, ARM, x86.

3D graphics languages in the notes

Java and C.

Game programming

Often C++ or C#; input-driven graphics.

Language evaluation criteria

Readability, writability, reliability, cost.

Readability

Ease of reading and understanding code.

Readability benefits

Easier maintenance.

Multiplicity

Multiple ways to express one operation.

Multiplicity's readability effect

More alternatives can reduce readability.

Special words

Keywords whose design affects readability.

Writability

Ease of expressing programs in a language.

Writability factors

Simplicity, orthogonality, abstraction.

Abstraction

Hiding details behind a simpler interface.

Reliability

Conformance to specifications.

Type checking

Detecting type errors before or during execution.

Exception handling

Catching and responding to runtime errors.

Aliasing

Multiple names or references for one storage location.

Aliasing risk

Changes through one name affect the others.

Strong typing (course definition)

Detects all type errors at compile time or runtime.

Dynamic typing

Type checking occurs at runtime.

Language cost

Total expense of development, execution, and maintenance.

Von Neumann architecture

Instructions and data share memory.

Von Neumann bottleneck

CPU-memory transfer limits execution speed.

Imperative programming

Variables, assignments, and iteration change state.

Imperative language examples

C, C++, Java, Python, JavaScript.

Functional programming

Computing by applying functions; minimizes mutable state.

First-class functions

Functions can be stored, passed, and returned.

Functional programming's foundation

Lambda calculus.

Functional language examples

Lisp, Haskell, Racket, Clojure, ML, F#.

Logic programming

Computation from facts and rules.

Logic language examples

Prolog, ASP, Datalog.

Rule order in logic programming

The implementation selects rule-application order.

Declarative paradigms

Functional and logic programming.

Compilation

Translating source code into machine code.

Pure interpretation

Executing source directly without prior compilation.

Hybrid implementation

Translating to intermediate code, then executing it.

Interpreter

Executes high-level instructions at runtime.

High-level language advantage

Easier program development.

Machine language

CPU-executable instructions; architecture-specific.

Assembly language

Low-level symbolic machine instructions.

Early hardware programming

Machine code; poor readability and writability.

Fortran

First widely used high-level language; scientific computing.

Fortran I target

IBM 704; floating point and index registers.

Fortran II addition

Independent compilation.

Fortran IV addition

Explicit type declarations.

Fortran 77 features

IF-THEN-ELSE and improved loop support.

Fortran 90 features

Modules, arrays, pointers, recursion.

Lisp

Functional pioneer for AI and symbolic list processing.

Lisp memory-management innovation

Garbage collection.

Scheme

Small Lisp dialect supporting functional and procedural styles.

Common Lisp

Unified Lisp dialects for larger applications.

ALGOL 60

Machine-independent foundation for later imperative languages.

ALGOL 60 syntax notation

BNF.

ALGOL's historical contribution

Structured programming; influenced Pascal and C.

COBOL

Business-oriented language with decimal data.

BASIC

Beginner-oriented language designed for timesharing.

PL/I

Combined scientific and business programming.

APL

Dynamically typed, array-oriented language.

SNOBOL

Dynamic string-processing language from Bell Labs.

Simula 67

Introduced classes, objects, inheritance, and coroutines.

Pascal

Designed to teach structured programming.

C's original purpose

UNIX systems programming at Bell Labs.

Prolog

Logic programming based on formal logic.

Ada

DoD language for embedded and real-time systems.

Ada features

Packages and exception handling.

Smalltalk

Pioneering pure object-oriented language.

C++

Combines imperative and object-oriented programming.

C++ designer

Bjarne Stroustrup at Bell Labs.

Java

Portable, C++-influenced object-oriented language.

Java memory management

Garbage collection; no explicit pointer arithmetic.

Scripting language uses

Automation and web programming.

Scripting language examples

Perl, JavaScript, PHP, Python, Ruby.

HTML

Defines web-page structure.

JavaScript

Adds web-page interactivity.

XML

Structures and transports data.

Language definition

Syntax plus semantics.

Syntax

Rules governing program form.

Semantics

Meaning of program constructs.

Formal language

Set of sentences over an alphabet.

Sentence

Terminal-only string belonging to a language.

Lexeme

Smallest meaningful syntactic unit, such as an identifier.

Token

Category of lexemes, such as IDENTIFIER.

Terminal

Grammar symbol that cannot be expanded.

Nonterminal

Symbol representing a syntactic category.

Context-free grammar (CFG)

Rules replace one nonterminal with a symbol sequence.

BNF

Backus-Naur Form; notation for context-free grammars.

BNF nonterminal notation

Angle brackets, e.g., <expression>.

Grammar production

Rule mapping a nonterminal to possible replacements.

Start symbol

Nonterminal where derivation begins.

Derivation

Repeated rule applications from the start symbol.