10 ms·

Honest question: why do tutorials in this topic seem to always use functional languages/syntax as examples? Our compilers class at MST had us re-implement a lis

Honest question: why do tutorials in this topic seem to always use functional languages/syntax as examples? Our compilers class at MST had us re-implement a lisp compiler, but didn't touch on why we used lisp specifically (other than the professor liking it; we were a largely C++ school). Do they think functional languages are simpler / less complex / easier to understand? Is there something inherently easier to implementing a functional language instead of something more imperative?

tel 10y ago
Modeling a pipeline of transformations of a well-understood data type it sort of whatever comes right after "hello world" in functional programming. A compiler is a very scaled up version of this, but it certainly fits naturally with the standard ideas of FP.
marcosdumay 10y ago
The simplest languages around are all functional. And most of them are Lisp idioms. Besides, when writing a compiler, it's always great if you can ignore the possibility of some value changing. It makes implementation much simpler even more if you go into optimizations. And while you can't completely ignore value mutation on Lisp, it is always explicit, what makes an implementer's life easier.
lmm 10y ago
Not having to deal with a statement/expression distinction makes it a lot easier. Functional languages often have a simpler syntax with fewer special cases. (Though there are other languages like this e.g. Smalltalk)
- vidarh 10y ago
  I agree in general. Though Wirth-ian languages, like Pascal, Modula-II and Oberon are good examples of languages that are very simple to parse despite not being functional. Though they are slightly more complx than some functional languages, you can prototype a hand-written parser for them in a day if you've got a bit of experience.. E.g. the Oberon-07 grammar takes up 1.5 pages of BNF [1]of which the first third of a page or so represent the lexer symbols (you don't need a separate lexer module for most of these languages). [1] Page 166 and 17 of the language report (which incidentally only spends 17 pages to describe the entire language...) https://www.inf.ethz.ch/personal/wirth/Oberon/Oberon07.Report.pdf https://www.inf.ethz.ch/personal/wirth/Oberon/Oberon07.Repor...
inimino 10y ago
It isn't really meaningful to call a language like this functional or imperative. It's far too simple. If you're asking about the s-expressions specifically, they are very easy to parse for the same reason they are easy to read: you don't need any precedence rules. Writing interpreters in Lisp languages for Lisp languages also has a long history.
keithb- 10y ago
I think you're asking the right questions. I would assume that your class targeted Lisp because SICP uses it. While that is a great resource, it is light on details when it comes to the end game: runtime. If you are developing a language today and you aren't considering runtime, then you are just writing macros. Lexing, and parsing are not trivial tasks, but powerful tooling already exists for these. Compiling means knowing how to translate your language into something that executes, and I would say "must execute well". I'm in favor of hobbies (fun) and exploration (growth), but if you are "perfecting" steps 1&2 and haven't yet considered step 3, then maybe it is time to support another language community rather than develop something on your own.
- inimino 10y ago
  I'm not sure what you mean by "runtime" here and I'm having a little trouble seeing what you're getting at.
  - greenshackle2 10y ago
    Runtime means program execution, basically. With steps 1 and 2, you're just translating between different program representations. You could hand-write your programs as syntax trees directly if you really wanted to, and you wouldn't even need those steps. It would be a bit more work, but not insanely so; Lisp syntax looks a lot like a syntax tree already, and some people are perfectly happy writing Lisp. Step 3 is where you go from 'code' in one form or another (usually AST), to an actual process that's executing on the machine, either through interpretation or compilation. It's where most of the magic happens. You have to turn your AST into a series of machine instructions that will i) do what the code says ii) in an efficient manner. Sometimes achieving i) at all is hard; it's not immediately clear how to implement certain high level operations using machine instructions. Sometimes there are obvious ways to do it, but there are also much less obvious ways that are much faster (more efficient). Finding those ways is 'optimization'. Unlike steps 1 and 2, which can be done by hand relatively easily, trying to execute your program by hand, for any non-trivial program, would be an absolute nightmare. (The exception is very low level languages, like assembly, where your language maps almost 1-to-1 with machine instructions. In that case step 3 is trivial. But if you're designing a language today it's probably not an assembly language.)
