for loop and break

[Yanyan]

Hi,

I'm having some trouble with for loops, in terms of conciseness and break.

1. how do I write a program equivalent to this (Python syntax):

for a in range(1, 1000):

    for b in range(1, 1000):

       print a+b

Right now, I wrote this:

for map(elem from range(0, 999)):

  a = elem + 1

  for map(elt from range(0, 999)):

    b = elt + 1

    print(a + b)

  end

end

Is there a shorter/simpler way to write this?

2. How do I break out of a for loop?

Thanks!

Yanyan

[Shriram Krishnamurthi]

Hi,

Thanks for your question.

The essence of Pyret is to think of computation as consuming and producing values, not to think about language constructs. That means we want to first think about what computational goal we're trying to accomplish. Therefore, if you don't mind, I'm going to take a Socratic approach to answering your question.

So let me ask you to instead think about concrete examples of what you want to compute. Say these loops lived within a function, `f`, which took the two lists you're iterating over as an argument. Can you give me some examples of input-output pairs for `f`? For instance, say as a check block (though that's optional)? For instance

check:

  f(empty, empty) is <<< what? >>>

  f(range(1, 10), range(1, 10)) is <<< what? >>>

  f(range(1, 10), range(1, 1000)) is <<< what? >>>

  f(range(1, 1000), range(1, 1000)) is <<< what? >>>

end

Because until we know what computation you're trying to achieve, it's not very meaningful to talk about what constructs will get us there.

I know this is a pretty frustrating and complicated response to what sounds like a simple question. What I'm trying to do is get you the gestalt of thinking about computation in a value-oriented way, and this is the first step to that.

Shriram

[Yanyan]

Hi Shriram,

thanks for the reply. Now I realize it's hard to talk about my questions without the actual problem.

Here's what I'm trying to solve: 

For natural numbers a < b < c, a + b + c = 1000, and a² + b² = c²

What is the value of abc?

I'm using two for loops to iterate through values for a and b, and then check if they satisfy the equation. Here's my whole program:

for map(a from range(1, 1000)):

  for map(b from range(1, 1000)):

    c = 1000 - a - b

    when (c > 0) and (((a * a) + (b * b)) == (c * c)):

      print(a * b * c)

    end  

  end

end

There are two things that bother me.

1. for loop looks kind of complicated (though a bit better than my first post, now it doesn't have the step a = elmt + 1). Using map here feels unnecessary. Is there a better way to iterate through range(1, 1000)?

2. When I reach the print statement, I should end the program. So how do I break from a for loop?

Thanks,

Yanyan

[Yanyan]

Today Joe and I discussed my questions in details (thanks Joe!). Here's what I learned, and some more questions.

1. "for" in Pyret is not the same thing as Python. 

In Python, "for" is used for iteration; in Pyret, "for" is used for applying functions over a list. 

2. A better built-in function to iterate through 1 to 1000 is each.

e. g. for each(a from range(1, 1001)):

The difference between each and map is that each returns nothing, and map returns a list.

Here's my improved-for-loop program solving the same problem: https://code.pyret.org/editor#share=0B2FZe8qT7G81aTk0czQzSTRBS3c&v=v0.5r1440

3. PAPL's design recipe teaches recursion at the very beginning, instead of focusing on iteration. So another way to tackle the problem is to think in terms of input-output and designing reusable recursive functions. (Shriram explained this idea better in his reply above)

4. I tried to follow the recipe and came up with a recursion version:

https://code.pyret.org/editor#share=0B2FZe8qT7G81WVU1RlEtU3dCODQ&v=v0.5r1440

However, I feel like I'm still trying to translate nested loops. Maybe I'm too comfortable with iteration. 

Can I get some critiques on this program? Why doesn't it feel like legit recursion? Is there a better recursion solution for this problem?

Thanks!

Yanyan

[Joe Gibbs Politz]

Thanks for the summary, Yanyan!

> 3. PAPL's design recipe teaches recursion at the very beginning, instead of
> focusing on iteration. So another way to tackle the problem is to think in
> terms of input-output and designing reusable recursive functions. (Shriram
> explained this idea better in his reply above)

It's worth saying that there are two separate ideas here:

1. Thinking in terms of input-output, which helps us design reusable,
testable functions
2. Designing specifically _recursive_ functions

The first urges you to write this program as a function rather than a
toplevel printing statement, whether the function is recursive or
iterative or whatever. This gives us a function that's testable,
parameterizable, etc.

It turns out that there's a whole bunch of good pedagogic reasons to
do the latter (learning to write recursive functions) in order to get
to the former (implementations of input-output specifications).


But it's obviously not true that all good reusable functions are
recursively implemented. So it's worth asking how we can write
iterative(-looking) programs to do the former.

In this case, something like "for find(...): ... end" would work well,
if we had a good way to get the cross-product of two lists and iterate
over it. Here's a solution that uses tuples (upcoming feature! more
on that soon) to do that, in a nicely iterative-looking solution that
stops at the right answer:

