bug in syntax-case in master
I'm trying to port syntax-parse to master. And get into the following trubble (syntax-case x (integrate) ((integrate a b) ...)) fails, but (syntax-case x (integrate) ((_ a b) ...)) does not fail looking at the code for syntax-case I would expect that the datum integrate is match against and not using syntax any syntactic information. In psyntax.scm around 2419 we have, ((bound-id-member? p keys) (values (vector 'free-id p) ids)) keys are the fixed datums, and (define bound-id-member? (lambda (x list) (and (not (null? list)) (or (bound-id=? x (car list)) (bound-id-member? x (cdr list)) e.g. no comparisons of the datum. Is this correct! I do understand that this can be a feature but is this expected? In syntax parse both options are possible. /Regards Stefan
Re: stack closures for guile-log
Hi, Yes, I think that if one go for capturing the stack via copying frames then that's the way to go. This makes rewinding and unwinding fast. on the other hand, currently in guile-log we use very small linked frames so that essentially all the stored information is lying in the heap compressed to a tree and is therefore superior memory wise, because of the compression and because the GC get better oppertunities to reclaim memory. However I need to find more bench mark more in order to understand this better. I also must add hooks to handle a satck with stored coses. They serve as a derefernce and identity objects for the closures which will be reference throughout the heap. I cannot move the conses but I can release the references to them and allocate new conses in essence move a cons from the stack to the heap. This is quite neat but do decrease the possibilities of reclaiming memory in some cases so conses on the stack will be an expert option but is needed to get the last 2x - 3x speedup down to what compiled prolog can do. The bulk of the closures stack is quite simple in it's functioning and there I think it's a bit over kill to use a dynstack. Thanks for the info and Cheers! On Tue, May 15, 2012 at 10:37 PM, Andy Wingo wi...@pobox.com wrote: On Tue 08 May 2012 21:16, Stefan Israelsson Tampe stefan.ita...@gmail.com writes: I have three stacks 1. a control stack that stores undo information scheme hooks aka dynamic-wind and stack references to the other stacks. Have you seen dynstack.[ch] on master? 2. stack from which data is allocated from like the bulk of a closure and special pairs 3. a cons stack, e.g. an array of allocated conses I wonder, can you implement these too using something like the dynstack? Andy -- http://wingolog.org/
Re: syntax parse link
Thx, I have a few things I would like to do first but maybe after this weekend I will make the linkage! /Stefan On Tue, May 15, 2012 at 10:33 PM, Andy Wingo wi...@pobox.com wrote: On Tue 08 May 2012 17:46, Stefan Israelsson Tampe stefan.ita...@gmail.com writes: I would like to add a link to the syntax-parse repo from guile's home page. I was told to try get the rights to do this myself. If that doesn't work I will need help from any of the maintainers to make the linkage. I've added you to the Guile group. You should be able to make a writable CVS checkout of the web repository. (Yes, CVS. It's incredible. I keep forgetting how to use it.) Anyway the bulk of the web site is in template/ and generated. I think there is a README. It is still horribly complex. Anyway good luck, and ask on IRC when you have problems! Andy -- http://wingolog.org/
problems evaluating code depending on version
hi, I'm trying to use this as a way to defined different versions of the code depending on the guile-version. So here it is, (eval-when (compile load eval) (define (ver) (let ((v (version))) (cond ((string-match ^2.0 v) 'v2.0) ((string-match ^2.1 v) 'v2.1) (else #f) (define-syntax guile-stuff (lambda (x) (syntax-case x () (_ (let ((q (ver))) (cond ((eq? q 'v2.0) #'(begin 1)) ((eq? q 'v2.1) #'(begin (define-syntax-rule (fluid-let-syntax . l) (syntax-parametrize . l)) (export fluid-let-syntax))) (else (error not supported version (guile-stuff) This does not work in master (v2.1) why? /Stefan
bug in syntax-case in master
I have found the bug, It was because of the bug fixed in master got a bug in my code visible! /Stefan -- Forwarded message -- From: Stefan Israelsson Tampe stefan.ita...@gmail.com Date: Wed, May 16, 2012 at 8:57 PM Subject: bug in syntax-case in master To: guile-devel guile-devel@gnu.org I'm trying to port syntax-parse to master. And get into the following trubble (syntax-case x (integrate) ((integrate a b) ...)) fails, but (syntax-case x (integrate) ((_ a b) ...)) does not fail looking at the code for syntax-case I would expect that the datum integrate is match against and not using syntax any syntactic information. In psyntax.scm around 2419 we have, ((bound-id-member? p keys) (values (vector 'free-id p) ids)) keys are the fixed datums, and (define bound-id-member? (lambda (x list) (and (not (null? list)) (or (bound-id=? x (car list)) (bound-id-member? x (cdr list)) e.g. no comparisons of the datum. Is this correct! I do understand that this can be a feature but is this expected? In syntax parse both options are possible. /Regards Stefan
Re: problems evaluating code depending on version
I tried cond-expand, just to see if it worked and no the export clause does not fall through and the symbols are not exported. I can fix this as you say by using the new interface syntax-parameter interface but I'm curious how to be ably to conditionally export symbols depending on the guile-version! /Stefan On Thu, May 17, 2012 at 10:20 AM, Andy Wingo wi...@pobox.com wrote: On Wed 16 May 2012 23:32, Stefan Israelsson Tampe stefan.ita...@gmail.com writes: (define-syntax guile-stuff (lambda (x) (syntax-case x () (_ (let ((q (ver))) (cond ((eq? q 'v2.0) #'(begin 1)) ((eq? q 'v2.1) #'(begin (define-syntax-rule (fluid-let-syntax . l) (syntax-parametrize . l)) (export fluid-let-syntax))) (else (error not supported version Here the macro introduces a new identifier, fluid-let-syntax. But its context is not that of the (guile-stuff) expression. If you did (datum-syntax 'fluid-let-syntax x) that might work. In general cond-expand is better. I just added a guile-2.2 feature on master. Use that instead. But in this case, better to just change both versions to use syntax-parameterize :) Andy -- http://wingolog.org/
Re: problems evaluating code depending on version
Your version works but I would like to export as well in the cond-expand e.g. (cond-expand (guile-2.2 (define-syntax-rule (fluid-let-syntax . l) (syntax-parametrize . l)) (export fluid-let-syntax)) (guile-2) (else (error not supported version))) /Stefan On Thu, May 17, 2012 at 3:25 PM, Andy Wingo wi...@pobox.com wrote: On Thu 17 May 2012 14:47, Stefan Israelsson Tampe stefan.ita...@gmail.com writes: I tried cond-expand, just to see if it worked and no the export clause does not fall through and the symbols are not exported. I can fix this as you say by using the new interface syntax-parameter interface but I'm curious how to be ably to conditionally export symbols depending on the guile-version! (cond-expand (not guile-2.2 (define-syntax-rule (fluid-let-syntax . l) (syntax-parameterize . l))) (else #t)) At the top level, not wrapped in (guile-stuff) :) Andy -- http://wingolog.org/
Re: how to implement mutual recursive parsers in syntax-parse
I manage to make it work under master as well as guile-2.0 But the mutual code does not work. On the other hand what you said some months ago was correct and I believe that we do not need special constructs for local syntax-classes anymore which if correct is a plus. Please read the mail again is master supposed to expand and evaluate all the syntax defines before expanding the defines? And if a plain macro is encountered at the toplevel it is expanded as well in the first run. I don't understand exactly how the expansion progresses so can you describe or link to a description? Regards Stefan On Tue, May 15, 2012 at 8:38 PM, Andy Wingo wi...@pobox.com wrote: On Mon 14 May 2012 21:13, Stefan Israelsson Tampe stefan.ita...@gmail.com writes: (begin (define parser-a code-a ...) (define-syntax a spec-a)) (begin (define parser-b code-b ...) (define-syntax b spec-b)) In racket they manage to evaluate the define-syntax forms before the define-forms cause in the expansion of code-a amd code-b they need the spec's spec-a and spec-b. Do you have any ideas how solve this. I do have a fix for problem but it is not easy to use. Have you tried master? If I understand you correctly I think it should work there. Andy -- http://wingolog.org/
Re: how to implement mutual recursive parsers in syntax-parse
Another clue, Put this into a file and load it (define (f x) (c)) (define-syntax c (lambda (x) (pk 'c) #t)) ,x f shows 0(assert-nargs-ee/locals 1) ;; 1 arg, 0 locals 2(toplevel-ref 1);; #syntax-transformer c 4(tail-call 0) at examples/mutual.scm:9:14 and (f 1) yields scheme@(guile-user) [4] (f 1) ERROR: In procedure #syntax-transformer c: ERROR: Wrong type to apply: #syntax-transformer c This is confusing!! /Stefan On Tue, May 15, 2012 at 8:38 PM, Andy Wingo wi...@pobox.com wrote: On Mon 14 May 2012 21:13, Stefan Israelsson Tampe stefan.ita...@gmail.com writes: (begin (define parser-a code-a ...) (define-syntax a spec-a)) (begin (define parser-b code-b ...) (define-syntax b spec-b)) In racket they manage to evaluate the define-syntax forms before the define-forms cause in the expansion of code-a amd code-b they need the spec's spec-a and spec-b. Do you have any ideas how solve this. I do have a fix for problem but it is not easy to use. Have you tried master? If I understand you correctly I think it should work there. Andy -- http://wingolog.org/
Re: syntax parse link
Ok! I Updated the homepage with a link to guile syntax parse I put it on the tools section at the bottom! Pleas do a sanity check that I did this correctly. This was my first step to edit that repo. /Stefan On Wed, May 16, 2012 at 11:12 PM, Ludovic Courtès l...@gnu.org wrote: Hi Stefan, Stefan Israelsson Tampe stefan.ita...@gmail.com skribis: I have a few things I would like to do first but maybe after this weekend I will make the linkage! Please add it to gnu-guile-projects.html (under template/ first, as Andy mentioned), and using the same format as other entries there. Thanks! Ludo’.
Re: how to implement mutual recursive parsers in syntax-parse
Jolly nice, this is perfect! Den 21 maj 2012 10:59 skrev Andy Wingo wi...@pobox.com: On Sat 19 May 2012 00:05, Stefan Israelsson Tampe stefan.ita...@gmail.com writes: (define (f x) (c)) (define-syntax c (lambda (x) (pk 'c) #t)) These expressions are expanded in order, not together. To expand them together they need to be wrapped in a begin. We can consider changing our toplevel expansion process to do something else, if there is a right thing. Andy -- http://wingolog.org/
Re: syntax parse link
Ok, those issues are now fixed! On Tue, May 22, 2012 at 6:18 PM, Ludovic Courtès l...@gnu.org wrote: Hi! Thanks! There are a few typos: guile - Guile racket - Racket an hygienic - a hygienic recomending - recommending Also, could you move it above, to keep the list alphabetically sorted? Thanks, Ludo’.
Re: patch to guile to allow c-code closure interaction for logic programming
I use this method to interop c-code compiled logic programs o guile,
note: I saw that there have been restructuring the call logic somewhat
meaning that
the dispatching to the logic c code get's a little more expensive and a
little more different then presented below bot hey we can fix my code later
on!
Assume that we add a check for a data-structure representing a c code
closure that is located last in the chain of tests for special callable
structures just to be defensive to other
systems who want to call!
this check in call, tail-call and mv-call can then point to the different
goto labels in the supplied file (let's forget about mv-call for now) Then
the execution of the c-code will be done by starting a trampoline. This
trampoline assumes c functions that takes an argument representing the call
stack, the number of arguments, a pointer to the list of closure variables
and optionally a pointer representing the end of the stack. the function
assumes it return a integer. If it is possitive then there has been a new
function and arguments loaded into the old functions possition e.g. an
ordinary tail call from c land, the integer is the number of arguments for
this tail call. If the integer is negative then a return has been done with
the absolute value of the return representing the number of returned values
- useful information for mv-call logic.
Currently the c closure is represented as a cons of a tag with a vector
consisting of an integerization of the function pointer and closure data.
This should be changed later on but for now it's the right thing because of
the transparancy. (later on a smob would be a better fit)
By the way smob checks seems to be a little expensive, I noted that my
logic code spend a lot of time in these smob tests and wonders if the tests
for smob identity can be optimized?
So the basic code for handling this logic is attached to this document.
Coding c code using this method is error prone and perhaps not that useful
as an official interface to C-land. On the other hand I have a macro system
in scheme that transform a mix of scheme and C inspired language out to C
and using this system the interfacing is automated (I can actually write
logic programming code and it compiled it directly to C). It's just a proof
of concept right now and is a way to test the limits of the logic framework
(guile-log) I've coded on for some time.
So Comments lpease there might be some details I'm missing and also iI
wouldlike to have comments if it would be possible to include such a system
and maybe put it in relation to how we intend to use naitive code in the
future! On the other hand, apart from the bloat, the wished for changes to
the code base is not that intrusive so we could as well implement this
so that people can play with the logic system even on the c-level without
needing to recompile a patched guile!
/Stefan
On Tue, May 15, 2012 at 10:38 PM, Andy Wingo wi...@pobox.com wrote:
On Wed 09 May 2012 18:07, Stefan Israelsson Tampe stefan.ita...@gmail.com
writes:
I post here a directory of patches and code that can be used to enhance
guile to interact nicely
with logic programming code written in C. I can reach very good
performance using this tool
please have a look and comment on it.
Would you mind attaching them to the message directly? It's easier to
read and comment that way.
If you want, you can do the linux kernel thing of one patch per
message. But as you like.
Cheers,
Andy
--
http://wingolog.org/
#define NUM2PTR(x) ((SCM *) (SCM_UNPACK(x) ~2))
{
//C trampolines
int ret; SCM *spp;
const SCM *vec;
int (*subr)(SCM **spp, int nargs, const SCM *closure, const SCM *end);
vm_c_call:
//printf(c call!\n);
vec = SCM_I_VECTOR_ELTS(SCM_CDR(program));
//VM_HANDLE_INTERRUPTS;
//SYNC_REGISTER ();
spp = sp;
SCM *sp_old = sp;
//printf(dp %p\n,sp);
subr = (subr_type) NUM2PTR(vec[0]);
ret = subr(spp,nargs,vec + 1,stack_limit);
//CACHE_REGISTER ();
sp = spp;
if(ret0)
{
//printf(return call\n);
sp = sp + ret - 2;
sp[0] = sp[-ret + 2];
//printf(dp %p, n = %d\n,(void *)(sp_old-sp), nargs);
program = SCM_FRAME_PROGRAM (fp);
NEXT;
}
nargs = ret;
program = sp[-nargs];
if(SCM_CONSP(program) scm_is_eq(SCM_CAR(program),c_closure_tag))
goto vm_c_call;
goto vm_call;
vm_c_tail_call:
vec = SCM_I_VECTOR_ELTS(SCM_CDR(program));
subr= (subr_type) NUM2PTR(vec[0]);
//printf(c tail call!\n);
//VM_HANDLE_INTERRUPTS;
//SYNC_REGISTER ();
spp = sp;
ret = subr(spp, nargs, vec + 1, stack_limit);
//CACHE_REGISTER ();
sp = spp;
if(ret0)
{
sp = sp + ret + 1;
goto vm_return;
}
nargs = ret;
program = sp[-nargs];
if(SCM_CONSP(program) scm_is_eq(SCM_CAR(program),c_closure_tag))
goto vm_c_tail_call;
goto vm_tail_call;
}
assembler in scheme
I got an idea, why not design a portable assembler that have a unifying simple core and try to model a VM on that e.g. simple things will be naitive and complex instructions can be dispatched via a named goto. The solution would fix a few registers like the bp and then have enough instructions to be able to dispatch and move objects in memory and implement correct function call semantics. I would use two fixed hardware - registers. 1. bp: to track the function stack 2. vm: to track vm local data. It would be cool if we could say to gcc to not clobber those registers and compile the vm as before without changing especially much but with some assembler to do the needed jump correctly and also reach the register associated data. One idea was to use sassy, but it does only support x86. Another idea is to port the sbcl assembler to scheme. This means that we will get assemblers for a larger set of targets but still not enough to be portable. The final idea I got was to use the information in gcc or gas somehow. Anyway I need somthing new to chew on, so why not port the sbcl assembler at some level. Regards Stefan
The future of guile-log
Hi all, I feel that the basic technology is now in place when it comes to guile-log. It's future proof code base meaning that other technologies has to be in place before tweaking it further. I know that it can handle multiple threads and be speedy when native compilation becomes a reality. So I will from now on focus on improving the documentation. I also plan to port over the rack-log interface to logic programming. The current version is not too bad when it comes to speed but will be more then 10x from what's possible. I will let it rest on that. I did try to initiate a discussion about C closures and trampoline framework. But feel that it's better to wait until guile get's a decent framework for JIT and native code. /Regards Stefan
Re: ballpark rtl speeds
Great!
So If you code the new VM interpreter you get 2x improvement
If you generate code and compile with no optimization about another 3x
If you are able to generate code that compiles with optimisation bsically
using a register
you will get ?
Using a register as a storage on my machine yields 0.4s and the above c code
was using about 2.6s. About a further 6x in performance.
Great work!
/Stefan
On Thu, Jun 7, 2012 at 10:47 AM, Andy Wingo wi...@pobox.com wrote:
Hi,
Some ballpark measurements of the overhead of the old VM, the new VM,
and C (compiled with gcc -g -O0).
Old interpreter:
$ guile --no-debug
(define (countdown* n)
(let lp ((n n))
(if (zero? n)
#t
(lp (1- n)
,time (countdown* 10)
;; 14.054572s real time, 14.033213s run time. 0.00s spent in GC.
New interpreter:
(use-modules (system vm rtl))
(define countdown
(assemble-program
'((begin-program countdown 1)
(assert-nargs-ee/locals 1 2)
(br fix-body)
(label loop-head)
(load-constant 2 0)
(br-if-= 1 2 out)
(sub1 1 1)
(br loop-head)
(label fix-body)
(mov 1 0)
(br loop-head)
(label out)
(load-constant 0 #t)
(return 0
,time (countdown 10)
;; 6.023658s real time, 6.014166s run time. 0.00s spent in GC.
Note that this is not the ideal bytecode -- there are two branches per
loop iteration when there could just be one. But it's what the existing
tree-il compiler would produce.
C, with gcc -O0, disassembled:
#include stdlib.h
int
main (int argc, char *argv[])
{
400514: 55 push %rbp
400515: 48 89 e5mov%rsp,%rbp
400518: 48 83 ec 20 sub$0x20,%rsp
40051c: 89 7d ecmov%edi,-0x14(%rbp)
40051f: 48 89 75 e0 mov%rsi,-0x20(%rbp)
if (argc != 2)
400523: 83 7d ec 02 cmpl $0x2,-0x14(%rbp)
400527: 74 07 je 400530 main+0x1c
return 1;
400529: b8 01 00 00 00 mov$0x1,%eax
40052e: eb 2e jmp40055e main+0x4a
long l = atol (argv[1]);
400530: 48 8b 45 e0 mov-0x20(%rbp),%rax
400534: 48 83 c0 08 add$0x8,%rax
400538: 48 8b 00mov(%rax),%rax
40053b: 48 89 c7mov%rax,%rdi
40053e: e8 dd fe ff ff callq 400420 atol@plt
400543: 48 89 45 f8 mov%rax,-0x8(%rbp)
while (l--);
400547: 90 nop
400548: 48 83 7d f8 00 cmpq $0x0,-0x8(%rbp)
40054d: 0f 95 c0setne %al
400550: 48 83 6d f8 01 subq $0x1,-0x8(%rbp)
400555: 84 c0 test %al,%al
400557: 75 ef jne400548 main+0x34
return 0;
400559: b8 00 00 00 00 mov$0x0,%eax
}
40055e: c9 leaveq
40055f: c3 retq
$ time ./a.out 10
real 0m2.061s
user 0m2.056s
sys 0m0.000s
Of course with -O2 the loop goes away entirely ;) But it's an
interesting exercise.
Andy
--
http://wingolog.org/
progress with native code generation in guile
Hi, On linux, x86-64 I can now write, (use-modules (native aschm)) (define b (asm (inst mov rbx 10) ;rbx = 1000,000,000 loop: (inst cmp rbx 0) (inst jmp #:eq out:) (inst dec rbx) (inst jmp loop:) out: (inst mov rax 2) ; return value in register rax (inst pop rbx); we pushed the return adress before (inst jmp rbx))) ; jump back (mk-rwx b) ; Make the memory pages read write and ; execute (run-native b) ; run the code using a simple scheme And the code loops and return 0 (2). So it is possible to generate assembler from whithin guile and execute it which is pretty cool. If you have the right architecture, you can play with it at: https://gitorious.org/aschm Have fun Stefan
Re: Growable arrays?
Maybe this could be a first stub for a table structure that is uses both an array and a hash-table. I do think that implementing this might need fine tuning in order to have good defaults and so on. So in that sense one probably need to check out reference implementations. But this is for discussion! I Assumed growing here and have no shrinking! I made it nonfunctional. One note to the discussion. It is not just to combine a growable vector with a growable hash in ordder to have a one tool for all cases. The reason is that one need to tackle the issue with sparse tables with integer keys. I tried to add that feature as well in some way. Anyway it shows that you don't need a ton of code to get something pretty functional. On Mon, Jun 11, 2012 at 4:19 PM, David Kastrup d...@gnu.org wrote: Daniel Hartwig mand...@gmail.com writes: On 11 June 2012 20:20, David Kastrup d...@gnu.org wrote: P.S.: I still need to look at vlists. They might already address this issue, though I can't use them in Guile 1.8. No, the immutable angle would make them unsuitable again. Note that vlists are only immutable in the sense that you can not modify the value of a slot already allocated. Which makes it useless here. Scheme/Guile vectors are fixed size. Now I have a situation where I have a basic type lattice with records stored in vectors, and this type lattice may be extended dynamically (which typically happens at the start of a whole file, for potentially multi-file runs). From this I gather that your use case only appends to the lattice, if so, vlist is suitable for that task. Wrong. My use case only _allocates_ at the end of the existing type lattice, but the records are not read-only. Cough, cough. Standard vectors are not growable. Which is the original problem of this thread, never mind Lua. True, but a growable vector is a tiny step away from the standard vector. A tiny step if you are modifying the C code. A not so tiny step if you are working with Scheme. hashtables have additional indirection through hash buckets and coalescing lists This is fairly standard for a hash table. I would be quite surprised if the hash table part of a Lua table did not also use buckets. But it is not standard for a growable vector that it only comes with buckets and chains. Except that this one isn't. Why not? You take a vector and a hash table, store your values in them, and grow either as needed. This is not a complicated type. Except that vectors don't grow. Are you even reading what you are replying to? -- David Kastrup hasharray.scm Description: Binary data
Re: patching gcc to allow other calling conventions
Why not specify the logic in scheme and output it either to C or Assembler :-) /Stefan On Tue, Jun 19, 2012 at 12:30 AM, Noah Lavine noah.b.lav...@gmail.comwrote: Hello, But the used sbcl derivative although not gnu is either in the public domain or bsd so we should be able to publish what we are doing. I prefere now to start working on a simple jit scheme for the fun of it, because it is a good learning experience and that getting results are a good driver to continueu. A JIT would be a good thing for Guile to have. I worked on a JIT a while ago, and I found that the hard part was not generating machine code or connecting it to the VM - both of which it looks like you've done - but making the JIT engine understand all of the VM instructions. You could just hard-code them all, but then you've got a complete duplicate of vm-engine.c with exactly the same information, but in different syntax. So I thought I wanted some way to generate the JIT from vm-engine.c, but that requires parsing C code. That's a capability I want Guile to have in general, but I haven't made it happen yet. What do you think about this? Would you just want to maintain the JIT engine separately from vm-engine.c, or would you like to automatically generate it? (Note: you could also generate vm-engine.c and your JIT from some third source, but I think we rejected that for being too complicated. It would certainly make the build process more difficult.) Noah /stefan Den 18 jun 2012 02:43 skrev Noah Lavine noah.b.lav...@gmail.com: Hello, Did you consider starting from GNU/MIT Scheme? It supports only IA32 and x86_64, I think, but it’s in Scheme, and it’s GNU. Actually, that's an interesting thought in general. I looked at MIT scheme a bit a long time ago, but I believe it uses two intermediate languages, a high-level one similar to Tree-IL and a low-level one that I don't know much about. We might be able to turn Tree-IL into the high-level one and use their compiler infrastructure. Since they're a GNU project, there might not be copyright issues. However, I'm not sure if this has advantages over just building it ourselves. And I don't know if the MIT Scheme developers would like this or not. Noah
Re: patching gcc to allow other calling conventions
Yes this can be an issue. On a second thought guile do have an initital interpreter that is either a vm or a native no? Perhaps one can make use of that somehow! /Stefan On Thu, Jun 21, 2012 at 7:14 PM, Daniel Krueger keen...@googlemail.comwrote: Hey, On Thu, Jun 21, 2012 at 2:32 PM, Stefan Israelsson Tampe stefan.ita...@gmail.com wrote: Why not specify the logic in scheme and output it either to C or Assembler :-) That sounds very cool, and would be very cool, I thought first, but then I realized that you wouldn't be able to bootstrap guile anymore :-/ - Daniel
Re: patching gcc to allow other calling conventions
Hmm, yes then it can work. I would compile only to C at the first phase as you say as it should not be of too high complexity to output the C part and be pretty swift although you are interpreting. Then the VM can compile all guile including code to emit and compile assembler and then one can add the possibility to compile to native code by some kind of just in time mechanism. Cool! I will try to start investigating this approach. /Stefan On Thu, Jun 21, 2012 at 7:57 PM, Daniel Krueger keen...@googlemail.comwrote: On Thu, Jun 21, 2012 at 7:50 PM, Stefan Israelsson Tampe stefan.ita...@gmail.com wrote: On a second thought guile do have an initital interpreter that is either a vm or a native no? Perhaps one can make use of that somehow! Yeah, I thought about that too, but thought first that it would be impossible. But if you first only compile the interpreter code (without the VM), then create the C file with the instructions and compile the VM it should work. I think .. ^^ - Daniel
Re: Enhancement to the syntax system?
Maybe this help to see what I'm after, #'(let ((x v)) #.(f #'x)) = (let-syntax ((g (lambda (stx) (syntax-case stx ((_ x) (f #'x) #'(let ((x v)) (g x)) Now I would like to have a corresponding #.@ notation as well but can't find an analog for that :-( /Stefan On Mon, Jul 2, 2012 at 9:28 PM, Ludovic Courtès l...@gnu.org wrote: Hi Stefan, Stefan Israelsson Tampe stefan.ita...@gmail.com skribis: Hygiene is harder to maintain. e.g. I kept on hitting this kind of code snippets #'(let ((x v)) #,(f rest #'x)) The problem with this code is hygiene, I need to make a gensym and use with-syntax to bound x to that gensym in order to be safe at the macro expansion. What do you mean? Here ‘x’ leads to a newly introduced binding. Likewise, the code below doesn’t introduce bindings non-hygienic bindings, and is non-ambiguous: (macroexpand '(let-syntax ((f (lambda (s) (syntax-case s () ((_ x y) #`(let ((p x)) (+ p #,(identity #'y (f 1 2))) = #tree-il (let (p) (p-28239) ((const 1)) (apply (toplevel +) (lexical p p-28239) (const 2))) Thanks, Ludo’.
Re: A vm for native code in guile
On Tue, Jul 3, 2012 at 12:16 AM, Andy Wingo wi...@pobox.com wrote: On Mon 02 Jul 2012 09:53, Stefan Israelsson Tampe stefan.ita...@gmail.com writes: Anyway I can now compile simple functions to native sequences of machine code but with some tools around it so let me explain the setup. Where is this code? Sorry for not following the context. https://gitorious.org/aschm I agree with you that maintenance is the challenge. Have you looked at wip-rtl, Stefan? It should be easier to compile. However it's not fully baked yet, unfortunately. The problem with rtl is that it is not fully baked and that I expect that the hard part is to get the framework correct so that you do not shoot yourself in the foot all the time with the assembler - it's really hard to use! To speak honestly I am very impressed with your work. Thx, dito for many other guile hackers, including you, I really like this community! I leave that as its own paragraph because that's what I think. However, with my conservative Guile co-maintainer hat on I still have hesitations as to its applicability to mainline Guile. You are very good at getting Guile to work for you, but I would like to see more incremental patches. No problemo, The worst thing that can happen is that I get a well tested assembler framework running that people can download and use at their will which is not too bad. I do hope to start discussions about how to setup a native environment, If you look at the vm.scm file in the repo you will get the impression of a proposed design, I also propose to still keep some of the old VM's philosophy in using named goto when we can amortize the cost of doing it for the sake of a more compact compiled procedures. And many more things. However the assembler is a stand alone application independent of guile and there is a connection that hook into guile but that's just an incrementation away from plain guile. So you see, there is this although bloated chunk of 1 row scheme code that is standalone and there is a patch of 100 rows that makes it possible to execute a procedure as native. Not sure how to make the 1, row beasty creature incremental but surely the other part should be fine to increment in. It's basically 1. An extra flag for marking a procedure native executable 2. code to set a native bytevector on the objcode 3. hooks in vm-i-system.c to check for the native flag and if so executre the native code. (this is a half hearted implementation) 4. Implement some support functions on the C level to avoid writing all code in assenmbler but this is orthogonal code compared to plan guile. I expect this to grow look in the guile directory to see the file'a I've been touched in the guile-repo Also the assembler needs to go at some point because it's not GNU owned code. And Ludo suggested that we try to port over MIT/GNU Scheme over to guile, which is not a bad idea Also I do know enough, (after porting SBCL's assembler) to implement a Assembler from scratch but of cause that will take a couple of month's. I'll keep the aschm assembler for now though because I really want to play with the native execution issues. (sassy is also a possibility but that is only for x86 assembler and I wanted x86-64 to play with) I know that we have gone back and forth over the past couple years and this is probably frustrating to you. At the same time I think that your code, commits, and communication have gotten a _lot_ better over that time. If you have a complaint, please voice it. Otherwise we keep with this code review thing. Actually I have a really fun time hacking, so that I really do not care much about thumbs down or nit pickling, I can cope with that. Also I'm realistic about how much time people can spare and I do care that you continue with your own work for the benefit of the project. Also my own time commenting on other peoples ideas and question is not good so I can't demand that all should gather around and cheer the ideas I try to bring. But I do try to read in some of what you do and sometimes takes a detour in the wake of that information. What do you think about this situation? I enjoy it currently so why change! Peace, Andy -- http://wingolog.org/ /Stefan
Re: Enhancement to the syntax system?
You do not need gensyms if you try to mimic or implement my suggested #. . On the other hand when if you do this (define (f stx) #`(let ((x 1)) #,stx)) and use this with #`(let ((x 2)) #,(f #'x)) the resulting expanded code would produce 1 which is not what you want. So in the racket matcher I wrote I needed to do (with-syntax ((x (datum-syntax stx (gensym x #`(let ((x 2)) #,(f #'x)) Hope that this makes things clear! /Stefan On Tue, Jul 3, 2012 at 11:33 PM, Ludovic Courtès l...@gnu.org wrote: Hey! Stefan Israelsson Tampe stefan.ita...@gmail.com skribis: Stefan Israelsson Tampe stefan.ita...@gmail.com skribis: Maybe this help to see what I'm after, #'(let ((x v)) #.(f #'x)) = (let-syntax ((g (lambda (stx) (syntax-case stx ((_ x) (f #'x) #'(let ((x v)) (g x)) [...] If you want to try another path using functions in stead of macros and working hard with #, and #,@ you will for complex macros like a matcher need to gensym by hand or destroy the readability of the code. As illustrated by the simple example above. Hmm, the example above does not use gensym. What am I missing? Ludo’.
Re: Enhancement to the syntax system?
Funny, for guile I get, scheme@(guile-user) (define (f x) #`(let ((x 1)) #,x)) scheme@(guile-user) (define-syntax m (lambda (x) (syntax-case x () ((_) #`(let ((x 2)) #,(f #'x)) scheme@(guile-user) (m) $1 = 1 I ported the racket matcher to guile and worked in that environment, so this illustrate the problem. In racket the same idea will error out as you say (I did not find anything wrong with your example). I do prefer the racket behavior of bailing out because it can help detecting the bug in stead of silently behave against the intention for newbies. My original code where this issue comes from is located in compat/racket/match/match.scm in the syntax-parse repo at https://gitorious.org/guile-syntax-parse/guile-syntax-parse This is the racket matcher implemented using syntax-parse! These bugs should have been corrected though in that code! /Stefan On Wed, Jul 4, 2012 at 9:47 AM, Marijn hk...@gentoo.org wrote: -BEGIN PGP SIGNED MESSAGE- Hash: SHA1 Hi Stefan, On 03-07-12 23:52, Stefan Israelsson Tampe wrote: You do not need gensyms if you try to mimic or implement my suggested #. . On the other hand when if you do this (define (f stx) #`(let ((x 1)) #,stx)) and use this with #`(let ((x 2)) #,(f #'x)) the resulting expanded code would produce 1 which is not what you want. I tried it in Racket: (define-for-syntax (f stx) #`(let ((x 1)) #,stx)) (define-syntax (m stx) (syntax-case stx () ((_) #`(let ((x 2)) #,(f #'x))) )) (m) but I get error messages which I don't know what to do about. Do you have running examples of code not producing the result you want? Marijn -BEGIN PGP SIGNATURE- Version: GnuPG v2.0.19 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAk/z9PsACgkQp/VmCx0OL2xMNACbBJKq9nZJKTzCJbdnq0iPgJoE rSwAn2yJ1JTLMUn6v5ZR/PatxcGxgVrU =HFFX -END PGP SIGNATURE-
Re: A vm for native code in guile
Hi, Branching now works and a big enough subset of the VM is translatable for some interesting benchmarks to be done. So by skipping the goto structure a the win is maybe 3-4x for simple numerical loops. I do expect these loop ta be another factor of 2 when the wip-rtl is translated in the same way. The reason is that the overhead mainly consists of the instructions that move things to and from the cache and rtl seams to decrease the number of such operations. I've been incrementing fixnums and walked some through lists of size 1 to measure these numbers. One thing to note with that code are that it piggy-packs onto the C-stack and is not working with it's own. I bet that is not optimal but that's what I did and it should mean that it's fast to switch to C-code from the native compiled or jit compiled ones. Have fun! /Stefan
Re: Enhancement to the syntax system?
I did miss something when trying in racket, it's a psyntax bug!
Look!
racket:
(define-for-syntax (f x) #`(let ((x 1)) #,x))
(define-syntax (g x) (syntax-case x ()((_ y) #`(let ((x y)) #,(f #'x
)
(g 4)
4
In guile,
scheme@(guile-user) (define (f x) #`(let ((x 1)) #,x))
scheme@(guile-user) (define-syntax g (lambda (x) (syntax-case x () ((_ y)
#`(let ((x y)) #,(f #'x))
scheme@(guile-user) (g 4)
$1 = 1
!
I much prefer rackets version here. I will file a bug report and also try
to understand what spec that racket is following!
On Tue, Jul 10, 2012 at 10:24 AM, Ludovic Courtès l...@gnu.org wrote:
Hi!
Stefan Israelsson Tampe stefan.ita...@gmail.com skribis:
| It’s true that it’s annoying that the wrong binding is silently used.
| Do you think it’s common enough to justify new syntax?
Yes this highlights a comon problem when implementing racket match with
#`.
Sure, but it’s not good-style. ;-) In general, ‘syntax-case’ is great,
but it’s low-level plumbing to be used with care, compared to
‘syntax-rules’.
I do think
that the best solution is to somehow extend the syntax expander to mimic
my
sugested
#. and #.@. The simple solution is to rewrite according to
#`(... #.((x y) (f #'x #'y)))
-
#`(let-syntax ((g (lambda (x) (syntax-case x () ((_ x y) (f #'x #'y))
(... (g x y))
Unlike syntax-{quote,unquote,...}, #. has no non-syntax-prefixed
equivalent. And what it does is non-trivial. So I don’t feel
comfortable with this extension, FWIW.
[...]
I also feel that the issue needs to be
liffted up to the
community of at least syntax-case user crowd before doing anything Ill
try
to spur
some discussions on it and come back later!
Yes, this should be discussed on c.l.s or scheme-reports.
Thanks,
Ludo’.
Re: [racket-dev] Enhancement to the syntax system?
samth made a pointer to http://srfi.schemers.org/srfi-72/srfi-72.html It does not look like guile racket etc. have implemented this yet. Am I wrong? This is precisely what I'm after! On Tue, Jul 10, 2012 at 5:26 PM, Ludovic Courtès l...@gnu.org wrote: Hi, Matthew Flatt mfl...@cs.utah.edu skribis: It's natural --- but not correct --- to think that #` is responsible for hygiene, in which case `(f #'x)' should keep the given `x' separate from the `let'-bound `x' in the result. [...] If you change the example to #lang racket (begin-for-syntax (define-syntax-rule (f body) #`(let ([x 1]) body))) (define-syntax (m stx) (with-syntax ([zz (f x)]) #`(let ([x 2]) zz))) (m) so that `f' is used as a macro instead of a function, then you get 2, since the macro-expansion of `(f x)' keeps the `x's separate. Interesting. Thanks for the clarification and examples. Ludo’.
srfi-72
Hi, I have thought about what abstraction is needed to be supported by psyntax in order to implement srfi-72. Consider macro expansion of code #'C, ideally we would like to write the expansion as E#'C with E an expansion operator. For two expansion operators E,F we would expect to support this E(F(#'C)) = (E o F)#'C eg it's possible to compose expansion operators. I also expect an identity expansion I as the expansion in the current module. Assume that #'C1 ... is embeded in lower level code. The feature we are searching for is the following lambda (/. E (E I code(#'C1 ...))) Now E does not touch the lower level code part it is only a syntax expansion for the higher order syntax #'C, on the other hand I expands in the lower level. and one would expect via with-syntax that expansion rules for the higher level is build up to Q1 ... so that we could compile to (/. E code(EQ1#'C1 ...)) and we could drop the lambda into the syntax expression and be viewed as a anonymous macro. This will probably be a kind of lambda in reality possible marked to make sure non macro lambdas get expanded. when the expander sees the lambda it will call the lambda with expansion parameters so that in the end it will work on a new syntax object eg. it will expand like E#'D( (EQ1)C1 ...). To note is that if we used the old semantic of #`, #, etc. we would end up with E#'D( Q1C1 ...) in stead which is not that nice. what do we have (/. E ) - an in syntax embeded lambda EQ1#'C1 - (f Q1#'C1 E) - f is a function that takes a syntax object and join another syntax operator marking??- dunno syntax objects with embedded lambdas go files - dunno So the question is could we cook something like this up with the current psyntax system? /Stefan
Re: wip-rtl return location
Hi interesting thoughts Mark, The below refere to to (very) simplistic vm compiler I'm working on right now. The current overhead found in function call's, function setup and function return means that it's hard to factor in the lowest level of optimizations. I view the call overhead so large that function call's is dispatched to gosub routines and not inlined. E.g. it is very close in spirit to a VM call. On the other hand the compiler can be improved and and some point in the future function call's might be so fast (especially for functions where we can prove features) so that your ideas can be a real boon. I will try to do my best though to implement some of your ideas at a second rewrite of the compiler. but at the first step I care to make sure to inline for example + - ash etc. so that they are fast on fixnums, that the branching is done natively list processing is fast and a large enough set of translations of VM operations is ready so that we can translate most of the code in guile. This can increase the speed at the first step with a factor of maybe 3-5. We can then continue to work from there. I would also like to say that the current rtl call overhead is less then the old stable-2.0 versions so plain rtl VM will be faster in this respect. Also to note is that, by the nature of the new VM, a simple compilation might yield less of an advantage then the stable-2.0 VM. The reason is that it looks like many operations in the RTL VM does more things per operations - a boon for it's speed because those things will mean that we don't gain as much on a native compilation of the RTL VM as of the stable-2.0 VM. A though: assert_nargs_ee reserve_locals assert_nargs_ee_locals bind_rest bind_kwargs Could we not implement this logic in the call instructions? /Stefan On Fri, Aug 3, 2012 at 4:29 AM, Mark H Weaver m...@netris.org wrote: Hi Andy, thanks for the update! Exciting times for Guile :) On 08/02/2012 10:29 AM, Andy Wingo wrote: Instead I'd rather just use Dybvig's suggestion: every call instruction is preceded by an MV return address. For e.g. (values (f)), calling `f' would be: ... goto CALL MVRA: truncate-and-jump RA CALL: call f RA: return So the overhead of multiple values in the normal single-value case is one jump per call. When we do native compilation, this cost will be negligible. OTOH for MV returns, we return to a different address than the one on the stack, which will cause a branch misprediction (google return stack buffers for more info). I wonder if it might be better to avoid this branch misprediction by always returning to the same address. Upon return, a special register would contain N-1, where N is the number of return values. The first few return values would also be stored in registers (hopefully at least two), and if necessary the remaining values would be stored elsewhere, perhaps on the stack or in a list or vector pointed to by another register. In the common case where a given call site expects a small constant number of return values, the compiler could emit a statically-predicted conditional branch to verify that N-1 is the expected value (usually zero), and then generate code that expects to find the return values in the appropriate registers. On some architectures, it might also make sense for the callee to set the processor's zero? condition code as if N-1 had been tested, to allow for a shorter check in the common single-value case. Of course, the calling convention can be chosen independently for each instruction set architecture / ABI. What do you think? Mark
Re: wip-rtl return location
in the normal case you just have assert-nargs-ee/locals which is very cheap, no? Sure it's not the slowest of instructions, but in the VM it's an extra jump and for the Native part it either bloats the code or one has to jump out to supporting code subs in the VM. Considering the other call overhead it's maybe a non issue but I think we should time current setup with a version where we grovel the callee information from the program datastructure. /Stefan On Fri, Aug 3, 2012 at 2:38 PM, Andy Wingo wi...@pobox.com wrote: On Fri 03 Aug 2012 13:54, Stefan Israelsson Tampe stefan.ita...@gmail.com writes: A though: assert_nargs_ee reserve_locals assert_nargs_ee_locals bind_rest bind_kwargs Could we not implement this logic in the call instructions? This is a characteristic of the callee -- more work is needed if there are optional/kw args, but in the normal case you just have assert-nargs-ee/locals which is very cheap, no? Andy -- http://wingolog.org/
wip-rtl native closure creation
Hi, I was thinking how to mix rtl-VM and native compilation with respect to closure creation currently in the code we layout the program as ((nfree :16 | flags:8 | ?:7 | tag:0), code, freevar1 ) Then at closure creation we just set first slot, the code to point to a relative adress relative ip e.g. we just need 24 bits, and finally the free-vars is handled. The thing to think of here is how to introduce a reference to native code, if we add an extra slot in the program data structure as currently down in the old program (not rtl programs) definition, then we must do some heavy magic to map vm-code to native code. Probably it is best to have the first qword / dword in the code to be 0 or the native adress e.g. I propose to add that feature to the rtl-branch. /Stefan
Re: wip-rtl native closure creation
Hi, When code is both VM and native it's nice to be able to have both code blocks as a unit because then we can freely compile a function without needing to do graph analysis. It simply makes the life easier to maintain the two setups. And incrementally compile to native on a per uses base and not in one go very much like JIT ing. Also the overhead on the VM side is low but the native execution will of cause be a little bit slower because of an extra indirection. I don't expect the slowdown to be too bad though. Perhaps we could mark the beginning of a code block in a program as 0 - the rest of the vector is VM code 1 - the rest of the vector is Native code addr - there is native code at the addr indirection Then we can skip the expensive extra inderection for native code when suitable. To note here I assume that picking a[0],a[1] is less expensive then a[0],*a[0]. At some stage we may leave the VM and perhaps enter into a Native only mode. Then we can restructure. /Stefan On Mon, Aug 6, 2012 at 11:32 AM, Andy Wingo wi...@pobox.com wrote: On Sun 05 Aug 2012 17:19, Stefan Israelsson Tampe stefan.ita...@gmail.com writes: Probably it is best to have the first qword / dword in the code to be 0 or the native adress e.g. I propose to add that feature to the rtl-branch. Good question! Given the different tradeoffs, that seems workable. Another possibility would be to use a different TC7 for native procedures. After all, the only calls we need to make cheaply are native-native and bytecode-bytecode, and the rest can go through a general dispatch loop (possibly with inline caching). WDYT? (Also note that RTL words are 32 bits wide, which may or may not be sufficient for native code pointers.) Andy -- http://wingolog.org/
wip-rtl native patch
Hi, DO you think that this will do as an initial patch to wip-rtl in order to introduce the possibility to execute native code or JIT:ed code. We reserve the first two indexes in the ip text area to fit a pointer to native code to be executed. There is changes to two parts of the code 1. module/system/vm/rtl.scm, we wrap the make-asm record constructor to initiate the first two slots to 0 and advance the index pointer. 2. We add code in libguile/cm-engine.c rtl function execution stubs to include a check for 0 at the initial two/one positions in ip. depending on architecture this will lead to a nonzero value in the case native code should be executed. Currently the code will abort if the head is nonzero but this will change of cause as we introduce more code. When the head is zero the ip is incremented two steps and the code executes as usual. A cavet could be if writing compiled code out to disk is done lately when native code have been compiled in. In this case we should clean the native part (In the jit case). I did not find where the code that does this is located so I left it open for now. /Stefan native-wip-rtl.diff Description: Binary data
overhead of soem accessors
Hi! I was looking at the code for bytevector-ref, vector-ref, struct-ref and it's pretty conclusive that there is a hugh overhead of implementing those. We are talking of 30-40 instructions that has to be put into native code. Now most of this code is working with registers so it's not that bad. But The code size will be hugh for vector oriented and struct oriented code. On the other hand the call overhead will not be that large compared to all those instructions so we could simply use the C corresponding C-functions directly. What's interesting though for a more elaborate native translation is if the compiler (or the user demands it) for unsafe versions of these accessors (I saw that we have class-of as a dengerous version of struct-ref). The idea here would be to add similar unsafe instructions for later use. They will then most certainly lead to a very efficient execution of many algorithms in guile. Regards Stefan
wip-rtl extra space at allocation of frame at call's
Hi, Currently if we want to compile to native code in the rtl branch the call instruction is very heave to inline directly. I would like to, when the number of arguments is less then 20 arguments jump to global code segment where all the nessesary heavy lifting is done. Else the whole call instruction can go in. So the issue here is that I would like to move the alloc-frame part of the call instruction out to the general code and simply just add the argumet's to their place and then jump to this global code. The problem is that we need to check the stack space before jumping and this checking is quite wordy and I would like to keep the size if the inlined code small. Therefore I suggest that always when we allocate stack space we take out 20 extra slots in the check, meaning that we do not need to check for these slot's when the call. At least that's what I plan to do in the native compilation. Any other ideas? /Stefan
wip-rtl: nargs logic in call/values op looks weird
Hi, In wip-rtl vm-engine.c around line 1047 in opcode call/values tehre seams to be some strangeities with the use of the nargs variable in, SCM_FRAME_SET_DYNAMIC_LINK (fp, old_fp); SCM_FRAME_SET_RTL_MV_RETURN_ADDRESS (fp, ip + 2 + nargs); SCM_FRAME_SET_RTL_RETURN_ADDRESS (fp, ip + 3 + nargs); fp[-1] = old_fp[proc]; nargs = vp-sp - fp; I supposed that the first two uses of nargs should be removed! /Stefan
Re: Extensible vm ops?
Hi, I have now implemented most of the rtl oops and in the phase where i am testing the ops so that all generate assembler .e.g. generate not run, I will run them later. I have a few problems usng the rtl codebase, namely I don't know how to tell the program where the rtl bytecode ends, I would expect wingo to clear this up in a few weeks and for now I can manualy tune this for the compilation to native code. For the question of having a possibility to extend the byte-code or native instruction generation I would like to implement something like SBCL and CMUCL's VOP, e.g. a virtual instructions that can be translated to machine code. I think that we can copy that interface. Anyway one important feature of these virtual instructions are that they will need to specify the register usage in order for guile at a later stage be able to store data in cpu registers. Thinking about this one thing that make things harder is that in many instructions we have fast paths for e.g. fixnums and a backup plan using a C function call. Now that means that we loose the control over registers which may be clobbered by the C-function. One way to solve this is to jump to common code for dispatching to C call's e.g. we have a few call stubs where a set of registers are pushed ontop of the stack before the call and then pushed back at the end of the call. This can work but it will make the slow path slower. I would still vote for such a feature if and when we will be able to make reasonable efficient use of cpu registers across instructions. Regards Stefan On Thu, Aug 9, 2012 at 9:07 AM, Tristan Colgate tcolg...@gmail.com wrote: Hi All, Is it possible, or practical, to support addition of VM ops to the VM dynamically? The only use case I am really thinking of is for adding SIMD based functions for operations on uniform numeric vectors. I realise I could just take all the funky maths and add it in a C extension, but then I'm calling out to C, have an extra function call and all that entails. Providing a bunch of hard coded SIMD based vector ops might well be good enough, but I thought a more general solution might be sexier. I've no idea how such a thing might look though. -- Tristan Colgate-McFarlane You can get all your daily vitamins from 52 pints of guiness, and a glass of milk
Re: Ang.: Will guile support R7RS terminating equal? in the presence of cycle?
Typed Guile? Did I miss something? :-) https://gitorious.org/typed-guile It's a type system implemented using guile-log! By the way, I do not think the overhead is that dramatic. I guess that guile's equal would be any slower with this feature added. you typically does a circularity check via a hare/turtouse pair and when circularity is found one adress the issue in some way, what might be needed now is to hook into this code and make sure that rnr7 logic is implemented for that one version. /Stefan On Sat, Sep 1, 2012 at 7:26 PM, Ludovic Courtès l...@gnu.org wrote: Hi Stefan! stefan.ita...@gmail.com stefan.ita...@gmail.com skribis: 1 I don't think the current equal? Will need to change, but Another one that under rnr7 will be coded and used with the Symbol equal? In that module. Hence no problems. Yes, of course. 2 The guile hackers are able enough to implement it. In typed-guile there is an implementation that does unification on circular lists and Also there is probably enough reference information to code this in due time. Typed Guile? Did I miss something? :-) Ludo’.
rtl - native
Hi all, The rtl native environment is close to a usable state for linux x86-64. Most instructions have been translated to assembler and it remains to debug them and write test cases which will take some time. Consider the simple code, (define (f n) (let loop ((n n) (s 0)) (if (eq? n 0) s (loop (- n 1) (+ n s) for n = 100 000 000 I get old vm,2.74s 5x rtl vm , 1.43s 3x rtl,native, 0.54s 1x - One can do better but then we must make sure to use the cpu registers and not memory based registers. I would expect a direct C loop to be less then 0.1s. /Stefan
Re: Will guile support R7RS terminating equal? in the presence of cycle?
The cycle detection for a tree would probably look something like,
SCM scm_equal_cons(SCM x, SCM y, SCM slow, int move)
{
SCM res;
if(scm_is_pair? (x) scm_is_pair (y))
{
if(scm_is_eq (x, slow)) cycle_detection_hit();
if(move)
if(scm_is_pair? (SCM_CAR (slow)))
slow = scm_cons(SCM_CAAR (slow),
scm_cons(SCM_CDAR (slow), SCM_CDR (slow)));
else
slow = SCM_CDR (slow);
ccx
res = scm_equal_cons (SCM_CAR(x), SCM_CAR(y), slow, !move);
if(scm_is_false (res)) return SCM_BOOL_T;
res = scm_equal_cons (SCM_CDR (x), SCM_CDR (y), slow, !move);
}
}
Although it probably works there will be a lot of consing being done
slowing the algorithm, as said.
So I take back what I said earlier with tree cycle code added equal will be
slower.
/Stefan
On Sun, Sep 2, 2012 at 5:17 PM, David A. Wheeler dwhee...@dwheeler.comwrote:
I said:
I'd really like for there to be a common spec for Scheme with
libraries, etc., and my hope is that R7RS will be that spec.
Ian Price:
Call me a cynic, but if r6rs couldn't do that, then I don't see how r7rs
could be given that it actively avoids many important portability
questions.
Well, the cynics are often right :-). But I think R7RS is intentionally
much more conservative and R5RS-like. In particular, it's *supposed* to be
easy for an R5RS implementation to move to R7RS. If it's easier to adopt,
it's more likely to be adopted.
Scheme is rediculously non-portable due to its lack of a *standard*
library system. If a standard for *that* could be widely adopted, many
other portability problems would be drastically reduced.
But we all can dream...
Indeed!
--- David A. Wheeler
Re: Will guile support R7RS terminating equal? in the presence of cycle?
No I wanted to say that you create a linearisation of the search and apply tourtouse hare on that. One can make that linearisation fast for list traversals but expensive for deep trees. To note here is that if we had one bit to spare for every cons representation we could do use that bit to mark conses as been touched and abort the ordinary equal if we find a mark. For x86-64 we have one such bit available which is cool. My sugestion is to implemen those two versions and we well then not see a performans degradation unless on 32bit platforms with treelike structures Stefan Den 3 sep 2012 00:08 skrev Ludovic Courtès l...@gnu.org: Hi, Stefan Israelsson Tampe stefan.ita...@gmail.com skribis: The cycle detection for a tree would probably look something like, Tortoise-and-hare would have to be applied to arbitrary data structures, AIUI. Ludo’.
Re: Will guile support R7RS terminating equal? in the presence of cycle?
I actually implemented an algorithm to handle infinite trees that we could use if we like. Enjoy! On Mon, Sep 3, 2012 at 12:07 AM, Ludovic Courtès l...@gnu.org wrote: Hi, Stefan Israelsson Tampe stefan.ita...@gmail.com skribis: The cycle detection for a tree would probably look something like, Tortoise-and-hare would have to be applied to arbitrary data structures, AIUI. Ludo’. cycle.scm Description: Binary data
things are eq? but not generated at the same time
Hi, I found that this optimization can lead to dangerous bugs. If I put, (define a #(1)) (define b #(1)) , load the file. Then (eq? a b) #t Is this an optimization we need. I can figure out applications where you do not want this behavior e.g. I wan't to make distinct objects and add metadata by making a vector of it. Now different objects might have the same metadata and now go against my intuition and coerce the objects. I fear that many difficult to spot bugs will come out of this design choice! /Stefan
Re: things are eq? but not generated at the same time
Yes, I can agree om that. But this should be very stated clearly and perhaps added to a pitfall's section. /Stefan On Wed, Sep 5, 2012 at 9:13 PM, Ian Price ianpric...@googlemail.com wrote: Stefan Israelsson Tampe stefan.ita...@gmail.com writes: Is this an optimization we need. I can figure out applications where you do not want this behavior e.g. I wan't to make distinct objects and add metadata by making a vector of it. Now different objects might have the same metadata and now go against my intuition and coerce the objects. I'm not sure I understand what you are trying to say, make vector of what, the distinct objects? Then you can't do that as a vector literal anyway. Anyway if vectors are immutable, as I believe they are, it doesn't really harm to make them eq? If you want distinctness and mutability, you can always call the vector constructor. -- Ian Price -- shift-reset.com Programming is like pinball. The reward for doing it well is the opportunity to do it again - from The Wizardy Compiled
wip-rtl, non-immediate constants like lists and arrays does not have a 64bit aligned address!
Hi, I was a bit surprised when I coded the native versions of rtl-sinstruction, make-non-immediate I just assumed that alignement meant 64bit on 64bit platforms. It doesen't in for example, (define const (assemble-program `((begin-program test-bind-rest) (assert-nargs-ee/locals 0 2) (load-constant 0 '(1 2)) (load-constant 1 #(1)) (cons 0 0 1) (return 0) (end-program -- ??dissassembles into ;;; ((assert-nargs-ee/locals (op : 20) (expected : 0) (nlocals : 2))) ;;; ((inst)) ;;; ((make-non-immediate (op : 52) (dst : 0) (offset : -7) (ip : 20677408))) ;;; ((inst)) ;;; ((make-non-immediate (op : 52) (dst : 1) (offset : -31) (ip : 20677320))) ;;; ((inst)) ;;; ((cons (op : 74) (dst : 0) (x : 0) (y : 1))) ;;; ((inst)) ;;; ((return (op : 5) (src : 0))) And we see that 20677320 8 == 8, hence not 64 bit aligned. Assuming alignment meant 32bit the native code works very well! But would I dear to suggest that we try to keep all non immediates aligned on 64bit boundaries? /Stefan
Re: Will guile support R7RS terminating equal? in the presence of cycle?
You are right! That will only work for one thread! Remain to see how much the overhed there is to linearize the search and use tourtoues - hare, should be much less overhead then using a map to mark the objects though! /Stefan On Sat, Sep 8, 2012 at 6:56 PM, Mark H Weaver m...@netris.org wrote: On 09/03/2012 09:55 AM, Stefan Israelsson Tampe wrote: To note here is that if we had one bit to spare for every cons representation we could do use that bit to mark conses as been touched and abort the ordinary equal if we find a mark. For x86-64 we have one such bit available which is cool. This trick of mutating bits in the conses fails badly in case of multiple threads, therefore we cannot use it. Mark
Re: Will guile support R7RS terminating equal? in the presence of cycle?
There is another interesting option that uses a hash to mark objects. Keep a counter and for each new object check the counter, if it's 0 then check to see if the object have been visited before else register it! then initiate the counter with (random N) elements. If N equals 10 in guile scheme, then equal-with-cycle-detection is about twice as slow as an ordinary equal? on two equal? 1000 times long list. The drawback is that for cyclic structures you get a positive probability to wait for a very long time but typically the expected waiting time should be less then (N / 2) ** 2 = 25 in my test case. By increasing the N you will cause less overhead on the normal behavior but increase the cost for structures with cycles. Anything unsound with this approach? /Stefan On Sun, Sep 9, 2012 at 3:35 AM, Alex Shinn alexsh...@gmail.com wrote: On Sun, Sep 9, 2012 at 2:00 AM, Stefan Israelsson Tampe stefan.ita...@gmail.com wrote: You are right! That will only work for one thread! Remain to see how much the overhed there is to linearize the search and use tourtoues - hare, should be much less overhead then using a map to mark the objects though! See http://srfi.schemers.org/srfi-85/srfi-85.html for a common implementation approach. The basic idea there is just to run equal? normally, but keep a counter of how many objects have been compared. If the count gets too high, there is a decent chance you have a cycle, and only then do you switch to a more expensive approach. You could of course use a modified hare and tortoise with the same goal of just detecting when a cycle has occurred and switching algorithms. You only need to do this on one of the data structures, since if either is non-cyclic equal? will terminate naturally. This would be slightly more overhead than a counter, and probably require heap allocation to keep the search path in memory, but it removes the need to choose a good limit. Small cycles will still be detected right away, and very long straight lists won't switch to the expensive algorithm. I think trying to use two hares and two tortoises to compare directly without a fallback algorithm would be very harey. -- Alex
typed-guile
Hi all, I've been reworking my little type-checking library built on guile-log. It now works on some pretty recent guile-2.0 repo and a recent guile-log. It has subtypes it has recursive types allow for or and and not in the spec for the type. You can check it out at https://gitorious.org/typed-guile To see how it works consider to take a look at example.scm It's not as featurefull as typed-racket but has been a great testbed for guile-log. Have fun Stefan
compile-rtl
Hi, I'm right now trying to port compile-glil to compile-rtl and I would say that what's hindering me is what design choices to take? 1. The main problem is that we do not have a stack pointer the same way as before. Of cause we still need to store temporary values and we will simply have to use predefined local register indices, that's not hard to implement though. The problem is that we will have memory not cleared that's not going to be GC:ed until the frame is changed. This will cause some potential memory leaks. To let it be as it is designed right now, will mean that it is very difficult looking at the scheme code to see what will be protected from gc or not. And I fear that we will need to handle this in some smart way. The solutions are either, keep a stack pointer in a register and updated it for each push and pop as before. Or do what we do after let forms, clear the variable slots - expensive! What I think is that we need to have the equivalent of a stack pointer in order to properly handle gc'ing. We could still have a register approach and gain quite some speed bump (2x) from using direct addressing in stead of using the middle layer of the stack for everything. My vote is introduce a register sp again! 2. Now when we are tail-calling in rtl, we just fill the argument slots with the new function arguments directly and then tail-call by filling in number of arguments and function. This is very smart and just some simple features added would mean that a lot of translation from one memory location to the other is skipped. I really like how the rtl code handle this but there is an expense. It complicates life a little when we overwrite arguments that are used in the calculation of other arguments. I'm working on how to handle this but I just wanted to point out how nice this design choice is. 3. call's, here currently we send a list of register positions to the call function and the call function itself will copy those to the argument fields. This is the opposite of the tail-call, in a case like (f 1 3) you will create two temporary variables and copy them later on to the argument position. Here I would like to change the semantic so that we fill in the arguments directly just like in the tail-call. Also, I would like to use the end of the stack region to compute the function frame. Well even if we use the end of the full frame we will save one move per argument which is nice. 4. Return values. We talked about this before and there is some concerns how to make this fast. I would like to skip the complication by simply put the return values in the argument positions to the function. Also the number of arguments is mediated to the reciever. I would like to skip the mv-return slot and add a rmove function like, (call pos proc) (rmove pos (i ...)) And it is rmove's responsibility to move the arguments to it's return positions, also it's possible for functions calling functions to just clear the function slot and keep the values for later use by simply increasing the stack to contain the return value(s). this means that we can keep the copying to the minimal (which is one of the big costs). Also keeping it this way lead to quite some smooth handling of code that evaluates a function on the return values, one just need to fill in the function and return ip and evaluate. cool. The downside is for native code where we may transfer things back in computer registers. But the overhead of function call's are of such dignity that the copying of one value is not of importance even for natively compiled functions, The upfront cost of handling functions is pretty high. Note that the improvement's that I suggest have two properties, 1. they are composable, 2. they scale well in the number of arguments and return values. My feeling is that speed bumps due to function overhead can be adressed by a) Inlining b) A well designed interface of user defined instructions c) Develop separate function call mechanisms that a compiler can deduce and use. WDYT /Stefan
Re: More RTL Tests
On Sun, Oct 14, 2012 at 9:59 PM, Noah Lavine noah.b.lav...@gmail.comwrote: Hello, I have been working on understanding RTL, and I wrote the following tests. They're mostly to illustrate for myself how calling works in RTL, but they also serve to test it. Any objections if I commit them as part of rtl.test? (with-test-prefix call (assert-equal 42 (let ((call ;; (lambda (x) (x)) (assemble-program '((begin-program call) (assert-nargs-ee/locals 1 0) (call 1 0 ()) (return 1) ;; MVRA from call (return 1) ;; RA from call (call (lambda () 42 (assert-equal 6 (let ((call-with-3 ;; (lambda (x) (x 3)) (assemble-program '((begin-program call-with-3) (assert-nargs-ee/locals 1 1) (load-constant 1 3) (call 2 0 (1)) (return 2) ;; MVRA from call (return 2) ;; RA from call (call-with-3 (lambda (x) (* x 2)) (with-test-prefix tail-call (assert-equal 3 (let ((call ;; (lambda (x) (x)) (assemble-program '((begin-program call) (assert-nargs-ee/locals 1 0) (tail-call 0 0) (call (lambda () 3 (assert-equal 6 (let ((call-with-3 ;; (lambda (x) (x 3)) (assemble-program '((begin-program call-with-3) (assert-nargs-ee/locals 1 1) (mov 1 0) ;; R1 - R0 (load-constant 0 3) ;; R0 - 3 (tail-call 1 1) (call-with-3 (lambda (x) (* x 2)) This look good to me My next goal is to learn to reference top-level variables. Could anyone tell me how that works, to make it easier? The general way, use a symbol in loc a and a module in loc b and then issue (resolve c b a) (box-ref c c) To put the symbol into c. The simplest way to check this is to pass b and a as arguments to the funciton, you may set the toplevel by using box-set! For reference inside functions you may use (toplevel-ref dst var_label mod_label sym_label) This is a bit complicated and I havenot found that all the infrastructure is in place to handle this but basically one should need to prepare the code like this if I'm not missing anything (program f) (toplevel-ref 1 var mod sym) ... (label var) (store-slot SCM_BOOL_F) (label mod) (store-slot module) (label sym) (stire-slot 'symbol) where the stire-slot mechanism is not yet supported but should mean that aligned to SCM it stores the needed references. This is what I guess it all means, correct me if i'm wrong! /Stefan
Re: Fixing the slib mess
Hi Mikael and welcome back! *But*, the proper implementation of syntax-toplevel? requires modification of psyntax.scm and adding it to the (system syntax) module. I didn't want to do this until I've had your comments, so the present patch has its own syntax-object accessors (which breaks abstraction and is therefore not a real solution). I should also say that I have not yet fixed the slib interface to the new Guile uniform arrays, so there's a lot of slib functionality which won't yet work. Comments? Can I add syntax-toplevel? to psyntax.scm and (system syntax)? Do you think it is reasonable to submit something along the line of guile.init.diff to slib guile.init? Best regards, Mikael Djurfeldt I can answer with some kind of suggestion here. in (system syntax) there is syntax-local-binding which you can use for example as (define-syntax f (lambda (x) (syntax-case x () ((_ x) (call-with-values (lambda () (syntax-local-binding #'x)) (lambda (x y) (pk x) (pk y))) #'#t Then, scheme@(guile-user) [1] (f +) ;;; (global) ;;; ((+ guile-user)) And, scheme@(guile-user) [1] (let ((s 1)) (f s)) ;;; (lexical) ;;; (s-490) (let ((s 1)) (define-syntax g (lambda (x) #'#f)) (f g)) ;;; (displaced-lexical) ;;; (#f) I'm not sure what exactly syntax-toplevel? does, but can you base it on syntax-local-binding? And if not is it possible to change syntax-local-binding so that you can use it? Regards Stefan
Re: Fixing the slib mess
Yes in that case this stands on it's own! /Stefan On Mon, Oct 22, 2012 at 9:11 PM, Mikael Djurfeldt mik...@djurfeldt.comwrote: On Mon, Oct 22, 2012 at 8:31 PM, Stefan Israelsson Tampe stefan.ita...@gmail.com wrote: Comments? Can I add syntax-toplevel? to psyntax.scm and (system syntax)? [...] I can answer with some kind of suggestion here. in (system syntax) there is syntax-local-binding which you can use for example as (define-syntax f (lambda (x) (syntax-case x () ((_ x) (call-with-values (lambda () (syntax-local-binding #'x)) (lambda (x y) (pk x) (pk y))) #'#t Then, scheme@(guile-user) [1] (f +) ;;; (global) ;;; ((+ guile-user)) And, scheme@(guile-user) [1] (let ((s 1)) (f s)) ;;; (lexical) ;;; (s-490) (let ((s 1)) (define-syntax g (lambda (x) #'#f)) (f g)) ;;; (displaced-lexical) ;;; (#f) I'm not sure what exactly syntax-toplevel? does, but can you base it on syntax-local-binding? And if not is it possible to change syntax-local-binding so that you can use it? Thanks, Stefan. (syntax-toplevel?) expands to #t if occurs in a context (position in the code if you prefer) where a (define x #f) would create/set! a global binding for x. It expands to #f otherwise. I had a look at syntax-local-binding, but decided that syntax-toplevel? was needed since the latter is not trying to determine the nature of an existing binding but rather the nature of the context. Of course oncould probe the context by first creating a new binding (with some random name) and then use syntax-local-binding to determine the nature of the context by looking at the new binding, but that seems somewhat invasive. :-)
progress
Hi, OK, the last progress for the rtl compilation is make it work to something as close as the current RTL VM, I have added a few variables that can control the kind of compilation strategy we would like to have as an output. I can for example now do (define f ((c (lambda (x) (let loop ((s 0) (i 0)) (if (eq? i x) s (loop (+ s i) (+ i 1 ;; This will compile the following RTL Code ((begin-program program278) (assert-nargs-ee/locals 0 1) (label :LCASE273) (make-empty-closure 0 program277 0) (return 1) (end-program) (begin-program program277) (assert-nargs-ee/locals 1 2) (label :LCASE272) (br :L274) (label :LCASE271) (br-if-eq 2 0 1 :L275) (mov 0 1) (return 1) (label :L275) (add 1 1 2) (add1 2 2) (br :LCASE271) (label :L274) (load-constant 1 0) (load-constant 2 0) (br :LCASE271) (end-program)) Then we can do (define g (lambda (x) (let loop ((s 0) (i 0)) (if (eq? i x) s (loop (+ s i) (+ i 1)) And compare, ,time (g 1000) $3 = 499500 ;; 0.293595s real time, 0.290550s run time. 0.00s spent in GC. scheme@(guile-user) ,time (f 1000) $4 = 499500 ;; 0.158049s real time, 0.150505s run time. 0.00s spent in GC So it starts to live in some sense. Now I consider the compile-rtl code as a research code e.g. it can compile correctly but it's a bit of a hack to churn in the rtl functionality in the old compile-glil code. It seems to work and I have made enough tooling so that the changes are clean in some sense at the higher level. On the lower level I rest on fluids and hacks with set! to achieve what I need. Anyway the abstractions are powerful enough so that I could build several compilation strategies and mix between them, for example we could have a native startegy and vm strategy that is more optimized if we have a vm or is running native. There are a few more options as well. The idea I have is that I would like to have a fairly complete picture of how to compile to the current RTL VM and not introduce too large deviations from wingo's strategy. But instead make it work and build explore from that base. Again having something that run's before trying to tweak is a good strategy I would say. Anyway, as you see there is some progress. Cheers Stefan
Re: thoughts on native code
I would like to continue the discussion about native code. Some facts are, For example, consider this (define (f x) (let loop ((s 0) (i 0)) (if (eq? i x) s (loop (+ s i) (+ i 1) The timings for (f 1) ~ (f 100M) is 1) current vm : 2.93s 2) rtl : 1.67s 3) compressed native : 1.15s 4) uncompressed native : 0.54s sbcl = compressed nativ + better register allocations (normal optimization level) : 0.68s To note is that for this example the call overhead is close to 5ns per iteration and meaning that if we combined 4 with better register handling the potential is to get this loop to run at 0.2s which means that the loop has the potential of running 500M iterations in one second without sacrifying safety and not have a extraterestial code analyzer. Also to note is that the native code for the compressed native is smaller then the rtl code by some factor and if we could make use of registers in a better way we would end up with even less overhead. To note is that compressed native is a very simple mechanism to gain some speed and also improve on memory usage in the instruction flow, Also the assembler is very simplistic and it would not be to much hassle to port a new instruction format to that environment. Also it's probably possible to handle the complexity of the code in pure C for the stubs and by compiling them in a special way make sure they output a format that can be combined with the meta information in special registers needed to make the execution of the compiled scheme effective. This study also shows that there is a clear benefit to be able to use the computers registers, and I think this is the way you would like the system to behave in the end. sbcl does this rather nicely and we could look at their way of doing it. So, the main question now to you is how to implement the register allocations? Basic principles of register allocation can be gotten out from the internet, I'm assure of, but the problem is how to handle the interaction with the helper stubs. That is something i'm not sure of yet. A simple solution would be to assume that the native code have a set of available registers r1,...,ri and then force the compilation of the stubs to treat the just like the registers bp, sp, and bx. I'm sure that this is possible to configure in gcc. So the task for me right now is to find out more how to do this, if you have any pointers or ideas, please help out. Cheers Stefan On Sat, Nov 10, 2012 at 3:41 PM, Stefan Israelsson Tampe stefan.ita...@gmail.com wrote: Hi all, After talking with Mark Weaver about his view on native code, I have been pondering how to best model our needs. I do have a framework now that translates almost all of the rtl vm directly to native code and it do shows a speed increase of say 4x compared to runing a rtl VM. I can also generate rtl code all the way from guile scheme right now so It's pretty easy to generate test cases. The problem that Mark point out to is that we need to take care to not blow the instructuction cache. This is not seen in these simple examples but we need larger code bases to test out what is actually true. What we can note though is that I expect the size of the code to blow up with a factor of around 10 compared to the instruction feed in the rtl code. One interesting fact is that SBCL does fairly well by basically using the native instruction as the instruction flow to it's VM. For example if it can deduce that a + operation works with fixnums it simply compiles that as a function call to a general + routine e.g. it will do a long jump to the + routine, do the plus, and longjump back essentially dispatching general instructions like + * / etc, directly e.g. sbcl do have a virtual machine, it just don't to table lookup to do the dispatch, but function call's in stead. If you count longjumps this means that the number of jumps for these instructions are double that of using the original table lookup methods. But for calling functions and returning functions the number of longjumps are the same and moving local variables in place , jumping is really fast. Anyway, this method of dispatching would mean a fairly small footprint with respect to the direct assembler. Another big chunk of code that we can speedup without to much bloat in the instruction cache is the lookup of pairs, structs and arrays, the reason is that in many cases we can deduce at compilation so much that we do not need to check the type all the time but can safely lookup the needed infromation. Now is this method fast? well, looking a the sbcl code for calculating 1+ 2 + 3 + 4 , (disassembling it) I see that it do uses the mechanism above, it manages to sum 150M terms in one second, that's quite a feat for a VM with no JIT. The same with the rtl VM is 65M. Now, sbcl's compiler is quite matured and uses native registers quite well which explains one of the reasons why
Re: thoughts on native code
Hi, hope that i'm not boring you!
Ok, The next effort will be to investigate the issue of cpu register
allocations. Some features noted here is
that 1. some instruction takes vastly more resources than others and we
need to track this, I'm leaning on implementing
a version of the linear scan algorithm. This is how I think.
The first issue is that I love to relate everything to costs. So basically
if we manage to keep a local variable in a register, we would gain
something e.g. g. On the other hand during the intervall of setting and
retrieving the local variable we have performed a set of operations e.g w.
If we find that g / w is large we would decide that we would gain so much
during the interval that we should put it in a register. Or else we do not
bother putting it in a register. Now over to a branching for a branch we
split up the liveness interval in the number of segments between usages,
for such a segment over a branch we would have
[g1, w1] - { [g2,w2] , [g3,w3] }
Now generally we would like to assign some kind of probability to the
different branches and do something like
F = p * (g1 + g2) / (w1 + w2) + (1-p) * (g1 + g3) / (w1 + w3)
If we do not have any information we just put p = 1/2. The astute reader
would realize that this mean a potential
geometrical explosion in the number of terms in the sum let's try
F = g1 / w1 + p (g2 / w2) + (1 -p) (g2/w3)
Nah that's not good either, if g1 is zero we would not amortize over w1,
this leads to
g1' = (g1 + L ( p g2/w2 + (1-p) g3 / w3))
F = g1'/w1
The linear updating will be
p = 1 = g1' = g1 + w1 L* g2/w2
and
F = g1/w1 + L/w1 * g2/w2
How to select L? consider take one w2 for which we think that this
expression should be true to the more theoretically compelling e.g.
F = g1/w + g2/(w1 + w2) = g1/w + L * g2/w2
And we would then conclude to use L = w / (w1+w), and
F = g1/w1 + w / (w1 + w) * (g2 / w2)
Although i'm not certain this is the best, maybe you see a better solution,
but the nice thing is that we can build up the solution recursively if we
follows this scheme. and for code graph being a tree we could scan the tree
only ones and build
up these numbers. This method can be refined.
Anyhow we can take all usages and sum up a F for the start and move forward
at each segment for the whole liveness
of the local variable. Now do all this for all variables. Then employ a
version of the linear scan algorithm but only select a variable for
register allocation if the corresponding F is above a threshold C. Which
threshold? Well you could try to vary F, e.g. Let Q(C) = fraction of
allocated registers per unit of time. then select C so that MIN(C s.t. Q(C)
0.9).
We could refine this method to try vary C over the graph somewhat.
What do you think?
Happy Mathing!!
/Stefan
On Sat, Nov 10, 2012 at 11:06 PM, Stefan Israelsson Tampe
stefan.ita...@gmail.com wrote:
I would like to continue the discussion about native code.
Some facts are,
For example, consider this
(define (f x) (let loop ((s 0) (i 0)) (if (eq? i x) s (loop (+ s i) (+ i
1)
The timings for (f 1) ~ (f 100M) is
1) current vm : 2.93s
2) rtl : 1.67s
3) compressed native : 1.15s
4) uncompressed native : 0.54s
sbcl = compressed nativ + better register allocations (normal optimization
level) : 0.68s
To note is that for this example the call overhead is close to 5ns per
iteration and meaning that
if we combined 4 with better register handling the potential is to get
this loop to run at 0.2s which means
that the loop has the potential of running 500M iterations in one second
without sacrifying safety and not
have a extraterestial code analyzer. Also to note is that the native code
for the compressed native is smaller then the
rtl code by some factor and if we could make use of registers in a better
way we would end up with even less overhead.
To note is that compressed native is a very simple mechanism to gain some
speed and also improve on memory
usage in the instruction flow, Also the assembler is very simplistic and
it would not be to much hassle to port a new
instruction format to that environment. Also it's probably possible to
handle the complexity of the code in pure C
for the stubs and by compiling them in a special way make sure they output
a format that can be combined
with the meta information in special registers needed to make the
execution of the compiled scheme effective.
This study also shows that there is a clear benefit to be able to use the
computers registers, and I think this is the way
you would like the system to behave in the end. sbcl does this rather
nicely and we could look at their way of doing it.
So, the main question now to you is how to implement the register
allocations? Basic principles of register allocation can be gotten out from
the internet, I'm assure of, but the problem is how to handle the
interaction with the helper stubs
Re: thoughts on native code
Thanks for your mail Noah, Yea libjit is quite interesting. But playing around with an assembler in scheme I do not want to go back to C or C++ land. The only problem is that we need a GNU scheme assembler and right now I use sbcl's assembler ported to scheme. We could perhaps use weinholts assembler as well in industria if he could sign papers to make it GNU. For the register allocation part I would really like to play a little in scheme to explore the idea you saw from my previous mail in this thread. Again I think it's natural to have this features in scheme and do not want to mess in C land too much. Am I wrong? Cheers Stefan On Sat, Nov 10, 2012 at 11:49 PM, Noah Lavine noah.b.lav...@gmail.comwrote: Hello, I assume compressed native is the idea you wrote about in your last email, where we generate native code which is a sequence of function calls to VM operations. I really like that idea. As you said, it uses the instruction cache better. But it also fixes something I was worried about, which is that it's a lot of work to port an assembler to a new architecture, so we might end up not supporting many native architectures. But it seems much easier to make an assembler that only knows how to make call instructions and branches. So we could support compressed native on lots of architectures, and maybe uncompressed native only on some. If you want a quick way to do compressed native with reasonable register allocation, GNU libjit might work. I used it a couple years ago for a JIT project that we never fully implemented. I chose it over GNU Lightning specifically because it did register allocation. It implements a full assembler, not just calls, which could also be nice later. Noah On Sat, Nov 10, 2012 at 5:06 PM, Stefan Israelsson Tampe stefan.ita...@gmail.com wrote: I would like to continue the discussion about native code. Some facts are, For example, consider this (define (f x) (let loop ((s 0) (i 0)) (if (eq? i x) s (loop (+ s i) (+ i 1) The timings for (f 1) ~ (f 100M) is 1) current vm : 2.93s 2) rtl : 1.67s 3) compressed native : 1.15s 4) uncompressed native : 0.54s sbcl = compressed nativ + better register allocations (normal optimization level) : 0.68s To note is that for this example the call overhead is close to 5ns per iteration and meaning that if we combined 4 with better register handling the potential is to get this loop to run at 0.2s which means that the loop has the potential of running 500M iterations in one second without sacrifying safety and not have a extraterestial code analyzer. Also to note is that the native code for the compressed native is smaller then the rtl code by some factor and if we could make use of registers in a better way we would end up with even less overhead. To note is that compressed native is a very simple mechanism to gain some speed and also improve on memory usage in the instruction flow, Also the assembler is very simplistic and it would not be to much hassle to port a new instruction format to that environment. Also it's probably possible to handle the complexity of the code in pure C for the stubs and by compiling them in a special way make sure they output a format that can be combined with the meta information in special registers needed to make the execution of the compiled scheme effective. This study also shows that there is a clear benefit to be able to use the computers registers, and I think this is the way you would like the system to behave in the end. sbcl does this rather nicely and we could look at their way of doing it. So, the main question now to you is how to implement the register allocations? Basic principles of register allocation can be gotten out from the internet, I'm assure of, but the problem is how to handle the interaction with the helper stubs. That is something i'm not sure of yet. A simple solution would be to assume that the native code have a set of available registers r1,...,ri and then force the compilation of the stubs to treat the just like the registers bp, sp, and bx. I'm sure that this is possible to configure in gcc. So the task for me right now is to find out more how to do this, if you have any pointers or ideas, please help out. Cheers Stefan On Sat, Nov 10, 2012 at 3:41 PM, Stefan Israelsson Tampe stefan.ita...@gmail.com wrote: Hi all, After talking with Mark Weaver about his view on native code, I have been pondering how to best model our needs. I do have a framework now that translates almost all of the rtl vm directly to native code and it do shows a speed increase of say 4x compared to runing a rtl VM. I can also generate rtl code all the way from guile scheme right now so It's pretty easy to generate test cases. The problem that Mark point out to is that we need to take care to not blow the instructuction cache. This is not seen
Re: thoughts on native code
Arg, I prematurely send that mail, well here is the continuation 4. I prefere to have an evironment like (assemble target (inst jmp label:) (inst mov b a) label: (inst mov b c) This makes the labels stand out and makes for a nice read of the assembler. You can see how weinholt in industria solves the assembling issue, also MIT Scheme as an assembler that you can learn from, I was not liking the syntax of that one though, but You maybe can port that over to guile, this is GNU and may be the shortest path to success. I like the environment in the sbcl assembler, I ported that over in the aschm repo and you can see a lot of assembler in the nativ/vm/insts.scm file in that repo on gitorious. We cannot use that one due to the fact that it's not GNU although it's open source and the code is somewhat unclean. It would also be nice if we could concentrate on a restricted set of instruction support from the beginning and make sure to support more architectures instead. What do you think? /Stefan On Thu, Nov 15, 2012 at 11:19 AM, Sjoerd van Leent Privé svanle...@gmail.com wrote: Hi Stefan, Just my idea about an assembler in Scheme. Sounds interesting. If it's done properly, it can be very promising to use scheme itself to directly emit machine instructions. This would also be interesting for meta compilation in the future (think of aiding GCC). So you are thinking about an assembler for x86? Perhaps I can help out on this one. I would like to do this part, as I haven't been able to aid on other parts besides voicing my ideas (anyways, I am on embedded development these days.) The only discussion is the syntax I believe, I mean, should it be ATT like, Intel like, or leave this domain and do something new. I would go for instructions like this (using macros): (let ((target :x686)) (assemble target ((mov long 100 EAX) (mov long 200 EBX) (add long EBX EAX Giving back the native machine code instructions. Perhaps special constructions can be made to return partially complete instructions (such as missing labels or calls to guile procedures...) Sjoerd On 11/12/2012 10:50 PM, Stefan Israelsson Tampe wrote: Thanks for your mail Noah, Yea libjit is quite interesting. But playing around with an assembler in scheme I do not want to go back to C or C++ land. The only problem is that we need a GNU scheme assembler and right now I use sbcl's assembler ported to scheme. We could perhaps use weinholts assembler as well in industria if he could sign papers to make it GNU. For the register allocation part I would really like to play a little in scheme to explore the idea you saw from my previous mail in this thread. Again I think it's natural to have this features in scheme and do not want to mess in C land too much. Am I wrong? Cheers Stefan On Sat, Nov 10, 2012 at 11:49 PM, Noah Lavine noah.b.lav...@gmail.comwrote: Hello, I assume compressed native is the idea you wrote about in your last email, where we generate native code which is a sequence of function calls to VM operations. I really like that idea. As you said, it uses the instruction cache better. But it also fixes something I was worried about, which is that it's a lot of work to port an assembler to a new architecture, so we might end up not supporting many native architectures. But it seems much easier to make an assembler that only knows how to make call instructions and branches. So we could support compressed native on lots of architectures, and maybe uncompressed native only on some. If you want a quick way to do compressed native with reasonable register allocation, GNU libjit might work. I used it a couple years ago for a JIT project that we never fully implemented. I chose it over GNU Lightning specifically because it did register allocation. It implements a full assembler, not just calls, which could also be nice later. Noah On Sat, Nov 10, 2012 at 5:06 PM, Stefan Israelsson Tampe stefan.ita...@gmail.com wrote: I would like to continue the discussion about native code. Some facts are, For example, consider this (define (f x) (let loop ((s 0) (i 0)) (if (eq? i x) s (loop (+ s i) (+ i 1) The timings for (f 1) ~ (f 100M) is 1) current vm : 2.93s 2) rtl : 1.67s 3) compressed native : 1.15s 4) uncompressed native : 0.54s sbcl = compressed nativ + better register allocations (normal optimization level) : 0.68s To note is that for this example the call overhead is close to 5ns per iteration and meaning that if we combined 4 with better register handling the potential is to get this loop to run at 0.2s which means that the loop has the potential of running 500M iterations in one second without sacrifying safety and not have a extraterestial code analyzer. Also to note is that the native code for the compressed native is smaller then the rtl code
Re: thoughts on native code
Hi, Yes this is pre-work and what i'm doing is an investigation trying out things. bare that in mind :-) For the assembler it can be really good to support one that comes with guile so I do not find this work as a research work but as a service work to propose components that can be included in guile. Mark, don't you agree on that my higher level research here is experimental, but that you will need to have some kind of assembler in the end to have a sane working environment to output native code? /Stefan On Thu, Nov 15, 2012 at 6:50 PM, Mark H Weaver m...@netris.org wrote: Before anyone spends any more time on this, I want to make it clear that although I very much appreciate Stefan's pioneering spirit, and some of his ideas are likely to be incorporated, Stefan's work on native compilation is an independent project of his, and is unlikely to be merged into the official Guile. Andy and I have been planning a different approach. Mark
register allocation
Hi all, If I've not miss - understood wingo's and Marks intention for native code, there need to be a intermediate format to output from tree-il that is different from the rtl bytecode. One of the reason's for this is that one need a better format in order to do register allocations well. What I can do to quickly output examples for this language is for the compile-glil port to compile-rtl add another emit command e.-g. emit-tree where for example (lexical-ref ... ) get's an emitting of (ref I #f ) where I is an identity for the memory slot furthermore there will be a set meaning setting a variable e.g. (set I #f), and (set I reg) for sources that we can have sinks as well e.g. for function call registers e.g. typically they add a constraint on the used register (sink I reg) (sink I #f) with set! and sink we can model the constraints that are imposed by the function argument and return values or even user demanded constraints. numbers 10 15 25 is also included in the list and will represent the actual cost for doing any work * will represent an action that will clobber any register, we could add (* reg1 reg2 reg3) to refine this but this will be for later. branches e.g. condition will be represented by ((w1 code-x) (w2 code-y)) w1 is the weight for branch 1 and w2 will be the weight for branch 2, w1 + w2 = 1. with this we can make sure that register allocation can take advantage of a (unlikly pred) hint for an if as well as if we profile code we can analyze which numbers to put for w1 and w2 due to statistics about the branches, I suppose we need a phi statements or the goto that letrec and named let's will end up generating. Not sure what to do with them, but I will in the first version assume they are not imposing any constraints. If the arguments of the head of the code representing the phi is allocated in the first pass to a register that information can be used at a second pass or something like that. The fun part is that this representation is almost for free using the tree-il representation due to not having the goto you have in c++ and c. If we would like to generate this representation for such languages that include them I suspect that everything will be more costly. I think thik wingo said something along this line previusly on the net no? What I have now is an register allocator for non constrained cases. I have a plan to incorporate the constraints as well and I will probably finish that work within a week or so. So, we will then have a register allocator in scheme that can make use of constraints coming from register arguments both as caller and calle as well as return register(s). But not only this it will be able to intelligently make use of branch hints as well. Also one version will be a linear scan like algorithm, But we will be able totest out more intelligently or more stupidly (if i'm algorithms as well Again this is a lot of experimenting maybe we will use it or we don't but this module can be used separately. Have fun Stefan
Re: CPS and RTL
Hi Noha, very clean code indeed, nice work, (mine rtl compiler is much more a bit of a hack btw :-)) One thing to think about from the beginning is how to protect variables from gc and at the same time offer unreachable vars to be gc:d at an early state. In guile-2.0 we kept using a stack for e.g. the middle terms in the executions of expressions like (+ (+ x y) (+ w z)) and there the end stack pointer was updated after each primitive. This is an overhead and in the rtl code wingo's trying to remove the need for a sp register in hardware and in stead occasionally update a vp-sp value probably sitting in the memory cache. The problem with this is that now we must take care to occasionally write over memory regions in order to allow the contents therein being gc'd at an early state. This means that we must record which registers have been used between the erasing's. Now what I tried to use is that the activities for which we will need to have well defined sp is mostly quite expensive so we can allow to update it then. Then looking at instructions like (add dst argx argy) in most cases the place to put in vp-sp is the dst location, but not always, I took the path to keep a base sp memory location which we could call bsp and I stored it in vp-sp. Now when the add need to go out to the slow path, which may cons, it will check if dst is below bsp, if so it will use bsp as the sp position, else it will use dsp e.g. it will temporary set vp-sp to fp[dst]. when executing the slow path. This method will mean that we need at times set the bsp as the code flows, but it will not be many places in practice, and they will most often be out of the hot path, so I added a (set-sp pos) rtl vm-op and tried with that. In all this means that I got a very effective way of keeping track of the end of the stack with the same or better accuracy as before and it's really fast and there is no need to keep vp-sp in a hardware register. The problem is that the code base got more comlpex both in C land and in scheme and I needed to store the bsp across function call's along with fp because bsp could be pointing at somewhere other the start of the next function frame. We could solve this on the other hand by demanding the destination of a call always sit's at the end of the sp and add a mov operation after teh call if needed instead, meaning that we can save on the amount of storage needed to be done on each frame. Anyway my message here is that one need to make sure that the register allocator play's nicely with the mechanism of marking the region eligible for gc or not for gc. Another thing to look out for is the tail call's and berhaps multiple value returns, You will need to fill in the start of the frame with the at say register 0 and make sure that if it's not used later just overwrite or if it's used later move it and use that location for that's register location (actually named let is another similar activity where you do a goto back to the start but then 0 is not the start of the registers to mangle. Maybe You solved this. And one can do that by just parsing the continuation of that call to see if there is a reference to it. If one chooses that it can be ok, I choose to delay the evaluations of the actual register number to a later phase by in stead of numbers store (lambda () (+ (d) i)), where is is the number I would have chosen if there was no problem and d is a function who's value is determined later by later usages of the same variable identity. I think that this is overly complicated and would today just go after a simple scan of the continuation. I will try to comment more later. Regards Stefan On Sat, Nov 17, 2012 at 4:35 PM, Noah Lavine noah.b.lav...@gmail.comwrote: Hello, I've had several conversations on this list about using continuation-passing style in Guile. I recently decided to take the hint and implement it. I've pushed a new branch called wip-rtl-cps that I'd appreciate comments on (but I do not necessarily think that this is the branch that will be merged with master - it's still pretty rough). The branch contains a CPS data structure based on the paper Compiling with Continuations, Continued, by Andrew Kennedy. It lives in module/language/cps.scm. The branch is based on the RTL branch, and there's a CPS-RTL compiler in module/language/cps/compile-rtl.scm. There are also tests for it in test-suite/tests/cps.test. Here are some notes: - It may have been a mistake to do a CPS-RTL compiler first. Even if we want to use RTL eventually, it probably would have been more sensible to do CPS-GLIL first, so the change would be independent of the switch to RTL. However, the code is already here - we can use it as-is, or change to GLIL, or something else. - There's no Tree-IL-CPS compiler yet, mostly because I'm confident that we can do it, so I figured we could always add it later. - There are three major language features missing from the compiler: top-level variables, closures,
Re: Guile Lua
Hi, In terms of strategy, I think Guile’s focus should remain primarily on Scheme variants, and ELisp. Other language front-ends are of course welcome, but we must keep an eye on what the demand is. What about common lisp is scheme a lisp or is CL a scheme :-) Anyway to support CL I would think that we need to support placing properties on symbols, e,g. currently a symbol slot is a variable, but to effectively support CL I would go for /Stefan Den 21 nov 2012 14:26 skrev Ludovic Courtès l...@gnu.org: Hi! nalaginrut nalagin...@gmail.com skribis: I switch to lua branch then compiled it and try, seems some bugs there, it can't run successfully: ---cut scheme@(guile-user) ,L lua Happy hacking with Lua! To switch back, type `,L scheme'. lua@(guile-user) x=1 Maybe you need a semicolon here? And I checked the code, it doen't use Guile inner LALR parser. Anybody point me out what is the suggested parser implementation? (system base lalr). And is there anyone ever evaluated the efficiency about the non-scheme language implemented within Guile? I don’t think so. Only the Scheme and Emacs Lisp front-end are reasonably mature, anyway. Anyway, this wouldn't be a big problem, since Guile could be the future dynamic language compiler collection, it could be optimized later. FWIW, I don’t quite buy the “dynamic language compiler collection”. Others tried this before (Parrot), with some success in terms of supported languages, but not much beyond that. In terms of strategy, I think Guile’s focus should remain primarily on Scheme variants, and ELisp. Other language front-ends are of course welcome, but we must keep an eye on what the demand is. Thanks, Ludo’.
Bug int rtl.scm in wip-rtl
Hi, I just found a bug in rtl.scm, it's triggere by compiling larger rtl codes. In rtl.scm, we have the function (define (link-text-object asm) (let ((buf (make-u32vector (asm-pos asm (let lp ((pos 0) (prev (reverse (asm-prev asm (if (null? prev) (let ((byte-size (* (asm-idx asm) 4))) (bytevector-copy! (asm-cur asm) 0 buf pos byte-size) (unless (eq? (asm-endianness asm) (native-endianness)) (swap-bytes! buf)) (make-object asm '.rtl-text buf (process-relocs buf (asm-relocs asm) (asm-labels asm)) (process-labels (asm-labels asm (let ((len (* *block-size* 4))) (bytevector-copy! (car prev) 0 buf pos len) (lp (+ pos len) (cdr prev))) In thh lp loop I had added reverse in order for the code to emmit the chunks in the right order (the bug was no reverse and we got code emitted in the wrong order) as you can see for smaller codees prev is null and this bug is not triggered. Have fun with rtl, /Stefan
Re: More RTL Tests
Hi Noah, I have a fix to rtl.scm that add an instruction macro like this (toplevel dst sym) e.g. (toplevel 0 pk) to refere to pk in the current module I can send you a patch if you like, it's very instructing for learning how to program the rtl machine to your needs. And it also allows you to write rtl assembler refering to toplevels in a nice way /Stefan On Sun, Oct 14, 2012 at 10:57 PM, Stefan Israelsson Tampe stefan.ita...@gmail.com wrote: On Sun, Oct 14, 2012 at 9:59 PM, Noah Lavine noah.b.lav...@gmail.comwrote: Hello, I have been working on understanding RTL, and I wrote the following tests. They're mostly to illustrate for myself how calling works in RTL, but they also serve to test it. Any objections if I commit them as part of rtl.test? (with-test-prefix call (assert-equal 42 (let ((call ;; (lambda (x) (x)) (assemble-program '((begin-program call) (assert-nargs-ee/locals 1 0) (call 1 0 ()) (return 1) ;; MVRA from call (return 1) ;; RA from call (call (lambda () 42 (assert-equal 6 (let ((call-with-3 ;; (lambda (x) (x 3)) (assemble-program '((begin-program call-with-3) (assert-nargs-ee/locals 1 1) (load-constant 1 3) (call 2 0 (1)) (return 2) ;; MVRA from call (return 2) ;; RA from call (call-with-3 (lambda (x) (* x 2)) (with-test-prefix tail-call (assert-equal 3 (let ((call ;; (lambda (x) (x)) (assemble-program '((begin-program call) (assert-nargs-ee/locals 1 0) (tail-call 0 0) (call (lambda () 3 (assert-equal 6 (let ((call-with-3 ;; (lambda (x) (x 3)) (assemble-program '((begin-program call-with-3) (assert-nargs-ee/locals 1 1) (mov 1 0) ;; R1 - R0 (load-constant 0 3) ;; R0 - 3 (tail-call 1 1) (call-with-3 (lambda (x) (* x 2)) This look good to me My next goal is to learn to reference top-level variables. Could anyone tell me how that works, to make it easier? The general way, use a symbol in loc a and a module in loc b and then issue (resolve c b a) (box-ref c c) To put the symbol into c. The simplest way to check this is to pass b and a as arguments to the funciton, you may set the toplevel by using box-set! For reference inside functions you may use (toplevel-ref dst var_label mod_label sym_label) This is a bit complicated and I havenot found that all the infrastructure is in place to handle this but basically one should need to prepare the code like this if I'm not missing anything (program f) (toplevel-ref 1 var mod sym) ... (label var) (store-slot SCM_BOOL_F) (label mod) (store-slot module) (label sym) (stire-slot 'symbol) where the stire-slot mechanism is not yet supported but should mean that aligned to SCM it stores the needed references. This is what I guess it all means, correct me if i'm wrong! /Stefan
Re: More RTL Tests
Rather than sending me a patch, I'd like to know what Andy Wingo's plans were for accessing variables. I imagine he was thinking of something like this too, so the best thing would be to get that patch merged into the regular wip-rtl branch. Yea that's of cause best, but for now we can just lurk around the code and learn it so that at worst we can help with bugfixing and at best give design feedback for the continuation of the rtl hackaton. Next on my list is to see how we can add metadata to the procedures in order to get better help when looking at back-traces which will be needed in order to pinpoint problems when starting to compile larger code bases to test out any future compiler. In this effort I will make sure that I can get use ,x seamlessly and get back the assembler which also will be crucial when we want to pinpoint problems in the compiler and or rtl VM. Regards Stefan On Wed, Nov 28, 2012 at 8:31 PM, Noah Lavine noah.b.lav...@gmail.comwrote: I would definitely like to see something like that appear in the RTL branch. Otherwise it might be very difficult to write RTL code. Rather than sending me a patch, I'd like to know what Andy Wingo's plans were for accessing variables. I imagine he was thinking of something like this too, so the best thing would be to get that patch merged into the regular wip-rtl branch. Noah On Wed, Nov 28, 2012 at 2:13 PM, Stefan Israelsson Tampe stefan.ita...@gmail.com wrote: Hi Noah, I have a fix to rtl.scm that add an instruction macro like this (toplevel dst sym) e.g. (toplevel 0 pk) to refere to pk in the current module I can send you a patch if you like, it's very instructing for learning how to program the rtl machine to your needs. And it also allows you to write rtl assembler refering to toplevels in a nice way /Stefan On Sun, Oct 14, 2012 at 10:57 PM, Stefan Israelsson Tampe stefan.ita...@gmail.com wrote: On Sun, Oct 14, 2012 at 9:59 PM, Noah Lavine noah.b.lav...@gmail.comwrote: Hello, I have been working on understanding RTL, and I wrote the following tests. They're mostly to illustrate for myself how calling works in RTL, but they also serve to test it. Any objections if I commit them as part of rtl.test? (with-test-prefix call (assert-equal 42 (let ((call ;; (lambda (x) (x)) (assemble-program '((begin-program call) (assert-nargs-ee/locals 1 0) (call 1 0 ()) (return 1) ;; MVRA from call (return 1) ;; RA from call (call (lambda () 42 (assert-equal 6 (let ((call-with-3 ;; (lambda (x) (x 3)) (assemble-program '((begin-program call-with-3) (assert-nargs-ee/locals 1 1) (load-constant 1 3) (call 2 0 (1)) (return 2) ;; MVRA from call (return 2) ;; RA from call (call-with-3 (lambda (x) (* x 2)) (with-test-prefix tail-call (assert-equal 3 (let ((call ;; (lambda (x) (x)) (assemble-program '((begin-program call) (assert-nargs-ee/locals 1 0) (tail-call 0 0) (call (lambda () 3 (assert-equal 6 (let ((call-with-3 ;; (lambda (x) (x 3)) (assemble-program '((begin-program call-with-3) (assert-nargs-ee/locals 1 1) (mov 1 0) ;; R1 - R0 (load-constant 0 3) ;; R0 - 3 (tail-call 1 1) (call-with-3 (lambda (x) (* x 2)) This look good to me My next goal is to learn to reference top-level variables. Could anyone tell me how that works, to make it easier? The general way, use a symbol in loc a and a module in loc b and then issue (resolve c b a) (box-ref c c) To put the symbol into c. The simplest way to check this is to pass b and a as arguments to the funciton, you may set the toplevel by using box-set! For reference inside functions you may use (toplevel-ref dst var_label mod_label sym_label) This is a bit complicated and I havenot found that all the infrastructure is in place to handle this but basically one should need to prepare the code like this if I'm not missing anything (program f) (toplevel-ref 1 var mod sym) ... (label var) (store-slot SCM_BOOL_F) (label mod) (store-slot module) (label sym) (stire-slot 'symbol) where the stire-slot mechanism is not yet supported but should mean that aligned to SCM it stores the needed references. This is what I guess it all means
Re: A proper tail version of with-fluids
You are correct Noha, but please play down the impressed part, we have not reached the goal yet. 1. I did not implement the proper full scale one where we actually can (In case of knowing that no continuation have been stored, get proper tail calls) The reason is that 1. It contains a significant overhead, 2. I'm yet a little ignorant about the inner workings of guile fluids. But in principle, one add meta information to the fluids so that one can know that it's safe to overwrite the old fluid. 2. The one I implemented was simply pushing things on the dynstack located on the heap. This still saves a lot of memory because the function stack was handled more optimal because we used the tail call mechanism. The trick was to be able to unwind automatically in a correct way when we issue a return. 3. Although I coded a version that should mix well with continuations, I haven't tested it yet. /Stefan On Fri, Jan 4, 2013 at 12:44 AM, Noah Lavine noah.b.lav...@gmail.comwrote: I think with-fluids could at least be semi-tail-recursive. If you imagine a normal non-tail-recursive implementation, you might get to a point where your continuation is going to set a fluid back to a value, and then the *next* continuation is going to set that fluid back to *another* value. Since these are only set!s and have no side-effects, you could somehow notice that and not do the first set!. So your continuation only needs to have one set! for each fluid, no matter how many times that fluid is changed by with-fluids. But that seems tricky to implement. I haven't looked at how Stefan did it, but I'm impressed. Noah On Thu, Jan 3, 2013 at 6:36 PM, Ludovic Courtès l...@gnu.org wrote: Hi Stefan, Stefan Israelsson Tampe stefan.ita...@gmail.com skribis: (define f (lambda (n) (if (= n 0) (fluid-ref a) (with-fluids ((a n)) (f (- n 1)) with the modified VM: scheme@(guile-user) (f 1000) $2 = 1 with the old VM, it craches. It works! Hmm, I can’t see how ‘with-fluids’ or ‘parameterize’ could be tail-recursive given that it uses ‘dynamic-wind’. Am I missing something? Ludo’.
Re: Guile Lua
Hi, To note is that in order to implement common lisp one need to bypass tree-il and generate directly to glil, the reason is that tagbody is poorly represented by tree-il. If we intend to be multilingual it would be nice to be able to effectively represent those ideoms. Any thoughts on it? /Stefan On Sun, Jan 13, 2013 at 4:13 PM, Ian Price ianpric...@googlemail.comwrote: Nala Ginrut nalagin...@gmail.com writes: What about common lisp is scheme a lisp or is CL a scheme :-) IIRC， someone raised the topic that emerge Clisp into Guile in 2011, but what's the status now? Anyway to support CL I would think that we need to support placing properties on symbols, e,g. currently a symbol slot is a variable, but to effectively support CL I would go for /Stefan I don't think we should get ahead of ourselves, but emacs has had some minor CL emulation in things like cl.el and cl-lib. I think these could be good test cases for the elisp support. -- Ian Price -- shift-reset.com Programming is like pinball. The reward for doing it well is the opportunity to do it again - from The Wizardy Compiled
Re: wip-rtl native patch
Hi, As I understood my reason for doing this was that many closures point to the same code fragment and If we compile one of those closures the others will not benefit. So therefore I stored the native code at the beginning of the rtl code fragment and used this mechanism. I have not gotten this nailed though because I'm unsure how to treat this data correctly w.r.t. GC. Currently I just keep a reference to the native code to prevent garbage collection if I'm not miss-remember. But perhaps I'm missing something in this argument I would be glad to be wrong in this case :-). Of cause if we compile the module directly to native code this will be a non issue and I completely agree with your approach. Cheers! Stefan On Mon, Jan 21, 2013 at 2:21 PM, Andy Wingo wi...@pobox.com wrote: On Thu 09 Aug 2012 20:59, Stefan Israelsson Tampe stefan.ita...@gmail.com writes: DO you think that this will do as an initial patch to wip-rtl in order to introduce the possibility to execute native code or JIT:ed code. We reserve the first two indexes in the ip text area to fit a pointer to native code to be executed. I would rather use a different tc7 and the existing fallback `apply' loop. Note that this does not preclude JIT compilation: we can change the tc7 of an object at runtime. Cheers, Andy -- http://wingolog.org/
Re: native compilers
Yeah, this is pretty crazy stuff. But crazy fun stuff! 1. Anyway I think that I could just do away with two table lookups to reach both c-function pointers and the goto gosub stuff generated from assembler. 2. A think more work is needed of the extra layer to allow for correct continuation properties. 3. Would be good if we could just pass a pointer to the rtl-vm local data in stead of copying them into a third vm. 4. Good register handling is needed, right now this is the most simplest approach you can have towards native / JIT compiling e.g. take the rtl code and transform it directly to rtl code. you do get faster code but it would be nice to actually take advantage of hardware regiosters. And for that we would need ideally to compile from something else than rtl bytecode. Anyway I could imagine an intrmediate state of guile where we took this simplistic approach to compiling - it should at least be very fast to compile the code and if we look at it as some speedier VM it's actually not a bad idea appart from beeing hard to maintain with respect to hardware architecture. 5. To simplify further we could design most of the meaty stuff in C-code and restrict the target registers for this code and hook everything together with some basic assembler. Then I don't expect the assembler work to be that hefty. 6. As Noha later on in the list point out, there is already JIT engines out there that can work with this without the extra overhead. But I'm so in love with assembler in scheme that I couldn't resist hacking this together. Regards Stefan On Mon, Jan 21, 2013 at 5:53 PM, Andy Wingo wi...@pobox.com wrote: On Sat 22 Sep 2012 23:28, Stefan Israelsson Tampe stefan.ita...@gmail.com writes: I've now coded two version of native compilers for x86-64 linux compiling either the old guile-2.0 VM language or guile-2.2 RTL VM language. This is pretty crazy and wonderful stuff, Stefan. https://gitorious.org/aschm https://gitorious.org/aschm/aschm/blobs/rtl/module/native/vm/inst.scm looks really promising. I guess I need to consolidate the RTL branch now, and we need to make sure that we can plug in a JIT. I don't want to incorporate all of this code at once, so ideally we can make it so that you can load your code as a module and Guile will have the needed hooks to run JITted code if it is there. Excellent hacking! Andy -- http://wingolog.org/
Re: compile-rtl, II
On Mon, Jan 21, 2013 at 6:39 PM, Andy Wingo wi...@pobox.com wrote: On Mon 15 Oct 2012 16:05, Stefan Israelsson Tampe stefan.ita...@gmail.com writes: (arg1, return-address, old-frame, program, arg2 ...) This way we do not need to copy the program field at a tail call What would you do for 0 arguments? I would just fill in the first argument with SCM_UNSPECIFIED or such and send information to the call that 0 argumnets is filled in, then the compiled code would work smartly and use this field for normal rtl registers. Ayway I did not pursue this at date more than adding some flags to the compiler so that we can turn on this feature and try it out later. Also another kind of difficulty will arise, many instructions only take a value of 256 register positions Do you have examples? I think the idea I had in mind was to reserve the last two or three of the 8-bit-addressable registers as temporaries, and emit long-mov shuffles to handle those cases. To be frank it looks like 95% of the code will never need to think about this issue, so your approach seams sane. Andy -- http://wingolog.org/
Re: native compilers
I guess I need to consolidate the RTL branch now, and we need to make sure that we can plug in a JIT. I don't want to incorporate all of this code at once, so ideally we can make it so that you can load your code as a module and Guile will have the needed hooks to run JITted code if it is there. Yes, We might want to use another asssember, e.g. If we wouldl ike to use a more advenced one with more features it should be possible to hook it in. In the end we just will support some smaller subset of the instruction set which we ship with guile. /Stefan
Re: syntax closures
Hi On Tue, Jan 22, 2013 at 1:56 PM, Andy Wingo wi...@pobox.com wrote: Hi, On Thu 17 Jan 2013 21:51, Stefan Israelsson Tampe stefan.ita...@gmail.com writes: Hi all, I wanted to resurrect the idea of a syntactic closure. I did some thinking and Meta: I seem to be receiving your mails with this really strange line wrapping. It's been this way for a while, and it makes it difficult to read your mails. Would you mind taking a look at your editor and setting the fill column to 72 characters? Thanks :) I'm using a web interface, poor me, I'll try to use a proper client after this mail. 2. The idea is to capture the syntactic environment in template1 ... and call the closure with the captured syntactic elements and insert the resulting syntax into . Into what? Heh, I misstakenly pushed a send shortcut that mixed badly with emacs keybindings. Anyway the captured syntaxes is then inserted in their positions. There are a few caveats with the approach, see the code file in the repo for a discussion of that. (read-hash-extend #\_ syntax-closure-reader) Have you tried having your srfi-72 module export a binding for unsyntax? I would like to use that of cause, but does it mix well with other already written code? The question for me is how to treat this code, as a library of it's own supporting e.g. racket and guile and other schemes with the syntax case system, or should we try to make this reader extension as nice as possible and incorporate the code in guile. Is #_ ok? do you have any other suggestion? I would prefer not to include it in the core; in my ignorance I do not see the need, especially if it can be implemented in a library. Of course it may make sense to bundle a srfi-72 implementation with guile, but ideally we can do so without affecting the core. I would like to be able to set this feature on per port bases just like we do with other reader features. Don't know to what a degree you need to do to achieve this. Is it something that a library can do? This relates to the previous question. Anyway I just thoght your thoughts and published a repo, https://gitorious.org/syntax-closures And I also suggeted to ijp to put it into guild-hall. Regards Stefan
Re: syntax closures
Hi wingo: Yes this is something I can do. But on a second thought I can't find a way to handle unsyntax-splicing without a splicing macro. Modding #, and not #,@ just screams for difficult errors to show up. Therefor I will in stead just write another macro unsyntax-72 that people can use. btw, I tried to get gnus working but cannot send mail from it :-( /Stefan On Tue, Jan 22, 2013 at 5:38 PM, Andy Wingo wi...@pobox.com wrote: On Tue 22 Jan 2013 17:19, Stefan Israelsson Tampe stefan.ita...@gmail.com writes: (read-hash-extend #\_ syntax-closure-reader) Have you tried having your srfi-72 module export a binding for unsyntax? I would like to use that of cause, but does it mix well with other already written code? It should work in a modular fashion. #,foo reads as (unsyntax foo), and the meaning of that depends on the binding of unsyntax that is current. Andy -- http://wingolog.org/
Re: syntax closures
Ok, the unsyntax-72 code cannot be cleanly done I think. You really need to use a reader macro. I leave the code base modding the reader char #. as before and will simple wait for a a possibility of per port reader option to be configured via a library. /Stefan On Tue, Jan 22, 2013 at 5:38 PM, Andy Wingo wi...@pobox.com wrote: On Tue 22 Jan 2013 17:19, Stefan Israelsson Tampe stefan.ita...@gmail.com writes: (read-hash-extend #\_ syntax-closure-reader) Have you tried having your srfi-72 module export a binding for unsyntax? I would like to use that of cause, but does it mix well with other already written code? It should work in a modular fashion. #,foo reads as (unsyntax foo), and the meaning of that depends on the binding of unsyntax that is current. Andy -- http://wingolog.org/
Re: syntax closures
Hi, I managed to do what you said, the result is at https://gitorious.org/syntax-closures I changed it so that it is enough to do (use-modules (srfi srfi-72)) and hacking along with it using both #, and #,@ Especially #,@ was difficult but using the ck macro the appending become more natural. I would expect the code to be quite expensive computationally though. On a side note, the quasisyntax expander will severely transform syntaxes of the form (a b c #,@( ...) a) though and therefore any macro that assume that this list can have some form on say 'a b c', will fail because the whole list will be transformed by quasisyntax. It is possible to introduce splicing macros in psyntax I think and then the system would be even more true to the srfi-72. Because I suspect that the srfi-72 spec and the huge transformation of the list e.g. append macros, does not mix well. Anyway it was a fun hack, thanks! /Stefan On Tue, Jan 22, 2013 at 5:38 PM, Andy Wingo wi...@pobox.com wrote: On Tue 22 Jan 2013 17:19, Stefan Israelsson Tampe stefan.ita...@gmail.com writes: (read-hash-extend #\_ syntax-closure-reader) Have you tried having your srfi-72 module export a binding for unsyntax? I would like to use that of cause, but does it mix well with other already written code? It should work in a modular fashion. #,foo reads as (unsyntax foo), and the meaning of that depends on the binding of unsyntax that is current. Andy -- http://wingolog.org/
Re: syntax closures
Hi Alex! Note SRFI-72 is not an implementation of syntactic-closures. It's an alternate hygiene algorithm closer to the R6RS one which includes a compatible syntax-case and some convenience utilities. To comments to this: 1. The main reason for SRFI-72 is to e.g. capture the let bound y in the syntax in (define y 1) (define (f x) x) (let-syntax ((g (lambda (x) #`(let ((y 2)) #,(f #'y) g) - 2 And the same with #,@. In SRFI-72 they design a whole new hygiene method etc. for that. What I tried to do was to get this result as well at good approximation within the current syntax system. 2. I was actually hesistant to call this srfi-72 because of trying to do what it want more than what it say's. A main trick to simulate the effect was to introduce a closure in the syntax at one point and therefore a choose the name syntax-closure not knowing that there is an already a notion of that in the wild sorry! Syntactic-closures never had a formal specification, just an informal description and reference implementation, so it's not clear to me if SRFI-72's make-capturing-identifier is equivalent to the synclos free variables. yeah I could be out of the blue saying srfi-72. Maybe the algorithm needs a srfi of it's own because it does useful stuff and integrates well with standard syntax-case systems which srfi-72 don't. And of cause the mentioning of synclos could be confusing. /Stefan
Re: compile-rtl
Andy Wingo wi...@pobox.com writes: Now when we are tail-calling in rtl, we just fill the argument slots with the new function arguments directly and then tail-call by filling in number of arguments and function. This is very smart and just some simple features added would mean that a lot of translation from one memory location to the other is skipped. I really like how the rtl code handle this but there is an expense. It complicates life a little when we overwrite arguments that are used in the calculation of other arguments. I'm working on how to handle this but I just wanted to point out how nice this design choice is. Thanks! In general at the end you have a parallel register move (or parallel assignment), which has a number of standard solutions out there. This is quite a natural first step. But especially for loops there is a similar tail pattern that probably needs to be optimized better w.r.t. register slots when we compile nativly /Stefan
splicing macros
Hi all, This is something fun to implement using ck-macros and local-syntax-value. The idea is to patch guile's quasisyntax.scm in ice-9 to implement splicing of macros. If we assume a reader macro #.code == (macro-splicing code), with the proposed hack I can now write: (define-syntax-rule (2x x) (x x)) and (define-syntax 4x (lambda (x) (syntax-case x () ((_ x) #`(#.(2x x) #.(2x x)) and (define-syntax g (lambda (x) #`(#.(4x 1) #.(4x 2 $4 = (1 1 1 1 2 2 2 2) I will assume that you are familliar with th ck macro, included in recent guile releases or else consider looking it up at http://okmij.org/ftp/Scheme/macros.html It is now quite natural to use his c-append macro to do do the transformation: (a b #.(f x) c d) -- (ck () (c-append '(a b) (c-append (ck-it '(f x)) '(c d And assuming that ck-it can dispatch the macro (f x) the appending would be obvious. The second magic is ck-it, it is defined as (use-modules (system syntax)) (define-syntax ck-it (lambda (x) (syntax-case x (quote) ((_ s (quote f)) (and (identifier? #'f) (eq? (syntax-local-binding #'f) 'macro)) (call-with-values (lambda () (syntax-local-binding #'f)) (lambda (m transformer) (list #'ck-it #'s (list #'quote (transformer #'f)) ((_ s (quote (quote x))) (list #'ck #'s #'(quote x))) ((_ s (quote (f . x))) (and (identifier? #'f) (eq? (syntax-local-binding #'f) 'macro)) (call-with-values (lambda () (syntax-local-binding #'f)) (lambda (m transformer) (list #'ck-it #'s (list #'quote (transformer #'(f . x))) ((_ s f) (list #'ck #'s #'f) It will iterativelly apply macros until a non macro sexp is appearing, To inhibit macro expeansion one need to quote it. This is a bit unclean because if the macro returns (quote x), x any sexp, it will return x in stead. A better solution might be to introduce a special inhibit macro. Also notice how splicing in already spliced syntaxes works as the example above works. Another thing to note is how we use syntax-local-binding to search find the macro transformer and use that in order to make all this work. Any thoughts? Should we add ck-it to guile's ck.scm? Should we add splicing macros? /Stefan
Re: splicing macros
Yes, I can add documentation for it. /Stefan On Sun, Jan 27, 2013 at 11:17 AM, Andy Wingo wi...@pobox.com wrote: On Sat 26 Jan 2013 14:03, Stefan Israelsson Tampe stefan.ita...@gmail.com writes: I will assume that you are familliar with th ck macro, included in recent guile releases or else consider looking it up at http://okmij.org/ftp/Scheme/macros.html It does not seem to be documented in Guile's manual. Want to write some documentation? :) Andy -- http://wingolog.org/
Re: syntax closures
I didn't know that this was a taken name already, Let's call it guile-srfi-72, In the end it is a srfi-72 simulator that mix well with the current guile macro system but is not a perfect replacement (yet) I'll check it out, But srfi-72 really covers a need I have when writing macros with syntax-parse. I'll check the sc-macro-transformer out. /Stefan On Thu, Feb 14, 2013 at 10:42 AM, Mikael Djurfeldt mik...@djurfeldt.com wrote: Just saw this. Right, syntactic closures is the name of a macro system by Alan Bawden and Jonathan Rees: http://en.wikipedia.org/wiki/Syntactic_closures http://www.gnu.org/software/mit-scheme/documentation/mit-scheme-ref/Syntactic-Closures.html#Syntactic-Closures So, it would be good to choose a different name if what you are doing is different. BTW, the sc-macro-transformer facility of MIT-scheme would be nice to have. :-) Best regards, Mikael D. On Thu, Jan 24, 2013 at 9:45 AM, Alex Shinn alexsh...@gmail.com wrote: On Thu, Jan 24, 2013 at 4:11 PM, Stefan Israelsson Tampe stefan.ita...@gmail.com wrote: 2. I was actually hesistant to call this srfi-72 because of trying to do what it want more than what it say's. A main trick to simulate the effect was to introduce a closure in the syntax at one point and therefore a choose the name syntax-closure not knowing that there is an already a notion of that in the wild Oh - I thought you were referring to the existing syntactic-closures. I guess it's a plausible enough name to reuse coincidentally... Carry on then :) -- Alex
Re: syntax closures
BTW. Of cause if you read the doc's for srfi-72 you will see a whole different machinery that brings many features, they explicitly states 6 facts in the abstract for which I adress one in the code. On the other hand when they try to sell it it they just uses examples for the case for witch I try to implement a solution for. So in this light I would say that I practically cover 90% of srfi-72 intention. But from a theoretical standpoint I would just say 10%. /Stefan On Fri, Feb 15, 2013 at 5:16 AM, Mark H Weaver m...@netris.org wrote: Stefan Israelsson Tampe stefan.ita...@gmail.com writes: Let's call it guile-srfi-72, In the end it is a srfi-72 simulator [...] I'm pretty sure this is also false. One of the main points of SRFI-72 is the improved hygiene algorithm, which is quite different than psyntax in its details. Unless I'm mistaken, you have picked out only one small aspect of SRFI-72 that happens to be relevant to what you're doing. Therefore, I don't think it should be called SRFI-72 either. Mark
Re: CPS Update
Hey Noha, Great work indeed. Isn't the primitiveness decided by tree-il? you wil get a (primcall ...) tree il element and then should know how to emit a corresponding primitive instruction(s). Anyway I think that your conclusion is right, it would not make sense to support overwriting these primitives dynamically, but scheme@(guile-user) (set! + (lambda x (apply * x))) scheme@(guile-user) (+ 2 3) $1 = 6 scheme@(guile-user) (define (f x y) (+ x y)) scheme@(guile-user) ,x f Disassembly of #procedure f (x y): 0(assert-nargs-ee/locals 2) ;; 2 args, 0 locals 2(local-ref 0) ;; `x' 4(local-ref 1) ;; `y' 6(add) 7(return) So things are not consistent! BTW If you like I could work on getting define* and lambda* to work, I have that code in my branch and should be able to make it work on your branch as well. WDYT? /Stefan On Sat, Feb 16, 2013 at 1:53 AM, Noah Lavine noah.b.lav...@gmail.com wrote: Hello, The wip-rtl-cps branch has been rebased again (on top of wip-rtl). It now includes support for toplevel references and sets, thanks mostly to Andy's work on supporting them in RTL. (Although you shouldn't kick that part of it too hard just yet; I think I know where it will break.) Other highlights include using the top-level variable support to evaluate (+ 3 4) correctly. Overall, I think it's coming along well. The parts of Tree-IL that are left to implement are local mutable variables (should be easy after toplevel ones), module references and sets (very similar to top-level ones), closures, and the dynamic environment stuff. Local mutable variables are my next project, and then I think closures. One question I've had is, can we assume that the variables in the (guile) module are immutable? I think the current compiler does this. Otherwise there's no correct way to inline primitive procedures like + unless we have a way to invalidate our compiled code and recompile it (which I would like to have anyway, but that's a different story). Best, Noah
potluck
Hi all, for what it's worth, I have been playing, for this potluck, with guile-zmq. I compiled a small layer on top of that library that should make it easy to implement some simple applications consisting of many concurrent small programs by sending messages between them. You can find it at https://gitorious.org/guile-message To find out more information see the DOCUMENTATION file in that repo /Stefan
Re: CPS Update
Hi, 1. Does any other system recompile stuff that set! a + operation 2. Isn't the least we should do to warn when a user set! + as I did in the last email 3. Wouldn't it be a good idea to allow a user to specify which basic vm op's would be translated to a macine instruction or not. So say that I would like to count the number of scheme + guile uses at startup, then I could specify in a configuration that + should not be comiled to a vm-op and then recompile guile and then use set! On Sat, Feb 16, 2013 at 5:29 PM, Noah Lavine noah.b.lav...@gmail.com wrote: Hello, On Sat, Feb 16, 2013 at 2:39 AM, Stefan Israelsson Tampe stefan.ita...@gmail.com wrote: Isn't the primitiveness decided by tree-il? you wil get a (primcall ...) tree il element and then should know how to emit a corresponding primitive instruction(s). Oh, you're right. I was thinking about that because I don't run the Tree-IL optimizers when I test it, so I don't get any Tree-IL primitives. Eventually maybe the primitive generation should happen in CPS, but I don't think it has to happen all at once. Anyway I think that your conclusion is right, it would not make sense to support overwriting these primitives dynamically, but scheme@(guile-user) (set! + (lambda x (apply * x))) scheme@(guile-user) (+ 2 3) $1 = 6 scheme@(guile-user) (define (f x y) (+ x y)) scheme@(guile-user) ,x f Disassembly of #procedure f (x y): 0(assert-nargs-ee/locals 2) ;; 2 args, 0 locals 2(local-ref 0) ;; `x' 4(local-ref 1) ;; `y' 6(add) 7(return) So things are not consistent! Good example! This looks like a bug to me. I think I read that loading GOOPS turns things like '+ into generic operations - that might be a case where this matters a lot. I have thought a bit about how to fix this. The module system already allows us to be notified whenever a variable changes, so it would be easy to watch all of the variables in (guile) and recompile procedures when they change. I might take a look at this soon. BTW If you like I could work on getting define* and lambda* to work, I have that code in my branch and should be able to make it work on your branch as well. WDYT? Thanks, but I haven't even gotten far enough to think about this. I'm still working on getting all of the basic features going. After that I would definitely like define* and lambda*. Noah /Stefan On Sat, Feb 16, 2013 at 1:53 AM, Noah Lavine noah.b.lav...@gmail.com wrote: Hello, The wip-rtl-cps branch has been rebased again (on top of wip-rtl). It now includes support for toplevel references and sets, thanks mostly to Andy's work on supporting them in RTL. (Although you shouldn't kick that part of it too hard just yet; I think I know where it will break.) Other highlights include using the top-level variable support to evaluate (+ 3 4) correctly. Overall, I think it's coming along well. The parts of Tree-IL that are left to implement are local mutable variables (should be easy after toplevel ones), module references and sets (very similar to top-level ones), closures, and the dynamic environment stuff. Local mutable variables are my next project, and then I think closures. One question I've had is, can we assume that the variables in the (guile) module are immutable? I think the current compiler does this. Otherwise there's no correct way to inline primitive procedures like + unless we have a way to invalidate our compiled code and recompile it (which I would like to have anyway, but that's a different story). Best, Noah
Re: goops - accessors, methods and generics
For the mg-3 case, Actually, only (merge-generics) in mg-3 is needed, the accessors are automatically generics. /Stefan
Re: Programming racket like in guile
On Saturday, February 23, 2013 08:54:09 AM Daniel Hartwig wrote: For those parts specific to racket, did you consider the (language racket ..) namespace, where an eventual language definition could be placed also? Hmm, my problem with this is that to cover the racket lang is a monumental effort because it covers such things like imutable cons cells a new macrology system, a new module system etc. It would take me forever to actually complete anything close to #lang racket. Therefore I prefere to call it a compatibility module. The idea is to minimize the work needed to port code written in racket to guile. If we than mange after some significant time to repreoduce #:lan racket we can of cause promote this module to (language racket). Does this make sense? /Stefan
Re: Programming racket like in guile
Let me illustrate the problem. Consider macro syntax-parse written in (language racket). My view is that the sourcecode for that code should just have been copied from the racket sources in order to keep the code maintainable. Could we use that macro from whithin a guile scheme program? sometimes but for this example the syntax-parse macro uses so many features in racket syntax expander that you simply cannot use it without copying the racket macro framework. So you have racket macros and you have guile macros and they do not compose. But we would like to be able to use syntax-parse in guile scheme. Hence we must port over the code, and I can tell you that porting syntax-parse is not trivial. Should we mix guile syntax parse and racket syntax parse in the same namespace. It is the same store when it comes to porting over common lisp ideoms. If you would like to port cl's loop macro to guile you cannot use the sources. The reason is that cl uses tagbody and tagbody is not supported in tree-il. So you write a separate port in scheme with syntax-parse and friends and use that. On the other hand I had a though of extending tree-il with a tagbody form and use that as a separate language, again macros would not compose and the same issue will appear. Say that we manage to unify the macrology, no problem, then we can just use re-export. Hope this show some light on the problem /Stefan
Re: Programming racket like in guile
On Sunday, February 24, 2013 10:07:36 PM Ludovic Courtès wrote: What would have been nice IMO is to import, say, ‘syntax-parse’ and contracts, without having to pull in a whole compatibility layer. Ludo’. I would say that I tried more to make syntax-parse independent. contracts on the other hand depends on syntax-parse for loops racket structs etc. That said syntax parse is quite a hefty sized library. /Stefan
Better generator and iterator support in guile w.r.t. speed
Hi guilers! Inspired by wingo's recent blogage on wingolog in combination with my portings of racket and cl loop frameworks, I did some thinking about generators. Especially inlining. 1. Can we make stubs like this inlinable (iterate (generator g (iterate (for x in l-i-s-t) (when (even? x) (yield (f x) (collect (+ (next g) (next g A generator would be somthing like (define-syntax-rule (generator _thunk) (lambda () (let ((thunk (lambda () (_thunk) (finish (call-with-prompt tag thunk (lambda (k . l) (set! thunk k) (apply values l)) (define-syntax-rules (yield x) (abort-to-prompt tag x)) With this kind of generator, as wingo says, we will get what we want but slowly. Might matter sometimes and not somtimes. What we would have liked here is some way of noticing that the liveness of tag is somewhat lexical and cannot be hidden in f. With that information a compiler would be able to inline code quite efficiently and make extensive use of gotos. How? Let's see how finish is working (define-syntax-parameter finish) (define-syntax-rule (iterate c ...) (syntax-parametrize ((finish (syntax-rules () ((_ x) (apport-to-prompt tag2 x) (call-with-prompt (lambda () loop code) (lambda _ final code This whole setup would then be identified to something like (seqence loop: (with-frame g (generator thunk) code ...) finish: finish-code) To make the compilation to glil simple we mean by with-frame that we can setup a stack area where we can inline the thunk code and then a call to g like (next g) == (g) we can identify that 1. if (g) returns it will be from the abort clause in the prompt because the next part will jump to the finish part in the section which is below the generator frame and then it's possible to mark that stack space void. 2 The usage of the continuation is that we overwrite the same stack space with continuos versions of k's e.g. this is a characterizatin that we can keep the stack as a storage for this continuation. 3 with-frame is not recursive in g e.g. g is not visible inside thunk 4 So we should be able to make this work with intelligent usage of gotos. No, (f x) will be a problem because that we cannot know how much stack-space that function is needing. 5 What is interesting with the rtl format is that function applications are setuped at the end of the stack frame. This means that imersion of a generator is pretty simple using gotos and for rtl we would be able to manage quite general iterators and inline them with quite simple means. My conclusion is that for wip-rtl we should really start working on a prompt ideom that is lexical. But is it general enough. probably, but if you If you consider the main use case to be inlinable code, then you would need to consider the following tree-il extension (lexical-rec-prompts (name thunk abort-lam) ...) where name ... is visible inside the thunk's and abort's sections. Of cause not all versions of this code will be possible to manage without long-jumps and old pompt like features. (to note, CL's tagbody seams to be a very similar notion) Am I out in the blue or do you agree? Cheers Stefan.
Re: Better generator and iterator support in guile w.r.t. speed
Hi all, In my previous mail I did some discussions about what structure to use in order to allow efficient implementatin og generators and one main observation is that the curretn rtl strategy can be used. Now Have you all thought about the stack beeing a must to execute funcitons. Well we have threads but we can get lightweight in process threads quite naturally in the rtl version of guile. We could call it a coroutine and let it be an object co = (code,stack,ip,outer-stack) The idea here is that the code will have a fixed sized stack that is just enough room to store all locals and intermediate variables e.g. all the registers needed to execute the function. Any call would then need to hook onto the outer stack. The stack is typically of the form stack = [IP OUTER-FP LOCALS ...] At the creation, IP points to the starting code position and then after each exit the next ip is stored in IP and so on. To support this we need a few new operations * MULTIMOVE, from the local stack to outer stack * MULTIMOVE, to the local stack from the outer stack * OUTER-TAIL-CALL This re-uses the outer call frame used to call this coroutine and resets the IP to the initial value * OUTER-CALL This will setup a new call frame on the outer stack execute the function there * RESET-IP RESET the IP value to the initial start value * STORE-IP Store an local ip adress in IP using a label. * OUTER-RETURN Simply return using the OUTER-FP and make sure * CALL-CO This will call a CO routine by setting up the * TAIL-CALL-CO call frame or reusing the current one (in tail context) then set the OUTER-FP and jump to the IP value if a number else throw an error. And then setting IP to #f and start executing This will probably work quite ok. But the question is how well it play with call/cc and classic prompts as well as usage of the same object many times. 1. This object can only be located one time in the stack because when in use IP = #f and another application of the object down the stack would throw an error at the application 2. call/cc prompt code dynwinds and fluids inside co needs to have special versions 3. When one store the stack space one need to make sure that the co routines also get copied. To note is that these objects should be able to live immersed in the stack space for quick allocation when we inline them inside functions. -- Anyway I will explore this concept semewhat more and see if all scheme features can be made to interop in a good way with it. -- I would also come back to the question if we should have a special tree-il concept that can be used to model this behavior. I'm now inclined to concider something like. (lexical-prompts ((g #:exits (a ...) #:body (th thunk) #:exit-case (((a) (lambda (k kind arg ...) code2)) ...)) ...) code ...) The default expansion of this woule then be something like (letrec ((g . l) (let* ((tag (make-tag)) (th thunk)) (call-with-prompts tag (apply th l) (lambda (k kind arg ...) (case kind ((a) code2 ...) ...) ...) code ...) So if we can prove: 1. The only references of g ... inside th is through e.g. (a g arg ...) where we mean ( g arg ...) = (abort-to-prompt tag 'a g arg ...). 2. these (a ...) forms is not included in any lambda definitions or entering any funciton via it's argumnets. 3. g is never feeded as an argument to a function or located inside a closure definition anywhere in the form. 4. in ((code2 ...) ...) ... any applications of g ... is located in tail position. 5.th is always setted to either k or the initial thunk or never setted in any of the ((a) ...) forms. with these things satisfied we should be able to inline the co routine or generator inside of the function with quite good characteristic. This is interesting this should be a logically step up in generality from CL's tagbody. Of cause there is a lot of substructure and combination of the general construct. From the rtl code we would manage just ok with the old instructions just fine except for the need to be be able to store a label value and goto to a stored label value aka named goto. WDYT? /Stefan
Re: set! semantics
On Sunday, March 17, 2013 09:36:29 AM Noah Lavine wrote: Hello, I believe that keeping the box identity but not the box value is the correct behavior of continuations under the Scheme standard. I agree it's not intuitive, though. I have been thinking that we could eliminate variable boxes for mutable variables when we can prove that the continuation is never captured. I need to understand more about how continuations work, but I don't think we need a new variable type for efficiency reasons. If you want a new type of variable because you want different semantics, that's a different issue. Could you give more of an example? I assume that you're talking about something like this: (loop ;; the macro defines a loop counter (call/cc some-other-function)) So when the continuation of the loop is called more than once, the loop counter is incremented too much. Is that right? Best, Noah On Sun, Mar 17, 2013 at 9:07 AM, Stefan Israelsson Tampe stefan.ita...@gmail.com wrote: Dear all, I just noted an issue with a programming style, that I suspect schemers try to avoid but still is quite common in the lisp community and actually makes for simpler macros when e.g. writing loop macros. The issue here is that one setup local variables with a let and then modify them using set!. The problem is that this code will always be boxed. Now the overhead of this is almost invisible due to other overhead. What I ask is what happens when we store the stack at a call/cc setup? What will happen is that the box identity is stored but not the box value and hence there will be problems with recurrent calls of a continuation. Now I could be pretty fine with this because it's a clean statement to say that this behavior is included in the set! semantic. And we actually need keep this semantic to not break backward compability. Anyway. It's still pretty useful to have a local-set that will only set a variable if it safely can set the local variable on the stack directly I therefore propse for guile to include a new variable binding construct called local-set! personally I would in most cases avoid it's use but I would love to have it in my loop macros. WDYT /Stefan I did a test here with, (define k #f) (define (f n) (call-with-prompt 'a (lambda () (let ((s 0) (i 0)) (let loop () (set! s (+ s i)) (set! i (+ i 1)) (case i ((20 50) (abort-to-prompt 'a s))) (if (= i 100) 'ok (loop) (lambda (_k v) (set! k _k) v))) (pk (f 1)) (pk (call-with-prompt 'a k (lambda (k x) x))) (pk (call-with-prompt 'a k (lambda (k x) x))) which outputs ;;; (190) ;;; (1225) ;;; (ok) And what you write is inded what is implemented. I think this is ok! what I wan't is an ideom, local-set! that only set the variable local to the function, and errors out if it tries to local-set! a variable ouside of the functions scope, e.g. (let ((a 1)) (lambda () (local-set! a 2))) Should fail to compile if the lambda is needed for the final output. This does have the drawback that we cannot push the values down the stack for lambdas, remains to design dynamic wind like (let ((i 0)) (dynamic-wind-x (lambda (w) (set! i (car w))) (lambda () code ...) (lambda x (dynwind-store (list i) And then let the optimizations, when possible, inline things in a nice form /Stefan
Special variables to relax boxing
Hi, I wouldl like to start a discussion of introducing a way to mark variables as special, and by that mean that set! variables does not nessesary get boxed. This is a deviation from the scheme standard but it's pretty useful if one want to set! local variables but make sure that the state of the function can be stored in a continuation and later restart at the same state. This patch introduces a macro (mark-as-special var), this will mark var as a special variable in the above meaning, please look at the example in special.scm for more info. There is a preleminary patch following the document against stable-2.0 that we can use as a discussion point for know about this feature. Best Greetings Stefan (use-modules (system vm special-variable)) ;; This makes sure to treat s special and not box it (define (g x) (let ((s 0)) (mark-as-special s) (let lp ((i 0)) (if ( i 1000) (begin (set! s (+ i s)) (lp (+ i 1))) s #| ,x g 0(assert-nargs-ee/locals 17) ;; 1 arg, 2 locals 2(make-int8:0) ;; 0 3(local-set 1) ;; `s' 5(new-frame) 6(toplevel-ref 1);; `((system vm special-variable) special #f)' 8(local-ref 1) ;; `s' 10(mv-call 1 :L583) ;; MV - 20 15(drop) 16(br :L584) ;; - 23 20(truncate-values 0 0) 23(br :L585) ;; - 56 27(local-ref 2) ;; `i' 29(make-int16 3 232) ;; 1000 32(lt?) 33(br-if-not :L586) ;; - 53 37(local-ref 2) ;; `i' 39(local-ref 1) ;; `s' 41(add) 42(local-set 1) ;; `s' 44(local-ref 2) ;; `i' 46(add1) 47(local-set 2) ;; `i' 49(br :L587) ;; - 27 53(local-ref 1) ;; `s' 55(return) 56(make-int8:0) ;; 0 57(local-set 2) 59(br :L587) ;; - 27 |# ;; This makes sure to treat s as special but we cannot box it because it's ;; referenced in closure, set! + closure = boxed (define (g2 x) (let ((s 0)) (mark-as-special s) (let lp ((i 0)) (if ( i 1000) (begin (set! s (+ i s)) (lp (+ i 1))) (lambda () s) #| 0(assert-nargs-ee/locals 17) ;; 1 arg, 2 locals 2(make-int8:0) ;; 0 at /home/stis/src/special.scm:45:2 3(box 1) 5(new-frame) at /home/stis/src/special.scm:46:4 6(toplevel-ref 1);; `((system vm special-variable) special #f)' 8(local-boxed-ref 1) ;; `s' 10(mv-call 1 :L824) ;; MV - 20 15(drop) 16(br :L825) ;; - 23 20(truncate-values 0 0) 23(br :L826) ;; - 67 at /home/stis/src/special.scm:47:4 27(local-ref 2) ;; `i' 29(make-uint64 0 0 0 0 0 152 150 128);; 1000 38(lt?) at /home/stis/src/special.scm:48:10 39(br-if-not :L827) ;; - 59 at /home/stis/src/special.scm:48:6 43(local-ref 2) ;; `i' 45(local-boxed-ref 1) ;; `s' 47(add) at /home/stis/src/special.scm:49:25 48(local-boxed-set 1) ;; `s'at /home/stis/src/special.scm:49:17 50(local-ref 2) ;; `i' 52(add1)at /home/stis/src/special.scm:50:21 53(local-set 2) ;; `i' 55(br :L828) ;; - 27 at /home/stis/src/special.scm:50:17 59(object-ref 2) ;; #procedure 13bbe80 at /home/stis/src/special.scm:51:10 () 61(local-ref 1) ;; `s' 63(make-closure 0 1) 66(return) at /home/stis/src/special.scm:47:4 67(make-int8:0) ;; 0 68(local-set 2) 70(br :L828) ;; - 27 |#diff --git a/module/Makefile.am b/module/Makefile.am index c47d0b4..b07c342 100644 --- a/module/Makefile.am +++ b/module/Makefile.am @@ -101,6 +101,7 @@ SCHEME_LANG_SOURCES = \ language/scheme/decompile-tree-il.scm TREE_IL_LANG_SOURCES = \ + language/tree-il/special.scm \ language/tree-il/primitives.scm\ language/tree-il/effects.scm
Re: Special variables to relax boxing
Ok, This was a first step to get what I would like to have implemented in the tree il backend (Not for scheme but perhaps something useful for e.g. emacs-lisp, python etc). My main issue with the current setup is that adding undoing and redoing feature with the help of prompts will fail in 95% of the cases where the program is written in an imperative style which is not uncommmon in languages we would like to support in guile. Prompts is such a cool feature and is probably one of the main selling points of why one should use their language ontop of guile. So I've just exploring how to improve on this. I think you missundeerstood my posted semantic. It will box if you set! a variable and the same variable is located in a closure, I think that is a safe approach. But you are right that it's a very unclear semantic but my intention was to use this as a step of a better primitive. So over to the semantic I would like to have, To do it currently in guile you would need to do something like, (define-syntax with-guarded-var (lambda (x) (syntax-case x () ((_ var code) (with-syntax ((guard ...)) #'(let ((guard (make-fluid))) (with-fluids ((guard var)) (dynamic-wind (lambda () (set! var (fluid-ref guard)) (lambda () (mark-as-special var) code) (lambda x (fluid-set! guard var))) It might be improved but is really really a horrendous solution to the semantic. The semantic is pretty close to a fluid variable solution but it will mix much better with delayed computations and is a big reason for not using fluids in a more simple try. What I would like to propose is an idiom in tree-il that basicly looks like (with-special (var ...) code ...) and what it does is to put onto the stack is the following mark var1 place1 var2 place2 ... mark-end - and then execute the code just as nothing have happend. Then we could add the code to the stack copying part of the prompt cal/cc etc to when scanning the stack backwards, if it sees maek-end, then it will store the value of var1 in place 1 etc. And when reinstalling the stack it will search for the mark and place the value of place1 into the var in var1 and so on. Another solution is to add a new control ideom onto the control stack where the fluid controls and dynamic wind control lives with a pointer ti the var1 position and the number of vars. With this solution we can skip the marks and also improve the performance of the installment and savings of the stack, the drawback is that we neede to handle that we install the saved stack perhaps at another adress, but it's doable. (A good thing using this is that we can reuse this rebasing technique to improve the speed and scaleup of fluid variables at a tail call position in many cases) I actually use a clumsy version of this semantic in guile-log and I know that although it is anesoteric feature it means that you can easilly implement really cool features that I would not dare to write in e.g. kanren, If you write a prompt based logic implementation It will make a hughe difference in what you have the above semantic without going down to snail speed. To increase speed further the system would use (mark-as-special) and check if it can be unboxed, in which case tha variable will not be baxed and with-special will be a no op. I hope that this is a clearer description of what I'm aiming at! /Stefan On Thu, Mar 21, 2013 at 7:00 AM, Mark H Weaver m...@netris.org wrote: Hi Stefan, Stefan Israelsson Tampe stefan.ita...@gmail.com writes: I wouldl like to start a discussion of introducing a way to mark variables as special, and by that mean that set! variables does not nessesary get boxed. I don't think you fully understand the ramifications of what you're proposing here. In the general case, mutable variables need to be boxed because closures end up with copies of any free variables that they reference. If a free variable is mutable, that means it needs a copy of the _location_ where the value is stored. Making a copy of the _value_ of a variable at the time of closure creation would lead to very unintuitive (and IMO broken) behavior. More importantly, you are describing this proposed language feature in terms of low-level implementation details. If you're serious about proposing such a fundamental new feature to Scheme, please start by reading and understanding the denotational semantics of the R5RS, especially sections 3.1 and 3.4, and then reformulate your proposal in those terms. For such a fundamental change, I'd want to see a proposed new formal denotational semantics to replace those in section 7.2. To be honest, I'm not suggesting this to help you refine this proposal. I'm suggesting it because I think it would help you to think more clearly about these issues
Re: Special variables to relax boxing
On Thursday, March 21, 2013 11:35:19 AM Noah Lavine wrote: (lambda () (let ((x 5)) (set! x (compute-1 x)) (set! x (compute-2 x)) x)) becomes (lambda () (let ((k1 (lambda (x) (k2 (compute-2 x (k2 (lambda (x) x))) (k1 (compute-1 x However, this rewriting idea runs into trouble when you try to figure out what happens to mutable variables that have been captured by closures (as Mark said). I don't know what the right solution is here. The semantic is that cpatured variables in lambdas will be restored to the value when the continuation left the guard. And this is something you want many times e.g. consider, (let ((a 0) (f (case-lambda (() a) ((b) (set! a b) (with-special (a) (for-each (lambda (x) (if (blah x) (k x f) (abort-to-prompt 'tag a))) a-list) (f))) Assume that you would like to be able to go back to the tag abort many times in a redo/undo sequence, then it is natural for the a referenced in f to be restored as well. But as you know sometimes this is not what we want. As I said, using dynwinds and fluids it's really possible to get this behavior today but it's really a bloated solution. Anyhow the good news with this semantic is as with the current behavior of assigned variables it's easy to reason with the code although one risk some severe bugs. A good question though is what we should use as default for e.g. a python implementation where prompts is not included per se, but which we might want to add as a special scheme flavour of python using an import e.g. what is the natural thing to expect for the variables that are assigned. Also in the previous email I had a suggestion to for each with variable, a, add two slots in the stack e.g. a1 val1 s2 val2 ... But there is a good reason to asign a kind to this as well e.g. a1 val kind a2 val2 kand2 ... then we could use a predicates when we rewind a continuation e.g. at rewind: (when (pred1 kind1) (set! a1 (ref-val val1))) ... and and at wind (when (pred2 kind1) (set-val val1 a1)) ... A simple version of this with a complex implementation is what I actually use in guile-log. BTW after this deep realizations of the guile variable behavior I'm ready to implement a much improved version of these special variables in guile-log that is both efficient and featureful. Cool! Have fun /Stefan
Re: Special variables to relax boxing
On Thursday, March 21, 2013 03:03:06 PM Mark H Weaver wrote: Stefan, you're still describing your proposal in terms of low-level implementation details such as stacks. In the general case, we cannot store environment structures on the stack. Furthermore, in the general case *all* variables in scheme are bound to locations, not values. Only in special cases can we use stacks, and only in special cases can we avoid boxing variables. These are only _optimizations_. If you're serious about this proposal, please read sections 3.1 and 3.4 of the R5RS carefully. Explain your proposed _semantics_ (not the implementation details) in those terms, where *all* variables are bound to _locations_, and where there is no stack at all (everything is conceptually stored in a garbage-collected heap). We need to understand the *semantics* in the simplest possible terms before we even begin to think about how to implement it. Thanks, Mark Ok, the sematics for the simple version is are, Assume k, the continuation associated with with a dynamic wind or unwind assume that there is a map from each continuation (k,id) to a value and getting and setting of this value is done through ref-get and ref-set, assume that the winder and the rewinder lambda takes a first argument k beeing the continuation under action, finally make-id will make a unique object. then the semantic would be: (define-syntax-rule (with-special (a) code) (let ((id (make-id))) (dynamic-wind (lambda (k) (set! a (ref-get k id))) (lambda () code) (lambda (k) (ref-set! k id a) A possible refinment of this is associate to k two predicates e.g. (do-wind? k kind) predicate and a (do-unwind? k kind) wich takes a parameter kind, then use the semanics (define-syntax-rule (with-special (a kind) code) (let ((id (make-id))) (dynamic-wind (lambda (k) (when (do-wind? k kind) (set! a (ref-get k id (lambda () code) (lambda (k) (when (do-unwind? k kind) (ref-set! k id a)) Hopes this helps! /Stefan
Re: Special variables to relax boxing
Hi list, Mark and Noah,
Yesterday I noticed that the sematics for special variables are quite
close to fluids and decied to see if I could model special variables
ontop of that with-fluids semantics. That was pretty easy. The basic
difference between fluid and special variables is that with fluids one
swaps between the storages at the with-fluids point, both backwards
and forwards. in the case of special variables one bascially takes on
half of the swap at the wind and the other half at the unwind. So it
become quite easy to just copy the fluid logic and then slightly
modify that source. The scheme compilation part is a little hacky but
it was not that hard to plumb an acceptable solution for testing. I
did verify that it manages the value as said and noticed a 10x
increase of speed when it comes to code passing into a with-fluids
without any prompts compared to any possible setup using dynamic-wind
and fluids. The system is still pretty rough though but there are some
significant optimization implemented.
a preliminary git diff is attached for you to play with.
I did try to implement special variables in current guile. I found
that it is pretty difficult to get the correct semantics working
anyone able to spot it. I use,
(define guards (make-vector 10))
(let lp ((i 0))
(when ( i 10) (vector-set! guards i (make-fluid
(define-syntax with-special-soft
(lambda (x)
(syntax-case x ()
((_ (x ...) code ...)
(with-syntax (a k) ...) (y ...))
(let loop ((i 0) (l #'(x ...)) (r '()))
(if (or (= i 10) (null? l))
(list (reverse r) l)
(loop (+ i 1) (cdr l) (cons (car l) r))
(with-syntax (((i ...) (iota (length #'(a ...)
(if (null? #'(y ...))
#'(with-fluids (((vector-ref guards i) a) ...)
(with-special* ((i a k) ...)
code ...))
#'(with-fluids (((vector-ref guards i) a) ...)
(with-special* ((i a k) ...)
(with-special-soft (y ...) code ...))
(define special-wind-guard (make-fluid (lambda (x) #t)))
(define-syntax-rule (with-special* ((i a k) ...) code ...)
(dynamic-wind
(lambda ()
(set! a (fluid-ref (vector-ref guards i)))
...)
(lambda ()
code ...)
(lambda y
(fluid-set! (vector-ref guards i) a)
...)))
(define (f x)
(let ((s 0))
(with-special-soft ((s 0))
(let lp ((i 0))
(cond
((= i 100) s)
((= i 50) (abort-to-prompt 'tag) (lp (+ i 1)))
(else (set! s (+ s i)) (lp (+ i 1
(define k (call-with-prompt 'tag (lambda () (f 1)) (lambda (k . l)
k)))
scheme@(guile-user) (k)
$1 = 4900
scheme@(guile-user) (k)
$2 = 8575
Can you spot the bug?
The example works very well with my hardcoded version code and is as
fast as this logic can get, much better than 10x faster because this
case can be very well optimized.
To note here also is that with this code we might get into stack
issues due to the with-special can spoil tail call stack features just
as with-fluids.
WDYT?
/Stefan
diff --git a/libguile/dynwind.c b/libguile/dynwind.c
index 14dd861..76c4889 100644
--- a/libguile/dynwind.c
+++ b/libguile/dynwind.c
@@ -244,6 +244,11 @@ scm_i_dowinds (SCM to, long delta, void (*turn_func) (void *), void *data)
scm_i_swap_with_fluids (wind_elt,
SCM_I_CURRENT_THREAD-dynamic_state);
}
+ else if (SCM_WITH_SPECIAL_P (wind_elt))
+ {
+ scm_i_with_special_from_guard (wind_elt,
+ SCM_I_CURRENT_THREAD-dynamic_state);
+ }
else if (SCM_PROMPT_P (wind_elt))
; /* pass -- see vm_reinstate_partial_continuation */
else if (scm_is_pair (wind_elt))
@@ -277,6 +282,11 @@ scm_i_dowinds (SCM to, long delta, void (*turn_func) (void *), void *data)
scm_i_swap_with_fluids (wind_elt,
SCM_I_CURRENT_THREAD-dynamic_state);
}
+ else if (SCM_WITH_SPECIAL_P (wind_elt))
+ {
+ scm_i_with_special_to_guard (wind_elt,
+ SCM_I_CURRENT_THREAD-dynamic_state);
+ }
else if (SCM_PROMPT_P (wind_elt))
; /* pass -- though we could invalidate the prompt */
else if (scm_is_pair (wind_elt))
diff --git a/libguile/fluids.c b/libguile/fluids.c
index 327d12f..c43011d 100644
--- a/libguile/fluids.c
+++ b/libguile/fluids.c
@@ -346,6 +346,47 @@ scm_i_make_with_fluids (size_t n, SCM *fluids, SCM *vals)
return ret;
}
+
+const int nguards = 10;
+SCM guards[10];
+SCM scm_i_make_with_special (size_t n, SCM *fluids, SCM *vals)
+{
+ SCM ret;
+ if(n nguards)
+scm_misc_error (with-special,
+ VM with-special can maximally be called with 10 slots,
+SCM_EOL);
+
+ /* Ensure that there are no duplicates in the fluids set -- an N^2 operation,
+ but N will usually be
Re: Special variables to relax boxing
Hi guiler, Hi Daniel. I lost this thread in my mail application, sorry, so I try to continue this way instead. * This feature for scheme is mainly for macro writers which knows what they are doing and which only guard state varibles not seen to the application programmer. This is how I use this feature in guile-log so it will not change how most people need to reason about scheme, the beuty remains. It makes insanly difficult tasks possible and simple things works as before. * I really like guile to cater for advanced users. Not only noobs. Although we should hide this feature really deep and put some serious warnings in the documentatin about the use. I actually hate using set! and if you look at e.g. guile-syntax-parse you will see that I rewrote everything with let loops, e.g. I really prefere that way of looping. I do understand your worry to let people loose on writing set! heavy code - that is not scheme. I also ported common lisp code to scheme and It was a horrible experience to see all set! ing in the code and I just had to rewrite quite a lot of the common lisp with rewriting the loops. But then a new version comes out and you are smoked. * If we are serious about combining emacs-lisp with guile we should really aim to have this feature added with deep support. The reason is that using set! in lisp world is a style of programming and is very common. For this reason I don't expect much emacs-lisp to combine well with undo redo additions via prompts. This hearts me really hard because it would be so cool to be able and schime in to a emacs-lisp project, add a few lines of code and show of a well functioning redo and undo addition to the complex emacs lisp code - this would be a really good selling point for guile-emacs and as I said, I hate that we don't have a nice support for it. * The proposed semantics piggy packs ontop of fluids sematics so everything we have done incorporating fluids carry over directly to special variables. And the extra stuff is really not that much. E.g. the maintainance burden is probably much less that your perception of it. * We need 2 extra VM op's if we are serious ablut implementing this though but they are simply essentially a copy paste of the fluid code so one could factor out the code somewhat. Another possibility is to add an option to the current fluid vm ops. * If you don't redo and undo nothing in the way scheme works changes it's only when you undo and redo stuff that the semantics becomes important. I really think that this is an important addition of guile and it would really be a dissapointment not having it's support considering the great gain you can get via optimizations with really not much extra work in guile. Also I think that I managed to get the semantics and implementation in a really beutiful state where a lot of effort have been in making it mix well and be consistant in what it does and actually get it into a state where it _is_ much simpler to reason about the code considering other way's of implementing the optimisations. Albait more difficult than before. Have fun /Stefan
Re: Special variables to relax boxing
Ok, I have felt your punches against the idea and have thought about it somewhat more. 1. I can only conclude that today it's already difficult to reason about code with respect to multiple restarts of continuation and the main reason is that at least I have been sloppy to add a ! to the macros that use set! internally. To a fun example: I have been pondering to poer common-lisp iterate for fun to learn and enjoy guile. In there they have generators e.g. (generati i ...) and then take out the values with (next i) construct. For a simple i = 1 ... one would expand next i to (begin (set! i (+ i 1)) i). So next is really next!. So this will not mix well with undo and redo. It's possible to define i as a special variable though and you will get the feature of proper undo redo support but now another problem appears we will as Mark and Daniel introduce i into any uses of next i in user and can get hard to reason about properties when the value is put into a lambda. So next is not next or next! but what? maybe next~ To indicate that lambdas that include this must expect to mutate when one does a redo!. Conventions like this is problematic because coders will most certainly be sloppy to follow this convention resulting in a mess. One really long for a type system to help clarify the matters here. Typically macro writers that post a binding a, might want users to use the underlying a~, variable as well and it would probably be good practice to let users refer to this at will e.g. reference it with (~ a), set it with (set~ a 1) as well as (set! a 1) and refer to it with e.g. a just as ordinary scheme. I would suggest that both reference a variable with set!,a, and with set~, (~ a) should be an error. Otherwise if the macro writer manages the macro correct and basically uses a user guard that we should provide e.g. (with-user (a) user-code ...) especially this means that if a is set! ed then we know that redo undo cannot work and we will force the underlying variable to be a usual variable. To accomplish this I would formulate the semantics as follows. Consider * k, the r5rs continuation * dynamic-wind, r5rs dynamic wind with the addition that k is an argument to the rewinder. Introduce (with-special ((a:id kind:object) ...) code ...) and (set~ a:id v:obj) Let self identifying the dynamic wind object lexically Introduce (special-set! self k value) (special-ref self k) Also define (guard-special? k kind) A setter and a getter of an object indexed by self and k Then the semantic for with-special in guard mode would be (let ((last #f)) (dynamic-wind (lambda (k) (when (guard-special? k kind) (set! a (special-ref self k (lambda () (call-with-values (lambda () (begin code ...)) (lambda ret (set! last #t) (apply values ret (lambda (k . l) (unless last (special-set! self k a Guard mode is entered only if a is referenced with set~ and never with set! if it can be proved Otherwise guard mode is never entered. The semantics of set~ is the same as with set! otherwise. if with-special is not in guard-mode then it behaves just as (let () code ) I really hope that I mange to converge a good concept with this discussion! WDYT On Thu, Mar 21, 2013 at 8:03 PM, Mark H Weaver m...@netris.org wrote: Stefan, you're still describing your proposal in terms of low-level implementation details such as stacks. In the general case, we cannot store environment structures on the stack. Furthermore, in the general case *all* variables in scheme are bound to locations, not values. Only in special cases can we use stacks, and only in special cases can we avoid boxing variables. These are only _optimizations_. If you're serious about this proposal, please read sections 3.1 and 3.4 of the R5RS carefully. Explain your proposed _semantics_ (not the implementation details) in those terms, where *all* variables are bound to _locations_, and where there is no stack at all (everything is conceptually stored in a garbage-collected heap). We need to understand the *semantics* in the simplest possible terms before we even begin to think about how to implement it. Thanks, Mark
Logic programming with prompts
Dear friends, I think that the current state of guile is in a sad state for logic programming with prompts in guile. I really think that we should fix the most pressing issues or stop touting prompts as a way to implement logic programming and direct to kanren or guile-log instead. Issues. 1. with a prompt based solution fluids is the natural choice to implement backtracking logical variables. But the current fluid implementation is fundamentally broken with respect to undo and redo semantics and will haunt any project that want to have interactive logic reasoning implemented. It's possible to fix it in pure guile with a horrible complex solution and will lead to laughable performance. 2. with-fluids is not tail recursive. It is quite possible that project will fail due to burnout of the stack in current guile because of this. One probably cannot get kanrens great support for tail call's implemented but at-least reduce the total memory consumption quite significantly. 3. Speed, Logic programming in pure guile is currently 100x slower then than with e.g. gprolog. It can be imporved to 20x by using a C-based backend. It's possible to get down to 4x (with prompts) if we could have a fast C-call mechansim or support in the VM. 4. This is a less important issue. But in order to implement all logic constructs found in kanren with prompts you will need to be able to use a special-variables construct that i'm touting which is needed if one want to be able to undo and redo things. Regards Stefan
redo-safe-variables and redo-safe-parameters
Dear friends, 1. I will change the name special variables to redo-safe-variables. And the parameter semantic I'm using to redo safe parameters. Itis clumsy but descriptive. 2. To implement these in a good way we need to touch the fundamentals of scheme. If we want to. But the concept is difficult and it is therefore wise to try to lift it as an srfi spec so that rthe whole scheme commmunity can take advantage of the concept and also help design it. 3. Before sending it to them I will ask you to comment on the idea and perhaps help a little to get the spec into a form that does not make me look like a fool and so that I don't step on any of you huy's toes. 4. I will wait to send it until the next version of guile is outr and people can sit down and read it. Here is my draft: - Dear editors of srfi, Authors background: I'm an active developer of scheme centered around the guile scheme ecosystem and the developer of guile-log, a logic programming system on top of guile. The background of the proposal. The background has a plurality of origins that converged into one concept. 1. Current scheme is a beautiful language but has a drawback. If you set! a variable that variable will be boxed and any uses of undo/redo semantic becomes broken. This is not acute in scheme because we try to avoid set! and that is well. But there are cases where you would like to use set!. One example being utilizing a simple generator e.g. (next! n) - (begin (set! n (+ n 1)) n) This can many times be implemented efficiently and with a good semantic in a looping macro for example. To achieve that without using set! seams to be difficult and the resulting loop! macro will not mix well with trying to implement undo and redo features on top of the system. 2. Emacs lisp is coded very much in an imperative style and with guile we would like to sell guile scheme as a backend for emacs lisp and emacs as a whole. One of the selling point to do this could be that we could use continuations to seamlessly add undo redo like semantics to already written programs in emacs lisp. The problem is twofold here. i) Typically emacs variable are dynamical variables. Dynamic variables in scheme is modeled on parameters and they posses the property that for each dynamic state S and parameter p the evaluation of p under S is always the last value settedt e.g. it is working like a local variable in the S environment. Because each continuation get's it's own dynamic state dynamically, the possibility of freezing a state that can be restarted multiple times seams to be there. The problem is that a dynamic state can be referenced as a scheme object and used as the current state multiple times as well for the same continuation and hence we must overwrite the initial value at a normal return from the dynamic state and hence loose the ability to store and restore naturally. This property also prevent a possible optimization to store the parameter directly on the stack. ii) Scheme local variables does also show up in the compilation of emacs lisp to guile. The problem with this is that typically lisp programs in emacs is littered with set!-ing of local variables. And the semantic for this in scheme is to box them and again you loose the ability to redo and undo without a hefty reprogramming or write an advanced compiler to scheme - which is typically not a beautiful solution. Again a good concept for enabling seamless and efficient and well designed code that can be undone and redone multiple times is needed. 3. Guile log is a combination of both traditional stack based logic programming concept and the kanren concept and together with a separate continuation implementation targeted for logical variables. To be able to code all of kanrens concept including a stack as well for speed and extra semantics like easy tracing or more generally to have a dynamic-wind like idioms. The ability to redo and undo is really helpful and enables interesting logic programs to be written. So here it was found out that having variables that dynamically can change between behaving like normal variables or during other dynamical context behave like a state preserving variable. The problem is that everything was based on code living in C and a separate stack implementation. So in order to use less library code and take advantage of fundamental scheme concepts with classy implementation semantics. It is actually possible with current scheme + parameters to implement these concepts, but the code will be slow and risk to be hard to reason about. Rational for lifting this to a srfi request: The concept have been proven useful and also implementing this in the right way do touch the fundamentals of scheme in such a way that it , from the perspective of the author, that help from the greater scheme community to improve upon the idea into a good specification is a well tought