jedimastert 10y ago
I think it's because the text representation is super close to the AST
kazinator 10y ago
If the language supports assignment, which allows variables and parts of data structures to be treated as mutable memory locations, then it isn't functional. Using Lisp syntax lets the class have more time for semantics.
throwaway2016a 10y ago
Because languages like this map so closely to the AST (as someone else pointed out) you don't need to deal with complexities such as look aheads, regular expressions, and formal syntax definitions (BNFs). I suppose this makes it a good getting started point. Most more complex languages you'd use something like lex and yacc which would add quite a bit more overhead to the tutorial. The danger of these tutorials is the whole "grow your own parser" method doesn't scale to more complex languages (you need better tooling for that and/or a lot firmer grasp of the concepts) and I would be concerned that people would try to extend this tutorial and go down a rabbit hole. Edit: I know this from experience because when I was in high school I wrote a compiler this way (let's call it the naive way). And then in college I learned how to do it with BNF and code generators and the difference in maintainability and code complexity between the two is ridiculous. I would never do it the old way again, even for a toy language.
- greenshackle2 10y ago
  I'm writing an assembler for a virtual 16 bit CPU I built, and I hesitated on using BNF. It seemed overkill so I ended up hand-rolling a parser; for an assembler it's straightforward enough, but I can easily see how it could get ridiculous to implement a compiler this way.
  - kd0amg 10y ago
    I hesitated on using BNF. It seemed overkill Presumably because there's no real nesting of terms in assembly code? Personally, I find BNF so simple that I'd probably still use it for describing the grammar, but lots of parser generator technology is heavier machinery than required (though a recursive descent parser built from a regular grammar is essentially a DFA if your language/compiler offers tail call elimination).
    - greenshackle2 10y ago
      Right, with the syntax I chose there ends up being, IIRC, 6 different forms (<op>, <op> <arg1>, etc.), which can't be nested. Some of those forms share patterns which could be described as a nested grammar, but I just abstracted them in the parser code as functions (i.e. functions to parse patterns that show up in multiple forms). I did use a lexer. I wrote an assembler before without using a lexer; using the lexer isn't that much simpler IMO, but it makes it more robust and makes it much easier to systematically catch syntax errors and produce meaningful errors.
ufo 10y ago
It depends on hoe you are writing your compiler. If you are coding in a high level language, then writing an AST interpreter for a functional language is super simple. You just need to mix first-class functions and an unsurprising expression evaluator and you end up with something really expressive. If you are targeting a lower level language like assembly language then I think an imperative language is easier to do though. You need to worry a lot about memory layouts, register allocation and calling conventions and in this paradigm a simple imperative language will be an easier fit.
- DonaldFisk 10y ago
  That's only because the hardware architecture's designed that way. If your target is a stack machine (with no general purpose registers), a functional language would be just as easy if not easier to generate code for.
