loop with dummy variable
Nick Keighley
that I'm thinking of it as a loop construct. I recently ended up with
this
(define (flush-stack)
(let loop ((x '())) ; x is a dummy argument
(if (not (stack-empty? stack))
(if (or (open-brak? (stack-top stack))
(close-brak? (stack-top stack)))
(error "infix->postfix: mismatched bracket")
(begin
(q-add! output (stack-pop! stack))
(loop '())
)))))
the dummy argument just looks *wrong*. The function is embedded in a
larger function that declares stack and output. The loop terminates
because stack-pop! modifies the value of stack. Should I be trying to
avoid mutation or is there a way to recurse without the bodgy named-
let?
--
Nick Keighley
Vitaly Magerya
> (define (flush-stack)
> (let loop ((x '())) ; x is a dummy argument
> (if (not (stack-empty? stack))
> (if (or (open-brak? (stack-top stack))
> (close-brak? (stack-top stack)))
> (error "infix->postfix: mismatched bracket")
> (begin
> (q-add! output (stack-pop! stack))
> (loop '())
> )))))
>
> the dummy argument just looks *wrong*. The function is embedded in a
> larger function that declares stack and output. The loop terminates
> because stack-pop! modifies the value of stack. Should I be trying to
> avoid mutation or is there a way to recurse without the bodgy named-
> let?
Why not just drop the dummy?
(let loop () (if (cold-outside?) (loop)))
In your example above you can also call (flush-stack) to recurse,
removing the need for an extra named let.
Nick Keighley
> Nick Keighley wrote:
> > (define (flush-stack)
> > (let loop ((x '())) ; x is a dummy argument
> > (if (not (stack-empty? stack))
> > (if (or (open-brak? (stack-top stack))
> > (close-brak? (stack-top stack)))
> > (error "infix->postfix: mismatched bracket")
> > (begin
> > (q-add! output (stack-pop! stack))
> > (loop '())
> > )))))
>
> > the dummy argument just looks *wrong*. The function is embedded in a
> > larger function that declares stack and output. The loop terminates
> > because stack-pop! modifies the value of stack. Should I be trying to
> > avoid mutation or is there a way to recurse without the bodgy named-
> > let?
>
> Why not just drop the dummy?
>
> (let loop () (if (cold-outside?) (loop)))
I could have sworn I tried that...
> In your example above you can also call (flush-stack) to recurse,
> removing the need for an extra named let.
(blush!) I /told/ you I was over-using named-let! I do on the other
hand have other examples where simple recursion won't work.
(define (do-operator token)
(let while-operators ())
(if (and (not (stack-empty? stack))
(operator? (stack-top stack)))
(if (<= (precedence token)
(precedence (stack-top stack)) )
(begin
(q-add! output (stack-pop! stack))
(while-operators)))))
(stack-push! stack token))
Grant Rettke
wrote:
> My scheme code tends to use named lets rather heavily. I'm suspicious
> that I'm thinking of it as a loop construct.
You think your code doesn't warrant the iteration?
Nick Keighley
I'm a C programmer learning scheme. I'm trying to avoid the you-can-
write-fortran-in-any-language syndrome. I was partly trying to confirm
that my scheme code was reasonably idiomatic. I /like/ named-let,
before I grokked it my code was filled with helper functions.
Aaron W. Hsu
<nick_keigh...@hotmail.com> wrote:
> I'm a C programmer learning scheme. I'm trying to avoid the you-can-
> write-fortran-in-any-language syndrome. I was partly trying to confirm
> that my scheme code was reasonably idiomatic. I /like/ named-let,
> before I grokked it my code was filled with helper functions.
Don't be afraid to use helper functions. Scheme programs that are written
well tend to have clear procedural abstraction that divides up tasks in a
much more granular way than idiomatic C code, because function calls are
cheap in Scheme.
Aaron W. Hsu
--
Of all tyrannies, a tyranny sincerely exercised for the good of its
victims may be the most oppressive. -- C. S. Lewis
dj3v...@csclub.uwaterloo.ca.invalid
If you're a C programmer trying to wrap your brain around Scheme, you
should definitely avoid mutation, not because there's anything wrong
with mutation but because it will make it too easy to write C-in-Scheme
instead of learning how to work with the functional style and idioms.
The "loop" construct you should be using the most in Scheme is simple
tail recursion; you can do this without the named let.
If I were writing this code (in Scheme), I'd probably pass around the
current stack instead of using mutation for that, and the code would
start out something like this:
--------
(define (flush-stack stack)
(cond
((stack-empty? stack) stack)
((or (open-brak? (stack-top stack))
(close-brak? (stack-top stack)))
(error "infix->postfix: mismatched bracket"))
(else
(q-add! output (stack-top stack))
(flush-stack (stack-pop stack)))))
--------
(Here stack-pop discards the top element of the stack and returns a new
stack without the top element.)
Note that this is still a loop (it's isomorphic to your version), but
the named let ends up being unnecessary.
If you use a list for the stack, you can use library functions to make
your life easier:
--------
;; Either throws an error or empties stack.
;; Does not return an interesting value; there's only one empty stack,
;; so the caller can make its own if it really wants one.
(define (flush-stack stack)
(for-each (lambda (elem)
(if (or (open-brak? elem) (close-brak? elem))
(error "infix->postfix: mismatched bracket")
(q-add! output elem)))
stack))
--------
(Even if you don't want to use a list for the stack, if you do a lot of
"walk through the stack until...", it may make sense to write your own
stack-foreach (or maybe stack-do-until) which you could use in a
similar manner.)
Depending on what you're doing with output, it may make sense to do a
similar conversion there, and pass around the current output queue
where it's useful instead of mutating a single copy. A flush-stack
that doesn't do any mutation would look something like:
--------
;; Either throws error or empties stack.
;; In the absence of errors, returns output queue with all elements
;; from stack pushed into it, in the order they were taken off the
;; stack.
(define (flush-stack stack output)
(foldl (lambda (elem q)
(if (or (open-brak? elem) (close-brak? elem))
(error "infix->postfix: mismatched bracket")
(q-add q elem)))
output
stack))
--------
Here q-add returns a new queue containing the items in its first
argument (old queue) plus its second argument (elem).
So, in summary, there's nothing grossly wrong with your original code,
but if you're trying to learn not to write C-in-Scheme you're not quite
there yet...
dave
--
Dave Vandervies dj3vande at eskimo dot com
(This is ambiguous if you happen to run the compiler at sunrise, but the
implementation is allowed to produce extraneous diagnostics.)
--Keith Thompson in comp.lang.c
dj3v...@csclub.uwaterloo.ca.invalid
Nick Keighley <nick_keigh...@hotmail.com> wrote:
>(blush!) I /told/ you I was over-using named-let! I do on the other
>hand have other examples where simple recursion won't work.
>
>(define (do-operator token)
> (let while-operators ())
> (if (and (not (stack-empty? stack))
> (operator? (stack-top stack)))
> (if (<= (precedence token)
> (precedence (stack-top stack)) )
> (begin
> (q-add! output (stack-pop! stack))
> (while-operators)))))
> (stack-push! stack token))
>
There's a perfectly sensible recursive implementation of that; just
push token onto the stack in your base case.
For extra credit, write stack-do-while so that this will do what you
want:
--------
(define (do-operator token stack)
(stack-push token
(stack-do-while (lambda (elem)
(and (operator? elem)
(<= (precedence token)
(precedence elem))))
(lambda (elem)
(q-add! output elem))
stack)))
--------
Nick Keighley
> In article <380bc114-95e6-4f57-b079-34f166572...@a32g2000yqm.googlegroups.com>,
> Nick Keighley <nick_keighley_nos...@hotmail.com> wrote:
> >My scheme code tends to use named lets rather heavily. I'm suspicious
> >that I'm thinking of it as a loop construct. I recently ended up with
> >this
>
> >(define (flush-stack)
> > (let loop ((x '())) ; x is a dummy argument
> > (if (not (stack-empty? stack))
> > (if (or (open-brak? (stack-top stack))
> > (close-brak? (stack-top stack)))
> > (error "infix->postfix: mismatched bracket")
> > (begin
> > (q-add! output (stack-pop! stack))
> > (loop '())
> > )))))
>
> >the dummy argument just looks *wrong*. The function is embedded in a
> >larger function that declares stack and output. The loop terminates
> >because stack-pop! modifies the value of stack. Should I be trying to
> >avoid mutation or is there a way to recurse without the bodgy named-
> >let?
>
> If you're a C programmer trying to wrap your brain around Scheme, you
> should definitely avoid mutation,
I started out that way but I've found mutations slipping back in.
> not because there's anything wrong
> with mutation but because it will make it too easy to write C-in-Scheme
> instead of learning how to work with the functional style and idioms.
yes, I can't see any point in learning to write C in a funny syntax.
> The "loop" construct you should be using the most in Scheme is simple
> tail recursion; you can do this without the named let.
>
> If I were writing this code (in Scheme), I'd probably pass around the
> current stack instead of using mutation for that, and the code would
> start out something like this:
> --------
> (define (flush-stack stack)
> (cond
> ((stack-empty? stack) stack)
> ((or (open-brak? (stack-top stack))
> (close-brak? (stack-top stack)))
> (error "infix->postfix: mismatched bracket"))
> (else
> (q-add! output (stack-top stack))
> (flush-stack (stack-pop stack)))))
> --------
> (Here stack-pop discards the top element of the stack and returns a new
> stack without the top element.)
> Note that this is still a loop (it's isomorphic to your version), but
> the named let ends up being unnecessary.
>
> If you use a list for the stack, you can use library functions to make
> your life easier:
yes, my stack was a list hidden behind a set of functions
> --------
> ;; Either throws an error or empties stack.
> ;; Does not return an interesting value; there's only one empty stack,
> ;; so the caller can make its own if it really wants one.
> (define (flush-stack stack)
> (for-each (lambda (elem)
> (if (or (open-brak? elem) (close-brak? elem))
> (error "infix->postfix: mismatched bracket")
> (q-add! output elem)))
> stack))
> --------
> (Even if you don't want to use a list for the stack, if you do a lot of
> "walk through the stack until...", it may make sense to write your own
> stack-foreach (or maybe stack-do-until) which you could use in a
> similar manner.)
>
> Depending on what you're doing with output, it may make sense to do a
> similar conversion there, and pass around the current output queue
> where it's useful instead of mutating a single copy.
yes, the so-called output queue was pretty clunky. The trouble is lost
of C leads you to "but that wouldn't be efficient!". But I'm trying to
reprogram myself.
I've code as far as confusing my inner-coder I start to type C for-
loops like this
(for i
and then I think an interrupt gets generated "is that let or = next"?
> A flush-stack
> that doesn't do any mutation would look something like:
> --------
> ;; Either throws error or empties stack.
> ;; In the absence of errors, returns output queue with all elements
> ;; from stack pushed into it, in the order they were taken off the
> ;; stack.
> (define (flush-stack stack output)
> (foldl (lambda (elem q)
> (if (or (open-brak? elem) (close-brak? elem))
> (error "infix->postfix: mismatched bracket")
> (q-add q elem)))
> output
> stack))
> --------
foldl? One of them functional programming thingies? <pause>
Ok, it's a HoF that "folds" or "accumlates" a list (or in general any
other collection) of values tograther to form a result.
fold-left and fold-right were added to R6RS.
Just curious, if scheme is to an extent a functional language why
wasn't "fold" in there in the first place? I couldn't even find a HoF
SRFI. Too obvious?
Ah! SRFI 1 has filter and SRFI 26 has fold.
More Ah! there's lots of stuff in srfi-1 fold, unfold, filter,
partition
> Here q-add returns a new queue containing the items in its first
> argument (old queue) plus its second argument (elem).
>
> So, in summary, there's nothing grossly wrong with your original code,
> but if you're trying to learn not to write C-in-Scheme you're not quite
> there yet...
thanks!
Aaron W. Hsu
<nick_keigh...@hotmail.com> wrote:
> yes, the so-called output queue was pretty clunky. The trouble is lost
> of C leads you to "but that wouldn't be efficient!". But I'm trying to
> reprogram myself.
As a note here, efficiency can be important, but if you care about
efficiency in Scheme, it pays not to think like a C programmer. Scheme can
be very efficient, but you have to look at it through a different filter.
Mutation in Scheme can often be less efficient than the functional style.
Recursion is sometimes faster than iteration, and so forth. In Scheme,
different things become more efficient than in C. Thus, it's best if you
start with a book like The Little Schemer, or TSPL, or SICP, which will
show you familiar, basic concepts in a different style, and you can
probably build up from there.
Nick Keighley
> On Thu, 05 Nov 2009 06:23:37 -0500, Nick Keighley
> > yes, the so-called output queue was pretty clunky. The trouble is [lots]
> > of C leads you to "but that wouldn't be efficient!". But I'm trying to
> > reprogram myself.
>
> As a note here, efficiency can be important, but if you care about
> efficiency in Scheme, it pays not to think like a C programmer.
I was kind of gathering that (I've tell of Stalin for instance). Years
of wondering where every bit falls kind of of distorts your view.
> Scheme can
> be very efficient, but you have to look at it through a different filter.
> Mutation in Scheme can often be less efficient than the functional style.
ah. I'll try harder to functional
> Recursion is sometimes faster than iteration, and so forth. In Scheme,
> different things become more efficient than in C. Thus, it's best if you
> start with a book like The Little Schemer, or TSPL, or SICP, which will
> show you familiar, basic concepts in a different style, and you can
> probably build up from there.
I'm SICPing (actually I've not picked it up for a while- maybe that's
caused the back sliding)
Aaron W. Hsu
<nick_keigh...@hotmail.com> wrote:
> I'm SICPing (actually I've not picked it up for a while- maybe that's
> caused the back sliding)
Good luck then!
Andrew Reilly
> The trouble is lost
> of C leads you to "but that wouldn't be efficient!". But I'm trying to
> reprogram myself.
After a couple of projects that I've done in scheme, after many years of
C (and assembler), I've come to the conclusion that even *starting* a
program in C is an exercise in premature optimization. Correctness
trumps everything, and algorithm design and selection trump brute force.
C doesn't help much with either of those. There isn't even a place for C
until you're well into your first or second revision...
Cheers,
--
Andrew
Nick Keighley
> On Thu, 05 Nov 2009 03:23:37 -0800, Nick Keighley wrote:
> > The trouble is [lots]
> > of C leads you to "but that wouldn't be efficient!". But I'm trying to
> > reprogram myself.
>
> After a couple of projects that I've done in scheme, after many years of
> C (and assembler), I've come to the conclusion that even *starting* a
> program in C is an exercise in premature optimization. Correctness
> trumps everything, and algorithm design and selection trump brute force.
> C doesn't help much with either of those. There isn't even a place for C
> until you're well into your first or second revision...
interesting thoughts