Programming Languages - Logic and Object-Oriented Paradigms

The focus is on logic programming (Prolog and Curry) and object-oriented programming (Smalltalk, Java, and C++).

Explain the fundamental principle of logic programming.

Logic programming is based on the idea that computation can be viewed as a form of logical deduction. A logic program consists of a set of axioms (logical statements assumed to be true), and computation involves attempting to prove a query (a statement to be derived) from these axioms using inference rules.

What is a Horn clause, and what are its key components (head and body)?

A Horn clause is a logical statement of the form A1 and A2 and ... and An implies B, where Ai and B are simple statements without "or" connectives or quantifiers. 'B' is the head of the clause (the conclusion), and 'A1, ..., An' form the body (the conditions)

Describe the processes of resolution and unification in logic programming.

Resolution is an inference rule for Horn clauses: if the head of one Horn clause matches a statement in the body of another, we can infer a new clause by replacing the matched statement with the body of the first clause. Unification is the process of finding substitutions for variables that make two logical expressions identical, often used during resolution.

In Prolog, how does the notation for a Horn clause differ from its logical representation? Provide an example.

In Prolog, the implication arrow (←) in a Horn clause is written as :-, and the "and" connective in the body is represented by a comma. For example, the Horn clause "mammal(x) and arms(x, 2) implies legs(x, 2)" is written in Prolog as legs(X, 2) :- mammal(X), arms(X, 2).

What is Prolog's search strategy for satisfying goals, and what potential issue can arise from it?

Prolog uses a strictly depth-first search strategy, replacing goals from left to right and considering clauses in the database from top to bottom. A potential issue with this strategy is that if the search tree has infinitely deep branches, Prolog may get stuck in an infinite loop and never find other possible solutions.

Define the "occur-check problem" in the context of unification.

The "occur-check problem" arises during unification when a variable is being unified with a term that contains that same variable. If this check is not performed, it can lead to the creation of infinite or circular data structures, which can cause programming errors like infinite loops.

Explain the concept of "negation as failure" in logic programming and the closed-world assumption.

"Negation as failure" is a principle in logic programming where a goal not(X) is considered true if the system cannot prove X to be true. This relies on the "closed-world assumption," which states that any fact not explicitly known to be true is assumed to be false.

What are the core principles of object-oriented programming that support software reuse and independence?

The core principles of object-oriented programming that support software reuse and independence include abstraction (focusing on essential features), encapsulation (hiding internal details), inheritance (creating new classes based on existing ones), and polymorphism (allowing objects of different classes to respond to the same method call in their own way).

Briefly compare and contrast the memory management approaches of Java and C++.

Java employs automatic memory management through garbage collection, where the JVM automatically deallocates memory occupied by objects that are no longer referenced. C++, on the other hand, requires manual memory management, where programmers must explicitly allocate memory using new and deallocate it using delete to prevent memory leaks.

Explain the concept of dynamic binding and the role of virtual functions in C++.

Dynamic binding is a mechanism where the specific method implementation to be executed is determined at runtime based on the actual type of the object. In C++, dynamic binding for member functions is enabled by declaring them as virtual; this allows for polymorphism where derived classes can override methods and have the correct version called even when accessed through a base class pointer or reference.

Axiom

A logical statement that is assumed to be true and serves as a starting point for proving other statements.

Predicate

In logic, a function that returns a Boolean value (true or false), representing a property or relationship.

Prolog

A widely used logic programming language based on Horn clauses and resolution.

Resolution

An inference rule used in logic programming to derive new Horn clauses from existing ones by matching the head of one clause with a goal in another.

Rule

In Prolog, a Horn clause with a non-empty body, defining a logical implication (e.g., legs(X, 2) :- mammal(X), arms(X, 2).).

Static Binding

The process of determining at compile time which specific method implementation will be executed.

Unification

The process of finding substitutions for variables that make two terms or logical expressions identical.

Virtual Function

In C++, a member function declared with the virtual keyword, allowing for dynamic binding and polymorphism.

Virtual Table (vtable)

A table of function pointers used in C++ (and other object-oriented languages) to implement dynamic binding for virtual functions. Each class with virtual functions has a vtable, and each object of that class contains a pointer to its class's vtable.

What is logic programming and what are its fundamental principles?

Logic programming is a programming paradigm based on formal logic. It views computation as a form of automated deduction. The programmer provides a set of logical statements (axioms or facts and rules), and a query or goal is posed. The logic programming system then attempts to prove whether the goal can be derived from the given statements using inference rules. First-order predicate calculus provides a formal way of expressing these logical statements, which can involve constants, predicates, functions, variables, connectives (and, or, not, implication), and quantifiers (universal and existential).

What are Horn clauses and why are they important in logic programming?

