Hi!
The other day I caught myself thinking that in some cases it would be convenient to have a programmatic access to the stack environment. It
usually is available in debuggers when a break occurs, but I think that
since the data in stack can be thought as a result of some calculation
chain this thing would be of much more general use. For example, in a
simple case of a self-recursive function traversing a tree, the path in
the tree is already there, in the stack, and there's no need to save it somewhere else. There are means to access the stack in C (libunwind
which I haven't tried) and in R (sys.parent, eval.parent and friends,
see https://www.rdocumentation.org/packages/base/versions/3.6.2/topics/sys.parent) but I haven't found any attempts to do that in Lisp. To me it seems very organic to be done in Lisp though. Probably when implemented
thoughtfully it draws a number of problems similar to upward funargs
one and wasn't taken upon by this reason.
So before I made a mess with my toy Lisp, could someone point to an
existing implementation of such thing in Lisp, possibly a description of
some ancient dialect?

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Wednesday, March 31, 2021 at 9:19:19 PM UTC-7, Arseny Slobodyuk wrote:

Hi!
So before I made a mess with my toy Lisp, could someone point to an
existing implementation of such thing in Lisp, possibly a description of
some ancient dialect?

(As you probably know) There isn't any standardized way to do this.
But if you are looking for an example, you could look at the SBCL code
for the function SB-DEBUG:LIST-BACKTRACE.

This may not be quite as useful as you hope, especially since there is both
a lot of implementation-dependent items as well as things like tail call optimizations that can make it hard to interpret. Not to mention that it is
of course subject to change without notice at the discretion of the implementation.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

But if you are looking for an example, you could look at the SBCL code
for the function SB-DEBUG:LIST-BACKTRACE.

Thank you, Tom! I'll try to look into it. Indeed, this feature prevents
tail recursion optimization from being made. This again is why it fits
to Lisp nicely.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Arseny Slobodyuk <arseny@mail.org> wrote:

For example, in a
simple case of a self-recursive function traversing a tree, the path in
the tree is already there, in the stack, and there's no need to save it somewhere else.

AIM-443: what stack is it that you imagine exists?

--
the small snake

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

AIM-443: what stack is it that you imagine exists?

This document looks ancient.
Do you remember a moment in T.Gilliam movie "The Imaginarium of Doctor Parnassus" when monks read their books about the world and the world
starts to exist? So does the stack exist or not depends on my intent.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Zyni Mo? <no_email@invalid.invalid> wrote:

Yes, was a long time ago (years before I was born) that people worked out that function call and GOTO can be the same thing. From this came
everything like CPS conversion etc. CPS programs simply have no stack, at all: no function call ever returns so all function calls are now GOTO.

(defun kfact (n k)
(if (zerop n)
(k 1)
(kfact (1- n) (lambda (x)
(k (* x n))))))

(defun id (x) x)

(kfact 5 id)

(kfact 4 (lambda (x)

(id (* x 5))))

(kfact 3 (lambda (x)

((lambda (x)
(id (* x 5)))
(* x 4))))

(kfact 2 (lambda (x)

((lambda (x)
((lambda (x)
(id (* x 5)))
(* x 4)))
(* x 3))))

(kfact 1 (lambda (x)

((lambda (x)
((lambda (x)
((lambda (x)
(id (* x 5)))
(* x 4)))
(* x 3)))
(* x 2))))

((lambda (x)

((lambda (x)
((lambda (x)
((lambda (x)
(id (* x 5)))
(* x 4)))
(* x 3)))
(* x 2)))
1)

Looks suspiciously like a stack to me.

But like everything people still live in their heads in a world of
clockwork PDP-11s, because that world is easier to understand than the real one.

--
Nils M Holm < n m h @ t 3 x . o r g > www.t3x.org

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Arseny Slobodyuk <arseny@mail.org> wrote:

This document looks ancient.

Yes, was a long time ago (years before I was born) that people worked out
that function call and GOTO can be the same thing. From this came
everything like CPS conversion etc. CPS programs simply have no stack, at
all: no function call ever returns so all function calls are now GOTO.

But like everything people still live in their heads in a world of
clockwork PDP-11s, because that world is easier to understand than the real one.


--
the small snake

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Yes, was a long time ago (years before I was born) that people worked out that function call and GOTO can be the same thing. From this came
everything like CPS conversion etc. CPS programs simply have no stack, at all: no function call ever returns so all function calls are now GOTO.

But like everything people still live in their heads in a world of
clockwork PDP-11s, because that world is easier to understand than the real one.

[ Drifting off-topic: ]
There are other points of views for which continuations aren't "real".

E.g. call/cc corresponds (in the Curry-Howard isomorphism) to the law of excluded middle (LEM), which is a standard axiom of classical logic but
is the main axiom not included in constructive logic because LEM gives
you access to proofs which can't be constructed ("aren't real").
[ The deceptive part of it is that LEM is rarely really needed: you
don't need the LEM axiom to prove that integers are either odd or
even, and indeed for most such "either/or" you can actually prove
the proposition without having to resort to an axiom. ]

In terms of programming, the problem with continuations can be
represented by the following: if your functions never "return",
then how do you write the initial continuation?
Of course there is a standard answer to that: make it be the `halt`
primitive which stops the machine or calls itself infinitely, but from
a "real world" perspective, this is not fully satisfactory.


Stefan

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Yes, was a long time ago (years before I was born) that people worked out that function call and GOTO can be the same thing. From this came

I was once surprised how programmers of the past saw almost no
difference between goto labels and function names.

everything like CPS conversion etc. CPS programs simply have no stack, at all: no function call ever returns so all function calls are now GOTO.

I thought the Steele's paper is against GOTO.
My, what a struggle it was. I'm still afraid to use GOTO, though nobody
beats me with a wooden pointer for it today.
Actually it's a good idea for me - as long as everything is collected in
the stack no need to return because it would be lost. Stack is needed
though.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Arseny Slobodyuk <arseny@mail.org> writes:

So before I made a mess with my toy Lisp, could someone point to an existing implementation of such thing in Lisp, possibly a description
of some ancient dialect?

I think what you really want is called a zipper data structure, which is something like a reified stack pointing into a tree or other such
object.

https://en.wikipedia.org/wiki/Zipper_(data_structure)

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 4/3/2021 6:24 AM, Zyni Moë wrote:

Arseny Slobodyuk <arseny@mail.org> wrote:

This document looks ancient.

Yes, was a long time ago (years before I was born) that people worked out that function call and GOTO can be the same thing. From this came
everything like CPS conversion etc. CPS programs simply have no stack,

at

all: no function call ever returns so all function calls are now GOTO.

But like everything people still live in their heads in a world of
clockwork PDP-11s, because that world is easier to understand than the real one.

It curious that the opposite was observed first I think, i.e., the
observation that any program can be written without GOTO`s. I know that
Knuth attributed this observation to D. Val Schorre (spelling?) in ART.
An interesting way to see this is generate a subroutine for each label
(target of a GO, not a functional closure) that takes all visible
variables as arguments. A GO then turns into a CALL! A RETURN from a
routine in the original was replaced by a CALL on a generated routine
that represented the return point with the current values of all the
variables that would be visible at that point. This was theory. The
amount of stack that would be chewed up by most programs would be
incredible. Of course you could take the transformed program and convert
it back to a no-CALL program but it would be much larger still.

I worked with Val at SDC in the 1960`s when we were doing Lisp 2 along
with III. Val and Erwin Book, as part of a very early SIGPLAN at UCLA,
wrote a very competent meta compiler with a simple Lisp in its gut. That
meta compiler was rewritten in Lisp 2 (I think they had META automate
the transform) and then incorporated it into the Lisp 2 system. So META
was available to any user of Lisp 2.
--
Jeff Barnett

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 2021-04-03, Stefan Monnier <monnier@iro.umontreal.ca> wrote:

In terms of programming, the problem with continuations can be
represented by the following: if your functions never "return",
then how do you write the initial continuation?

Ordinary functions have that problem. If functions return to a
caller, how do you write the initial caller?

You don't; you hack together a stack frame which looks like there had
been an initial caller, such that the return jumps to some entry point
in the system that terminates the program or thread or whatever,
or hits that special trap or halt instruction.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

I think what you really want is called a zipper data structure, which is something like a reified stack pointing into a tree or other such
object.

https://en.wikipedia.org/wiki/Zipper_(data_structure)

I don't think it's what I want but thanks. It seems to fit the case when
a tree already exists while my trees need to be built yet. Another
example is a conjunction expression where variables are bound to various
values until the solution is found and then the solution is in the stack.
I think the thing I want is current bindings which are not disappearing
nor shadowed in a nested call. More precisely I want to try it for a
while to decide whether I want it or not.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Nils M Holm <nmh@ananda.local> wrote:

Looks suspiciously like a stack to me.

Yes. Any program which has a list of things still to do must have a list
of things still to do. But it is not just a stack: it is a first class
object which can be invoked or not invoked, or invoked several times. Is
much more than a stack.



--
the small snake

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Zyni Mo? <no_email@invalid.invalid> wrote:

Nils M Holm <nmh@ananda.local> wrote:

Looks suspiciously like a stack to me.

Yes. Any program which has a list of things still to do must have a list
of things still to do. But it is not just a stack: it is a first class object which can be invoked or not invoked, or invoked several times. Is much more than a stack.

Agreed! But it is also a stack.

As you noted yourself, as long as you want to suspend one thing
in order to do another, you will need a stack. No matter how
clever the abstraction, you cannot get rid of it.

