From - Fri Oct 19 17:52:21 2001 Return-Path: Received: from cs.iastate.edu (leavens.cs.iastate.edu [129.186.3.47]) by css-1.cs.iastate.edu (8.9.0/8.9.0) with ESMTP id QAA02930; Fri, 19 Oct 2001 16:56:01 -0500 (CDT) Message-ID: <3BD0A165.7535F9C2@cs.iastate.edu> Date: Fri, 19 Oct 2001 16:55:49 -0500 From: "Gary T. Leavens" Organization: Department of Computer Science, Iowa State University X-Mailer: Mozilla 4.78 [en] (Win98; U) X-Accept-Language: en MIME-Version: 1.0 To: Daniel J Heck CC: Georgiy A Ushakov Subject: Re: Currying? References: <5.0.1.4.2.20011018211239.009f5980@gushakov.mail.iastate.edu> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Dan, Yes, I tkink George has answered your question. Let me know if you need more explanation. In the lecture notes, it's covered in the file basics/procedures.txt, or in the meeting outlines, in the file basics.txt. Both are available from the course web page. Georgiy A Ushakov wrote: > Dan, > > "currying" is the concept of partial application of functions. For example, > this is the uncurried version of add, it takes two arguments and returns > their sum. > > (define add-full > (lambda (arg1 arg2) > (+ arg1 agr2))) > > > (add-full 3 4) => (+ 3 4) => 7 > > (add-full 3) => error (two arguments are expected) > > The curried version of this function can be defined like this. > > (define add-curried > (lambda (arg1) > (lambda (arg2) > (+ arg1 arg2)))) > > > (add-curried 3 4) => 7 > > (add-curried 3) => (lambda (arg2) (+ 3 arg2)) -- we made a tool > > As you can see with add-curried you can partially apply it to the first > argument (3) and get a FUNCTION back that you can further apply to any > other argument. In the example above this function just adds a number to 3, > not very useful, but you get the idea. Hope it helps. > > George > > At 04:09 AM 10/18/01 -0500, you wrote: > >I swear I took notes on and understood the concept of currying when it > >was first presented in lecture. It seems that I cannot find my record of > >it, and it does not show up in the online lecture materials. If someone > >could describe, even in just one sentence, currying in a nutshell again > >to me, I would really appreciate it. > > > >This kind of question could have been easily prevented and I totally > >understand if you feel it's a waste of your time. > > > >Dan Heck > >CS 342 -- Gary T. Leavens Department of Computer Science, Iowa State University 229 Atanasoff Hall, Ames, Iowa 50011-1040 USA http://www.cs.iastate.edu/~leavens phone: +1-515-294-1580 From leavens@cs.iastate.edu Sun Oct 21 12:19:11 2001 Date: Sun, 21 Oct 2001 11:14:07 -0500 (CDT) From: Gary T. Leavens To: Daniel J Heck Cc: cs342s@cs.iastate.edu Subject: Re: has-type-trusted? Dan, On Sun, 21 Oct 2001, Daniel J Heck wrote: > I was looking in sym-exp-cooked.scm a little bit to try to understand > exactly what is going on in the tests in question #2. What exactly does > the has-type-trusted function do? Its implementation is not offered > anywhere in the files question #2 deals with, and (to my memory) it > hasn't been explicitly discussed elsewhere. Thank you. Things like this that are specific to the type checker are covered in the document defining our type notation in more detail. YOu can get to that from the course resources web page. But anyway, dynamically, (has-type-trusted T E) means the same thing as the expression E. Statically, the type system interprets (has-type-trusted T E) as an expression of type T, and doesn't check the expression E at all. So that effectively tells the type system "I know that E is supposed to have type T". It's used when the type system isn't smart enough to figure this out on its own. In this class you should never use has-type-trusted yourself. Gary T. Leavens Department of Computer Science, Iowa State University 229 Atanasoff Hall, Ames, Iowa 50011-1040 USA http://www.cs.iastate.edu/~leavens phone: +1-515-294-1580 From leavens@cs.iastate.edu Sun Oct 21 12:19:37 2001 Date: Sun, 21 Oct 2001 11:28:26 -0500 (CDT) From: Gary T. Leavens To: Daniel J Heck Cc: cs342s@cs.iastate.edu Subject: Re: Slight Typo Dan, Thanks for pointing that out to me. I'm fixing it... On Sun, 21 Oct 2001, Daniel J Heck wrote: > In problem #5, there is a very slight typo that nevertheless could cause > confusion : > > Using your solution from problem 4, define a procedure, > (deftype average-with-9-42 (-> (number) number)) > that takes a number, c, and returns the average > of 10, 42, and c. For example, > (average-9-42 0) ==> 17 > (average-9-42 3) ==> 18 > > The examples clearly show that the average is to be taken from 9, 42, and > c, but the description says 10, 42, and c. Just thought I'd point it > out. Thank you for your time. > > Dan Heck > CS 342 > Gary T. Leavens Department of Computer Science, Iowa State University 229 Atanasoff Hall, Ames, Iowa 50011-1040 USA http://www.cs.iastate.edu/~leavens phone: +1-515-294-1580 From leavens@cs.iastate.edu Sun Oct 21 12:23:51 2001 Date: Sun, 21 Oct 2001 11:38:54 -0500 (CDT) From: Gary T. Leavens To: Daniel J Heck Cc: cs342s@cs.iastate.edu Subject: Re: [HW3, problems 6 and 7] Typed or Not Typed? Dan, On Sun, 21 Oct 2001, Daniel J Heck wrote: > For those problems in HW #3 that involve re-writing something from HW#1 > or earlier, should we re-write and test them with scheme342typed in mind, > even if they were not originally type-checked? "Occurs-twice" is an > example of this. I just wasn't sure whether you wanted the use of the > type checker to become a standard from now on. Thanks. For this homework, we're pretty much only doing things for which the type checker works. I believe it should give you no trouble and would in fact be helpful for these problems. However, you aren't required to use the type checker for problems 6 and 7. Other problems for which use of the type checker is required are explictly noted in the problem. I don't believe we'll be requiring the type checker for everything in the future, although that remains to be seen somewhat. I'm still working on getting it to be helpful for later parts of the course... Probably what will happen is that it will be optional in most of the later parts of the course. Do you find it useful or a hindrance? Gary T. Leavens Department of Computer Science, Iowa State University 229 Atanasoff Hall, Ames, Iowa 50011-1040 USA http://www.cs.iastate.edu/~leavens phone: +1-515-294-1580 From leavens@cs.iastate.edu Sun Oct 21 12:36:07 2001 Date: Sun, 21 Oct 2001 12:29:47 -0500 (CDT) From: Gary T. Leavens To: Daniel J Heck Cc: cs342s@cs.iastate.edu Subject: Re: Another Question [HW3, problem 2] Dan, On Sun, 21 Oct 2001, Daniel J Heck wrote: > The problem statement for #2 says the following : > > Hint: you may want to look at the code of the two procedures for > subst-sym-exp.scm in these two files. Yes, that's a mistake, it should read: Hint: you may want to look at the code of the two procedures subst-in-symbol-expression and subst-sym-exp in these two files. > I think I understand what this refers to. I have looked inside 1.scm and > subst.scm, which have procedures subst-in-symbol-expression and > subst-sym-exp, respectively. [...] > I think I can use it to explain what's going on, but the > filename "subst-sym-exp.scm" threw me off, because there is no such thing > in $PUB/lib. Thank you for your continued patience and help. Sorry about that. Yes, the files in question are 1.scm and subst.scm. Gary T. Leavens Department of Computer Science, Iowa State University 229 Atanasoff Hall, Ames, Iowa 50011-1040 USA http://www.cs.iastate.edu/~leavens phone: +1-515-294-1580 From leavens@cs.iastate.edu Sun Oct 21 12:43:47 2001 Date: Sun, 21 Oct 2001 12:38:49 -0500 (CDT) From: Gary T. Leavens To: Daniel J Heck Cc: cs342s@cs.iastate.edu Subject: Re: Interface/Implementation [re problem 2 on HW3] Dan, On Sun, 21 Oct 2001, Daniel J Heck wrote: > I want to make sure that I understand the material we are working with > lately, and what section 2.1 in the book says about data. > > Would it be correct to say that, in the context of some of the homework > we have done so far, the interface for a data abstraction includes mainly > deftype expressions, and that the implementation is the code supporting > those expressions? Yes, although I would also include whatever specifications in the form of comments and test cases are given in the interface. But essentially, its the names and types of the operations. Gary T. Leavens Department of Computer Science, Iowa State University 229 Atanasoff Hall, Ames, Iowa 50011-1040 USA http://www.cs.iastate.edu/~leavens phone: +1-515-294-1580 From - Sun Oct 21 21:21:19 2001 Return-Path: Received: from cs.iastate.edu (larch.cs.iastate.edu [129.186.3.5]) by css-1.cs.iastate.edu (8.9.0/8.9.0) with ESMTP id VAA10707; Sun, 21 Oct 2001 21:18:18 -0500 (CDT) Sender: leavens Message-ID: <3BD381E0.E8D82F09@cs.iastate.edu> Date: Sun, 21 Oct 2001 21:18:08 -0500 From: "Gary T. Leavens" Organization: Department of Computer Science, Iowa State University X-Mailer: Mozilla 4.77 [en] (X11; U; HP-UX B.10.20 9000/735) X-Accept-Language: de,fr MIME-Version: 1.0 To: Aaron R Forsyth Subject: Re: HW3 - Prob 5 References: <5.1.0.14.2.20011021194035.00a86318@forsytha.mail.iastate.edu> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Aaron, Aaron R Forsyth wrote: > > I am having trouble with the average-with-9-42.scm. Every time I call > average3-c I get an error. I ran the test for average3-c and all tests > passed. I tried (((average3-c 1) 2) 3) and got a deftype error. This is my > deftype: > > (deftype average3-c (-> (-> (-> (number) number) number) number)) > > Is it way off or how do I call that function? Your deftype is wrong in two senses: it's not syntactically correct and it means the wrong thing when corrected. First, you have something that isn't syntactically correct, which is why it's complaining about the deftype. To correct just the syntax, you would write: (deftype average3-c (-> ((-> ((-> (number) number)) number)) number)) This is syntactically valid, and means a procedure that takes as an argument a procedure of type (-> ((-> (number) number)) number) and returns a number. The type (-> ((-> (number) number)) number) means a procedure that takes a procedure from numbers to numbers and returns a number. So although what I wrote above is syntactically valid, it's not right. What you want is a the type of a procedure that takes a number (not a procedure) and returns a procedure that takes a number and returns a procedure that takes a number and returns a number. That's quite a bit different. None of the arguments are procedures, it's only the results that are procedures. See the type notation description page available from the course resources web page for more about the notation. It's available at: http://www.cs.iastate.edu/~leavens/ComS342-EOPL2e/docs/typedscm_toc.html Does that help? -- Gary T. Leavens Department of Computer Science, Iowa State University 229 Atanasoff Hall, Ames, Iowa 50011-1040 USA http://www.cs.iastate.edu/~leavens phone: +1-515-294-1580 From - Sun Oct 21 21:29:54 2001 Return-Path: Received: from cs.iastate.edu (larch.cs.iastate.edu [129.186.3.5]) by css-1.cs.iastate.edu (8.9.0/8.9.0) with ESMTP id VAA10919; Sun, 21 Oct 2001 21:29:39 -0500 (CDT) Sender: leavens Message-ID: <3BD38489.26359A92@cs.iastate.edu> Date: Sun, 21 Oct 2001 21:29:29 -0500 From: "Gary T. Leavens" Organization: Department of Computer Science, Iowa State University X-Mailer: Mozilla 4.77 [en] (X11; U; HP-UX B.10.20 9000/735) X-Accept-Language: de,fr MIME-Version: 1.0 To: "D. Kaiser" CC: Chunrong Pan , Com_S_342 , Facundo Bromberg , Gary Leavens , George Ushakov , Dong-Shin Kim , Wen-Chieh Chang Subject: Re: correction to hw3 problem 7 in 342 References: <000c01c15a7e$73e437c0$d8f3b218@ames1.ia.home.com> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Doug, you wrote: > For Question #7, HW 3, should the vector-index problem work similar to > our HW 2, question 17... Exercise 1.15 part 6, p. 25 in the book? > It says it is from HW 1, question 18 ... Exercise 1.15, part 10 p. 25 > in the book. Thanks for pointing that out. I do want homework 3 problem 7 to be the same problem as homework 2, problem 18. This is similar to exercise 1.15 part 10, as you point out, but it's different in that we return -1 when the element is not in the list, whereas the one in the book returns #f in that case. So I really shouldn't have the problem refer to the book directly. But thanks for the correction. I have corrected the statement of the homework to refer to the right problem in homework 2. -- Gary T. Leavens Department of Computer Science, Iowa State University 229 Atanasoff Hall, Ames, Iowa 50011-1040 USA http://www.cs.iastate.edu/~leavens phone: +1-515-294-1580 From - Mon Oct 22 13:08:44 2001 Return-Path: Received: from cs.iastate.edu (leavens.cs.iastate.edu [129.186.3.47]) by css-1.cs.iastate.edu (8.9.0/8.9.0) with ESMTP id NAA28050; Mon, 22 Oct 2001 13:06:40 -0500 (CDT) Message-ID: <3BD4601C.B254CC15@cs.iastate.edu> Date: Mon, 22 Oct 2001 13:06:20 -0500 From: "Gary T. Leavens" Organization: Department of Computer Science, Iowa State University X-Mailer: Mozilla 4.78 [en] (Win98; U) X-Accept-Language: en MIME-Version: 1.0 To: Mark P Nessen Subject: Re: 342 question References: <5.1.0.14.2.20011022125236.00a93c70@mnessen.mail.iastate.edu> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Mark, Mark P Nessen wrote: > I'm having trouble with the typed scheme interpreter, scheme342typed. I'm > working on the hw and when I load my average3-c.scm, it type checks fine > and tests ok, but when I try to test it manually, it doesn't work. Here is > a sample of what I'm talking about: > typed> (load "average3-c.scm") > Type checking "average3-c.scm" ... > ... done type checking "average3-c.scm" > average3-c : (-> (number) number) Here's the problem. Your deftype for average3-c is wrong. So the type checker thinks it's just a procedure that takes a number and returns a number. But it should be a procedure that takes a number and returns a procedure that takes a number and returns a procedure that takes a number and returns a number. :-) So you just need to fix your deftype. > > loading average3-c.scm ... > Name: Mark Nessen > Section: A, Facundo > typed> (test-hw3 "average3-c") > loading /home/course/cs342/public/homework/hw3/average3-c.tst ... > > Test case of $Date: 2001/10/17 23:31:27 $ > > ... > (((average3-c 100) 5) 93) > ==> 66 > All tests passed! > > # : void This works because applications of average3-c are hidden from the type checker in quoted lists in the test cases. Also the type checker isn't doing a good job of comparing the types in deftypes and the types of the procedures. (This is a bug in the type checker I haven't had time to fix yet.) > typed> (((average3-c 0) 3) 6) > : line 3: Attempt to apply non-procedure > Not a procedure: (average3-c 0) > Inferred type : number > Skipping evaluation because of the type errors... > This problem happens because it's using the deftype to tell it what the type of average3-c is. > I get this similar problem when I try to load average-9-42.scm, it doesn't > type check. That would explain that also. -- Gary T. Leavens Department of Computer Science, Iowa State University 229 Atanasoff Hall, Ames, Iowa 50011-1040 USA http://www.cs.iastate.edu/~leavens phone: +1-515-294-1580 From - Mon Oct 22 13:09:53 2001 Date: Mon, 22 Oct 2001 10:44:32 -0500 (CDT) From: "Gary T. Leavens" To: Aaron R Forsyth cc: Com_S_342 Subject: Re: COMS 342: Re: correction to hw3 problem 7 in 342 In-Reply-To: <5.1.0.14.2.20011022082411.00a865a0@forsytha.mail.iastate.edu> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Aaron, Right, my mistake. Problem 7 on homework 3 should really refer to problem 17 on homework 2. Here's the corrected text of problem 7 on homework 3. 7. (10 points) [vector-index with letrec] Write the procedure, vector-index, from homework 2 problem 17 using "letrec" and tail recursion. Do not use Scheme's procedures vector->list or list->vector. You can run our the tests using (test-hw2 "vector-index") Use of the type checker is optional for this problem, although it should work fine and may be helpful to you. Thanks for pointing out my mistake. I'm sorry for the confusion. Gary T. Leavens Department of Computer Science, Iowa State University 229 Atanasoff Hall, Ames, Iowa 50011-1040 USA http://www.cs.iastate.edu/~leavens phone: +1-515-294-1580 From leavens@cs.iastate.edu Tue Oct 23 09:56:36 2001 Date: Tue, 23 Oct 2001 09:51:56 -0500 (CDT) From: Gary T. Leavens To: Mark P Nessen Cc: Com_S_342 , cs342s@cs.iastate.edu Subject: Re: 342 question about homework 3, problem 9, quote-exp->symbol Mark, On Mon, 22 Oct 2001, Mark P Nessen wrote: > I'm working on problem 9 and am having some trouble. I have most of it > figured out, but in part b, when trying to return the var-exp x from the > last expression, ((lambda (x) (f x)) (quote x)), I'm getting an > error. This is what I have: (quote-exp->symbol (app-exp->rand e)) where i > have defined e as follows: (define e (app-exp d (quote-exp 'x))) > e=((lambda (x) (f x)) (quote x)) : lambda-1+quote-exp > This is the error I get in the scheme342typed interpreter: > typed> (quote-exp->symbol (app-exp->rand e)) > ERROR: quote-exp->symbol: not a quote-exp: (quote x) There are two problems here. First, the code in the library was wrong. The code for quote-exp->symbol was testing for an app-exp instead of a quote-exp as you point out below. I have fixed the library code (just now). Second, in (quote x), the x is not a variable expression, but a mere constant. So the x you need to extract in this example is not the x in (quote x), but the one in (f x). > So, I have tried defining another variable, q, such that it is just a > quote-exp: > typed> (define q (quote-exp 'x)) > q : lambda-1+quote-exp > typed> q > (quote x) : lambda-1+quote-exp > > But when I do the following, it won't convert quote-exp->symbol: > typed> (quote-exp->symbol q) > ERROR: quote-exp->symbol: not a quote-exp: (quote x) > typed> (quote-exp? q) > #t : boolean > typed> (quote-exp? (app-exp->rand e)) > #t : boolean > > Something seems amiss. Am I doing something wrong? > I looked in the lambda-1+quote-exp.scm file, and this is what I found: > > (define quote-exp->symbol > (lambda (qe) > ;; REQUIRES: qe represents a quote-exp > ;; ENSURES: result is the operand in the representation of qe > (if (app-exp? qe) > (cadr qe) > (error "quote-exp->symbol: not a quote-exp:" qe)))) > > Now, it seems like quote-exp->symbol requires qe to be a quote-exp, but > instead you check to see if it is an app-exp. Yes, I had the wrong code in the library, but this has now been fixed. As you noted, the test should be for quote-exp?, not app-exp Gary T. Leavens Department of Computer Science, Iowa State University 229 Atanasoff Hall, Ames, Iowa 50011-1040 USA http://www.cs.iastate.edu/~leavens phone: +1-515-294-1580 From leavens@cs.iastate.edu Tue Oct 23 09:57:03 2001 Date: Tue, 23 Oct 2001 09:54:05 -0500 (CDT) From: Gary T. Leavens To: Daniel J Heck Cc: cs342s@cs.iastate.edu Subject: Re: Problem 9, part b On Tue, 23 Oct 2001, Daniel J Heck wrote: > I want to make sure I am understanding the problem statement correctly > for Problem 9, part b. > > It says: > > Using the helping procedures in lambda-1+quote-exp.scm, and > names you defined in part (a), make a transcript that shows an > expression that returns the var-exp x from each of the 5 > expressions in part a. > > Does this mean that our transcript should contain one expression that > returns x for ALL five cases, or one expression for EACH of the five, for > five total? I am pretty sure it is the latter, because the former would > involve quite a bit of manipulation with cond expressions and type-checking, > but I want to be sure. Yes it is the latter: 5 separate expressions, one for each of the 5 expressions in part a. Gary T. Leavens Department of Computer Science, Iowa State University 229 Atanasoff Hall, Ames, Iowa 50011-1040 USA http://www.cs.iastate.edu/~leavens phone: +1-515-294-1580 From - Tue Oct 23 18:17:39 2001 Return-Path: Received: from cs.iastate.edu (leavens.cs.iastate.edu [129.186.3.47]) by css-1.cs.iastate.edu (8.9.0/8.9.0) with ESMTP id SAA11150; Tue, 23 Oct 2001 18:12:03 -0500 (CDT) Message-ID: <3BD5F925.A0DADE2C@cs.iastate.edu> Date: Tue, 23 Oct 2001 18:11:34 -0500 From: "Gary T. Leavens" Organization: Department of Computer Science, Iowa State University X-Mailer: Mozilla 4.78 [en] (Win98; U) X-Accept-Language: en MIME-Version: 1.0 To: Gary Leavens , George Ushakov , Facundo Bromberg , Com_S_342 , Wen-Chieh Chang , Chunrong Pan , Dong-Shin Kim Subject: Revised due dates for 342 homework 3, type of equal? Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Hi, In our staff meeting today, we decided to revise the due dates for homework 3 in 342. Problems 17-19 will now be due on Tuesday, October 30, although there are still several problems due on Thursday. Also, someone gave feedback to me to suggest that the type checker should allow one to test obejects of different types for equality. Currently the type checker thinks that the type of equal? (and eq? and eqv?) is (forall (T) (-> (T T) boolean)) This is, as pointed out, more restrictive than necessary. Since Scheme does actually allow you to compare objects of different types for equality. But it doesn't work well for the type checker to allow this, because then the type checker would miss lots of common mistakes. In general, type checkers have to err on the side of being conservative, and reject some good programs in order to prevent bad ones from executing. I think the type of equal? falls into this area. That said, we'd also like to be able to execute programs that don't run into type errors at run-time to the extent possible. It turns out that the type checker does allow what you want to do at the price of rewriting your code using has-type. If you write (equal? (has-type datum 3) (has-type datum #f)) then the type checker is perfectly happy, and doesn't complain. Everything has type datum, and the type checker thus instantiates the type of equal as (-> (datum datum) boolean) and proceeds. This doesn't constrain the types of the two subexpressions. This would be more useful in cases like (equal? (has-type datum my-number-variable) (has-type datum my-boolean-var)) where we don't know the result ahead of time, of course. -- Gary T. Leavens Department of Computer Science, Iowa State University 229 Atanasoff Hall, Ames, Iowa 50011-1040 USA http://www.cs.iastate.edu/~leavens phone: +1-515-294-1580 From leavens@cs.iastate.edu Tue Oct 23 23:25:17 2001 Date: Tue, 23 Oct 2001 23:21:18 -0500 (CDT) From: Gary T. Leavens To: irl@iastate.edu Cc: Com_S_342 , cs342s@cs.iastate.edu Subject: Re: HW3, correction to bound.tst in $PUB/homework/hw3 Tony, I have now fixed this, by replacing the test for "bound" in $PUB/homework/hw3/bound.tst. I also checked and made small fixes to the dates in the other tests, although I don't think any others needed real changes. Anyway, if you're working from home, you'll need to download the test cases in $PUB/homework/hw3/ again. (If that's too much trouble, you can just edit the test in $PUB/homework/hw3/bound.tst and change all occurrences of lambda-1+quote to lambda-1+quote-exp.) Sorry about the problem; I thought I had tested all of these, but I must not have done that. My mistake. On Tue, 23 Oct 2001, Tony Irlbeck wrote: > I am currently working on gambit, with the > scheme342typed interpreter. I ran through the test > cases given in the homework and they worked fine but > when I try to run the test script it crashes out. > > typed> (bound? 'y (parse-lambda-1+quote-exp '(lambda > (x) (x (x y))))) > #f : boolean > typed> (bound? 'x (parse-lambda-1+quote-exp '(x > (lambda (x) (x (x y)))))) > #t : boolean > typed> (test-hw3 "bound") > loading > /home/course/cs342/public/homework/hw3/bound.tst ... > > Test case of $Date: 2000/10/05 02:51:23 $ > > > Error in open-input-file: error opening > "/home/course/cs342/public/lib/lambda-1+quote.scm": No > such file or directory. Gary T. Leavens Department of Computer Science, Iowa State University 229 Atanasoff Hall, Ames, Iowa 50011-1040 USA http://www.cs.iastate.edu/~leavens phone: +1-515-294-1580 From leavens@cs.iastate.edu Thu Oct 25 09:28:45 2001 Date: Thu, 25 Oct 2001 09:25:17 -0500 From: Gary T. Leavens To: Daniel J Heck Cc: Gary Leavens , George Ushakov , Facundo Bromberg , Com_S_342 , Wen-Chieh Chang , Chunrong Pan , Dong-Shin Kim Subject: Re: cond clauses with no else arm are expected to have type void, so use else Dan, Daniel J Heck wrote: > I found out what my problem was, but if you could post this (or > something like it) as an FYI to the other students I bet they'd > appreciate it. > > It seems that the type checker hates no-else cond statements. Apparently > it saw that, when my helper function called free-vars, free-vars could > return something unspecified (void), if the input was none of the four > types of lambda-1+quote-exp expressions. But, this makes no sense, > because it has to be one of those four. So, I simply shifted the last > case to an else instead of checking for it explicitly. > > Dunno if the type-checker was supposed to do this or not.... Thanks, yes, the type checker does, and is supposed to, treat cond expressions that have no "else" part differently than those that have an "else". Cond expressions that have no "else" can't be (statically) guaranteed to have a value, so they are pessimistically expected to possibly have no value, and thus each arm of the cond is also expected to have no value; i.e., in a no-else cond expression, the whole expression and each arm is expected to have type "void". The moral is: use an "else" if you know there are no other cases in a cond clause. (By the way, the same thing happens with an "if" expression that has only the true branch, and with case expressions.) Sorry for the confusion this has caused you. -- Gary T. Leavens Department of Computer Science, Iowa State University 229 Atanasoff Hall, Ames, Iowa 50011-1040 USA http://www.cs.iastate.edu/~leavens phone: +1-515-294-1580 From leavens@cs.iastate.edu Thu Oct 25 11:41:11 2001 Date: Thu, 25 Oct 2001 11:34:46 -0500 From: Gary T. Leavens To: Mark P Nessen Cc: Gary Leavens , George Ushakov , Facundo Bromberg Subject: Re: 342 - hw3, problem 14 Mark, Mark P Nessen wrote: > Prof. Leavens: > > In problem 14, I can't get the test cases to run. The problem says we are > to write free-vars-lambda+if-exp, but the deftype says (defype free-vars > ...). To test it, it says use > (test-hw3 "free-vars-lambda+if-exp") but I can't get it to work. This is > what I get: > > (load "free-vars-lambda+if-exp.scm") > loading free-vars-lambda+if-exp.scm ... > Name: Mark Nessen > Section: A, Facundo > Name: Mark Nessen > Section: A, Facundo > > (test-hw3 "free-vars-lambda+if-exp") > loading /home/course/cs342/public/homework/hw3/free-vars-lambda+if-exp.tst ... > > Test case of $Date: 2001/10/18 06:40:12 $ > > loading /home/course/cs342/public/lib/set-equal.scm ... > loading /home/course/cs342/public/lib/lambda+if-exp.scm ... > (free-vars (parse-lambda+if-exp 'x)) > > Error: variable free-vars is not bound. > Type (debug) to enter the debugger. > > Are we supposed to call out function free-vars or free-vars-lambda+if-exp? You're supposed to call it "free-vars". The heading in the problem is the point of confusion, I think. It said [free-vars-lambda+if-exp, bound-vars-lambda+if-exp], but the deftypes tell you the names you are supposed to use. I'm changing the heading. Call them free-vars and bound-vars. Sorry for the confusion. -- Gary T. Leavens Department of Computer Science, Iowa State University 229 Atanasoff Hall, Ames, Iowa 50011-1040 USA http://www.cs.iastate.edu/~leavens phone: +1-515-294-1580 From - Fri Oct 26 11:20:14 2001 Return-Path: Received: from cs.iastate.edu (leavens.cs.iastate.edu [129.186.3.47]) by css-1.cs.iastate.edu (8.9.0/8.9.0) with ESMTP id KAA23704; Fri, 26 Oct 2001 10:24:57 -0500 (CDT) Message-ID: <3BD98024.2966FCD2@cs.iastate.edu> Date: Fri, 26 Oct 2001 10:24:20 -0500 From: "Gary T. Leavens" Organization: Department of Computer Science, Iowa State University X-Mailer: Mozilla 4.78 [en] (Win98; U) X-Accept-Language: en MIME-Version: 1.0 To: Daniel J Heck CC: cs342s@cs.iastate.edu Subject: Re: Mixing Recursions? References: <200110261233.HAA04757@isua1.iastate.edu> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Dan, Daniel J Heck wrote: > I remember that one of the programming tips (rules?) presented in class > was to avoid mixing recursions. I have found what I think might be a > nifty solution to some parts of problem #14, but I'm not sure if it would > be ok with respect to this rule. Would you call the following an act of > mixing recursions? > > (deftype free-vars-in-lambda-exp (-> (lambda+if-exp) (set-of symbol))) > (define free-vars-in-lambda-exp > (lambda (expr) > (define lebody (lambda-exp->body expr)) > (define leids (lambda-exp->ids expr)) > (if (null? leids) > (free-vars lebody) > (if (set-member? (car leids) (free-vars lebody)) > (set-remove (car leids) > (free-vars-in-lambda-exp (lambda-exp (cdr leids) lebody))) > (free-vars-in-lambda-exp (lambda-exp (cdr leids) lebody)))))) > > This function recurs over itself to remove all bound variables from the > set of free variables in the lebody. The process of finding the set of > free variables is itself a recursion. These two processes don't > necessarily interfere with each other, and I found that coding it this > way was easier and more understandable than if I had used a helper function. > > (Of course, I haven't thoroughly tested this code yet, so it's possible > there are far more problems with it than mixing recursions, perhaps as > a result of mixing recursions.....) > > Am I guilty? Would I suffer a sentence of significant point loss if I > submitted it this way? Thank you for your input. This is an interesting question. First, I note that your code is essentially only a part of the recursion for lambda+if-exp for free-vars. You have separated it out into a helper, which makes this recursion of the formal parameter list not go through the main recursion in free-vars directly. Since your recursion on the formal parameter list only goes through the function free-vars-in-lambda-exp, this isn't technically a case of mixing recursions in one procedure. So I think it's not a problem from this respect. That said, I think you're making things more complex and hard to read than they need to be. First, I generally think it shouldn't be necessary for free-vars to call helpers for each production (the slogan is "one nonterminal, one procedure"). I think you can conceptualize the procedure differently to avoid that. Let's look at what's happening with free-vars-in-lambda-exp. In this case, what free-vars-in-lambda-exp is doing is stacking up pending compuations to remove elements from the set of free variables in the body. And it's doing it in an inefficient way, because you're computing free-vars for the body for each formal parameter in the lambda (to test for set-member?). One way to avoid this is to delegate much more responsibility to the set operations. In the first case, doesn't set-remove work both when the element is in the set and when it isn't? That is, doesn't (set-remove 'x (set 'y)) = (set 'y)? Yes, it does. So you don't need to test membership at all before removing. Just remove the formal from the set. This means that you don't need the inner if expression, and eliminates the inefficiency there: (define free-vars-in-lambda-exp (lambda (expr) (define lebody (lambda-exp->body expr)) (define leids (lambda-exp->ids expr)) (if (null? leids) (free-vars lebody) (set-remove (car leids) (free-vars-in-lambda-exp (lambda-exp (cdr leids) lebody)))))) Now, what free-vars-in-lambda-exp is doing is just removing each identifier in the list of formals from the set of free variables in the body. For example, if we have lebody = (parse-lambda+if-exp '(f x y z)) expr = (lambda-exp '(x y) lebody) then (free-vars-in-lambda-exp expr) = (set-remove 'x (free-vars-in-lambda-exp (lambda-exp '(y) lebody)))) = (set-remove 'x (set-remove 'y (free-vars-in-lambda-exp (lambda-exp '() lebody))))) = (set-remove 'x (set-remove 'y (free-vars lebody))) This suggests that what is really needed is a helping procdure that will remove all the elements of a list from a set. We could write that directly, but it's very similar to set-minus, if only we had a set formed from the formals instead of a list. But that is easy: (define list->set (lambda (ls) (apply set ls))) Well, okay, the above is a hack, but you can write it out the hard way without too much trouble... (define list->set (lambda (ls) (if (null? ls) the-empty-set (set-add (car ls) (list->set (cdr ls)))))) So now we can write: (define free-vars-in-lambda-exp (lambda (expr) (set-minus (list->set (lambda-exp->ids expr)) (free-vars (lambda-exp->body expr))))) And this is code that is short enough to go back in the body of free-vars. -- Gary T. Leavens Department of Computer Science, Iowa State University 229 Atanasoff Hall, Ames, Iowa 50011-1040 USA http://www.cs.iastate.edu/~leavens phone: +1-515-294-1580 From leavens@cs.iastate.edu Fri Oct 26 12:07:21 2001 Date: Fri, 26 Oct 2001 12:05:51 -0500 From: Gary T. Leavens To: Daniel J Heck Cc: Gary Leavens , George Ushakov , Facundo Bromberg Subject: Re: Interesting.... Dan, Daniel J Heck wrote: > I see what you mean by my code being inefficient, but I was thinking that > using types other than those documented in the problem statement was > unadvisable. No, especially since sets are used in the types of the arguments and results, you should think that maybe the set operations will be useful in writing the code. In any case, helping procedures should always be an option, and no one will ever tell you explicitly to think about them on the job... > After all, we are working to make our programs follow the > grammar, so set-ops, lambda-1+quote-exp, and lambda+if-exp should be all > we need. ... Using list->set, for me, is sort of 'thinking outside the > box...' > I will have to start doing that more often. Ok. I think that sort of thing is classic functional programming, since a mismatch between types is something that can often be solved by writing a helping procedure. I'm glad to hear you're starting to think about it. > Secondly, I do not understand why you are advising against breaking up > the functionality into one helper for each of the types in the grammar. > I thought that was part of what 'following the grammar' meant. As I did > earlier homeworks it became clear to me how often, especially in mutual > recursion, that the same pattern showed up that I have used here. I have > not showed you free-vars-in-var-exp, free-vars-in-app-exp, etc., but you > see what I mean. If I am on the wrong track in terms of grammatical > thinking, please clarify what I can do to change that. It's not wrong to do that, but I think it makes the code unnecessarily complex and thus harder to understand. It will also take longer to write (especially on a test!) because there is simply more of it. To me when you have a grammar with 1 non-terminal and 4 alternative productions (like lambda-1+quote-exp's grammar), this suggests that the code should have 1 procedure with 4 cond clauses (or cases). Of course, if one of the cases gets to be quite involved, I would think about splitting it out into another procedure. Also, if one of the alternatives involves a list, I would use a helping procedure; but often you can use a helping procedure like map or set-minus, instead of writing a new one. Take a look at some of the examples in the library or in the code examples web page to see more of what I mean. Hope that helps. > I really appreciate the help and continued concern for our success as > students! I cannot say it enough! Thanks :-) -- Gary T. Leavens Department of Computer Science, Iowa State University 229 Atanasoff Hall, Ames, Iowa 50011-1040 USA http://www.cs.iastate.edu/~leavens phone: +1-515-294-1580 From leavens@cs.iastate.edu Sun Oct 28 01:06:09 2001 Date: Sun, 28 Oct 2001 01:05:00 -0600 (CST) From: Gary T. Leavens To: David Adam Faden Cc: cs342s@cs.iastate.edu Subject: Re: mysterious load [type checker not finding end of comment on a Mac] David, I've fixed the code in $PUB/lib/type-check-scheme-scanner.scm so that it understands that either a newline or a carriage return can end a comment in Scheme. This makes your code work okay. You should download it if you're working on a computer at home. You can get it in the zip file for the whole library also (see the course library web page). As you'll recall, the problem was that the Mac-encoded file you sent me was beinging interpreted by the type checker as one big comment, since it was looking for a newline to end the comment. I believe that this version also correctly counts line numbers for a Mac-encoded file. Please let me know if you have trouble with it. Sorry for the difficulty with this. > typed> (load "free-vars.scm") > Type checking "free-vars.scm" ... > Type checking "set-ops.scm" ... > ... done type checking "set-ops.scm" > free-vars.scm: line 9: Unknown variable: the-empty-set > free-vars.scm: line 17: Unknown variable: set-member? > free-vars.scm: line 18: Unknown variable: set > free-vars.scm: line 19: Unknown variable: the-empty-set > free-vars.scm: line 20: Unknown variable: the-empty-set > free-vars.scm: line 30: Unknown variable: set-add > free-vars.scm: line 37: Unknown variable: set-union > ... done type checking "free-vars.scm" > Skipping evaluation because of the type errors... Gary T. Leavens Department of Computer Science, Iowa State University 229 Atanasoff Hall, Ames, Iowa 50011-1040 USA http://www.cs.iastate.edu/~leavens phone: +1-515-294-1580 From leavens@cs.iastate.edu Sun Oct 28 23:41:34 2001 Date: Sun, 28 Oct 2001 23:40:19 -0600 (CST) From: Gary T. Leavens To: Aaron R Forsyth Cc: cs342s@cs.iastate.edu Subject: Re: HW3 error and printing lexical address code Aaron, On Sun, 28 Oct 2001, Aaron R Forsyth wrote: > Nevermind, I got the problem figured out. Thanks anyway. I'm glad you figured it out. > I was wondering if I could remove some of the comments from the file when I > print off my code so that it is not 4 pages long? And also the same thing > with the output file. Can I trim down the non-important stuff to save on > paper?? Yes, absolutely. You don't need to hand in the hints, just take them out please. Gary T. Leavens Department of Computer Science, Iowa State University 229 Atanasoff Hall, Ames, Iowa 50011-1040 USA http://www.cs.iastate.edu/~leavens phone: +1-515-294-1580 From leavens@cs.iastate.edu Mon Oct 29 08:31:41 2001 Date: Mon, 29 Oct 2001 08:29:47 -0600 (CST) From: Gary T. Leavens To: dongshin kim Cc: cs342s@cs.iastate.edu Subject: Re: Question for homework3 Dong-Shin Kim, On Sun, 28 Oct 2001, dongshin kim wrote: > Dear Professor, > > Just in case of lexical-address helper procedure, > If var is not in var-table, what is happened? > For instance, > (lexical-address-helper (parse-lambda+if-exp 'x) > '((p q r y) (w z) (car ls))) > Is 'x considered as free variable? That should never happen, because you start the var-table with a list containing the list of all free variables of the expression. So issue an error or ignore that case. Gary T. Leavens Department of Computer Science, Iowa State University 229 Atanasoff Hall, Ames, Iowa 50011-1040 USA http://www.cs.iastate.edu/~leavens phone: +1-515-294-1580 From leavens@cs.iastate.edu Mon Oct 29 19:04:51 2001 Date: Mon, 29 Oct 2001 18:00:55 -0600 From: Gary T. Leavens To: Anthony Willis Barber Subject: Re: HW3 question Anthony, This is a syntax errror in your deftype: Anthony Willis Barber wrote: > I'm working on problem 14, the bound-vars function. i believe I have free-vars > working already, but the function that is giving me problems is in free-vars as well, so maybe not. > > I can't seem to get map to work when converting a lambda-exp->ids, so I wrote a helper to do it for me. > > (deftype get-all-ids (-> (list-of symbol) (set-of symbol))) In the above, you need to write: (deftype get-all-ids (-> ((list-of symbol)) (set-of symbol))) Both the procedure type's formals and the application of list-of require a set of parentheses. > but if I use get-all-ids, it complains about a type error > (get-all-ids (lambda-exp->ids (parse-lambda+if-exp > '(lambda () (lambda (x) (if p (f 'x) (f y))))))) > Offending call: (get-all-ids (lambda-exp->ids (parse-lambda+if-exp (quote (lam > bda () (lambda (x) (if p (f (quote x)) (f y)))))))) > Operator type : (-> (list-of symbol) (set-of symbol)) > Argument type list: ((list-of symbol)) You can tell from the above, as you note below: > I don't understand why the argument passed is a ((list-of symbol)) instead of > just (list-of symbol) > Sorry for the confusion... -- Gary T. Leavens Department of Computer Science, Iowa State University 229 Atanasoff Hall, Ames, Iowa 50011-1040 USA http://www.cs.iastate.edu/~leavens phone: +1-515-294-1580 From leavens@cs.iastate.edu Tue Oct 30 00:53:43 2001 Date: Tue, 30 Oct 2001 00:49:38 -0600 (CST) From: Gary T. Leavens To: David Faden Cc: cs342s@cs.iastate.edu Subject: Re: set! OK for hw3 problem 19? David, On Mon, 29 Oct 2001, David Faden wrote: > Is it OK for us to use set! in doing hw3 problem 19? I would rather you didn't do that. It will make your code non-reentrant unless you're careful, and it will make it harder to understand in any case. Gary T. Leavens Department of Computer Science, Iowa State University 229 Atanasoff Hall, Ames, Iowa 50011-1040 USA http://www.cs.iastate.edu/~leavens phone: +1-515-294-1580 From leavens@cs.iastate.edu Tue Oct 30 00:54:02 2001 Date: Tue, 30 Oct 2001 00:52:20 -0600 (CST) From: Gary T. Leavens To: David Faden Cc: cs342s@cs.iastate.edu Subject: Re: OK to use hw3 14a on hw3 19? On Mon, 29 Oct 2001, David Faden wrote: > I guess my question on set! is moot since the type checker seems to > hate it (and internal redefinitions). Too bad. I think set! allowed a > neat solution. I'd be interested in seeing that. The type checker does understand all of Scheme syntax, including set! and internal redefinitions. But it may be that you aren't understanding the (undocumented) type rules for using set! Internal to a procedure, a define is treated as a letrec, so that should cause no problems. > Is OK for us to reuse our code for hw3 problem 14a on hw3 problem 19? > In general, is always OK for us to reuse our old code? Yes, that's always okay. And often (as in this homework) it's expected. Gary T. Leavens Department of Computer Science, Iowa State University 229 Atanasoff Hall, Ames, Iowa 50011-1040 USA http://www.cs.iastate.edu/~leavens phone: +1-515-294-1580 From leavens@cs.iastate.edu Tue Oct 30 02:04:43 2001 Date: Tue, 30 Oct 2001 01:55:40 -0600 (CST) From: Gary T. Leavens To: David Adam Faden Cc: cs342s@cs.iastate.edu Subject: Re: problem with hw3 problem 19 David, On Tue, 30 Oct 2001, David Adam Faden wrote: > Hi, > My code for hw3 problem 19 passes all of the tests under scheme342; the type checker refuses to accept one of my procedures, however. I've pasted the error message to the bottom of this message. > Is the error in my code? Yes > I have attached my code to this message. > I thought the type checker might be getting tripped up on my passing in '() for something that expects a list of lists; however, altering the code to supply an initial (list '()) only changes the error message slightly. I believe the procedures involved are lexical-address-var-exp, address-of, and index-of. yes, the error is elsewhere, and the empty list is fine. > typed> (load "lexical-address.scm") > Type checking "lexical-address.scm" ... > lexical-address.scm: lines 66 to 68: Expected type of variable and definition di > ffer > Variable: lexical-address-var-exp > Type from deftype or uses : (forall (t) (-> (lambda+if-exp (list-of t) (set-o > f symbol)) lexical-addr-exp)) > Type of defining expression: (forall (t) (-> (lambda+if-exp (list-of (list-of > t)) (list-of t)) lexical-addr-exp)) > ... done type checking "lexical-address.scm" > Skipping evaluation because of the type errors... The problem is that the third argument to lexical-address-var-exp is a set, but it should be a list. You'll have to write a helping procedure to convert it from a set to a list. Gary T. Leavens Department of Computer Science, Iowa State University 229 Atanasoff Hall, Ames, Iowa 50011-1040 USA http://www.cs.iastate.edu/~leavens phone: +1-515-294-1580 From leavens@cs.iastate.edu Tue Oct 30 08:57:28 2001 Date: Tue, 30 Oct 2001 08:53:34 -0600 (CST) From: Gary T. Leavens To: Daniel J Heck Cc: cs342s@cs.iastate.edu Subject: Re: Infuriating TypeChecking Error Hi Dan, On Tue, 30 Oct 2001, Daniel J Heck wrote: > I am getting extremely frustrated by a seemingly simple part of > lexical-address.scm that has turned into a roadblock. The worst part is > that isn't even related to the most current class material. I wrote and > tested lexical-address-of-var-exp and lexical-address-helper, and both > work fine. The last part of the problem is so ridiculously easy that I > thought it would just fall into place. All you have to do is have > lexical-expression call lexical-address-of-var-exp, passing it the input > if-exp and the list containing the list of its free variables, > right? Yes. > My problem is that free-vars produces not a list, but a set. Right. That is the problem. > ... set->list is a helper I defined as follows: > > (deftype set->list (-> ((set-of symbol)) (list-of symbol))) > (define set->list > (lambda (syms) syms) > ) > > I tried to define this recursively, rather than in aggregate, but the > type checker gave me errors in that case. As it is now, set->list works > fine if I load it (along with set-ops.scm) in the type checker. The > checker tells me it returns a (list-of symbol) in that environment, but > in my overall program, it just gives me this : > > lexical-address.scm: lines 163 to 164: Expected type of variable and > definition > differ > Variable: set->list > Type from deftype or uses : (-> ((set-of symbol)) (list-of symbol)) > Type of defining expression: (forall (t) (-> (t) t)) > ... done type checking "lexical-address.scm" > > Does this have something to do with the use of the cons? I have tried it > with list instead and it also gives me a similiar error. No the problem isn't that cons you have. It's that you are relying on the fact that sets are represented as lists. Your code for set->list can't just return the set, since (set-of symbol) is a different type from (list-of symbol) outside of set-ops.scm. The type checker is (correctly) telling you that your code for set->list just returns an object of the same type it was given. The error message here only appears because you are trying to use set->list, whereas if you don't use it there's no inconsistency to complain about. So you have to, as a client (in lexical-address.scm), write set->list recursively, taking each element out of the set, and putting it in the result list. I understand you tried that before, and it didn't work, but try again. I suggest using set-empty?, set-one-elem, and set-rest to code set->list. Gary T. Leavens Department of Computer Science, Iowa State University 229 Atanasoff Hall, Ames, Iowa 50011-1040 USA http://www.cs.iastate.edu/~leavens phone: +1-515-294-1580