News for hackers. Stuff that matters.
Re:Dependently Typed Programming by al2o3cr on Tuesday July 01, 2014 @06:41PM (#7973911)
"and to terminate"

That must be a neat trick - or you've constructed a non-Turing -complete language...

Re:Dependently Typed Programming by skew on Tuesday July 01, 2014 @06:53PM (#7973967)
Non-Turing-complete is not a bad way to go. You pretty much have to already be a researcher in dependent type systems (or maybe set theory) to invent functions that always terminate but can't be written in non-Turing-complete languages like Coq (an evaluator for programs in an at-least-as-powerful dependently typed language is the only remotely natural example I know of). Also, writing a program that proves some programs terminate is way easier than proving a program that correctly proves any terminating program terminates, if you are confusing the two. If it's not too common, "I didn't manage to prove this terminates" sounds like a reasonable compiler error.
Re:Dependently Typed Programming by tel on Tuesday July 01, 2014 @09:46PM (#7974646)
It can be kind of hard to satisfy termination checkers, though. They're not smart. You basically have to show structural induction on something which sometimes forces you to invent lots of new proof terms.
Re:Dependently Typed Programming by Ono-Sendai on Wednesday July 02, 2014 @08:02AM (#7976391)
Indeed. I suspect that's where a lot of my time will be invested, making the checker better, improving error messages, etc..
Re:Dependently Typed Programming by dllthomas on Wednesday July 02, 2014 @09:37AM (#7976855)
"(an evaluator for programs in an at-least-as-powerful dependently typed language is the only remotely natural example I know of)"

Note, also, that there's an obvious restriction for that case to get something you can write: "evaluate for the next X steps".

Re:Dependently Typed Programming by Ono-Sendai on Tuesday July 01, 2014 @07:21PM (#7974105)
Yeah, it's non turing-complete.
Re:Dependently Typed Programming by qu4z-2 on Tuesday July 01, 2014 @07:16PM (#7974081)
Or it just refuses to compile/execute something it can't prove terminates.
Re:Dependently Typed Programming by TheCoelacanth on Tuesday July 01, 2014 @08:05PM (#7974295)
That would make it non-Turing complete. Of course there probably aren't many interesting programs that are ruled out by that restriction.
Re:Dependently Typed Programming by marcosdumay on Tuesday July 01, 2014 @10:08PM (#7974729)
There are many interesting programs that don't ave any guarantee that they terminate. A a few that don't really terminate, ever.

In fact, if you click on the launcher menu on your computer, I'll bet most programs there just keep going, until some random event (AKA clicking on an "x") throws them out of the loop.

Re:Dependently Typed Programming by eru on Wednesday July 02, 2014 @02:36AM (#7975549)
That's why you'd ask your programs to be `productive'. Also look up co-recursion and co-data, if you want to find out more about this.

(It's basically the logical way to extend `termination' from batch programs to things like continuously running programs like operating systems.)

Re:Dependently Typed Programming by TheCoelacanth on Tuesday July 01, 2014 @10:24PM (#7974772)
It wouldn't require that all programs terminate, just that all functions terminate.
Re:Dependently Typed Programming by marcosdumay on Tuesday July 01, 2014 @10:48PM (#7974848)
Your programs aren't composed of one top-level function?
Re:Dependently Typed Programming by TheCoelacanth on Tuesday July 01, 2014 @10:51PM (#7974857)
More likely they would be composed on one top-level IO value, like in Haskell, or something similar.
Re:Dependently Typed Programming by qu4z-2 on Wednesday July 02, 2014 @08:50PM (#7980817)
That is a very good point.
Re:Dependently Typed Programming by eru on Tuesday July 01, 2014 @06:59PM (#7973999)
Finding non-Turing complete, but still interesting languages, is a noble pursuit.
Re:Dependently Typed Programming by tel on Tuesday July 01, 2014 @11:27PM (#7975002)
Why? PFPL has like 10 chapters on them.

It's never really been stated why Completeness is a good thing.

Re:Dependently Typed Programming by eru on Wednesday July 02, 2014 @12:10AM (#7975142)
Yes. It's a useful endeavour. Things like Datalog, regular expressions or applicative parser combinators come out of it.