From: Rick DeNatale Date: 2010-10-06T00:13:52+09:00 Subject: Re: how can we make a ruby compiler On Tue, Oct 5, 2010 at 8:31 AM, Samuel Williams wrote: > Dear Ryan, > > Thanks for your comments. In this discussion there are many opinions, so please keep in mind this is simply my perspective based on my experience. > > On 5/10/2010, at 11:01 PM, Ryan Davis wrote: > >> On Oct 5, 2010, at 02:49 , Samuel Williams wrote: >> >>> If you have a truly dynamic language (like Ruby), it is almost impossible to compile it adequately. This is because compilation is all about making assumptions. A dynamic language makes it very hard to make assumptions (there is quite a bit of research in this area, it is worth reading about it). >> >> Well this just isn't true (or is overly vague and my tired brain is reading more into it than it should). Look at anything written by David Ungar, or the research done on self, smalltalk, the latest javascript engines, etc... > > > I'm aware of most of this work, however I don't consider many of these languages to be completely dynamic. By dynamic, I mean that it is not possible to make an assumption about the result of an expression unless it is executed. If you can make an assumption about an expression, I don't consider it to be dynamic. What assumptions can you make about the result of an expression in any of these languages without running it? The result of a method send in Smalltalk, Ruby, or Self depends on the runtime state of the receiver of the message, and in the case of Ruby and Self, where compile time is the same as run-time methods can change as the program runs. In Ruby this evolution happens as the program requires new code, mixes in new modules, defines singleton methods, redefines methods, uses meta-programming techniques, such as the alias_method_chain found in Rails ... In Self static analysis of a method can't even determine if the reference to an 'instance variable' is really just a value reference or a method call. > For example, in most of those languages, the name of a function is specified explicitly and can't change due to the environment or scope of execution. We also know that all arguments to a function will be evaluated in the current scope. We can do some analysis and determine that an expression won't change in a loop, and then optimise for this case. No I don't think we can. Not for Ruby, nor Smalltalk, nor Self, nor as Shyouhei-san has pointed out, for JavaScript. Smalltalk is a bit more static than Ruby, Self, or JavaScript, in that, although run-time and development take place in the same environment, code changes happen mostly when a programmer changes a method/class definition in the IDE, which causes an incremental compilation of the affected methods. Smalltalk classes are 'statically' defined in this sense. >Many of these languages provide some semantic models which allow the interpreter to make assumptions. > > A good indication of a non-dynamic programming language is the presence of semantically meaningful keywords, especially those that have fixed behaviour. Examples include "def", "if", "while", "switch" and "try". These expressions can all be analysed with the knowledge of a given semantic model. A truly dynamic language has no such luxury... > Smalltalk at the language level has no such keywords, control flow is defined in terms of method sends. For example if is implemented by ifTrue:, ifFalse:, and ifTrue:ifFalse: messages, and boolean classes define these methods to evaluate one of (or none) of the block arguments. One could model this in Ruby with something like: class Object # define the if methods for truthy values def if_true(eval_if_true) eval_if_true.call end def if_true_else(eval_if_true, eval_if_false) eval_if_true.call end def if_false(eval_if_false) nil end end module FalsyIfMethods # define the if methods for falsy values def if_true(eval_if_true) nil end def if_true_else(eval_if_true, eval_if_false) eval_if_false.call end def if_false(eval_if_false) eval_if_false.call end end class NilClass include FalsyIfMethods end class FalseClass include FalsyIfMethods end is_truthy = lambda {"truthy"} is_falsy = lambda {"falsy"} 1.if_true(is_truthy) # => "truthy" 1.if_true_else(is_truthy, is_falsy) # => "truthy" 1.if_false(is_falsy) # => nil nil.if_true(is_truthy) # => nil nil.if_true_else(is_truthy, is_falsy) # => "falsy" nil.if_false(is_falsy) # => "falsy" true.if_true(is_truthy) # => "truthy" true.if_true_else(is_truthy, is_falsy) # => "truthy" true.if_false(is_falsy) # => nil (1 == 2).if_true_else(is_truthy, is_falsy) # => "falsy" Now most Smalltalk implementations do cheat on things like this and treat methods like ifTrue: and its brethren as special cases and compile them to test and branch bytecodes, with or without an escape if the receiver turns out not to be a boolean. But Self came about primarily because Dave Ungar, whose PhD dissertation was on Smalltalk performance, wanted to explore doing away with such cheats, as well as statically determination of whether something was an iv or a method, as well as relying on the 'static' class definitions in Smalltalk and see if dynamic runtime techniques could achieve equivalent if not better performance. And that work led to things like the JIT implementations in the Java hotspot VM, and Self appears to have been an strong influence on JavaScript, which uses the same kind of prototype technique for implementation sharing, rather than a class hierarchy. > In the case of a dynamic language we are reduced to statistical analysis at run time. Compilation becomes a method of speeding up the interpreter execution rather than optimising based on assumptions in the code itself. Few, if any, programming languages are completely dynamic. Scheme would be one language that I would consider very dynamic, as an example. Which you later correct to say 'Sorry, I meant to say "Scheme would be one language that I would consider very close to being completely dynamic".' Which I interpret to mean that you put Scheme as being even more dynamic than Smalltalk, Ruby, Self or JavaScript > An interpreter is simply a high level processor (i.e. CPU). However, there are intrinsic semantic structures which cannot be lowered. "Sufficiently smart compilers", and all that. Programming languages range from completely dynamic to completely static, depending on the semantic and execution model. I'm confused by your argument at this point, because there are quite a few compilers for Scheme http://en.wikipedia.org/wiki/Category:Scheme_compilers some of these compile to an intermediate 'language' like C or JVM bytecodes, others directly to some machine language. And, Guy Steele, one the inventors of Scheme wrote his PhD dissertation on a Scheme compiler "Rabbit" So it's not impossible to write a compiler for a dynamic language, but it takes more thought and techniques than most introductory compiler texts/courses teach. And Scheme was a seminal influence on those who have tackled the task. Particularly in the form of the "Lambda Papers" a series of M.I.T. A.I. lab memos by Guy Steele and Gerald Sussman as they explored usage and implementation around various issues such as the lambda calculus, continuations and a few other things leading up to and including Steele's dissertation on Rabbit. http://en.wikipedia.org/wiki/History_of_the_Scheme_programming_language#The_Lambda_Papers http://library.readscheme.org/page1.html And Gerald Sussman went on to write, with Julie Sussman and Harold Abelson, "The Structure and Interpretation of Computer Programs" which should be an eye-opener to anyone who has thought of C as the prototypical programming language. -- Rick DeNatale Blog: http://talklikeaduck.denhaven2.com/ Github: http://github.com/rubyredrick Twitter: @RickDeNatale WWR: http://www.workingwithrails.com/person/9021-rick-denatale LinkedIn: http://www.linkedin.com/in/rickdenatale