tscs37 10y ago
I can probably answer the LISP question; the Core LISP Languages is incredibly simple. It has only 8 or so keywords you really need and 5 syntax forms (probably wrong, I don'T have the exact numbers in my head) It comes with very few special forms and makes no difference between a variable, function or macro. Everything is same-y.
- zeveb 10y ago
  > It comes with very few special forms and makes no difference between a variable, function or macro. Everything is same-y. That's true of Scheme, not Lisp (Lisp has rather more special forms, and definitely makes distinctions between variables, functions and macros), but it is indeed why Scheme is so popular in compiler classes.
  - tscs37 10y ago
    You're right, I always confuse the many forms of LISP to some certain degree...
  - DonaldFisk 10y ago
    Scheme is a Lisp. Lisp is nowadays a language family, built upon a common core: both programs and data are nested lists of symbols; the interpreter executes by recursively calling eval and apply functions.
  - duaneb 10y ago
    I think you mean lisp-1 (or something). Lisp as a whole is a, erm, genus of languages.
- kazinator 10y ago
  Yeah, if you ignore the reader, garbage collector, hash table implementation, vectors, object system, stack unwinding, representation of closures, etc, etc. all you're left with is a handful of special forms. Unicode support? Why, practically just a footnote; leave that to the summer students.
  - 10y ago
davidkellis 10y ago
Lisp, or any prefix or postfix language, is relatively easy to parse and execute (in the case of an interpreter) or translate (in the case of a compiler/translator) because its syntactic structure mirrors the abstract syntax tree (AST) that the semantic analysis phase (i.e. the last of the 3 phases identified in the post) will traverse as it either executes (interpreter) or translates (compiler). In other words, the parse tree is nearly identical to the AST. That isn't true of Algol-like languages, and so the syntactic analysis and semantic analysis phases of a compiler/translator of Algol-like languages is more complex. That's why Lisp, or really any prefix or postfix language, is a good first language to implement, as opposed to something like C.
gshubert17 10y ago
TECS (The Elements of Computing Systems) devotes 2 chapters out of 12 to writing a compiler for a Java-like language. Lexical analysis is more complex, with operators and identifiers and comments in addition to parentheses, numbers, and the letter 's'. TECS provides a skeleton of a recursive descent parser, with about a dozen different methods to write. The Java-like language has many different kinds of expressions and statements, and this is reflected in the complexity of the parser. At first the output is an XML tree. Code generation gets an entire chapter. Some of the chapters are straightforward, less than 6 hours of work. But the harder chapters have taken me around 15 hours each. YMMV, but this gives one some idea of the differences between functional languages and procedural languages.
- protomikron 10y ago
  TECS is a wonderful book! I think it was one of the most enjoyable books about CS I have ever read.
t1m 10y ago
Prefix notation (ie. + 1 1) instead of infix notation (ie. 1 + 1) is much easier parse, as there are no precedence rules and you don't require different conventions for expressions and function calls.
danblick 10y ago
If you were trying to implement a language with assignment statements like: x := y + z or f(y + z) or g(f(x, y)) you'd need to be able to evaluate expressions first. Maybe it's just simpler to illustrate a smaller language first?
johnbender 10y ago
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.

tel 10y ago

Modeling a pipeline of transformations of a well-understood data type it sort of whatever comes right after "hello world" in functional programming. A compiler is a very scaled up version of this, but it certainly fits naturally with the standard ideas of FP.

marcosdumay 10y ago

The simplest languages around are all functional. And most of them are Lisp idioms. Besides, when writing a compiler, it's always great if you can ignore the possibility of some value changing. It makes implementation much simpler even more if you go into optimizations. And while you can't completely ignore value mutation on Lisp, it is always explicit, what makes an implementer's life easier.

lmm 10y ago

Not having to deal with a statement/expression distinction makes it a lot easier. Functional languages often have a simpler syntax with fewer special cases. (Though there are other languages like this e.g. Smalltalk)

vidarh 10y ago
I agree in general. Though Wirth-ian languages, like Pascal, Modula-II and Oberon are good examples of languages that are very simple to parse despite not being functional. Though they are slightly more complx than some functional languages, you can prototype a hand-written parser for them in a day if you've got a bit of experience.. E.g. the Oberon-07 grammar takes up 1.5 pages of BNF [1]of which the first third of a page or so represent the lexer symbols (you don't need a separate lexer module for most of these languages). [1] Page 166 and 17 of the language report (which incidentally only spends 17 pages to describe the entire language...) https://www.inf.ethz.ch/personal/wirth/Oberon/Oberon07.Report.pdf https://www.inf.ethz.ch/personal/wirth/Oberon/Oberon07.Repor...

inimino 10y ago

It isn't really meaningful to call a language like this functional or imperative. It's far too simple. If you're asking about the s-expressions specifically, they are very easy to parse for the same reason they are easy to read: you don't need any precedence rules. Writing interpreters in Lisp languages for Lisp languages also has a long history.

