[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 people used goto for large-scale program structure, which was too large a scope for a human to keep track of what's what, leading to the fabled spaghetti code. But the baby was thrown out with the bath water. 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. "Oh, in this case, we need to go and restart from this point up here". At which point, you need to rearrange the whole thing in order to fit the new structure. This is particularly obvious in exception handling; C programmers often have to resort to a "cleanup:" label at the end of a function that they can goto, which exceptions are to some extent syntactic sugar for. But written as a state machine, such extra control flow arcs are easy to add. So, these two threads have been bubbling around in my head, and 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. Obviously, I was just going to make them generate letrecs, since I was interested in designing a structure that I knew *could* be implemented efficiently if made a special form, rather than actually trying to get Chicken to be efficient, but that's by the by; if I came up with a syntax that was elegant, we could look at an efficient implementation later - perhaps even one that the chicken core knows about (or, more likely, that compiles to a low- level special form that just handles generating a set of goto-able labels and gotos between them). ABS -- Alaric Snell-Pym Work: http://www.snell-systems.co.uk/ Play: http://www.snell-pym.org.uk/alaric/ Blog: http://www.snell-pym.org.uk/?author=4 _______________________________________________ Chicken-users mailing list Chicken-users@nongnu.org http://lists.nongnu.org/mailman/listinfo/chicken-users