https://pyret-horizon.herokuapp.com/editor#share=0B32bNEogmncOWEVpdFhxTVdnVXM

(The weakness of this solution is that is creates the whole one
million-length list first to traverse. It would be nice to not do
that work somehow, which the recursive solution accomplished. In the
for loop, we'd need a better lazy version of cross() to avoid creating
the big list first.)

[Mark Engelberg]

Another weakness of the solution is that both a and b range from 1 to 1000, whereas in the original statement of the problem we could break symmetry and reduce the problem space by assuming a <= b, i.e., ranging a from 1 to 1000 and b from a to 1000.  So not only would you benefit from a lazy version of cross, but you would benefit from a version where the second argument was contingent upon the first.

This hearkens back to my post from last summer asking about support for comprehension syntax, and this sort of nested for loop problem is exactly the kind of thing I was talking about.  My point at the time was that I see students get bogged down in the details of writing a custom version of cross for their problem, where the right syntactic construct makes it much easier to focus on the problem at hand.

To me, this problem is a good example of why the existing Pyret for syntax is not (yet) sufficiently rich.  At the time, you said comprehension syntax wasn't completely off the table, it was just set aside for the time being because of the complexity of making it work within the type system.  Maybe tuples will make this more tractable?

--
You received this message because you are subscribed to the Google Groups "Pyret Discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pyret-discus...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Shriram Krishnamurthi]

Sorry for the late reply.

Yes, Mark, you're absolutely right. I personally am more and more

convinced that `for` is really not that great.

Part of our bias is pedagogic. The focus of the kind of problems in

HtDP has been strongly _away_ from this kind (as you well know, but

saying this for the benefit of others). So these haven't really been

an issue.

The kinds of questions we're tackling in Pyret and PAPL is

increasingly different, and our users are pulling us in new places as

well. As these evolve, so does our thinking.

We have some really neat new work coming up in a general bracket we're

calling "lightweight data science". That, for sure, is stretching us

in new dimensions. One of the things I really like about that work is

that it's giving us some means to side-step the whole "loop vs

recursion" debate (the right answer there is, you write somewhat

declarative commands that operate over tables…). This work came about

in part as a reaction to the "`for` is not good enough" mindset,

except it led us in a different way (a bit SQL-inspired).

So, we're not disregarding your suggestion. This is something Pyret

just does poorly. I believe there are many things it does really well,

and that set is growing quite a bit (our new table support will come

online in the next few weeks; already very much available in the

repo). Translating programs that are natural in other languages

doesn't showcase what Pyret does well, for sure.

Shriram

[Mark Engelberg]

On Sat, Jul 16, 2016 at 11:22 AM, Shriram Krishnamurthi <s...@cs.brown.edu> wrote:

Part of our bias is pedagogic. The focus of the kind of problems in

HtDP has been strongly _away_ from this kind (as you well know, but

saying this for the benefit of others). So these haven't really been

an issue.

I would certainly agree that the iterative formulation of for doesn't have a lot of relevance to the Htdp approach.  The original example that triggered this thread wanted to print tuples that satisfy a certain condition to the screen, and Htdp has convinced me that's not something we should be encouraging students to do.  Something that prints to the screen can't easily be composed with other things, so we want to formulate such problems in terms of returning a list of all such tuples, or maybe returning the first such tuple.  Printing should happen automatically at the REPL, keeping the student focus on making composable components.

But `for` as a comprehension syntax is a somewhat different story, in my mind.  We don't want to introduce it too soon, because then it comes across as a magical syntax that does too much for the students.  We want them to learn how to solve such problems using simple constructs because gaining a deep understanding of how you generate and traverse recursive data structures is a large focus of the curriculum.  But at some point, it's very useful to have a syntax that lets you focus on the problem at hand, not the details of looping/accumulating. 

