Pretty nice discussion, want to see much more on it! :) Congrats on your work. Sorry I wont get to see you at worlds. famvir and shingles webpage devoted to famvir and shingles. spironolactone weight loss webpage devoted to spironolactone weight loss.

That final sucked! It was 50 points all on Prolog and ML, which wasn't very representative of the course. I hope the curve is low and grading scale adjusted differently than 50% final!

You too, Fox.

Thanks, Sean. Once again, your intelligence and devilish good looks have kept me from dropping this class in frustration.

Yongbo:

You should figure it out as an exercise. Use the type precedence rules on page 313 of Sethi.

Taybo:

Your answer is not correct. Think of it this way:

Would you draw the array layout differenly for integers vs reals (which take up more space in memory)? For allocation you actually need to know the sizes of array elements. Sethi says "the layout of the array determines the machine address of an element A[i] relative to the address of the first item." "The machine address" has to do with location, not size. Locations can be described using relative addresses.

 fn : ('a * 'b -> 'b) -> 'a list -> 'b -> 'b

What does the above function type mean?

In the posted solutions for the midterm, problem 1, the definition of layout is given as "determine locations for storage." The other feasible solution is "determine the sizes for storage needed." Shouldn't it be the latter? I thought allocation is when you actually assign memory, and layout is when you just see "how it looks" in some abstract place in memory, more or less.

Thanks for the clarification.

Mickey - this is how "not()" is (or can be) implemented. To see how it works, and to gain a much better understanding of how prolog works, I encourage you to try tracing through the search tree in both the "X is true" and "X is false" cases. Remember: prolog tries rules from top to bottom, and satisfies subgoals from left to right.

In "Notes on Chapter 11", there is an example of using "not" together with "!(cut)".

not(X) :- X, !, fail.
not(X).

not(fly(penguin)). // #1

not(fly(X)). // #2

so how do these work? What does "succeed" in the sentence "the first caluse for not will try to make fly(penguin) succeed" mean? Why does #2 produce incorrect results?

Amir:

Maybe you have done all this already but:

Of course read chapter 1 in the book.

Also check here:
http://www-cse.ucsd.edu/users/goguen/papers/compl.html
and here:
http://www-cse.ucsd.edu/users/goguen/courses/130/s1.html

Finally, review your lecture notes from the first week of class.

You don't need to know anything about the theory of evolution in biology. Just the evolution of programming languages.

Last touch up question.

Would you please discuss, the history of evolution and emphasis on why , not when or who. Or at least point me in the direction of where I could do some reading on that.

Thanks, much appreciated.

Amir

Then you are enlightened, grasshopper ;). (btw, my experiments show that GNU prolog will go into an infinite loop for (c), and crash for (d), so while they may unify in theory, this fact isn't too useful in practice)

I did read that section and what i get out of it is that yes they unify, but you cant guarantee that the computation will terminate.

Edited by author 03-14-2004 05:27 PM
abster -- Maybe, maybe not -- it depends on the rules. I encourage you to read Sethi on this, as he does a pretty good job explaining, and there are advantages and disadvantages to either approach. If you don't like Sethi on this, the first link for a google search turns up a good explanation.

so what you are saying is that they both unify?

duy -- for extra understanding through extra pain, infer the types of map and reduce.

abster -- (c) See the section in Sethi on the "occurs check", and note that this is a way to create infinite, recursively-defined data structures, e.g.
    X = [1,2|X]
is an endless list of [1,2,1,2,...]. Also note that X = f(f(X)) doesn't have to be strange at all -- f() can be the identity function. (d) same.

yo
i needs some help with understanding #7c and d on previous final.
c) can f(f(X)) unify with X?
    If X can be substituted for f(f(X)) then yes, but the question is: is
    the substitution even possible. Can X unify with an expression
    containing X?? And even if X can unify with an expression
    containing X will the meaning of it be valid in this case. i.e. if we
    sub f(f(x)) for X in both expressions we then get f(f(f(f(x)))) and
    f(f(x)) these two do not seem equivalent.
d) can f(g(X,Y),h(X)) unify with f(Z,h(g(Z,X)))?
     if Z = g(X,Y) and X = g(Z,X) then yes, but as above is the
     substitution if g(Z,X) for X legal or valid as the expression g(Z,X)
     contains X?

Duy--

The map funtion takes in a function and a list as arguments and applies the function to each item in the list.

The reduce function takes in a function and a list and applies the function to the first item in the list and a recursive call to reduce with the function and the tail of the list as arguments.

Think of reduce as a generalization of "sum-all" or "product-all." The difference is that the function can be something else besides add or multiply.

