4337 Midterm Guide Questions

What are 6 reasons for studying concepts of programming languages?

• Increased capacity to express ideas

• Improved background for choosing appropriate languages

• Increased ability to learn new languages

• Better understanding of the significance of implementation

• Better use of languages that are already known

• Overall advancement of computing

What are 5 (non-exhaustive) programming domains?

• Scientific Application

• Business Application

• Artificial Intelligence

• Systems Programming

• Web Software

What are the language criteria for readability?

• Orthogonality

• Simplicity

• Syntax Design

• Data Types

What are the language criteria for writability?

• Orthogonality

• Simplicity

• Syntax Design

• Data Types

• Expressivity

• Support for Abstraction

What are the language criteria for reliability?

• Orthogonality

• Simplicity

• Syntax Design

• Data Types

• Expressivity

• Support for Abstraction

• Exception Handling

• Restricted Aliasing

• Type Checking

What is von Neumann architecture?

The design model that almost all modern computers, nearly 50 years later, are based on. Proposed by John von Neumann in the 1940s. Languages applying this architecture are called Imperative programming languages.

What is the fetch-execute cycle?

The execution of a machine code program on a von Neumann architecture computer occurs in a process called the _.

What is the structured programming design methodology?

• Movement to stop using GOTOs and instead write organized code

• Occurred in the late 1960s to early 1970s

• Two primary deficiencies found: incompleteness of type checking and inadequacy of control statements (too many GOTOs)

• Introduction of top down design and step-wise refinement

What is the procedure-oriented programming design methodology?

• Code started being organized around functions/processes; introduced usage of functions

• Occurred in the 1970s to early 1980s

• Data and procedures were separated

What is the data-oriented software development programming design methodology?

• Shifted the focus from procedures/functions to building code around data structures

• Late 1970s to current

• Emphasis on abstract data types

• Limitedly supported by SIMULA 67

What is object-oriented design?

• Subset of data-oriented software development methodology.

• Modern

• Starts from data abstraction and adds three key items: encapsulation, inheritance dynamic method binding

• First implemented fully by Smalltalk

What is encapsulation?

Bundling data and the procedures that operate on it together

What is inheritance?

Allowing new classes to reuse existing ones, increasing productivity

What is dynamic method binding?

The method to call is decided at runtime, not compile time.

What are imperative languages?

Languages with variables, assignment, iterations. Modeled on von Neumann architecture. State exactly now to solve a problem, step by step. Examples: C, C++, Python, Java

What are functional languages?

Programming languages that use computation by applying functions; functions are first class citizens. Examples: LISP, Haskell, Racket, Scheme

What are logic languages?

Languages that are rule-based, no specified order given, implementation chooses the execution order. Given the rules, the program is them to figure out how to execute further. Example: Prolog

What are mark-up/hybrid programming languages?

Kark-up extended with programming (shouldn’t need to know, hopefully). Examples: JSTL, XXTL, HTML, XML

What are scripting languages?

Languages that are a subset of imperative languages and grouped together because of their interpretation-based implementation. Examples: Perl, JavaScript, Ruby

Three examples of language design trade-offs

Reliability vs. Execution cost: Java checks array indexes which makes it more reliable but it is slower, C skips index checking making it faster but less reliable.

Readability vs. writability: APL has powerful array operators making it very writable, but the programs are unreadable, McCraken took 4 hours to read 4 lines

Writability vs. reliability: C++ pointers are flexible and powerful meaning they are writable, but pointers cause reliability issues, Java removed pointers for reliability.

What are the three general methods of implementation?

Compilation implementation, pure interpretation implementation, and hybrid implementation

What is compilation implementation?

Source code is entirely translated to machine code before execution. Runs directly on hardware, slow translation, fast execution. Examples: C, C++, Fortran

What is pure interpretation implementation?

Source code is never translated into machine code, and the interpreter reads and executes at runtime. Fast to start, slow to execute. Easier to debug because runtime errors show up immediately, common for webscripting languages. Examples: early Javascript, early Python, PHP

What is hybrid implementation?

Source code is compiled into an intermediate form which is byte code (most cases), faster than pure interpretation, but more portable than compilation. Examples: Java and Perl

What was Charles Babbage’s main contribution to Computer Science?

Designed the Analytical Engine (1842)

What was Ada Lovelace’s main contribution to Computer Science?

Considered the first programmer; wrote the first program (1843), designed to run on Babbage’s Analytical Engine. Computed the Bernoulli numbers

What was Alan Turing’s main contribution to Computer Science?

Developed the Turing machine, the theoretical foundation of computation. Broke the Enigma code in WWII, considered the father of computer science

What was Grace Hopper’s main contribution to Computer Science?

Led the development of A-0, A-1, A-2 compiling systems at UNIVAC from 1951-1953. Developed FLOW-MATIC

What was John von Neumann’s main contribution to Computer Science?