Consider the problem of generating all permutations, which is a major case study in Htdp, one of the harder problems that students encounter.  It's a wonderful exercise to go through, but if students had to re-derive that process every time, from scratch, each time they wanted to solve a problem for which permutations was a sub-component of the problem, that would really bog students down.  Generating all the Cartesian product of certain lists where the tuples satisfy certain conditions is, in my view, a very similar kind of thing.  We certainly want students to know how to do it, but re-inventing this from scratch every time gets distracting.  However, with permutations, the students can just build up a library of functions they've written, stick permutations in that library and "require" that library, and use it in later problems.  My claim is that comprehension syntax doesn't lend itself to that strategy -- you can accumulate a bunch of individual functions, such as the ability to generate Cartesian products, the ability to generate lazy streams, etc., but a small difference to the shape of a problem can dramatically hinder your ability to reuse those building blocks  ("Oh, this time the j is dependent on i in this particular way").  You end up either deep in a nest of higher-order functions requiring other higher-order functions (which is confusing for students), or you end up wanting to create a macro to abstract over these issues (which is outside the scope of what we teach students).  This is why I think there's a real place for a comprehension-based for.

My view is certainly influenced by the fact that my students stick with their learning language (e.g., Racket and hopefully at some point Pyret) for more years than the typical student (I gather most students encounter it for one semester and then move on to other languages).  So my students want to enter programming contests using their learning language, and want to have a set of constructs that let them go head to head with kids using other languages for a wide variety of problems.

 

We have some really neat new work coming up in a general bracket we're

calling "lightweight data science". That, for sure, is stretching us

in new dimensions. One of the things I really like about that work is

that it's giving us some means to side-step the whole "loop vs

recursion" debate (the right answer there is, you write somewhat

declarative commands that operate over tables…). This work came about

in part as a reaction to the "`for` is not good enough" mindset,

except it led us in a different way (a bit SQL-inspired).

Although I haven't used it myself, my understanding is that the C# Linq syntax is essentially a SQL-inspired comprehension syntax.  As far as I know, it doesn't have any expressive power beyond the comprehension syntax offered in other languages, but there's certainly nothing wrong with an SQL-flavored version.  I'm looking forward to see what you come up with, especially if it really does empower new capabilities, or a new way of thinking about the problem.

As some points for comparison:

Scala's for comprehension syntax generates a collection based on the type of the first collection you draw from in your comprehension.  So if you draw from a set, it produces a set.  If you draw from a list, it produces a list.  This is convenient in some cases, inconvenient in others.

Racket, as you surely know, has different flavors -- for/list, for*/list, for/set, for*/set.  You need constructs such as for*/first to grab the first such item.

Clojure's for always produces a lazy list, similar to what for*/stream would do in Racket.  Then you can "pour" this lazy list into the container (list, vector, set, etc.) you want using `into`.  In Clojure, `first` and `rest` operate on anything that participates in the sequence abstraction, not just lists, so they work on lazy lists too.  So finding the first item that satisfies a property can just be written as (first (for ...)) and because it's lazy, no additional computation is required beyond what is needed to find the first.