More important than just understanding what these functions do is understanding how and why they work. I suggest tracing through them on some sample input.

Edited by author 03-14-2004 04:26 PM
what is the difference between map and reduction function on page 352(Chapter 9 ML stuff).
Thanks

Good catch. I'm wrong here. Neither of these is more specific than the other, but both are legal substitutions, and both are more specific than the MGU.

Edited by author 03-14-2004 01:43 PM
{ A = B = C = D = X }, which in turn is more specific than { A = C = f(X, Y), B = D = f(Z, W) },

Hey Sean, I don't quite understand why you can make the above assertion. Like you said in the review, you should be able to substitute into a more general unifier to obtain a more specific one. How does it work in this case since you have functors in the second unifier? Substituions are function from Variables to Terms...

Thanks dawg.

Mickey -- I'm not sure I understand your question. Think of the differences between structs and arrays in C.

What is the difference between "array" and "record" again?

Edited by author 03-14-2004 02:29 PM
Amir -- I don't have the exact Sethi description in front of me, but in general, the difference is that objects can have methods and access control (e.g. "private"). In reality, this is just a bit of syntactic sugar, but conceptually, this means that objects can be thought of as "active" things responding to messages, while records are just passive data.

copypaper -- dear God no.

Taybo -- Sure. Unifying
    f(A,B) = f(C,D).
{ A = B = C = D = 3 } is more specific than { A = B = C = D = X }, which in turn is more specific than (Update: this is false -- see later post) { A = C = f(X, Y), B = D = f(Z, W) }, which is more specific than { A = C = X, B = D = Y }, which is the most general unifier (MGU). As I tried to say in the review, you can substitute into the MGU to obtain any other unifier, but not the other way around. Practically, if you build up your substitution recursively, you will end up with the MGU by default:
    f(A, B) = F(C, D)
    { A = C = X } // unifying A and C
    f(X, B) = F(X, D)
    { A = C = X, B = D = Y } // unifying B and D
    f(X, Y) = f(X, Y)

Though my understanding of Prolog has come a long way in the last 24 or so hours, one concept I am still a little unclear on is that of the "most general unifier." Could anyone provide a relatively simple example with two terms that unify under two different unifiers, one of them being the most general. Despite his painfully formal treatment of the concept, I think Sethi really could have used this in the text.

Do we need to know about Quilts for the final?

Edited by author 03-13-2004 09:15 PM
Hey Sean or Fox,

Could you list a couple differences between Objects in Java and Records as defined by Sethi (if there are any).

Thanks,

Amir

Ms. Iqua -- You should know the cool trick that underlies them: that you use variables as parts of lists, then fill those in later. An easier example is inserting items in the back of a list:
    X = [1,2|Y],
    Y = [3,4|Z].
here we leave a hole in X, named Y, then put [3,4] into that hole, leaving a new hole named Z. To test your understanding, you should try to explain difference lists in terms of their creating and filling a hole in a list.

Amir -- To answer your question with a question, the EBNF for statements with a terminator is:
    stmts: { <stmt> <terminator> }*
while that for a separator is:
    stmts: { <stmt> { <separator> <stmt> }* }?
BTW, I don't think you're right about the semicolon in Java; and there's not much to know about sep. vs. term. -- just the definitions.

What is the difference between a terminator and a separator. What are the major differences between them and what would you expect that we would need to know with regards to this topic for the final.

My current understanding is that terminator ends a sequence of code, for example the way a bracket would in java. But, a seperator would seperate segments/lines of code much as a semi-colon would in java.

Do we need to know difference lists for the final? And if so, to what extent?

Edited by author 03-13-2004 04:12 PM
Thanks Sean.

Amir -- Not even in a disjunction, like "Do you want to be social, or do some more programming?" "Social" here is meant in the broader sense that programming languages are products and producers of culture. For example, your familiarity with Java is due largely to social factors like Sun's successful marketing campaign and UCSD's desire to meet perceived industry needs. Students in 5 years will likely be learning C# for similar reasons, which have nothing to do with technical merit. It goes the other way, too -- thousands of Perl programmers socialize at Perl conferences around the world, having been brought together by their common choice of programming language. And the language used to express algorithms strongly influences what algorithms can be expressed, and how easily. Like human languages, programming languages live and die by their users, and in turn influence what these users can say and do.

Abstraction... Think about modules, classes, and objects as units of data abstraction, and blocks, control structures, and procedures as units of control abstraction. Each lets you hide some details of how some data is structured, or how a task is performed. When looking at some language, you should ask yourself what mechanisms it provides for control and data abstraction, and how they differ from the corresponding facilities in other languages. For example, Fortran doesn't do much in the way of control and data abstraction, but does at least have subroutines. C has procedures, blocks, and structured control, all mechanisms of control abstraction that Fortran lacks.

