Midterm Ready Flashcards
What are the reasons for studying concepts of programming languages?
Increased ability to express ideas, Improved background for choosing appropriate languages, Increased ability to learn new languages, Better understanding of significance of implementation, Better use of languages that are already known, Overall advancement of computing
Name a programming language commonly used for scientific applications.
Fortran
Which language is primarily used for business applications?
COBOL
What is the main focus of artificial intelligence programming languages?
Symbols rather than numbers manipulated; use of linked lists
Identify a programming language used in systems programming.
C
What are the categories of programming languages?
Imperative, Functional, Logic, Markup/programming hybrid
List the evaluation criteria for programming languages.
- Readability
- Writability
- Reliability
- Cost
Define readability in the context of programming languages.
The ease with which programs can be read and understood
What does writability refer to in programming languages?
The ease with which a language can be used to create programs
What is meant by reliability in programming languages?
Conformance to specifications (i.e., performs to its specifications)
What is the ultimate total cost in programming languages?
Cost
Fill in the blank: The ease with which programs can be moved from one implementation to another is called _______.
Portability
What is the influence of computer architecture on programming languages?
Languages are developed around the prevalent computer architecture, known as the von Neumann architecture
What are the components of the fetch-execute cycle in the von Neumann architecture?
- Initialize the program counter
- Fetch the instruction pointed by the counter
- Increment the counter
- Decode the instruction
- Execute the instruction
What did programming methodologies evolve from in the 1950s and early 1960s?
Simple applications; worry about machine efficiency
What is a characteristic of imperative programming languages?
Central features are variables, assignment statements, and iteration
True or False: Functional programming languages compute by applying functions to given parameters.
True
What is the main purpose of hybrid implementation systems?
A compromise between compilers and pure interpreters
Define the term ‘compilation’ in programming.
Translate high-level program (source language) into machine code (machine language)
What are the phases of the compilation process?
- Lexical analysis
- Syntax analysis
- Semantics analysis
- Code generation
What is the von Neumann bottleneck?
The connection speed between a computer’s memory and its processor determines the speed of a computer
What is the main disadvantage of pure interpretation?
Slower execution (10 to 100 times slower than compiled programs)
What does the term ‘load module’ refer to?
The user and system code together
What is the purpose of linking and loading in programming?
The process of collecting system program units and linking them to a user program
What is one advantage of hybrid implementation systems?
Faster than pure interpretation
What is a key characteristic of programming languages that allows easy interpretation?
Faster than pure interpretation
This characteristic is crucial for efficient programming and debugging.
What is the purpose of partially compiling Perl programs?
To detect errors before interpretation
This helps in identifying issues early in the development process.
What is byte code in Java?
An intermediate form that provides portability to any machine with a byte code interpreter and a run-time system
This is executed by the Java Virtual Machine (JVM).
What does JIT stand for in programming?
Just-in-Time Implementation Systems
JIT systems compile intermediate language to machine code during execution.
What is the primary function of preprocessors in programming?
To expand embedded preprocessor macros
Examples include #include and #define in C preprocessor.
What is an example of a programming environment that is a collection of tools used in software development?
Microsoft Visual Studio.NET
This environment supports building both Web and non-Web applications.
What are the most important criteria for evaluating programming languages?
- Readability
- Writability
- Reliability
- Cost
These criteria help in choosing the right programming language for a task.
What are the major methods of implementing programming languages?
- Compilation
- Pure interpretation
- Hybrid implementation
Each method has its own advantages and disadvantages.
True or False: Zuse’s Plankalkül was designed in 1945 and published in 1972.
True
It was never implemented but introduced advanced data structures.
What was the main issue with using machine code?
- Poor readability
- Poor modifiability
- Tedious expression coding
- No indexing or floating point
These limitations led to the development of higher-level programming languages.
What was Speedcoding developed for?
IBM 701
It introduced pseudo ops for arithmetic and math functions.
What was a significant feature of Fortran I?
User-defined subprograms
This allowed programmers to create reusable code.
What is the significance of Fortran IV?
Introduced independent compilation and fixed bugs from earlier versions
It was a major step forward in the evolution of Fortran.
What programming paradigm does Lisp primarily follow?
Functional Programming
Lisp was designed for AI research and emphasizes processing data in lists.
What is a defining feature of Common Lisp?
An effort to combine features of several dialects of Lisp into a single language
It is known for its complexity and large feature set.
What programming language was developed at MIT in the mid-1970s and is known for its simple syntax?
Scheme
It is often used for educational applications due to its small size.
What programming feature was introduced in Fortran 90?
- Modules
- Dynamic arrays
- Pointers
- Recursion
- CASE statement
- Parameter type checking
These features significantly modernized the Fortran language.
What does the acronym AI stand for in the context of programming languages?
Artificial Intelligence
Lisp was specifically designed to facilitate AI research.
What programming paradigm allows functions to be treated as first-class entities?
Functions as first-class entities
This allows functions to be passed as arguments, returned from other functions, and assigned to variables.
What is a key feature of Common Lisp?
An effort to combine features of several dialects of Lisp into a single language
Common Lisp is large, complex, and used in industry for large applications.
What was ALGOL 60 designed to achieve?
To design a universal language for communicating algorithms
It was a response to the lack of portable languages that were machine-independent.
What were the goals of the early design process for ALGOL?
Close to mathematical notation, good for describing algorithms, translatable to machine code
These goals were set during the ACM and GAMM meeting in 1958.
What significant concept was formalized in ALGOL 58?
The concept of type
This included features like names of any length and arrays with multiple subscripts.
What was a major limitation of ALGOL 60?
Lack of I/O and string handling
This contributed to its limited adoption despite its theoretical strengths.
What was COBOL’s historical background based on?
FLOW-MATIC
COBOL features embedded hyphens in names and English names for arithmetic operators.
What were the design goals of COBOL?
Must look like simple English, easy to use, broaden the base of computer users
These goals were established during the first design meeting in May 1959.
What was a significant contribution of COBOL?
First macro facility in a high-level language
It also introduced hierarchical data structures and separate data division.
What is a characteristic of PL/I?
Designed to handle both scientific and business computing
It originated from the need for a single language that could address both types of applications.
What did APL emphasize in its design?
Highly expressive with many operators for scalars and arrays
It was initially designed as a hardware description language.
What are the primary contributions of SIMULA 67?
Coroutines, classes, objects, and inheritance
It was primarily designed for system simulation.
What was ALGOL 68 known for?
User-defined data structures and reference types
It introduced dynamic arrays called flex arrays.
What was Pascal primarily designed for?
Teaching structured programming
It became the most widely used language for teaching programming from the mid-1970s to late 1990s.
What is a defining feature of C?
Designed for systems programming with powerful operators but poor type checking
Initially spread through UNIX and has been used in many application areas.
What is Prolog based on?
Formal logic
It is a non-procedural language and operates as an intelligent database system.
What were the design goals of the Basic programming language?
Easy to learn and use for non-science students, pleasant and friendly interface
It was the first widely used language with time-sharing capabilities.
What was a major concern regarding PL/I?
Many new features were poorly designed, too large and complex
These concerns limited its effectiveness and adoption.
What is a characteristic of dynamic languages like APL and SNOBOL?
Dynamic typing and dynamic storage allocation
Variables acquire a type when assigned a value, and storage is allocated at that time.
What type of logic is the intelligent database system based on?
Formal logic
The system uses an inferencing process to infer the truth of given queries.
Who is Ada named after?
Augusta Ada Byron
She is recognized as the first programmer.
What was the sequence of requirements for Ada’s design?
Strawman, Woodman, Tinman, Ironman, Steelman
This design effort took about eight years and involved hundreds of people.
What are some contributions of Ada?
- Packages for data abstraction
- Exception handling
- Generic program units
- Concurrency through tasking model
What significant feature was introduced in Ada 95?
Support for OOP through type derivation
It also included better control mechanisms for shared data and new concurrency features.
What is the main reason for Ada’s decline in popularity?
The DoD no longer requires its use and the popularity of C++
Who developed Smalltalk?
Alan Kay initially, later by Adele Goldberg
Smalltalk is known for being the first full implementation of an object-oriented language.
What does C++ combine?
Imperative and Object-Oriented Programming
It evolved from C and SIMULA 67.
What is the ANSI standard approval date for C++?
November 1997
What is Swift a replacement for?
Objective-C
Released in 2014, it is used by Apple for systems programming.
What is the primary use of PHP?
Server-side HTML-embedded scripting language
Often used for form processing and database access through the Web.
What kind of typing does Python use?
Dynamically typed
Python is an OO interpreted scripting language.
What is the flagship .NET language?
C#
It is part of the .NET development platform and includes features like pointers and delegates.
What is XSLT?
eXtensible Stylesheet Language Transformation
It transforms XML documents for display.
What is meant by syntax in programming languages?
The form or structure of the expressions, statements, and program units
What does semantics refer to in programming languages?
The meaning of the expressions, statements, and program units
What is a lexeme?
The lowest level syntactic unit of a language
Examples include characters like ‘*’, ‘sum’, and ‘begin’.
What is a token in the context of programming languages?
A category of lexemes, such as an identifier
Who developed Context-Free Grammars?
Noam Chomsky in the mid-1950s
What is Backus-Naur Form (BNF)?
A notation to describe the syntax of programming languages
Invented by John Backus for Algol 58.
What does a grammar consist of?
A finite non-empty set of rules
What is the purpose of a start symbol in a grammar?
It is a special element of the nonterminals
What is a rule in BNF?
It has a left-hand side (LHS) which is a nonterminal and a right-hand side (RHS) which is a string of terminals and/or nonterminals
How are syntactic lists described in BNF?
Using recursion
Example: <ident_list> → ident | ident, <ident_list></ident_list></ident_list>
What is a syntactic list described using?
Recursion
The structure is defined as <ident_list> → ident | ident, <ident_list></ident_list></ident_list>
What is a derivation in the context of grammar?
A repeated application of rules, starting with the start symbol and ending with a sentence
What does the grammar <program> expand to?</program>
<stmts>
## Footnote
This is part of the example grammar provided.
</stmts>
What is a sentential form?
Every string of symbols in a derivation
What defines a leftmost derivation?
The leftmost nonterminal in each sentential form is the one that is expanded
What is a parse tree?
A hierarchical representation of a derivation
When is a grammar considered ambiguous?
If it generates a sentential form that has two or more distinct parse trees
What is the purpose of using a parse tree for precedence levels?
To avoid ambiguity
What is operator precedence?
The rule that multiplicative operators come before additive operators
What does associativity of operators define?
The order in which operators of the same precedence are evaluated
What type of recursion causes problems in syntax analysis?
Left recursion
What does right recursion indicate?
Right associativity
What is an example of an ambiguous grammar in Java?
<if_stmt> → if (<logic>) <stmt> | if (<logic>) <stmt> else <stmt>
</stmt></stmt></logic></stmt></logic></if_stmt>
What is the purpose of Extended BNF?
To define optional parts, alternatives, and repetitions in grammar
What do brackets [] indicate in Extended BNF?
Optional parts
What do braces {} signify in Extended BNF?
Repetitions (0 or more)
What is static semantics concerned with?
More syntax than semantics, related to the structure of programs
What are attribute grammars (AGs)?
Context-free grammars with additions to carry semantic information on parse tree nodes
What is the primary value of attribute grammars?
Static semantics specification
How is an attribute grammar defined?
A context-free grammar G = (S, N, T, P) with additional attributes and functions
What type of attributes are defined by functions of the form S(X0) = f(A(X1), …, A(Xn))?
Synthesized attributes
What is a predicate in the context of attribute grammars?
A condition to check for attribute consistency
What are the two types of attributes defined in attribute grammars?
Synthesized attributes and inherited attributes
Synthesized attributes pass information up a parse tree, while inherited attributes pass semantic information down and across a tree.
Define synthesized attributes in the context of attribute grammars.
Functions of the form S(X0) = f(A(X1), …, A(Xn)) define synthesized attributes
Synthesized attributes are used to pass information up a parse tree.
Define inherited attributes in the context of attribute grammars.
Functions of the form I(Xj) = f(A(X0), …, A(Xn)) for i <= j <= n define inherited attributes
Inherited attributes pass semantic information down and across a tree.
What are intrinsic attributes in attribute grammars?
Attributes determined outside the tree, e.g., type of a variable looked up in the symbol table
Intrinsic attributes exist on the leaves of the parse tree.
What is the role of expected_type in attribute grammars?
Used to store type expected for <expr> as determined by variable of LHS of assignment</expr>
This is an example of an inherited attribute.
What is the operational semantics?
Describes the meaning of a program by executing its statements on a machine
The change in the state of the machine defines the meaning of the statement.
What is the challenge of using a pure hardware interpreter?
It would be too expensive
This is a limitation in defining operational semantics.
What are the two different levels of uses of operational semantics?
Natural operational semantics and structural operational semantics
Define denotational semantics.
Based on recursive function theory; the most abstract semantics description method
Originally developed by Scott and Strachey in 1970.
What does the process of building a denotational specification involve?
Define a mathematical object for each language entity and define a function that maps instances of the language entities onto instances of the corresponding mathematical objects
What defines the meaning of language constructs in denotational semantics?
The values of the program’s variables
What is the state of a program in denotational semantics?
The values of all its current variables
Represented as s = {<i1, v1>, <i2, v2>, …, <in, vn>}
What is the function VARMAP used for in denotational semantics?
It returns the current value of the variable when given a variable name and a state
What does Mdec represent in the context of decimal numbers?
The mapping from character representation of decimal numbers to their integer values
What are expressions mapped onto in the context of the discussed semantics?
Z ∪ {error}
Expressions can be decimal numbers, variables, or binary expressions.
What action does the function Me perform on an expression?
It evaluates the expression based on its type, returning either a value or error
What does the assignment statement map in the context of semantics?
Maps state sets to state sets U {error}
What do assignment statements map?
State sets to state sets
Maps state sets to state sets U {error}
What is the outcome of M_a(x := E, s) if M_e(E, s) equals error?
Error
How is the new state s’ defined in assignment statements?
s’ = {<i1, v1’>, <i2, v2’>,…,<in, vn’>}
Where vj’ is determined by M_e(E, s) or VARMAP(ij, s)
What does M_l(while B do L, s) represent?
The execution of a loop while a condition B is true
What is the meaning of a loop in programming?
The value of program variables after executing the loop statements a prescribed number of times
How is recursion compared to iteration in the context of loops?
Recursion is easier to describe with mathematical rigor
What can denotational semantics be used for?
To prove the correctness of programs
What is the original purpose of axiomatic semantics?
Formal program verification
What are assertions in axiomatic semantics?
Logic expressions that state relationships and constraints among variables
What is a precondition in the context of axiomatic semantics?
An assertion before a statement
What is a postcondition in axiomatic semantics?
An assertion following a statement
Define weakest precondition.
The least restrictive precondition that guarantees the postcondition
What is the form of an axiomatic semantics statement?
{P} statement {Q}
What is the example given for a precondition in axiomatic semantics?
{b > 10}
What is the weakest precondition example provided?
{b > 0}
What is the postcondition for the entire program in program proof process?
The desired result
What does the axiom for assignment statements state?
{Q x->E} x = E {Q}
What is the Rule of Consequence in axiomatic semantics?
{P} S {Q}, P’ ⇒ P, Q ⇒ Q’ {P’} S {Q’}
What is the inference rule for sequences in axiomatic semantics?
{P1} S1 {P2}, {P2} S2 {P3} ⇒ {P1} S1; S2 {P3}
What is the inference rule for selection in axiomatic semantics?
{B and P} S1 {Q}, {(not B) and P} S2 {Q} ⇒ {P} if B then S1 else S2 {Q}
What is the inference rule for logical pretest loops?
{P} while B do S end {Q}
What are the conditions that a loop invariant I must meet?
- I must be true initially
- Evaluation of B must not change validity of I
- I is not changed by executing the body of the loop
- If I is true and B is false, Q is implied
What is a loop invariant?
A weakened version of the loop postcondition and a precondition
What is a challenge in developing axiomatic semantics?
Developing axioms or inference rules for all statements in a language
How does operational semantics differ from denotational semantics?
Operational semantics defines state changes by coded algorithms, while denotational semantics defines them by rigorous mathematical functions
What are the three primary methods of semantics description?
- Operational
- Axiomatic
- Denotational