Your comment about "lightweight data science" reminds me of something else from the Clojure community.  In the Clojure community, one popular commercial database is Datomic, which uses a datalog query engine rather than SQL and presents the database as a sort of immutable data structure.  Someone in the community wrote an open-source, in-memory version of Datomic called Datascript (https://github.com/tonsky/datascript) and it has gained quite a following.  You construct it like a database, but it keeps all the data in simple in-memory tables so there's little performance overhead beyond coding up the tables directly, and then you use the Datalog syntax familiar from Datomic to query.  You might find it interesting to look at as an example of building a database layer on top of tables, and to think about the value of SQL vs Datalog for students.

While I'm on the subject, there's one other thing from the Clojure community you may find useful for inspiration.  In Racket's learning languages and to some extent in Pyret, one of the challenges with students comes with teaching them to update something deep inside a nested, immutable data structure (e.g., update the y field of all the posns of all the sprites in my spritelist in my world data structure).  There's a lot of mental overhead in drilling down and then building back up the data structure.  Nathan Marz introduced the concept of "navigators" through a library he built for Clojure called Specter (https://github.com/nathanmarz/specter), and it is extremely useful for this sort of situation.  So, in the example I gave above, you could specify the path [:spritelist ALL :posn :y], and this one path allows you to retrieve and/or update all the corresponding parts of the immutable data structure with a single instruction.  A good video about the library is https://www.youtube.com/watch?v=VTCy_DkAJGk.

 

So, we're not disregarding your suggestion. This is something Pyret

just does poorly. I believe there are many things it does really well,

and that set is growing quite a bit (our new table support will come

online in the next few weeks; already very much available in the

repo). Translating programs that are natural in other languages

doesn't showcase what Pyret does well, for sure.

I'm looking forward to seeing the new additions!

 

[Shriram Krishnamurthi]

Yes, precisely, to your first comment. I was going to post a much

longer message here about how the traditional

  v = read_input

  for ... over v: ... w = do something to v ...

  print w

is pretty much the antithesis of what we're trying to support, and

formulating this instead as

  f(v) = do something to v

  v0 = read_input

  w = f(v0)

  print w

has the virtue that the last three lines are already implemented for

you by the REPL, so you can focus on developing f, which includes

testing it, and so on. But the answers here had already covered a lot

of ground and I didn't want to make the thread even more complicated.

=====

As for your other remarks: yes, I agree with the principle. I'm still

not sold on comprehension syntax. I think the easy cases are truly

easy (at least to someone versed in set theory!), but once things

start to nest I run into examples where I am simply not sure which

interpretation to apply. [For instance, if I'm sampling {i; j} (using

Pyret's tuple syntax) from 1 to 100 for each of i and j, am I getting

100 tuples or 100 * 100 tuples?]

Having stamped operator precedence out of Pyret's infix syntax, I

don't know that I want to introduce that new kind of syntactic

ambiguity back into the language.

Perhaps infix offers a useful analogy. We tossed out precedence, but

not infix itself. The same way, perhaps we can have unamibiguous

precedence, and whenever we run into something that might have

multiple interpretations, resist. If that resulting language is

powerful enough to express sufficiently many useful cases, we would

have a net win. I'm worried we'll run into those cases sooner than we

hit a point of utility, though.

=====

Thanks for the Specter pointer. Defining these kinds of indices well

is a fascinating problem. I've long enjoyed Karl Lieberherr's work on

the Demeter project, which takes this up to 11, and for a while was

working with one of his students on porting this to FP (see

http://cs.brown.edu/~sk/Publications/Papers/Published/wlk-functional-demeter/

for a pretty crappy preliminary effort). So it's a topic that holds a

lot of fascination for me. Which is a bad thing, because we're not

allowing ourselves to do research. (-:

Shriram

[Ben Lerner]

It seems to me that "symmetry breaking and allowing the second argument to be contingent on the first" doesn't imply the need for comprehensions.  Here's a workable solution that requires a slightly different find function than the one currently in our lists library:

fun find-opt(f, lst):
  doc: "Returns the first answer that is non-none, if any, of running f over the given list"
  cases(List) lst:
    | empty => none
    | link(first, rest) =>
      ans = f(first)
      cases(Option) ans:
        | none => find-opt(f, rest)
        | some(_) => ans
      end
  end
end

fun find-pair(min, max):
  for find-opt(a from range(min, max)):
    for find-opt(b from range(a, max)):
      if ((1000 - a - b) > 0) and checktrip(a, b, (1000 - a - b)): some({a; b})
      else: none
      end
    end
  end
end

No explicit cartesian product, no overly-large ranges.  It's a different solution plan than "generate all pairs, and then winnow out the ones that don't work", certainly, but it's closer to the original wording of the problem, I think.  (Find-opt is slightly different than the usual find, since it doesn't necessarily return the item in the list that satisfied a predicate, but the regular find is a special case of this one.)

The main remaining weakness of this solution is it's still non-lazy: ranges have to be allocated completely in order to be iterated over.  There were some proposals for enhancing for-loop syntax that would address this particular issue, but I'm not sure how generalizable the solutions would be.

[Mark Engelberg]

On Sat, Jul 16, 2016 at 2:32 PM, Ben Lerner <ble...@cs.brown.edu> wrote:

No explicit cartesian product, no overly-large ranges.  It's a different solution plan than "generate all pairs, and then winnow out the ones that don't work", certainly, but it's closer to the original wording of the problem, I think.  (Find-opt is slightly different than the usual find, since it doesn't necessarily return the item in the list that satisfied a predicate, but the regular find is a special case of this one.)

Another issue is that if you do want to produce a list of all the tuples, instead of just the first one, and you use nested fors, then you have to explicitly flatten out the resulting list, which can be cumbersome if it gets more than a couple of levels deep.