CSC324 — Assignments

Assignment 4

Questions.

Solutions.

Answers to some Asked Questions

1. Does the shortest trip algorithm assume an implementation of bounds that counts up?

   Yes, so write one that counts up for this assignment.

2. Do we write the CFGs in Prolog?

   No, in plain text.

3. How close does the two non-terminal CFG have to be to the Prolog code?

   Use the same associativity as the code produces, and make a second non-terminal for the same reason you made a helper.

4. Help, I can't make the one terminal CFG work

   I may have outsmarted myself. I can't seem to regenerate my solution that corresponds to the trick in the Prolog code and have become convinced that it's at least not as simple as I wanted. So let's drop CFG (4) from the assignment.

5. How do I get Prolog to show me all of a long list?

   Use write when you're testing: ?- p(X),write(X). will have a side-effect of displaying X.

6. How would I do trip in Scheme?

   trip.scm.

7. Can we use not?

   Yes.

8. Any hints on how to approach parse?

   Yes, the usual: solve simpler parts. Write something to parse noun phrases. How do you do that? Write something to parse noun phrases where the determiner and adjective are not optional. How do you do that? Write something to parse a noun. How do you do that? Write something that says what your nouns are.

9. Any hints on how to approach p?

   Yes, the usual: solve simpler parts. Write something to parse just addition. Write something to parse just multiplication. How do you do that? For multiplication, study the accumulating versions of length and reverse from tutorial. Hint: it might be simplest to give the multiplication helper the list without the first element, i.e. have it work on lists of the form [*, a, *, b, *, c].

10. Is something wrong if my CFGS for (2) and (3) are very similar?

    No.

11. Is something wrong if my CFGs for (1) and (3) very similar?

    Yes. You may be thinking that a CFG is only about recognizing a language. But it also imposes a structure (parse trees) on the sentences of the language. That's what associativity, precedence and ambiguity was all about in lecture. Your CFG for (1) will view [a, *, b, *, c] differently than (3) will view a*b*c: the parse trees will have quite a different shape, even ignoring the punctuation.

12. Any hints on how to approach trip?

    Yes, the usual: solve simpler parts. Write it assuming there are no cycles. How do you do that? Write something that just decides whether there's a trip, without producing a trip. How do you do that? Complete the following sentence: "there is a trip from S to E if <base case> or there is a <child> and a trip from <child> to E". How do we say "or" and "there is" in Prolog?

Assignment 3

Part II.

Solutions.

Answers to some Asked Questions

1. Various collected from emails over the weekend:

   General: use pattern matching instead of =.

   mingle: you may use , (the comma in the question is an English comma, separating the three operators (! ; ->) you can't use).

   mingle: sorted means sorted non-decreasing.

   mingle: M has only the elements from L1 and L2.

   bounds: don't try to test for instantiated versus uninstantiated. Write the code to produce all the values, keeping in mind that Prolog goes through all matching facts and rules (not just the first matching one). Then trace it to see what it will do with an instantiated value (yes, I know you can just try running it).

   level and data: these also produce multiple answers.

   level and data: the definition of binary trees is right there: the atomic value nil or a recursively built ternary structure bt. We used structures in lecture to model propositional logic. And by now you should be very familiar with this style of definition from CSC 236/240, ML user-defined datatypes and CFGs.

   level: consider the root's data to be at level 0.

2. Some more questions answered:

   General: is is for doing arithmetic calculation, not for generally binding a variable. If, for example, you want to say something like "make T be bt(X, nil, Y) and Y be Z" you could use =, but usually it's much better to rewrite your code, replacing (in the source code) "T" and "Y" with "bt(X, nil, Z)" and "Z"! Trust matching. On the other hand, number(X - 1) will always fail, since it doesn't compute the value of X with 1 subtracted. For that you have to use is to trigger numeric computation and bind the result to another variable.

   mingle: "only" above means M has no other elements, so for each L1 and L2 there is exactly one result to produce for M.

   mingle: if you're stuck, try writing it in Scheme or ML using pattern matching: the algorithm and flow of control is the same (we did something similar in lecture when first introducing Prolog, for length and append). Each match, if or cond clause/branch corresponds to a Prolog rule/fact, with possible explicit `else' checks in some of the Prolog rules.

   bounds, level: if you're stuck, try writing it in Scheme, displaying each value instead of returning it (that's one way to get closer to the multiple-value semantics of Prolog).

   level, data: don't define bt, simply use data of that from. As mentioned in lecture, this is like in Scheme where we could simply use 'nil or '(bt 1 nil nil) without defining them. Prolog doesn't have a quote, it uses the context: "nil." is a fact, "?- nil." asks whether nil is a fact, but "p(nil)." is a fact about p that says p is true for the atomic piece of data nil.

   data: you'll probably need a helper method to partially `break up' the data in various ways before `feeding' it to various trees recursively.

3. Don't despair, even if you're just starting!

   A student who hadn't started asked for an extension today. I couldn't give one at this point, but listen to what he said a couple of hours later: "I've just begun the assignment, but I'm picking up Prolog pretty quickly, the assignment doesn't seem too bad on the surface."

   Another student today told me he initially had 50 lines for the tree part, but cut it down to under 10. So try to keep it `simple', then test and trace.

