Subrecursive dialect (was: Declarative vs. Inferential) 
Author Message
 Subrecursive dialect (was: Declarative vs. Inferential)

Quote:
> (This is not to disagree with your point that subrecursive languages
> are important.  I believe that most parts of most programs can and
> should be written in a subrecursive language, escaping into a general
> recursive programming language for the main event loop or equivalent.)

I have to agree with all the posts -- there are programs that should
"persist". I hesitate to say "loop forever", since the inputs on which these
programs terminate is very precisely defined (Microsoft Word terminates on the
input "Alt-F4"), unlike the general Halting Problem.

It seems it would be very useful to write 99% of one's code in a subrecursive
dialect and escape to turing-complete code only where necessary, just as
modern Haskell programs are mostly pure and non-monadic, using a small monadic
backbone only where necessary.

Can anybody give me a reference into research on such a language? This can't
be the first time the idea has come up...

............................................................................

Quote:
> A simple way to make such programs terminate is to give them a timeout.

Unfortunately the language that has timeouts is equal in power to the
nonrecursive language (I can just expand out all the recursive calls to a
depth equal to the timeout).

Quote:
> All programs, even operating systems, should not evaluate to bottom.
> But evaluating to an infinite data structure is fine.

I understand the logic of how to prove this about a program, but I don't see
what that gains us... the program that attempts to traverse an infinited data
structure will loop forever just as will one that attempts to evaluate
bottom...

  - aj

---
"Nobody has any 'Rights'. We are entitled only to Liberties"



Sun, 05 Aug 2001 03:00:00 GMT  
 Subrecursive dialect (was: Declarative vs. Inferential)

Quote:


>> A simple way to make such programs terminate is to give them a timeout.

>Unfortunately the language that has timeouts is equal in power to the
>nonrecursive language (I can just expand out all the recursive calls to a
>depth equal to the timeout).

I don't see what is "unfortunate" about the language with timeouts
being equal in power to a nonrecursive language.

Recursive languages may be more powerful in a theoretical sense
than nonrecursive languages, but as my example with very large
timeouts shows, they are not more powerful in practice.

You also need to be careful to distinguish power from expressiveness;
timeouts may not add any theoretical power to a language, but they
do make it much easier to express some useful things.

Quote:
>> All programs, even operating systems, should not evaluate to bottom.
>> But evaluating to an infinite data structure is fine.

>I understand the logic of how to prove this about a program, but I don't see
>what that gains us...
>the program that attempts to traverse an infinited data
>structure will loop forever just as will one that attempts to evaluate
>bottom...

The criterion I gave handles that case fine.

There's two cases to consider.  If, operationally speaking, the program
attempts to traverse an infinite data structure without doing I/O as it
goes, then declaratively speaking the program will evaluate to bottom,
or to some term containing bottom.  If on the other hand, the program
attempts to traverse an infinite data structure but continues to do I/O
as it goes, then declaratively speaking the program will evaluate to an
infinite I/O action.  The act of executing the program may result in an
infinite loop, but that should not be considered a problem -- it may
very well be the desired intent.  It's only for loops with no I/O
that we can be sure there is a problem.

--

WWW: <http://www.cs.mu.oz.au/~fjh>  |   but source code lives forever"



Sun, 05 Aug 2001 03:00:00 GMT  
 Subrecursive dialect (was: Declarative vs. Inferential)

Quote:

> It seems it would be very useful to write 99% of one's code in a
> subrecursive dialect and escape to turing-complete code only where
> necessary, just as modern Haskell programs are mostly pure and
> non-monadic, using a small monadic backbone only where necessary.

> Can anybody give me a reference into research on such a language?
> This can't be the first time the idea has come up...

Well, not directly, but it may be worth pointing out that languages
like Haskell and ML have this property in a sense.

All terms typable in the basic Hindley-Milner type system are strongly
normalisable (not only non-bottom, but their B?hm trees are finite).
The general recursion is got by adding a fixed-point operator.
Unfortunately (from the point of view of seeing whether a programme
terminates) both languages tacitly insert fixpoint combinators
whenever they see a recursive call.

It is possible to use the types of terms to decide whether it's safe
to reduce them at compile time, though - I did this in the Ponder
compiler.

--



Mon, 06 Aug 2001 03:00:00 GMT  
 
 [ 3 post ] 

 Relevant Pages 

1. Declarative vs. Inferential

2. Declarative vs Inferential

3. Declarative vs. Inferential

4. Imperative vs Declarative (was:DBC useful?)

5. Declarative vs. Procedural

6. procedural Vs declarative

7. subrecursive programming tools?

8. I am not deaf, but am I mute?

9. stdcall vs c vs cdecl vs pascal vs whosyerdaddy

10. 68K vs CFM68K vs Tk 8.0.3 vs AppearanceLib vs System 7

11. MASM vs TASM vs VC++ vs DJGPP vs A*^ vs PCC vs DEBUG,, "Hello World!"

12. MASM vs TASM vs VC++ vs DJGPP vs A*^ vs PCC vs DEBUG,, "Hello World!"

 

 
Powered by phpBB® Forum Software