Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!samsung!caesar.cs.montana.edu!milton!uw-beaver!zephyr.ens.tek.com!tekcrl!tekchips!kend From: kend@tekchips.LABS.TEK.COM (Ken Dickey) Newsgroups: comp.object Subject: Re: Continuations Message-ID: <5168@tekcrl.LABS.TEK.COM> Date: 6 Dec 89 21:10:49 GMT References: <2664@bingvaxu.cc.binghamton.edu> <9624@pyr.gatech.EDU> <1623@odin.SGI.COM> <1989Nov28.183816.15252@odi.com> <9964@june.cs.washington.edu> <1989Nov29.225826.19483@odi.com> <10008@june.cs.washington.edu> <5153@tekcrl.LABS.TEK.COM> <3374@brazos.Rice.edu> Sender: news@tekcrl.LABS.TEK.COM Reply-To: kend@mrloog.WR.TEK.COM (Ken Dickey) Organization: Tektronix, Inc., Beaverton, OR. Lines: 200 In article <3374@brazos.Rice.edu> boehm@flora.rice.edu (Hans Boehm) writes: >In article <5153@tekcrl.LABS.TEK.COM> kend@mrloog.WR.TEK.COM (Ken Dickey) writes: > >>In C you get a local/global namespace. You don't have name scoping in >>blocks nested more than 1 deep. That's pretty trivial. >What about: > >int i; >int f() >{ > int i; > ... > { > int i; > ... > } >} > >I won't argue about whether this is trivial, but there are certainly nested >scopes. Try it with functions. >... I am reasonably familiar with >the Scheme literature, and it seems to me that most of the standard >examples involving continuations translate reasonably easily into a >world without closures, though they may be much less clean. Call/cc is >probably not quite the right primitive. An interface closer to >setjmp/longjmp (but without the restriction on the caller to setjmp >exiting, and with a cleaner distinction of what's saved, and what isn't) >probably makes more sense. This would certainly be adequate for >implementing coroutines and the like. It would be similar to >Call/cc(lambda x . (jmpbuf := x; 0)) in Scheme-like languages. The literature I was thinking of is on the order of: Wand, Mitchell: "Continuation-Based Program Transformation Strategies" JACM V 27, #1, January 1980 Friedman, Haynes, & Kohlbecker: "Programming with Continuations" in "Program Transformations and Programming Environments" Ed: P. Pepper Springer-Verlag 1984 Haynes, Friedman, & Wand: "Obtaining Coroutines with Continuations" Computer Languages: V11, #3/4 1986 Haynes, Friedman, & Wand: "Continuations & Coroutines" 1984 Symposium on Lisp and Functional Programming Friedman, Haynes: "Constraining Control" Proceedings 12th Annual Symposium on Principles Of Programming Languages (ACM), January 1985 Wand: "Continuation-Based Multiprocessing" Proceedings of the 1980 Lisp Conference Felleisen, Friedman, Kohlbecker, & Duba: "Reasoning with Continuations" Proceedings of the Symposium on Logic in Computer Science, IEEE Press, 1986 Haynes & Friedman: "Engines Build Process Abstractions" 1984 Symposium on Lisp and Functional Programming Haynes & Friedman: "Abstracting Timed Preemption with Engines" Computer Languages, V20, #2, 1987 (pub Great Britain). Clinger, Will: "The Scheme Environment: Continuations" Lisp Pointers, V1, #2, June-July 1987 I guess I don't quite see what you are looking for here. With a timer interrupt, you can implement multitasking. Other applications [8^] of continuations are non-blind backtracking, dynamic-wind, reasonable error recovery (correct & reexecute), etc. Yes, you can do these things in the os/runtime environment (outside of the C language). Yes, you can do this in less clean ways. Yes, call/cc is not necessarily intuitive to think about. Why do you want something less clean? How do you `reexecute' code in sane ways without a segmented stack? >>>4. C and C++ have first class functions. Functions can be passed as >>> parameters, returned as function values, and assigned to variables. >> >>They cannot be unnamed. They cannot be parameterized. They are *not* >>first class. > >I'm not sure what "They cannot be parametrized" means. For most >interpretations of the sentence, it's wrong. I am thinking of parameterization by currying. With higher order functions, you create families of functions parameterized/specialized for particular tasks. E.g. a function which does numerical integration becomes a specialized integrator by being parameterized with a particular function and can then be used to integrate various intervals. A generic device interface becomes specialized for a particular hardware environment by being parameterized by a particular HW device driver. Et cetera. Sorry for the confusion. > >I would be among the first to argue that languages should provide real >higher-order functions. However, it also seems clear that this requires >garbage collection of one form or another. I have yet to see an open system without a memory allocator. Languages without a `pointer' abstraction save a certain class of errors (i.e. one does not dereference bogus pointers). Dealing with *values* and having the language implementation deal with what fits in a register and what does not can save significantly in implementation time. I do not view automatic storage management as a bad thing. The "GC in an uncooperative environment" people observed that even with partial collection of C code, they were able to take care of storage leaks which they found in almost all large C programs they looked at. Using more memory to get faster development may buy market share where time-to-market is important. >... Furthermore it removes >some control over allocation behavior from the programmer. I don't fully agree with this. Don't use CONS. Allocate data statically. Parameterize your functionals at compile time. Demand and use non-cons runtime services. > .. Both of >these in turn cause some difficulty with programs operating under severe >real-time constraints. C and C++ chose not to go this route. Again, I don't fully agree. It depends on how close you are to the limits. Some C implementations have allocators which don't allocate in constant time (e.g. best fit) and fail in the real-time area. Some highly constrained RT systems are coded in assembler because C is too slow. Some real time applications have enough margin to collect adequately if coded in low-cons style. The Appel-Ellis-Li real-time collector (e.g. with a 68030) looks very interesting. I think that the general picture is unclear enough here that it is difficult to make a blanket statement about real-time systems in general. > ... Given that >they didn't, I know of no way to implement continuations efficiently, >while sticking to the design philsophy of either language. Thus it doesn't >make sense to me to add first-class continuations to C++. But this >argument has nothing to do with their utility to the programmer. > >Hans-J. Boehm >boehm@rice.edu Questions of design philosophy aside, it is interesting to look more closely at what `efficiency' is being asked for. The ability to mix compiled and interpreted code gives a very short design-code-test loop. Not dereferincing bogus pointers eliminates a class of programming errors. *Efficiency in bringing products rapidly to market. Having first class functions help encapsulation and can lead to smaller, cleaner code and more code reuse--which means lower maintainance costs. This means more production efficiency because engineers can be building new product rather than doing maintenance. *Efficiency in product production; less rework, less spoilage. I guess if you are not building production code, you don't care about time-to-build/time-to-market. But you probably aren't worried about hard real-time performance either. ===== Having gone this far, I guess I should make a philosoply statement and do some language bashing so people really have something to flame about. [ Don't get too excited; but I do like a good discussion! ] I think the C is a great language for writing device drivers. When it comes to do doing large systems (>200-500 KLOC), system complexity becomes a larger dragon than execution speed. C has won because of its simple execution model, closeness to assembler, and Un*x usage. In C++, the simple execution model is lost [An assignment statement may copy data 3 times. Strings may be reference counted within the parameter passing mechanism. Arrays may not be allocated until first use. Et cetera.] I know a number of people programming in C++ and none who is happy with it. Using a very complex artifact [a Language has a single defining document and a well understood semantics] like C++ does not help in minimizing system complexity. Go ahead! Call me a language bigot! I deserve it! I have also written 50-100 KLOC each of Pascal and C code, some Smalltalk, APL, FP, Fortran, and a fair amount of Scheme code. I find that Scheme gets in my way the least. Having said that, I think that implementation technologies only make sense in the context of implementations. In some contexts, the language of choice may be C, Basic, Beta, Scheme, Ada, assembler, etc. I go for the best technology I can to solve problems in a given context. I think that the important thing is to know more than 1 technology so that one knows what reasonable choices exist and how to evaluate what is reasonable. [Please, flames to /dev/null -- I freely admit, I don't know it all]. [Non-continuation follow-ups probably belong somewhere other than comp.object] -Ken