Part I.

Solutions.

Answers to some Asked Questions

1. Is class missing a line?

   Yes, the last line got cut off. And Circular-Queue has a typo, and I momentarily thought of it as a stack in the example of its use. Here are class and Circular-Queue in a text file.

2. How do I understand class?

   First, determine what ordinary Scheme code class produces for Circular-Queue without the observe clause. Then check your work by putting a quote in front of the result part of class's definition: that will make class return a list representing the code it would have produced and executed. You can display it in a more formatted form with pretty-print in (require (lib "pretty.ss")).

   Second, trace the produced code to understand how it works.

   Third, see how much of the observer pattern you can implement `manually' by adding code to Circular-Queue (not class). Try to use as little knowledge of how Circular-Queue works as possible (so the code will be most usable in any class).

   Fourth, implement the observer pattern in the code produced by class for Circular-Queue.

   Make class do what you did in the Fourth step.

3. Why do you point out that 'd' can be any expression?

   You're probably wondering since we don't bother to point out that (list + -), yoshi etc are just examples and could be any expression. We point out 'd' because if you don't think about it you're likely to make an error: what if 'd' takes a long time to compute, or has side-effects? Does your case-sign do the right thing?

4. If I redefine =, how can I use it's original meaning?

   Note that = is a variable referring to some equality procedure. You just need to `remember' the original value of = somehow (how do you remember things in a program?)

5. Why doesn't my case-sign tell the difference between + and -?

   In your syntax-rules, when you mention + you mean literally +, not some arbitrary piece of code that you are calling +. Look at how we handled this in lecture when defining for.

