There's a common belief floating around that total functions are an essential component of functional programming. I suppose there's growing demand for developing in Turing-incomplete languages.
-
-
Replying to @eiriktsarpalis
a nice paper of David Turner about this: http://www.jucs.org/jucs_10_7/total_functional_programming … Anyway I'm pretty ok with
@edwinbrady pacman completeness1 reply 0 retweets 3 likes -
Replying to @giacomociti @edwinbrady
Don't get me wrong, reasoning about totality is useful. Total functions are however not a defining characteristic of FP, as is often erroneously claimed on twitter.
1 reply 0 retweets 0 likes -
Replying to @eiriktsarpalis @edwinbrady
I don't have a strong opinion on this, but those who claim that programming is math (I like theory but I'm not in this camp) tend to forget that totality is at odd with Turing completeness
2 replies 0 retweets 0 likes -
Replying to @giacomociti @edwinbrady
I guess I’m a bit confused by the assertion that a language can be both total and TC. Is it maybe claiming that the core of the language is total and TC is obtainable via effect interpretation? But then the language core is not TC.
1 reply 0 retweets 0 likes -
Replying to @eiriktsarpalis @giacomociti
One could write a program in a total language that describes a turing machine, and have a run time system execute it. There'd be things one couldn't prove within the language, but that's a different issue.
1 reply 0 retweets 1 like -
Every language relies on an executing environment to interpret the effects described by the program - that we don't execute at compile time - and we still say they're Turing complete...
1 reply 0 retweets 1 like -
Or maybe another way to say this: the type system may not be (quite) turing complete, but the language is. This is probably true of essentially all mainstream languages.
1 reply 0 retweets 1 like -
Replying to @edwinbrady @giacomociti
I think that is akin to claiming that all recursive functions are total, because they have a finitary representation. One could alter the runtime semantics of so that the program terminates after n recursive calls. But is that a satisfactory definition of totality?
1 reply 0 retweets 0 likes
I don't. Really the best (most detailed/precise) explanation is the paper I linked.
-
-
Thanks. Twitter will use this to make your timeline better. UndoUndo
-
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.