Horn clauses are a restricted form of logical statements that are widely used in logic programming systems. A Horn clause has the form "a1 and a2 and ... and an implies b," where 'b' (the head) and all 'ai' (the body) are simple statements without 'or' connectives or quantifiers. If there are no 'ai's, the clause is a fact ('b' is always true). If there is no 'b', it's a goal or query. Horn clauses are significant because automated deduction (proving new statements) is more manageable with this subset of predicate calculus, avoiding the complexities of handling the full range of logical expressions and inference rules. Many logic programming languages, like Prolog, are based on Horn clauses.

Explain the concepts of resolution and unification in the context of logic programming.

Resolution is a key inference rule used in logic programming with Horn clauses. If the head of one Horn clause matches a statement in the body of another Horn clause, resolution allows us to infer a new clause by replacing the matched statement with the body of the first clause. Unification is the process of making two logical statements identical by substituting variables with terms (constants, variables, or functions). When applying resolution, unification is used to find appropriate substitutions for variables so that the head of one clause can match a goal (or a statement in the body of another clause). If all goals can be unified and resolved to an empty set of goals, the original query is proven to be true.

What is Prolog and what are some of its key characteristics and syntax?

Prolog is a widely used logic programming language. It is based on Horn clauses and implements resolution using a depth-first search strategy. Prolog programs consist of a database of facts and rules (Horn clauses). Facts are statements assumed to be true, and rules define relationships between facts. Queries are posed to the system to determine if they can be logically derived from the database. In Prolog syntax, the implication "a implies b" is written as b :- a.. Variables begin with an uppercase letter or an underscore, while constants and predicate names start with a lowercase letter. A comma represents "and," and lists are enclosed in square brackets (e.g., [a, b, c]).

What are some of the challenges and problems associated with logic programming?

Logic programming systems face several challenges. One is the difficulty of fully automating deduction in first-order predicate calculus due to the vast number of ways to express statements and the multitude of inference rules. Most systems, therefore, restrict themselves to Horn clauses. Prolog's depth-first search strategy can lead to infinite loops if the search space is not structured carefully. The "occur-check problem" in unification (failing to verify if a variable occurs within the term it's being unified with) can lead to logical inconsistencies. "Negation as failure," where something is considered false if it cannot be proven true, can lead to non-intuitive results and nonmonotonic reasoning (adding information can invalidate previous conclusions). Furthermore, not all logical statements can be easily or accurately translated into Horn clauses.

How does the language Curry relate to logic programming, and what are some of its distinguishing features?

Curry is a programming language that aims to integrate the paradigms of functional programming and logic programming into a single framework. It supports features from both, such as higher-order functions, lazy evaluation (from functional programming), and non-deterministic computations with logical variables, partial applications, and constraint solving (from logic programming). A key distinguishing feature of Curry is its support for non-deterministic functions, where a function might have multiple possible results for the same input, and the system can explore these possibilities. It also uses a notion of computation based on needed reduction, which combines lazy evaluation with the ability to handle logical variables.

What are the core concepts of object-oriented programming (OOP) and how do languages like Java and C++ embody these concepts?

The core concepts of OOP include encapsulation (bundling data and methods that operate on that data), inheritance (allowing a class to inherit properties and behaviors from a parent class), and polymorphism (the ability of objects of different classes to respond to the same method call in their own way). Java and C++ are both object-oriented languages that heavily utilize these concepts. They use classes to define blueprints for objects, providing mechanisms for encapsulation through access modifiers (like private, protected, public in Java and C++). Inheritance is supported through keywords like extends (Java) and the colon syntax (C++). Polymorphism is achieved through method overriding and, in some cases, method overloading (though Java does not support operator overloading like C++). Java emphasizes platform independence through bytecode and automatic memory management (garbage collection), while C++ offers more control over system resources and memory management but is platform-dependent after compilation.

What are some key differences between Java and C++ in terms of platform dependency, memory management, and object-oriented features?

Java is designed to be platform-independent; its code compiles to bytecode that runs on the Java Virtual Machine (JVM), enabling "write once, run anywhere." C++, on the other hand, compiles directly to machine code specific to a particular platform. Java features automatic memory management through garbage collection, which reduces the risk of memory leaks but can have performance implications. C++ requires manual memory management using new and delete, offering more control but demanding careful programming. Regarding OOP, both support core principles, but C++ is a hybrid language supporting both procedural and object-oriented programming, while Java is purely object-oriented (with the exception of primitive types). C++ allows multiple inheritance (inheriting from more than one base class) and operator overloading, which Java does not directly support. C++ also offers more fine-grained control over features like virtual functions (dynamic binding is not the default and must be explicitly specified with virtual), whereas dynamic dispatch is the default for non-final methods in Java.