Re: how can we make a ruby compiler

On Tue, Oct 5, 2010 at 8:31 AM, Samuel Williams
<[e-mail]> 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 impossib=
le to compile it adequately. This is because compilation is all about makin=
g assumptions. A dynamic language makes it very hard to make assumptions (t=
here 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 read=
ing 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 la=
nguages to be completely dynamic. By dynamic, I mean that it is not possibl=
e to make an assumption about the result of an expression unless it is exec=
uted. If you can make an assumption about an expression, I don't consider i=
t 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 specif=
ied explicitly and can't change due to the environment or scope of executio=
n. We also know that all arguments to a function will be evaluated in the c=
urrent 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 inter=
preter to make assumptions.


>
> A good indication of a non-dynamic programming language is the presence o=
f semantically meaningful keywords, especially those that have fixed behavi=
our. Examples include "def", "if", "while", "switch" and "try". These expre=
ssions 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 =3D lambda {"truthy"}
is_falsy =3D lambda {"falsy"}

1.if_true(is_truthy)                    # =3D> "truthy"
1.if_true_else(is_truthy, is_falsy)     # =3D> "truthy"
1.if_false(is_falsy)                    # =3D> nil

nil.if_true(is_truthy)                  # =3D> nil
nil.if_true_else(is_truthy, is_falsy)   # =3D> "falsy"
nil.if_false(is_falsy)  # =3D> "falsy"

true.if_true(is_truthy)                 # =3D> "truthy"
true.if_true_else(is_truthy, is_falsy)  # =3D> "truthy"
true.if_false(is_falsy)                 # =3D> nil

(1 =3D=3D 2).if_true_else(is_truthy, is_falsy)  # =3D> "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 ex=
ecution 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, ther=
e 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 mode=
l.

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.
--=20
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