keithb- 10y ago

I think you're asking the right questions. I would assume that your class targeted Lisp because SICP uses it. While that is a great resource, it is light on details when it comes to the end game: runtime. If you are developing a language today and you aren't considering runtime, then you are just writing macros. Lexing, and parsing are not trivial tasks, but powerful tooling already exists for these. Compiling means knowing how to translate your language into something that executes, and I would say "must execute well". I'm in favor of hobbies (fun) and exploration (growth), but if you are "perfecting" steps 1&2 and haven't yet considered step 3, then maybe it is time to support another language community rather than develop something on your own.

inimino 10y ago
I'm not sure what you mean by "runtime" here and I'm having a little trouble seeing what you're getting at.
- greenshackle2 10y ago
  Runtime means program execution, basically. With steps 1 and 2, you're just translating between different program representations. You could hand-write your programs as syntax trees directly if you really wanted to, and you wouldn't even need those steps. It would be a bit more work, but not insanely so; Lisp syntax looks a lot like a syntax tree already, and some people are perfectly happy writing Lisp. Step 3 is where you go from 'code' in one form or another (usually AST), to an actual process that's executing on the machine, either through interpretation or compilation. It's where most of the magic happens. You have to turn your AST into a series of machine instructions that will i) do what the code says ii) in an efficient manner. Sometimes achieving i) at all is hard; it's not immediately clear how to implement certain high level operations using machine instructions. Sometimes there are obvious ways to do it, but there are also much less obvious ways that are much faster (more efficient). Finding those ways is 'optimization'. Unlike steps 1 and 2, which can be done by hand relatively easily, trying to execute your program by hand, for any non-trivial program, would be an absolute nightmare. (The exception is very low level languages, like assembly, where your language maps almost 1-to-1 with machine instructions. In that case step 3 is trivial. But if you're designing a language today it's probably not an assembly language.)

jedimastert 10y ago

I think it's because the text representation is super close to the AST

kazinator 10y ago

If the language supports assignment, which allows variables and parts of data structures to be treated as mutable memory locations, then it isn't functional. Using Lisp syntax lets the class have more time for semantics.

throwaway2016a 10y ago

Because languages like this map so closely to the AST (as someone else pointed out) you don't need to deal with complexities such as look aheads, regular expressions, and formal syntax definitions (BNFs). I suppose this makes it a good getting started point. Most more complex languages you'd use something like lex and yacc which would add quite a bit more overhead to the tutorial. The danger of these tutorials is the whole "grow your own parser" method doesn't scale to more complex languages (you need better tooling for that and/or a lot firmer grasp of the concepts) and I would be concerned that people would try to extend this tutorial and go down a rabbit hole. Edit: I know this from experience because when I was in high school I wrote a compiler this way (let's call it the naive way). And then in college I learned how to do it with BNF and code generators and the difference in maintainability and code complexity between the two is ridiculous. I would never do it the old way again, even for a toy language.

greenshackle2 10y ago
I'm writing an assembler for a virtual 16 bit CPU I built, and I hesitated on using BNF. It seemed overkill so I ended up hand-rolling a parser; for an assembler it's straightforward enough, but I can easily see how it could get ridiculous to implement a compiler this way.
- kd0amg 10y ago
  I hesitated on using BNF. It seemed overkill Presumably because there's no real nesting of terms in assembly code? Personally, I find BNF so simple that I'd probably still use it for describing the grammar, but lots of parser generator technology is heavier machinery than required (though a recursive descent parser built from a regular grammar is essentially a DFA if your language/compiler offers tail call elimination).
  - greenshackle2 10y ago
    Right, with the syntax I chose there ends up being, IIRC, 6 different forms (<op>, <op> <arg1>, etc.), which can't be nested. Some of those forms share patterns which could be described as a nested grammar, but I just abstracted them in the parser code as functions (i.e. functions to parse patterns that show up in multiple forms). I did use a lexer. I wrote an assembler before without using a lexer; using the lexer isn't that much simpler IMO, but it makes it more robust and makes it much easier to systematically catch syntax errors and produce meaningful errors.