Proposed the von Neumann architecture in the 1940s, basis for almost all modern computers in the past 50 years, led directly to imperative programming languages

What was John Backus’s main contribution to Computer Science?

Led development of Fortran, the first successful high-level language, at IBM (1954). Invented BNF (Backus-Naur Form), the formal notation used to describe programming language syntax

What was Donald Knuth’s main contribution to Computer Science?

Developed Big-O notation as used today and made foundational contributions to algorithm analysis and complexity theory

What was Brian Kernighan and Dennis Ritche’s main contribution to Computer Science?

Wrote The C Programming Language”, the definitive book on C, together, developed C programming language (Ritchie mainly), and later Unix together (written in C)

What is Plankalkül?

First high-level language ever Konrad Zuse, Germany, 1945. Never implemented in original form. Had advanced features: floating point, arrays, records. Not published until 1972. 

What is Pseudocode/speedcoding?

Early 1950s IBM systems, precursor to real high-level languages, ex. Grace Hopper’s A-0, A-1, A-2

What are IBM 704 and Fortran?

Hardware that prompted Fortran's development, Fortran = Formula Translation John Backus at IBM, First successful high-level language for scientific applications, Large numbers of floating point computations, use of arrays, Introduced: symbolic notation, subroutines, formatted I/O

What is LISP?

This is the first functional programming language, developed by John McCarthy at MIT in 1958 for artificial intelligence and list processing. It introduced garbage collection, recursion as primary control, and dynamic typing. It is an ancestor of Scheme, Racket, Haskell, and Common LISP.

What is Prolog?

A logic programming language made by Colmerauer, Roussel, and Kowalski in 1972. It is rule-based, a database of facts and rules, used in AI research, and has no specified execution orde

What is Java?

This programming language was invented by James Gosling at Sun Microsystems in 1995. It was influenced by C++ and Smalltalk, is portable across platforms, and uses a hybrid implementation (compiles to bytecode and runs on JVM). It is widely used for both web and general purpose programming.

What is C?

This programming language was invented by Dennis Ritchie at Bell Labs in 1972. It is the basis for UNIX, a systems programming language, and allows for fast, low level control in exchange for low reliability.

What is C++?

This programming language was developed by Bjarne Stroustrup at Bell Labs in 1983. It added object oriented features to its prefixed language.

What is Perl?

This programming language is a scripting language developed by Larry Wall in 1987. It uses hashes as a core data structure and influenced the array structure of PHP

What is Python?

This programming language was developed by Guido van Rossum in 1991. It uses lists, dictionaries, and tuples instead of arrays. It is known for its readability and simplicity.

What is Ruby?

This programming language was developed by Yukihiro Matsumoto in 1995. It is a pure object oriented language. It was influenced by Smalltalk, Perl, and Python, and is an imperative scripting language.

What is Ada?

This programming language was developed by Jean Ichback in 1983 and was commissioned by the US DoD (Department of Defense). It was influenced by Pascal. It was designed with very strong type checking and program correctness in mind, and meant for embedded and real-time systems

What is Cobol?

This programming language was developed in 1959, with Grace Hopper at the lead. It is the first successful high-level language for business applications. It is based on FLOW-MATIC. It produces reports, and uses decimal numbers and characters.

What is SNOBOL?

This programming language was created in Bell Labs in 1962, designed specifically for string processing and pattern matching.

What is Pascal?

This programming language was developed in 1970 by Niklaus Wirth. It was influenced by ALGOL 60. It influenced Ada and Modula.

What is Smalltalk?

This programming language was developed by Alan Kay in 1972. It is the first fully object-oriented language. It influenced Java, Ruby, Python, and Objective-C.

What is Scheme?

This programming language was developed in 1975 at MIT by Guy Steele and Gerald Sussman. It is a clean, minimalist dialect of LISP used heavily in education. It introduced lexical scoping, and directly influenced Racket.

What is Racket?

This programming language was developed by Matthias Felleisen and his team in 1994. It is a descendant of Scheme.

What is Haskell?

This programming language was developed in 1990 and named after Haskell Curry after design by a committee. It is a purely functional language that computes values only when needed (lazy). It was influenced by Miranda and ML (meta language)

What is a Language?

Characterized by a potentially infinite set of all valid statements (strings) within itself

What is a grammar?

A formal description of a language which must have a finite set of rules

What is syntax?

A formal method to describe how to determine a statement’s membership in a language

What are the two approaches to describing Syntax?

Language Recognizers and Language Generators

What is a language recognizer?

This is used to check a string; take an input and determine if it belongs to a language or not, if it is valid or not; essentially what a parser does (verify syntactic validity)

What is a language generator?

This is used to produce valid strings for a language, from a start symbol until only terminals remain.

BNF (Backus-Naur Form)

A formal notation for describing the syntax of a programming language using rules, nonterminals, and terminals

Terminal

