CODEWITHSUNDEEP
pascal
vesii
vesii

Reputation: 3128

The "set of" operator in Pascal

I was reading that the set of operator in Pascal represents the Mathematical "Power Set", but I can't seem to understand how.

For example, on Wikibooks, The Free Textbook Project, Page “Pascal Programming/Sets” I have found the following piece of code:

program setDemo(output);
type
    skill = (cooking, cleaning, driving, videogames, eating);
var
    slob: set of skill;
begin
    slob := [videogames, eating];
end.

What do we get from slob := [videogames, eating] command? I guess that slob will contain those two "skills", but how does it represented by the Power set?

Upvotes: 2

Views: 1313

Answers (1)

Andreas Rejbrand
Andreas Rejbrand

Reputation: 108963

Basically, being a subset of the set of (all) skills, slob is an element of the power set of the set of (all) skills.

In Pascal, set of A, where A is some ordinal type, is a type that represents a mathematical set of elements of type A. More precisely, each value of this type is such a mathematical set. For example, in Delphi (a modern version of Pascal), you have the

TFontStyle = (fsBold, fsItalic, fsUnderline, fsStrikeOut)

enumeration and the corresponding TFontStyles = set of TFontStyle set type. While a value of type TFontStyle is simply either of fsBold, fsItalic, fsUnderline, or fsStrikeOut, a value of type TFontStyles is a set of font styles (or attributes), such as [fsBold, fsUnderline]. If you set a label's Font.Style property to this value, the label's font will be bold and underlined.

You seems to understand this, so let me instead focus on the 'power set' concept, which you seem to be confused about.

Using mathematical syntax, consider the set

A = {cooking, cleaning, driving, gaming, eating}

of skills. The power set of A, sometimes denoted P(A) or 2^A, is the set of all subsets of A. (Hence, it is a set whose members are sets.) Some of the members of this set are listed below:

{} (=the empty set)
{cooking}
{driving}
{cooking, cleaning}
{cleaning, gaming, eating}
{cooking, cleaning, driving, eating}
{cooking, cleaning, driving, gaming, eating} (=A)

In total, P(A) consists of 2^|A| = 2^5 = 32 elements. Indeed, in a given subset of A, either cooking is part of it or it is not (2 options), and for each of these options, either cleaning is part of the subset or it is not (2 options), and so on. The total number of combinations thus becomes 2×2×...×2 = 32.

Now, given the Pascal enumeration

skill = (cooking, cleaning, driving, gaming, eating)

set of skill is a type whose values are sets of skill values, like [cooking, cleaning] or [cleaning, gaming, eating] (using Pascal syntax). Clearly, each such value -- a subset of A -- is an element of P(A), in much the same way as each value of type skill is an element of A itself.

You asked specifically,

What do we get from slob := [videogames, eating] command?

You assign the value [videogames, eating] to the variable slob. This is a value of type set of skill, and this particular value contains the members videogames and eating.

Under the hood, a set value in Delphi is represented using a number of bytes (each set type has a specific size), and each possible element in the set is represented by a specific bit. In Delphi, the type set of A is only allowed if A has no more than 256 values. If A has this many values (say if A is byte), this requires set of A to have 256 bits (so that there are 2^256 = 1.16 × 10^77 possible values of type set of A).

Sometimes people wonder why they cannot declare a type set of integer. But an integer is a 32-bit value, so there are 2^32 = 4294967296 such values. A value of the hypothetical type set of integer would thus require 4294967296 bytes, or 4 GB. That's a huge amount of memory for a single variable!

Upvotes: 3

Related Questions