Writing a procedure in different style

Writing a procedure in different style

[Zelphir Kaltstahl]

Hello Guile Users!

I've been using PEG parsing lately a few times, for advent of code and
needed to write a procedure, which would give me a subtree of the
peg-tree, searching by any criteria. So what I did is writing a
procedure, which takes a predicate and if that predicate is #t then I
would collect the subtree for which it is true into a list.

Problem was, that those subtrees could be on different depths of the
tree, depending on the grammar I defined. So my initial version would
give me back all occurrences of any predicate fulfilling subtree, but in
a list, which was not flat. So I thought for a few hours on and off, how
I could solve it and tried various incantations of (list ...) (cons ...)
and (append ...), for the recursive calls of the procedure, but none
would get the resulting list in ways I wanted. Then I had an idea: I
could use a continuation! I would "flatten" the structure, by giving the
continuation of "where else to look for more subtrees" as an argument
and could later on put it all on the same level. Perhaps this is
difficult to describe and here is my code:

~~~~
(define find-in-tree*
  (λ (peg-tree filter-proc)

    (define traverse
      (λ (subtree cont)
        (simple-format (current-output-port)
                       "working with subtree ~a\n"
                       subtree)
        (cond
         [(null? subtree) (cont)]
         [(pair? (first subtree))
          (traverse (first subtree)
                    (λ () (traverse (cdr subtree) cont)))]
         [(filter-proc (first subtree))
          (cons subtree (cont))]
         [else
          (traverse (cdr subtree) cont)])))

    (traverse peg-tree (λ () '()))))
~~~~

(I know, I could probably use a named let here, but somehow I like the
current form of it with the inner define, SICP style.)

(I've only tested this for the parsing here:
https://notabug.org/ZelphirKaltstahl/advent-of-code/src/b676eb5ad7f1c61c84585346ebf36f9fb9f6f8d1/2020/day-07
in puzzle 1. I should probably write some tests for it, for more wildly
nested trees. The procedure is in peg-tree-utils.scm. The program can be
called with `guile -L . puzzle-01.scm input`.)

I am wondering however, whether there is a way to write the procedure
without resorting to mutation (so no hash table or vector) and
continuations. I could not find the correct version without using
continuations. Not that using continuations is inherently bad, I simply
think perhaps there is an alternative version, which is simple, but
which I could not find.

Best wishes,
Zelphir

-- 
repositories: https://notabug.org/ZelphirKaltstahl

Re: Writing a procedure in different style

[Taylan Kammer]

On 12.12.2020 13:22, Zelphir Kaltstahl wrote:
> ~~~~
> (define find-in-tree*
>    (λ (peg-tree filter-proc)
> 
>      (define traverse
>        (λ (subtree cont)
>          (simple-format (current-output-port)
>                         "working with subtree ~a\n"
>                         subtree)
>          (cond
>           [(null? subtree) (cont)]
>           [(pair? (first subtree))
>            (traverse (first subtree)
>                      (λ () (traverse (cdr subtree) cont)))]
>           [(filter-proc (first subtree))
>            (cons subtree (cont))]
>           [else
>            (traverse (cdr subtree) cont)])))
> 
>      (traverse peg-tree (λ () '()))))
> ~~~~

 From what I can tell, the continuation argument is essentially used as 
a way of queuing up further work that is to be done.  Adding an element 
is done by wrapping it in yet another procedure that adds some work, and 
popping an element is done by applying it.

This means it should be possible to change it into an explicit data 
structure (e.g. simply a list).  Here's an attempt, which I have not 
tested in any way:

   (define find-in-tree*
      (λ (peg-tree filter-proc)

        (define traverse
          (λ (subtree rest)
            (simple-format (current-output-port)
                           "working with subtree ~a\n"
                           subtree)
            (cond
             [(null? subtree)
              (if (null? rest)
                  '()
                  (traverse (car rest) (cdr rest))]
             [(pair? (first subtree))
              (traverse (first subtree)
                        (cons (cdr subtree) rest))]
             [(filter-proc (first subtree))
              (cons subtree
                    (traverse (car rest) (cdr rest)))]
             [else
              (traverse (cdr subtree) rest)])))

        (traverse peg-tree '())))

In summary:

- I rename 'cont' to 'rest'

- I change
   (cont)
   to
   (if (null? rest) '() (traverse (car rest) (cdr rest)))

- I change
   (λ () (traverse (cdr subtree) cont))
   to
   (cons (cdr subtree) rest)

- I change the initial seed of
   (λ () '())
   to
   '()

And I think theoretically it should behave the same.


Taylan

Re: Writing a procedure in different style

[Taylan Kammer]

On 13.12.2020 08:06, Taylan Kammer wrote:
> 
>    (define find-in-tree*
>       (λ (peg-tree filter-proc)
> 
>         (define traverse
>           (λ (subtree rest)
>             (simple-format (current-output-port)
>                            "working with subtree ~a\n"
>                            subtree)
>             (cond
>              [(null? subtree)
>               (if (null? rest)
>                   '()
>                   (traverse (car rest) (cdr rest))]
>              [(pair? (first subtree))
>               (traverse (first subtree)
>                         (cons (cdr subtree) rest))]
>              [(filter-proc (first subtree))
>               (cons subtree
>                     (traverse (car rest) (cdr rest)))]
>              [else
>               (traverse (cdr subtree) rest)])))
> 
>         (traverse peg-tree '())))

Correction, for third branch of the cond that didn't check if rest is null:

   (define find-in-tree*
      (λ (peg-tree filter-proc)

        (define traverse
          (λ (subtree rest)
            (simple-format (current-output-port)
                           "working with subtree ~a\n"
                           subtree)
            (cond
             [(null? subtree)
              (if (null? rest)
                  '()
                  (traverse (car rest) (cdr rest)))]
             [(pair? (first subtree))
              (traverse (first subtree)
                        (cons (cdr subtree) rest))]
             [(filter-proc (first subtree))
              (cons subtree
                    (if (null? rest)
                        '()
                        (traverse (car rest) (cdr rest))))]
             [else
              (traverse (cdr subtree) rest)])))

        (traverse peg-tree '())))


Taylan

Re: Writing a procedure in different style

[Zelphir Kaltstahl]

Hello Taylan!

I tried your procedure and indeed it seems to work : )

I think what I had been missing before were 2 things:

1. I did not have the (if (null? rest) ...) parts, so I always tried to
directly make a recursive call, perhaps wrapped into a cons, append or
list. But if the rest was not null, then this would always add some
level of nesting to my result, when it finally returned, which I did not
want. The (if (null? rest) ...) part makes sure, that the empty list is
given instead.

2. The fact that I could simply cons onto the rest, because the
procedure works with arbitrarily nested lists anyway.

Thanks for your input!

Regards,
Zelphir

On 13.12.20 12:51, Taylan Kammer wrote:
> On 13.12.2020 08:06, Taylan Kammer wrote:
>>
>>    (define find-in-tree*
>>       (λ (peg-tree filter-proc)
>>
>>         (define traverse
>>           (λ (subtree rest)
>>             (simple-format (current-output-port)
>>                            "working with subtree ~a\n"
>>                            subtree)
>>             (cond
>>              [(null? subtree)
>>               (if (null? rest)
>>                   '()
>>                   (traverse (car rest) (cdr rest))]
>>              [(pair? (first subtree))
>>               (traverse (first subtree)
>>                         (cons (cdr subtree) rest))]
>>              [(filter-proc (first subtree))
>>               (cons subtree
>>                     (traverse (car rest) (cdr rest)))]
>>              [else
>>               (traverse (cdr subtree) rest)])))
>>
>>         (traverse peg-tree '())))
>
> Correction, for third branch of the cond that didn't check if rest is
> null:
>
>   (define find-in-tree*
>      (λ (peg-tree filter-proc)
>
>        (define traverse
>          (λ (subtree rest)
>            (simple-format (current-output-port)
>                           "working with subtree ~a\n"
>                           subtree)
>            (cond
>             [(null? subtree)
>              (if (null? rest)
>                  '()
>                  (traverse (car rest) (cdr rest)))]
>             [(pair? (first subtree))
>              (traverse (first subtree)
>                        (cons (cdr subtree) rest))]
>             [(filter-proc (first subtree))
>              (cons subtree
>                    (if (null? rest)
>                        '()
>                        (traverse (car rest) (cdr rest))))]
>             [else
>              (traverse (cdr subtree) rest)])))
>
>        (traverse peg-tree '())))
>
>
> Taylan

-- 
repositories: https://notabug.org/ZelphirKaltstahl

Re: Writing a procedure in different style

[tomas]

[-- Attachment #1: Type: text/plain, Size: 1094 bytes --]

On Sun, Dec 13, 2020 at 01:29:31PM +0100, Zelphir Kaltstahl wrote:
> Hello Taylan!
> 
> I tried your procedure and indeed it seems to work : )
> 
> I think what I had been missing before were 2 things:
> 
> 1. I did not have the (if (null? rest) ...) parts, so I always tried to
> directly make a recursive call, perhaps wrapped into a cons, append or

    "When recurring on a list of atoms, /lat/, ask
    two questions about it: /(null? lat)/ and *else*.
    When recurring on a number, /n/, ask two
    questions about it: /(zero? n)/ and *else*.
    When recurring on a list of S-expressions, /l/,
    ask three question about it: /(null? l)/, /(atom?
    ( car l))/, and *else*."

Daniel P. Friedman and Matthias Felleisen: The Little Schemer [1]
"First Commandment".

Now before this sounds arrogant or something: this is a botch
I'd be very likely to do myself. That's perhaps why this book,
which at first sight looks so harmless, was for me a joy to read.

Cheers

[1] https://pdfs.semanticscholar.org/35d0/d5275a8390c351ce98fbdc2ad37d210ba63b.pdf

 - t

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

Re: Writing a procedure in different style

[Zelphir Kaltstahl]

Hi Tomas!

In some way what you write makes sense. Let me state here, that I did
read that book and worked through it for a year though, even through the
complicated parts like the y-combinator and some chapters I must have
read like 4 or 5 times and discovered new aspects on each try.

What is typically the case in the book is a different situation though,
than what was in Taylan's procedure. Usually it is the list you are
working on in that iteration, which you check for being (null? ...), not
the thing, that you give as argument to a recursive call or as a return
value, which you add in some way to the result. Usually the questions
from the quote are asked once the argument is received in the next
iteration. That I definitely usually do, but in Taylan's answer there is
an (if (null? ...) ...) for the `rest`, inside the case, where the usual
(null? ...) check is already done on the subtree, which we recur on.

Perhaps I did not recognize the similarity there. Perhaps the rule from
TLS is applies more broadly, than I was aware of. And perhaps that is
something, that I can take from your reply! Thanks!

Anyway, it is at least also new aspect, that I got from Taylan's answer.

Regards,
Zelphir


On 12/13/20 3:24 PM, tomas@tuxteam.de wrote:
> On Sun, Dec 13, 2020 at 01:29:31PM +0100, Zelphir Kaltstahl wrote:
>> Hello Taylan!
>>
>> I tried your procedure and indeed it seems to work : )
>>
>> I think what I had been missing before were 2 things:
>>
>> 1. I did not have the (if (null? rest) ...) parts, so I always tried to
>> directly make a recursive call, perhaps wrapped into a cons, append or
>     "When recurring on a list of atoms, /lat/, ask
>     two questions about it: /(null? lat)/ and *else*.
>     When recurring on a number, /n/, ask two
>     questions about it: /(zero? n)/ and *else*.
>     When recurring on a list of S-expressions, /l/,
>     ask three question about it: /(null? l)/, /(atom?
>     ( car l))/, and *else*."
>
> Daniel P. Friedman and Matthias Felleisen: The Little Schemer [1]
> "First Commandment".
>
> Now before this sounds arrogant or something: this is a botch
> I'd be very likely to do myself. That's perhaps why this book,
> which at first sight looks so harmless, was for me a joy to read.
>
> Cheers
>
> [1] https://pdfs.semanticscholar.org/35d0/d5275a8390c351ce98fbdc2ad37d210ba63b.pdf
>
>  - t

-- 
repositories: https://notabug.org/ZelphirKaltstahl

Re: Writing a procedure in different style

[tomas]

[-- Attachment #1: Type: text/plain, Size: 1492 bytes --]

On Sun, Dec 13, 2020 at 04:01:24PM +0100, Zelphir Kaltstahl wrote:
> Hi Tomas!
> 
> In some way what you write makes sense. Let me state here, that I did
> read that book and worked through it for a year though, even through the
> complicated parts like the y-combinator and some chapters I must have
> read like 4 or 5 times and discovered new aspects on each try.

That's it -- I'm through some n-th iteration and still go "oh!" from
time to time :-D

> What is typically the case in the book is a different situation though,
> than what was in Taylan's procedure. Usually it is the list you are
> working on in that iteration, which you check for being (null? ...), not
> the thing, that you give as argument to a recursive call or as a return
> value, which you add in some way to the result. Usually the questions
> from the quote are asked once the argument is received in the next
> iteration. That I definitely usually do, but in Taylan's answer there is
> an (if (null? ...) ...) for the `rest`, inside the case, where the usual
> (null? ...) check is already done on the subtree, which we recur on.

I have the hunch that this is only shifting things one level
up or down the stack, but basically, it's the same principle
at work. I'd have to fiddle for a while with that to see whether
I'm totally off, though.

Anyway, a reminder for me to do the n+1st iteration: "Do It, Do
It Again, and Again, and Again, ..." :-)

Thanks for that!

Cheers
 - t

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

Re: Writing a procedure in different style

[Zelphir Kaltstahl]

Hello Tomas!

I think you are right about it only being down one stack frame down. The
checks are performed on what contains the next thing which is recurred on.

For a moment I thought "But isn't the null? check done twice in the
first cond part?" But then I realized, that the rest is split up into
car and cdr before recurring on it and that the first check if for the
whole of rest, while in the next iteration, the check would only be for
the car of rest. So no duplicated work.

On 13.12.20 16:43, tomas@tuxteam.de wrote:
> On Sun, Dec 13, 2020 at 04:01:24PM +0100, Zelphir Kaltstahl wrote:
>> Hi Tomas!
>>
>> In some way what you write makes sense. Let me state here, that I did
>> read that book and worked through it for a year though, even through the
>> complicated parts like the y-combinator and some chapters I must have
>> read like 4 or 5 times and discovered new aspects on each try.
> That's it -- I'm through some n-th iteration and still go "oh!" from
> time to time :-D
>
>> What is typically the case in the book is a different situation though,
>> than what was in Taylan's procedure. Usually it is the list you are
>> working on in that iteration, which you check for being (null? ...), not
>> the thing, that you give as argument to a recursive call or as a return
>> value, which you add in some way to the result. Usually the questions
>> from the quote are asked once the argument is received in the next
>> iteration. That I definitely usually do, but in Taylan's answer there is
>> an (if (null? ...) ...) for the `rest`, inside the case, where the usual
>> (null? ...) check is already done on the subtree, which we recur on.
> I have the hunch that this is only shifting things one level
> up or down the stack, but basically, it's the same principle
> at work. I'd have to fiddle for a while with that to see whether
> I'm totally off, though.
>
> Anyway, a reminder for me to do the n+1st iteration: "Do It, Do
> It Again, and Again, and Again, ..." :-)
>
> Thanks for that!
>
> Cheers
>  - t

Regards,
Zelphir

-- 
repositories: https://notabug.org/ZelphirKaltstahl

Re: Writing a procedure in different style

[tomas]

[-- Attachment #1: Type: text/plain, Size: 849 bytes --]

On Sun, Dec 20, 2020 at 06:57:34PM +0100, Zelphir Kaltstahl wrote:
> Hello Tomas!
> 
> I think you are right about it only being down one stack frame down. The
> checks are performed on what contains the next thing which is recurred on.

Nice explanation :)

> For a moment I thought "But isn't the null? check done twice in the
> first cond part?" [...]

This is one of the fantastic (and scary) things I often experience
in this (scheme-y) context (take SICP, or the Little Schemer).

Everything looks so easy, but whenever I try myself, I realise that
I've been taken along a path along high mountains, with breathtaking
views, and down there it gets messy and there are crocodiles.

It takes a long time to massage one's messy, lowly programs into a
form which approaches that deep beauty.

But it's fun :)

Cheers
 - t

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

Re: Writing a procedure in different style

[Zelphir Kaltstahl]

Hey Tomas,

On 12/21/20 1:31 PM, tomas@tuxteam.de wrote:
> On Sun, Dec 20, 2020 at 06:57:34PM +0100, Zelphir Kaltstahl wrote:
>> Hello Tomas!
>>
>> I think you are right about it only being down one stack frame down. The
>> checks are performed on what contains the next thing which is recurred on.
> Nice explanation :)
>
>> For a moment I thought "But isn't the null? check done twice in the
>> first cond part?" [...]
> This is one of the fantastic (and scary) things I often experience
> in this (scheme-y) context (take SICP, or the Little Schemer).
>
> Everything looks so easy, but whenever I try myself, I realise that
> I've been taken along a path along high mountains, with breathtaking
> views, and down there it gets messy and there are crocodiles.
>
> It takes a long time to massage one's messy, lowly programs into a
> form which approaches that deep beauty.

I definitely agree!

When I went through the book and also through some SICP exercises, I was
amazed by how much is contained in just a short snippet of code and how
nuanced it can be.

I wonder how much crap code I write on the job, when I am not given as
much time, as I take in my free time, and even in my free time, I often
notice, that I could have written things more succinctly or in a more
idiomatic way or that some special case was not covered. If I look at my
time spent on writing code in a functional style, while trying to not
unnecessarily increase runtime complexity, compared with time spent on
code, that makes use of mutation or even global state, simply hoping
that things will work out later, I also get an idea of how much more one
can think about a short program and how much more there is to think about.

Writing code, a simple thing to learn, a very long (never ending)
journey to master.

I hope that the whole virus stuff will be over soon and I manage at some
point to join an event in the e-lok (it was e-lok something, wasn't it?) ; )

Best regards,
Zelphir

-- 
repositories: https://notabug.org/ZelphirKaltstahl