Introduction to ISETL Updated for Windows version in December 2008 by Vincent Cicirello Assistant Professor of Computer Science Stockton State College Pomona, NJ 08240 Based on tutorial originally prepared in March 1989, updated in January 2001 by Murray Kirch Professor of Computer Science and Mathematics Stockton State College Pomona, NJ 08240 --> All user input will be indicated in lower case. ISETL is case sensitive; for the sake of simplicity during this tutorial, use only lower case when typing at the terminal. User input will be indented. --> ISETL output will not be indented. --> All commentary will begin on a new line and be enclosed in parentheses. --> When the ISETL output is long and not critical, it is omitted and replaced by the symbol ... . (ISETL may be run from any disk drive, including floppies if you still know someone who uses them.) To exit ISETL at any time, select exit from the File menu. You can also save via the save and save as options. (The ISETL prompt is >. ISETL is an interactive language. If an expression is typed at the terminal, then ISETL will evaluate it and then prompt the user for more input. All expressions must terminate with a semi-colon and each line must end with a carriage return.) __________________________________________________________________ MATH EXPRESSIONS Mathematics expresions can simply be typed using the expected operators (+, -, /, *, mod). / does division and does not have special behavior for integers. > 4 + 5; 9; > 2 / 3; 0.667; > (Expressions can be continued over several lines. ISETL uses >> to prompt for more input to complete an expression. If you make an error and are still on the first line of an expression, use the delete key to make corrections. Otherwise, press return to finish the current line; then type !clear and press return. When you see the > prompt, you may reenter the expression. The math operators: +, -, /, *, mod, div, ** > 4 >> + >> 5 >> ; 9; > (ISETL provides the usual arithmetic and boolean operations. x mod y evaluates to the remainder obtained by dividing the integer x by the integer y. x /= y denotes "x is not equal to y".) > 5 mod 2; 1; > 6 * 2; 12; > true or false; true; > (2 < 3) and (3 > 10); false; > (2 * 3) /= (3 * 2); false; > 5 mod 2 = 0; false; > not (5 mod 2 = 0); true; > Integer division: div > 5 div 2; 2; > Exponentiation: ** > 2**4; 16; > The boolean operators in ISETL: and, or, not The relational operators: >, <, <=, >=, =, /= Implications: impl > false impl false; true; > false impl true; true; > true impl true; true; > true impl false; false; > 5 > 2 impl 10 > 4; true; > __________________________________________________________ VARIABLES AND ASSIGNMENTS (Assignment statements in ISETL are similar to those in the language Pascal as well as what is used in Maple for assignment. You do not need to declare variables before first use as you do in most languages (such as Java). You can simply use them as in the examples below.) > x := 1 + 3; > x; 4; > b := 2 < 5; > b; true; > y := x * 10; > y; 40; > __________________________________________________________ SETS AND SET OPERATIONS (A set is an unordered collection of objects.) > s := {1, 4, 5}; > s; {1, 5, 4}; > s := {1..20}; > s; {7, 8, 5, 6, 4, 3, 2, 1, 12, 11, 10, 9, 13, 14, 15, 16, 17, 18, 20, 19}; > (The last assignment statement above assigns to s the set of all integers from 1 to 20, inclusive (can use .. for range specifications). When the value of a set is displayed, the order of the elements is unpredictable. The above is the actual output from a run in ISETL. ISETL provides several set operations and functions including the following: union a + b intersection a * b difference a - b power set pow (a) size #(a) #a membership x in a x notin a selection of an arbitrary member arb (a) Evaluate each of the above expressions after assigning a the value {1..4}, b the value {2,4,6} and x the value 1. _____________________________________________ PREDICATES ISETL also provides for predicates, boolean valued expressions which can include quantified variables.) > a := {1..4}; > forall k in a | k * k = k; false; > exists k in a | k * k = k; true; > (The first expression is false since it states that each member of a is equal to its own square. However 1 is a member of a. Hence the second expression is true since it states that there exists a member of a which is its own square. ______________________________________________ CONTROL STRUCTURES: IF and LOOPS ISETL has Pascal-like control structures and the capability to nest statements within statements. For example, to form the set of squares of all integers in the range 1..20 which are multiples of 5, enter the following statements.) > squares := {}; > > for x in {1..20} do >> if x mod 5 = 0 then >> squares := squares + { x * x }; >> end if; >> end for; > > squares; {25, 100, 225, 400}; > ____________________________________________________ FORMING SETS (However sets can also be formed in ISETL using expressions of the form { e(x) : x in s | p(x) }; where e(x) is an expression, s is a set, and p(x) is a predicate. Here is how we could use this approach to form the same set as described in the previous example.) > squares := {x * x : x in {1..20} | x mod 5 = 0 }; > squares; {25, 100, 225, 400}; > (Suppose we want to find all integers between 2 and 35 which divide 36.) > { x : x in {2..35} | 36 mod x = 0 }; ...; > _______________________________________________________ TUPLES: Ordered collections of objects (Sometimes we want to consider ordered collections of objects which can include duplicates. These are called tuples and are provided by ISETL.) > t := [2, 3, 5, 2, 3]; > t; [2, 3, 5, 2, 3]; > 2 in t; true; > 1 in t; false; > #t; 5; > u := [1..20]; > u; ...; > #u; 20; > (#t computes the number of objects in the tuple t. t(i) is the ith object in the tuple t.) > t(2); 3; > t(3); 5; > [ t(k) : k in [1..#t] | t(k) mod 2 = 1]; [3, 5, 3]; > (The last expression forms a tuple whose objects are the objects in t which are odd integers. _____________________________________________________________ FUNCTIONS ISETL enables you to define functions. For example, suppose we wish to define g to be the quadratic function which takes a number x and produces the value x*x - 5*x + 6.) > g := func (x); >> return x * x - 5 * x + 6; >> end func; > (Now let's use this function.) > g(0); 6; > g(1); 2; > [ g(x) : x in [-2..2] ]; [20, 12, 6, 2, 0]; > (The tuple [20, 12, 6, 2, 0] equals [g(-2),g(-1),g(0),g(1),g(2)].) (We will now find all integers in the range [-10..10] which are solutions to the equation g(x) = 0.) > [x : x in [-10..10] | g(x) = 0]; [2, 3]; > (Now let's define a function which takes an integer greater than 1 and returns true or false depending upon whether it is prime.) > prime := func (x); >> return forall k in [2..x-1] | x mod k /= 0; >> end func; > (An alternative way of defining this function would be to replace the second line by >> return #{ k : k in [2..x-1] | x mod k = 0} = 0; Now we will use this function.) > prime (5); true; > prime (15); false; > [ x : x in [2..20] | prime (x) ]; [2, 3, 5, 7, 11, 13, 17, 19]; > (The following function takes an integer greater than 1 and returns the set of all primes less than or equal to that integer.) > set_of_primes := func (n); >> return { x : x in [2..n] | prime (x) }; >> end func; > (We may use this function to create sets of prime numbers.) > primes50 := set_of_primes (50); > primes50; ... ; > #primes50; 15; > primes100 := set_of_primes (100); > #primes100; 25; > (There are 15 primes less than 50 and 25 primes less than 100. Exercise 1: A prime pair is a pair of consecutive odd numbers which are both prime. For example, [11, 13] is a prime pair. Use ISETL to determine the number of prime pairs which are less than 100.) ____________________________________________ BINARY RELATIONS (A binary relation r on a set a is a set of ordered pairs of members of a. In the following, we define two relations r1 and r2 on a set a1.) > a1 := {1..5}; > r1 := { [1,1], [1,2], [2,3], [3,2], [2,1] }; > r2 := r1 + { [1,4] }; > (The inverse of a relation r is the set of ordered pairs obtained by reversing the order of the elements of the pairs in r; that is, a pair [x,y] is in the inverse of r if and only if [y,x] is in r. We will now write a function that produces the inverse of a binary relation r on a set a.) > inverse := func (r, a); >> return { [x,y] : x,y in a | [y,x] in r }; >> end func; (A relation is said to be symmetric if it is equal to its inverse.) > inverse (r1, a1); ... ; > inverse (r2, a1); ... ; > r1 = inverse (r1, a1); true; > r2 = inverse (r2, a1); false; > (Thus we see that r1 is symmetric but r2 is not. Exercise 2: The symmetric closure of a relation r on a set a is the smallest symmetric relation on a which contains r. For example, if a = {1, 2, 3} and r = {[1,1], [1,2]}, then the symmetric closure of r is {[1,1], [1,2], [2,1]}. Write an ISETL function which produces the symmetric closure of a given relation r on a. __________________________________________________________ RANDOM EVENTS AND SIMULATIONS ISETL can be used to simulate random events. The following function returns the result of selecting an integer at random from the set {1..n}.) > rand := func (n); >> return arb ({1..n}); >> end func; > (The next function simulates n tosses of a pair of dice.) > toss := func (n); >> return [ rand (6) + rand (6) : k in [1..n] ]; >> end func; > (Let's use this function to simulate 36 tosses of a pair of dice.) > results := toss (36); > results; ... ; > #[ results (k) : k in [1..36] | results (k) = 7 ]; ... ; > (The last expression counts the number of 7's which occurred in the 36 tosses.) Let's generalize this by defining a function which produces an ordered sample obtained by selecting n objects at random, with replacement, from a set p.) > sample := func (n, p); >> return [ arb (p) : k in [1..n] ]; >> end func; > (The following function determines whether there are duplicate values in the tuple t.) > nodups := func (t); >> return #t = #{ k : k in t }; >> end func; > > tup := [2, 3, 4, 2, 4]; > set := { k : k in tup }; > set; {2, 3, 4}; > #set; 3; > #tup; 5; > nodups (tup); false; > tup2 := [2, 4, 7, 6]; > nodups (tup2); true; > (Suppose 10 numbers were selected at random, with replacement, from the set {1..20}. What is the probability that the 10 numbers are distinct? We could simulate this experiment in probability in ISETL. The following expression has value true if the numbers are distinct and has value false otherwise.) > nodups (sample (10, {1..20})); ... ; > (Exercise 3: Give an ISETL expression that simulates the experiment of examining a class of 35 students and determining whether or not two (or more) students share a common birthday.)