Does anyone know of a LISP variant which allows for manipulation of the
execution stack?
It would be very helpful in natural language processing when trying to do
DFS with backtracking. Without manipulating the stack, normal method
invocation is inadequate because you may need to return to a function other
than the calling one.
For that matter, does anyone know of any language at all in which the
execution stack can be manipulated?
Thanks,
Jimmy Ross
Jimmy Ross wrote:
>
> Does anyone know of a LISP variant which allows for manipulation of the
> execution stack?
You can do it to some extent in Common Lisp using catch/throw, or using
trampolines. You can do it to a much greater extent in Scheme using
call/cc, or if all the interesting calls are in tail position you
can do it very naturally using continuation-passing techniques.
> It would be very helpful in natural language processing when trying to do
> DFS with backtracking. Without manipulating the stack, normal method
> invocation is inadequate because you may need to return to a function other
> than the calling one.
>
> For that matter, does anyone know of any language at all in which the
> execution stack can be manipulated?
Well, Scheme doesn't necessarily use a stack -- its control flow is
described in terms of continuations -- it's just that under normal
flow these continuations tend to follow a stack discipline.
SML/NJ is also implemented in terms of continuations, so it can play
scheme-like games with it's control flow.
If you really want a control stack, then Forth certainly can do this,
and Pop-11 can probably do this. In the late 80's Phil Koopman at CMU
did a *really* fast graph reducer in Forth using this technique, which
the Haskell guys later used to good effect. Both of these languages
put the control-related information on a different stack from the data,
so you can pull some really neat (evil?) stunts if you're so inclined.
"Jimmy Ross" <·····@REMOVE.cc.gatech.edu> writes:
> Does anyone know of a LISP variant which allows for manipulation of the
> execution stack?
Manipulation of _the_ execution stack?
Please explain your assumptions.
--
Duane Rettig Franz Inc. http://www.franz.com/ (www)
1995 University Ave Suite 275 Berkeley, CA 94704
Phone: (510) 548-3600; FAX: (510) 548-8253 ·····@Franz.COM (internet)
"Jimmy Ross" <·····@REMOVE.cc.gatech.edu> writes:
> Does anyone know of a LISP variant which allows for manipulation of the
> execution stack?
>
> It would be very helpful in natural language processing when trying to do
> DFS with backtracking. Without manipulating the stack, normal method
> invocation is inadequate because you may need to return to a function other
> than the calling one.
>
> For that matter, does anyone know of any language at all in which the
> execution stack can be manipulated?
There are several possible answers to this.
(1) If you just want to return to a stack frame farther out, use a downward
closure over RETURN, RETURN-FROM, or GO. Such as:
(defun parse-foo (token-stream success-continuation failure-continuation)
(if ... blah blah ...
(funcall success-continuation ... success data ...)
(funcall failure-continuation ... failure data ...)))
(defun parse-bar (token-stream)
(block winnage
(let ((backup (checkpoint-token-stream token-stream)))
(block lossage
... (parse-foo token-stream
#'(lambda (result)
(return-from winnage `(bar ,result 17)))
#'(lambda (message)
(maybe-show-for-debugging message)
(return-from lossage))))
(restore-backup token-stream backup)
(try-alternate-foo-parse token-stream))))
(2) The second way you can do this is to use dynamic tags like catch and
throw. In this case, you don't have to do things as explicitly as
in (1) but you get a similar effect. You do have the problem that
if you end up dynamically nesting certain routines that share the same
tags, you can get them confused in ways that can't happen in (1) but it's
possible to ensure that never happens.
(defun parse-foo (token-stream)
(if ... blah blah ...
(throw 'parse-success ... success data ...)
(throw 'parse-failure ... failure data ...)))
(defun parse-bar (token-stream)
`(bar ,(catch 'parse-success
(let ((backup (checkpoint-token-stream token-stream)))
(catch 'parse-failure
... (parse-foo token-stream) ...)
(restore-backup token-stream backup)
(try-alternate-foo-parse token-stream)))
17))
(3) You can make your stack a datastructure and sit in a loop never pushing
any Lisp stack, just pushing and popping a stack data structure of your
own devising using PUSH and POP or (better, since it mostly won't cons)
VECTOR-PUSH-EXTEND and VECTOR-POP.
If you don't like any of these, use Scheme and read about first class
continuations, which gives you the most general form of control.
"Jimmy Ross" <·····@REMOVE.cc.gatech.edu> writes:
> Does anyone know of a LISP variant which allows for manipulation of
> the execution stack?
In CMU, the multiprocessing implementation is built on stack groups.
There is an interface to them in the mp code.
I guess they're called stack groups because apparently there is a
binding stack, an alien stack, an eval stack and a control stack.
I don't understand that code, but it's clear that to do the lisp
multiprocessing you have to be able to fiddle with the flow of program
execution, and this sounds like what you want to do.
> It would be very helpful in natural language processing when trying
> to do DFS with backtracking. Without manipulating the stack, normal
> method invocation is inadequate because you may need to return to a
> function other than the calling one.
OTOH, you can use something like Screamer, which gives a higher level
interface to the same kind of thing. (Screamer, by the way, is an
example of a program that depends on a code-walker. It uses the code
walker to transform portions of a user program into
continuation-passing-style.)
--
Fred Gilham ······@csl.sri.com
Do remember you're there to fuddle him. From the way some of you
young fiends talk, anyone would suppose it was our job to teach!
-- The Screwtape Letters, C. S. Lewis
On Wed, 6 Mar 2002 20:30:24 -0500, "Jimmy Ross"
<·····@REMOVE.cc.gatech.edu> wrote:
> Does anyone know of a LISP variant which allows for manipulation of the
> execution stack?
>
> It would be very helpful in natural language processing when trying to do
> DFS with backtracking. Without manipulating the stack, normal method
You may check chapters 20-23 of Paul Graham's book "On Lisp", which is
available at his Web site:
http://www.paulgraham.com
Paolo
--
EncyCMUCLopedia * Extensive collection of CMU Common Lisp documentation
http://www.paoloamoroso.it/ency/README
[http://cvs2.cons.org:8000/cmucl/doc/EncyCMUCLopedia/]
Thanks for all the replies. call/cc is exactly what I was looking for (4.5
years as a CS major at Georgia Tech and they never mentioned this... I'm
going to have to have a little chat with some profs).
-Jimmy
"Jimmy Ross" <·····@REMOVE.cc.gatech.edu> writes:
> Thanks for all the replies. call/cc is exactly what I was looking for (4.5
> years as a CS major at Georgia Tech and they never mentioned this... I'm
> going to have to have a little chat with some profs).
But perhaps there is a reason why they haven't mentioned it. It may do
precisely what you want it to do, but it may also be more expensive
than you can live with.
Sorry for my cryptic question previously. It was designed to wrench you
away from the notion that there was one place where backtracking could be
done, and that that was on "the" execution stack. It appears that you have
now discovered that there may be more than one execution stack (although
call/cc is not necessary to achieve that) but one further assumption that
I'd like to smash is the assumption that you need an execution stack at all
to do your backtracking. You only need a stack; it doesn't need to be an
execution stack; it might be a data stack instead, and it might be as simple
as pushing/popping from a list. You might find such data stacks more
efficient than piggybacking on someone's stack-management mechanism.
--
Duane Rettig Franz Inc. http://www.franz.com/ (www)
1995 University Ave Suite 275 Berkeley, CA 94704
Phone: (510) 548-3600; FAX: (510) 548-8253 ·····@Franz.COM (internet)