EOPL
Marlene Miller
Friedman's Essentials of Programming Language (EOPL).
EOPL uses interpreters to study the execution of languages and to analyze
languages. I'd like to know whether this knowlege is *useful* for people who
use a compiled language such as C++.
When you are trying to understand C++, do you imagine or explain the
semantics as if an interpreter where evaluating the program?
Is EOPL mostly for people who research and design languages, or is it also
for ordinary programmers?
Thank you,
Marlene Miller
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Thant Tessman
> This question is addressed to those users of C++ who have studied Daniel
> Friedman's Essentials of Programming Language (EOPL).
>
> EOPL uses interpreters to study the execution of languages and to analyze
> languages. I'd like to know whether this knowlege is *useful* for people who
> use a compiled language such as C++.
There's concepts in there (like continuation-passing-style) that don't
translate to the C++ world at all, but the more you learn about
programming in general, the better programmer you are regardless of the
language(s) you use.
> When you are trying to understand C++, do you imagine or explain the
> semantics as if an interpreter where evaluating the program?
No. What's important is the model of computation that the programming
language is trying to embody. Interpreters often make it easier to
understand that model of computation (because an interpreter is supposed
to allow you to ignore the lower-level abstractions upon which the
interpreter itself is built), but they aren't necessary, and in the case
of C++ don't really help.
> Is EOPL mostly for people who research and design languages, or is it also
> for ordinary programmers?
There is a point of view that considers the difference between "ordinary
programming" and "language design" as a matter of degree, not of kind.
-thant
Antoun Kanawati
> Marlene Miller wrote:
>
>>This question is addressed to those users of C++ who have studied Daniel
>>Friedman's Essentials of Programming Language (EOPL).
>>
>>EOPL uses interpreters to study the execution of languages and to analyze
>>languages. I'd like to know whether this knowlege is *useful* for people who
>>use a compiled language such as C++.
>
>
> There's concepts in there (like continuation-passing-style) that don't
> translate to the C++ world at all, but the more you learn about
> programming in general, the better programmer you are regardless of the
> language(s) you use.
The simplification/transformation of recursive programs is a direct
application of CPS, in C++ or any other language. Closures are
not exactly C++, however the other representations of continuations
are mere data structures, mappable to C++ with ease.
>>Is EOPL mostly for people who research and design languages, or is it also
>>for ordinary programmers?
>
>
> There is a point of view that considers the difference between "ordinary
> programming" and "language design" as a matter of degree, not of kind.
Once you drop the syntax out of the way, any data structure can be seen
as an abstract syntax tree. But, then again, this is only my opinion :)
--
A.K.
Thant Tessman
> Thant Tessman wrote:
>
> > Marlene Miller wrote:
[...]
> >>EOPL uses interpreters to study the execution of languages and to analyze
> >>languages. I'd like to know whether this knowlege is *useful* for people who
> >>use a compiled language such as C++.
> >
> >
> > There's concepts in there (like continuation-passing-style) that don't
> > translate to the C++ world at all, but the more you learn about
> > programming in general, the better programmer you are regardless of the
> > language(s) you use.
>
> The simplification/transformation of recursive programs is a direct
> application of CPS, in C++ or any other language. [...]
Good point, but show me someone whose leveraged CPS in C++ to do, say,
coroutines, and I'll show you someone whose written an interpreter.
-thant
Antoun Kanawati
> Antoun Kanawati wrote:
>>The simplification/transformation of recursive programs is a direct
>>application of CPS, in C++ or any other language. [...]
>
> Good point, but show me someone whose leveraged CPS in C++ to do, say,
> coroutines, and I'll show you someone whose written an interpreter.
[pedantic nitpickery: ... someone who's ... (twice) :-]
Frankly, I am missing the point.
In the particular case of coroutines: show me any implementation of
coroutines in C/C++, and I'll show you a concrete representation of
continuations.
In fact: show me any program, and I'll show you the continuations:
it's the runtime stack and the program counter. Not exactly concrete,
not a class or data structure you can mess with freely, and it doesn't
do call/cc, but it's there.
Continuations are always there, by definition: a continuation is
what your program will do next. EOPL and similar works introduce
a notation and a framework for reasoning soundly and rigourously
about continuations.
It is important to recognize that continuation passing style is
fundamentally a "reasoning" technique, not a programming technique.
With that in mind, it is clear that it is not essential that your
continuations be general purpose closures, or that you have the
equivalent of call/cc or lambda expressions. The form and expressive
power of the continuation notation must match what your concrete
programming system allows.
In particular, if you choose the runtime stack/instruction pointer as
your primary concrete representation of continuations, the results of
applying CPS techniques to your programs may not be apparent to the
naked eye, or distinguishable from more "conventional" approaches.
--
Antoun Kanawati
Thant Tessman
[...]
> Frankly, I am missing the point.
[...]
> It is important to recognize that continuation passing style is
> fundamentally a "reasoning" technique, not a programming technique.
Continuations are a "reasoning" technique. Continuation-passing-style is
a programming and implementation technique--an extremely valuable one.
My point to the OP was that CPS as a programming technique is something
you will not see in C++. This is simply because any attempt to leverage
the technique in C++ to do something like coroutines requires an effort
comparable to building an interpreter or compiler. This doesn't mean
that knowing about CPS won't make you a better C++ programmer, or that
there aren't techniques in C++ which can be thought of in terms of
continuations. But CPS is *not* something you can apply in C++ in the
same sense that one would apply a GoF 'design pattern.'
> With that in mind, it is clear that it is not essential that your
> continuations be general purpose closures, or that you have the
> equivalent of call/cc or lambda expressions. The form and expressive
> power of the continuation notation must match what your concrete
> programming system allows.
As a programmer who has used C++ for reasons that are more often
cultural than technical, my biggest pet peeve is when someone belittles
the difference between programming in a language with genuine support
for closures, and a language like C++ in which they can be faked, but
with much effort and with less-than-satisfying results. Belittling the
difference between a language with support for first-class
continuations, and one without seems twice as absurd.
[...]
-thant
Antoun Kanawati
> Antoun Kanawati wrote:
>>With that in mind, it is clear that it is not essential that your
>>continuations be general purpose closures, or that you have the
>>equivalent of call/cc or lambda expressions. The form and expressive
>>power of the continuation notation must match what your concrete
>>programming system allows.
>
>
> As a programmer who has used C++ for reasons that are more often
> cultural than technical, my biggest pet peeve is when someone belittles
> the difference between programming in a language with genuine support
> for closures, and a language like C++ in which they can be faked, but
> with much effort and with less-than-satisfying results. Belittling the
> difference between a language with support for first-class
> continuations, and one without seems twice as absurd.
It is often best to control one's pet peeves, and refrain from making
statements as the above.
More precisely, in the context of applying CPS techniques while
programming in C++, one cannot ignore the limitations of C++
with respect to closures, lambda expressions, typelessness,
garbage collection, call/cc and the various other niceties that make
Scheme such a lovely language. To ignore these limitations would
be impractical, if not absurd.
Furthermore, my statement is not a general statement about
programming languages. It is a specific statement about the
generalized application of CPS techniques.
Thus, my statement does not belittle nor aggrandize differences; it
merely states the obvious: the successful application of CPS techniques
to real programs in a real programming language while staying in the
domain of that programming language demands that the continuations
remain within the expressive power of said language.
In EOPL, the reader is exposed to a myriad of representations for
continuations. Closures and lambda expressions account for a small
number of these variations.
Finally, I have spent my graduate life slicing and dicing
continutations, navigating between formal proofs and machine language
through Scheme.
--
ak
Thant Tessman
[...]
> Thus, my statement [...]
> merely states the obvious: the successful application of CPS techniques
> to real programs in a real programming language while staying in the
> domain of that programming language demands that the continuations
> remain within the expressive power of said language.
And I'm merely trying to point out the obvious fact that as a rule, CPS
techniques aren't applied in C++ because it lacks the expressive power
to make practical use of them.
[...]
> Finally, I have spent my graduate life slicing and dicing
> continutations, navigating between formal proofs and machine language
> through Scheme.
Sometimes I feel like the only one on the planet who has used
first-class continuations to do real work. Not that academics isn't real
work, but it's sad to see how much useful knowledge seems to go
unnoticed in the industry.
-thant
Antoun Kanawati
> Antoun Kanawati wrote:
>
> [...]
>
>
>>Thus, my statement [...]
>>merely states the obvious: the successful application of CPS techniques
>>to real programs in a real programming language while staying in the
>>domain of that programming language demands that the continuations
>>remain within the expressive power of said language.
>
> And I'm merely trying to point out the obvious fact that as a rule, CPS
> techniques aren't applied in C++ because it lacks the expressive power
> to make practical use of them.
Only if you insist that C++ must support higher order functions, and
first class continuations as you have seen them in Scheme. Given that
C++ has no higher order functions, and its simple semantics, the
continuations that you can derive from a C++ program will naturally
fit within the expressive power of C++. With an appropriate
representation scheme, you can actually realize these continuations
in C++, and play with them beyond the realm of analysis.
It would be quite neat if C++ had higher order facilities comparable
to those in Scheme or ML, bit it doesn't.
>>Finally, I have spent my graduate life slicing and dicing
>>continutations, navigating between formal proofs and machine language
>>through Scheme.
> Sometimes I feel like the only one on the planet who has used
> first-class continuations to do real work. Not that academics isn't real
> work, but it's sad to see how much useful knowledge seems to go
> unnoticed in the industry.
The state of the industry reflects the state of academia. Extensive
education in higher order programming is rare in Comp Sci curricula.
Even in those places where Scheme is taught as a first programming
language, advanced programming courses are usually of a more
conventional nature, except for specialized graduate work, typically
in the domain of Programming Languages theory.
I am quite curious about your industrial applications of CPS
techniques. It would be refreshing to explore that little
known segment of the industry where "real work" provides
such interesting opportunities. It's been my experience
that such jobs exists, but are very rare.
Thant Tessman
> [...] With an appropriate
> representation scheme, you can actually realize these continuations
> in C++, and play with them beyond the realm of analysis.
The claim is not that it's impossible. The claim is that someone
programming in C++ is most likely going to find it's not worth the effort.
[...]
> I am quite curious about your industrial applications of CPS
> techniques. It would be refreshing to explore that little
> known segment of the industry where "real work" provides
> such interesting opportunities. It's been my experience
> that such jobs exists, but are very rare.
It was part of the scripting language we built for this:
"Disney's Aladdin: First Steps Towards Storytelling in Virtual Reality,"
Randy Pausch, Jon Snoddy, Robert Taylor, Scott Watson, Eric Haseltine,
ACM SIGGRAPH `96 Conference Proceedings, Computer Graphics, August 1996.
And yes, it was a rare opportunity--much rarer than it should be given
the hoops I see programmers jump through doing things that shouldn't be
as hard as they are.
-thant
Antoun Kanawati
> The claim is not that it's [CPS techniques] impossible. The claim is that someone
> programming in C++ is most likely going to find it's not worth the effort.
I am someone who programs in C++ for a living, and Java, and Perl, and
god knows what else. And, I disagree, and have disagreed for a few
posts.
Given a problem to solve, the appropriate technique can make life a lot
easier. The inappropriate technique, no matter how sublime it is
otherwise, will remain inappropriate.
Hence, I argue that applying CPS techniques to the right problems,
in C++ and similar languages, is a profitable and enjoyable exercise.
Such has been my experience.
When you're trying to remove recursion, implement coroutines, or
write a threaded interpreter, you cannot avoid modeling some
form of continuation. Surely, knowing about continuations and
their techniques can only make such a task easier, and the results
more robust. And, there are many other programming problems that
will benefit from these techniques.
And, there are other programming problems where the application
of CPS techniques is just unnatural, requires far too much
effort, and yields no satisfying rewards.
Thant Tessman
> Thant Tessman wrote:
> > The claim is not that it's [CPS techniques] impossible. The claim is that someone
> > programming in C++ is most likely going to find it's not worth the effort.
>
> I am someone who programs in C++ for a living, and Java, and Perl, and
> god knows what else. And, I disagree, and have disagreed for a few
> posts.
Eliminating recursion via CPS is one thing, but the fact is that as a
rule, C++ programmers don't use coroutines. Instead they put huge
amounts of effort into hacky OS-level threading. I humbly suggest that
this is because it's easier than using CPS to bridge the semantic
disconnect between C++ and coroutines. (Yes, I know coroutines aren't
always an alternative to OS-level threading, but most of the time they
are. And coroutines certanly don't preclude OS-level threading.)
>
> Given a problem to solve, the appropriate technique can make life a lot
> easier. The inappropriate technique, no matter how sublime it is
> otherwise, will remain inappropriate.
Of course one must choose appropriate techniques, but what about
choosing the appropriate language?
[...]
-thant
Antoun Kanawati
> Eliminating recursion via CPS is one thing, but the fact is that as a
> rule, C++ programmers don't use coroutines. Instead they put huge
> amounts of effort into hacky OS-level threading. I humbly suggest that
> this is because it's easier than using CPS to bridge the semantic
I have a "real" problem: a recursive algorithm that for a very long
time while sucking CPU at 100%. Now, that I have tested it with
small inputs, and polished it up, I want to be able to use it
for large inputs. Since it may run for days on some inputs, it
is vital that I be able to stop and resume computation.
Due to my cultural bias, I have chosen CPS to address the problem.
Transform the algorithm to CPS form, while controlling the shape
of the continuation so that it can be easily saved and restored.
QED. And, it's in C++, of course.
I am not precluding that this problem has not been solved before.
I just find it simpler to apply a technique that I know well,
instead of winging it.
This is one of those cases where I would switch between Scheme
and C++ in the analytical stages.
So, is this an application of CPS to C++ programming, or is
it back of the envelope work in Scheme?
> Of course one must choose appropriate techniques, but what about
> choosing the appropriate language?
I smell a language war :) When you have to work on a product that
has been around for many years, with many teams working on many
parts, it is often the case that the programming language has
already been decided.