5 ms·
This is complete and utter hogwash. > Clearly lisp procedures are not functions Some are. Others are not. The only thing a language needs to be legitimately
by lisper 10y ago
This is complete and utter hogwash.
> Clearly lisp procedures are not functions
Some are. Others are not.
The only thing a language needs to be legitimately called a functional language is for functions to be first-class data objects. It's helpful but not necessary for them to be lexically scoped. It is also helpful but not necessary to have a conditional expression. Common Lisp has all of these things. In fact, Common Lisp has all of the features commonly associated with modern functional languages except static type inference (and you can add that if you really want it).
Common Lisp is not a purely functional language, but that's true of pretty much every language except Haskell.
- ScottBurson 10y agoI like to call Lisp "semi-functional" -- it provides better support for the functional style than ordinary imperative languages, particularly if you use FSet [0] (shameless plug), but is still perfectly good for imperative programming when you want to do that. [0] https://github.com/slburson/fset https://github.com/slburson/fset
- ordu 10y agoSo... Is C a functional language? It allows us to pass functions to functions, return them back, storing them in variables and structures, and so on. Looks like C is a functional language.
- lisper 10y agoNot quite. To be a first-class data object you not only need to be able to pass and return them, but you also need to be able to create new ones at run time (i.e. you need to be able to make closures). C can't quite do that. (You can roll your own closures, but it's awkward.) But yes, C is closer to being functional than most people realize.
- kazinator 10y agoI think you can achieve Turing completeness without higher order functions, using only primitive recursion. That tells us that whatever can be calculated with the help of higher order functions can be somehow calculated without them, without resorting to destructive manipulation.
- lisper 10y agoYou don't need higher order functions, but you do need lexical closures. C only has one stack, so it's a PDA. Strictly less powerful than a TM. This is the reason lexical closures are so important. They are what let you "allocate" an infinite amount of memory so you can be Turing-complete without side-effects.
- cronjobber 10y ago> C only has one stack Sure > so it's a PDA. Wrong
- lisper 10y agoWhy wrong? Remember, we're talking about functional C here, so no destructive operations are allowed.
- cronjobber 10y agoSomething like Baker's Cheney on the MTA without actually collecting garbage. The "cheat" is that unbounded stack size implies unbounded pointer sizes, which means no finite alphabet, but "C without pointers" isn't C, and "finite stack/tape" isn't PDA/TM, so I think the "cheat" is fair :-)
- lisper 10y agoOK, you're right. I concede the point.
- kazinator 10y agoIt isn't clear that C is just A PDA. Without any destructive manipulation, C functions can use pointers to pass down and maintain a chain of contexts, so that each function potentially has random access to something at each stack level above it without having to pop anything.