Concepts of Programming Languages

Vocabulary flashcards covering key terms, languages, concepts, and paradigms discussed in the video notes on programming languages (Pages 9–30).

What were the two most impactful/important languages in 1950

Cobal and Fortran were revolutionary programming languages that significantly influenced software development and data processing. Fortran was primarily designed for scientific computing, while COBOL focused on business applications.

Objective-C

Object-oriented extension of C used on Apple platforms; combines C syntax with Smalltalk-style messaging.

Object-Oriented Programming

Programming paradigm that uses objects (data + behavior), classes, inheritance, and abstraction to organize software.

Functional Programming

A paradigm where computation is the evaluation of functions without changing state or mutable data. Focuses on what to compute. Same input = same output

High-Level Language

Machine-independent language that abstracts hardware details and requires translation (compilation or interpretation) to machine code.

Compiler

Program that translates high-level language code into low-level code (machine or VM-ready) for execution.

Interpreter

Program that executes source code directly (often with run-time translation), enabling dynamic programming behavior.

What is Imperative Programming

A paradigm where the program is written as a sequence of statements that change state (variables, memory). Focuses on how to do tasks.

List the different types of languages in the hierarchy of programming languages

Machine Language, Assembly Languages, High Level Languages, Visual Languages

What is the differences between a compiler and interpreter? Benefits and drawbacks of both?

• Compilers

  • Translate code before execution

  • Advantages: Faster execution (once compiled), heavy optimizations, early error checking

  • Disadvantages: Less flexible, cannot change code on the fly

• Interpreters

  • Translate code during execution

  • Advantages: Flexible, can change/dynamically run code, full knowledge of runtime behavior

  • Disadvantages: Slower (re-interprets each time), limited optimization, errors only found at runtime

Explain the different Phases of a Compiler

1. Lexical Analysis – Breaks source into tokens (keywords, identifiers, literals).

2. Syntax Analysis – Checks grammar rules, builds parse tree.

3. Semantic Analysis – Ensures meaning correctness (types, scope, declarations).

4. Intermediate Code Generation – Converts code into IR (e.g., three-address code).

5. Code Optimization – Improves IR for efficiency (speed, memory).

6. Code Generation – Produces target machine code.

• Symbol Table – Stores identifiers, types, scope info (used throughout).

• Error Handling – Detects and reports errors at all stages.

Map the following languages to their corresponding programming paradigms:

• (a) C

• (b) C++

• (c) Java

• (d) JavaScript

• (e) Perl

• (f) Fortran

• (g) Python

• (h) Lisp

• (i) PHP

Paradigms:

• (1) Functional

• (2) Imperative

• (3) Object-Oriented

• (a) C → (2) Imperative

• (b) C++ → (2) Imperative, (3) Object-Oriented

• (c) Java → (3) Object-Oriented

• (d) JavaScript → (2) Imperative, (3) Object-Oriented

• (e) Perl → (2) Imperative

• (f) Fortran → (2) Imperative

• (g) Python → (1) Functional, (2) Imperative, (3) Object-Oriented

• (h) Lisp → (1) Functional

• (i) PHP → (2) Imperative, (3) Object-Oriented

Categorize the following as a feature of either high-level or low-level programming languages:

• A. Code runs faster on hardware

• B. Easy to write and maintain

• C. Easy to port to different machines

• D. Easy to debug (and detect errors)

• E. Easy for humans to understand

• F. Easy for machine translation

• A. Low-level

• B. High-level

• C. High-level

• D. High-level

• E. High-level

• F. Low-level

Map the following languages to their corresponding implementation mechanism:

• (a) C

• (b) C++

• (c) Java

• (d) JavaScript

• (e) Perl

• (f) Fortran

• (g) Python

• (h) Lisp

• (i) PHP

Implementation Mechanisms:

• (1) Compiled

• (2) Interpreted

• (a) C → (1) Compiled

• (b) C++ → (1) Compiled

• (c) Java → (1) Compiled

• (d) JavaScript → (2) Interpreted

• (e) Perl → (2) Interpreted

• (f) Fortran → (1) Compiled

• (g) Python → (2) Interpreted

• (h) Lisp → (2) Interpreted

• (i) PHP → (2) Interpreted

Select criteria for deciding whether a language should be implemented using a compiler or an interpreter.

• A. Whether an object code in another language is desired

• B. Whether input data is required for when running the program

• C. Whether the language allows each variable to have arbitrary types at runtime

• D. Whether the language implementation needs to be fast

• E. Whether the program needs to be used more than once

• F. Whether the language needs to support large-scale software development

• A. Compiler

• B. Interpreter

• C. Compiler

• D. Compiler

• E. Compiler

• F. Compiler

Decide whether each of the following components belongs to a compiler or interpreter (or both).

• A. Lexical analyzer

• B. Syntax analyzer

• C. Semantic analyzer

