I am working through http://www.haskell.org/tmrwiki/
WhyAttributeGrammarsMatter in lisp, and I am encountering circular code
like:
diff :: [Float] -> [Float]
diff xs =
let
nil avg = (0.0, 0.0, [])
cons x fs avg = let (s,l,ds) = fs avg
in (s+x,l+1.0,x-avg : ds)
(sum,length,ds) = foldr cons nil xs (sum / length)
in ds
We all know lisp is eager, but I was wondering if there was a cleaner way
to translate it than the following:
(defmacro delay (&body body) `(lambda () ,@body))
(defun force (expr) (funcall expr))
(defun diff2 (l)
(let* ((avg (cons nil nil))
(init (lambda (avg) `#(0.0 0.0 ,(delay nil))))
(comb (lambda (n fs)
(lambda (avg)
(let ((tup (funcall fs avg)))
(vector (+ n (elt tup 0))
(+ 1 (elt tup 1))
(delay
(cons (- n (car avg))
(force (elt tup 2)))))))))
(tup (funcall (foldr comb init l) avg)))
(setf (car avg) (/ (elt tup 0) (elt tup 1)))
(force (elt tup 2))))
I don't need a general purpose transformation, just some guidelines to
follow when I see code like this.
Thanks,
Matt
--
"You do not really understand something unless you can explain it to your
grandmother." -- Albert Einstein.
On May 28, 6:19 pm, Matthew D Swank <··················@gmail.com>
wrote:
> I am working throughhttp://www.haskell.org/tmrwiki/
> WhyAttributeGrammarsMatter in lisp
oh yeah:
(defun foldr (fun init seq)
(reduce fun seq :initial-value init :from-end t))
--
"You do not really understand something unless you can explain it to
your
grandmother." -- Albert Einstein.
Matthew D Swank wrote:
> I am working through http://www.haskell.org/tmrwiki/
> WhyAttributeGrammarsMatter in lisp, and I am encountering circular code
> like:
> diff :: [Float] -> [Float]
> diff xs =
> let
> nil avg = (0.0, 0.0, [])
> cons x fs avg = let (s,l,ds) = fs avg
> in (s+x,l+1.0,x-avg : ds)
> (sum,length,ds) = foldr cons nil xs (sum / length)
> in ds
>
> We all know lisp is eager, but I was wondering if there was a cleaner way
> to translate it than the following:
> (defmacro delay (&body body) `(lambda () ,@body))
> (defun force (expr) (funcall expr))
>
> (defun diff2 (l)
> (let* ((avg (cons nil nil))
> (init (lambda (avg) `#(0.0 0.0 ,(delay nil))))
> (comb (lambda (n fs)
> (lambda (avg)
> (let ((tup (funcall fs avg)))
> (vector (+ n (elt tup 0))
> (+ 1 (elt tup 1))
> (delay
> (cons (- n (car avg))
> (force (elt tup 2)))))))))
> (tup (funcall (foldr comb init l) avg)))
> (setf (car avg) (/ (elt tup 0) (elt tup 1)))
> (force (elt tup 2))))
>
> I don't need a general purpose transformation, just some guidelines to
> follow when I see code like this.
General guideline: Look for a solution that uses LOOP. ;)
(defun diff3 (list)
(let ((avg (loop for element in list
sum element into sum
count t into length
finally (return (/ sum length)))))
(loop for element in list
collect (- element avg))))
Pascal
--
1st European Lisp Symposium (ELS'08)
http://prog.vub.ac.be/~pcostanza/els08/
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
On Thu, 29 May 2008 09:38:30 +0200, Pascal Costanza wrote:
> Matthew D Swank wrote:
>> I am working through http://www.haskell.org/tmrwiki/
>> WhyAttributeGrammarsMatter in lisp, and I am encountering circular code
>> like:
>> diff :: [Float] -> [Float]
>> diff xs =
>> let
>> nil avg = (0.0, 0.0, [])
>> cons x fs avg = let (s,l,ds) = fs avg
>> in (s+x,l+1.0,x-avg : ds)
>> (sum,length,ds) = foldr cons nil xs (sum / length)
>> in ds
>>
...
>> I don't need a general purpose transformation, just some guidelines to
>> follow
...
>
> General guideline: Look for a solution that uses LOOP. ;)
>
Certainly that is less likely to blow the stack. :)
> (defun diff3 (list)
> (let ((avg (loop for element in list
> sum element into sum
> count t into length
> finally (return (/ sum length)))))
> (loop for element in list
> collect (- element avg))))
>
>
Of course you are still traversing the list twice. The point of the
haskell example is traverse the list just once.
> Pascal
Matt
--
"You do not really understand something unless you can explain it to your
grandmother." -- Albert Einstein.
Matthew D Swank wrote:
> On Thu, 29 May 2008 09:38:30 +0200, Pascal Costanza wrote:
>
>> Matthew D Swank wrote:
>>> I am working through http://www.haskell.org/tmrwiki/
>>> WhyAttributeGrammarsMatter in lisp, and I am encountering circular code
>>> like:
>>> diff :: [Float] -> [Float]
>>> diff xs =
>>> let
>>> nil avg = (0.0, 0.0, [])
>>> cons x fs avg = let (s,l,ds) = fs avg
>>> in (s+x,l+1.0,x-avg : ds)
>>> (sum,length,ds) = foldr cons nil xs (sum / length)
>>> in ds
>>>
>
> ...
>
>>> I don't need a general purpose transformation, just some guidelines to
>>> follow
> ...
>> General guideline: Look for a solution that uses LOOP. ;)
>>
>
> Certainly that is less likely to blow the stack. :)
>
>> (defun diff3 (list)
>> (let ((avg (loop for element in list
>> sum element into sum
>> count t into length
>> finally (return (/ sum length)))))
>> (loop for element in list
>> collect (- element avg))))
>>
>>
>
> Of course you are still traversing the list twice. The point of the
> haskell example is traverse the list just once.
No, the Haskell example has to do two traversals as well, the second one
is just implicit. It's inherent in the algorithm, you cannot avoid that.
On top of that: Why would that matter? Code should be clear and easy to
read, not clever and hard to understand...
Pascal
--
1st European Lisp Symposium (ELS'08)
http://prog.vub.ac.be/~pcostanza/els08/
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
Matthew D Swank wrote:
> The point of the haskell example is
> traverse the list just once.
On May 29, 4:05 am, Pascal Costanza wrote:
> No, the Haskell example has to do two traversals
> as well, the second one is just implicit.
> It's inherent in the algorithm, you cannot avoid that.
Even worse. Technically speaking, the Haskell implementation
avoids traversing the original list by constructing (and then
traversing) a stack of delayed function calls. I'd like to
know what practical use this could possibly have, because
to me, it looks like pure obfuscation.
> On top of that: Why would that matter?
> Code should be clear and easy to read,
> not clever and hard to understand...
Ha ha, haven't written much Haskell, have you?
:D
--Dan
------------------------------------------------
Dan Bensen http://www.prairienet.org/~dsb/
cl-match: expressive pattern matching in Lisp
http://common-lisp.net/project/cl-match/
On 29 May, 10:05, Pascal Costanza <····@p-cos.net> wrote:
> On top of that: Why would that matter? Code should be clear and easy to
> read, not clever and hard to understand...
I obviously agree that we should strive for clear code wherever
possible but sometimes we have to do messy things to our programs to
get them to run acceptably quickly (if my code takes more than 50ms to
match a limit order in an order book then my customers will buy
another matching engine, no matter how readable it is!).
--
Phil
http://phil.nullable.eu/
···············@gmail.com wrote:
> On 29 May, 10:05, Pascal Costanza <····@p-cos.net> wrote:
>
>> On top of that: Why would that matter? Code should be clear and easy to
>> read, not clever and hard to understand...
>
> I obviously agree that we should strive for clear code wherever
> possible but sometimes we have to do messy things to our programs to
> get them to run acceptably quickly (if my code takes more than 50ms to
> match a limit order in an order book then my customers will buy
> another matching engine, no matter how readable it is!).
Yes, with a stress on "sometimes."
Pascal
--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
??>> On top of that: Why would that matter? Code should be clear and easy
to
??>> read, not clever and hard to understand...
pa> I obviously agree that we should strive for clear code wherever
pa> possible but sometimes we have to do messy things to our programs to
pa> get them to run acceptably quickly
sure, but how does that relate to Haskell code? i'm pretty sure it's both
cryptic
and slow. (since there is no special lazy hardware, Haskell code _must_ be
translated into eager one, and believe Pascal's code is most optimal
eager code to do this).
pa> (if my code takes more than 50ms to match a limit order in an order
pa> book then my customers will buy another matching engine, no matter how
pa> readable it is!).
your customers are impatient! :)
On 29 May, 13:00, "Alex Mizrahi" <········@users.sourceforge.net>
wrote:
> ??>> On top of that: Why would that matter? Code should be clear and easy
> to
> ??>> read, not clever and hard to understand...
>
> pa> I obviously agree that we should strive for clear code wherever
> pa> possible but sometimes we have to do messy things to our programs to
> pa> get them to run acceptably quickly
>
> sure, but how does that relate to Haskell code? i'm pretty sure it's both
> cryptic
> and slow.
It doesn't relate to it which is why I was careful that no part of my
post, nor the part of Pascal's post that I quoted mentions Haskell at
all.
(since there is no special lazy hardware, Haskell code _must_ be
> translated into eager one, and believe Pascal's code is most optimal
> eager code to do this).
...nor does my post mention any of the code posted.
> pa> (if my code takes more than 50ms to match a limit order in an order
> pa> book then my customers will buy another matching engine, no matter how
> pa> readable it is!).
>
> your customers are impatient! :)
They're generally running algorithmic trading models, so in some sense
the "customer" is a machine :-)
--
Phil
http://phil.nullable.eu/
On Thu, 29 May 2008 11:05:50 +0200, Pascal Costanza wrote:
> Matthew D Swank wrote:
>> On Thu, 29 May 2008 09:38:30 +0200, Pascal Costanza wrote:
>>
>>> Matthew D Swank wrote:
>>>> I am working through http://www.haskell.org/tmrwiki/
>>>> WhyAttributeGrammarsMatter in lisp, and I am encountering circular
>>>> code like:
>>>> diff :: [Float] -> [Float]
>>>> diff xs =
>>>> let
>>>> nil avg = (0.0, 0.0, [])
>>>> cons x fs avg = let (s,l,ds) = fs avg
>>>> in (s+x,l+1.0,x-avg : ds)
>>>> (sum,length,ds) = foldr cons nil xs (sum / length)
>>>> in ds
>>>>
>>>>
>> ...
>>
>>>> I don't need a general purpose transformation, just some guidelines
>>>> to follow
>> ...
>>> General guideline: Look for a solution that uses LOOP. ;)
>>>
>>>
>> Certainly that is less likely to blow the stack. :)
>>
>>> (defun diff3 (list)
>>> (let ((avg (loop for element in list
>>> sum element into sum
>>> count t into length
>>> finally (return (/ sum length)))))
>>> (loop for element in list
>>> collect (- element avg))))
>>>
>>>
>>>
>> Of course you are still traversing the list twice. The point of the
>> haskell example is traverse the list just once.
>
> No, the Haskell example has to do two traversals as well, the second one
> is just implicit. It's inherent in the algorithm, you cannot avoid that.
>
Well, I don't know about the details of how haskell traverses the list,
but it seems to me there is one _list_ traversal. It is explicit in the
my lisp code:
(defun diff2 (l)
(let* ((avg (cons nil nil))
(init (constantly `#(0.0 0.0 ,(delay nil))))
(comb (lambda (n fs)
(lambda (avg)
(let ((tup (funcall fs avg)))
(vector (+ n (elt tup 0))
(1+ (elt tup 1))
(delay
(cons (- n (car avg))
(force (elt tup 2)))))))))
(tup (funcall (foldr comb init l) avg)))
(setf (car avg) (/ (elt tup 0) (elt tup 1)))
(force (elt tup 2))))
Instead of traversing the list twice, the fold builds up what is
effectively a chain of closures to build the returned list.
I admit that this is a false economy (at least in my lisp translation),
but those who make glib comments about how much clearer an idiomatic,
eager solution is in lisp* are missing the point of trying to learn from
others.
> On top of that: Why would that matter? Code should be clear and easy to
> read, not clever and hard to understand...
>
>
Right now, I am trying to program at the level of the domain of study
(catamorphisms in a lazy language). Bringing useful things down into lisp
comes later. I wasn't asking how to transform a list in lisp based on
some global property about the list, I was asking if there was a better
way to express idiomatic haskell.
> Pascal
Matt
* I refer you to most of the sub tree of the parent message.
Matthew D Swank wrote:
> On Thu, 29 May 2008 11:05:50 +0200, Pascal Costanza wrote:
>
>> Matthew D Swank wrote:
>>> On Thu, 29 May 2008 09:38:30 +0200, Pascal Costanza wrote:
>>>
>>>> Matthew D Swank wrote:
>>>>> I am working through http://www.haskell.org/tmrwiki/
>>>>> WhyAttributeGrammarsMatter in lisp, and I am encountering circular
>>>>> code like:
>>>>> diff :: [Float] -> [Float]
>>>>> diff xs =
>>>>> let
>>>>> nil avg = (0.0, 0.0, [])
>>>>> cons x fs avg = let (s,l,ds) = fs avg
>>>>> in (s+x,l+1.0,x-avg : ds)
>>>>> (sum,length,ds) = foldr cons nil xs (sum / length)
>>>>> in ds
>>>>>
>>>>>
>>> ...
>>>
>>>>> I don't need a general purpose transformation, just some guidelines
>>>>> to follow
>>> ...
>>>> General guideline: Look for a solution that uses LOOP. ;)
>>>>
>>>>
>>> Certainly that is less likely to blow the stack. :)
>>>
>>>> (defun diff3 (list)
>>>> (let ((avg (loop for element in list
>>>> sum element into sum
>>>> count t into length
>>>> finally (return (/ sum length)))))
>>>> (loop for element in list
>>>> collect (- element avg))))
>>>>
>>>>
>>>>
>>> Of course you are still traversing the list twice. The point of the
>>> haskell example is traverse the list just once.
>> No, the Haskell example has to do two traversals as well, the second one
>> is just implicit. It's inherent in the algorithm, you cannot avoid that.
>>
>
> Well, I don't know about the details of how haskell traverses the list,
> but it seems to me there is one _list_ traversal. It is explicit in the
> my lisp code:
>
> (defun diff2 (l)
> (let* ((avg (cons nil nil))
> (init (constantly `#(0.0 0.0 ,(delay nil))))
> (comb (lambda (n fs)
> (lambda (avg)
> (let ((tup (funcall fs avg)))
> (vector (+ n (elt tup 0))
> (1+ (elt tup 1))
> (delay
> (cons (- n (car avg))
> (force (elt tup 2)))))))))
> (tup (funcall (foldr comb init l) avg)))
> (setf (car avg) (/ (elt tup 0) (elt tup 1)))
> (force (elt tup 2))))
>
> Instead of traversing the list twice, the fold builds up what is
> effectively a chain of closures to build the returned list.
...and that chain is as long as the original list, and each closure in
that chain has to be visited - so there is your second, implicit
traversal. (In my book, whether you have to traverse something once or
twice is an efficiency measure, so the Haskell version has the same
overhead in that regard as traversing the same list twice. If you have
something else in mind why it should matter or not, I'd be interested to
hear that.)
> I admit that this is a false economy (at least in my lisp translation),
> but those who make glib comments about how much clearer an idiomatic,
> eager solution is in lisp* are missing the point of trying to learn from
> others.
I was referring to your and my Lisp solution. I think my solution is
easier to understand. Your Lisp solution has to express a lot of
machinery to make the lazy evaluation work, and that distracts from the
problem you actually want to solve, IMHO.
I can't judge how easy it is to understand the Haskell version for an
experienced Haskell programmer.
>> On top of that: Why would that matter? Code should be clear and easy to
>> read, not clever and hard to understand...
>
> Right now, I am trying to program at the level of the domain of study
> (catamorphisms in a lazy language). Bringing useful things down into lisp
> comes later. I wasn't asking how to transform a list in lisp based on
> some global property about the list, I was asking if there was a better
> way to express idiomatic haskell.
Fair enough, but that wasn't clear to me from your original post. So
sorry for misunderstanding you.
Pascal
--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
On Thu, 29 May 2008 20:44:21 +0200, Pascal Costanza wrote:
> Matthew D Swank wrote:
...
>> those who make glib comments about how much clearer an idiomatic,
>> eager solution is in lisp* are missing the point of trying to learn
>> from others.
>
> I was referring to your and my Lisp solution. I think my solution is
> easier to understand. Your Lisp solution has to express a lot of
> machinery to make the lazy evaluation work, and that distracts from the
> problem you actually want to solve, IMHO.
>
...
>>
>> I wasn't asking how to transform a list in lisp based on some global
>> property about the list, I was asking if there was a better way to
>> express idiomatic haskell.
>
> Fair enough, but that wasn't clear to me from your original post. So
> sorry for misunderstanding you.
>
Well, I should have been more explicit.
>
> Pascal
Matt
P� Thu, 29 May 2008 09:38:30 +0200, skrev Pascal Costanza <··@p-cos.net>:
>
> General guideline: Look for a solution that uses LOOP. ;)
>
> (defun diff3 (list)
> (let ((avg (loop for element in list
> sum element into sum
> count t into length
> finally (return (/ sum length)))))
> (loop for element in list
> collect (- element avg))))
>
>
> Pascal
>
Crystal clear as usual prof. except the name.
--------------
John Thingstad
MDS> I don't need a general purpose transformation, just some guidelines to
MDS> follow when I see code like this.
IMHO you can always make eager code that does same thing as lazy one, but
works faster and is much more readable. and probably lazy code won't
help you writting eager one, it's better just to throw it away and start
from scratch..
MDS> (defmacro delay (&body body) `(lambda () ,@body))
MDS> (defun force (expr) (funcall expr))
just as a note, these macros won't accurately reproduce Haskell's semantics
in some
cases -- computed value must be memorized to prevent computing it second
time.
On Thu, 29 May 2008 12:30:44 +0300, Alex Mizrahi wrote:
> MDS> (defmacro delay (&body body) `(lambda () ,@body)) MDS> (defun
> force (expr) (funcall expr))
>
> just as a note, these macros won't accurately reproduce Haskell's
> semantics in some
> cases -- computed value must be memorized to prevent computing it second
> time.
I realize this, but in the example I never force a delayed value more
than once.
Matt