Idea for algorithm for renaming in an Clojure IDE
I was thinking about how things like function or variable renaming are complicated by lisps macros. That it's almost impossible to track the scope of anything, since 2 symbols near each other might mean completely different things after macro expansion. So I came up with an algorithm that *might* work in the most common case. Is there a flaw in the idea, or did I overlook any major aspect of the language? Any idea of which IDE would be the best to try and prototype it? Here it is in pseudocode: select symbol in source that you want to rename parse the code add tracking meta-data (file, line, position in line) into all symbols of the tree expand all macros find selected symbol: it's either a definition in a def form or let* or letfn form, or a variable being used if the symbol is a definition, find all places where it is used, taking scope into account use metadata to find where the symbol was in the source code if it wasn't, it means a macro expanded it into place, so fail else rename it if the symbol is a variable, find where it was defined, taking scope into account use metadata to rename it, if there is none, fail find all symbols that refer to the definition, rename if there is metadata, fail otherwise -- 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: Regarding lexical scoping and usage of 'let' in a recursive function call
Well, a more important matter, this example in the documentation of
atom is wrong!
The recursive calls will not be memoized if called like that. Running
this code clearly shows:
(defn memoize [f]
(let [mem (atom {})]
(fn [ args]
(if-let [e (find @mem args)]
(val e)
(let [ret (apply f args)]
(swap! mem assoc args ret)
ret)
(defn fib [n]
(if (= n 1)
n
(+ (fib (dec n)) (fib (- n 2)
(time (fib 35))
user= Elapsed time: 1218.15834 msecs
(def fib (memoize fib))
(time (fib 35))
user= Elapsed time: 953.94816 msecs
I believe this is caused because defn creates a named fn:
user= (macroexpand '(defn fib [n]
(if (= n 1)
n
(+ (fib (dec n)) (fib (- n 2))
(def fib (.withMeta (clojure.core/fn fib ([n] (if (= n 1) n (+ (fib
(dec n)) (fib (- n 2)) (.meta (var fib
So the recursive call don't go through the global user/fib that has
been memoized, but by the local fib which hasn't.
So a correct way to write it would be:
(defn fib [n]
(if (= n 1)
n
(+ (user/fib (dec n)) (user/fib (- n 2)
(def fib (memoize fib))
(time (fib 35))
user= Elapsed time: 0.814599 msecs
By fully qualifying the recursive call, it forces it to use the global
var, memoizing all the recursive calls.
This example should be corrected.
On Nov 12, 2:13 pm, Joseph Smith j...@uwcreations.com wrote:
In this case 'memoize' returns a memoized version of the function 'f', which
closes over 'mem'. Each time 'memoize' is called a new atom is created, not
each time the function it returns is called.
---
Joseph Smith
j...@uwcreations.com
On Nov 11, 2010, at 2:06 PM, Manoj wrote:
I am a newbie to Clojure, so have some confusion around lexical
scoping especially when let is used in a recursive function call. To
be more precise, I am taking the example memoize() function used for
explaining the concept of atom at clojure.org.
Here is how it is explained:
(defn memoize [f]
(let [mem (atom {})]
(fn [ args]
(if-let [e (find @mem args)]
(val e)
(let [ret (apply f args)]
(swap! mem assoc args ret)
ret)
(defn fib [n]
(if (= n 1)
n
(+ (fib (dec n)) (fib (- n 2)
(time (fib 35))
user= Elapsed time: 941.445 msecs
(def fib (memoize fib))
(time (fib 35))
user= Elapsed time: 0.044 msecs
My question is when let is used in this context, wouldn't it create
a fresh binding to a new atom{}? Any explanation would be highly
appreciated.
Thanks.
--
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
--
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: Confused about =, native java arrays and seqs...
Arrays are mutable, seqs immutable. Clojure ='s compares immutable structures by value, and mutable structures by reference (for the objects that it is aware of, for others it just prays that they have a resoanable equals method). This behaviour is described in the very interisting Henry Baker's egal Paper, and yields the cleanest equality semantics that I know of. On 23 mar, 14:24, Frank Siebenlist frank.siebenl...@gmail.com wrote: My REPL shows: ... user (= (bytes (.getBytes a))(bytes (.getBytes a))) false user (= (seq (bytes (.getBytes a))) (seq (bytes (.getBytes a true ... in other words, equality for java byte arrays is defined differently than their seq'ed version. It seems that the native arrays are compared on their reference while the seq'ed version on their value (as it should...). Sometimes the seq'ing seems implied, however, like in: ... user (first (bytes (.getBytes a))) 97 ... but for the = function it is not. This doesn't feel right and is confusing to say the least. Could anyone shed some light on this behaviour? Thanks, Frank. -- 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 To unsubscribe from this group, send email to clojure+unsubscribegooglegroups.com or reply to this email with the words REMOVE ME as the subject.
Re: bounded memoize
On 8 mar, 23:22, Michał Marczyk michal.marc...@gmail.com wrote: I'd suggest a vector instead; they're countable in constant time and you can use, say, conj and rest for add to end of queue / eject from front of queue. Conj adds to the end of a vector in constant time, but rest will not return another vector, but a sequence. Converting that sequence into another vector will take O(n). If you want queueing behaviour, you should use a clojure.lang.PersistentQueue: (- clojure.lang.PersistentQueue/EMPTY (conj 5) (conj 7) pop (conj 8) peek) -- 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
Defn-memo doesn't work for recursive functions
;Simple example (defn fib1 [n] (if (or (= 0 n) (= 1 n)) 1 (+ (fib1 (- n 1)) (fib1 (- n 2) (defn-memo fib2 [n] (if (or (= 0 n) (= 1 n)) 1 (+ (fib2 (- n 1)) (fib2 (- n 2) ;workaround for this problem (declare aux-fib) (defn-memo fib3 [n] (if (or (= 0 n) (= 1 n)) 1 (+ (aux-fib (- n 1)) (aux-fib (- n 2) (def aux-fib fib3) (time (fib1 35)) Elapsed time: 4729.9318 msecs 14930352 = (time (fib2 35)) Elapsed time: 4727.70348 msecs 14930352 = (time (fib3 35)) Elapsed time: 0.875 msecs 14930352 The recursive call inside fib2 is not memoized because of the way Clojure expands defn, adding the function name to the generated fn. So, how to rewrite defn-memo so that fib2 behaves like fib3? It would be much easier to make defn stop adding the function name to the fn, but that makes normal recursive functions a little slower, and would change the behaviour if dynamic scoping was being used in a program. The problem is that if you change defn-memo so that it doesn't use defn, you lose all of defn goodness or have to reproduce all of defn's work inside of defn-memo. Memoization of recursive functions is very useful, with problems that are normally solved with dynamic program becoming much simpler and functional when used. Any idea on how to rewrite defn-memo so that it does the right thing? -- 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: Interesting ICFP slides from Guy Steele -- Organizing Functional Code for Parallel Execution
What he said is basically right, only instead of list it's called vector. Not sure if vector branching is 64 or 32. On 10 fev, 15:42, Paul Mooser taron...@gmail.com wrote: I ran across this on reddit this morning, and thought people on the group might find it interesting: http://docs.google.com/viewer?url=http%3A%2F%2Fresearch.sun.com%2Fpro... It actually mentions clojure briefly at the end, although I'm not sure what it said was right (that lists were represented as trees in clojure). Nonetheless, the slide deck is pretty interesting. -- 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: Clojure Scoping Rules
Would it be possible to create an implementation of delay and lazy-seq that didn't use fn to delay evaluation, or atleast captured dynamic variables? (delay (+ x 3)) reasonable semantics in current clojure (let [x x] (delay (+ x 3))) (delay (fn [y] (+ x y))) semantics should be the same it already is (x should get it's value from the dynamic binding) (delay [x (fn [y] (+ x y))]) semantics should be (let [G_N x] (delay [G_N (fn [y] (+ x y))])), so all captured variables would need renaming using gensyms. delay would need it's body macroexpanded code to be able to correctly capture variables. It would also try to capture local variables, but that wouldn't change the semantics and would probably be optimized away by the compiler. I might have missed some important detail, since dynamic binding and lazyness have such a peculiar semantics interaction, but it would yield much more reasoanable execution, wouldn't it? -- 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: Gensym collisions can be engineered.
It's one thing to try to protect the programmer from accidentally shooting himself on the foot, but I don't think it is as necessary for a language to prevent him from doing it on purpose. On 8 nov, 02:59, John Harrop jharrop...@gmail.com wrote: user= (def q 'G__723) #'user/q user= (def r (gensym)) #'user/r user= q G__723 user= r G__723 user= (= q r) true It's possible to anticipate the next gensym name that will be generated and then engineer a collision, and therefore possibly variable capture unintended by the author of a macro. It looks like manually generating a name does not remove it from the pool of allowable future gensym names. This shouldn't tend to cause accidental problems in practice, since gensym names tend not to collide with the kinds of identifiers programmers ordinarily use. Nonetheless it can be partially fixed comparatively easily by adding to the runtime a WeakHashMap into which a reference to any symbol, however created, is placed and modifying the gensym-generator to, at the point where it currently returns a value, first check if the WeakHashMap contains it already and if so, generate the next one, and the next, as needed until it gets a not-in-use name. This requires gensym creation and normal symbol creation to occur in a global lock but symbol creation rarely occurs at runtime and even more rarely in any kind of hot-spot at runtime. The use of WeakHashMap would prevent the runtime clogging up with ungarbagecollectable symbols, so the memory overhead of adding this would be smallish, one machine pointer per in-use symbol or so, equivalent to if every symbol had a few more characters in its name. This would stop gensym from producing a name already in use. It wouldn't prevent a gensym being generated somewhere and *then* the identical name being put together someplace else and passed to the symbol function, though; a small loophole. Collisions between gensyms in preexisting code and an enclosing lexical scope in new code would become impossible, but collisions between gensyms in preexisting code and an enclosed lexical scope (e.g. a macro-invocation body, such as a loop body) would remain theoretically possible. That last loophole can't really be plugged without giving Clojure true gensyms (uninterned anywhere), which would bring with it its own architectural problems. If that change were made, the above REPL interaction would be possible up to the (= q r) evaluation, but that would return false despite the names looking the same, so the symbols wouldn't really collide even though a collision of their printed representations could still be engineered. One bothersome consequence though would be that the textual output of macroexpand-1 could no longer always be substituted for a macro call in source code without altering the run-time semantics of that code, even when the macro's expansion-generation does not have side effects. (To reproduce that REPL interaction for yourself, evaluate (gensym) at the REPL and note the number. Add seven and then evaluate (def q 'G__#) with # replaced with the sum. Then evaluate (def r (gensym)) and, if you like, skip straight to (= q r). If that doesn't work, the number it goes up by must have changed between Clojure 1.0 and whatever version you're using; evaluate (gensym), then (def q 'xyzzy), then (gensym) again and note the increment and use that instead of seven. Oh, and don't have any background threads running in that JVM instance that might do something autonomously that causes a gensym to be generated.) --~--~-~--~~~---~--~~ 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: Proposal: New Reader Macro #s{ ... }
Lua's solution to long strings is having multiple levels of delimiters. [[ is the opening delimiter of level 0, and is closed by ]] . [=[ is of level 1, closed by ]=] , etc. No matter what string you are trying to represent, it can always be literally represented that way. On 12 out, 17:25, Greg g...@kinostudios.com wrote: Ah, I think I understand... but if you're saying that this should be something that can be done on an individual basis I think that's a bad idea, it would lead to confusing looking code and inconsistencies. There should be an officially sanctioned .. whatever it is this thing is called. That way whenever you look at someone else's code and see it, you know what it is, and people can update their code parser's/ syntax highlighters appropriately. - Greg On Oct 12, 2009, at 2:59 PM, DanL wrote: On 12 Okt., 20:46, Greg g...@kinostudios.com wrote: Forgive me, but I'm unfamiliar with the readtable, are you just referring to where this syntax might be implemented? Or are you suggesting an alternative syntax? I'm suggesting that the readtable might be exposed to user changes as it is in CL, but only if a means of managing different readtables is provided, hence the link pointing to named-readtables, which allows just that (naming and merging readtables using an API resembling the package API). This would allow introduction of new reader macros by the user. As I said, there already was some discussion on that topic, but I just have played around with named-readtables since the new release and came to the conclusion, that something akin to them might be nice in clojure, too. Things like heredocs are not something that every user needs every day, so they would, IMHO, be a good candidate for a user readmacro. Regards, dhl --~--~-~--~~~---~--~~ 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: Is apply slow or am I incorrectly benchmarking this?
If efficiency is really an issue (if it's not just use apply), how about using a macro for doing the dirty work of writing the direct function application for you? On 20 maio, 19:44, CuppoJava patrickli_2...@hotmail.com wrote: Thanks a lot for that really detailed analysis Stephen. I do find apply very convenient in a lot of cases, and am using it to save a line or two of code whenever I can. But after seeing this benchmark, I think I shall be more disciplined about my use of it. Especially in the case where the number of arguments of known, I can it's better to use the direction function application, even if it requires a little more typing. That seems to be a very useful tool. I'm gonna keep YourKit in mind in the future. Thanks again -Patrick --~--~-~--~~~---~--~~ 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 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 -~--~~~~--~~--~--~---
Amb operator
So, I was wondering if anyone had implemented the amb operator in Clojure, so I decided to give it a try. This is my first Clojure program bigger then 5 lines, the code still needs ALOT of work, it is ugly as hell atm, but I think it kind of works. (Yes, I know, it's very easy to bug it, its just a sketch). Notice that unlike most continuation based amb operators, the amount of backtracking this implementation has to do depends on the order of the requires, not the amb assignments. If anyone wants to clear or improve the code, go ahead. I also would like to know how to be able to write @baker instead of the current (myderef baker), I tried using a proxy and implementing IDeref, but then I couldn't acess the amb-struct private data. Since Clojure doesn't have continuations I had to use a try catch block to do the stack unwinding, and some redundant calculations might be done because of it. Here is the code: (defstruct amb-struct :instance :orig :possible) (def amb-stack nil) (defn amb [choices] (struct-map amb-struct :instance false :orig choices :possible choices)) (defn myderef [a] (if (:instance @a) (:value @a) (do (set! amb-stack (cons a amb-stack)) (let [oldpos (:possible @a)] (var-set a (assoc @a :value (first oldpos) :instance true :possible (rest oldpos (:value @a (defn amb-require [condition] (if condition nil (do (throw (.Exception nothing) (defn bindnext [] (if (empty? amb-stack) 'nomatchfound (let [lastbind (first amb-stack) oldpos (:possible @lastbind)] (if (empty? oldpos) (do (var-set lastbind (assoc @lastbind :instance false :possible (:orig @lastbind))) (set! amb-stack (rest amb-stack)) (recur)) (do (var-set lastbind (assoc @lastbind :value (first oldpos) :possible (rest oldpos))) 'recur) (defmacro amb-let [declarations body] `(with-local-vars ~declarations (binding [amb-stack nil] (loop [] (let [retvalue# (try (do ~...@body) (catch Exception ~'except (bindnext)))] (cond (= retvalue# 'recur) (recur) true retvalue#)) (defn distinct-seq? [s] (cond (empty? (rest s)) true (= (first s) (second s)) false true (and (distinct-seq? (cons (first s) (rest (rest s (distinct-seq? (rest s) (amb-let [baker (amb [1 2 3 4 5]) cooper (amb [1 2 3 4 5]) fletcher (amb [1 2 3 4 5]) miller (amb [1 2 3 4 5]) smith (amb [1 2 3 4 5])] (amb-require (distinct-seq? (map myderef (list baker cooper fletcher miller smith (amb-require (not (= (myderef baker) 5))) (amb-require (not (= (myderef cooper) 1))) (amb-require (not (= (myderef fletcher) 1))) (amb-require (not (= (myderef fletcher) 5))) (amb-require ( (myderef miller) (myderef cooper))) (amb-require (not (= 1 (. java.lang.Math abs (- (myderef smith) (myderef fletcher)) (amb-require (not (= 1 (. java.lang.Math abs (- (myderef fletcher) (myderef cooper)) [['baker (myderef baker)] ['cooper (myderef cooper)] ['fletcher (myderef fletcher)] ['miller (myderef miller)] ['smith (myderef smith)]]) Running it returns [[baker 3] [cooper 2] [fletcher 4] [miller 5] [smith 1]] --~--~-~--~~~---~--~~ 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 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: doseq vs. map
Laziness is the rule only on sequence operations. On Apr 2, 11:34 pm, Sean francoisdev...@gmail.com wrote: Thanks for the response everyone! I was able to get it working. If I understand what everyone is saying, the following statement is true: In Clojure, laziness is the rule not the exception. --~--~-~--~~~---~--~~ 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 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 -~--~~~~--~~--~--~---