A symbol that appears in the final string and cannot be expanded further — actual tokens like id, +, (, )

Nonterminal

A symbol that represents a grammatical category and must be expanded into other symbols — written in angle brackets like <expr>

Derivation

The process of expanding a start symbol by applying grammar rules until only terminals remain

Leftmost Derivation

A derivation where the leftmost nonterminal is always expanded first — determines the ORDER nodes are built in a parse tree, does NOT affect the shape

Rightmost derivation

A derivation where the rightmost nonterminal is always expanded first — used by LR/bottom-up parsers

Left recursion

A grammar rule where the nonterminal on the LHS appears at the beginning of the RHS — determines the SHAPE of the parse tree, causes infinite loop in top-down parsers

Right recursion

A grammar rule where the nonterminal on the LHS appears at the end of the RHS — used by LL parsers after left recursion is removed

Sentential Form

Any string of terminals and nonterminals derivable from the start symbol — every intermediate step in a derivation is a sentential form

Right Sentential Form

A sentential form produced by a rightmost derivation — what LR parsers work with in reverse

Parse Tree

A hierarchical tree structure that visualizes a derivation — nonterminals are interior nodes, terminals are leaf nodes

Ambiguity

A grammar is ambiguous if a single string can produce two or more distinct parse trees using the same grammar rules

Operator Precedence

Defined in BNF by tree depth — operators lower in the parse tree have higher precedence (e.g. multiplication is lower than addition)

Left Associative

An operator that groups left to right — implemented using left recursion in BNF (e.g. a + b + c = (a + b) + c)

Right Associative

An operator that groups right to left — implemented using right recursion in BNF (e.g. a = b = c means a = (b = c))

EBNF (Extended BNF)

An extension of BNF using additional symbols: {} for zero or more, [] for optional, | for alternatives

Attribute Grammar

A CFG extended with semantic functions and predicate functions — also called static semantics — used to enforce rules BNF cannot express

Static Semantics

Rules checked at compile time that are too complex for BNF — implemented using attribute grammars — primary use is enforcing type compatibility

Synthesized Attribute

An attribute whose value is computed from the values of a node's children — flows UP the parse tree

Inherited Attribute

An attribute whose value is passed down from a node's parent or siblings — flows DOWN the parse tree

Semantic Function

A rule in an attribute grammar that computes the value of an attribute

Predicate Function

A rule in an attribute grammar that checks a constraint — returns true or false — used to enforce type compatibility

Type Compatibility

The primary use of attribute grammars — checks that types on both sides of an operation or assignment are compatible

Dynamic Semantics

Describes what a program means when it actually executes — three approaches: operational, denotational, axiomatic

Operational Semantics

Defines meaning by how a program executes on an abstract machine

Denotational Semantics

Defines meaning by mapping program constructs to mathematical objects — based on recursive function theory

Axiomatic Semantics

Defines meaning using logical assertions about what is true before and after execution — basis for weakest preconditions — based on formal logic

Weakest Precondition

The least restrictive condition that must be true before a statement executes to guarantee the postcondition holds afterward — computed by substituting the RHS of an assignment into the postcondition

Lexical Analysis

The first phase of compilation — reads source code and converts characters into tokens (lexical units)

Token

A meaningful unit produced by lexical analysis — e.g. identifier, operator, integer literal

Syntax Analysis

The second phase of compilation — takes tokens from lexical analysis and builds parse trees — has two goals: find errors and produce parse tree

Three Reasons Lexical Analysis is Separate

Simplicity, efficiency, portability

Top-Down Parser (LL)

Builds parse tree from root to leaves — reads left to right, uses leftmost derivation — cannot handle left recursion

Bottom-Up Parser (LR)

Builds parse tree from leaves to root — reads left to right, uses rightmost derivation in reverse — can handle left recursion

LL Parser

Left to right scan, Leftmost derivation — top-down — requires left recursion to be removed

LD Parser

Left to right scan, Rightmost derivation — bottom-up — handles left recursion — shift-reduce is an LR parser

Three Advantages of LR Parsers

1) Works for all programming languages

2) Detects syntax errors as soon as possible

3) LR class is a proper superset of LL — handles grammars LL cannot

Direct Left Recursion

A rule that directly references itself on the left — A → Aα — causes infinite loop in top-down parsers — can be removed using the textbook algorithm

Indirect Left Recursion

A rule that references itself through other rules — A → B... and B → A... — detected using pairwise disjointness test

Pairwise Disjointness Test

A test to determine if a grammar is suitable for top-down parsing — compute FIRST() for each RHS of a rule, check that no two FIRST sets share a terminal

FIRST()

A function that returns the set of terminals that a RHS rule can begin with — argument must be a RHS rule — return value is a set of terminals enclosed in {}

Handle

The RHS substring on the parse stack that matches a grammar rule and should be reduced right now

Shift

A shift-reduce parser action — push the next input token onto the stack