Re: compiling the instructions of a simple vm into a function
There is two way to make a domain-specific language with a clojure back-end : - if you want the language to be an extension of Clojure, still to be used in a REPL or by clojure source - you write macros. That's what I call embedded. There is a lot of litterature on Embedded Domain Specific Language in functional languages. (A *lot* in Haskell, for example) In this situation, eval is most of the time evil. - you want to read instructions that are very far from Clojure in a file and execute them. (Your case, not by choice but because of the ICFP specs). Then, eval is necessary. But you have to call it only once per compiled function, ideally, and never while executing the code (for performance). In your situation, I would write (defn compile-instruction [instructions] ...) Then, when reading the instructions (let [compiled-function (eval (compile-instruction (read-file...)))] ... Then, eval is called once, just after reading and compiling. And compiled-function is a real Clojure function. Have fun, Nicolas. On Sat, Jun 19, 2010 at 3:39 AM, Eugen Dück eu...@dueck.org wrote: Thanks Nicolas, your first variant resembles the generated code much closer than my initial approach, which is great. I need the eval though, to be able to pass in non literals. In my real program I'm reading the instructions from a binary file. So if I want to be able to do something like this: (def three-instructions '([+ 2 3] [- 0 1] [+ 1 0])) (def compiled (compile-instructions three-instructions)) The macro would have to look like this: (defmacro compile-instructions [instructions] (let [memory (gensym memory-)] `(fn [~memory] ~@(map (fn [[op m1 m2]] `(aset ~memory ~m1 (~op (aget ~memory ~m1) (aget ~memory ~m2 (eval instructions) But I like your suggestion to turn it into a function even better: (defn compile-instructions [instructions] (let [memory (gensym memory-)] (eval `(fn [~memory] ~@(map (fn [[op m1 m2]] `(aset ~memory ~m1 (~op (aget ~memory ~m1) (aget ~memory ~m2 instructions) And (def compiled (compile-instructions three-instructions))) just works as before. So I guess macros don't add any value here. eval is evil, but eval is not evil is a compiler (you have to evaluate the code you read). However eval is evil again in an embedded compiler, when you use macro to extend Clojure. What do you mean by embedded compiler? Eugen -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.comclojure%2bunsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
compiling the instructions of a simple vm into a function
Recently, I implemented last year's ICFP problem. Part of it is writing a VM that consists of memory slots, some registers and input and input ports. It takes a list of instructions, works them off one after the other, reading from input or memory, calculating something and the changing registers or writing to memory or output. My implementation worked, but I wanted to make it faster, and thought compiling the instructions into a function using a macro could help. Indeed, my vm got 5 times faster, using arrays and an imperative style (generated by the compiler). But the macro I wrote is butt-ugly, so I thought I might get some advice on this list... To keep it simple I'll use an even simpler VM that only has memory and a simple instruction set. Example of an instruction: [+ 2 3] That means: read memory at address 2, read memory at address 3 and write the sum of both values back to address 2. This is how I use the compiler macro, feeding in 3 instructions: user= (def compiled (compile-instructions '([+ 2 3] [- 0 1] [+ 1 0]))) #'user/compiled user= (fn? compiled) true Now let's allocate an int array for the memory, using a size of 4 slots: user= (def memory (into-array Integer/TYPE (range 4))) #'user/memory user= (seq memory) (0 1 2 3) And now let's run the instructions on that memory: user= (compiled memory) 0 user= (seq memory) (-1 0 5 3) And finally, here comes the code for the macro - but be warned, I'm lacking formal macro education, which is why I'd appreciate any good comment: (defmacro compile-instructions [instructions] (let [memory (gensym memory-)] (apply list 'fn [memory] (map (fn [[op m1 m2]] (list aset memory m1 (list op (list aget memory m1) (list aget memory m2 (eval instructions) I'm not using the backtick as it seemed simpler for what I was trying to do. I don't know if eval is evil and there's a better alternative? I'm actually not so sure whether it is good to roll out all instructions for performance. It might makes things actually slower, as the JIT can compile less, apart from the fact that a Java method is limited to 64k in size, so the number of instructions I can compile is limited: user= (def compiled (compile-instructions (take 1150 (cycle '([+ 2 3] [- 0 1] [+ 1 0]) java.lang.ClassFormatError: Invalid method Code length 65581 in class file user$compiled__97 (NO_SOURCE_FILE:25) It blows up at just above 1k instructions. -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: compiling the instructions of a simple vm into a function
First a simple version, equivalent to yours but more readable. (defmacro compile-instructions [instructions] (let [memory (gensym memory-)] `(fn [~memory] ~@(map (fn [[op m1 m2]] `(aset ~memory ~m1 (~op (aget ~memory ~m1) (aget ~memory ~m2 instructions (def memory (into-array Integer/TYPE (range 4))) (def compiled (compile-instructions ([+ 2 3] [- 0 1] [+ 1 0]))) And another one to workaround the JVM 64K feature. I split the generated code into blocks of 500 instructions. (def length-threshold 500) (defmacro protected-fn [binding-form body] (if (= (count body) length-threshold) `(fn ~binding-form ~...@body) (let [small-funs (partition length-threshold length-threshold () body) let-block (map (fn [bod] (let [name (gensym let-)] [name `(fn [...@binding-form] ~@ bod)] )) small-funs)] `(let [~@(apply concat let-block)] (protected-fn [...@binding-form] ~@(map (fn [[name code]] `(~name ~...@binding-form)) let-block)) (defmacro compile-instructions-2 [instructions] (let [memory (gensym memory-)] `(protected-fn [~memory] ~@(map (fn [[op m1 m2]] `(aset ~memory ~m1 (~op (aget ~memory ~m1) (aget ~memory ~m2 instructions (def compiled-2 (eval `(compile-instructions-2 ~(take 1150 (cycle '([+ 2 3] [- 0 1] [+ 1 0])) This last line is quite ugly. In fact, if you want to use compile-instruction programatically, maybe it should not be a macro but a function. Then using a code-generating function in a macro is easy. Plus, it is easy to eval the generated code. But, be careful, you have to eval it once, just after the compiling phase. Then, you get a real function. eval is evil, but eval is not evil is a compiler (you have to evaluate the code you read). However eval is evil again in an embedded compiler, when you use macro to extend Clojure. -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: compiling the instructions of a simple vm into a function
Thanks Nicolas, your first variant resembles the generated code much closer than my initial approach, which is great. I need the eval though, to be able to pass in non literals. In my real program I'm reading the instructions from a binary file. So if I want to be able to do something like this: (def three-instructions '([+ 2 3] [- 0 1] [+ 1 0])) (def compiled (compile-instructions three-instructions)) The macro would have to look like this: (defmacro compile-instructions [instructions] (let [memory (gensym memory-)] `(fn [~memory] ~@(map (fn [[op m1 m2]] `(aset ~memory ~m1 (~op (aget ~memory ~m1) (aget ~memory ~m2 (eval instructions) But I like your suggestion to turn it into a function even better: (defn compile-instructions [instructions] (let [memory (gensym memory-)] (eval `(fn [~memory] ~@(map (fn [[op m1 m2]] `(aset ~memory ~m1 (~op (aget ~memory ~m1) (aget ~memory ~m2 instructions) And (def compiled (compile-instructions three-instructions))) just works as before. So I guess macros don't add any value here. eval is evil, but eval is not evil is a compiler (you have to evaluate the code you read). However eval is evil again in an embedded compiler, when you use macro to extend Clojure. What do you mean by embedded compiler? Eugen -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