ufo 10y ago

It depends on hoe you are writing your compiler. If you are coding in a high level language, then writing an AST interpreter for a functional language is super simple. You just need to mix first-class functions and an unsurprising expression evaluator and you end up with something really expressive. If you are targeting a lower level language like assembly language then I think an imperative language is easier to do though. You need to worry a lot about memory layouts, register allocation and calling conventions and in this paradigm a simple imperative language will be an easier fit.

DonaldFisk 10y ago
That's only because the hardware architecture's designed that way. If your target is a stack machine (with no general purpose registers), a functional language would be just as easy if not easier to generate code for.

tscs37 10y ago

I can probably answer the LISP question; the Core LISP Languages is incredibly simple. It has only 8 or so keywords you really need and 5 syntax forms (probably wrong, I don'T have the exact numbers in my head) It comes with very few special forms and makes no difference between a variable, function or macro. Everything is same-y.

zeveb 10y ago
> It comes with very few special forms and makes no difference between a variable, function or macro. Everything is same-y. That's true of Scheme, not Lisp (Lisp has rather more special forms, and definitely makes distinctions between variables, functions and macros), but it is indeed why Scheme is so popular in compiler classes.
- tscs37 10y ago
  You're right, I always confuse the many forms of LISP to some certain degree...
- DonaldFisk 10y ago
  Scheme is a Lisp. Lisp is nowadays a language family, built upon a common core: both programs and data are nested lists of symbols; the interpreter executes by recursively calling eval and apply functions.
- duaneb 10y ago
  I think you mean lisp-1 (or something). Lisp as a whole is a, erm, genus of languages.
kazinator 10y ago
Yeah, if you ignore the reader, garbage collector, hash table implementation, vectors, object system, stack unwinding, representation of closures, etc, etc. all you're left with is a handful of special forms. Unicode support? Why, practically just a footnote; leave that to the summer students.
- 10y ago

davidkellis 10y ago

Lisp, or any prefix or postfix language, is relatively easy to parse and execute (in the case of an interpreter) or translate (in the case of a compiler/translator) because its syntactic structure mirrors the abstract syntax tree (AST) that the semantic analysis phase (i.e. the last of the 3 phases identified in the post) will traverse as it either executes (interpreter) or translates (compiler). In other words, the parse tree is nearly identical to the AST. That isn't true of Algol-like languages, and so the syntactic analysis and semantic analysis phases of a compiler/translator of Algol-like languages is more complex. That's why Lisp, or really any prefix or postfix language, is a good first language to implement, as opposed to something like C.

gshubert17 10y ago

TECS (The Elements of Computing Systems) devotes 2 chapters out of 12 to writing a compiler for a Java-like language. Lexical analysis is more complex, with operators and identifiers and comments in addition to parentheses, numbers, and the letter 's'. TECS provides a skeleton of a recursive descent parser, with about a dozen different methods to write. The Java-like language has many different kinds of expressions and statements, and this is reflected in the complexity of the parser. At first the output is an XML tree. Code generation gets an entire chapter. Some of the chapters are straightforward, less than 6 hours of work. But the harder chapters have taken me around 15 hours each. YMMV, but this gives one some idea of the differences between functional languages and procedural languages.

protomikron 10y ago
TECS is a wonderful book! I think it was one of the most enjoyable books about CS I have ever read.

t1m 10y ago

Prefix notation (ie. + 1 1) instead of infix notation (ie. 1 + 1) is much easier parse, as there are no precedence rules and you don't require different conventions for expressions and function calls.

danblick 10y ago

If you were trying to implement a language with assignment statements like: x := y + z or f(y + z) or g(f(x, y)) you'd need to be able to evaluate expressions first. Maybe it's just simpler to illustrate a smaller language first?

johnbender 10y ago

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.