Exercises #4

1. Write the function mapping which implements extensionally defined functions. A function by extension is a function which is simply enumerated: the domain and range are fully specified, and the mapping between them indicated. A function defined via a table is defined extensionally; therefore, an array is a kind of extensional function. Consider the function defined by the table:

   file             -
   directory        d
   characterSpecial c
   blockSpecial     b
   fifo             p
   link             l
   socket           s

   which maps a long string to a one-character abbreviation. This function could be implemented with mapping as follows:

   mapping [list file directory characterSpecial blockSpecial fifo link socket] \e
           [list - d c b p l s] $x

   where $x is the actual parameter of the function. If $x happened to be directory, then mapping would return d.

   Why use mapping when you could simply define an array? For example, we could define:

   set mapping(file) -
   set mapping(directory) d
   set mapping(characterSpecial) c
   set mapping(blockSpecial) b
   set mapping(fifo) p
   set mapping(link) l
   set mapping(socket) s

   mapping has several nice properties: it doesn't require any state (say, a global array), which is an advantage if the mapping is only used once; it can also be profitably partially applied for use with functionals like map. You can also think of mapping as implementing a linguistic feature that's missing from Tcl (and indeed from most languages): the array literal.

   The trade off is that since mapping is implemented with lists, it will be much slower than Tcl's associative arrays (but this will only matter for functions with a large domain).

   # mapping :: [alpha] X [beta] X alpha -> beta
   proc mapping {domain range parm} {...}
   mapping [list foo bar baz] [list 12 69 45] baz
   => 45
   map {mapping [list foo bar baz] [list 12 69 45]} [list baz baz foo bar foo]
   => 45 45 12 69 12

2. Write the function choose, which takes three parameters: three equal-length lists, the first two of arbitrary values, and the third a list of boolean values (zeros and ones). choose returns a list (also of the same length) where each element is chosen from one of the first two lists, depending on the corresponding boolean value. Elements of the first parameter are chosen for 1's (true), while elements of the second parameter are chosen for 0's (false).

   choose is one of many useful functions that operate on bit vectors.

   # choose :: [alpha] X [beta] X [boolean] -> [alpha U beta]
   proc choose {trues falses bools} {...}
   choose [list a b c d] [list A B C D] [list 0 1 1 0]
   => A b c D

3. Write the function bits which takes two parameters, both numbers, and returns a binary representation of the first number as a list of bits (each bit is a 0 or a 1), from most significant at the left to least siginifcant at the right. The result list should contain as many bits as specified by the second number, which should be an optional parameter, using leading zero bits if necessary (assume that the bit length requested is long enough to represent the number). If the second parameter isn't specified, use the minimal number of bits (no leading zeros).

   You'll probably want to use the expr command's bit-fiddling operators for this.

   # bits :: num X num -> [boolean]
   proc bits {howmany num} {...}
   bits 0777
   => 1 1 1 1 1 1 1 1 1
   bits 0644
   => 1 1 0 1 0 0 1 0 0
   bits 19
   => 1 0 0 1 1
   bits 1 3
   => 0 0 1

4. Write the function rwx, which takes a three-bit number -- a Unix user, group, or other file permission vector -- (represented as an ordinary Tcl number, in decimal, octal or hex) and returns a string which is the rwx string representation of that bit vector.

   # rwx :: num -> string
   proc rwx {perm} {...}
   rwx 7
   => rwx
   rwx 6
   => rw-
   rwx 2
   => -w-
   rwx 1
   => --x

5. Write the function ls-line, which takes a file name as a parameter and returns a string, a single line which is formatted to look like the output of the Unix command ls -lgd.

   You do not have to get the modification date to match the ls output exactly; nor do you have to worry about any of the following (except for extra credit): sticky bit, setuid or setgid bit, major or minor numbers for character or block special files; symbolic links.

   # ls-line :: filename -> string
   ls-line {file} {...}
   ls-line .
   => drwxr-xr-x 2 keith keith 512 Aug 11 14:22 .
   ls-line /etc/passwd
   => -rw-r--r-- 1 root staff 5234 Aug 04 15:22 /etc/passwd
   ls-line /home/keith/dev/fifo
   => prw-r--r-- 1 keith keith 0 Mar 24 16:29 /home/keith/dev/fifo