Home » forums » LtU Forum

Speed and semantics in CTM Chap. 1

Because it seems highly regarded among LtU members, I've started reading CTM. Already Chapter 1 has provoked some thoughts/questions.

In Section 1.7 (Complexity), the authors introduce an optimization, which, in simplified form, is to use

L=expr
{Fn L L}

instead of

{Fn expr expr}.

This is advertised as changing the enclosing algorithm from complexity 2^n to n^2.

I have no doubt that in practice, i.e. using their implementation of the language (and many (all?) implementations of similar languages) this speedup holds.

But, my question is, what in the semantics of the language makes their speedup claim true?

At this point in the book their language lacks side effects, so, in theory, couldn't a compiler take advantage of referential transparency and "hoist" (is that the right word? seems like it is usally applied to loops) the evaluation of expr outside the function call, i.e. do same optimization suggested?

In general what (if anything) does the semantics of the language allow you to conclude about complexity?

Perhaps an operational semantics allows you to make such conclusions, but I really don't see how a denotational one does. And, if an operational semantics allows you to make complexity conclusions, does this mean that an optimizing compiler could violate semantics (even if such a "violation" were welcome because it resulted in a speedup)?

By bdenckla at 2005-03-22 20:00 | LtU Forum | previous forum topic | next forum topic | other blogs | 6894 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

A couple of comments

...couldn't a compiler take advantage of referential transparency and "hoist" the evaluation of expr outside the function call, i.e. do same optimization suggested?

Usually this compiler optimization is known as common subexpression elimination.

And, if an operational semantics allows you to make complexity conclusions, does this mean that an optimizing compiler could violate semantics?

If the operational semantics says that an operation has O(n^2) complexity and a compiler optimizes it to, say, O(n * log n), IIUC it won't violate the semantics, because O(n * log n) <: O(n^2), so an expression with less time complexity can be used whenever a expression with higher time complexity was expected.

By Daniel Yokomizo at Tue, 2005-03-22 20:33 | login or register to post comments

Are "Optimizations" always better?

Good point, I guess you can define conformance to the semantics as doing at least as well as instead of exactly as well as the reference implementation that the semantics imply.

So that would mean that you are not allowed to use an optimization of the form "usually faster to do this," you can only use optimizations of the form "always faster to do this."

I don't know whether in practice such "not always a win" optimizations are important.

By bdenckla at Tue, 2005-03-22 21:31 | login or register to post comments

It depends on your definition of better

So that would mean that you are not allowed to use an optimization of the form "usually faster to do this," you can only use optimizations of the form "always faster to do this."

Not just faster, faster or equal to. So if your optimization has worst-case complexity equal to the specified, than you can use this.

I don't know whether in practice such "not always a win" optimizations are important.

The answer is, as always, sometimes. It depends on the particular program and its usage.

Now, better usually also depends on other factor. For example memoization trades time for space, usually optimizations require some sort of trade-of (CSE costs an extra register, usually). In the operational semantics you can specify other factors, such as expected space consumption (both used by the operation and the space used by the results), so your optimizations may only happen if such invariants are respected.

By Daniel Yokomizo at Tue, 2005-03-22 21:51 | login or register to post comments

Decidability a problem?

Thanks for the clarification, indeed I should have said something like "at least as fast" where I said "faster."

I wonder, even within a performance category (e.g. considering only time, not time and space), does deciding whether an optimized version will be at least as fast as the unoptimized version end up sometimes butting up against provably undecidable program properties?

In other words, in trying to determine whether an optimization will ever make the program slower, do you ever end up needing to answer an unanswerable question like whether the program will loop?

I realize in that particular case (looping) the question of optimization impact is irrelevant, but I imagine there are similarly-undecidable questions about a program's behavior.

By bdenckla at Tue, 2005-03-22 22:22 | login or register to post comments

Purely based on the number of recursive calls

I can vouch for SML acting in the same manner as Oz.

By Chris Rathman at Tue, 2005-03-22 20:38 | login or register to post comments

One other thing

Another thing that occurred to me is not only could the speedup claim be untrue because of CSE, also it could be untrue since it might be semantically valid (although inefficient) to re-evaluate L.

In other words, at least in a denotational semantics (I'm not sure about operational) I see valid n^2 and 2^n interpretations (implementations) of both syntactic variants.

By bdenckla at Tue, 2005-03-22 22:38 | login or register to post comments

A really really good compiler...

...could do the calculation during compilation such that

{FastPascal 30}

doesn't call the function FastPascal during run time at all, just substituting the result for the above expression.

By Chris Rathman at Wed, 2005-03-23 00:30 | login or register to post comments

Calculating complexity

The first semantics given in CTM is the abstract machine semantics. It is an operational semantics that defines the execution of programs written in a kernel language (see section 2.4). Time complexity can be calculated directly from this semantics, given the assumption that its basic operations are constant time (see section 3.5). If you want to express optimizations such as CSE, you can do it by rewriting the kernel language program.

To calculate the time complexity of actual running programs, we further assume that the compiler is written so that the complexity of a compiled program can be derived in a simple way from the abstract machine semantics. We call such a compiler "straightforward" (see section 4.8.1). Personally, I think compilers should always be straightforward.

By Peter Van Roy at Wed, 2005-03-23 08:49 | login or register to post comments

Thanks for your reply (pointer)

See reply at top level. LtU (Drupal) interface always makes me think I'm replying when I'm just adding a new top-level post.

By bdenckla at Wed, 2005-03-23 16:24 | login or register to post comments

Thanks for your reply

It is not often you can get an answer to your question from an author!

Also I gather from your response that I am incorrectly treating Chap. 1 as self-contained, and should instead view it as kind of a "preview of coming attractions."

I do already have another question about the introduction to laziness (seems to me like it is conflated with memoization) but maybe I should hold my horses until it is discussed further in the book.

Also I wonder whether as I read through and have future questions whether the CTM Wiki might be more appropriate?

By bdenckla at Wed, 2005-03-23 16:22 | login or register to post comments

Chapter 1 of CTM

Actually, we do intend it to be self-contained, so you can understand it without having to read further. Chapter 1 implicitly assumes that there are no hidden surprises: everything you see gets executed!

By Peter Van Roy at Thu, 2005-03-24 08:27 | login or register to post comments