People should learn STREAMS. When some section of code requires
and allows it, you can trade abstraction for more speed by using LOOP
(you also gain by making it more accessible to the noninitiated).
--
Fernando D. Mato Mira
Real-Time SW Eng & Networking
Advanced Systems Engineering Division
CSEM
Jaquet-Droz 1 email: matomira AT acm DOT org
CH-2007 Neuchatel tel: +41 (32) 720-5157
Switzerland FAX: +41 (32) 720-5720
www.csem.ch www.vrai.com ligwww.epfl.ch/matomira.html
Fernando D. Mato Mira wrote:
>
> People should learn STREAMS. When some section of code requires
> and allows it, you can trade abstraction for more speed by using LOOP
> (you also gain by making it more accessible to the noninitiated).
About 10 years ago, some wizards at ICAD came up with a LET-STREAMS
macro, which, at the time, consistently outperformed LOOP, MAPxxx, and
DOxxx. It was declarative and I think it relied on a lot of
partial-evaluation. I don't know how, if at all, LET-STREAMS is related
to SERIES or GENERATOR/GATHERERS (appendix to CLtL2).
Has anyone done a recent survay of the state of the art in iteration and
come to any conclusions about any clear winners for either efficiency,
customizability or perspicacity.
"Howard R. Stearns" wrote:
> Fernando D. Mato Mira wrote:
> >
> > People should learn STREAMS. When some section of code requires
bzzt. SERIES
--
Fernando D. Mato Mira
Real-Time SW Eng & Networking
Advanced Systems Engineering Division
CSEM
Jaquet-Droz 1 email: matomira AT acm DOT org
CH-2007 Neuchatel tel: +41 (32) 720-5157
Switzerland FAX: +41 (32) 720-5720
www.csem.ch www.vrai.com ligwww.epfl.ch/matomira.html
"Fernando D. Mato Mira" <········@iname.com> writes:
> "Howard R. Stearns" wrote:
>
> > Fernando D. Mato Mira wrote:
> > >
> > > People should learn STREAMS. When some section of code requires
>
> bzzt. SERIES
A good number of months back I noticed a series package for the Debian
CMU Common Lisp and grabbed it and read the CLTL2 appendix about it
but I didn't think it was _that_ special, but some of it seemed to
allow stuff to be done trivially that I don't remember being certain
about how I'd do it with LOOP. I got the impression that the weird
#z(a b c ...) and other series stuff I remember doesn't really seem to
integrate well with the rest of Common Lisp. Is this why series didn't
become part of ANSI CL?
Who else here has used series? Do any of you use it routinely?
Performance seemed to be pretty good. I think that if I gave series a
serious time investment like LOOP that I might find that I really like
it. But if noone else uses it then it would get annoying to have to
ship the series package with your code and also have anyone else that
looks at your code unable to understand/modify it.
Also, I've heard Screamer mentioned a few times. I've seen a paper on
it before but it didn't indicate where it could be FTP'ed from. Anyone
have any experience/comments about it?
Christopher
Christopher R. Barry wrote:
> A good number of months back I noticed a series package for the Debian
> CMU Common Lisp and grabbed it and read the CLTL2 appendix about it
> but I didn't think it was _that_ special, but some of it seemed to
> allow stuff to be done trivially that I don't remember being certain
> about how I'd do it with LOOP. I got the impression that the weird
> #z(a b c ...) and other series stuff I remember doesn't really seem to
> integrate well with the rest of Common Lisp. Is this why series didn't
> become part of ANSI CL?
Seems pretty well integrated to me. What qualifies for
"well-integrated"
here anyway?
>
> Who else here has used series? Do any of you use it routinely?
> Performance seemed to be pretty good. I think that if I gave series a
> serious time investment like LOOP that I might find that I really like
I use series for almost all looping constructs. Works pretty well and
does
generate good code, especially if you know at compile time the length of
the
result vector.
> it. But if noone else uses it then it would get annoying to have to
> ship the series package with your code and also have anyone else that
> looks at your code unable to understand/modify it.
They'd have to understand your code whether you use series or not.
Understanding
series is not that hard.
Ray
> Also, I've heard Screamer mentioned a few times. I've seen a paper on
> it before but it didn't indicate where it could be FTP'ed from.
ftp://ftp.nj.nec.com/pub/qobi/screamer.tar.Z
Jeff (http://www.neci.nj.nec.com/homepages/qobi)
I am no series expert, having just read the CLtL2 section and glanced
at the implementation, so just my 0.02.
In article <·················@2xtreme.net>,
······@2xtreme.net (Christopher R. Barry) wrote:
> A good number of months back I noticed a series package for the Debian
> CMU Common Lisp and grabbed it and read the CLTL2 appendix about it
> but I didn't think it was _that_ special, but some of it seemed to
> allow stuff to be done trivially that I don't remember being certain
I think the elegance of series (and stream-like mechanisms in general)
is the most important thing.
Disclaimer: I don't know what `elegance' is... (HHOS).
> about how I'd do it with LOOP. I got the impression that the weird
> #z(a b c ...) and other series stuff I remember doesn't really seem to
> integrate well with the rest of Common Lisp. Is this why series didn't
Why not? It's not weird, at least if one is used to the idea of streams
which even a mediocre course in functional programming should ensure.
Or do you mean the fact that not all uses of series can be optimised?
> become part of ANSI CL?
(...)
Of course, I am not answering this question, just guessing the
usual suspects are:
* lack of sufficient confidence that the design was stable and bug-free;
* lack of support by implementors;
* lack of time.
I remember (it's in the series documentation, if not in the CLtL2
section, then in what accompanies the source) that the implementation
does quite some code-walking and transforming of the source program
that uses series (in order to achieve iteration-quality performance,
if that's the phrase I want), and it might not do it correctly in
complicated cases, which is a sort of off-putter.
Vassil Nikolov <········@poboxes.com> www.poboxes.com/vnikolov
(You may want to cc your posting to me if I _have_ to see it.)
LEGEMANVALEMFVTVTVM (Ancient Roman programmers' adage.)
-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
I use the LOOP macro quite a bit. In the past, I have attempted to
use the SERIES macro, but had not such great luck with it. The
problems I had seemed to be related to two issues:
1. The macro didn't seem to have been revised to work with
CLtL2-complying lisps. I had no end of trouble trying to get it
to work with Allegro. There was lots of eval-when stuff, and
that's changed radically (allegro has backward compatibility, but
it required more effort than I was willing to expend to make it
work).
2. I had a hard time getting it to work efficiently because it's a
macro. This means that, in order for it to function effectively,
you need to make sure all the relevant material is available in a
single lexical environment. This made SERIES not do what I was
interested in, lazy evaluation, particularly well. Locally,
SERIES gives a graceful implementation of lazy evaluation. Across
function boundaries, though, it didn't work that well.
On top of this, my use of LOOP is controversial enough locally. Using
yet another new syntax just didn't fly. Since there wasn't any
obvious win for SERIES over LOOP, I stuck with old practice that is
better supported by LISP vendors.
R
>>>>> "Robert" == Robert P Goldman <··············@htc.honeywell.com> writes:
Robert> 1. The macro didn't seem to have been revised to work with
Robert> CLtL2-complying lisps. I had no end of trouble trying to get it
Robert> to work with Allegro. There was lots of eval-when stuff, and
Robert> that's changed radically (allegro has backward compatibility, but
Robert> it required more effort than I was willing to expend to make it
Robert> work).
I think the incompatiblity is the use of compiler-let.
In any case, you can find a version of series that does work with
Allegro. It's at
http://www.mindspring.com/~rtoy/software/series/series.html
This is a version with many fixes supplied by several people. It runs
(almost) correctly on CMUCL, Allegro, and Lispworks.
Robert> 2. I had a hard time getting it to work efficiently because it's a
Robert> macro. This means that, in order for it to function effectively,
Robert> you need to make sure all the relevant material is available in a
Robert> single lexical environment. This made SERIES not do what I was
Robert> interested in, lazy evaluation, particularly well. Locally,
Robert> SERIES gives a graceful implementation of lazy evaluation. Across
Robert> function boundaries, though, it didn't work that well.
If I understand you correctly, to work across function boundaries, you
need to tell series that the function produces series as outputs.
This has worked for me. However, the net result is that "main"
function is now huge because everything got macro-expanded into the
main function. If I don't do this, then lazy evaluation isn't really
done.
Ray
In article <··············@rtp.ericsson.se>,
Raymond Toy <···@rtp.ericsson.se> wrote:
(...)
> If I understand you correctly, to work across function boundaries, you
> need to tell series that the function produces series as outputs.
> This has worked for me. However, the net result is that "main"
> function is now huge because everything got macro-expanded into the
> main function. If I don't do this, then lazy evaluation isn't really
> done.
I am speaking from memory (I looked at s.lisp a couple of years ago);
isn't the essential reason for that the fact that lazy evaluation is
implemented by extensive code walking and transformation of the code?
It seems, at least at first glance, that the implementation could be
more robust if co-routines were available.
(Obviously, I would be happy if there were co-routines in Common Lisp,
but I know that it is not trivial to Do The Right Thing...)
Happy Easter!
Vassil Nikolov <········@poboxes.com> www.poboxes.com/vnikolov
(You may want to cc your posting to me if I _have_ to see it.)
LEGEMANVALEMFVTVTVM (Ancient Roman programmers' adage.)
-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
Vassil Nikolov <········@poboxes.com> writes:
> (Obviously, I would be happy if there were co-routines in Common Lisp,
> but I know that it is not trivial to Do The Right Thing...)
>
Anybody aware of a language that has co-routines as a first class
supported concept? I know of several libraries and other stuff to
emulate them but other than Knuth Vol. 1 there doesn't seem to be much
mention of them in the computer language community.
Of course, they can be emulated by threads but they seem to be a
simpler model to program in, albeit less powerful.
--
Lieven Marchand <···@bewoner.dma.be>
If there are aliens, they play Go. -- Lasker
Lieven Marchand <···@bewoner.dma.be> writes:
> Anybody aware of a language that has co-routines as a first class
> supported concept? I know of several libraries and other stuff to
> emulate them but other than Knuth Vol. 1 there doesn't seem to be much
> mention of them in the computer language community.
>
> Of course, they can be emulated by threads but they seem to be a
> simpler model to program in, albeit less powerful.
Well, the obvious reference is SIMULA, anno 1967 or so.
(Obvious to a Norwegian, anyway :-)
Look at e.g. http://www.dcs.ed.ac.uk/home/rjp/bookhtml/, chapter 14
for a description of SIMULA co-routines, and at
http://www.ifi.uio.no/~cim/sim_history.html for a history of SIMULA.
Stig Hemmer,
Jack of a Few Trades.
In article <···············@gnoll.pvv.ntnu.no>,
Stig Hemmer <····@pvv.ntnu.no> wrote:
> Lieven Marchand <···@bewoner.dma.be> writes:
> > Anybody aware of a language that has co-routines as a first class
> > supported concept?
I think we need to distinguish between:
* support for co-routines as a language construct (and not by means
of implementation extensions, OS system calls, etc.) where besides
Simula we have some latter-day appearances including Modula-2,
Scheme, and some of the functional languages. Also, CLU has some
limited form of co-routines with its iterators (which use ``yield'');
* co-routines as first-class objects---correct me if I'm wrong but
I can think only of Scheme's continuations here.
I believe that co-routines can be very useful even if they are not
first class objects. And one can still achieve good things with them
(e.g. streams) while being saved from many headaches that go with
threads/processes. (Consider this as an illustration: one could use
Ada's tasks to do co-routines, but it would be rather more complicated
than if co-routines were directly supported.)
I guess many languages have saved themselves the trouble of
equipping themselves with co-routine constructs because most people
do it in OS calls. Perhaps UNIX pipes could serve as the canonical
example: their essence is in co-routines but they are commonly
implemented by processes. (Of course, there may be perfmorance
gains from implementing a pipe as a pair of processes, especially
if the two programs are I/O-intensive and/or we have multiprocessing,
but by the essence of pipes I mean that they are _not_ equivalent
to writing the output from the first program to a file and then
giving it as input to the second program.)
(...)
> > Of course, they can be emulated by threads but they seem to be a
> > simpler model to program in, albeit less powerful.
>
> Well, the obvious reference is SIMULA, anno 1967 or so.
Wasn't it _standardised_ in 1967, but developed earlier?
(Sorry, just don't have the time to look at those URLs.)
I don't know if it was just a coincidence that Simula was innovative
in two directions at once---objects/encapsulation and co-routines---
or that this indicates that one needs the other.
Disclaimer: none of the languages mentioned above should be considered
superior, equal, or inferior to any language (whether
mentioned here or not) just by virtue of being mentioned.
(In other words, if anyone wants to start y.a. argument
if language X is better than language Y, they are welcome
to do so, but `include me out.')
Vassil Nikolov <········@poboxes.com> www.poboxes.com/vnikolov
(You may want to cc your posting to me if I _have_ to see it.)
LEGEMANVALEMFVTVTVM (Ancient Roman programmers' adage.)
-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
From: Lars Marius Garshol
Subject: Re: co-routines (Ex: Re: Series. #)
Date:
Message-ID: <wksoaf76xf.fsf@ifi.uio.no>
* Vassil Nikolov
|
| * support for co-routines as a language construct (and not by means
| of implementation extensions, OS system calls, etc.) where besides
| Simula we have some latter-day appearances including Modula-2,
| Scheme, and some of the functional languages. Also, CLU has some
| limited form of co-routines with its iterators (which use ``yield'');
I think Sather has the support as CLU, through iterators with yield.
BETA also has co-routines, although I don't know in what form yet,
since I haven't gotten that far in the tutorial yet. :)
* Stig Hemmer
|
| Well, the obvious reference is SIMULA, anno 1967 or so.
* Vassil Nikolov
|
| Wasn't it _standardised_ in 1967, but developed earlier?
| (Sorry, just don't have the time to look at those URLs.)
There were two Simulas. Dahl & Nygaard started their work on Simula in
1962 and in late 1964 completed SIMULA I, which didn't have OO, but
some special constructs for simulation, which I think were called
ports and gates. This turned out to be insufficient, so they started
working on what later became SIMULA 67 (later known as Simula).
What was done in 1967 was to complete the definition in a conference
paper. This definition was extended in '68 to include string handling
and I/O (the TEXT, INFILE and OUTFILE pseudo-classes).
Only after this was SIMULA 67 implemented. So I think Stig's reference
is entirely correct, provided co-routines were in the 1967 language.
| I don't know if it was just a coincidence that Simula was innovative
| in two directions at once---objects/encapsulation and co-routines---
| or that this indicates that one needs the other.
I think Simula was innovative in more than one direction, and coming
up with an essentially complete object-oriented programming model
_before_ the introduction of Pascal and C is pretty amazing in itself.
Also, Simula takes a much more general view of what classes are than
most other languages do. In Simula, classes are simply a special form
of block (naming context or whatever) which can be used in several
ways: just execute it, create an instance of it with new, or prefix a
block with it to execute it and use the declarations statically.
And, in fact, Simulas co-routines use classes. I don't have any
examples here, but as far as I can tell from the standard I think this
is yet another way to use the naming context a class provides.
This view of classes was taken to an extreme with the BETA language,
which looks like a truly interesting language. Certainly, it is one of
the few languages that take a really different approach to
programming.
Conclusion? God knows. :)
--Lars M.
Lars Marius Garshol wrote:
> * Vassil Nikolov
> |
> | * support for co-routines as a language construct (and not by means
> | of implementation extensions, OS system calls, etc.) where besides
> | Simula we have some latter-day appearances including Modula-2,
> | Scheme, and some of the functional languages. Also, CLU has some
> | limited form of co-routines with its iterators (which use ``yield'');
>
> I think Sather has the support as CLU, through iterators with yield.
>
> BETA also has co-routines, although I don't know in what form yet,
> since I haven't gotten that far in the tutorial yet. :)
also Smalltalk-80. Stack frames can be accessed as context objects via
thisContext. Context objects refer to their caller contexts via a sender
slot. One can assign the sender slot, hence implementing co-routines,
amongst other things (e.g. see "Building a Backtracking Facility in Smalltalk
Without Kernel Support", Wilf LaLonde & Mark Gulik, Proc OOPSLA '88 for a
simple backtracking facility).
_______________,,,^..^,,,_______________
Eliot Miranda, ParcPlace
Vassil Nikolov <········@poboxes.com> wrote:
+---------------
| > > Anybody aware of a language that has co-routines as a first class
| > > supported concept?
|
| I think we need to distinguish between:
| * support for co-routines as a language construct...
| * co-routines as first-class objects---correct me if I'm wrong but
| I can think only of Scheme's continuations here.
+---------------
If by "first-class" you mean the usual -- can be stored & fetched
from user variables, can be provided as an argument to & returned
as a value from arbitrary procedure calls -- then both the BLISS
exchj-based and the C setjmp/longjmp-based co-routines I mentioned
in my other reply are first-class. Both implementations reify the
stack object containing the saved state of a co-routine.
-Rob
-----
Rob Warnock, 8L-855 ····@sgi.com
Applied Networking http://reality.sgi.com/rpw3/
Silicon Graphics, Inc. Phone: 650-933-1673
2011 N. Shoreline Blvd. FAX: 650-964-0811
Mountain View, CA 94043 PP-ASEL-IA
In article <···········@fido.engr.sgi.com>,
····@rigden.engr.sgi.com (Rob Warnock) wrote:
> Vassil Nikolov <········@poboxes.com> wrote:
> +---------------
> | > > Anybody aware of a language that has co-routines as a first class
> | > > supported concept?
> |
> | I think we need to distinguish between:
> | * support for co-routines as a language construct...
> | * co-routines as first-class objects---correct me if I'm wrong but
> | I can think only of Scheme's continuations here.
> +---------------
>
> If by "first-class" you mean the usual -- can be stored & fetched
> from user variables, can be provided as an argument to & returned
> as a value from arbitrary procedure calls -- then both the BLISS
I assumed this was what the original poster meant by `a first class
supported concept,' and yes, this is what I mean by `first class.'
> exchj-based and the C setjmp/longjmp-based co-routines I mentioned
> in my other reply are first-class. Both implementations reify the
> stack object containing the saved state of a co-routine.
Thanks for the information on BLISS. Regarding C's setjmp/longjmp,
I cannot agree.
For one, I want mechanisms that work in the _language_, not in a
specific implementation environment (I read your other reply where
you do say that doing co-routines with setjmp/longjmp is architecture
and compiler dependent). The _portable_ use of setjmp/longjmp is
analogous to CATCH/THROW (I'm not going to spend any time on `Lisp is
better than C,' though), not to resuming a co-routine.
For two, even in an implementation-dependent manner, I don't see how
setjmp/longjmp can be seen to provide co-routines as _first-class
objects_. The contents of a jmp_buf are of course
implementation-dependent, but they would normally carry information
only about the _state_ of the stack, not the stack _object_ itself.
If co-routines are available as first-class objects in a stack-based
implementation, the object that represents a co-routine would somehow
have to include the co-routine execution stack (and probably its
bindings stack as well). I cannot see anything in the description of
setjmp/longjmp that shows how in a standard way one could establish
another stack for a co-routine, not to speak of handling this stack
as a first class object.
So (ANSI) C does not have co-routines even as language constructs,
let alone as first-class objects. (This is not a problem in my eyes;
the problem is that ANSI C does not even have the primitives for
(portably) implementing co-routines.)
All of this is off-topic of course. And it led me to think what
the usefulness of comparing Lisp and C is. My answer is this:
Lisp is a language, while C is an (abstract) specification of a
(particular class of) machine, and it is often useful to see how
a concept at the language level maps to a concept at the machine
level, without restricting oneself to a specific machine. I think
that from this point of view comparing Lisp to C++ is much less
useful than comparing Lisp to C. (Many would probably disagree
with this last statement; I am not sure I am going to reply.)
Vassil Nikolov <········@poboxes.com> www.poboxes.com/vnikolov
(You may want to cc your posting to me if I _have_ to see it.)
LEGEMANVALEMFVTVTVM (Ancient Roman programmers' adage.)
-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
Stig Hemmer <····@pvv.ntnu.no> wrote:
+---------------
| Lieven Marchand <···@bewoner.dma.be> writes:
| > Anybody aware of a language that has co-routines as a first class
| > supported concept? ...
|
| Well, the obvious reference is SIMULA, anno 1967 or so.
+---------------
Or BLISS (1970), which had an "exchj(other_stack, value)" call. The CMU
BLISS tools included a thing called "POOMAS" ("POOr MAn's Simula") that
emulated a good deal of the Simula functionality with some macros and a
small library that sat on top of "exchj" (among other things). And using
BLISS-11 (1972) and "exchj", circa 1975 I wrote a toy multi-user operating
system in an afternoon[*].
And on a few architectures & C compilers [I mention both because both
matter], the C "setjmp()/longjmp()" can be used with no additional
assembly-language code to build coroutines [Unix kernel hackers should
be mumbling "resume()" right about now]. Circa 1982, Bakul Shah & I used
this to build a POOMAS clone in C [v.7 Unix PCC on an m68k], and then
used it for discrete simulation of multi-device DMA bus traffic in the
Fortune Systems 32:16. From the abstract of a talk I gave at the Spring
1984 USENIX:
The toolkit, a library of C routines, comprises three conceptual
layers (the user's simulation is the fourth), each reflecting some
well-known design borrowed from other systems. From the "bottom" up,
they are:
(1) Co-routines and process objects;
(2) Condition variables and priority queues; and
(3) A simulation kernel (the "clock" object and the "busy" statement).
Co-routines and process objects are as in the BLISS language.
Condition variables, priority queues, and the simulation kernel
itself are from Holt's Concurrent Euclid. The overall idea of
providing a simple skeleton for user-written simulations is from
CMU's POOMAS package (POOr MAn's Simula).
But of course, these days one must mention Scheme's "call/cc", as well
as numerous Schemes & Lisps that have user-mode light-weight "threads"
of some sort...
-Rob
[*] Admittedly, it was pretty dumb -- no disk, no inter-user protection,
all the "commands" were compiled in (a la Xinu), etc. -- but we just *had*
to get something running in a hurry to demonstrate a stat-mux for a tradeshow,
and we didn't have a server we could carry with us, only a PDP-11 with 16KB
of core (yes, core!). The toy operating system allowed up to 8 people to
log in from remote terminals and execute a handful of shell commands (most
notably a stub "systat" that showed you who else was on and what they were
doing).
-----
Rob Warnock, 8L-855 ····@sgi.com
Applied Networking http://reality.sgi.com/rpw3/
Silicon Graphics, Inc. Phone: 650-933-1673
2011 N. Shoreline Blvd. FAX: 650-964-0811
Mountain View, CA 94043 PP-ASEL-IA
····@rigden.engr.sgi.com (Rob Warnock) writes:
[snip]
> And on a few architectures & C compilers [I mention both because both
> matter], the C "setjmp()/longjmp()" can be used with no additional
> assembly-language code to build coroutines [Unix kernel hackers should
> be mumbling "resume()" right about now].
[snip]
could I trouble you to outline how one would go about doing this?
in particular, how does one create a second stack which would
automatically grow like the main one does?
andru
[This is getting pretty far off-topic, so maybe after this we should
go private...]
<······@andru.sonoma.edu> wrote:
+---------------
| ····@rigden.engr.sgi.com (Rob Warnock) writes:
| > And on a few architectures & C compilers [I mention both because both
| > matter], the C "setjmp()/longjmp()" can be used with no additional
| > assembly-language code to build coroutines [Unix kernel hackers should
| > be mumbling "resume()" right about now].
|
| could I trouble you to outline how one would go about doing this?
| in particular, how does one create a second stack which would
| automatically grow like the main one does?
+---------------
Those are two separate questions, the first easy and the second much harder.
1. Using C's setjmp/longjmp to build coroutines:
void resume(proc_p p)
{
extern proc_p self; /* the currently running thread */
jmp_buf regs;
if (setjmp(regs))
return; /* we've just been resume'd again */
self->save_area = (long *)®s[0]; /* save pointer to our state */
self = p; /* switch identities */
longjmp(*(jmp_buf*)self->save_area, 1); /* wake our new self */
/*NOTREACHED*/
}
[Note that resume() does *not* save the old "self" anywhere, so the caller
of resume() must do so, usually on a run queue or wait queue or something.]
Obviously, this only works the first time if somebody has created the
new coroutine (a.k.a. thread or process) object's stack and set it up so
that it looks like a setjmp() was previously done. A routine to do that:
proc_p
new_process(int stack_size, char name[], void (*f)(), int arg2, ...)
is a bit more complex than "resume()", so I won't show the whole thing
here, but basically it:
a. Malloc's some space for a new stack;
b. Copies its args into the new stack (for use when calling "f" the
first time, passing "arg2" and some number of further ones).
c. Does a setjmp() into the new stack, then diddles with the saved
value of the stack pointer so that a longjmp() will use the new
stack (with the args "in the right place").
d. Returns the constructed stack object (== thread == coroutine).
e. When resume()'d the very first time, calls "f(arg2, ...)".
On top of new_process() and resume(), one can build [and I have done]
whatever wait & run queues you like. For Simula-like (or these days,
we might say "Verilog-like") simulations, one of the most useful things
is a priority queue for which the key is "virtual time to start" (much
like the old Unix kernel "timeout" facility), and a "busy(n)" which
blocks the current thread until the virtual time in now+n ticks. With
that, plus simple wait-for-event queues, you can build a complete
discrete event simulator.
2. Creating multiple stacks that grow automatically: This ranges from
"trivial" (when using call/cc in Scheme) to "impossible" (running on
systems without multiple virtual memory segments). The above-mentioned
coroutine library set a *fixed* stack size at coroutine-creation time
[see the first arg to "new_process()"], and it was useful for a wide
variety of applications. But it was possible (too easy, even) to overflow
one of the stacks without warning, unless you added some safety code.
The main ways I know of to get multiple independently-growing stacks are:
a. Change the coroutine call so that the currently running thread doesn't
run *on* the stack object, it runs on the "main" stack. This involves
copying the main stack out into the heap & back on every resume()
[and allocating a new larger heap object for a thread's stack whenever
the old one isn't large enough to save a stack being "swapped out"].
This can be cheap or ex*PEN*sive, depending on average stack depth.
[But note that many Scheme implementations that use the C stack as
the Scheme execution stack do precisely this to implement call/cc.]
b. Change the way your compiler(s) work to use "segmented" (or "cactus")
stacks. Not an option for most people.
c. Write in a language that uses a heap-based stack (e.g. some Schemes
or Lisps, and maybe at least one ML?), so that cactus stacks are "free".
d. Play some tricky games (if your O/S lets you) with "mmap()", to allocate
larger-than-you'll-ever-need stacks sparsely in your virtual address
space. Some operating systems implement "allocate on first reference"
pages which are useful for this.
Like I said, it's harder & more environment-dependent than simple
coroutines with fixed-size stacks. (Sorry 'bout that...)
-Rob
-----
Rob Warnock, 8L-855 ····@sgi.com
Applied Networking http://reality.sgi.com/rpw3/
Silicon Graphics, Inc. Phone: 650-933-1673
2011 N. Shoreline Blvd. FAX: 650-964-0811
Mountain View, CA 94043 PP-ASEL-IA
[Sorry for following up to old articles, I've only just got the use of
a news server that works reasonably well.]
* Vassil Nikolov wrote:
> I remember (it's in the series documentation, if not in the CLtL2
> section, then in what accompanies the source) that the implementation
> does quite some code-walking and transforming of the source program
> that uses series (in order to achieve iteration-quality performance,
> if that's the phrase I want), and it might not do it correctly in
> complicated cases, which is a sort of off-putter.
I have a question related to this. Does anyone know of code-walkers
for CL which are reasonably up-to-date with the language and
reasonably flexible? I know of at least a couple (one written by
David Moon and distributed with (and used by?) Genera, but apparently
free, and the PCL one), but at least the Moon one is out of date, and
I remember the PCL one being `funny' somehow.
I'd like one that is pretty competent in terms of things like packages
-- the same way the compiler has to be really.
Thanks
--tim
From: Howard R. Stearns
Subject: Re: Code walkers (was Re: Series. (was Re: About loops))
Date:
Message-ID: <370CB18A.4926975E@elwood.com>
Tim Bradshaw wrote:
>
> [Sorry for following up to old articles, I've only just got the use of
> a news server that works reasonably well.]
>
> * Vassil Nikolov wrote:
>
> > I remember (it's in the series documentation, if not in the CLtL2
> > section, then in what accompanies the source) that the implementation
> > does quite some code-walking and transforming of the source program
> > that uses series (in order to achieve iteration-quality performance,
> > if that's the phrase I want), and it might not do it correctly in
> > complicated cases, which is a sort of off-putter.
>
> I have a question related to this. Does anyone know of code-walkers
> for CL which are reasonably up-to-date with the language and
> reasonably flexible? I know of at least a couple (one written by
> David Moon and distributed with (and used by?) Genera, but apparently
> free, and the PCL one), but at least the Moon one is out of date, and
> I remember the PCL one being `funny' somehow.
>
> I'd like one that is pretty competent in terms of things like packages
> -- the same way the compiler has to be really.
>
I don't think it's giving away any secrets to say that I think Duanne at
Franz is working on some compiler stuff that may or may not involve
making some code walking utilities available to the user (at least
environment stuff will be available), and that I am (though not quite
currently) working on a compiler that definately makes it's extensible
code walker available to users (though a generic function protocol and
user-extensible compiler objects -- a compiler MOP).
It would probably be good for people working on such things to hear what
your application is that you need a code walker for, and what
requirements you have for it.
From: Fernando D. Mato Mira
Subject: Re: Code walkers (was Re: Series. (was Re: About loops))
Date:
Message-ID: <370DED85.9A75FB1A@iname.com>
"Howard R. Stearns" wrote:
> Tim Bradshaw wrote:
>
> > I have a question related to this. Does anyone know of code-walkers
> > for CL which are reasonably up-to-date with the language and
> > reasonably flexible? I know of at least a couple (one written by
>
> I don't think it's giving away any secrets to say that I think Duanne at
> Franz is working on some compiler stuff that may or may not involve
> making some code walking utilities available to the user (at least
> environment stuff will be available), and that I am (though not quite
> currently) working on a compiler that definately makes it's extensible
> code walker available to users (though a generic function protocol and
There's a WALKER package in Harlequin Lispworks, too.
I remember having to tweak a bit the SERIES implementation to make it work
with it back in '94.
--
Fernando D. Mato Mira
Real-Time SW Eng & Networking
Advanced Systems Engineering Division
CSEM
Jaquet-Droz 1 email: matomira AT acm DOT org
CH-2007 Neuchatel tel: +41 (32) 720-5157
Switzerland FAX: +41 (32) 720-5720
www.csem.ch www.vrai.com ligwww.epfl.ch/matomira.html
* Howard R Stearns wrote:
> It would probably be good for people working on such things to hear what
> your application is that you need a code walker for, and what
> requirements you have for it.
Nothing very concrete. I really want to be able to do things like
cross-referencing and who-calls/uses and mechanically instrumenting
code and things like that. I know that packages to do many of these
things exist, but it would be good if the substrate facilities did
too.
--tim
From: Jeffrey Mark Siskind
Subject: Re: Code walkers (was Re: Series. (was Re: About loops))
Date:
Message-ID: <yq7u2ur3x9e.fsf@qobi.nj.nec.com>
> > I remember (it's in the series documentation, if not in the CLtL2
> > section, then in what accompanies the source) that the implementation
> > does quite some code-walking and transforming of the source program
> > that uses series (in order to achieve iteration-quality performance,
> > if that's the phrase I want), and it might not do it correctly in
> > complicated cases, which is a sort of off-putter.
>
> I have a question related to this. Does anyone know of code-walkers
> for CL which are reasonably up-to-date with the language and
> reasonably flexible? I know of at least a couple (one written by
> David Moon and distributed with (and used by?) Genera, but apparently
> free, and the PCL one), but at least the Moon one is out of date, and
> I remember the PCL one being `funny' somehow.
>
> I'd like one that is pretty competent in terms of things like packages
> -- the same way the compiler has to be really.
Screamer (available free from my home page) has a code walker that might fit
your needs.
Jeff (http://www.neci.nj.nec.com/homepages/qobi)
Howard R. Stearns wrote:
>
> Fernando D. Mato Mira wrote:
> >
> > People should learn STREAMS. When some section of code requires
> > and allows it, you can trade abstraction for more speed by using LOOP
> > (you also gain by making it more accessible to the noninitiated).
>
> About 10 years ago, some wizards at ICAD came up with a LET-STREAMS
> macro, which, at the time, consistently outperformed LOOP, MAPxxx, and
> DOxxx. It was declarative and I think it relied on a lot of
> partial-evaluation. I don't know how, if at all, LET-STREAMS is related
> to SERIES or GENERATOR/GATHERERS (appendix to CLtL2).
>
> Has anyone done a recent survay of the state of the art in iteration and
> come to any conclusions about any clear winners for either efficiency,
> customizability or perspicacity.
(let-streams
((...declaration statement...) ... ) ;;; multiple sequential declarations
((return-when <test-statement> return-value) ...) ;;; multiple return
statements
(<debugger-statements>)) ;;; interface for icad development environment
Let-streams is syntactically similar to loop (lots of clever control
constructs),
though I've yet to get anyone from KTI to admit just how it is implemented. The
really
useful part is the interface with the ICAD browser/common-lisp buffer that lets
you
see whats going on during iteration.
Just finished replacing all of the let-streams in an old ICAD (KTIWorld.com)
defpart
with any other appropriate iteration construct (mapcar, dolist, do*, and loop,
in that order).
In the past 3 years, I've NEVER found a let-stream to outperform any other
technique, but they are OK for
development purposes and teaching the concept of iteration to those without
much experience in other development environments/languages.
My conclusion is this: Relative efficiency (execution time and resource
expenditure)
is dependent on
(1) the specific algorithm,
(2) the implementation of the iteration macro (how well it was written and in
what language).
Based on your posting, in the ensuing ten years, Allegro CL (on which ICAD is
based)
iteration macros have become much more efficient relative to let-streams
developed by
KTI (then Concentra), which I assume was written in C or some other such
language.
slong
"Better to be a Client than a Server"