Unified prelude, FFI, multiple runtimes
Hi, please point your browser to http://nothingmuch.woobling.org/compilation_of_circular_prelude.; ~ any(graffle vdx pdf png jpg).pick; My proposition: 1. *the* perl 6 compiler should ship a reference implementation of the prelude, that is circular. For example multi *infix:* (Int $x, Int $y) { [+] $x xx $y } is the reference implementation of multiplication on integers. 2. each block of code has a cryptographic digest, which is the hash of it's body with the digests of all the functions it calls. This digest is stable regardless of optimization semantics, and is applied to the PIL structure. 3. a foreign function interface must exist, and have function somewhat like the Inline:: modules function today (presumably with a lower level but zero-copy interface an option). 4. FFI definitions are defined using a uniform interface, whose most basic interface is a constructor for a code object that takes a runtime and a string body, e.g. Code::Foreign.new(:languageC, :body(int foo () { return 10 })); (Some FFIs might only allow construction of foreign functions at compile time.) 5. Functions have a notion of equivelence. This is managed based on the digest. For example my c_int_mul = BEGIN { Code::Foreign.new(:languageC, :body( int foo (int x, int y) { return x * y } ) }; multi infix:* (int $x, int $y -- int) { [+] $x xx $y; } my $str = infix:*int, int -- int.digest; # must specify the variant c_int_mul.set_equiv($str); # could be in another file # or, if they are maintained together c_int_mul.set_equiv(infix:*int, int -- int); This equivelence is with respect to the semantics of the input and output. The test suite supposedly can assure that these are really equivelent by running the same tests against either version. 6. the runtime is just an FFI provider, which happens to be the default one too 7. When applying code in the runtime, the runtime is free to use any equivelent function 8. In order to run perl code at all, some native equivelent functions must be provided by the runtime, for the basic operations, and things that can't have reference implementations like IO calls (which are implemented in the prelude as stubs). 9. static analysis may be leveraged to compile direct calls to native functions when compile time resolution is possible. In the example graph, for example, no eval or symbol table assignments are made, so there is no way the code will ever change. Hence the entire program can be pre-resolved. This should be controlled via the 'optimize' pragma. the reasons for this will now be discussed. A unified prelude with reference implementations for even the simplest operations gives us several things: * a circular structure that doesn't make sense when we try to run it, since the prelude depends on itself (bad) * must break circularity by going to native operations * a reference spec that alternative runtimes can compare to * a way to kickstart implementations * just provide a root set of native operation, enough to break circularity in one single point * demagicalization of the language Since FFIs are going to be a core feature of perl 6, they can be used to bootstrap the whole compilation process. In effect, the primitive operations are now just FFI calls to the runtime we happen to be executing on. To promote code reuse and to simplify the model the notion of equivelence is introduced, letting the runtime pick which version of a function (FFI or native) it uses. To make things safe, when the prelude is bug fixed and the runtime is not yet updated, the cryptographic hash of the function changed, so it is no longer equal to the native one based on the way they are paired. To make things modular, the paring of FFI and pure perl functions is orthogonal to their location of definition based on the hashing scheme. This has some nice properties: Modules like Template::Stash::XS are depracated. Instead, an FFI based Template::Stash can be automatically loaded from the runtime library prefix, and it will be set as equivalenet to the pure perl Template::Stash. Modules like DBD::your_db which rely on a certain library can be stubbed in Perl 6 to tell the user that they must use a certain runtime. The stubs are set as equal to the FFI calls into the library. WRT MMD, you can set the entire MM equivalent to a certain foreign function, and
Re: Unified prelude, FFI, multiple runtimes
On Mon, Sep 12, 2005 at 13:15:33 +0300, Yuval Kogman wrote: To make things safe, when the prelude is bug fixed and the runtime is not yet updated, the cryptographic hash of the function changed, so it is no longer equal to the native one based on the way they are paired. It should be noted that this equivalence should be transitive.. For example, if the prelude's definition of foo is changed, but this is for readability or optimization, and did not change behavior at all, it can be simply marked as equal to the hash of the previous version. This way the runtimes' equality tables don't have to be updated every time the prelude changes - only when it's behavior changes. -- () Yuval Kogman [EMAIL PROTECTED] 0xEBD27418 perl hacker /\ kung foo master: /me sneaks up from another MIME part: neeyah! pgpwQmIzz5xGR.pgp Description: PGP signature
Re: Unified prelude, FFI, multiple runtimes
On Mon, Sep 12, 2005 at 13:15:33 +0300, Yuval Kogman wrote: The circularity issue was not made clear in the email or the diagram. Here is what I meant: The prelude operators are mutually recursive at some point, and completely pure. An pathetic example: multi infix:- (Int $x, Int $y) { $x + 1 - $y - 1 } multi infix:- (Int $x, 0) { $x } multi infix:+ (Int $x, Int $y) { ($x + 1) + ($y - 1) } multi infix:+ (Int $x, 0) { $x } multi infix:+ (Int $x, 1) { ... } # really a stub, requires native increment multi infix:- (Int $x, 1) { ... } # really a stub, requires native decrement (I should note that once the language grows it becomes rather circular especially when control flow and combinators get involved...) This allows runtime authors to provide a minimal root set of operations to break the circularity of the prelude (and even this can be done incrementally, i guess), and get a slow but functional system in very little time. This root set is dynamic, and can be chosen by the runtime implementor based on how well this fits into the the target arch. This opens a door to a variety of levels of target implementations... The metamodel, for example, could be implemented in the prelude. When it is not implemented natively it will be slow, but will work. Serious runtime implementations can override the parts of the metamodel that profiling has shown to be slow. -- () Yuval Kogman [EMAIL PROTECTED] 0xEBD27418 perl hacker /\ kung foo master: /me does not drink tibetian laxative tea: neeyah! pgpsTL94mNGSZ.pgp Description: PGP signature
Summary for the last 3 weeks
The Perl 6 Summary from 2005-08-24 to 2005-09-11 It's been a while hasn't it? We'll start as usual with perl6-compiler This week in perl6-compiler Changed ??:: to ??!! in Pugs Following discussion of the ternary operator in perl6-language, Benjamin Smith altered pugs to use the new ??!! syntax. http://xrl.us/hjb5 Meanwhile in perl6-internals Which 'English'? Joshua Hoblitt posted a patch to intro.pod fixing a few typos and wondered whether the docs should be in British or American English. Apparently the Perl 5 style rule is that British authors shouldn't be required to write American English, and vice versa, but that a consistent style within a document is preferred. The consensus so far seems to be Any documentation is good so write what's comfortable for you. http://xrl.us/hjb6 Meanwhile, at the test Warne just got Trescothick out. 109 for 4 Python PMCs Sam Ruby, Leo and Chip had a discussion of how to implement python semantics for parrot. I'm not sure I followed what was going on, but it looked like good 'crunchy' stuff. http://xrl.us/hjb7 Zcode interpreter release Amir Karger announced that he'd adopted the Zcode interpreter that Leo posted in February (having, according to Amir, done the hard parts). Apparently there's 41 opcodes to do just to get version 3 of the Z-machine working, and then there's the problem of making Zops into loadable Parrot ops. He had a few problems with the test suite which got fixed in discussion. http://xrl.us/hjb8 Pirate refactoring report Michal Wallace posted an update on Pirate (the python to parrot compiler). He and Curtis Hall have been taking advantage of a Google Summer of Code grant to refactor the (Curse! Now Flintoff's out. Caught bowled Warne for 8) current mess. Their first step was a generic transformation module which has apparently made life easier for the compiler module. They've also produced a plan in code for how they hope they'll have things working once the refactoring's finished and asked for comments. So far comments have not been forthcoming. http://xrl.us/hjb9 http://xrl.us/hjca Tcl in the leo-ctx5 branch Will Coleda's been having a crack at getting ParTcl working with the leo-ctx5 branch and had a few problems. It turns out that he'd tickled a bug that Leo described as 'a bit non-trivial'. It took him a while, but it got fixed eventually (Over 10 days, but he did have the excuse of being at YAPC::Europe for a chunk of that time). http://xrl.us/hjcb Meanwhile at the Oval They've gone in for lunch at 127 for 5. Hopefully I'll be able to get down to some summary writing without being on the edge of my seat for a while. Branch Review Chip posted a review of the leo-ctx5 branch prior, describing it as A significant improvement. The body of the review covers user visible changes and a few niggles with the current state of the branch. Leo replied with a few questions and explanations. http://xrl.us/hjcc GMC release Nattfodd announced the 'release' of GMC, the generation garbage collector he's been working on as part of Google's Summer of Code. It's not quite bug free yet, but the SoC deadline was the 1st of September, so that's when it got released. Discussion ensued, hopefully helping to triangulate bugs. http://xrl.us/hjcd Call for B0rked Following a discussion with Chip and Leo, chromatic posted a call for entries in a 'very specific TODO list'. A list of things that should work, but don't. He contributed a couple himself. Various other suggestions were offered. http://xrl.us/hjce Optimizer Documentation Curtis Rawls spent part of his Summer of Code project wishing there was better documentation of the Parrot optimizer. So he wrote some. Brent Royal-Gordon converted it to POD format, and Leo asked for someone to add it to the repository. http://xrl.us/hjcf HLL Namespace Design Matt Diephouse posted a list of namespace features that he thinks are necessary to support all the target languages and asked for some comments. He got several, including one from Larry. http://xrl.us/hjcg Global Destruction Nicholas Clark had some questions about finalization and destruction in Parrot. In particular, he asked: Does parrot make any guarantee that all objects will be rendered down to bare memory before program exit. Leo answered and the answer was good enough for Ponie. Huzzah. http://xrl.us/hjch Meanwhile, at the Oval Ah... they're back on the pitch... I may be slowing down again... Meanwhile, in perl6-language Demagicalizing Pairs Discussion of Luke's proposal to demagicalize Pairs continued. It turns out that it's actually a discussion of how to do named argument calling...
Object Model Pictures
Hello again. In my never ending quest to implement the Perl 6 object model, I have started drawing pictures. Here is the latest version: http://svn.openfoundry.org/pugs/perl5/Perl6-MetaModel2.0/docs/ p6_object_model.jpg (and for OmniGraffle users: http://svn.openfoundry.org/pugs/perl5/ Perl6-MetaModel2.0/docs/p6_object_model.graffle) I would appreciate any comments/questions/suggestions anyone has to offer. A few things to note: - Roles are not yet included in this, I am of the opinion that the core MetaModel should be role-less, and roles will be laid on top of the core metamodel post-bootstrapping. This makes the most sense currently, however, this may change down the road, either way I think it is an implementation detail as long as it looks the same when everything is loaded. - the word meta is used to describe the three-circle items. Please do not read to much into this terminology, meta simply means you should not touch this unless you *really* know what you are doing. Suggestions on better names are welcome. - the reason Foo and $foo are smaller is because they are user created items. Okay, thats all my caveats, fire away please. Stevan
Re: Unified prelude, FFI, multiple runtimes
On 9/12/05, Yuval Kogman [EMAIL PROTECTED] wrote: Hi, Hi. These are superficial thoughts, before I've had time to really think about the Big Picture. 2. each block of code has a cryptographic digest, which is the hash of it's body with the digests of all the functions it calls. This digest is stable regardless of optimization semantics, and is applied to the PIL structure. Okay, a little clarification needed here. Is the digest of the code itself a collection of digests, one for the lexical body, and one for each funciton it calls (1)? Or is it a hash that combines all of those somehow? How do you deal with recursive/mutually recursive functions? (I'm pretty sure there's a way, I just can't think of it) What about temp foo = sub {...} ? 5. Functions have a notion of equivelence. This is managed based on the digest. For example my c_int_mul = BEGIN { Code::Foreign.new(:languageC, :body( int foo (int x, int y) { return x * y } ) }; multi infix:* (int $x, int $y -- int) { [+] $x xx $y; } my $str = infix:*int, int -- int.digest; # must specify the variant You mean: my $str = infix:*:(int, int -- int).digest; Also, you said that the digest contains the digests of all called functions. How do you deal with multis there, which may depend on the runtime types? c_int_mul.set_equiv($str); # could be in another file # or, if they are maintained together c_int_mul.set_equiv(infix:*int, int -- int); This equivelence is with respect to the semantics of the input and output. The test suite supposedly can assure that these are really equivelent by running the same tests against either version. Okay, good. So you have a way of marking that two functions do the same thing, without having the program try to figure that out (which is impossible). That's something that Haskell didn't figure out :-) I suppose it would be nice to have subtype semantics, in that function A does the same thing as function B for all arguments that are valid for function B (but function A may have additional functionality for arguments that are not valid for B). Then you specify equivalence by specifying subtype equivalence in both directions (with a shortcut, of course). 9. static analysis may be leveraged to compile direct calls to native functions when compile time resolution is possible. In the example graph, for example, no eval or symbol table assignments are made, so there is no way the code will ever change. Hence the entire program can be pre-resolved. This should be controlled via the 'optimize' pragma. Rather than having the compiler try to infer for itself, which would come up negative 99% of the time and just waste compile time. Since FFIs are going to be a core feature of perl 6, they can be used to bootstrap the whole compilation process. In effect, the primitive operations are now just FFI calls to the runtime we happen to be executing on. And if you have a circular reference implementation, the implementors can decide to implement whatever generating subset is easiest and get a working Perl. I like this. Hmm, could we pull the idea of a generating subset out to roles/theories? That is, have a role specify that a and b are implemented in terms of each other, so if you provide one, you fulfill the role contract. In Haskell, if you don't fulfill a class contract that's mutually recursive, you get infinite loops. It be nice to catch that. Then I guess we would have theory PerlCore. Neat. To make things modular, the paring of FFI and pure perl functions is orthogonal to their location of definition based on the hashing scheme. So as we're hashing PIL, we'd leave out line number information and whatnot. WRT MMD, you can set the entire MM equivalent to a certain foreign function, and you can also set any variant individually. You can even set a single variant to be equivalent to a multimethod to make the FFI implementation simpler. The compiler simply presents the runtime with all the possible MMD choices, and lets the runtime choose between conflicting ones. Like a nice wrapping MMD scheme ought to. All in all, I like the idea. I hope there are no major technical hurdles. The hashing scheme scares me a little, because it's easy to create equivalent code that does not look the same from PIL, but it seems like you covered that base. Luke
Re: Unified prelude, FFI, multiple runtimes
A proof of concept is available here: http://svn.openfoundry.org/pugs/docs/notes/circular_prelude_stuff.pl And logs where I explain the guts to Luke are availble here: http://colabti.de/irclogger/irclogger_log/perl6?date=2005-09-12,Monsel=785#l1413 -- () Yuval Kogman [EMAIL PROTECTED] 0xEBD27418 perl hacker /\ kung foo master: /me supports the ASCII Ribbon Campaign: neeyah!!! pgppQ5g7Net6u.pgp Description: PGP signature
Re: Unified prelude, FFI, multiple runtimes
On Mon, Sep 12, 2005 at 13:27:21 -0600, Luke Palmer wrote: On 9/12/05, Yuval Kogman [EMAIL PROTECTED] wrote: Hi, Hi. These are superficial thoughts, before I've had time to really think about the Big Picture. 2. each block of code has a cryptographic digest, which is the hash of it's body with the digests of all the functions it calls. This digest is stable regardless of optimization semantics, and is applied to the PIL structure. Okay, a little clarification needed here. Is the digest of the code itself a collection of digests, one for the lexical body, and one for each funciton it calls (1)? Or is it a hash that combines all of those somehow? If there is a given function x, that calls another function y, and there is an FFI function z that is the same as x (it refers to it's hash). If 'y' is changed, then the semantics of x may change, hence the hash must change (a call to z is no longer equal to a call to x). (unless y says it is equal to the old y, by mentioning it's hash). How do you deal with recursive/mutually recursive functions? (I'm pretty sure there's a way, I just can't think of it) Right now I don't, i'm cheating. In the future I'd like to hash the body for all functions, and then hash the hash of the body and the hashes of all the called bodies to make a function hash. What about temp foo = sub {...} ? This has an entirely different hash, so it doesn't go to the same thing. my $str = infix:*int, int -- int.digest; # must specify the variant You mean: my $str = infix:*:(int, int -- int).digest; uh, yeah... I keep forgetting the syntax. Also, you said that the digest contains the digests of all called functions. How do you deal with multis there, which may depend on the runtime types? replacements are per variant i guess, and the catch all (completely unqualified multi) has a hash built out of all it's variants. I suppose it would be nice to have subtype semantics, in that function A does the same thing as function B for all arguments that are valid for function B (but function A may have additional functionality for arguments that are not valid for B). Then you specify equivalence by specifying subtype equivalence in both directions (with a shortcut, of course). I'll leave this part to you ;-) assignments are made, so there is no way the code will ever change. Hence the entire program can be pre-resolved. This should be controlled via the 'optimize' pragma. Rather than having the compiler try to infer for itself, which would come up negative 99% of the time and just waste compile time. I disagree... Most one liners and small scripts could really benefit from this, and it's an easy test - just set a flag the moment you see either the eval opcode or the ::= opcode. And if you have a circular reference implementation, the implementors can decide to implement whatever generating subset is easiest and get a working Perl. I like this. Yes, this is why I brought it up =) Hmm, could we pull the idea of a generating subset out to roles/theories? That is, have a role specify that a and b are implemented in terms of each other, so if you provide one, you fulfill the role contract. In Haskell, if you don't fulfill a class contract that's mutually recursive, you get infinite loops. It be nice to catch that. it's too late for me to understand that... sorry... So as we're hashing PIL, we'd leave out line number information and whatnot. Yeah, this is also possibly the canonical representation. For example sub foo ($x) { $x ? 1 : 2; } sub foo ($x) { if ($x) { return 1; } else { return 2; } } All in all, I like the idea. I hope there are no major technical hurdles. The hashing scheme scares me a little, because it's easy to create equivalent code that does not look the same from PIL, but it seems like you covered that base. I won't expect a reference implementation to be refactored too much, but even if it does, you just say that this function is the same as the function with the hash value x, where x is the hash it had before the refactoring. -- () Yuval Kogman [EMAIL PROTECTED] 0xEBD27418 perl hacker /\ kung foo master: /me tips over a cow: neeyah!! pgpzsQPvto7BO.pgp Description: PGP signature
Re: Object Model Pictures
On Mon, Sep 12, 2005 at 03:10:55PM -0400, Stevan Little wrote: In my never ending quest to implement the Perl 6 object model, I have started drawing pictures. Here is the latest version: http://svn.openfoundry.org/pugs/perl5/Perl6-MetaModel2.0/docs/ p6_object_model.jpg Awesome diagram. I would appreciate any comments/questions/suggestions anyone has to offer. In my never ending quest to understand the Perl 6 object model, I think it has become clearer each time I've discovered another document or picture. Thank you Stevan! A few things to note: - Roles are not yet included in this, I am of the opinion that the core MetaModel should be role-less, and roles will be laid on top of the core metamodel post-bootstrapping. This makes the most sense currently, however, this may change down the road, either way I think it is an implementation detail as long as it looks the same when everything is loaded. Yep, someone needs to make a diagram about Roles, too. -kolibrie