Re: [Chicken-users] optimizing mutually recursive loops
[cunning optimisation stunts] Some would say that the matrix multiply should just be written in C and FFIed. Some would say that Chicken should be improved until you can write natural Scheme code without a thought for performance, and Chicken should general optimal C as good as any human could handcode (although they may get a bit vague and hand-wavey as to how this might be accomplished). But finding middle grounds is interesting; Alex has found one by bending Chicken to his will cunningly. I wonder, though, how this can be generalised a bit, since I have an instinctive distaste for specific hacks: a let-machine is, in a way, a little subset of Scheme that can be implemented particularly efficiently by Chicken. Now I, in my own work, have sometimes had to implement low-level operations involving binary data, and I've hankered for a way to do them more efficiently in Scheme so I don't have to go into C so often. What I've been thinking of is somewhat similar in execution, but first a history lesson... One of my inspirations in programming language technology (other than Lisp) is Concurrent Clean, a Haskell-like purely functional language that, unlike Haskell, implements mutating operations (non-copying array ops, I/O, that sort of thing) using uniqueness typing. Basically, if an object like an array passed into an array-set! style function can be shown by the type system to be the only reference to that object in the system, then array-set! can modify it in-place and return the 'same' array with a new value, while still being a pure function. If you pass it in a non-unique reference, then it has to make a copy of the array to mutate and return. As well as implementing efficient updates on large arrays, this is also used for I/O; a top-level Clean program is a function of type Unique World -> Unique World. And the system provides a number of operations on type World, each of which require a unique reference to the World and return a unique reference to a World. Eg, there's a function that takes a World and a string, and returns a new World in which that string has been displayed on a display device somewhere; and a function that takes a World and returns a string and a World in which some time has passed and somebody has typed that string in and pressed enter... in effect, the entire universe is encapsulated in a logical object so the program can 'mutate' it using the same trick. But because the functions that accept Worlds all require them to be unique, the type system forces the program to only ever have a single World; if you try and keep a reference to a particular state of the World then it stops being unique, so your program gives a compile-time type error when you try and use that World or return it from 'main'. Anyway, you can write imperative-style code in Clean, but it looks a bit ugly. I can't remember the exact syntax, but in spirit, you end up with: SayHello :: !World -> !World SayHello World = let World2 = printString (World, "Please enter your name") in let World3, Name = inputString (World2) in printString (World3, "Hello, " + Name) This has benefits over monads - for a start, you can compose them in parallel; your program might have regions that mutate some array, and regions that mutate the world, and those two bits can be interleaved; while in Haskell you can only do this by bunging everything into a single IO monad, which ends up enforcing more sequentiality than is needed (subject only to actual data-flow requirements between the two "threads", the Clean compiler has more scope to rearrange or parallelise stuff). And it's really neat in that unique values don't need garbage collection. A function that takes an object and doesn't return it (in any form), if it's given a unique value, knows it never needs it again. Functions that require unique arguments can just hardcode deallocation; functions that might take a unique argument can, if they destroy their reference to it, do an "if unique then deallocate" operation reminiscent of a reference count decrement. Only shared values are prone to garbage collection, and if the compiler can correctly deduce the uniqueness of lots of data, that's lots of gc overhead removed. Anyway. Having noticed that the recursive-lets-with-new-names syntax sucked, I followed a chain of thought as to how I'd improve it. 1) I don't know why the examples I saw used a new name for the World each time - surely the nesting lexical scopes of the lets would let you write: let World = printString (World, "Please enter your name") in ... and keep things neater? 2) Isn't a mutually-recursive set of functions passing unique values between themselves just a state machine in register transfer language, and thus really trivial to implement efficiently? Now, I have a theory that state machines are a really good syntax for imperative stuff. Structured programming has put goto out of fashion, but used properly it was a good thing; the problem was that pe
Re: [Chicken-users] optimizing mutually recursive loops
Alaric Snell-Pym wrote: Some would say that the matrix multiply should just be written in C and FFIed. In fact, most would just (use blas) or such. But I understand it was just an example. Concurrent Clean, a Haskell-like purely functional language that, unlike Haskell, implements mutating operations using uniqueness typing. I'm wondering whether we could apply a similar idea to Chicken. Do you think there is any space for improvement, where we could somehow reduce GC by declaring stuff as unique? I know I'm just hand-waving at this point, I need to think more about it. Any complex imperative algorithm involves a certain number of nested control structures, and before long, you need to add a single extra arc to that. This is quite true and I've found Scheme's named let an excellent syntax for this kind of algorithm. You can just write the loops in the natural order of variable declaration, and then jump back and forth as you need: "Oh, I'll just restart with the 2nd outer loop here: (loop- row x (+ y 1))." In fact, I've been writing "named loops" in other languages too, where the language lets me do it... which means, if it has a syntax for lambdas. But they never come out as nicely as in Scheme. But written as a state machine, such extra control flow arcs are easy to add. I've been meaning for some time to experiment with writing Scheme macros that implement a state machine language designed for ease of use, and experimenting with using them. Nice! Do you have any prototype we could play with, or ideas we could discuss? -Tobia ___ Chicken-users mailing list Chicken-users@nongnu.org http://lists.nongnu.org/mailman/listinfo/chicken-users
Re: [Chicken-users] optimizing mutually recursive loops
On Mon, Feb 16, 2009 at 8:32 AM, Alex Shinn wrote: > When optimizing my Chicken code for speed, I find one of the > most important things is to write the code so that it gets > compiled into a single C function with gotos. It's often so > important to get this that I end up writing very unnatural > Scheme code, including manually combining several loops into > one. > This can be done by the chicken optimizer, but it's not trivial - checking for a node-tree to have the proper form and rearranging everything on that level is work-intensive. I'll try to think about this a bit more. cheers, felix ___ Chicken-users mailing list Chicken-users@nongnu.org http://lists.nongnu.org/mailman/listinfo/chicken-users
Re: [Chicken-users] optimizing mutually recursive loops
On 16 Feb 2009, at 5:09 pm, Tobia Conforto wrote: Alaric Snell-Pym wrote: Some would say that the matrix multiply should just be written in C and FFIed. In fact, most would just (use blas) or such. But I understand it was just an example. Well, yeah ;-) Concurrent Clean, a Haskell-like purely functional language that, unlike Haskell, implements mutating operations using uniqueness typing. I'm wondering whether we could apply a similar idea to Chicken. Do you think there is any space for improvement, where we could somehow reduce GC by declaring stuff as unique? I know I'm just hand-waving at this point, I need to think more about it. Quite possibly. In fact, Henry Baker (who wrote the paper on the Cheney MTA algorithm Chicken uses) has papers on the topic of Linear Lisp - see the references at http://en.wikipedia.org/wiki/Uniqueness_typing#Discussions_of_uniqueness_typing_in_programming_languages Any complex imperative algorithm involves a certain number of nested control structures, and before long, you need to add a single extra arc to that. This is quite true and I've found Scheme's named let an excellent syntax for this kind of algorithm. You can just write the loops in the natural order of variable declaration, and then jump back and forth as you need: "Oh, I'll just restart with the 2nd outer loop here: (loop-row x (+ y 1))." In fact, I've been writing "named loops" in other languages too, where the language lets me do it... which means, if it has a syntax for lambdas. But they never come out as nicely as in Scheme. Yeah! I've made delightful use of escape continuations in the command line interface for Ugarit. My core command line function presents a prompt and processes what the user inputs; if this is a "cd" then it recurses to work in the subdirectory, while "cd .." returns; other commands just tail-call the CLI function again, but "quit" escapes the whole lot by just calling a continuation established by a top-level let/cc. This made for a very natural structure; similar code in C I've written always seems to involve a boolean flag that requires sometimes complex handling... But written as a state machine, such extra control flow arcs are easy to add. I've been meaning for some time to experiment with writing Scheme macros that implement a state machine language designed for ease of use, and experimenting with using them. Nice! Do you have any prototype we could play with, or ideas we could discuss? No prototype, but lots of ideas: 1) Each state should be parameterised. This is a trick to convert a system of "state machine plus mutable memory" to just "state machine" - basically, you describe potentially infinite families of states in a single rule by giving the rule parameters. Rather than having mutable variables, you just pass parameters to states, and to "modify" them they just pass new values on to the next state (or to themselves, if looping). This reduces the state machine to a set of mutually recursive pure functions, and the uniqueness just removes the need for GC and opens up implementation as a set of registers. 2) Yet it'd also be nice to automate some of this by establishing a group of states as a form of "lexical scope", declaring some state variables for that scope, and having the states within that scope, when they call each other, automatically passing any variables they don't explicitly pass. An example might make that clear. Say your state machine, from time to time, has to do something a hundred times. So you might have a parameterised state that does something N times. Say this thing has several steps - the steps would have to pass N around between themselves so the last state can jump back to the original state, passing in N-1. But that might get tiresome - it'd be nice to write: (let (N) step1: ... ... ... (goto step2) step2: ... ... ... (goto step3) step3: ... ... ... (if (zero? N) (goto ...exit...) (goto step1 N: (- N 1))) Eg, N is being automatically passed along when step2 calls step3 (the initial entry to step1, being from outside the 'scope', must pass it in explicitly, of course); but step3 explicitly gives a value for N, which is then used. I don't know if this is a good idea or not - hidden state can be bad, and it requires keyword-style arguments to states, which may be more pain than it's worth. 2) How about reuse of portions of state machines? They should allow some kind of lexical scope, too. A complex set of states should be packagable into a black box with a set of defined entry states, and "dangling pointers" out to exit states that must be supplied when the package is used, in effect providing enough exit continuations with the correct signatures. It's not quite like a closure, since it might have several entry states. But perhaps that's not important and it should just be called a closure? Really, I need to work on some examples and work on a synt
Re: [Chicken-users] optimizing mutually recursive loops
On Tue, Feb 17, 2009 at 04:27:40PM +, Alaric Snell-Pym wrote: > 2) Yet it'd also be nice to automate some of this by establishing a > group of states as a form of "lexical scope", declaring some state > variables for that scope, and having the states within that scope, > when they call each other, automatically passing any variables they > don't explicitly pass. ...example elided... > I don't know if this is a good idea or not - hidden state can be bad, > and it requires keyword-style arguments to states, which may be more > pain than it's worth. Have you considered using SRFI-39 parameter objects? I think those give you precisely what you need - invisible parameters you don't need to pass every time you call a procedure that might need it. (can you tell I'm a parameter fanboy? :) ) I don't think "parameterize" is tail-recursive (it uses dynamic-wind), so if you expect procedure calls to be nested deeply, this might not be an option. > 2) How about reuse of portions of state machines? They should allow > some kind of lexical scope, too. A complex set of states should be > packagable into a black box with a set of defined entry states, and > "dangling pointers" out to exit states that must be supplied when the > package is used, in effect providing enough exit continuations with > the correct signatures. It's not quite like a closure, since it might > have several entry states. But perhaps that's not important and it > should just be called a closure? Or a module, perhaps? I guess it depends on whether it has any runtime state that it needs to keep. Cheers, Peter -- http://sjamaan.ath.cx -- "The process of preparing programs for a digital computer is especially attractive, not only because it can be economically and scientifically rewarding, but also because it can be an aesthetic experience much like composing poetry or music." -- Donald Knuth pgp9ouvcuc7m4.pgp Description: PGP signature ___ Chicken-users mailing list Chicken-users@nongnu.org http://lists.nongnu.org/mailman/listinfo/chicken-users
Re: [Chicken-users] optimizing mutually recursive loops
Peter Bex scripsit: > I don't think "parameterize" is tail-recursive (it uses dynamic-wind), > so if you expect procedure calls to be nested deeply, this might not be > an option. It is possible to have dynamic binding and tail recursion at the same time, though: see http://www.accesscom.com/~darius/writings/dynatail.html for the general scheme. -- John Cowanhttp://ccil.org/~cowanco...@ccil.org SAXParserFactory [is] a hideous, evil monstrosity of a class that should be hung, shot, beheaded, drawn and quartered, burned at the stake, buried in unconsecrated ground, dug up, cremated, and the ashes tossed in the Tiber while the complete cast of Wicked sings "Ding dong, the witch is dead." --Elliotte Rusty Harold on xml-dev ___ Chicken-users mailing list Chicken-users@nongnu.org http://lists.nongnu.org/mailman/listinfo/chicken-users
Re: [Chicken-users] optimizing mutually recursive loops
On Tue, Feb 17, 2009 at 9:36 PM, John Cowan wrote: > >> I don't think "parameterize" is tail-recursive (it uses dynamic-wind), >> so if you expect procedure calls to be nested deeply, this might not be >> an option. > > It is possible to have dynamic binding and tail recursion at the same > time, though: see http://www.accesscom.com/~darius/writings/dynatail.html > for the general scheme. Even if you make dynamic-wind tail-recursive (which isn't that trivial), it will still allocate storage for pending thunks. cheers, felix ___ Chicken-users mailing list Chicken-users@nongnu.org http://lists.nongnu.org/mailman/listinfo/chicken-users
