Reduce the number of core functions #19

Open
mwatts15 opened this Issue Nov 26, 2012 · 7 comments

Comments

Projects
None yet
3 participants
Owner

mwatts15 commented Nov 26, 2012

We can reduce the number of core functions by removing redundant ones (like GT and LT, ADD and SUB, even MUL and DIV since their implementations are based closely on Java's). The functionality can be added back with a surface layer that translates to the core. The surface layer should probably be added in Java for the sake of providing reasonable traces, but it might be fine to do in Prelude instead.

Collaborator

tvarney commented Nov 26, 2012

Could you please expand on how you would go about doing this? I don't even see how you could remove those and still have similar functionality in Crono, since what you are proposing is essentially removing the core crono functionality. You can't write a sub method in crono without having add and negation, and having a translation layer wouldn't allow for using those operations on symbols. Similarly, you can't write GT without LT, EQ and NOT, and visa-versa (LT requires GT and EQ). Further, the reason for having a MUL and DIV method is that the iterative approach in software is complicated, prone to bugs, and doesn't take advantage of hardware features on any CPU since about 1990.

As for a translation layer in java, I don't see what you are trying to propose. Would that be something that translates the (+ 1 2) directly into a 3? If so, how would it handle (+ var1 var2)? If it is doing that at the time that such a statement would be evaluated currently, it is no different than how we are doing it already. If you were proposing adding special function nodes (an AddNode, SubNode, etc), that could be done and would work fine, but would be a lot of work to rewrite the functions we already have as nodes. Also, it wouldn't readily support function currying.

Owner

mwatts15 commented Nov 27, 2012

On Mon, Nov 26, 2012 at 4:55 PM, tvarney notifications@github.com wrote:

Could you please expand on how you would go about doing this? I don't even see how you could remove those and still have similar functionality in Crono, since what you are proposing is essentially removing the core crono functionality. You can't write a sub method in crono without having add and negation, and having a translation layer wouldn't allow for using those operations on symbols.

I got the idea from PLAI chapter 4, latest edition
(http://www.cs.brown.edu/courses/cs173/2012/book/book.pdf).

Similarly, you can't write GT without LT, EQ and NOT, and visa-versa (LT requires GT and EQ).

Isn't "a > b" the same as "b < a"?

Further, the reason for having a MUL and DIV method is that the iterative approach in software is complicated, prone to bugs, and doesn't take advantage of hardware features on any CPU since about 1990.

I guess you mean iterative software development? My only point is that
we could probably just specify a "multiplicative operator" or
something and apply that to the two operands for MUL and DIV rather
than using '*' and '/' since the implementation is the same. I guess
it isn't exactly the same deal.

As for a translation layer in java, I don't see what you are trying to propose. Would that be something that translates the (+ 1 2) directly into a 3? If so, how would it handle (+ var1 var2)?
In Java it would basically mean making a CronoCoreFunctions.java to
have the core functionality in addition to a CronoFunctions.java where
the translation (desugaring) happens.

For doing it in crono, in prelude.lisp we would have something like:
(define - (lambda (a b) (+ a (* -1 b))))
(define < (lambda (a b) (> b a)))

Which is easier, but I qualify it with my concerns above.


Reply to this email directly or view it on GitHub.

Peace and rockets,
Mark Watts
College of Natural Sciences
University of Texas at Austin

cvidal commented Nov 27, 2012

While I appreciate the minimalistic approach, I don't think it's practical to remove many of the core functions we have already. My foremost concern is how the surface layer would even work. If we defined the core functions we took out in prelude.lisp, the java side has no way to know whether or not they should be traced differently than the rest. Of course, it would definitely be possible to come up with a solution, but it would likely be very kludgy and obfuscate our code unnecessarily.

I do support removing many of the redundant comparison operators, since even without the surface layer it would be fairly clear what's happening in the trace. You can definitely get away with only > and =.

we could probably just specify a "multiplicative operator" or
something and apply that to the two operands for MUL and DIV rather
than using '*' and '/' since the implementation is the same.

I can see where you're coming from, but defining division in terms of multiplication like I think you're proposing would still require taking the reciprocal of one of the operands, which is essentially division. Either way it would require at least 2 core functions.
Since we have floating-point numbers, we also can't really define multiplication in terms of addition (which is what I think Troy was hinting at with "iterative approach") Integer multiplication would certainly be possible, though. I don't think we should be concerned with performance issues.

Owner

mwatts15 commented Nov 27, 2012

we could probably just specify a "multiplicative operator" or
something and apply that to the two operands for MUL and DIV rather
than using '*' and '/' since the implementation is the same.

I can see where you're coming from, but defining division in terms of multiplication like I think you're proposing would still require taking the reciprocal of one of the operands, which is essentially division. Either way it would require at least 2 core functions.

That wasn't what I was thinking of; as far as I know, there isn't a way to define multiplication in terms of division that way. But forget that. My objective is to reduce code duplication in CronoFunction.java, but more importantly to extract out the typing policy for results of arithmetic operations. Currently, each function has almost exactly the same code implementing that policy with only the operators changed. Ideally, the type casting should be handled separately and then the correctly typed arguments passed back and the operation performed.

To be clear, the above is separate from my proposal to separate core operations from surface syntax.

cvidal commented Nov 27, 2012

My objective is to reduce code duplication in CronoFunction.java as well as to extract out the policy as far as types are concerned with arithmetic operations.

Oh, I see where you're coming from now. I just took a close look at CronoFunctions, and I can definitely see that there are a lot of redundant type checks that we could circumvent by reusing other arithmetic functions.

Although the trace would be less readable, I think it would be better to simply redefine the removed functions in prelude.lisp. Since this is a project, our objective should be transparency, which we could lose if we did that in java.

Collaborator

tvarney commented Nov 28, 2012

Currently we have to add Environment printouts, list combinators (?), and re-implement foldr using list combinators. We also have to figure out how to get the statement ((let ((f (\ (x) x))) f) (let ((x 4) x)) working. This is just for the Project B list. If we also wanted to actually deliver on what we promised, we would need a prolog style database and a type inferencing system. In 2 days.

At this point we should be focusing on finishing at least the Project B checklist and finishing up the features we promised in our presentation, not looking at restructuring the core Crono functionality. Removing functions and re-implementing them would just be extra work that we don't strictly need to do, and would be a lot of work if we use a translation layer in java to do so.

Also, say what you want about using a minimalistic AST, but it technically meets the requirements listed and I don't feel that it is an appropriate use of time to attempt to re-write when we have other issues to finish. If you are really concerned about Canata taking points off, I can talk to him and tell him that it was my job to implement it and if he does take points off he shouldn't penalize you two.

Further, as I understand it, tracing doesn't need to be anything particularly fancy. The line about tracing reads

Tracing of Operations to demonstrate concepts that have been implemented

So, if we are printing the return value of each step, that is tracing, since you can see how the concepts have been implemented. It doesn't print anything fancy, like recognizing the beta-reduction of a function as another function, but that isn't mandated by his checklist.

Finally, yes, there is a lot of duplicated code in the arithmetic functions, but that is easier to fix than ripping them all out. Simply create a function that takes two CronoNumbers, does the comparisons, then promotes as needed. The only reason why I haven't worked on that is because it was faster to copy+paste the relevant code than it was to write it properly, and I was attempting to get a working interpreter out as fast as I could (which, coincidentally, I only consider the Interpreter truly done as of 2 commits ago, yesterday, with the vector parsing addition).

@tvarney tvarney closed this Nov 28, 2012

@ghost ghost assigned mwatts15 Nov 28, 2012

Owner

mwatts15 commented Nov 28, 2012

I'm in agreement that we need to focus (and will be focusing) on other things for the immediate future, but I still want to do this thing, so I'm reopening the ticket. I'll do it after we finish for class.

@mwatts15 mwatts15 reopened this Nov 28, 2012

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment