New PLT utility
Paul Steckler
work on a utility that will soon be available from PLT.
The utility is called "down", for reasons that will
become clear. It takes as input an arbitrary S-expression,
and returns a boolean, as follows. If the S-expression
input would return a Scheme value in finite time, when supplied
to PLT Scheme's "eval", "down" returns #t; otherwise it
returns #f. The time needed for "down" to perform this calculation
is not specified. The name "down" is used, because a downward
arrow is used to denote termination, which is what the utility
detects.
The algorithm was kind of tricky to work out, but dang,
it works!
Look for this utility in the next PLT distribution.
More information about the program will be available
in the manual page, plt/man/man1/plt-down.man.
-- Paul
tal...@noshpam.lbl.government
in that formulation?
Specifically, what's the point of the '#f' return value; if the
s-expression never 'halts', then will '#f' ever be returned?
~Tomer
Paul Steckler <st...@ccs.neu.edu> writes:
--
()
Richard C. Cobbe
> Correct me if I'm wrong, but isn't there a halting-problem somewhere
> in that formulation?
This utility is almost exactly a solution to the halting problem, yes. But
see below (and notice the date of Paul's original post).
> Paul Steckler <st...@ccs.neu.edu> writes:
<SNIP>
>> Look for this utility in the next PLT distribution.
>> More information about the program will be available
>> in the manual page, plt/man/man1/plt-down.man.
~~~~~~~~~~~~
But it's *really* just a setup for a somewhat obscure joke.
Richard
Anton van Straaten
> Correct me if I'm wrong, but isn't there a halting-problem somewhere
> in that formulation?
>
> Specifically, what's the point of the '#f' return value; if the
> s-expression never 'halts', then will '#f' ever be returned?
That's a valid concern - in general, the commercial applications for this
promising utility are going to be somewhat limited until this performance
issue can be dealt with. Once that's dealt with, though, I can see a
promising future for it: for example, being able to easily ensure that
high-reliability software won't crash.
To be fair, Paul did address this point:
> The time needed for "down" to perform this calculation
> is not specified.
I downloaded a copy from the PLT cvs, and it seems to work exactly as
advertised. I'm still getting familiar with it. For example, I tried
evaluating (down ((call/cc call/cc) (call/cc call/cc))), and was taking a
long time. Then I realized that "down" is a function, not a macro, so you
have to quote the expression. Silly me, it was trying to evaluate the
expression before passing it to down, which kinda defeats the purpose. So I
quoted the expression, and it seems to be working much better now, although
it hasn't quite finished yet.
BTW, in cvs, "plt" in the man filename is misspelled as "pilt" for some
reason.
Anton
Anton van Straaten
> I downloaded a copy from the PLT cvs, and it seems to work exactly as
> advertised. I'm still getting familiar with it. For example, I tried
> evaluating (down ((call/cc call/cc) (call/cc call/cc))), and was taking a
> long time. Then I realized that "down" is a function, not a macro, so you
> have to quote the expression. Silly me, it was trying to evaluate the
> expression before passing it to down, which kinda defeats the purpose. So
I
> quoted the expression, and it seems to be working much better now,
although
> it hasn't quite finished yet.
This test finally returned an answer of #f. Took about 45 minutes
altogether. Impressive!
But I have a problem: "down" is still very new, and it could have bugs. How
can I tell for sure that this answer is correct?
Don Groves
Easy: (correct? #'down '((call/cc call/cc) (call/cc call/cc)))))
Code for correct? will be available 1 Apr 2005
--
dg
Using M2, Opera's revolutionary e-mail client: http://www.opera.com/m2/
Vincenzo aka Nick Name
>
> Easy: (correct? #'down '((call/cc call/cc) (call/cc call/cc)))))
>
> Code for correct? will be available 1 Apr 2005
And, of course, it will be applied to itself to check correctness of
implementation before the release.
V.
Don Groves
Of course.
Abdulaziz Ghuloum
> This test finally returned an answer of #f. Took about 45 minutes
> altogether. Impressive!
>
> But I have a problem: "down" is still very new, and it could have bugs. How
> can I tell for sure that this answer is correct?
One thing for sure though is that down will always terminate for every input:
Proof:
> (down '(down (read)))
#t
So, if it takes too long, just wait; it will get there.
Aziz,,,
Ivan Boldyrev
Cool!!! I was dreaming about such a tool for a very long time!!!
Could you, please, test this sample:
,----
| (define (test n)
| (if (down '(test 1))
| (test)
| #t))
|
| (test 1)
`----
--
Ivan Boldyrev
Outlook has performed an illegal operation and will be shut down.
If the problem persists, contact the program vendor.
Tom Breton
> After many years of effort, I've finally finished
> work on a utility that will soon be available from PLT.
>
> The utility is called "down", for reasons that will
> become clear. It takes as input an arbitrary S-expression,
> and returns a boolean, as follows. If the S-expression
> input would return a Scheme value in finite time, when supplied
> to PLT Scheme's "eval", "down" returns #t; otherwise it
> returns #f. The time needed for "down" to perform this calculation
> is not specified. The name "down" is used, because a downward
> arrow is used to denote termination, which is what the utility
> detects.
>
> The algorithm was kind of tricky to work out, but dang,
> it works!
I'm sure history will remember this day, Thu, 1 Apr 2004.
> Look for this utility in the next PLT distribution.
> More information about the program will be available
> in the manual page, plt/man/man1/plt-down.man.
Why did you bury it there?
--
Tom Breton, calm-eyed visionary
Hu, Wei
Richard C. Cobbe
> So is this an April Joke or not?
Yes. It's a reference to the Piltdown Man hoax; do a Google search for
details.
Richard
tal...@noshpam.lbl.government
> Yes. It's a reference to the Piltdown Man hoax; do a Google search for
> details.
Well, for working around the Halting Problem, I'd like to nominate the
Piltdown Man for the Turing Award. :-)
~Tomer
MJ Ray
> and returns a boolean, as follows. If the S-expression
> input would return a Scheme value in finite time, when supplied
At least in England, All Fools' Day jokes must be played before noon.
Anton van Straaten
MJ Ray
> > At least in England, All Fools' Day jokes must be played before noon.
> Afaict, it *was* before noon in Paul's timezone...
It certainly isn't now. Usenet is a dumb place to post these.
Johan
various news servers? Probably excluding alt.*, whcih I gather is
normally serviced at a lower priority.
Morris Carré
>>
>>>At least in England, All Fools' Day jokes must be played before noon.
>>
>>Afaict, it *was* before noon in Paul's timezone...
>
>
> It certainly isn't now. Usenet is a dumb place to post these.
>
What's dumb is to miss that Usenet ain't part of England.
MJ Ray
It would be, so I assume you do. I sure don't. FUs set.