9 ms·

I'm astonished to discover Clojure does do single-pass compilation. It used to be done primarily because some intermediate representations of programs could not

by m0th87 16y ago

I'm astonished to discover Clojure does do single-pass compilation. It used to be done primarily because some intermediate representations of programs could not fit entirely in memory, but virtually every compiler now is multi-pass because so many optimization opportunities are lost otherwise. I have minimum knowledge of Clojure, so is there some motivation for single-pass other than perhaps simplicity? Edit: A brief outline of the tradeoffs: http://en.wikipedia.org/wiki/Compiler#One-pass_versus_multi-pass_compilers http://en.wikipedia.org/wiki/Compiler#One-pass_versus_multi-...

swannodette 16y ago
Consider how much powerful macros can be if you don't have to deal with out of order definitions.
- m0th87 16y ago
  Macros are wonderful, but intuitively it seems very limited in scope wrt compile-time optimizations. For example, how would you do dataflow analysis at compile-time (which is necessary for a plethora of optimizations) with just macros?
  - swannodette 16y ago
    JVM does that for you. However you're free to do all sorts of kinds of optimizations that the JVM simply can't do. Think about a in-memory logic engine that's running during compilation - you can introduce relations which influence how code further down the line is compiled via macros.
- oconnore 16y ago
  Please explain?
- deleted 16y ago
  [deleted]
richhickey 16y ago
The issue is not single-pass vs multi-pass. It is instead, what constitutes a compilation unit, i.e., a pass over what? Clojure, like many Lisps before it, does not have a strong notion of a compilation unit. Lisps were designed to receive a set of interactions/forms via a REPL, not to compile files/modules/programs etc. This means you can build up a Lisp program interactively in very small pieces, switching between namespaces as you go, etc. It is a very valuable part of the Lisp programming experience. It implies that you can stream fragments of Lisp programs as small as a single form over sockets, and have them be compiled and evaluated as they arrive. It implies that you can define a macro and immediately have the compiler incorporate it in the compilation of the next form, or evaluate some small section of an otherwise broken file. Etc, etc. That "joke from the 1980's" still has legs, and can enable things large-unit/multi-unit compilers cannot. FWIW, Clojure's compiler is two-pass, but the units are tiny (top-level forms). What Yegge is really asking for is multi-unit (and larger unit) compilation for circular reference, whereby one unit can refer to another, and vice versa, and the compilation of both units will leave hanging some references that can only be resolved after consideration of the other, and tying things together in a subsequent 'pass'. What would constitute such a unit in Clojure? Should Clojure start requiring files and defining semantics for them? (it does not now) Forward reference need not require multi-pass nor compilation units. Common Lisp allows references to undeclared and undefined things, and generates runtime errors should they not be defined by then. Clojure could have taken the same approach. The tradeoffs with that are as follows: 1) less help at compilation time 2) interning clashes While #1 is arguably the fundamental dynamic language tradeoff, there is no doubt that this checking is convenient and useful. Clojure supports 'declare' so you are not forced to define your functions in any particular order. #2 is the devil in the details. Clojure, like Common Lisp, is designed to be compiled, and does not in general look things up by name at runtime. (You can of course design fast languages that look things up, as do good Smalltalk implementations, but remember these languages focus on dealing with dictionary-carrying objects, Lisps do not). So, both Clojure and CL reify names into things whose addresses can be bound in the compiled code (symbols for CL, vars for Clojure). These reified things are 'interned', such that any reference to the same name refers to the same object, and thus compilation can proceed referring to things whose values are not yet defined. But, what should happen here, when the compiler has never before seen bar? (defn foo [] (bar)) or in CL: (defun foo () (bar)) CL happily compiles it, and if bar is never defined, a runtime error will occur. Ok, but, what reified thing (symbol) did it use for bar during compilation? The symbol it interned when the form was read. So, what happens when you get the runtime error and realize that bar is defined in another package you forgot to import. You try to import other-package and, BAM!, another error - conflict, other-package:bar conflicts with read-in-package:bar. Then you go learn about uninterning. In Clojure, the form doesn't compile, you get a message, and no var is interned for bar. You require other-namespace and continue. I vastly prefer this experience, and so made these tradeoffs. Many other benefits came about from using a non-interning reader, and interning only on definition/declaration. I'm not inclined to give them up, nor the benefits mentioned earlier, in order to support circular reference. Rich

