From leavens@larch.cs.iastate.edu Sat Feb 18 18:11:56 2006 Date: Sat, 18 Feb 2006 18:11:56 -0600 (CST) From: Gary T. Leavens To: Com S 342 , Com S 342 TAs -- Kewei Tu , Ru He Subject: Corrections to homework 5 in Com S 342 Hi all, Some corrections to homework 5 in Com S 342 were made today at 6:00pm. These involve corrections to some of the types in the problems, specifically types written formerly as "lambda-if-exp" should be corrected to use "expression" instead. Also, more importantly, examples that use "parse-lambda-if-exp" should be corrected to use "parse-expression" instead. Furthermore, the template for the lexical-address problem (problem 10) has also had these fixes applied. If you are working from home, download a new copy of hw342.zip. My apologies for not catching these earlier, although I hope these were caught far enough ahead so that most of you haven't gotten to the problems involved yet. (They resulted from my attempts to making naming more consistent, which I missed in the initial version of the homework.) In any case, sorry for the errors. Gary T. Leavens Department of Computer Science, Iowa State University 229 Atanasoff Hall, Ames, Iowa 50011-1041 USA http://www.cs.iastate.edu/~leavens phone: +1-515-294-1580 ----------------------- From leavens@larch.cs.iastate.edu Sat Feb 18 18:34:21 2006 Date: Sat, 18 Feb 2006 18:34:21 -0600 (CST) From: Gary T. Leavens To: Chris Cornelison Cc: Com S 342 TAs -- Kewei Tu , Ru He Subject: Re: COMS 342: Corrections to homework 5 in Com S 342 Hi Chris, On Sat, 18 Feb 2006, Chris Cornelison wrote: > I've all ready solved the problems in question. The change in deftypes > shouldn't affect the correctness of my solution should it? Sorry about that. No the deftypes only affect the type checker. > Thanks, > Chris Cornelison Gary T. Leavens Department of Computer Science, Iowa State University 229 Atanasoff Hall, Ames, Iowa 50011-1041 USA http://www.cs.iastate.edu/~leavens phone: +1-515-294-1580 -------------------------- From leavens@larch.cs.iastate.edu Sun Feb 19 10:56:48 2006 Date: Sun, 19 Feb 2006 10:56:48 -0600 (CST) From: Gary T. Leavens To: Omar Germino Cc: Com S 342 TAs -- Kewei Tu , Ru He Subject: Re: CS 342 lambda-if-exp Hi Omar, On Sun, 19 Feb 2006, Omar Germino wrote: > While testing problem 6, I came across some rather curious behavior of the > lambda-if-exp grammar, examples of which can be seen in the attached PDF. > I'm unsure as to the cause of this behavior, since my solution passed the > assigned test cases. > (require (lib "lambda-if-exp.scm" "lib342")) > (app-exp (var-exp 'a) (var-exp 'b)) (a . b) > (app-exp? (app-exp (var-exp 'a) (var-exp 'b))) #f These happen because in the lambda-if expression grammar, you need to have a list as the second argument to app-exp. The app-exp? procedure is working correctly, but app-exp doesn't check it's arguments for being the right kind of data. This is because I was assuming the types would be enforced. Indeed if you use the type checker: > (type-check-and-eval-loop) Typed Scheme interpreter (by Brian Dorn, Gary T. Leavens, and Curtis Clifton) Use "(type-check-help)" to list options. typed> (require (lib "lambda-if-exp.scm" "lib342")) quote-exp->symbol : (-> (expression) symbol) lambda-exp? : (-> (expression) boolean) if-exp->false-exp : (-> (expression) expression) if-exp : (-> (expression expression expression) expression) lambda-exp : (-> ((list-of symbol) expression) expression) if-exp? : (-> (expression) boolean) app-exp->rands : (-> (expression) (list-of expression)) var-exp->id : (-> (expression) symbol) quote-exp : (-> (symbol) expression) parse-expression : (-> (datum) expression) app-exp->rator : (-> (expression) expression) if-exp->test-exp : (-> (expression) expression) var-exp? : (-> (expression) boolean) app-exp? : (-> (expression) boolean) if-exp->true-exp : (-> (expression) expression) lambda-exp->ids : (-> (expression) (list-of symbol)) lambda-exp->body : (-> (expression) expression) var-exp : (-> (symbol) expression) app-exp : (-> (expression (list-of expression)) expression) quote-exp? : (-> (expression) boolean) expression? : (type-predicate-for expression) typed> (app-exp (var-exp 'a) (var-exp 'b)) : line 2: Operator and argument types don't match Offending call: (app-exp (var-exp 'a) (var-exp 'b)) Operator type : (-> (expression (list-of expression)) expression) Argument type list: (expression expression) Skipping evaluation because of the type errors... typed> (app-exp? (app-exp (var-exp 'a) (var-exp 'b))) : line 3: Operator and argument types don't match Offending call: (app-exp (var-exp 'a) (var-exp 'b)) Operator type : (-> (expression (list-of expression)) expression) Argument type list: (expression expression) Skipping evaluation because of the type errors... So it does detect this as an error. Whether it's a good library design to trust callers to obey these type declarations is another matter... BTW, you can save the interactions window in DrScheme as a text file, by using the File / Save Other menu item. Gary T. Leavens Department of Computer Science, Iowa State University 229 Atanasoff Hall, Ames, Iowa 50011-1041 USA http://www.cs.iastate.edu/~leavens phone: +1-515-294-1580 -------------------------------------- From leavens@larch.cs.iastate.edu Sun Feb 19 13:17:29 2006 Date: Sun, 19 Feb 2006 13:17:29 -0600 (CST) From: Gary T. Leavens To: Omar Germino Cc: Com S 342 TAs -- Kewei Tu , Ru He Subject: Re: CS 342 making a list into a set? Hi Omar, On Sun, 19 Feb 2006, Omar Germino wrote: > Is there any way to "cast" a list into a set? You can use write a helping procedure to do this (it's fairly easy as a list recursion). Or you can use (apply set lst) to make lst into a set; that works because (apply set (list x1 x2 x3 ...)) = (set x1 x2 x3 ...) due to the definition of apply. > While running the > typechecker, it complained like so: > > vvvvvvvv BEGIN ERROR REPORT vvvvvvvvvv > d:\cs342\lambda-if-exp-vars.scm: line 38: Operator and argument types don't > match > Offending call: (set-union (lambda-exp->ids expr) can-be-bound) > Operator type : (forall (T) (-> ((set-of T) (set-of T)) (set-of T))) > Argument type list: ((list-of symbol) (set-of symbol)) > ^^^^^^^^ END ERROR REPORT ^^^^^^^^^^^ > > Or do I just have to ignore this, since sets are lists anyway. No, sets are not lists, esp. if you use the set-ops-as-vector.scm representation. The type checking is correctly pointing this out as a problem. Gary T. Leavens Department of Computer Science, Iowa State University 229 Atanasoff Hall, Ames, Iowa 50011-1041 USA http://www.cs.iastate.edu/~leavens phone: +1-515-294-1580 -------------------------------- From leavens@larch.cs.iastate.edu Sun Feb 19 22:56:38 2006 Date: Sun, 19 Feb 2006 22:56:38 -0600 (CST) From: Gary T. Leavens To: Denise Bacher Cc: Com S 342 TAs -- Kewei Tu , Ru He Subject: Re: Testing problem hw5 prob 6 Hi Denise, On Sun, 19 Feb 2006, Denise Bacher wrote: > Gary, whey I try to test problem 6 I get the following errors. I've downloaded > the newest hw342.zip file off the website and put in PLT\collects and re-run my > project and it still isn't working. Could you look at it? > > Thanks, > Denise > > Welcome to DrScheme, version 301. > Language: Typedscm, typed extension to EoPL(2e). > Teachpack: C:\Program Files\PLT\teachpack\drscheme-342-teachpack.scm. > Name: Denise Bacher > TA: Ru He Section: 1 >> (test-hw5 "free-vars-lambda-if-exp") > > Test case $RCSfile: free-vars-lambda-if-exp.tst,v $ of $Date: 2006/02/14 05:50:51 $ > > . . C:/Program Files/PLT/collects/homework/hw5/free-vars-lambda-if-exp.tst::727: > parse-expression: bad syntax for expression: (if p (f x g) (f y h)) >> (test-hw5 "bound-vars-lambda-if-exp") > > Test case $RCSfile: bound-vars-lambda-if-exp.tst,v $ of $Date: 2006/02/14 05:50:51 $ > > . . C:/Program > Files/PLT/collects/homework/hw5/bound-vars-lambda-if-exp.tst::799: > parse-expression: bad syntax for expression: (lambda () (lambda (x) (if p (f x) > (f y)))) >> Hmm, when I try it I get... (test-hw5 "bound-vars-lambda-if-exp") Test case $RCSfile: bound-vars-lambda-if-exp.tst,v $ of $Date: 2006/02/14 05:50:51 $ All tests passed! The test case that you are encountering is the first one that has a lambda with a list of formal parameters that has length not equal to 1. So, I'll bet that the problem is you are using something other than (require (lib "lambda-if-exp.scm" "lib342")) such as lambda-1-exp.scm or lambda-quote-exp.scm. That would cause this problem. Let me know if that's not the case... Gary T. Leavens Department of Computer Science, Iowa State University 229 Atanasoff Hall, Ames, Iowa 50011-1041 USA http://www.cs.iastate.edu/~leavens phone: +1-515-294-1580 --------------------- From leavens@larch.cs.iastate.edu Mon Feb 20 21:29:32 2006 Date: Mon, 20 Feb 2006 21:29:32 -0600 (CST) From: Gary T. Leavens To: Drew Templeton Cc: Com S 342 TAs -- Kewei Tu , Ru He Subject: Re: CS342 Question Hi Drew, On Mon, 20 Feb 2006, Drew Templeton wrote: > Hello Prof. Leavens. I'm getting stuck on part b. of problem 6. Almost > everything is working out right except 2 of the test cases involving nested > lambdas/app-exps are not coming out correctly. Could you take a look at my code > and see if you could provide some advice. Thanks, Drew. You're not using the correct definition of bound variables for the application and the lambda case. In the application case, you shouldn't be doing any subtraction of free variables. That should be happening in the lambda expression case. The lambda expression case isn't defined with respect to the set of free variables, not with respect to the set of all variables that occur in its body. Here are the definitions given in class... notation: FV(E) = set of variables that occur free in E BV(E) = set of variables that occur bound in E def: FV(E) = {x}, if E is a varref, x FV(E1) union FV(E2), if E is (E1 E2), and FV(E) - {y}, if E is (lambda (y) E) def: BV(E) = {}, if E is a varref BV(E1) union BV(E2), if E is (E1 E2), and BV(E) union ({y} intersect FV(E)), if E is (lambda (y) E) Gary T. Leavens Department of Computer Science, Iowa State University 229 Atanasoff Hall, Ames, Iowa 50011-1041 USA http://www.cs.iastate.edu/~leavens phone: +1-515-294-1580 --------------------------------- From leavens@larch.cs.iastate.edu Wed Feb 22 19:56:33 2006 Date: Wed, 22 Feb 2006 19:56:33 -0600 (CST) From: Gary T. Leavens To: rmatus@cs.iastate.edu Cc: Com S 342 TAs -- Kewei Tu , Ru He Subject: Re: Test question... Hi Rich, On Wed, 22 Feb 2006 rmatus@cs.iastate.edu wrote: > Could you explain this line from the study guide? > > + be able to write a variable arity procedure > > > I looked at the code listed, and I dind't seem to see much difference from it > and other code we had done... mynotes were of no help either... > > What is a variable arity procedure... what makes it so? It's a procedure that takes any number of arguments. Examples built-in to Scheme include +, *, list, vector, and append. To write one you use the form of lambda with one formal and no parentheses around it. Examples in the library are described in http://www.cs.iastate.edu/~leavens/ComS342/lib342/code-examples.html#SchemeProcedures Good question. Gary T. Leavens Department of Computer Science, Iowa State University 229 Atanasoff Hall, Ames, Iowa 50011-1041 USA http://www.cs.iastate.edu/~leavens phone: +1-515-294-1580 --------------------------- From leavens@larch.cs.iastate.edu Wed Feb 22 23:09:26 2006 Date: Wed, 22 Feb 2006 23:09:25 -0600 (CST) From: Gary T. Leavens To: rmatus@cs.iastate.edu Cc: Com S 342 TAs -- Kewei Tu , Ru He Subject: Re: Test question... Hi Rich, On Wed, 22 Feb 2006 rmatus@cs.iastate.edu wrote: > One of the study guide things says... > > + write a higher-order procedure > > Why is iterate considered a higher order procedure? What makes something a > higher ordered procedure? Good questions. A procedure is a higher-order procedure if it has more than one arrow -> in its type. So iterate is higher-order because it has type iterate : (forall (T) (-> ((-> (T) T) number) (-> (T) T))) One can actually define the "order" of a procedure inductively. A procedure like "not" is a first-order procedure, as its type has 1 arrow. Iterate is a second-order (and hence higher-order). Gary T. Leavens Department of Computer Science, Iowa State University 229 Atanasoff Hall, Ames, Iowa 50011-1041 USA http://www.cs.iastate.edu/~leavens phone: +1-515-294-1580 ---------------------- From leavens@larch.cs.iastate.edu Thu Feb 23 10:01:29 2006 Date: Thu, 23 Feb 2006 10:01:29 -0600 (CST) From: Gary T. Leavens To: Greg Walker Cc: Com S 342 TAs -- Kewei Tu , Ru He Subject: Re: HW5 Q10 just checking Hi Greg, On Thu, 23 Feb 2006 eibwen@cs.iastate.edu wrote: > in the Notes on lexical-address-helper, it suggests using free-vars for the > inital inputs, but the free-vars we used outputs a set, and the helper takes > in a list. > > So was there something else in mind that i'm misunderstanding, or should i > just write a quick 'set->list' conversion procedure? Yes, you should write such a helper. > oh there is already a 'vector->list' built into scheme it would seem, so > using that would be fine? No, because that would not be independent of the representation of sets. In this case you must write a separate helper. Gary T. Leavens Department of Computer Science, Iowa State University 229 Atanasoff Hall, Ames, Iowa 50011-1041 USA http://www.cs.iastate.edu/~leavens phone: +1-515-294-1580 ------------------------- From leavens@larch.cs.iastate.edu Thu Feb 23 10:15:08 2006 Date: Thu, 23 Feb 2006 10:15:07 -0600 (CST) From: Gary T. Leavens To: Grace Qiu Cc: Com S 342 TAs -- Kewei Tu , Ru He Subject: Re: a couple of questions Hi Grace, On Thu, 23 Feb 2006 gqiu@cs.iastate.edu wrote: > I just had a couple of questions about the upcoming exam. For syntactic sugar, > the spring05 practice exam asked whether "The *define* special form in Scheme > is syntactic sugar for a procedure call." was true. I'm not sure if it is true. > Could you verify and summarize? It's not be syntactic sugar for a procedure called because it can't evaluate its "arguments". The first "argument" is the name of the thing being defined, which doesn't have a value yet. The second argument can also depend on the value of the name, which is how we can define recursive procedures. None of this can be done by a procedure, which is why "define" is a special form. > Also for derivations, such as the spring05 exam problem with , I was > wondering if the following was correct: > > ::= ( require {}* ) > ::= > | > | ( file ) > | ( lib {}* ) > > > to derive > > ( require (lib "maybe.scm" "lib342" ) ) > > Would you do the following: > > > => ( require {}* ) > => ( require (lib {}* ) ) > > > or would you have to do: > > > => ( require {}* ) > => ( require ) > => ( require (lib {}* ) ) The latter is correct, as far as it goes. You have to continue with a few more steps, to get the actual terminal string required. => ( require {}* ) => ( require ) => ( require (lib {}* ) ) => ( require (lib {}* ) ) => ( require (lib ) ) => ( require (lib "maybe.scm" ) ) => ( require (lib "maybe.scm" "lib342" ) ) Gary T. Leavens Department of Computer Science, Iowa State University 229 Atanasoff Hall, Ames, Iowa 50011-1041 USA http://www.cs.iastate.edu/~leavens phone: +1-515-294-1580 ------------------------------------ From leavens@larch.cs.iastate.edu Mon Feb 27 12:35:26 2006 Date: Mon, 27 Feb 2006 12:35:25 -0600 (CST) From: Gary T. Leavens To: Steven Kroeger Cc: Com S 342 TAs -- Kewei Tu , Ru He Subject: Re: multiple recursions in one procedure Hi Steven, On Mon, 27 Feb 2006, Steven Kroeger wrote: > This is how I solved hw4 q8 and not too different from q7. I was wondering if > this is what you were talking about in class about not having different types > of recursion in a solution since I'm testing for different types, statements > or expressions? Or in simpler terms would I have lost credit for this for > solving it this way? > > Steven Kroeger > > (deftype subst-identifier (-> (symbol symbol statement) statement)) > (define subst-identifier > (lambda (new old sta) > (cond ((var-exp? sta) ... ) > ((num-exp? sta) ...) > ((exp-stmt? sta) ...) > ((set-stmt? sta) ...) > ((begin-exp? sta) ...) > (else (var-exp 'you-messed-up))))) Yes, this is incorrect, you are mixing recursions and should lose points for that. To follow the grammar, and to avoid calling procedures like num-exp? and set-stmt? outside their domains you have to have two separate procedures. See the following the grammar handout. In essence it should look like: (define subst-identifier (lambda (new old sta) (cond ((exp-stmt? sta) ...) (else ;; set-stmt case ...)))) (define subst-identifier-exp (lambda (new old sta) (cond ((var-exp? sta) ... ) ((num-exp? sta) ...) (else ;; begin-exp case ...)))) If you are working from home, there is a new version of statement-expression.scm that gives errors when you try to do things the way you did, by combining both in one procedure way. It passes all of the tests and none of my code using it (which is done correctly) had to be changed. But your code will fail with it, so I urge you to get the new library and see that. BTW, you should call "error" in the else case, if you have one like that. Silent errors are bad. Gary T. Leavens Department of Computer Science, Iowa State University 229 Atanasoff Hall, Ames, Iowa 50011-1041 USA http://www.cs.iastate.edu/~leavens phone: +1-515-294-1580 ------------------------------------ From leavens@larch.cs.iastate.edu Mon Feb 27 22:24:06 2006 Date: Mon, 27 Feb 2006 22:24:06 -0600 (CST) From: Gary T. Leavens To: rmatus@cs.iastate.edu Cc: Com S 342 TAs -- Kewei Tu , Ru He Subject: Re: Homework #5 Problem 10... Hi Rich, On Mon, 27 Feb 2006 rmatus@cs.iastate.edu wrote: > I'm trying to figure out what's going on with problem #10... Could you tell me > if I'm on the right track for understanding the problem, as well as the "hints" > you gave in the lexical-address.scm file? > > 1) lexical-address is going to handle the main grammar. This will have a cond > statement with the various conditions of the grammar in it. There will also > probably be another procedure to handle the second non-terminal listed, though > we dont' HAVE to have it, since it's a fairly short line... The grammar listed at the beginning of problem 10 is not the input grammar, which is the lambda-if-exp grammar of problem 6. The grammar at the beginning of problem 10 is the grammar describing the output (results). Your outline follows the input grammar, not the output grammar. > 2) lexical-address-helper is used to run through the lambda statement. Yes, more precisely over over the lambda-if-exp expression. > This > lambda statement is one of two places where we'd have to deal with outputting > the changed lexical address information... I don't however understand which > sublist is which. > > Given this list: '((a b) (p q r) (x y) (car ls)) > > According to the comments, would that mean that (x y) are free variables, (p q > r) are declared in the outer most lambda and (a b) are declared in the inner > most lambda? No car and ls would be the free variables, and (x y) is the formal parameter list of the outermost lambda, (p q r) is the formal parameter list of the next closest surrounding lambda. You are right about (a b). > 3) lexical-address-of-var-exp is the procedure that deals with the var-exp of > the grammar. yes, of the lambda-if-exp grammar. > This is the other place where our output woudl be different > because the variable would be declared elsewhere... either free, or in a nested > lambda someplace. Yes. > In fact, there really are only three procedures you gave us...we might have to > add one or two more depending to fulfill the grammar or finish out something? Yes, as many as you need, it may be several... Don't hesitate to make as many helpers as you wish. Gary T. Leavens Department of Computer Science, Iowa State University 229 Atanasoff Hall, Ames, Iowa 50011-1041 USA http://www.cs.iastate.edu/~leavens phone: +1-515-294-1580 ------------------------------ From leavens@larch.cs.iastate.edu Mon Feb 27 23:04:04 2006 Date: Mon, 27 Feb 2006 23:04:04 -0600 (CST) From: Gary T. Leavens To: rmatus@cs.iastate.edu Cc: Com S 342 TAs -- Kewei Tu , Ru He Subject: Re: Homework #5 Problem 10... Hi Rich, On Mon, 27 Feb 2006 rmatus@cs.iastate.edu wrote: > How do we deal with the fact that free-vars will give us a set of variables, > while all the deftypes you give us have list-of symbols as the type? Write a helping procedure that takes a set and returns a list of symbols. This can be done by using set-empty?, set-one-elem and set-rest. Gary T. Leavens Department of Computer Science, Iowa State University 229 Atanasoff Hall, Ames, Iowa 50011-1041 USA http://www.cs.iastate.edu/~leavens phone: +1-515-294-1580 ---------------------------