Com S 342 --- Principles of Programming Languages HOMEWORK 0: GETTING STARTED (File $Date: 1998/09/03 19:50:29 $) Due: problems 1-2, 4a at beginning of class, August 28; problems 7, 9 at beginning of class, August 31; problem 10 at beginning of class, September 4; problems 12-15, 17, 19 at beginning of class, September 9. In this homework, you will get around a bit on the Com S department machines, send us vital information about your login, recall (or learn) the basics of Scheme, and learn some basic terms and ideas about programming languages. For code hand in *both* your printout of the code and a transcript of testing; handwritten code is *not* acceptable unless the problem specifically states otherwise. The section headings below give the readings related to the problems. COURSE POLICIES AND PROCEDURES (HANDOUT) section 3.6 1. (10 points) a. If you haven't done this already, obtain a Com S department user account. To do this, go to the ``Unix Account Activation Terminal'' in 116 Atanasoff Hall. Then follow the directions on that terminal to get your account. If you have problems with this, contact the System Support Group (ssg@cs.iastate.edu) at 294-0179 or go to their office in 108 Atanasoff Hall. If you cannot complete this by the due date, let us know you are having problems, and hand this problem in as soon as you get your account. b. Send email to your TA with the subject "HW0, my information" Put in the body of the message the following information: your family name, your given name, the last 6 digits of your University ID number (i.e. your social security number), your Com S login name, your local phone number (if you have one), and time of the discussion/lab section for which you are registered. The format should look like the following example Family Name Given Name Last 6 of ID login Phone Discussion Sect Leavens, Gary 123456 leavens 294-1580 R 3 We will use this information for grading reports, class lists, and as a means to contact you. (We won't let anyone see your phone number except the course staff.) Also write a list of the languages that you have programmed with previously. Use a format like the following example, but change the list to match your actual experience. I have programmed in: APL, Ada, Algol W, BASIC, C, C++, CLU, COBOL, Cecil, FORTRAN, Haskell, Java, LISP, LambdaProlog, OBJ3, PL/1, Pascal, Perl, Prolog, SML, SNOBOL, SR, Scheme, Smalltalk, IBM 360 Assembly language, DEC VAX Assembly Language. We will use your list to help us plan the course better, and to tie the course material to your previous experience. Please omit any language you would not feel comfortable programming in. 2. (20 points) This problem is about the course directory structure and the course documents in the docs directory. You need to log in to a Com S department machine to do it. Write brief answers to the following questions on a piece of paper and hand them in. a. Change to the directory /home/course/cs342/public. What are the names of the directories in /home/course/cs342/public? b. One of the directories in /home/course/cs342/public is called docs. Change to that directory. What is in the file ``running-scheme.txt''? (Just give a general description in one sentence.) c. In what file in /home/course/cs342/public/docs are the office hours for the course? What are the office hours of your TA? d. What is in the file ``printing.txt''? e. What is in the file ``getting-to-coms.txt''? f. What is in the file ``policies-complete.txt''? g. Are you eligible for makeups on tests if you don't turn in homework, and attend the lectures and your discussion sections? Where does it say that? h. What is the late policy for homework? Where does it say that? i. How is extra credit work used in grading? Where does it say that? j. How should extra credit be turned in? Where does it say that? The rest of this homework is found in the file /home/course/cs342/public/homework/hw0.txt You should work on-line from this file. You might want to print a copy if you'd rather have it in front of you. 3. (suggested practice) a. Read, or print and read the file /home/course/cs342/public/docs/policies-complete.txt. b. If you are new to Scheme, print out your own copy of the file /home/course/cs342/public/docs/running-scheme.txt c. If you are new to Iowa State or our computer systems, print your own copy of /home/course/cs342/public/docs/getting-to-coms.txt 4. Read the file ``/home/course/cs342/public/docs/reading-news.txt''. Following the instructions, read the news for our class (in the newsgroup isu.coms.342). There should be a message whose subject is: ``The message for HW0''. You can handwrite your answers to the following. a. (5 points) Summarize, in a sentence or two of your own words, the idea of what the quotation in the message is saying. b. (5 points extra credit) If you've had Com S 331 already, using the appropriate technical terms from that course, restate the ideas from the quotation in the message. Hint, describe in terms of the type of grammar (e.g., context sensitive, context free, regular, unrestricted) and the corresponding automata (e.g., linear-bounded, push-down, finite state, Turing machine). 5. (10 points extra credit) You can handwrite your answers to the following. a. What kind of grammar corresponds to the devices in the newsgroup message for problem 4 above? b. What kind of grammar will be of the most importance in Com S 342? 6. (suggested practice) Read the newsgroup isu.coms.342 fairly often. 7. (10 points) This is to help configure your account for the course. a. To avoid retyping the name of the course public directory, /home/course/cs342/public, you'll need to use an abbreviation for it. Put the following line in your ~/.login file, so that when you type $PUB in the shell it expands to /home/course/cs342/public setenv PUB "/home/course/cs342/public" To see this working, you'll have to log out and then log back in. Do that, then try the following command, to demonstrate that it's working. ls $PUB b. To access the programs in the course directory /home/course/cs342/public/bin easily, put the following line in your ~/.login file setenv PATH ${PATH}:/home/course/cs342/public/bin Then log out and log back in for this to take effect. c. To use the ascii editor ``emacs,'' as we encourage you to do, put the lines from $PUB/docs/sample-.emacs at the end of your file ~/.emacs. If you don't already have a file ~/.emacs, then this can be done easily by typing the following command to the Unix shell: cp $PUB/docs/sample-.emacs ~/.emacs (You must do this, even if you don't (currently) use emacs. It will help us if you come to us for help with homework.) d. Print your files ~/.login and ~/.emacs and hand them in. (These have to be printed on a printer, preferably a Com S department printer.) 8. (suggested practice) To make life easier on the Com S Unix machines, you may want to personalize your environment by doing the following. a. To save yourself retyping information about the class for assignments, make a file ~/.me containing ;;; Name: ;;; Section: where you fill in the information following the colons as appropriate. (Your section should be the number and time.) b. The file ~/.cshrc can be used to customize the Unix (c)shell. Create this file and put in it the following line. alias rm 'rm -i' Make sure the file ends in a newline. This says to make the rm command (for removing files) always ask for confirmation; it may save your neck sometime. This makes pwd give you shorter strings. If you are a DOS user, you can put other lines in the file to alias your favorite DOS commands to their Unix equivalents. For example, you might want to use the following. alias dir ls alias copy cp alias rename mv c. The news readers on Unix, and some other programs use a file named ~/.signature. Create a file .signature in your home directory. It should contain your street address, your e-mail address, and (if you wish) your phone number. It should be no more than 4 lines long. d. For more information about details of using the Com S department machines, such as how to forward your mail to/from project Vincent, how to get your files to/from Vincent (use ftp), how to customize your X windows or how to display X windows stuff from a Vincent workstation, use the program ``netscape'' or ``mosaic'' on a Com S department workstation (or use the URL ``http://www.cs.iastate.edu/'') and click on the topic ``How Do I Do That'' in the first list of things, and then when you're in that page, click on the topic ``CS user FAQ'' (which is under the subheading ``Questions and Answers''). (The exact URL is ``http://www.cs.iastate.edu/help/faq.html''.) ESSENTIALS OF PROGRAMMING LANGUAGES: CHAPTER 1 and RUNNING SCHEME file See the file $PUB/docs/running-scheme.txt for details about running scheme. 9. (5 points) In this problem you will edit and run a simple scheme program. You will hand in a printout of the program when you are done. Create a file, let's call it ``simple-interp.scm'' (leave off the quotes), using emacs. In the file place the following Scheme procedure definitions, filling in your own name and section information (see problem 8a above). ;;; Name: ;;; Section: (define simple-interp ; TYPE: (-> () void) (lambda () ; EFFECT: prompt, read, interpret, and print values of expressions ; using the syntax: ; ::= | ( ) ; ::= + | - | * (display "Expression? ") (let ((exp (read))) (if (and (symbol? exp) (eq? exp 'quit)) (displayln 'Bye) (begin (displayln (interp exp)) (simple-interp)))))) (define interp ; TYPE: (-> (expression) number) (lambda (exp) ; ENSURES: result is the value of exp (cond ((number? exp) exp) ((and (list exp) (eq? (car exp) '+)) (+ (interp (cadr exp)) (interp (caddr exp)))) ((and (list exp) (eq? (car exp) '-)) (- (interp (cadr exp)) (interp (caddr exp)))) ((and (list exp) (eq? (car exp) '*)) (* (interp (cadr exp)) (interp (caddr exp)))) (else (error "bad expression: " exp))))) Now start up scheme at the unix prompt. Note: For this problem, you will need to load the procedure `displayln' since it is used above and is not a built-in procedure in Scheme. If problem 7b above has been completed properly, then the easiest way to load this procedure is by typing the command `scm342' at the unix prompt. This starts the SCM Scheme interpreter and automatically loads the `displayln' procedure (among other things that will be needed during the course). If `scm342' does not work, then your path has not be set up properly in problem 7b. If you wish to see the `displayln' procedure or to load it manually then it can be found in the public directory for the course in the following file: ``/home/course/cs342/public/lib/displayln.scm'' (end Note) In the scheme interpreter you can play with expressions. For example, if you type lines like the following: 'car (car (list 3 4 5)) something happens. (Try these.) Get out of the Scheme interpreter by typing the following: (exit) Now make a transcript. At the shell prompt in Unix (often %), type the following. script simple-interp.out this should start a new shell, after giving you a message like ``Script started, file is simple-interp.out''. Then type the command to start the interpreter scm342 Type in to Scheme comments to identify yourself: ; Name: ; Section: After typing the last two lines above, which are comments, Scheme won't prompt you (as it doesn't consider a comment to be real input). You can just keep typing, or enter an expression, such as 342 to get it to prompt you again. Now type (load "simple-interp.scm") to load in the code that you wrote in the file ``simple-interp.scm''. If you get an error, go back emacs, correct the file, and write it out again. Then do (load "simple-interp.scm") again. Now call the procedure simple-interp by typing (simple-interp) in this case, we'll ignore the warning you get from the type checker WARNING: this may have a type error... but here we go... and proceed to, when prompted, enter an expression such as (+ 3 4), (+ 5 (* 7 8)), or the word ``quit'' (without the quotes). When you are finished, exit Scheme by typing in the following line: (exit) Then stop the transcript by typing at the shell prompt: exit You should see a message like ``Script done, file is simple-interp.out'' that tells you that the shell is no longer making a transcript on the file ``simple-interp.out''. Hand in a printout of your files ``simple-interp.scm'' and the transcript ``simple-interp.out''. Note (other ways to do transcripts): if you are not using our Unix systems, you can produce a transcript in other ways. One way is to run Scheme from inside emacs (use M-x run-scheme), then write out the emacs buffer. Another is to run Scheme from within a terminal window and to copy and paste the output into a file. If all else fails you can use the transcript-on and transcript-off procedures in Scheme, but these seem to make slightly jumbled transcripts when used with our typed interpreter. To do this, start the transcript by using (transcript-on "simple-interp.out") and when you are done use (transcript-off) before calling exit. 10. (90 points) If you have not programmed in Scheme before, you must do the following, which will be of help in learning Scheme. You may also want to read in ``The Little LISPer'' (on reserve) p. xiii and chapters 1-4 (especially 1 and 4). Read section 1.1 and 1.2 in the text also! a. (5 points) Translate the following algebraic formulas into Scheme's notation. Check them with the Scheme interpreter. (4 * 7) - (13 + 5) (3 * (4 + (-5 - -3))) (2.5 / (5 * (1 / 100))) For example, translating (7 - (4 - 5)) into Scheme's notation yields (- 7 (- 4 5)). b. (5 points) Describe in words how to translate an algebraic formula into Scheme's notation. (This can be handwritten.) IMPORTANT: Make a transcript for parts c, e, f, g, i, k, l. *No credit* will be given without a transcript. These may be combined into one transcript, but each problem should be clearly labeled and they should be in order. The TA will deduct points (up to 30%) if there is any difficulty in finding and reading your solutions. c. (5 points) Give definitions of the variables e and pi in Scheme, so that they correspond to the usual values (2.73... and 3.14...). d. (5 points) How is an if-expression different in Scheme from an if-statement in a language like C++ or Pascal? (This can be handwritten.) Hint: The syntactic differences are not important here. The question is asking about the semantic differences, i.e., what is different about the way they behave. e. (5 points) Write an expression in Scheme that uses both variables e and pi, and that has as its value the larger of the two variables. Write a similar expression that has as its value the smaller of the two. f. (5 points) Without using an if (or cond) expression, write an expression that uses both variables e and pi, and that has as its value #t if the values of e and pi are equal, and #f otherwise. g. (5 points) Experiment with ' (quote) in the Scheme interpreter, and then answer the following question. (Try 'e, '+, '(+ 3 4), and unquoted versions of expressions.) What does ' do? h. (5 points) What can you do with a string in Scheme that you can't do with a symbol? Why is there a distinction between strings and symbols in Scheme? i. (5 points) Using *only* the Scheme procedure 'list', and numbers and quoted symbols (such as '+, 'sentence, and 'np), write Scheme expressions to make the following lists. Check them with the Scheme interpreter. (1 2 3) (+ 3 (- 4 2)) (sentence (np (noun apple)) (vp (verb sells) (object it))) For example, to make the list (3 (5)), one can use the expression (list 3 (list 5)). j. (5 points) Draw box and pointer diagrams, as in Figure 1.2.1, for the above lists. k. (10 points) Using only the Scheme procedure cons, numbers, quoted symbols (such as '+, 'sentence, and 'np), and the empty list ('()), write Scheme expressions to make the lists in part i above. For example, to make the list (3 (5)), one can use the expression (cons 3 (cons (cons 5 '()) '())) l. (5 points) Suppose we are in a procedure in which the variable lst is bound to a list of numbers. For example, it might be that lst is the list (3 4 2). Write an expression that uses lst and makes the lists (5 3 4 2) (6 5 3 4 2) (4 2) (2) You can check your answer on the computer by first typing (define lst (list 3 4 2)) m. (5 points) Make a transcript showing that Scheme's car and cdr procedures do not change their arguments. n. (5 points) What are the differences between a vector and a list in Scheme? What is a vector like in C or C++? How is a Scheme vector different than the corresponding feature in C or C++? o. (5 points) Do exercise 1.2.1 in the text. [car, cdr, cons transcript] Use the computer to check your work, but don't do this on the computer at first. p. (5 points) Do exercise 1.2.2 in the text. [eq? and sharing transcript] Use the computer to check your work, but don't do this on the computer at first. What you hand in should be handwritten for this problem. Note: There is a misprint in some copies of the text. The lines > (define x3 (cons x1 x2)) > x1 should be > (define x3 (cons x1 x2)) > x3 q. (5 points) Do exercise 1.2.3 in the text. [vector transcript] 11. (15 points; extra credit) Do exercise 1.3.1 in the text. [unusual expression] Use the computer to experiment. What you hand in should be a handwritten description of what the expression does, why that is strange, and whether it can be done without using list. 12. (3 points) Do exercise 1.3.2 in the text. [cell transcript] Use the computer to check your work, but don't do this on the computer at first. What you hand in should be handwritten for this problem. When checking your work, you needn't type the code in yourself, as you can find the code for this (and all other exercises and figures) in the file $PUB/eopl/sources.ss Have your editor search for ``;;; Exercise 1.3.2 : page 26''. 13. (5 points) a. Does C, C++, or Pascal impose any restriction on procedures that keeps them from being first-class? b. Can you create anonymous procedures at run-time in C, C++, or Pascal? c. What language are you answering for (C, C++, or Pascal)? 14. (10 points) [currying] Write Scheme code to define curried versions of the following procedures, calling the curried versions make-is-c and apply-to-each-c. (define make-is ; TYPE: (-> (symbol symbol) (list symbol)) (lambda (who what) (list who 'is what))) (define apply-to-each ; TYPE: (-> ((-> (S) T) (list S)) (list T)) (lambda (f ls) (map f ls))) The type of make-is-c should be: (-> (symbol) (-> (symbol) (list symbol))). When tested, your answers should behave as follows. typed> (define scheme-is (make-is-c 'scheme)) scheme-is: (-> (symbol) (list symbol)) typed> (scheme-is 'good) (scheme is good): (list symbol) typed> (scheme-is 'fun) (scheme is fun): (list symbol) typed> ((make-is-c 'c++) 'hard) (c++ is hard): (list symbol) typed> (define add1-to-each (apply-to-each-c (lambda (x) (+ x 1)))) add1-to-each: (-> ((list number)) (list number)) typed> (add1-to-each (list 3 4 2)) (4 5 3): (list number) typed> (add1-to-each (list 3 4 23 4 23 4 23 4 23 4 23 4 23 4 2)) (4 5 24 5 24 5 24 5 24 5 24 5 24 5 3): (list number) 15. (5 points) What's one use of a curried procedure? (Write a brief answer in English. This can be handwritten.) 16. (5 points; extra credit) Do exercise 1.3.4 in the text. [curry2] For this, hand in a printout of a file containing your procedure curry2, labeled with your course information (as in problem 8a above), and a transcript of your testing. 17. (5 points) Do exercise 1.3.5 in the text. [compose-c] Call your procedure compose-c. It should have the following type. (-> ((-> (T) U)) (-> ((-> (S) T)) (-> (S) U))) Make a transcript of your testing. 18. (15 points; extra credit) Do exercise 1.3.6 in the text. [automatic currying] (Check the errata in $PUB/docs/eopl-errata.txt if you have an old book.) 19. (5 points) Write a procedure, num-args, that returns the number of arguments with which it is called. For example (num-args 1 2 3) ==> 3 (num-args 'a 'b) ==> 2 (num-args 'a) ==> 1 (num-args) ==> 0 Make a transcript of your testing. 20. (15 points; extra credit) Do exercise 1.3.7 in the text. [2 or 3 arg compose] For this, hand in a printout of a file containing your procedure compose, labeled with your course information (as in problem 8a above), and a transcript of your testing.