by m0th87 16y ago

swannodette 16y ago

Consider how much powerful macros can be if you don't have to deal with out of order definitions.

m0th87 16y ago
Macros are wonderful, but intuitively it seems very limited in scope wrt compile-time optimizations. For example, how would you do dataflow analysis at compile-time (which is necessary for a plethora of optimizations) with just macros?
- swannodette 16y ago
  JVM does that for you. However you're free to do all sorts of kinds of optimizations that the JVM simply can't do. Think about a in-memory logic engine that's running during compilation - you can introduce relations which influence how code further down the line is compiled via macros.
oconnore 16y ago
Please explain?
deleted 16y ago
[deleted]

richhickey 16y ago

The issue is not single-pass vs multi-pass. It is instead, what constitutes a compilation unit, i.e., a pass over what? Clojure, like many Lisps before it, does not have a strong notion of a compilation unit. Lisps were designed to receive a set of interactions/forms via a REPL, not to compile files/modules/programs etc. This means you can build up a Lisp program interactively in very small pieces, switching between namespaces as you go, etc. It is a very valuable part of the Lisp programming experience. It implies that you can stream fragments of Lisp programs as small as a single form over sockets, and have them be compiled and evaluated as they arrive. It implies that you can define a macro and immediately have the compiler incorporate it in the compilation of the next form, or evaluate some small section of an otherwise broken file. Etc, etc. That "joke from the 1980's" still has legs, and can enable things large-unit/multi-unit compilers cannot. FWIW, Clojure's compiler is two-pass, but the units are tiny (top-level forms). What Yegge is really asking for is multi-unit (and larger unit) compilation for circular reference, whereby one unit can refer to another, and vice versa, and the compilation of both units will leave hanging some references that can only be resolved after consideration of the other, and tying things together in a subsequent 'pass'. What would constitute such a unit in Clojure? Should Clojure start requiring files and defining semantics for them? (it does not now) Forward reference need not require multi-pass nor compilation units. Common Lisp allows references to undeclared and undefined things, and generates runtime errors should they not be defined by then. Clojure could have taken the same approach. The tradeoffs with that are as follows: 1) less help at compilation time 2) interning clashes While #1 is arguably the fundamental dynamic language tradeoff, there is no doubt that this checking is convenient and useful. Clojure supports 'declare' so you are not forced to define your functions in any particular order. #2 is the devil in the details. Clojure, like Common Lisp, is designed to be compiled, and does not in general look things up by name at runtime. (You can of course design fast languages that look things up, as do good Smalltalk implementations, but remember these languages focus on dealing with dictionary-carrying objects, Lisps do not). So, both Clojure and CL reify names into things whose addresses can be bound in the compiled code (symbols for CL, vars for Clojure). These reified things are 'interned', such that any reference to the same name refers to the same object, and thus compilation can proceed referring to things whose values are not yet defined. But, what should happen here, when the compiler has never before seen bar? (defn foo [] (bar)) or in CL: (defun foo () (bar)) CL happily compiles it, and if bar is never defined, a runtime error will occur. Ok, but, what reified thing (symbol) did it use for bar during compilation? The symbol it interned when the form was read. So, what happens when you get the runtime error and realize that bar is defined in another package you forgot to import. You try to import other-package and, BAM!, another error - conflict, other-package:bar conflicts with read-in-package:bar. Then you go learn about uninterning. In Clojure, the form doesn't compile, you get a message, and no var is interned for bar. You require other-namespace and continue. I vastly prefer this experience, and so made these tradeoffs. Many other benefits came about from using a non-interning reader, and interning only on definition/declaration. I'm not inclined to give them up, nor the benefits mentioned earlier, in order to support circular reference. Rich