--
Nils M Holm < n m h @ t 3 x . o r g > www.t3x.org

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Nils M Holm <nmh@ananda.local> wrote:

As you noted yourself, as long as you want to suspend one thing
in order to do another, you will need a stack. No matter how
clever the abstraction, you cannot get rid of it.

There will be objects which may be stacks: perhaps one, perhaps many,
perhaps the machine's stack, perhaps more than one, perhaps managed by the programmer, perhaps by the compiler, perhaps by the hardware. Perhaps they will not be stacks at all but queues or some other structure.

If I write an agenda-based search which is the stack (which is likely not a stack) it is useful to print for debugging or to capture to keep the state
of the search?

This question does not have a simple answer in general (does for the agenda-based search: the agenda) which is why it is not right question to
ask.

--
the small snake

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Arseny Slobodyuk <arseny@mail.org> writes:

everything like CPS conversion etc. CPS programs simply have no stack, at >> all: no function call ever returns so all function calls are now GOTO.

I thought the Steele's paper is against GOTO.
My, what a struggle it was. I'm still afraid to use GOTO, though

what abount prog ? yes it is evil. I like loop way too much.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

In article <jwvpmzbxwxj.fsf-monnier+comp.lang.lisp@gnu.org>,
Stefan Monnier <monnier@iro.umontreal.ca> wrote:

Yes, was a long time ago (years before I was born) that people worked out
that function call and GOTO can be the same thing. From this came
everything like CPS conversion etc. CPS programs simply have no stack, at >> all: no function call ever returns so all function calls are now GOTO.

But like everything people still live in their heads in a world of
clockwork PDP-11s, because that world is easier to understand than the real >> one.

[ Drifting off-topic: ]
There are other points of views for which continuations aren't "real".

E.g. call/cc corresponds (in the Curry-Howard isomorphism) to the law of >excluded middle (LEM), which is a standard axiom of classical logic but
is the main axiom not included in constructive logic because LEM gives
you access to proofs which can't be constructed ("aren't real").
[ The deceptive part of it is that LEM is rarely really needed: you
don't need the LEM axiom to prove that integers are either odd or
even, and indeed for most such "either/or" you can actually prove
the proposition without having to resort to an axiom. ]

I have this thesis about Cauchy rows in intuitionistic mathematics.
Basically you can replace
There exist an epsilon such that ..
by
It is impossible that there does not exist an epsilon ...
and you are good to go.
This makes me think that evading the excluded middle is
mostly a boring exercise.

<SNIP>

Stefan

Groetjes Albert
--
"in our communism country Viet Nam, people are forced to be
alive and in the western country like US, people are free to
die from Covid 19 lol" duc ha
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

albert@cherry.(none) (albert) writes:

I have this thesis about Cauchy rows in intuitionistic mathematics.

I hadn't heard of Cauchy rows, and the only web search hits I found were
from some functional analysis notes by R. R. van Hassel. Looking at the
notes I think by "Cauchy row" the author means what in English is
usually called a Cauchy sequence: he says that a metric space is
complete iff every Cauchy row converges. The notes do look interesting
in general.

Basically you can replace
There exist an epsilon such that ..
by
It is impossible that there does not exist an epsilon ...

That is called the Gödel-Gentzen double-negative translation and it is important!

and you are good to go. This makes me think that evading the excluded
middle is mostly a boring exercise.

No no, it's very interesting, it means intuitionistic proofs can be
translated into computer programs among other things. Intuitionistic
logic may be a niche topic in math, but in computer science it is
fundamental, since it's the main way to prove programs correct. The
Wikipedia article about intuitionistic logic is pretty good.

I don't understand how call/cc translates into the LEM, but I've seen
that stated before, so I hope to understand it someday.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

I don't understand how call/cc translates into the LEM, but I've seen
that stated before, so I hope to understand it someday.

(call/cc f)

calls `f` with the current continuation `k`, which is basically a "function that never returns". When the body of `f` calls `k` with an argument of
type `t`, then `call/cc` returns that argument of type `t`.

Let's assume that (contrary to the usual `call/cc`) `f` is not allowed
to return normally (i.e. the only way it can finish is by calling `k`).
[ You can recover the usual semantics by simply using
(call/cc (lambda (k) (k (f k)))), so this difference is not
fundamentally important. ]

So if you think in terms of types, you have

k : t → ??
f : (t → ??) → ??
call/cc: ∀t.(((t → ??) → ??) → t)

The ?? indicates the return type of functions which should never
return, which can be represented by the empty type (i.e. the
type which has no inhabitants), usually denoted `False`.
and since `¬A` is encoded in intuitionistic logic as `A → False`,
you get

call/cc: ∀t.(((t → False) → False) → t)
call/cc: ∀t.(¬¬t → t)

And you can easily prove equivalence between this "double negation" rule
and the law of excluded middle.


Stefan

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)