Programming Languages & Computer Graphics

Overview

This unit has two halves that are examined differently. The programming-languages half rewards precise definitions and careful tracing: given a short program, what is printed, which function is called, and what changes? The graphics half rewards hand computation: given two endpoints, which pixels light up, and given a point and a matrix, where does the point land? Study them with different habits. For languages, trace small programs on paper under each rule before you look at the answer. For graphics, work one algorithm at a time with a table of steps, and check each row against the rule, not against a remembered picture.

Programming paradigms & scope

A programming paradigm is a coherent set of concepts for structuring programs. The imperative paradigm is built on variables, assignment and control flow: a program is a sequence of commands that changes state, as in C and Pascal. The object-oriented paradigm organises state and behaviour into objects that exchange messages; it is often implemented on top of imperative ideas, as in Java, C++ and Python. The functional paradigm treats computation as function evaluation, avoids mutable state and side effects where possible, and favours recursion, higher-order functions and immutable data, as in Haskell and the functional parts of Python. The logic paradigm, exemplified by Prolog, declares facts and rules; execution is search for a proof that satisfies a query, with unification binding variables to values. Declarative programming is the wider family that includes functional and logic styles: the programmer states what is wanted rather than the exact steps.

Binding is the association of a name with a property, such as its type, its value or its storage. Static binding is fixed before or at compile time, for example a variable declared with a fixed type in C, or a non-virtual function call resolved by the compiler. Dynamic binding is deferred to run time, for example a virtual function call in C++ or Java, where the method executed depends on the actual object type, not the declared reference type. Early binding is efficient; late binding is flexible and powers runtime polymorphism.

Scope is the region of the program where a name is visible. Under static, or lexical, scope, a free variable refers to the declaration in the nearest enclosing block in the program text. Most modern languages use static scope. Under dynamic scope, a free variable refers to the most recent binding on the call stack at run time, so the same function can print different values depending on who called it. Lifetime is different from scope: it is the interval during which storage for a variable exists. A local variable typically lives only during its function activation, while a static variable in C lives for the whole program run even though it is visible only inside its function. A global variable has both wide scope and long lifetime. Confusing scope with lifetime is a classic exam trap.

Parameter passing determines the relationship between an actual argument and a formal parameter. Pass by value copies the value, so changes to the parameter do not affect the caller; C passes by value by default. Pass by reference gives the parameter access to the caller's variable itself, so changes persist; C++ references and the effect of passing a pointer in C achieve this. Pass by name, historically in Algol, substitutes the argument expression textually and re-evaluates it on every use, which can give surprising results when the expression has side effects. Pass by value-result copies in on entry and copies back on return, so intermediate changes are invisible to the caller until the function returns. Python uses a model often called pass by object reference: the reference to the object is copied, so mutating a list inside a function is visible to the caller, but rebinding the parameter name is not.

Type systems add another dimension. A statically typed language checks types at compile time; a dynamically typed language checks them at run time. Strong typing restricts implicit conversions that would change meaning; weak typing permits them more freely. Type checking can be static or dynamic independently of strong or weak typing, and the exam often tests the four combinations. Recursion is the technique of defining a function in terms of itself, with a base case that stops the recursion and a recursive case that reduces the problem; without a reachable base case the program recurses until the stack overflows. A closure is a function together with the environment in which it was defined, so it can remember variables from its enclosing scope after that scope has finished executing.

How this is examined: expect questions that ask which paradigm a snippet belongs to, what a program prints under static versus dynamic scope, whether a caller variable changes under a given passing mode, and which binding time applies to a virtual call. Work by naming the rule first, then tracing, never by intuition about what the program ought to do.

OOP concepts

Object-oriented programming organises a program around objects, which bundle data and the operations on that data. Encapsulation is the bundling itself together with hiding of internal details: an object exposes an interface and keeps its representation private, so clients depend on behaviour rather than on fields. Abstraction is the related idea of exposing only the essential features and suppressing irrelevant detail; an abstract class or interface is abstraction made explicit in code. Inheritance lets a new class reuse and extend an existing class: the subclass inherits fields and methods and can add or replace behaviour. Polymorphism means one interface with many forms: the same call can behave differently depending on the object it acts on. Together these four ideas explain most object-oriented design questions.

A class is a blueprint; an object is an instance of a class. A constructor is a special method that runs when an object is created and initialises its state. In Java a constructor has the same name as the class and no return type; in Python the initialiser is the method named __init__. A default constructor takes no arguments; a parameterised constructor takes arguments. In garbage-collected languages, finaliser timing is not guaranteed, so it must not be relied on for essential cleanup.

Overloading and overriding are the two faces of polymorphism and are constantly confused. Overloading is compile-time polymorphism: several methods in the same class share a name but differ in their parameter lists, in number, type or order of parameters. The compiler picks the version by matching the call arguments. Overriding is runtime polymorphism: a subclass provides its own implementation of a method already defined in its superclass, with the same name and the same parameter list. The version executed is chosen at run time from the actual object type, provided the method is virtual or dynamically dispatched. Overloading is resolved by the compiler; overriding is resolved at run time. Changing only the return type does not overload a method in Java, and changing the parameter list does not override one.