6. How can instances of a class refer to themselves?

   The original class contains code to make an `instance'. You want to refer to that instance elsewhere in the code: how do you do that in programming (also notice that you are referring to something from within code for that thing, so you need letrec instead of let).

Assignment 2

Questions.

Answers to some Asked Questions

1. What exactly do rules select-boolean, append-singleton, etc do?

   A number of students have asked me this, but until one specific email tonight it didn't occur to me what/why some (but not all) of them were asking: they hadn't read the whole assignment! There is a discussion of rules, including their datatype (procedure) number of arguments and returned value, along with an example for the case of data representing propositional formulas. You have to read that of course, but let me point out that the two push-negations rules combined are only four lines long. Yours might have an extra line each because they have names and if you don't want to look up or figure out match-lambda from the example you might have an extra line to separate match and lambda.

   If you do know what a rule is but are wondering about one of the specific rules: part of the assignment is to improve your own style by figuring out what a better style would be for the given example code, understanding the general style principle in Human, and writing the corresponding rule. E.g. if you see a Java programmer write Kart.mario(yoshi, toad) == true you would tell them that comparing something to true can be simplified: foo == true is equivalent to just foo, and you could write a method that takes a string (or maybe some datatype to represent the Abstract Syntax Tree of Java source code) and if it's of that form removes "== true".

2. Help, I can't figure out an algorithm for trippy.

   Have you practiced on something simpler? For example, can you find the shortest path to a leaf in a tree? If a tree's nodes hold data, can you find the shortest path to some piece of data? What if it's not a tree but a directed acyclic graph? What if it's an arbitrary graph? If you email me with answers to the tree questions, we can work on them and I can also tell you where exactly in a previous course you saw the simple algorithm for trippy.

3. Can you show me the main algorithm in your trippy?

   Here it is again, reformatted. The only helper procedures used are select and fold (not shown). There are two simple but different base cases, and the rest is two maps, a select and a fold with one recursive call and a simple post-processing step. The calls to those higher-order procedures could be made into helper procedures and the main algorithm would be extremely short. Let me emphasize that it does nothing particularly clever (it wouldn't impress anyone in CSC 263): the two base cases, the four higher-order processing steps and the bit of post-processing are natural to describe in Human. Here's what one student said about their solution:

   "I figured out trippy. Thanks for chatting with me about it. I can't believe I was so fixated on it being impossible to implement recursively (I blame it on lack of sleep). It was really quite straightforward."

4. How general should I make my rules?

   Start with: write a match pattern that matches the example, and then simplify it to make it more powerful. E.g. changing ('if ('yoshi 'peach 'toad) #f #t) to '(not (yoshi peach toad)) is more complicated and less powerful than changing ('if e #f #t) to `(not ,e). Do that much for append-singleton, unwrap-lambda, refactor-if and linked-list.

   You may assume toad is a procedure in unwrap-lambda and refactor-if. This is a good assumption for unwrap-lambda, but less so for refactor-if: a "production quality" style checker would be smarter and also interact with the user.

   For ifs->cond, transform the standard if-elseif-...-else pattern (and anything similar that helps you handle that pattern).

   For ->map, first look at whether you used map everywhere you could in A1, especially in the testers and deep-map. Put your code into the form of the example (if it's not already in that form) and then rewrite it using map. Now tell the computer how to do that for you.

Submission

Please put your code into "trippy.scm" and "rewrite.scm". Helper code that you load can be put into separate files if you like. Your code for Metaprogramming can be put in one file "rewrite.scm" if you like, or into separate files like for A1 (e.g. scheme-file->list can be submitted in "scheme-file-list.scm").

Assignment 1

New Due Date: Oct 17 at 5pm.

Questions.

Solutions.

Submission

Please put each procedure in its own file, with the filename as procedure name followed by ".scm", e.g. unary-tester.scm. If you use one procedure as a helper for another, load the helper procedure's code at the beginning of the file that uses it. If you write a helper for use by more than one procedure, put it in its own file and load it at the beginning of the files that use it.

Answers to some Asked Questions

1. How does tester differ from unary-tester?

   It can test more kinds of procedures than unary-tester: unary-tester only works on procedures taking one argument, but tester can test any procedure. The format of the test cases has to change as described, to accommodate any number of arguments.

2. What does choosy-fold do with an empty list?

   For choosy-fold to do its job of calling the combiner, there needs to be a current element. Consider it a precondition that the list isn't empty, and that the combiner won't ask for the result of processing the rest when the rest is empty. There are situations where this is a reasonable precondition (especially if choosy-fold is used as a helper procedure), but the main point of choosy-fold is not the recursion, but to practice more with higher-order functions and to mimic call-by-need.

3. How can I get my fold-in to work like fold?

   The specification doesn't ask you to do that, so don't worry about it. Some problems are best solved using one but not the other. If you need a source of list questions to think about, see CSC 148's A2. For each one decide whether fold or fold-in is more suitable (though for some either works naturally, and for others one can force it).

4. Can you give me a test case for fold-in?

   fold-in is a very valuable exercise for:

   1. Understanding the difference between the two types of recursion.
   2. Tracing your code.

   Two students already have mentioned that working on it made them finally understand recursion. To get a similar enlightenment, here are some steps to take:

   1. Determine which of your two SumOfSquares methods from A0 does its work on the way in, and which on the way back.
   2. Write Human language high-level descriptions of those method implementations, using as much of the terminology of fold and fold-in as possible.
   3. Write length in the two styles (in Java or Python first if necessary, then Scheme).
   4. Trace your length to make sure it really does the work in the correct order. If you can't do it by hand you need to essentially stop programming until you learn that skill: it's orders of magnitude more important than solving just one particular assignment question by fiddling around until it matches a particular test case. Soon you will be one of the 'fast' programmers that the Spolsky article talks about.
   5. Write the two lengths as calls to fold and fold-in, and trace to make sure fold-in is doing the work in the correct order. As a temporary hack if you can't trace it by hand, put a display statement at the beginning of fold-in and your combiner, to tell you when they are called and with what arguments.
   6. Find a combiner you can send to both fold and fold-in where you expect different results (hint: which of + and - should give the same result, and which should give a different one?).
   7. If you get stuck at one of these steps, send me the steps you've done so far and where you're stuck, so we can get you unstuck!

5. Will there be style marks?

   Yes, and most of the usual style principles from your other courses apply. And though we've only seen a small part (higher-order functions) of the full refactoring power of Scheme, there are already some good opportunities to use our new powers. As the specification says: "Use higher order functions [...] where appropriate". In particular, there are opportunities to use map instead of reimplementing each special case of it. And there are two very similar procedures that can be implemented in terms of each other, or as special cases of a generalized procedure (that's three choices for refactoring that particular repeated code). Every time you do the `same/similar' thing, try to refactor.

6. How can unary-tester be "given" a test case that both passes and fails?

   Write "an example of a call to tester that tests unary-tester", without yet worrying about which exact example. Since you have written unary-tester and tester, you know the datatypes and meanings of their arguments and what they do with their arguments, so you can do this without any more explanation. Then read the rest of the specification, which narrows down the kind of call (i.e. the specific arguments you choose).

   We don't want to spoil the learning exercise, but here is some of what you will discover: since unary-tester is both something that can be tested and something that tests, it can be given a test case in two senses:

   1. a valid input for unary-tester, where we expect a certain result from unary-tester
   2. a valid input & expected output for the procedure that we are using unary-tester to test

   If you're stuck, do the usual: send me the simplest part you can't do, i.e. send me an example of a call to unary-tester, a call to tester, and as much as you can fill in of a call to tester that tests unary-tester. You know the arguments and their datatypes, so at least make an example with any arguments of those datatypes (where you don't worry at all about what tester and unary-tester does with them).

7. How can I execute two expressions (in caching)?

   There are two main approaches: exploit pass-by-value, or put them inside something that can execute more than one expression. Using the first approach: make a procedure and call it with your expressions as arguments; variations are to use an existing procedure or syntactic form, or use the expressions as variable initializers in a let/let* (see the lecture summaries for why the let approach is essentially the same as the procedure approach). Using the second approach: make a procedure with the expressions in the body and call it right away, or put them in a let without variables (again, see the lecture summaries for why this the essentially the same as the procedure approach). If you'd like to just use begin you may; but be sure to understand how it can be done in other ways (see e.g. the "Closures" section of the lecture summaries).

Assignment 0

Coverage: reviews some material from prerequisite courses, relevant to CSC 324.

New Due Date: Thr Sep 28 at 5pm.

Questions.

Answers to some Asked Questions

1. How exactly does List represent lists?

   This is a small exercise in identifying concepts you've learned, in new situations. Progammers need to see the concepts in their code independent of superficial aspects such as naming and syntax. In other words, seeing the semantics instead of just the syntax, and being able to ignore irrelevant syntactic differences. Refactoring and Design Patterns are all about this.

   List is about as close as you can get to a Java class you worked with in CSC 148, without being identical (in particular they're both in Java syntax). Be on the lookout when you review Java and lists.

   If you want to work it out yourself without looking for it in CSC 148, the following three questions will get you started: how could you use List to store one/two/three elements? This is of course a general technique for understanding many things: try small examples.

2. Is length static? What are its parameters?

   Standard OO questions answer this:

   • What kind of objects does length work on?
   • What class is length in?

3. Do I preserve order in lists? What about duplicates?

   The list ADT (as opposed to the set ADT) in CS usually considers index/order/location significant and allows duplicates. Preserve this where reasonable.

   Duplicate elements can appear in an input list, are treated separately, and can cause duplicates in the output.

4. What similarities do I look for in length, map and append?

   This is a nice little example of refactoring and Design Patterns. Some questions to get you started:

   • Are the recursions similar? Are they linear or branching? Do they do work on the way up, down or both?
   • Do the methods have syntactic similarities? Can you make them more syntactically similar? Can you phrase the syntactic similarities semantically?
   • Can you match up some words, and maybe similar sentences, in the English implementation comments? If not, can you rewrite the comments to use each other's words?

5. Can I use Python's list functions?

   The Java and Python implementations should be as close as possible semantically, so avoid Python's lists and corresponding list functions.

6. Does pushNegations() simplify double negation?

   Yes.

7. Do we use full Javadoc?

   No, don't bother. In fact the parameter and return tags often encourage repetition.

8. Do we submit test cases? Will you autotest?

   We'll look at your code: if we're convinced then we won't test it, else we'll manually test it. You should test it yourself to check your reasoning.

9. Do we do error handling?

   No, don't bother. Assume the input is correct according to the preconditions.

10. Another hint about length, map and append? (Now I know how contestants on Jeopardy feel, having to phrase everything in the form of a question; does just adding a "?" count?)

    No one has asked since the posting of #4 above, but here's a great hint anyway: try to write them using Java and Python's ternary conditional operators.

11. Do we store list elements front to back or back to front?

    If we were hiding the list implementation from the user of lists, it might not matter. But we aren't, and the assignment is also explicitly about implementation. So (and I'm phrasing this in a way to not spoil your review of list implementations) use the most common approach for this kind of list implementation: a reference to a List is considered essentially a reference to its first/front/left-most element.