Prog Lang Exam 2 Flashcards
Logic Programming
A programming paradigm where logic is used to represent both programs and the process of computation.
Mathematical Logic
Basis for logic programming, involving the first-order predicate calculus, axioms, theorems, and logical interferences.
What are the two logic programming languages?
Prolag and Curry
Logical Statements
Etiher true or false; axioms are assumed true statements from which other true statements are derived.
Horn Clauses
A simplified form of first-order predicate calculus used in logic programming.
Resolution
A rule for combining Horn Clauses by eliminating matching terms.
Unification
Process of making staements identical by assigning values to variables, essential in deriving logical conclusions.
Core structures of Prolog, where rules and facts are expressed in a logical format.
Horn Clauses
Prolog’s Search Strategy
Prolog employs a depth-first search strategy to resolve goals, which can lead to infinite loops if not carefully managed.
Structure of Horn Clauses
a1 and a2 and a3 … and an –> b
b
Head of the clause.
a1, …, an
Body of the clause
Backtracking
Allows Prolog to search for multiple solutions, but care must be taken to avoid infinite loops.
Negation as Failure
A goal fails if it cannot be proven true, representing the closed-world assumption.
Problems with Logic Programming
Control issues, occur-check problems, and declarative nature.
The Curry Language
Combines the features of Haskell (functional programming) and Prolog (logic programming).
Curry Key Features
Nondeterminism, lazy evaluation, and combincation of functional and logic programming.
Nondeterminism
Allows multiple solutions to be explored without a predefined order.
Lazy Evaluation
Only computes values when needed, enhancing efficiency.
Prolog vs. Curry
Prolog focuses on logic programming with backtracking and unification, whereas Curry blends logic and functional programming with features like lazy evaluation and nondeterminism.
OOP languages aim to facilitate:
- Reusability of software components.
- Modification of behavior with minimal code changes.
- Independence of different components through abstraction, polymorphism, and encapsulation.
Polymorphism
Ability to extend the types of data operations can apply to, like method overloading and parameterized types.
Manual memory management
Developers must manually allocate and deallocate memory using new and delete.
Multiple Inheritanc
C++ supports multiple inheritance, which is not allowed in Java due to complexity (such as the diamond problem).
Templates
C++ templates allow for generic programming, enabling compile-time polymorphism without the overhead of virtual functions
Encapsulation
Use of private instance variables and accessor methods ensures encapsulation.
Constructors/destructors
C++ objects have constructors for initialization and destructors for deallocation.
Static binding
Occurs at compile-time, when the compiler determines the method to call based on the declared type of the object.
Dynamic binding
Occurs at runtime, where the method to be invoked depends on the actual type of the object. This is achieved through virtual functions and is a key feature in C++ for polymorphism.
Compile-time polymorphism
Achieved through method overloading and operator overloading.
Object overhead
OOP introduces additional memory overhead due to metadata like virtual tables.
Virtual function calls
Introduce performance penalties due to the indirection required for resolving method calls at runtime.
Garbage collection
In languages like Java or C#, memory management is handled by garbage collection. The GC periodically runs to reclaim memory from objects that are no longer in use. This can introduce unpredictable pauses, which may be problematic for real-time applications.
Which of the following best describes the structure of a Horn clause?
A rule in the form of A1 ∧ A2 ∧ … ∧ An → B
What is the primary inference method used in Prolog?
Resolution
In Prolog, which operator is used to control backtracking?
! (cut)
Which language is Curry an extension of?
Haskell
What is the role of the “fail” predicate in Prolog?
It forces Prolog to backtrack and look for another solution.
Which of the following is a key principle of object-oriented programming?
Polymorphism
In Java, which keyword is used to prevent a method from being overridden in a subclass?
final
What is the purpose of the virtual table (vtable) in C++?
To resolve dynamically bound methods at runtime
What is the main difference between compile-time polymorphism and runtime polymorphism?
Compile-time polymorphism is resolved at compile time, while runtime polymorphism is resolved at runtime.
T/F Unification is the process of matching variables with terms to make logical statements identical.
True
T/F In Prolog, changing the order of Horn clauses can never lead to infinite loops.
False
T/F The occur-check problem refers to Prolog’s failure to check whether a variable appears in the term it’s being unified with.
True
T/F Curry supports both deterministic and non-deterministic computations.
True
T/F The depth-first search strategy in Prolog is more efficient than breadth-first search and avoids all infinite loops.
False
T/F Dynamic binding is used when a method call is resolved at runtime.
True
T/F C++ supports both multiple inheritance and operator overloading, while Java does not.
True
T/F In Java, all objects are allocated on the heap and garbage collected automatically.
True
T/F The friend keyword in C++ allows one class to access private members of another class.
True
T/F Garbage collection in Java introduces predictable pauses, making it ideal for real-time systems.
False
Explain the difference between resolution and unification in logic programming.
Resolution is the process of deriving new logical statements by combining Horn clauses, while unification is the process of making two logical expressions identical by assigning values to variables.
What is the closed-world assumption in logic programming?
The closed-world assumption in logic programming means that anything that cannot be proven to be true is assumed to be false. This assumption underlies the “negation as failure” concept, where if a statement fails to be proven true, it is treated as false.
Describe the purpose of the cut operator (!) in Prolog.
The cut operator in Prolog is used to prevent further backtracking by pruning parts of the search tree. Once a cut is encountered, Prolog will not try other alternatives for that goal, effectively fixing the choices made up to that point.
How does Curry combine functional and logic programming paradigms?
Curry combines functional and logic programming by supporting both higher-order functions, lazy evaluation, and logic-based constructs like nondeterminism and unification. It allows programmers to use functional programming constructs alongside logic programming techniques to solve problems.
What is negation as failure in Prolog, and what are its limitations?
Negation as failure is a rule in Prolog where a goal is assumed false if it cannot be proven true. Its limitation lies in the fact that it depends on the closed-world assumption, meaning it might not work well in cases where knowledge is incomplete or unknown facts exist outside the system.
Explain the difference between static binding and dynamic binding in C++.
Static binding occurs at compile time and resolves method calls based on the declared type of the object. Dynamic binding occurs at runtime, where the actual method invoked depends on the object’s runtime type. Dynamic binding is achieved in C++ using virtual functions and a virtual table (vtable).
What is the significance of the final keyword in Java, and how does it impact performance?
In Java, marking a method or class as final means it cannot be overridden. This allows the compiler to optimize method calls by avoiding dynamic dispatch and potentially inlining the method, thus improving performance.
How does C++ handle memory management, and what are the risks associated with it?
C++ uses manual memory management through new for allocation and delete for deallocation. If developers forget to deallocate memory, it can result in memory leaks. Other risks include dangling pointers, where memory is deallocated but still referenced by a pointer, leading to undefined behavior.
Describe how garbage collection works in Java and its potential drawbacks in performance-critical applications.
Java uses automatic garbage collection to manage memory, periodically freeing up memory from objects that are no longer referenced. While it simplifies memory management, it can introduce unpredictable pauses (garbage collection pauses), which may negatively impact the performance of real-time or performance-critical applications.
Why does Java not support multiple inheritance of classes, and how does it achieve similar functionality?
Java does not support multiple inheritance of classes to avoid the complexity and ambiguity of the “diamond problem.” However, it allows classes to implement multiple interfaces, which provides a form of multiple inheritance by allowing objects to inherit behavior from multiple sources.