An abstract class is a class that cannot be instantiated directly and may contain abstract methods without bodies; subclasses must implement them unless they are also abstract. An interface declares a contract of methods without, in the classic form, providing implementations; a class implements an interface by supplying all its methods. A class in Java extends one superclass but can implement several interfaces, which is how Java provides multiple inheritance of type without multiple inheritance of implementation. Access control shapes all of this: public members are visible everywhere, private members only inside the class, and protected members inside the class, its subclasses and, in Java, its package. A static member belongs to the class rather than to any instance, and a final member in Java cannot be reassigned, overridden or extended, depending on what it qualifies.

Inheritance has forms worth naming. Single inheritance has one direct superclass; multilevel inheritance chains classes; hierarchical inheritance has several subclasses of one superclass; multiple inheritance has several direct superclasses, permitted in C++ and Python but not as class inheritance in Java. The diamond problem arises in multiple inheritance when two superclasses share a common ancestor and the subclass inherits the same member through both paths; languages resolve it by rules such as method resolution order in Python or by virtual inheritance in C++. Composition, where a class holds an object of another class, is often preferable when the relationship is has-a rather than is-a.

How this is examined: expect code-tracing questions asking which overloaded method matches a call, which overridden method runs for a reference of one type holding an object of another, whether a class can be instantiated, and which access modifier permits a given access. Answer by checking, in order, the reference type, the object type, the parameter list and the dispatch rule, rather than by reading the code as if it were prose.

Computer graphics basics

Computer graphics produces pictures from numerical descriptions. In raster graphics the picture is a grid of pixels, each with a colour value stored in a frame buffer; in vector graphics the picture is a list of geometric primitives such as lines and curves, which are resolution independent but must be rasterised to display. A raster display needs algorithms that decide which pixels best approximate a mathematical shape.

Line drawing is the fundamental case. The Digital Differential Analyzer, or DDA, samples a line at unit steps in the dominant direction: if the absolute slope is at most one, step x by one and add the slope to y; otherwise step y by one and add the reciprocal slope to x, rounding each computed coordinate to the nearest pixel. DDA is simple but uses floating-point addition and rounding at every step, which makes it slower and less accurate over long lines. Bresenham line algorithm uses only integer arithmetic. For a line with slope between zero and one, it maintains a decision parameter that tracks the error between the true line and the chosen pixel; at each step it moves one pixel in x and decides, from the sign of the parameter, whether to also move one pixel in y, updating the parameter by fixed integer amounts. Bresenham is faster, exact in integer arithmetic, and is the standard answer when a question asks for the efficient line algorithm. The midpoint circle algorithm applies the same decision-parameter idea to circles, exploiting eight-way symmetry: compute pixels for one octant and mirror them to the other seven. It starts at the top of the circle and steps in x, deciding at each step whether to move in y, with the decision parameter updated by integer rules derived from the circle equation.

Transformations change the position, size or orientation of objects. In two dimensions, translation by (tx, ty) sends (x, y) to (x plus tx, y plus ty). Scaling by (sx, sy) sends (x, y) to (sx times x, sy times y). Rotation by angle theta about the origin sends (x, y) to (x cos theta minus y sin theta, x sin theta plus y cos theta). Using homogeneous coordinates, a point is written as (x, y, 1) and each transformation becomes a three by three matrix, so transformations can be composed by matrix multiplication and applied in one step. Order matters: matrix multiplication is not commutative, so scaling then translating generally differs from translating then scaling. Rotation and scaling are normally performed about the origin, so rotating about another point requires translating that point to the origin, rotating, and translating back. Three-dimensional transformations extend the same idea with four by four matrices.

Clipping removes the parts of a picture outside a viewing window. The Cohen-Sutherland line clipping algorithm assigns each endpoint a four-bit outcode recording whether the point is above, below, to the left of, or to the right of the window. If the bitwise AND of the two outcodes is non-zero, the line is trivially rejected because both endpoints share an outside region. If both outcodes are zero, the line is trivially accepted. Otherwise the line is partially visible: an endpoint outside the window is replaced by its intersection with a window edge, its outcode is recomputed, and the process repeats. The viewing pipeline as a whole runs from modelling coordinates, through world coordinates, to viewing coordinates, then to normalised device coordinates, and finally to device or screen coordinates by a viewport mapping. Hidden-surface removal decides which surfaces are visible in a three-dimensional scene: the depth-buffer, or Z-buffer, algorithm keeps, for each pixel, the smallest depth seen so far and draws only a surface nearer than the stored value; the painter algorithm sorts surfaces by depth and draws them back to front, which is simpler but fails when surfaces overlap cyclically or intersect.

How this is examined: expect a Bresenham table for a short line, a matrix applied to a point, a statement of which transformation order is correct, a Cohen-Sutherland accept or reject decision from outcodes, and a comparison of DDA with Bresenham or of Z-buffer with painter.

Parameter-passing modes compared

Overloading versus overriding

DDA versus Bresenham

Scope and binding contrasts