0
$\begingroup$

(Initially this question was on cstheory, but I was told cs would be a better fit, so posting it here.)

All other things being equal, which of the following languages would be more challenging to design a compiler and/or interpreter for? (If the answer would vary depending on whether one is designing a compiler or interpreter, please address that difference.)

Language 1: Supports recursion but not higher-order functions in any sense, not even C-language qsort function-as-parameter style, let alone functions as a return value.

Language 2: Supports higher-order functions, but not recursion. Higher-order meaning that a function is allowed to both take functions as inputs as well as return functions.

-- Some answers from post on cstheory: recursion is trivial. It amounts to backwards jumps and a bit of care with the stack and stack frames. Support for full higher order functions, especially if you want to be efficient needs a bit of care, you need things like closures (or compile higher-orderness away).

When your code needs to return a function, and that function captures some local data, then you don't know in advance the lifetime of that local data. This forces you either into garbage collection, or into sophisticated reference counting / lifetime tracking, or full-blown ownership types like in Rust, or something like this. Objective C and Swift have trouble with closures, due to this problem with unknown lifetimes of memory allocated data.

Improve this question
$\endgroup$
5
  • $\begingroup$ Cross-posted: cstheory.stackexchange.com/q/52366/5038, cs.stackexchange.com/q/156706/755. Please do not post the same question on multiple sites. If you discover you've posted a question on the wrong site, you can delete it on the wrong site before posting on the new site -- please make sure that you've investigated and addressed all feedback before posting on the new site, and summarize any helpful suggestions you've received. $\endgroup$
    – D.W. ♦
    Jan 9 at 19:52
  • $\begingroup$ It seems like you got a pretty good answer in the comments on CSTheory.SE. Perhaps you can answer your own question now? Or, if you didn't find that satisfactory, revise the question to clarify your question and your doubt in light of the comments you've received? $\endgroup$
    – D.W. ♦
    Jan 9 at 19:54
  • 1
    $\begingroup$ Thank you for copy-pasting comments you already got, so they are not lost forever. It would be even better to engage with them. Did they answer your question? If so, perhaps you can write an answer to answer your own question? If it failed to answer your question, perhaps you can use the responses you've gotten to elaborate on your question and on why you remain unsure? $\endgroup$
    – D.W. ♦
    Jan 9 at 22:06
  • 1
    $\begingroup$ Garbage collection is a red herring; you didn't say what language the implementation should target. An interpreter written in a garbage-collected language will naturally inherit garbage-collection from the host language, and likewise for a compiler targeting a garbage-collected language. This is also moot because a language supporting "higher-order functions" does not necessarily support closures. $\endgroup$
    – kaya3
    Jan 10 at 0:22
  • $\begingroup$ @kaya3 The garbage-collection comment was not in my original post; I copied it from cstheory where I had originally posted before moving here. I didn't have a particular language in mind as the target and was wondering about making my own. I don't know of a language with HOFs (closures or o.w.) that doesn't have recursion. So to test out things like a Y combinator in a truly recursion-less language would require inventing one from scratch, AFAIK. And garbage-collection is a nice luxury, though I could sacrifice it for a simpler implementation of the aforementioned goals. $\endgroup$
    – Hank Igoe
    Jan 10 at 1:31

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.