Is there any way I can do this fold w/o the setf?
(loop :with state := next-state
:for i :from 0 :below n
:do (setf state (build-nfa regex state))
:finally (return state)))
Thanks,
Matt
Matthew D Swank <··················@gmail.com> wrote:
> Is there any way I can do this fold w/o the setf?
>
> (loop :with state := next-state
> :for i :from 0 :below n
> :do (setf state (build-nfa regex state))
> :finally (return state)))
>
This might work:
(loop
for state = next-state then (build-nfa regex state)
for i from 0 below n
finally (return state))
Bob Felts wrote:
> Matthew D Swank <··················@gmail.com> wrote:
>
>
>>Is there any way I can do this fold w/o the setf?
>>
>>(loop :with state := next-state
>> :for i :from 0 :below n
>> :do (setf state (build-nfa regex state))
>> :finally (return state)))
>>
>
>
> This might work:
>
> (loop
> for state = next-state then (build-nfa regex state)
> for i from 0 below n
> finally (return state))
>
Does that do n-1 transitions instead of n? My head too dense to be sure,
but it looks like the original would do n transitions while the above
consumes an iteration just setting state to next state.
Mind you, I never heard of a state machine being driven by transition count.
Meanwhile, are billing by LOC? :) "from 0" is the default.
kt
On Sat, 13 Sep 2008 22:44:40 -0400, Kenny wrote:
> Bob Felts wrote:
>> Matthew D Swank <··················@gmail.com> wrote:
>>
>>
>>>Is there any way I can do this fold w/o the setf?
>>>
>>>(loop :with state := next-state
>>> :for i :from 0 :below n
>>> :do (setf state (build-nfa regex state)) :finally (return
>>> state)))
>>>
>>>
>>
>> This might work:
>>
>> (loop
>> for state = next-state then (build-nfa regex state) for i
>> from 0 below n
>> finally (return state))
>>
>>
> Does that do n-1 transitions instead of n? My head too dense to be sure,
> but it looks like the original would do n transitions while the above
> consumes an iteration just setting state to next state.
>
> Mind you, I never heard of a state machine being driven by transition
> count.
>
> Meanwhile, are billing by LOC? :) "from 0" is the default.
>
> kt
Well this happens in sbcl and clisp:
(loop :for x := 1
:then (progn (format t "~a~%" x) (+ 5 x))
:for n :below 5
:finally (return x))
1
6
11
16
21
=> 26
But am I relying on unspecified behavior?
Matt
On Sep 14, 1:59 am, Matthew D Swank <··················@gmail.com>
wrote:
> On Sat, 13 Sep 2008 22:44:40 -0400, Kenny wrote:
> > Bob Felts wrote:
> >> Matthew D Swank <··················@gmail.com> wrote:
>
> >>>Is there any way I can do this fold w/o the setf?
>
> >>>(loop :with state := next-state
> >>> :for i :from 0 :below n
> >>> :do (setf state (build-nfa regex state)) :finally (return
> >>> state)))
>
> >> This might work:
>
> >> (loop
> >> for state = next-state then (build-nfa regex state) for i
> >> from 0 below n
> >> finally (return state))
>
> > Does that do n-1 transitions instead of n? My head too dense to be sure,
> > but it looks like the original would do n transitions while the above
> > consumes an iteration just setting state to next state.
>
> > Mind you, I never heard of a state machine being driven by transition
> > count.
>
> > Meanwhile, are billing by LOC? :) "from 0" is the default.
>
> > kt
>
> Well this happens in sbcl and clisp:
> (loop :for x := 1
> :then (progn (format t "~a~%" x) (+ 5 x))
> :for n :below 5
> :finally (return x))
> 1
> 6
> 11
> 16
> 21
> => 26
> But am I relying on unspecified behavior?
> Matt
MatzLisp:
((0..4).inject(1) do |x,n|
(p x)
(x += 5)
end)
1
6
11
16
21
==>26
On Sep 14, 5:10 am, William James <·········@yahoo.com> wrote:
> On Sep 14, 1:59 am, Matthew D Swank <··················@gmail.com>
> wrote:
>
>
>
> > On Sat, 13 Sep 2008 22:44:40 -0400, Kenny wrote:
> > > Bob Felts wrote:
> > >> Matthew D Swank <··················@gmail.com> wrote:
>
> > >>>Is there any way I can do this fold w/o the setf?
>
> > >>>(loop :with state := next-state
> > >>> :for i :from 0 :below n
> > >>> :do (setf state (build-nfa regex state)) :finally (return
> > >>> state)))
>
> > >> This might work:
>
> > >> (loop
> > >> for state = next-state then (build-nfa regex state) for i
> > >> from 0 below n
> > >> finally (return state))
>
> > > Does that do n-1 transitions instead of n? My head too dense to be sure,
> > > but it looks like the original would do n transitions while the above
> > > consumes an iteration just setting state to next state.
>
> > > Mind you, I never heard of a state machine being driven by transition
> > > count.
>
> > > Meanwhile, are billing by LOC? :) "from 0" is the default.
>
> > > kt
>
> > Well this happens in sbcl and clisp:
> > (loop :for x := 1
> > :then (progn (format t "~a~%" x) (+ 5 x))
> > :for n :below 5
> > :finally (return x))
> > 1
> > 6
> > 11
> > 16
> > 21
> > => 26
> > But am I relying on unspecified behavior?
> > Matt
>
> MatzLisp:
>
> ((0..4).inject(1) do |x,n|
> (p x)
> (x += 5)
Simplify to (x + 5):
((0..4).inject(1) do |x,n|
(p x)
(x + 5)
end)
1
6
11
16
21
==>26
William James schrieb:
> On Sep 14, 5:10 am, William James <·········@yahoo.com> wrote:
>> On Sep 14, 1:59 am, Matthew D Swank <··················@gmail.com>
>> wrote:
>>
>>
>>
>>> On Sat, 13 Sep 2008 22:44:40 -0400, Kenny wrote:
>>>> Bob Felts wrote:
>>>>> Matthew D Swank <··················@gmail.com> wrote:
>>>>>> Is there any way I can do this fold w/o the setf?
>>>>>> (loop :with state := next-state
>>>>>> :for i :from 0 :below n
>>>>>> :do (setf state (build-nfa regex state)) :finally (return
>>>>>> state)))
>>>>> This might work:
>>>>> (loop
>>>>> for state = next-state then (build-nfa regex state) for i
>>>>> from 0 below n
>>>>> finally (return state))
>>>> Does that do n-1 transitions instead of n? My head too dense to be sure,
>>>> but it looks like the original would do n transitions while the above
>>>> consumes an iteration just setting state to next state.
>>>> Mind you, I never heard of a state machine being driven by transition
>>>> count.
>>>> Meanwhile, are billing by LOC? :) "from 0" is the default.
>>>> kt
>>> Well this happens in sbcl and clisp:
>>> (loop :for x := 1
>>> :then (progn (format t "~a~%" x) (+ 5 x))
>>> :for n :below 5
>>> :finally (return x))
>>> 1
>>> 6
>>> 11
>>> 16
>>> 21
>>> => 26
>>> But am I relying on unspecified behavior?
>>> Matt
>> MatzLisp:
>>
>> ((0..4).inject(1) do |x,n|
>> (p x)
>> (x += 5)
>
> Simplify to (x + 5):
>
> ((0..4).inject(1) do |x,n|
> (p x)
> (x + 5)
> end)
> 1
> 6
> 11
> 16
> 21
> ==>26
I wrote the 0.. function last year in January and made use of it here.
It�s shorter in Lisp:
(reduce (lambda (x n) (print (+ x 5)))
(0.. 4)
:initial-value 1)
While your Ruby function has 15 program points the lisp code only has
12. By saying (p (x + 5)) you can come a bit closer to Lisp, going down
to 14 points.
Andr�
--
Kenny <·········@gmail.com> writes:
> Mind you, I never heard of a state machine being driven by transition count.
> Meanwhile, are billing by LOC? :) "from 0" is the default.
(loop :repeat n
:for state = (build-nfa regex next-state) :then (build-nfa regex state)
:finally (return state))
--
__Pascal Bourguignon__ http://www.informatimago.com/
ADVISORY: There is an extremely small but nonzero chance that,
through a process known as "tunneling," this product may
spontaneously disappear from its present location and reappear at
any random place in the universe, including your neighbor's
domicile. The manufacturer will not be responsible for any damages
or inconveniences that may result.
On Sun, 14 Sep 2008 09:06:58 +0200, Pascal J. Bourguignon wrote:
> Kenny <·········@gmail.com> writes:
>> Mind you, I never heard of a state machine being driven by transition
>> count. Meanwhile, are billing by LOC? :) "from 0" is the default.
>
> (loop :repeat n
> :for state = (build-nfa regex next-state) :then (build-nfa regex
> state) :finally (return state))
This one actually doesn't execute rebinding of state enough times.
The original loop was:
(loop :with state := next-state
:for i :from 0 :below n
:do (setf state (build-nfa regex state))
:finally (return state)))
The two "correct" choices would seem be
(loop :repeat (1+ n)
:for state := (build-nfa regex next-state)
:then (build-nfa regex state)
:finally (return state))
or somewhat more perversely
(loop :for state := (build-nfa regex next-state)
:then (build-nfa regex state)
:repeat n
:finally (return state))
Witness
(loop :repeat 5
:for x := 1 :then (progn (format t "~a~%" x) (+ 5 x))
:finally (return x))
1
6
11
16
=> 21
(loop :for x := 1
:then (progn (format t "~a~%" x) (+ 5 x))
:repeat 5
:finally (return x))
1
6
11
16
21
=> 26
Matt
Matthew D Swank wrote:
> On Sun, 14 Sep 2008 09:06:58 +0200, Pascal J. Bourguignon wrote:
>
>
>>Kenny <·········@gmail.com> writes:
>>
>>>Mind you, I never heard of a state machine being driven by transition
>>>count. Meanwhile, are billing by LOC? :) "from 0" is the default.
>>
>>(loop :repeat n
>> :for state = (build-nfa regex next-state) :then (build-nfa regex
>> state) :finally (return state))
>
>
> This one actually doesn't execute rebinding of state enough times.
> The original loop was:
>
> (loop :with state := next-state
> :for i :from 0 :below n
> :do (setf state (build-nfa regex state))
> :finally (return state)))
>
> The two "correct" choices would seem be
>
> (loop :repeat (1+ n)
> :for state := (build-nfa regex next-state)
> :then (build-nfa regex state)
> :finally (return state))
>
> or somewhat more perversely
>
> (loop :for state := (build-nfa regex next-state)
> :then (build-nfa regex state)
> :repeat n
> :finally (return state))
>
> Witness
> (loop :repeat 5
> :for x := 1 :then (progn (format t "~a~%" x) (+ 5 x))
> :finally (return x))
> 1
> 6
> 11
> 16
> => 21
>
> (loop :for x := 1
> :then (progn (format t "~a~%" x) (+ 5 x))
> :repeat 5
> :finally (return x))
> 1
> 6
> 11
> 16
> 21
> => 26
>
> Matt
...and finally:
(loop for x below 2
for y = 0 then (+ 1 y)
do (print (list x y))
finally (print (list x y)))
(0 0)
(1 1)
(2 1)
(loop for x below 2
and y = 0 then (+ 1 y)
do (print (list x y))
finally (print (list x y)))
(0 0)
(1 1)
(2 2)
Which is why I never take my gun off finally. Or and.
kt
Matthew D Swank <··················@gmail.com> writes:
> On Sun, 14 Sep 2008 09:06:58 +0200, Pascal J. Bourguignon wrote:
>
>> Kenny <·········@gmail.com> writes:
>>> Mind you, I never heard of a state machine being driven by transition
>>> count. Meanwhile, are billing by LOC? :) "from 0" is the default.
>>
>> (loop :repeat n
>> :for state = (build-nfa regex next-state) :then (build-nfa regex
>> state) :finally (return state))
>
> This one actually doesn't execute rebinding of state enough times.
> The original loop was:
>
> (loop :with state := next-state
> :for i :from 0 :below n
> :do (setf state (build-nfa regex state))
> :finally (return state)))
Both will call build-nfa N times.
--
__Pascal Bourguignon__ http://www.informatimago.com/
"By filing this bug report you have challenged the honor of my
family. Prepare to die!"
On Sun, 14 Sep 2008 15:23:40 +0200, Pascal J. Bourguignon wrote:
> Matthew D Swank <··················@gmail.com> writes:
>
>> On Sun, 14 Sep 2008 09:06:58 +0200, Pascal J. Bourguignon wrote:
>>
>>> Kenny <·········@gmail.com> writes:
>>>> Mind you, I never heard of a state machine being driven by transition
>>>> count. Meanwhile, are billing by LOC? :) "from 0" is the default.
>>>
>>> (loop :repeat n
>>> :for state = (build-nfa regex next-state) :then (build-nfa regex
>>> state) :finally (return state))
>>
>> This one actually doesn't execute rebinding of state enough times. The
>> original loop was:
>>
>> (loop :with state := next-state
>> :for i :from 0 :below n
>> :do (setf state (build-nfa regex state)) :finally (return
>> state)))
>
> Both will call build-nfa N times.
Yeah. It was late, and I misread
:for state = (build-nfa regex next-state)
as
:for state = next-state
I bow to your loop skills.
Matt
Pascal J. Bourguignon <···@informatimago.com> wrote:
> Kenny <·········@gmail.com> writes:
> > Mind you, I never heard of a state machine being driven by transition count.
> > Meanwhile, are billing by LOC? :) "from 0" is the default.
>
> (loop :repeat n
> :for state = (build-nfa regex next-state) :then (build-nfa regex state)
> :finally (return state))
This version isn't equivalent to the original. Encapsulating the
original in a function in order to easily explore the effect of the loop
limit, and using a simple state transtion:
(defun loop-original (n)
(loop
with state = 1
for i from 0 below n
do (setf state (1+ state))
finally (return state)))
(loop-original 0) -> 1
Doing the same with Pascal's version:
(defun loop-pascal (n)
(loop
repeat n
for state = 1 then (1+ state)
finally (return state)))
(loop->pascal 0) -> nil
My reformulation:
(defun loop-felts (n)
(loop
for state = 1 then (1+ state)
for i from 0 below n
finally (return state)))
(loop-felts 0) -> 1
The :with in the original problem sets state even if the loop is
executed zero times and this is why the assignment to state has to
happen before the loop control in the revised versions.
Kenny: "My head too dense to be sure" too. That's why I tested it
before hitting "send".
On Sep 14, 1:56 pm, ····@stablecross.com (Bob Felts) wrote:
> Pascal J. Bourguignon <····@informatimago.com> wrote:
>
> > Kenny <·········@gmail.com> writes:
> > > Mind you, I never heard of a state machine being driven by transition count.
> > > Meanwhile, are billing by LOC? :) "from 0" is the default.
>
> > (loop :repeat n
> > :for state = (build-nfa regex next-state) :then (build-nfa regex state)
> > :finally (return state))
>
> This version isn't equivalent to the original. Encapsulating the
> original in a function in order to easily explore the effect of the loop
> limit, and using a simple state transtion:
>
> (defun loop-original (n)
> (loop
> with state = 1
> for i from 0 below n
> do (setf state (1+ state))
> finally (return state)))
>
> (loop-original 0) -> 1
>
> Doing the same with Pascal's version:
>
> (defun loop-pascal (n)
> (loop
> repeat n
> for state = 1 then (1+ state)
> finally (return state)))
>
> (loop->pascal 0) -> nil
>
> My reformulation:
>
> (defun loop-felts (n)
> (loop
> for state = 1 then (1+ state)
> for i from 0 below n
> finally (return state)))
>
> (loop-felts 0) -> 1
>
> The :with in the original problem sets state even if the loop is
> executed zero times and this is why the assignment to state has to
> happen before the loop control in the revised versions.
MatzLisp:
(def loop_m (n)
((0...n).inject(1) do |x,i|
(x + 5)
end)
end)
==>nil
(loop_m 0)
==>1
(loop_m 1)
==>6
····@stablecross.com (Bob Felts) writes:
> The :with in the original problem sets state even if the loop is
> executed zero times and this is why the assignment to state has to
> happen before the loop control in the revised versions.
I fail to see the importance of binding a loop variable. The compiler
may elide any binding anyways. What I maintained was the number of
times build-nfa was called. If returning the initial value when n is
0 is important you can always wrap the loop in an OR:
(or (loop ...) next-state)
--
__Pascal Bourguignon__ http://www.informatimago.com/
"What is this talk of "release"? Klingons do not make software
"releases". Our software "escapes" leaving a bloody trail of
designers and quality assurance people in its wake."
Pascal J. Bourguignon <···@informatimago.com> wrote:
> ····@stablecross.com (Bob Felts) writes:
> > The :with in the original problem sets state even if the loop is
> > executed zero times and this is why the assignment to state has to
> > happen before the loop control in the revised versions.
>
> I fail to see the importance of binding a loop variable.
Perhaps, but the original example did and I didn't think I had the right
to change the behavior.
> The compiler may elide any binding anyways.
How so? Is it the case that:
(loop
for foo = bar than (baz foo)
repeat 0)
won't set foo to bar?
> What I maintained was the number of times build-nfa was called.
That wasn't the only invariant in the original code, however.
> If returning the initial value when
> n is 0 is important you can always wrap the loop in an OR:
>
> (or (loop ...) next-state)
Or you can assign it before the loop counter. That's the great thing
about programming. So many different ways to do the same thing.
····@stablecross.com (Bob Felts) writes:
> Pascal J. Bourguignon <···@informatimago.com> wrote:
>
>> ····@stablecross.com (Bob Felts) writes:
>> > The :with in the original problem sets state even if the loop is
>> > executed zero times and this is why the assignment to state has to
>> > happen before the loop control in the revised versions.
>>
>> I fail to see the importance of binding a loop variable.
>
> Perhaps, but the original example did and I didn't think I had the right
> to change the behavior.
>
>> The compiler may elide any binding anyways.
>
> How so?
(disassemble (compile nil (lambda (x) (let ((y (* x x))) (+ y y)))))
Disassembly of function NIL
1 required argument
0 optional arguments
No rest parameter
No keyword parameters
7 byte-code instructions:
0 (LOAD&PUSH 1)
1 (LOAD&PUSH 2)
2 (CALLSR&PUSH 2 55) ; *
5 (LOAD&PUSH 0)
6 (LOAD&PUSH 1)
7 (CALLSR 2 53) ; +
10 (SKIP&RET 3)
NIL
See? No binding! (ie. no PUSH-NIL to reserve the space, no STORE
statement, no y "variable" in the generated code).
> Is it the case that:
>
> (loop
> for foo = bar than (baz foo)
> repeat 0)
>
> won't set foo to bar?
Indeed:
S/CL-USER[6]> (locally (declare (optimize (space 3) (speed 3) (safety 0) (debug 0)))
(disassemble (compile nil (lambda (bar)
(loop for foo = bar then (baz foo) repeat 0)))))
; in: LAMBDA NIL
; (BAZ FOO)
; ==>
; FOO
;
; note: deleting unreachable code
;
; compilation unit finished
; printed 1 note
; 0AA309CA: BA0B001001 MOV EDX, 17825803 ; no-arg-parsing entry point
; CF: 8D65F8 LEA ESP, [EBP-8]
; D2: F8 CLC
; D3: 8B6DFC MOV EBP, [EBP-4]
; D6: C20400 RET 4
; D9: 90 NOP
; DA: 90 NOP
; DB: 90 NOP
; DC: 90 NOP
; DD: 90 NOP
; DE: 90 NOP
; DF: 90 NOP
;
NIL
--
__Pascal Bourguignon__ http://www.informatimago.com/
"Klingon function calls do not have "parameters" -- they have
"arguments" and they ALWAYS WIN THEM."
Pascal J. Bourguignon <···@informatimago.com> wrote:
> ····@stablecross.com (Bob Felts) writes:
>
> > Pascal J. Bourguignon <···@informatimago.com> wrote:
> >
> >> ····@stablecross.com (Bob Felts) writes:
> >> > The :with in the original problem sets state even if the loop is
> >> > executed zero times and this is why the assignment to state has to
> >> > happen before the loop control in the revised versions.
> >>
> >> I fail to see the importance of binding a loop variable.
> >
> > Perhaps, but the original example did and I didn't think I had the right
> > to change the behavior.
> >
> >> The compiler may elide any binding anyways.
> >
> > How so?
>
> (disassemble (compile nil (lambda (x) (let ((y (* x x))) (+ y y)))))
>
> Disassembly of function NIL
> 1 required argument
> 0 optional arguments
> No rest parameter
> No keyword parameters
> 7 byte-code instructions:
> 0 (LOAD&PUSH 1)
> 1 (LOAD&PUSH 2)
> 2 (CALLSR&PUSH 2 55) ; *
> 5 (LOAD&PUSH 0)
> 6 (LOAD&PUSH 1)
> 7 (CALLSR 2 53) ; +
> 10 (SKIP&RET 3)
> NIL
>
> See? No binding! (ie. no PUSH-NIL to reserve the space, no STORE
> statement, no y "variable" in the generated code).
>
But the function still has to return (+ (* x x) (* x x)) regardless of
how it computes it.
>
> > Is it the case that:
> >
> > (loop
> > for foo = bar than (baz foo)
> > repeat 0)
> >
> > won't set foo to bar?
>
>
> Indeed:
>
> S/CL-USER[6]> (locally (declare (optimize (space 3)
> (speed 3) (safety 0) (debug 0)))
> (disassemble (compile nil (lambda (bar)
> (loop for foo = bar then (baz foo) repeat 0)))))
[...]
Yes, compilers can optimize code. I don't think that's what we're
arguing. In the original reformulation of Swank's question:
(loop
for state = next-state then (build-nfa regex state)
for i from 0 below n
finally (return state))
Since state is returned, even if the compiler knew that n was zero, so
that the loop woudn't execute, the loop would still have to return
next-state.
On Sep 15, 12:04 pm, ····@stablecross.com (Bob Felts) wrote:
> Yes, compilers can optimize code. I don't think that's what we're
> arguing. In the original reformulation of Swank's question:
>
> (loop
> for state = next-state then (build-nfa regex state)
> for i from 0 below n
> finally (return state))
>
> Since state is returned, even if the compiler knew that n was zero, so
> that the loop woudn't execute, the loop would still have to return
> next-state.
Yes, the original loop needed to return next-state on n <= 0.
Matt
Dnia 14-09-2008 o 03:11:13 Matthew D Swank <··················@gmail.com>
napisa�(a):
> Is there any way I can do this fold w/o the setf?
>
> (loop :with state := next-state
> :for i :from 0 :below n
> :do (setf state (build-nfa regex state))
> :finally (return state)))
Wow, haven't known that Lisp is so ugly. Your problem fits into the
pattern:
unfold + (cut + take-last = take-nth)
Since Common Lisp doesn't support these functions, you have to eithter
write such functions yourself, or use the series package:
(flet ((init () state)
(step (st) (build-nfa regexp st)) )
(collect-nth n (scan-fn t #'init #'step)) )
--
Micha� Przyby�ek
On Sun, 14 Sep 2008 11:01:47 +0200, Michal Przybylek wrote:
> Dnia 14-09-2008 o 03:11:13 Matthew D Swank
> <··················@gmail.com> napisał(a):
>
>> Is there any way I can do this fold w/o the setf?
>>
>> (loop :with state := next-state
>> :for i :from 0 :below n
>> :do (setf state (build-nfa regex state)) :finally (return
>> state)))
>
> Wow, haven't known that Lisp is so ugly. Your problem fits into the
> pattern:
>
> unfold + (cut + take-last = take-nth)
>
> Since Common Lisp doesn't support these functions, you have to eithter
> write such functions yourself, or use the series package:
>
> (flet ((init () state)
> (step (st) (build-nfa regexp st)) )
> (collect-nth n (scan-fn t #'init #'step)) )
Oh, aren't you so clever for figuring out that lisp doesn't have a built
in fold for integer ranges.
The pattern is common enough, and for sequences there is reduce* and
pretty enough idioms using loop.
Even for ranges Pascal B. came up with
(loop :repeat n
:for state := (build-nfa regex next-state)
:then (build-nfa regex state)
:finally (return state))
Though some lispers would rather use scheme than do, this doesn't look so
bad either
(do ((i 0 (1+ i))
(state next-state (build-nfa regex state)))
((>= i n) state))
Matt
* Though wide adoption of
http://www.doc.gold.ac.uk/~mas01cr/papers/ilc2007/sequences-20070301.pdf
would make reduce usable for a range type as well.
Dnia 14-09-2008 o 18:20:40 Matthew D Swank <··················@gmail.com>
napisa�(a):
> Oh, aren't you so clever for figuring out that lisp doesn't have a built
> in fold for integer ranges.
>
> The pattern is common enough, and for sequences there is reduce* and
> pretty enough idioms using loop.
I don't understand. Neither your offensive style, nor what you're trying
to say.
I've just said, that your problem follows a very common pattern that (in
the functional world) can be expressed as ,,unfold + cut + last''. I've
also said, that a code like:
> (loop :repeat n
> :for state := (build-nfa regex next-state)
> :then (build-nfa regex state)
> :finally (return state))
is both - ugly and unlispy. Furthermore, I can add, that a code like:
> (do ((i 0 (1+ i))
> (state next-state (build-nfa regex state)))
> ((>= i n) state))
is only ugly.
--
Micha� Przyby�ek
On Sun, 14 Sep 2008 19:41:10 +0200, Michal Przybylek wrote:
> I've just said, that your problem follows a very common pattern that (in
> the functional world) can be expressed as ,,unfold + cut + last''.
In the "function world" the pattern is precisely a left fold on some
notional integer sequence
(foldl (lambda (state i)
(build-nfa regex state))
next-state
(** 0 n))
> I've also said, that a code like:
>
>> (loop :repeat n
>> :for state := (build-nfa regex next-state)
>> :then (build-nfa regex state)
>> :finally (return state))
>
> is both - ugly and unlispy.
Yes, clear declarative code is horrible way to have to write iteration.
,,unfold + cut + last''
is a warthog's tuckus.
Matt
On Sep 14, 1:38 pm, Matthew D Swank <··················@gmail.com>
wrote:
> On Sun, 14 Sep 2008 19:41:10 +0200, Michal Przybylek wrote:
> > I've just said, that your problem follows a very common pattern that (in
> > the functional world) can be expressed as ,,unfold + cut + last''.
>
> In the "function world" the pattern is precisely a left fold on some
> notional integer sequence
>
> (foldl (lambda (state i)
> (build-nfa regex state))
> next-state
> (** 0 n))
Ruby:
(1..n).inject(first_state){|state,i|
build_nfa regex, state }
>
> > I've also said, that a code like:
>
> >> (loop :repeat n
> >> :for state := (build-nfa regex next-state)
> >> :then (build-nfa regex state)
> >> :finally (return state))
>
> > is both - ugly and unlispy.
>
> Yes, clear declarative code is horrible way to have to write iteration.
>
> ,,unfold + cut + last''
>
> is a warthog's tuckus.
>
> Matt
On Sun, 14 Sep 2008 18:38:22 +0000, Matthew D Swank wrote:
> In the "function world" the pattern is precisely a left fold on some
> notional integer sequence
>
> (foldl (lambda (state i)
> (build-nfa regex state))
> next-state
> (** 0 n))
Depending on how one decides to define ** it might make more sense to have
(** 0 (1- n))
or define below and have
(below n) as the "sequence" argument.
Matt
Dnia 14-09-2008 o 20:38:22 Matthew D Swank <··················@gmail.com>
napisa�(a):
> In the "function world" the pattern is precisely a left fold on some
> notional integer sequence
>
> (foldl (lambda (state i)
> (build-nfa regex state))
> next-state
> (** 0 n))
No, it's not. ,,Fold'' is for folding sequences. Here, it could hardly be
said that you are ,,folding'' any sequence (btw, it should be 1..n or
0..n-1). You are just ,,unfolding'' a state via the function build-nfa.
--
Micha� Przyby�ek
On Sun, 14 Sep 2008 21:40:58 +0200, Michal Przybylek wrote:
> Dnia 14-09-2008 o 20:38:22 Matthew D Swank
> <··················@gmail.com> napisał(a):
>
>> In the "function world" the pattern is precisely a left fold on some
>> notional integer sequence
>>
>> (foldl (lambda (state i)
>> (build-nfa regex state))
>> next-state
>> (** 0 n))
>
> No, it's not. ,,Fold'' is for folding sequences. Here, it could hardly
> be said that you are ,,folding'' any sequence (btw, it should be 1..n or
> 0..n-1). You are just ,,unfolding'' a state via the function build-nfa.
*sigh*
Unfold is still using a sequence to drive the iteration.
Unless I'm writing a proof, what does it matter which combinator I use to
accumulate the value of state. If I wanted to do this functionally in
lisp the fold is a _lot_ closer built in lisp idioms than the lazy unfold
madness you find so dear. Lisp, as it has been noted, is not haskell.
Matt
Dnia 15-09-2008 o 00:08:18 Matthew D Swank <··················@gmail.com>
napisa�(a):
> Unfold is still using a sequence to drive the iteration.
No, it isn't. But it's not the case. It doesn't matter.
> Unless I'm writing a proof, what does it matter which combinator I use to
> accumulate the value of state.
The answer is obvious - using right patterns makes the code more readable.
> If I wanted to do this functionally in lisp the fold
> is a _lot_ closer built in lisp idioms than the lazy
> unfold madness you find so dear.
,,When all you have is a hammer, everything looks like a nail.''
Using ,,fold'' for unfolding is the wrong idiom. And a wrong idiom is a
wrong idiom in any language.
--
Micha� Przyby�ek
* Michal Przybylek
> a wrong idiom is a wrong idiom in any language.
Oh. Let's take any strictly evaluated language and a certain "unfold +
take-nth" idiom so wrong, it doesn't even terminate. You'd say that
makes it wrong in Haskell, too?
--
Marcus
Dnia 15-09-2008 o 14:01:38 Marcus Breiing
<······@2008w36.mail.breiing.com> napisa�(a):
>> a wrong idiom is a wrong idiom in any language.
>
> Oh. Let's take any strictly evaluated language and a certain "unfold +
> take-nth" idiom so wrong, it doesn't even terminate. You'd say that
> makes it wrong in Haskell, too?
Let's take Common Lisp and the code from my initial post. What's your
point?...
--
Micha� Przyby�ek
On 15 Sep., 17:43, "Michal Przybylek" <················@gmail.com>
wrote:
> Dnia 15-09-2008 o 14:01:38 Marcus Breiing
> <······@2008w36.mail.breiing.com> napisa³(a):
>
> >> a wrong idiom is a wrong idiom in any language.
>
> > Oh. Let's take any strictly evaluated language and a certain "unfold +
> > take-nth" idiom so wrong, it doesn't even terminate. You'd say that
> > makes it wrong in Haskell, too?
>
> Let's take Common Lisp and the code from my initial post. What's your
> point?...
>
> --
> Micha³ Przyby³ek
The point is that loops are written in Common Lisp mainly using one of
the iteration
constructs DO, DOLIST, DOTIMES and LOOP. Some people also use the
ITERATE macro.
Mapping is done with MAP, MAPCAR and related. Additionally there is
REDUCE.
I've never found the SERIES tools to be a real improvement - though I
tried to
use them several times. LOOP and ITERATE are declaratively enough for
my
purposes. I've also moved away from using tail recursive functions as
loop replacements.
It takes some experience to accept that the 'ugly' and old tools are
more useful
and less obfuscating than the alternatives.
Something like
(loop repeat n
for state = (build-nfa regex next-state) then (build-nfa regex
state)
finally (return state))
or
(let ((state next-state))
(dotimes (i n state)
(setf state (build-nfa regex state))))
is fine for me.
Usually I would write a function for it. Something like:
(defun run-through-states (function n start-state)
(let ((state start-state))
(dotimes (i n state)
(setf state (funcall function state)))))
and call that in my code:
(run-through-states (lambda (state) (build-nfa regex state))
n
next-state)
* Michal Przybylek
> What's your point?...
My point is that I'm not getting your point. Your suggestion of an
admittedly elegant "unfold + take-nth" seems to rely on lazy
evaluation for termination (but correct me if I'm wrong) and thus
would seem to be wrong in a non-lazy language.
So, either your point was that Common Lisp isn't a lazy language (duh)
or else I'm not yet getting what point you wanted to make.
--
Marcus
Dnia 15-09-2008 o 19:20:00 Marcus Breiing
<······@2008w36.mail.breiing.com> napisa�(a):
>> What's your point?...
>
> My point is that I'm not getting your point. Your suggestion of an
> admittedly elegant "unfold + take-nth" seems to rely on lazy
> evaluation for termination (but correct me if I'm wrong) and thus
> would seem to be wrong in a non-lazy language.
It doesn't rely. Laziness has slightly more than nothing to this pattern.
What really matters is how the standard library is designed. If CL
functions worked on the concept of ,,arbitrary abstract collection'', this
style of iteration would be fairly natural (see for example an
experimental language Kogut, which semantically is very similar to CL -
http://kokogut.sourceforge.net/kogut.html ; the same is true for most
languages that support generators).
I haven't said that you should use this pattern in Common Lisp. I've just
said that this is the right pattern (it decomposes the problem into two
unrelated parts). Of course, it's not always worth following ,,the right''
pattern.
--
Micha� Przyby�ek
* Michal Przybylek
> What really matters is how the standard library is designed. If CL
> functions worked on the concept of ,,arbitrary abstract
> collection'', this style of iteration would be fairly natural (see
> for example an experimental language Kogut, which semantically is
> very similar to CL - http://kokogut.sourceforge.net/kogut.html ; the
> same is true for most languages that support generators).
Thanks for clarifying your point. Your initial choice of terminology
made me assume you were talking about a (purely) functional pattern.
--
Marcus
??>> (loop :repeat n
??>> :for state := (build-nfa regex next-state)
??>> :then (build-nfa regex state)
??>> :finally (return state))
MP> is both - ugly and unlispy. Furthermore, I can add, that a code like:
are you sure you're not confusing Lisp with Haskell?
Dnia 14-09-2008 o 19:58:07 Alex Mizrahi <········@users.sourceforge.net>
napisa�(a):
> ??>> (loop :repeat n
> ??>> :for state := (build-nfa regex next-state)
> ??>> :then (build-nfa regex state)
> ??>> :finally (return state))
>
> MP> is both - ugly and unlispy. Furthermore, I can add, that a code
> like:
>
> are you sure you're not confusing Lisp with Haskell?
Pretty sure. I'm not saying that the imperative style is wrong in Lisp,
I'm saying that such a form of iteration is wrong in Lisp (i.e. keywords
aren't used in Lisp-like fashion).
--
Micha� Przyby�ek
In article <·················@dmn178.neoplus.adsl.tpnet.pl>,
"Michal Przybylek" <················@gmail.com> wrote:
> Dnia 14-09-2008 o 19:58:07 Alex Mizrahi <········@users.sourceforge.net>
> napisa�(a):
>
> > ??>> (loop :repeat n
> > ??>> :for state := (build-nfa regex next-state)
> > ??>> :then (build-nfa regex state)
> > ??>> :finally (return state))
> >
> > MP> is both - ugly and unlispy. Furthermore, I can add, that a code
> > like:
> >
> > are you sure you're not confusing Lisp with Haskell?
>
> Pretty sure. I'm not saying that the imperative style is wrong in Lisp,
> I'm saying that such a form of iteration is wrong in Lisp (i.e. keywords
> aren't used in Lisp-like fashion).
Although LOOP doesn't care about the packages of its keywords, many
people have adopted the above style so that the keywords stand out.
It's similar to writing SQL with all the keywords in uppercase.
I don't use it myself, but I can appreciate why others like it. The
only thing I fibnd particularly distasteful is :=, because it doesn't
look like an = with a keyword prefix, it looks like an Algol assignment
operator. But the ultimate cause of this problem is that the LOOP
designers chose to use a non-word keyword for this one feature; for
consistency, it might have been better to use a word like BEING:
(loop :repeat n
:for state :being (build-nfa regex next-state)
:then (build-nda regex state)
:finally (return state))
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***
??>>>> (loop :repeat n
??>>>> :for state := (build-nfa regex next-state)
??>>>> :then (build-nfa regex state)
??>>>> :finally (return state))
??>>
MP>>> is both - ugly and unlispy. Furthermore, I can add, that a code
??>> like:
??>>
??>> are you sure you're not confusing Lisp with Haskell?
MP> Pretty sure. I'm not saying that the imperative style is wrong in Lisp,
MP> I'm saying that such a form of iteration is wrong in Lisp
the idea of lisp IMHO is that you can have quite alternative syntax without
using custom parser/lexer stuff and headache of operating on text level.
in this sense LOOP is quite a lispy thing. some might not like it
aestetically
-- too few parentheses -- but there is nothing really wrong with it.
MP> (i.e. keywords aren't used in Lisp-like fashion).
bullshit. it's not far from keyword parameters, actually.
i could make a macro for this:
(defmacro loop-x (&key repeat initially for then finally)
`(let ((,for ,initially))
(dotimes (#:i ,repeat) (setf ,for ,then))
,finally))
then call would look like:
(loop-x :repeat n
:initially next-state
:for state
:then (build-nfa regex state)
:finally (return state))
the only difference is that LOOP has a bit more syntax in :for part.
do you say that keyword parameters are unlispy???
Dnia 14-09-2008 o 23:19:50 Alex Mizrahi <········@users.sourceforge.net>
napisa�(a):
> MP> (i.e. keywords aren't used in Lisp-like fashion).
>
> bullshit. it's not far from keyword parameters, actually.
> i could make a macro for this:
>
> (defmacro loop-x (&key repeat initially for then finally)
> `(let ((,for ,initially))
> (dotimes (#:i ,repeat) (setf ,for ,then))
> ,finally))
>
> then call would look like:
>
> (loop-x :repeat n
> :initially next-state
> :for state
> :then (build-nfa regex state)
> :finally (return state))
>
> the only difference is that LOOP has a bit more syntax in :for part.
Aha. So why doesn't the following code work:
(loop :collect i
:for i
:from 0
:below 10 )
?
--
Micha� Przyby�ek
??>> (defmacro loop-x (&key repeat initially for then finally)
??>> `(let ((,for ,initially))
??>> (dotimes (#:i ,repeat) (setf ,for ,then))
??>> ,finally))
??>>
??>> then call would look like:
??>>
??>> (loop-x :repeat n
??>> :initially next-state
??>> :for state
??>> :then (build-nfa regex state)
??>> :finally (return state))
??>>
??>> the only difference is that LOOP has a bit more syntax in :for part.
MP> Aha. So why doesn't the following code work:
MP> (loop :collect i
MP> :for i
MP> :from 0
MP> :below 10 )
MP> ?
because LOOP hasa bit more syntax..
Dnia 14-09-2008 o 23:45:48 Alex Mizrahi <········@users.sourceforge.net>
napisa�(a):
> ??>> (loop-x :repeat n
> ??>> :initially next-state
> ??>> :for state
> ??>> :then (build-nfa regex state)
> ??>> :finally (return state))
> ??>>
> ??>> the only difference is that LOOP has a bit more syntax in :for
> part.
>
> MP> Aha. So why doesn't the following code work:
>
> MP> (loop :collect i
> MP> :for i
> MP> :from 0
> MP> :below 10 )
>
> MP> ?
>
> because LOOP hasa bit more syntax..
in :for part, right?... You are not honest, are you?
The key difference between key arguments and positional arguments is that
the firsts rely on keys instead of positions. The above code breaks this
rule.
--
Micha� Przyby�ek
P� Mon, 15 Sep 2008 11:46:58 +0200, skrev Michal Przybylek
<················@gmail.com>:
>
>
> The key difference between key arguments and positional arguments is
> that the firsts rely on keys instead of positions. The above code breaks
> this rule.
>
>
indeed. loop is a macro that defines it's own language. Which is a
perfectly lispy thing to do. The symbols generated by the reader are not
really used as keywords. There is no rule that sais a macro MUST behave
like a function. In fact the whole point of macros is to allow control
over syntax and order of execution.
--------------
John Thingstad
"Michal Przybylek" <················@gmail.com> writes:
> The key difference between key arguments and positional arguments is
> that the firsts rely on keys instead of positions. The above code
> breaks this rule.
Anyways, my reason to use keyboard instead of mere symbols, is foremost this:
(defpackage "UTILITIES"
(:use "CL")
(:export "FOR" "WHILE"))
(loop for i from 0 to 10 while (evenp (* i i)))
(use-package "UTILITIES")
Since some LOOP keywords are not exported from CL, they will be
interned as normal symbols in the current package. If you later
import symbols of same name from another package, you break into the
debugger, and I don't like this.
--
__Pascal Bourguignon__
MP>>> Aha. So why doesn't the following code work:
??>>
MP>>> (loop :collect i
MP>>> :for i
MP>>> :from 0
MP>>> :below 10 )
??>>
MP>>> ?
??>>
??>> because LOOP hasa bit more syntax..
MP> in :for part, right?... You are not honest, are you?
it seems we've lost point we are discussing. for sure LOOP defines quite
complex syntax, and you can have complex stuff with it.
but _most_ LOOPs are relatively simple, and in those simple LOOPs keywords
are used almost like they are used in keyword
parameters.
from aestetics point of view (i thought we were discussing), it doesn't
matter what _can_ be done with LOOP, it only matters
how it _looks_. and as we see it looks quite familiar.
if we are discussing broader topic of keyword semantics, i'd like to point
that keywords are not just a thing to use
in keyword parameters, that's just a handy symbol that evaluates to itself
and always is interned in keywords package.
it makes sense to use it wherever you need to label something -- like
labeling individual parameters in keyword parameters
list or labeling parts of plist or labeling parts of loop. so using keywords
in LOOP macro is certified as 100% sane Lisp.
if you can think of keywords only as labels for keyword parameters, that
only means you have a narrow view and
do not actually understand lisp.
MP> The key difference between key arguments and positional arguments is
MP> that the firsts rely on keys instead of positions. The above code
MP> breaks this rule.
the truth is there is no such rule -- it's not present in standard, neither
is common
usage practice.
Matthew D Swank <··················@gmail.com> writes:
> Is there any way I can do this fold w/o the setf?
>
> (loop :with state := next-state
> :for i :from 0 :below n
> :do (setf state (build-nfa regex state))
> :finally (return state)))
What about:
(loop :repeat n
:for state = next-state :then (build-nfa regex state)
:finally (return state))
--
Thomas A. Russ, USC/Information Sciences Institute
On Sep 15, 12:53 pm, ····@sevak.isi.edu (Thomas A. Russ) wrote:
> Matthew D Swank <··················@gmail.com> writes:
>
> > Is there any way I can do this fold w/o the setf?
>
> > (loop :with state := next-state
> > :for i :from 0 :below n
> > :do (setf state (build-nfa regex state))
> > :finally (return state)))
>
> What about:
>
> (loop :repeat n
> :for state = next-state :then (build-nfa regex state)
> :finally (return state))
>
> --
> Thomas A. Russ, USC/Information Sciences Institute
See http://groups.google.com/group/comp.lang.lisp/msg/559cd82e66209742
I misread Pascal's loop as the one you give in the parent, so I think
my critique applies, with the added caveat that that the loop needs to
return next-state when n = 0 (as the original, but neither yours nor
Pascal's does).