• D. Intermediate code generator

• E. Code optimizer

• F. Code generator

• A. Both (Compiler and Interpreter)

• B. Both (Compiler and Interpreter)

• C. Both (Compiler and Interpreter)

• D. Compiler

• E. Compiler

• F. Compiler

Which of the following defines or correctly categorizes the halting problem?

• A. Whether an arbitrary program can halt eventually when given an arbitrary input

• B. The halting problem is not solvable (i.e., not computable by computers)

• C. Whether an arbitrary program can always halt for all program inputs

• D. Whether some given program can always halt for arbitrary program inputs

• A. Correct

• B. Correct

• C. Incorrect: This statement would imply a decision about all programs, but not all programs halt for all inputs.

• D. Incorrect: This statement is too specific and does not describe the general halting problem. Some programs do halt for some inputs, but the halting problem is about the general case.

Most general programming languages are Turing complete and can express all functions that are:

• A. Finite

• B. Partial

• C. Discrete

• D. Partial recursive

• E. Arbitrary

• F. Recursive

• A. Incorrect: Turing-complete languages can express more than finite functions.

• B. Incorrect: Turing-complete languages can express both partial and total functions.

• C. Incorrect: While discrete functions can be expressed, this term isn’t central to Turing completeness.

• D. Correct: Turing-complete languages can express partial recursive functions. These functions may not halt for all inputs, but they can still be expressed by a Turing machine.

• E. Incorrect: Arbitrary functions may not be the most precise definition for Turing completeness.

• F. Correct: Turing-complete languages can express recursive functions, which are essential for representing all computable functions.

Which of the following problems are computable (can be fully solved by computers)? Which are not computable?

• A. The halting problem

• B. Translating an arbitrary Java program to C

• C. Whether a sorting program is implemented correctly

• D. Whether an arbitrary program is free of bugs

• A. Not computable: The halting problem is famously undecidable and cannot be solved by any algorithm for all possible programs and inputs.

• B. Computable: Translating a Java program to C can be done because a Java compiler can be extended to produce C code, and this is a solvable problem (essentially a proof by contradiction).

• C. Computable: Whether a sorting program is implemented correctly is solvable. If the sorting algorithm is clearly defined, you can test whether a given program correctly sorts data, assuming it's a single program.

• D. Not computable: Determining whether an arbitrary program is free of bugs is not computable because it essentially reduces to the halting problem—defining a program as "free of bugs" means ensuring it halts without error, which is undecidable.

What are the key features of Functional Programming?

• A program is an expression:

  • Focuses on expressing the flow of data from input to output.

  • No side effects or modifications to variables.

• Functions are first-class objects:

  • Functions can be defined and used everywhere.

  • Functions don’t have to have names.

  • Can take other functions as parameters and return functions as results (higher-order functions).

• No side-effect operations:

  • The same expression always produces the same result no matter where it appears (important for predictability and reliability).

• Evaluation of functions:

  • The core idea is the evaluation of functions without changing state or mutable data.

  • Focuses on what to compute rather than how.

  • Same input = same output.

A Lisp program may include which of the following as the sole component?

• (a) An expression

• (b) An assignment

• (c) A variable definition

• (d) A loop

• (a) An expression: Correct: A Lisp program can be a single expression, which holds a value or refers to a variable with an initialized value.

• (b) An assignment: Incorrect: In Lisp, an assignment cannot exist on its own. You must first define a variable before assigning a value to it.

• (c) A variable definition: Incorrect: A variable definition must be paired with an assignment to create a new variable, even if allowed in some extended Lisp versions.

• (d) A loop: Incorrect: A loop in Lisp generally cannot exist on its own; it would require other components, like a function or variable definition, for it to be meaningful.

Which of the following about lists in Lisp are false?

• (a) They may contain arbitrary types of elements

• (b) They can be nested and thus become trees

• (c) They cannot be built incrementally

• (d) They cannot be given names

• (a) They may contain arbitrary types of elements: True. Lists in Lisp can contain arbitrary types of elements due to dynamic typing.

• (b) They can be nested and thus become trees: True. Lisp lists can be nested within each other, creating tree-like structures.

• (c) They cannot be built incrementally: False. Lisp lists can be built incrementally, meaning new elements can be added to a list as needed.

• (d) They cannot be given names: False. Lisp lists can be named just like any other variable or data structure in Lisp.

What are the programming steps in lisp?

• dentify input parameters
  – Ask: What does the function need to work with? (e.g., a number, a list).

• Consider possible values
  – Think through the different forms those inputs might take (empty list, positive/negative number, etc.).

• Enumerate cases and return values
  – For each kind of input, define what the function should return.
  – Example: (if (null lst) 0 (+ 1 (my-length (cdr lst)))) handles both the empty list and non-empty list cases.

Who created the divide and conquer paradigm?

Dijkstra