Black Box 4/BlackBox.cdr/proglang/isetl.arj/TUTORIAL.TXT

Text File | 1989-10-05 | 12KB | 451 lines

Introduction to ISETL  (March 1989)
                       (Modified October 5, 1989)

Prepared by Murray Kirch
            Professor of Computer Science and Mathematics
            Stockton State College
            Pomona, NJ 08240
            [phone]
            E-MAIL: [e-mail]




--> 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 on this typescript 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.  We will assume your ISETL
disk is in drive A and we have a system prompt for that drive.
Enter ISETL.)


a> isetl
...
>

(If, at any time, you wish to leave ISETL, type !quit .)

(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.)

>       4 + 5;
9;
>

(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.

ISETL 2.0 does provide editing capabilities but they are not needed
for this tutorial.)


>>      !clear
!clear complete
>

>       4
>>      +
>>      5
>>      ;
9;
>       4 = 3 + 1;
true;
>

(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;
>

(Assignment statements in ISETL are similar to those in Pascal.)

>      x := 1 + 3;
>      x;
4;
>      b := 2 < 5;
>      b;
true;
>

(A set is an unordered collection of objects.)

>      s := {1, 4, 5};
>      s;
{1, 4, 5};
>      s := {1..20};
>      s;
...
>

(The last assignment statement assigns to s the set of all integers
from 1 to 20, inclusive.  When the value of a set is displayed, the
order of the elements is unpredictable.

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.

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.

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};
>

(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 };
...;
>

(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.

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.)

(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.

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.)

(While in ISETL, it is possible to enter text from either the
terminal or from a disk file.  For example, there is a file on the
ISETL disk named math.stl  which defines the functions g,
prime, set_of_primes, inverse, rand, toss, sample, and nodups as
described in this tutorial.  This file also assigns values to the
identifiers squares, t, u, primes50, primes100, a1, r1, r2, results,
tup, set as described previously.  To enter these definitions from
the disk file, type the following command.)

>      !include math.stl
!include math.stl completed
>

(Also defined in math.stl is a function called answer.
After including math.stl, you may find the answer to
Exercise k by typing answer (k).)

>      answer (1);
... ;
>

(To exit ISETL, type !quit)

>      !quit

(You will then be asked to confirm that you really want to quit.
Type Y to return to the system prompt or N to stay in ISETL.)

a>


(This tutorial covers only a small subset of ISETL.  An example
of a func which takes as input two funcs and returns a func appears
in MATH.STL.  The .LPR files which are distributed with the ISETL
interpreter provide a complete description of the language and
instructive examples.)

                        REFERENCES


Baxter, Nancy et al., Learning Discrete Mathematics with ISETL.
New York: Springer-Verlag, 1989.

Schwartz, J. T. et al., Programming with Sets: An Introduction to
SETL. New York: Springer-Verlag, 1986.