Comp 210 Lab 4: define-structure, some Unix basics

Index: define-structure, Unix basics

This week's lab is primarily more about data definitions. In particular, we'll introduce another piece of Scheme that helps us represent data structures and build our data definitions.

pairs

How would you represent a "pair" in Scheme? So far, we would have represented it as a two-element list. Well, that seems kind of strange:

• A two-element list contains a null as an end-marker, which we don't need because we know we'll have exactly two elements.
• Accessing the second element is more difficult than the first, i.e., compare (car (cdr pair)) vs. (car pair), respectively.

First, congratulations you have graduated to DrScheme's "intermediate" language level! What we will be introducing isn't allowed in the beginner level. In DrScheme, select Configure Language Level from the Language Level menu. Choose Intermediate from the resulting menu. Restart DrScheme.

OK, back to pairs. What do we care about pairs. More importantly, they contain exactly two elements. Also, it would be nice to have helper functions like Scheme provides for numbers, lists, etc.:

• constructors, like cons, and
• predicates, like cons?,
• selectors, like car and cdr

Scheme gives us a way to define all of that at once: (define-structure (pair first second)). This defines several functions:

• make-pair, which takes two arguments and returns a "pair" of those arguments (constructor),
• pair?, which takes one argument and returns whether that it a "pair" (predicate), and
• pair-first and pair-second, which each take one argument, a "pair", and returns the appropriate element of it (selector).

Binary numbers

For another example, consider our data definition for binary number: a list of bits is one of

1. null,
2. (cons 0 bits), where bits is a list of bits, or
3. (cons 1 bits), where bits is a list of bits.

Rather than thinking of a binary number as a list of bits, let's consider it its own entity: a binary number is one of

1. no-number
2. (make-bit0 number), where number is a binary number, or
3. (make-bit1 number), where number is a binary number.

; defines make-no-number, no-number?
(define-structure (no-number))
; define the one unique no-number
(define no-number (make-no-number))

; represents binary number with 0 at right end
; defines make-bit0, bit0?, bit0-rest
(define-structure (bit0 rest))

; represents binary number with 1 at right end
; defines make-bit1, bit1?, bit1-rest
(define-structure (bit1 rest))

But what's that (define-structure (nonumber))? It doesn't have any arguments! It defines, among other things, a function make-no-number such that calling it with no arguments, (make-no-number), results in a value representing no number.

But where did the 0 and 1 data values go? We don't need them, since we added that information into the function names!

So what's the template for a function that takes a binary number?

(define bn-fun
   (lambda (bn)
      (cond
         ((no-number? bn) ...)
         ((bit0? number) ...(bn-fun (bit0-rest number)...))
         ((bit1? number) ...(bn-fun (bit1-rest number)...)))))

Details for everyone

If you have downloaded DrScheme onto your PC/Mac, it does not recognize (define-structure (foo a b)). Instead, it recognizes (define-struct foo (a b)).

For more ideas on how to use define-structure, read about data definitions.

Don't test structures with eq? (at least for now), use only the structure's predicates!

Even more details for those who really want to know

For all intents and purposes, lists are just built-in structures. The following defines things just like the built-in lists:

(define-structure (cons car cdr))
(define cons make-cons)
;cons? already defined by define-structure
(define car cons-car)
(define cdr cons-cdr)

(define-structure (null))
(define null (make-null))    ; define the value from the 0-ary constructor
;null? already defined by define-structure

Hmmm, doesn't that cons structure definition look just like the pair's? Well, that's because conses are really just pairs after all -- the second element doesn't have to be a list. But when we use cons and null together in the appropriate way, we call the result a "list", rather than a bunch of nested pairs.

Now for a quick intro to a handful of Unix basics...

Unix keeps each of your files in a directory. Directories may themselves be nested in other directories. (Directories are just special kinds of files.) Directories are just the same thing as Windows/Mac folders. At any point, you (or more accurately, each xterm) is in a specific directory, your working directory. Each directory contains itself, always named . (a period) and its parent, always named .. (two periods). The top root directory is called / (a slash).

• pwd prints the path (see below) of your current working directory.
• cd path changes your working directory to that specified.
• ls path lists the files in the the specified directory. If no path is given, it lists the files in the current working directory.

A path is a name for a file. A path can be relative or absolute. A relative path names a file relative to your current working directory. An absolute path give the total name for the file.

• foo.ss is a relative path to a file in your current directory.
• ../foo.ss is a relative path to a file in the parent of your current directory.
• /bin an absolute path to a subsdirectory of the root directory.
• ~comp210/public_html is a path to a subdirectory of the home directory of comp210.

When you type a command, e.g., drscheme, Unix searches a variable (PATH) that contains a list of paths to look in to find that program. One of the things that register comp210 did for you was to add things to your PATH.

• printenv prints your environment variables, including your PATH.

Commands/programs take arguments telling them what to do. E.g., register comp210 told the register program to add you to this course. Some of you also used the program to register for other courses.

You will need to manipulate files in various ways.

• mv oldpath newpath moves a file from one location to a new one.
• cp oldpath newpath copies (duplicates) a file from one location to a new one.
• rm path removes (deltes) a file.
• more path displays the contents of a file, a screenful at a time.

We will occasionally cover more Unix basics. For more info, refer to Owlnet handouts available in Mudd or just ask around. Also use the online (terse) manual pages:

• man program gives information about the specified Unix program.
• man -k keyword looks for a manual page related to the keyword.