Does anybody have an clue to what is meant by the "social use of programming and programming languages." I don't generally put programming and social in the same sentence, so I'm not really sure how to interpret this.

Secondly, any idea what specifically we need to know as it relates to abstraction. Abstraction, in the outline, is placed within the Introduction, but there is really no discussion about abstraction (or it's definition) in the pages of the book or notes.

Thanks a lot.

Amir

If your Prolog assignment was scored "0" because it was the same as another student's assignment, and you spoke to me during the review session today, please email me.

Hi Everyone,

I hope that our review session and discussion sections were useful. Personally, I would like to make them even more useful in the future. If you have a chance, feel free to send some feedback for future reference.

Good luck (skill) on the final!

Fox

Please explain more about unification, since the previous final includes a question about this, but it seems to be very confusing .

I second the cut. The text is really confusing, it'd be great to get an explanation of it during the review session tmw.

I still don't understand what ! (cut) does in prolog. If this is important in doing well in the final, I would like to see an example on it.

A student emails me:

> pg. 332 Sethi: Type Names and Type Equivalence
> I didn't understand any of the conditions. They seem so vague, do you
> think you could provide an example?

Does any of you have a response, or further questions along these lines? Note that this is material from the first half, and so will be covered less heavily by the final than the more recent material.

"Prolog(ue) to a beating"? Or, for all the optimists out there (where?), "prolog to superior test-taking action"?

"Amalog: Prolog for amateurs"?

Seriously, you guys' posting (and answering!) questions on the webboard will make the review much more productive, both because we can prepare for them in advance, and because seeing others' questions can help you refine your own. So post away, and we will collect and (try to) address the question tomorrow.

I concur.

I think the title of the review session should be "Prolog for Dummies".

sean, i sent you an email. hopefully you've read it.

Edited by author 03-11-2004 12:48 PM
Shaniqua -- (ack, more prolog flashbacks!) This approach is much harder to get working, since you need to use some fancy ML to modify the output parameter. It's much simpler to just construct a return value (recursively).

Update: Ack, my bad! Of course you can build up the result as a parameter (thanks, Shaniqua).

For question 9.5, is it ok if our functions have 3 parameters, i.e. the two sets to be manipulated and a third blank set to hold the result?

All: Assume that the lists representing the sets begin without duplicate elements. You are responsible for making sure that the functions you define ensure that the set representation remains without duplicate elements. (Notice that the problem says "Suppose that sets are...." This means that you take this as a given and then define the functions asked for in parts a-d.)

Shaniqua-yes, yes.

Marilyn:[9.5e] Write a brief paragraph describing what you would need to change given the new implementation (e.g. your functions (besides member) must produce sets represented as sorted lists without repeats).

[9.8] Clear succinct English describing what happens is ok, so is your trace of the function execution.

Edited by author 03-11-2004 05:55 AM
For exercise 9.5, I am not sure how we are to enforce that someone does not declare a set with duplicate elements (since we are just using lists for the implementation). Are we supposed to enforce this somehow; if so, any hints as to what kind of feature to put the the datatype declaration to take care of this?

Edited by author 03-11-2004 01:30 AM
for 9.5 (e) part. could anybody explain more precisely to me?
do we need to implement a) thru d) again with conditions that "sets were implemented by sorted lists w/out repeated elements" or just write what will happen for the result of a) thru d) if it's the case. or what?

Also, 9.8 it requires us to "explain", so we will explain step by step how will we get the answer? like i.e.
reverse([2,3,4],[1]) = reverse([3,4],[2,1])
                     = reverse([4],[3,2,1])
                     = reverse([],[4,3,2,1])
                     = [4,3,2,1]
if we write explaination of reduce add[1,2,3,4],0 like that, is it acceptable?

dauuum gurrll, whatchu talkin bout? sheeit you gotsta bring daddy da green yo... where my money auuut hoe? i don want ta hear none of dis buuuulsheeeit!

I thought I understodd everything, until I read that our code was responsible for removing duplicates within a set. Are we not to assume that the user inputs a set? Or do we assume that they've input a list, remove all duplicates (if any exist), and THEN do the action that the portion of 9.5 asks for?

Can functions call other functions in ML? If so, do we just cut and paste both functions into the interpreter?

m - c&p (cut and paste ;)

What is the file extension for an ML file? just .ml? Also after i get to the command line with "-", how do I run my file?

