4 ms·

I've built interpreters for both a subset of Java and a full Lisp. Here's my take. > Is there something inherently easier to implementing a functional language

I've built interpreters for both a subset of Java and a full Lisp. Here's my take. > Is there something inherently easier to implementing a functional language instead of something more imperative? Other answers have focused on the parsing of the language (that is, the production of an AST) which is much easier to cover instructionally for a Lisp because it's basically the AST already. To my mind the semantics' of imperative languages is the real issue. In particular when defining and/or implementing the semantics for an imperative language, eventually store (memory) management comes up and everything gets much more complicated instantly. [edit] And to go along with the store there are often more forms for which you need to define the semantics (statements, expressions, classes, etc). In contrast functional languages can frequently be implemented using term rewriting which can deal directly with the AST itself. More broadly, this is why I wish students were required to implement an interpreter of an imperative language. The act of debugging programs becomes more difficult for the same reason the semantics is more difficult to define and implement: it's more complex and there are more nuts and bolts to consider.

emp 10y ago
I agree, but would add I wish student had to build compilers/interpreters for 3 languages: Forth, Lisp and something like C. As a student we went right into C: BNFs, lex, yacc, emitting machine code, optimizations, etc. Very interesting but the beauty of simplicity is lost in it all. Forth at first is baffling - there is no syntax! It's amazing how little you need to get going. Lisp, to just get right to the parse tree. And you already have intuition on the interpreter part. And finally C or Java for all the upfront complexity required.
ced 10y ago
In particular when defining and/or implementing the semantics for an imperative language, eventually store (memory) management comes up and everything gets much more complicated instantly. Why? Isn't C-like "call malloc" simpler than the GC which is required for most (all?) functional languages?
- kd0amg 10y ago
  It's not really being functional that calls for GC -- if you have data structures (whether they're closures, records, or whatever) escaping up from the scope in which they were created, you have a tricky lifetime question to deal with. In both the imperative and functional cases, you could require explicit allocation and deallocation (like malloc/free), and you could make it automatic (garbage collection). Functional programming tends to use GC because passing/returning closures is a common thing to do. These days, I would say imperative programmers also tend to use GC.

emp 10y ago

I agree, but would add I wish student had to build compilers/interpreters for 3 languages: Forth, Lisp and something like C. As a student we went right into C: BNFs, lex, yacc, emitting machine code, optimizations, etc. Very interesting but the beauty of simplicity is lost in it all. Forth at first is baffling - there is no syntax! It's amazing how little you need to get going. Lisp, to just get right to the parse tree. And you already have intuition on the interpreter part. And finally C or Java for all the upfront complexity required.

ced 10y ago

In particular when defining and/or implementing the semantics for an imperative language, eventually store (memory) management comes up and everything gets much more complicated instantly. Why? Isn't C-like "call malloc" simpler than the GC which is required for most (all?) functional languages?

kd0amg 10y ago
It's not really being functional that calls for GC -- if you have data structures (whether they're closures, records, or whatever) escaping up from the scope in which they were created, you have a tricky lifetime question to deal with. In both the imperative and functional cases, you could require explicit allocation and deallocation (like malloc/free), and you could make it automatic (garbage collection). Functional programming tends to use GC because passing/returning closures is a common thing to do. These days, I would say imperative programmers also tend to use GC.