Shaniqua -- (Whoa, bad prolog flashbacks...) No. Your code is responsible for removing duplicates.

in regards to question 9.5, so if we implement sets using lists, can we assume that if duplicates exist within the list represenation of a set, that they are adjacent?

Edited by author 03-10-2004 02:34 PM
Fox -- does your factorial function work for numbers other than 4? ;)

Shank (1-3) -- it should be called "sml" or "smlnj". Type that at the command-line, then copy-and-paste your program into the interpreter. If it still says "=" rather than "-", try typing in a few semicolons, since it thinks you're in the middle of something (sure welcome).

A set is a simple, unique, associative container -- it can contain zero or one of an item, and you can query whether it contains a given item. Its semantics should be the same as those for Java sets (basically, a hashtable whose values equal its keys).

Dan -- no. You should implement sets using lists.

Brian -- Sure your scores are (email me).

Mickey -- "sml" (see above).

I have the same question as shank you. After "prep smlnj", what should I do to run a program? If someone could explain it, I would very much appreciate it.

ML compiler!??!!? how do you use it, where can i find it?

for question 9.5, what exactly is a set? can i see a simple example?

Hi, Fox or Sean is there a way for me to check all my scores so far. I know I should have kept all my homeworks. Sorry

for question 9.5 for we want to say that an element is a member of a set, can we just write "if x mem b then....."

Is this syntactically correct in mL?

how exactly do we write and compile a program in ML?

gw: The "factorial" function works as follows:
factorial (4) will return 24.

The tail-recursive version works like your first example.

what does the factoria function look like?
factoria(4, 1) = 24
or
factoria([1,2,3,4], 1) = [1,2,6,24]

Implement sets using lists. Lists do not automatically have duplicates removed. Your implementation should behave as a set. Filtering out duplicates is an efficient way to enforce appropriate behavior for your implementation.

in regards to question 9.5, are our parameters already sets, so that duplicates are already removed, or are they lists, meaning we have to filter out duplicates ourselves?

Omid -- the short-circuit version of "or" is called "orelse" (there's also "andalso" for short-circuit "and"). Yeah, it's weird.

Edited by author 03-09-2004 07:25 PM
hello,
i was wondering how we would do this in ML:

if (X or Y) then...
else...

i tried using or, |, || and OR.

i also tried formating as:

if X or if Y...

but that didnt work either...

is it possible to do this?

thanks,

Omid.

Yongbo -- don't do that. Every expression in ML has a value, and you should use these values. Trying to think in terms of functions (i.e. consuming values and producing others) instead of procedures (i.e. transforming data by a sequence of steps) helps. One thing you can do is to bind these intermediate values with "let", like
    let a = print "hello"
    in 2 + 3
    end;

Edited by author 03-09-2004 01:38 PM
What is the syntax in ML for the following code in Java

if(something) {
   statement;
   statement;
}
else
    statement;
I could not find the syntax for executing more than one statement in the "then" block
Thanks!

Edited by author 03-08-2004 11:35 PM
Thanks Sean!
 I meant: "2::[3,4,5]" yields "[2,3,4,5]."

(I've been going over too many "append" examples between this chapter and the Prolog assignment!)

Fox -- "[2]::[3,4,5]" should be an error, since it's trying to push an int list onto a list of ints (i.e. "[[2],3,4,5]")

Students -- the "len(X)" example mistakenly refers to another function, "length". It should instead read "len".

Edited by author 03-08-2004 07:23 PM
Mickey:

"::" is the cons operator. It is used for making lists. "[2]::[3,4,5]" returns "[2,3,4,5]." "2::[]" returns "[2]."

Also, review the chapter for how that notation is used in pattern matching, e.g. in the length function. In this case the notation is used to indicate a pattern that an argument may be matched against in the function declaration.

Please check the course webpage. Your concerns (and those of other students) have been noted and the grading scale policy has been updated.

Bill, I quite agree with you . It's not fair at all to change the grading scale in this way, since this will frustrate the students who studied hard for the midterm . I think if the professor meant to do this way, he needs to offer another option : 15% for homework and 35% for midterm for students who did OK for the Midterm, or at least keep the same grading scale .

I don't understand the notation "::" very well.
How can I read it and how can I use it?

I think we should keep the same grading scale. It's not fair to the students who studied their butts off for the midterm, by alleviating the students that didn't!!!.

Instructions for using SML/NJ on ieng9 are at

http://acs.ucsd.edu/info/sml.php

There isn't a lot of online documentation for ML, though some is linked from the SML homepage at

http://www.smlnj.org/

Sethi is probably the easiest resource for this.