Tag Archives: ACTA

Introspection

Post Syndicated from Eevee original https://eev.ee/blog/2017/05/28/introspection/

This month, IndustrialRobot has generously donated in order to ask:

How do you go about learning about yourself? Has your view of yourself changed recently? How did you handle it?

Whoof. That’s incredibly abstract and open-ended — there’s a lot I could say, but most of it is hard to turn into words.


The first example to come to mind — and the most conspicuous, at least from where I’m sitting — has been the transition from technical to creative since quitting my tech job. I think I touched on this a year ago, but it’s become all the more pronounced since then.

I quit in part because I wanted more time to work on my own projects. Two years ago, those projects included such things as: giving the Python ecosystem a better imaging library, designing an alternative to regular expressions, building a Very Correct IRC bot framework, and a few more things along similar lines. The goals were all to solve problems — not hugely important ones, but mildly inconvenient ones that I thought I could bring something novel to. Problem-solving for its own sake.

Now that I had all the time in the world to work on these things, I… didn’t. It turned out they were almost as much of a slog as my job had been!

The problem, I think, was that there was no point.

This was really weird to realize and come to terms with. I do like solving problems for its own sake; it’s interesting and educational. And most of the programming folks I know and surround myself with have that same drive and use it to create interesting tools like Twisted. So besides taking for granted that this was the kind of stuff I wanted to do, it seemed like the kind of stuff I should want to do.

But even if I create a really interesting tool, what do I have? I don’t have a thing; I have a tool that can be used to build things. If I want a thing, I have to either now build it myself — starting from nearly zero despite all the work on the tool, because it can only do so much in isolation — or convince a bunch of other people to use my tool to build things. Then they’d be depending on my tool, which means I have to maintain and support it, which is even more time and effort poured into this non-thing.

Despite frequently being drawn to think about solving abstract tooling problems, it seems I truly want to make things. This is probably why I have a lot of abandoned projects boldly described as “let’s solve X problem forever!” — I go to scratch the itch, I do just enough work that it doesn’t itch any more, and then I lose interest.

I spent a few months quietly flailing over this minor existential crisis. I’d spent years daydreaming about making tools; what did I have if not that drive? I was having to force myself to work on what I thought were my passion projects.

Meanwhile, I’d vaguely intended to do some game development, but for some reason dragged my feet forever and then took my sweet time dipping my toes in the water. I did work on a text adventure, Runed Awakening, on and off… but it was a fractal of creative decisions and I had a hard time making all of them. It might’ve been too ambitious, despite feeling small, and that might’ve discouraged me from pursuing other kinds of games earlier.

A big part of it might have been the same reason I took so long to even give art a serious try. I thought of myself as a technical person, and art is a thing for creative people, so I’m simply disqualified, right? Maybe the same thing applies to games.

Lord knows I had enough trouble when I tried. I’d orbited the Doom community for years but never released a single finished level. I did finally give it a shot again, now that I had the time. Six months into my funemployment, I wrote a three-part guide on making Doom levels. Three months after that, I finally released one of my own.

I suppose that opened the floodgates; a couple weeks later, glip and I decided to try making something for the PICO-8, and then we did that (almost exactly a year ago!). Then kept doing it.

It’s been incredibly rewarding — far moreso than any “pure” tooling problem I’ve ever approached. Moreso than even something like veekun, which is a useful thing. People have thoughts and opinions on games. Games give people feelings, which they then tell you about. Most of the commentary on a reference website is that something is missing or incorrect.

I like doing creative work. There was never a singular moment when this dawned on me; it was a slow process over the course of a year or more. I probably should’ve had an inkling when I started drawing, half a year before I quit; even my early (and very rough) daily comics made people laugh, and I liked that a lot. Even the most well-crafted software doesn’t tend to bring joy to people, but amateur art can.

I still like doing technical work, but I prefer when it’s a means to a creative end. And, just as important, I prefer when it has a clear and constrained scope. “Make a library/tool for X” is a nebulous problem that could go in a great many directions; “make a bot that tweets Perlin noise” has a pretty definitive finish line. It was interesting to write a little physics engine, but I would’ve hated doing it if it weren’t for a game I were making and didn’t have the clear scope of “do what I need for this game”.


It feels like creative work is something I’ve been wanting to do for a long time. If this were a made-for-TV movie, I would’ve discovered this impulse one day and immediately revealed myself as a natural-born artistic genius of immense unrealized talent.

That didn’t happen. Instead I’ve found that even something as mundane as having ideas is a skill, and while it’s one I enjoy, I’ve barely ever exercised it at all. I have plenty of ideas with technical work, but I run into brick walls all the time with creative stuff.

How do I theme this area? Well, I don’t know. How do I think of something? I don’t know that either. It’s a strange paradox to have an urge to create things but not quite know what those things are.

It’s such a new and completely different kind of problem. There’s no right answer, or even an answer I can check for “correctness”. I can do anything. With no landmarks to start from, it’s easy to feel completely lost and just draw blanks.

I’ve essentially recalibrated the texture of stuff I work on, and I have to find some completely new ways to approach problems. I haven’t found them yet. I don’t think they’re anything that can be told or taught. But I’m starting to get there, and part of it is just accepting that I can’t treat these like problems with clear best solutions and clear algorithms to find those solutions.

A particularly glaring irony is that I’ve had a really tough problem designing abstract spaces, even though that’s exactly the kind of architecture I praise in Doom. It’s much trickier than it looks — a good abstract design is reminiscent of something without quite being that something.

I suppose it’s similar to a struggle I’ve had with art. I’m drawn to a cartoony style, and cartooning is also a mild form of abstraction, of whittling away details to leave only what’s most important. I’m reminded in particular of the forest background in fox flux — I was completely lost on how to make something reminiscent of a tree line. I knew enough to know that drawing trees would’ve made the background far too busy, but trees are naturally busy, so how do you represent that?

The answer glip gave me was to make big chunky leaf shapes around the edges and where light levels change. Merely overlapping those shapes implies depth well enough to convey the overall shape of the tree. The result works very well and looks very simple — yet it took a lot of effort just to get to the idea.

It reminds me of mathematical research, in a way? You know the general outcome you want, and you know the tools at your disposal, and it’s up to you to make some creative leaps. I don’t think there’s a way to directly learn how to approach that kind of problem; all you can do is look at what others have done and let it fuel your imagination.


I think I’m getting a little distracted here, but this is stuff that’s been rattling around lately.

If there’s a more personal meaning to the tree story, it’s that this is a thing I can do. I can learn it, and it makes sense to me, despite being a huge nerd.

Two and a half years ago, I never would’ve thought I’d ever make an entire game from scratch and do all the art for it. It was completely unfathomable. Maybe we can do a lot of things we don’t expect we’re capable of, if only we give them a serious shot.

And ask for help, of course. I have a hell of a time doing that. I did a painting recently that factored in mountains of glip’s advice, and on some level I feel like I didn’t quite do it myself, even though every stroke was made by my hand. Hell, I don’t even look at references nearly as much as I should. It feels like cheating, somehow? I know that’s ridiculous, but my natural impulse is to put my head down and figure it out myself. Maybe I’ve been doing that for too long with programming. Trust me, it doesn’t work quite so well in a brand new field.


I’m getting distracted again!

To answer your actual questions: how do I go about learning about myself? I don’t! It happens completely by accident. I’ll consciously examine my surface-level thoughts or behaviors or whatever, sure, but the serious fundamental revelations have all caught me completely by surprise — sometimes slowly, sometimes suddenly.

Most of them also came from listening to the people who observe me from the outside: I only started drawing in the first place because of some ridiculous deal I made with glip. At the time I thought they just wanted everyone to draw because art is their thing, but now I’m starting to suspect they’d caught on after eight years of watching me lament that I couldn’t draw.

I don’t know how I handle such discoveries, either. What is handling? I imagine someone discovering something and trying to come to grips with it, but I don’t know that I have quite that experience — my grappling usually comes earlier, when I’m still trying to figure the thing out despite not knowing that there’s a thing to find out. Once I know it, it’s on the table; I can’t un-know it or reject it meaningfully. All I can do is figure out what to do with it, and I approach that the same way I approach every other problem: by flailing at it and hoping for the best.

This isn’t quite 2000 words. Sorry. I’ve run out of things to say about me. This paragraph is very conspicuous filler. Banana. Atmosphere. Vocation.

Julia language for Raspberry Pi

Post Syndicated from Ben Nuttall original https://www.raspberrypi.org/blog/julia-language-raspberry-pi/

Julia is a free and open-source general purpose programming language made specifically for scientific computing. It combines the ease of writing in high-level languages like Python and Ruby with the technical power of MATLAB and Mathematica and the speed of C. Julia is ideal for university-level scientific programming and it’s used in research.

Julia language logo

Some time ago Viral Shah, one of the language’s co-creators, got in touch with us at the Raspberry Pi Foundation to say his team was working on a port of Julia to the ARM platform, specifically for the Raspberry Pi. Since then, they’ve done sterling work to add support for ARM. We’re happy to announce that we’ve now added Julia to the Raspbian repository, and that all Raspberry Pi models are supported!

Not only did the Julia team port the language itself to the Pi, but they also added support for GPIO, the Sense HAT and Minecraft. What I find really interesting is that when they came to visit and show us a demo, they took a completely different approach to the Sense HAT than I’d seen before: Simon, one of the Julia developers, started by loading the Julia logo into a matrix within the Jupyter notebook and then displayed it on the Sense HAT LED matrix. He then did some matrix transformations and the Sense HAT showed the effect of these manipulations.

Viral says:

The combination of Julia’s performance and Pi’s hardware unlocks new possibilities. Julia on the Pi will attract new communities and drive applications in universities, research labs and compute modules. Instead of shipping the data elsewhere for advanced analytics, it can simply be processed on the Pi itself in Julia.

Our port to ARM took a while, since we started at a time when LLVM on ARM was not fully mature. We had a bunch of people contributing to it – chipping away for a long time. Yichao did a bunch of the hard work, since he was using it for his experiments. The folks at the Berkeley Race car project also put Julia and JUMP on their self-driving cars, giving a pretty compelling application. We think we will see many more applications.

I organised an Intro to Julia session for the Cambridge Python user group earlier this week, and rather than everyone having to install Julia, Jupyter and all the additional modules on their own laptops, we just set up a room full of Raspberry Pis and prepared an SD card image. This was much easier and also meant we could use the Sense HAT to display output.

Intro to Julia language session at Raspberry Pi Foundation
Getting started with Julia language on Raspbian
Julia language logo on the Sense HAT LED array

Simon kindly led the session, and before long we were using Julia to generate the Mandelbrot fractal and display it on the Sense HAT:

Ben Nuttall on Twitter

@richwareham’s Sense HAT Mandelbrot fractal with @JuliaLanguage at @campython https://t.co/8FK7Vrpwwf

Naturally, one of the attendees, Rich Wareham, progressed to the Julia set – find his code here: gist.github.com/bennuttall/…

Last year at JuliaCon, there were two talks about Julia on the Pi. You can watch them on YouTube:

Install Julia on your Raspberry Pi with:

sudo apt update
sudo apt install julia

You can install the Jupyter notebook for Julia with:

sudo apt install julia libzmq3-dev python3-zmq
sudo pip3 install jupyter
julia -e 'Pkg.add("IJulia");'

And you can easily install extra packages from the Julia console:

Pkg.add("SenseHat")

The Julia team have also created a resources website for getting started with Julia on the Pi: juliaberry.github.io

Julia team visiting Pi Towers

There never was a story of more joy / Than this of Julia and her Raspberry Pi

Many thanks to Viral Shah, Yichao Yu, Tim Besard, Valentin Churavy, Jameson Nash, Tony Kelman, Avik Sengupta and Simon Byrne for their work on the port. We’re all really excited to see what people do with Julia on Raspberry Pi, and we look forward to welcoming Julia programmers to the Raspberry Pi community.

The post Julia language for Raspberry Pi appeared first on Raspberry Pi.

Research into the Root Causes of Terrorism

Post Syndicated from Bruce Schneier original https://www.schneier.com/blog/archives/2017/02/research_into_t_1.html

Interesting article in Science discussing field research on how people are radicalized to become terrorists.

The potential for research that can overcome existing constraints can be seen in recent advances in understanding violent extremism and, partly, in interdiction and prevention. Most notable is waning interest in simplistic root-cause explanations of why individuals become violent extremists (e.g., poverty, lack of education, marginalization, foreign occupation, and religious fervor), which cannot accommodate the richness and diversity of situations that breed terrorism or support meaningful interventions. A more tractable line of inquiry is how people actually become involved in terror networks (e.g., how they radicalize and are recruited, move to action, or come to abandon cause and comrades).

Reports from the The Soufan Group, International Center for the Study of Radicalisation (King’s College London), and the Combating Terrorism Center (U.S. Military Academy) indicate that approximately three-fourths of those who join the Islamic State or al-Qaeda do so in groups. These groups often involve preexisting social networks and typically cluster in particular towns and neighborhoods.. This suggests that much recruitment does not need direct personal appeals by organization agents or individual exposure to social media (which would entail a more dispersed recruitment pattern). Fieldwork is needed to identify the specific conditions under which these processes play out. Natural growth models of terrorist networks then might be based on an epidemiology of radical ideas in host social networks rather than built in the abstract then fitted to data and would allow for a public health, rather than strictly criminal, approach to violent extremism.

Such considerations have implications for countering terrorist recruitment. The present USG focus is on “counternarratives,” intended as alternative to the “ideologies” held to motivate terrorists. This strategy treats ideas as disembodied from the human conditions in which they are embedded and given life as animators of social groups. In their stead, research and policy might better focus on personalized “counterengagement,” addressing and harnessing the fellowship, passion, and purpose of people within specific social contexts, as ISIS and al-Qaeda often do. This focus stands in sharp contrast to reliance on negative mass messaging and sting operations to dissuade young people in doubt through entrapment and punishment (the most common practice used in U.S. law enforcement) rather than through positive persuasion and channeling into productive life paths. At the very least, we need field research in communities that is capable of capturing evidence to reveal which strategies are working, failing, or backfiring.

CES 2017: Trends For the Tech Savvy To Watch

Post Syndicated from Peter Cohen original https://www.backblaze.com/blog/ces-2017-trends-tech-savvy-watch/

This year’s Consumer Electronics Show (CES) just wrapped up in Las Vegas. The usual parade of cool tech toys created a lot of headlines this year, but there were some genuine trends to keep an eye on too. If you’re like us, you’re probably one of the first people around to adopt promising new technologies when they emerge. As early adopters we can sometimes lose the forest through the trees when it comes to understanding what this means for everyone else, so we’re going to look at it through that prism.

Alexa everywhere

2017 promises to be a big year for voice-activated “smart home” devices. The final landscape for this is still to be determined – all the expected players have their foot in it right now. Amazon, Apple, Google, Microsoft, even some smaller players.

Amazon deserves props after a holiday season that saw its Echo and Echo Dot devices in high demand. The company’s published an API that is Alexa is picking up plenty of support from third party manufacturers. Alexa’s testing for far beyond Echo, it seems.

Electronics giant LG is building Alexa into a line of robots designed for domestic duties and a refrigerator that also sports interior fridge cams, for example. Ford is integrating Alexa support into its Sync 3 automotive interface. Televisions, lighting devices, and home security products are among the many devices to feature Alexa integration.

Alexa is the new hotness, but the real trend here is in voice-assisted connectivity around the home. Even if Alexa runs out of steam, this tech is here to stay. The Internet of Things and voice activated interfaces are converging quickly, though that day isn’t today. It’s tantalizingly close. It’s still a niche, though, where it will stay for as long as consumers have to piece different things together to get it to work. That means there’s still room for disruption.

There’s especially ripe opportunity in underserved verticals. Take the home health market, for example: Natural language interfaces have huge implications for elderly and disabled care and assistance. Finding and developing solutions for those sorts of vertical markets is an awesome opportunity for the right players.

Of course, with great power comes great responsibility. A family of a six-year-old recently got stuck with a $160 bill after she told Alexa to order her cookies and a dollhouse. The family ended up donating the accidental order to charity. For what it’s worth, that problem can be avoided by activating a confirmation code feature in the Alexa software.

The Electric Vehicle (EV) Market Heats Up

One of the trickiest things to unpack from CES is hype from substance. Nowhere was that more apparent last week than the unveiling of Faraday Future’s FF91, a new Electric Vehicle (EV) positioned to go toe-to-toe with Tesla’s EV fleet.

The FF91 EV can purportedly go 378 miles on a single charge and also possesses autonomous driving capabilities (although its vaunted self-parking abilities didn’t demo as well as planned). When or if it’ll make it into production is still a head-scratcher, however. Faraday Future says it’ll be out next year, assuming that the company is beyond the production and manufacturing woes that have plagued it up until now.

While new vehicles and vehicle concepts are still largely the domain of auto shows, some auto manufacturers used CES to float new concepts ahead of the Detroit Auto Show, which happens this week. Toyota, for example, showed off its Concept-i, a car with artificial intelligence and natural language processing (like Siri or Alexa) designed to learn from you and adapt.

As we mentioned, Alexa is integrated into Ford’s Sync 3 platform, too. Already you can buy new cars with CarPlay and Android Auto, which makes it a lot easier to just talk with your mobile device to stay connected, get directions and entertain yourself on the morning commute simply by talking to your car instead of touching buttons. That’s a smart user interface change, but it’s still a potentially dangerous distraction for the driver. For this technology to succeed, it’s imperative that natural language interface designers make the experience as frictionless as possible.

Chrysler is making a play for future millennial families. We’re not making this up – they used “millennial” to describe the target market for this several times. The Portal concept is an electric minivan of sorts that’s chock-full of buzzwords: Facial recognition, Wi-Fi, media sharing, ten charging ports, semi-autonomous driving abilities and more).

2017 marks a pivot for car makers in this respect. For years the conventional wisdom that millennials were a lost cause for auto makers – Uber and Zipcar was all they needed. It turns out that was totally wrong. Economic pressures and diverse lifestyles may have delayed millennials’ trek toward auto ownership, but they’re turning out now in big numbers to buy wheels. Millennial families will need transportation just like generations before them back to the station wagon, which is why Chrysler says this “fifth-generation” family car will go into production sometime after 2018.

Volkswagen showed off its new I.D. concept car, a Golf-looking EV that also has all the requisite buzzwords. Speaking of buzzwords, what really excited us was the I.D. Buzz. This new EV resurrects the styling of the Hippy-era Microbus, with mood lighting, autonomous driving capabilities and a retractable steering wheel.

Rumors have persisted for years that VW was on the cusp of introducing a refreshed Microbus, but those rumors have never come to pass. And unfortunately, VW has no concrete plans to actually produce this – it seems to be a marketing effort to draw on nostalgic Boomer appeal, more than anything..

Both Buzz and Chrysler’s Portal do give us some insight about where auto makers are going when it comes to future generations of minivans: Electric, autonomous, customizable and more social than ever. If we are headed towards a future where vehicles drive themselves, family transportation will look very different than it is today.

Laptops At Both Extremes

CES saw the rollout of several new PC laptop models and concepts that will be hitting store shelves over the next several months.

Gamers looking for more real estate – a lot more real estate – were interested in Razer’s latest concept, Project Valerie. The laptop sports not one but three 4K displays which fold out on hinges. That’s 12K pixels of horizontal image space, mated to an Nvidia GeForce GTX 1080 graphics processor. A unibody aluminum chassis keeps it relatively thin (1.5 inches) when closed, but the entire rig weighs more than 12 pounds. Razer doesn’t have any immediate production plans, which may explain why their prototype was stolen before the end of the show.

Unlike Razer, Acer has production plans – immediate plans – for its gargantuan 21-inch Predator 21X laptop, priced at $8,999 and headed to store shelves next month. It was announced last year, but Acer finally offered launch details last week. A 17-inch model is also coming soon.

Big gaming laptops make for pretty pictures and certainly have their place in the PC ecosystem, but they’re niche devices. After a ramp up on 2-in-1s and low-powered laptops, Intel’s Kaby Lake processors are finally ready for the premium and mid-range laptop market. Kaby Lake efficiency improvements are helping PC makers build thinner and lighter laptops with better battery life, 4K video processing, faster solid state storage and more.

HP, Asus, MSI, Dell (and its gaming arm Alienware) were among the many companies with sleek new Kaby Lake-equipped models.

Gaming in the cloud with Nvidia

Nvidia, makers of premium graphics processors, offers GeForce Now cloud gaming to users of its Shield, an Android-based gaming handheld. That service is expanding to Windows and Mac in March.

Gaming as a Service, if you will, isn’t a new idea. OnLive pioneered the concept more than a decade ago. Gaikai followed, then was acquired by Sony in 2012. Nvidia’s had limited success with GeForce Now, but it’s been a single-platform offering up until now.

Nvidia has robust data centers to handle the processing and traffic, so best of luck to them as they scale up to meet demand. Gaming is very sensitive to network disruption – no gamer appreciates lag – so it’ll be interesting to see how GeForce Now scales to accommodate the new devices.

Mesh Networking

Mesh networking delivers more consistent, stronger network reception and performance than a conventional Wi-Fi router. Some of us have set up routers and extenders to fix dead spots – mesh networking works differently through smart traffic and better radio management between multiple network bases.

Eero, Ubiquiti, and even Google (with Google Wifi) are already offering mesh networking products, and this market segment looks to expand big in 2017. Netgear, Linksys, Asus, TP-Link and others are among those with new mesh networking setups. Mesh networking gear is still hampered by a higher price than plain old routers. That means the value isn’t there for some of us who have networking gear that gets the job done, even with shortcomings like dead zones or slow zones. But prices are coming down fast as more companies get into the market. If you have an 802.11ac router you’re happy with, stick with it for now, and move to a mesh networking setup for your next Wi-Fi upgrade.

Getting Your Feet Into VR

Our award for wackiest CES product has to go to Cerevo Taclim. Tactile feedback shoes and wireless hand controllers that help you “feel” the surface you’re walking on. Crunching snow underfoot, splashing through water. At an expected $1,000-$1,500 a pop, these probably won’t be next year’s Hatchimals, but it’s fun to imagine what game devs can do with the technology. Strap these to your feet then break out your best Hadouken in Street Fighter VR!

CES isn’t the real world. Only a fraction of what’s shown off ever sees the light of day, but it’s always interesting to see the trend-focused consumer electronics market shift and change from year to year. At the end of the year we hope to look back and see how much of this stuff ended up resonating with the actual consumer the show is named for.

The post CES 2017: Trends For the Tech Savvy To Watch appeared first on Backblaze Blog | Cloud Storage & Cloud Backup.

Iteration in one language, then all the others

Post Syndicated from Eevee original https://eev.ee/blog/2016/11/18/iteration-in-one-language-then-all-the-others/

You may have noticed that I like comparing features across different languages. I hope you like it too, because I’m doing it again.

Python

I’m most familiar with Python, and iteration is one of its major concepts, so it’s a good place to start and a good overview of iteration. I’ll dive into Python a little more deeply, then draw parallels to other languages.

Python only has one form of iteration loop, for. (Note that all of these examples are written for Python 3; in Python 2, some of the names are slightly different, and fewer things are lazy.)

1
2
for value in sequence:
    ...

in is also an operator, so value in sequence is also the way you test for containment. This is either very confusing or very satisfying.

When you need indices, or specifically a range of numbers, you can use the built-in enumerate or range functions. enumerate works with lazy iterables as well.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
# This makes use of tuple unpacking to effectively return two values at a time
for index, value in enumerate(sequence):
    ...

# Note that the endpoint is exclusive, and the default start point is 0.  This
# matches how list indexing works and fits the C style of numbering.
# 0 1 2 3 4
for n in range(5):
    ...

# Start somewhere other than zero, and the endpoint is still exclusive.
# 1 2 3 4
for n in range(1, 5):
    ...

# Count by 2 instead.  Can also use a negative step to count backwards.
# 1 3 5 7 9
for n in range(1, 11, 2):
    ...

dicts (mapping types) have several methods for different kinds of iteration. Additionally, iterating over a dict directly produces its keys.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
for key in mapping:
    ...

for key in mapping.keys():
    ...

for value in mapping.values():
    ...

for key, value in mapping.items():
    ...

Python distinguishes between an iterable, any value that can be iterated over, and an iterator, a value that performs the actual work of iteration. Common iterable types include list, tuple, dict, str, and set. enumerate and range are also iterable.

Since Python code rarely works with iterators directly, and many iterable types also function as their own iterators, it’s common to hear “iterator” used to mean an iterable. To avoid this ambiguity, and because the words are fairly similar already, I’ll refer to iterables as containers like the Python documentation sometimes does. Don’t be fooled — an object doesn’t actually need to contain anything to be iterable. Python’s range type is iterable, but it doesn’t physically contain all the numbers in the range; it generates them on the fly as needed.

The fundamental basics of iteration are built on these two ideas. Given a container, ask for an iterator; then repeatedly advance the iterator to get new values. When the iterator runs out of values, it raises StopIteration. That’s it. In Python, those two steps can be performed manually with the iter and next functions. A for loop is roughly equivalent to:

1
2
3
4
5
6
7
8
9
_iterator = iter(container)
_done = False
while not _done:
    try:
        value = next(_iterator)
    except StopIteration:
        _done = True
    else:
        ...

An iterator can only move forwards. Once a value has been produced, it’s lost, at least as far as the iterator is concerned. These restrictions are occasionally limiting, but they allow iteration to be used for some unexpected tasks. For example, iterating over an open file produces its lines — even if the “file” is actually a terminal or pipe, where data only arrives once and isn’t persistently stored anywhere.

Generators

A more common form of “only forwards, only once” in Python is the generator, a function containing a yield statement. For example:

1
2
3
4
5
6
7
8
9
def inclusive_range(start, stop):
    val = start
    while val <= stop:
        yield val
        val += 1

# 6 7 8 9
for n in inclusive_range(6, 9):
    ...

Calling a generator function doesn’t execute its code, but immediately creates a generator iterator. Every time the iterator is advanced, the function executes until the next yield, at which point the yielded value is returned as the next value and the function pauses. The next iteration will then resume the function. When the function returns (or falls off the end), the iterator stops.

Since the values here are produced by running code on the fly, it’s of course impossible to rewind a generator.

The underlying protocol is straightforward. A container must have an __iter__ method that returns an iterator, corresponding to the iter function. An iterator must have a __next__ method that returns the next item, corresponding to the next function. If the iterator is exhausted, __next__ must raise StopIteration. An iterator must also have an __iter__ that returns itself — this is so an iterator can be used directly in a for loop.

The above inclusive range generator might be written out explicitly like this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class InclusiveRange:
    def __init__(self, start, stop):
        self.start = start
        self.stop = stop

    def __iter__(self):
        return InclusiveRangeIterator(self)

class InclusiveRangeIterator:
    def __init__(self, incrange):
        self.incrange = incrange
        self.nextval = incrange.start

    def __iter__(self):
        return self

    def __next__(self):
        if self.nextval > self.incrange.stop:
            raise StopIteration

        val = self.nextval
        self.nextval += 1
        return val

This might seem like a lot of boilerplate, but note that the iterator state (here, nextval) can’t go on InclusiveRange directly, because then it’d be impossible to iterate over the same object twice at the same time. (Some types, like files, do act as their own iterators because they can’t meaningfully be iterated in parallel.)

Even Python’s internals work this way. Try iter([]) in a Python REPL; you’ll get a list_iterator object.

In truth, it is a lot of boilerplate. User code usually uses this trick:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class InclusiveRange:
    def __init__(self, start, stop):
        self.start = start
        self.stop = stop

    def __iter__(self):
        val = self.start
        while val <= self.stop:
            yield val
            val += 1

Nothing about this is special-cased in any way. Now __iter__ is a generator, and calling a generator function returns an iterator, so all the constraints are met. It’s a really easy way to convert a generator function into a type. If this class were named inclusive_range instead, it would even be backwards-compatible; consuming code wouldn’t even have to know it’s a class.

Reversal

But why would you do this? One excellent reason is to add support for other sequence-like operations, like reverse iteration support. An iterator can’t be reversed, but a container might support being iterated in reverse:

1
2
3
4
fruits = ['apple', 'orange', 'pear']
# pear, orange, apple
for value in reversed(fruits):
    ...

Iterating a lazy container doesn’t always make sense, but when it does, it’s easy to implement by returning an iterator from __reversed__.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class InclusiveRange:
    def __init__(self, start, stop):
        self.start = start
        self.stop = stop

    def __iter__(self):
        val = self.start
        while val <= self.stop:
            yield val
            val += 1

    def __reversed__(self):
        val = self.stop
        while val >= self.start:
            yield val
            val -= 1

Note that Python does not have “bi-directional” iterators, which can freely switch between forwards and reverse iteration on the fly. A bidirectional iterator is useful for cases like doubly-linked lists, where it’s easy to get from one value to the next or previous value, but not as easy to start from the beginning and get the tenth item.

Iteration is often associated with sequences, though they’re not quite the same. In Python, a sequence is a value that can be indexed in order as container[0], container[1], etc. (Indexing is implemented with __getitem__.) All sequences are iterable; in fact, if a type implements indexing but not __iter__, the iter function will automatically try indexing it from zero instead. reversed does the same, though it requires that the type implement __len__ as well so it knows what the last item is.

Much of this is codified more explicitly in the abstract base classes in collections.abc, which also provide default implementations of common methods.

Not all iterables are sequences, and not every value that can be indexed is a sequence! Python’s mapping type, dict, uses indexing to fetch the value for a key; but a dict has no defined order and is not a sequence. However, a dict can still be iterated over, producing its keys (in arbitrary order). A set can be iterated over, producing its values in arbitrary order, but it cannot be indexed at all. A type could conceivably use indexing for something more unusual and not be iterable at all.

A common question

It’s not really related to iteration, but people coming to Python from Ruby often ask why len() is a built-in function, rather than a method. The same question could be asked about iter() and next() (and other Python builtins), which more or less delegate directly to a “reserved” __dunder__ method anyway.

I believe the technical reason is simply the order that features were added to the language in very early days, which is not very interesting.

The philosophical reason, imo, is that Python does not reserve method names for fundamental operations. All __dunder__ names are reserved, of course, but everything else is fair game. This makes it obvious when a method is intended to add support for some language-ish-level operation, even if you don’t know what all the method names are. Occasionally a third-party library invents its own __dunder__ name, which is a little naughty, but the same reasoning applies: “this is a completely generic interface that some external mechanism is expected to use”.

This approach also avoids a namespacing problem. In Ruby, a Rectangle class might want to have width and length attributes… but the presence of length means a Rectangle looks like it functions as a sequence! Since “interface” method names aren’t namespaced in any way, there is no way to say that you don’t mean the same thing as Array.length.

It’s a minor quibble, since everything’s dynamically typed anyway, so the real solution is “well don’t try to iterate a rectangle then”. And Python does use keys as a method name in some obscure cases. Oh, well.

Some cute tricks

The distinction between sequences and iterables can cause some subtle problems. A lot of code that only needs to loop over items can be passed, e.g., a generator. But this can take some conscious care. Compare:

1
2
3
4
5
6
7
8
# This will NOT work with generators, which don't support len() or indexing
for i in range(len(container)):
    value = container[i]
    ...

# But this will
for i, value in enumerate(container):
    ...

enumerate also has a subtle, unfortunate problem: it cannot be combined with reversed. This has bit me more than once, surprisingly.

1
2
3
4
5
6
7
# This produces a TypeError from reversed()
for i, value in reversed(enumerate(container)):
    ...

# This almost works, but the index goes forwards while the values go backwards
for i, value in enumerate(reversed(container)):
    ...

The problem is that enumerate can’t, in general, reverse itself. It counts up from zero as it iterates over its argument; reversing it means starting from one less than the number of items, but it doesn’t yet know how many items there are. But if you just want to run over a list or other sequence backwards, this feels very silly. A trivial helper can make it work:

1
2
3
4
5
def revenum(iterable, end=0):
    start = len(iterable) + end
    for value in iterable:
        start -= 1
        yield start, value

I’ve run into other odd cases where it’s frustrating that a generator doesn’t have a length or indexing. This especially comes up if you make heavy use of generator expressions, which are a very compact way to write a one-off generator. (Python also has list, set, and dict “comprehensions”, which have the same syntax but use brackets or braces instead of parentheses, and are evaluated immediately instead of lazily.)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def get_big_fruits():
    fruits = ['apple', 'orange', 'pear']
    return (fruit.upper() for fruit in fruits)

# Roughly equivalent to:
def get_big_fruits():
    fruits = ['apple', 'orange', 'pear']
    def genexp():
        for fruit in fruits:
            yield fruit.upper()
    return genexp()

If you had thousands of fruits, doing this could save a little memory. The caller is probably just going to loop over them to print them out (or whatever), so using a generator expression means that each uppercase name only exists for a short time; returning a list would mean creating a lot of values all at once.

Ah, but now the caller wants to know how many fruits there are, with minimal fuss. Generators have no length, so that won’t work. Turning this generator expression into a class that also has a __len__ would be fairly ridiculous. So you resort to some slightly ugly trickery.

1
2
3
4
5
6
7
8
# Ugh.  Obvious, but feels really silly.
count = 0
for value in container:
    count += 1

# Better, but weird if you haven't seen it before.  Creates another generator
# expression that just yields 1 for every item, then sums them up.
count = sum(1 for _ in container)

Or perhaps you want the first big fruit? Well, [0] isn’t going to help. This is one of the few cases where using iter and next directly can be handy.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# Oops!  If the container is empty, this raises StopIteration, which you
# probably don't want.
first = next(iter(container))

# Catch the StopIteration explicitly.
try:
    first = next(iter(container))
except StopIteration:
    # This code runs if there are zero items
    ...

# Regular loop that terminates immediately.
# The "else" clause only runs when the container ends naturally (i.e. NOT if
# the loop breaks), which can only happen here if there are zero items.
for value in container:
    first = value
    break
else:
    ...

# next() -- but not __next__()! -- takes a second argument indicating a
# "default" value to return when the iterator is exhausted.  This only makes
# sense if you were going to substitute a default value anyway; doing this and
# then checking for None will do the wrong thing if the container actually
# contained a None.
first = next(iter(container), None)

Other tricks with iter and next include skipping the first item (or any number of initial items, though consider itertools.islice for more complex cases):

1
2
3
4
5
6
7
it = iter(container)
next(it, None)  # Use second arg to ignore StopIteration
for value in it:
    # Since the first item in the iterator has already been consumed, this loop
    # will start with the second item.  If the container had only one or zero
    # items, the loop will get StopIteration and end immediately.
    ...

Iterating two (or more) items at a time:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# Obvious way: call next() inside the loop.
it = iter(container)
for value1 in it:
    # With an odd number of items, this will raise an uncaught StopIteration!
    # Catch it or provide a default value.
    value2 = next(it)
    ...

# Moderately clever way: abuse zip().
# zip() takes some number of containers and iterates over them pairwise.  It
# stores an iterator for each container.  When it's asked for its next item, it
# in turn asks all of its iterators for their next items, and returns them as a
# set.  But by giving it the same exact iterator twice, it'll end up advancing
# that iterator twice and returning two consecutive items.
# Note that zip() stops early as soon as an iterator runs dry, so if the
# container has an odd number of items, this will silently skip the last one.
# If you don't want that, use itertools.zip_longest instead.
it = iter(container)
for line1, line2 in zip(it, it):
    ...

# Far too clever way: exactly the same as above, but written as a one-liner.
# zip(iter(), iter()) would create two separate iterators and break the trick.
# List multiplication produces a list containing the same iterator twice.
# One advantage of this is that the 2 can be a variable.
for value1, value2 in zip(*[iter(container)] * 2):
    ...

Wow, that got pretty weird towards the end. Somehow this turned into Stupid Python Iterator Tricks. Don’t worry; I know far less about these other languages.

C

C is an extreme example with no iterator protocol whatsoever. It barely even supports sequences; arrays are just pointer math. All it has is the humble C-style for loop:

1
2
3
4
5
int[] container = {...};
for (int i = 0; i < container_length; i++) {
    int value = container[i];
    ...
}

Unfortunately, it’s really the best C can do. C arrays don’t know their own length, so no matter what, the developer has to provide it some other way. Even without that, a built-in iterator protocol is impossible — iterators require persistent state (the current position) to be bundled alongside code (how to get to the next position). That pretty much means one of two things: closures or objects. C has neither.

Lua

Lua has two forms of for loop. The first is a simple numeric loop.

1
2
3
4
-- 1 3 5 7 9 11
for value = 1, 11, 2 do
    ...
end

The three values after the = are the start, end, and step. They work similarly to Python’s range(), except that everything in Lua is always inclusive, so for i = 1, 5 will count from 1 to 5.

The generic form uses in.

1
2
3
for value in iterate(container) do
    ...
end

iterate isn’t a special name here, but most of the time a generic for will look like this.

See, Lua doesn’t have objects. It has enough tools that you can build objects fairly easily, but the core language has no explicit concept of objects or method calls. An iterator protocol needs to bundle state and behavior somehow, so Lua uses closures for that. But you still need a way to get that closure, and that means calling a function, and a plain value can’t have functions attached to it. So iterating over a table (Lua’s single data structure) looks like this:

1
2
for key, value in pairs(container) do
    ...

pairs is a built-in function. Lua also has an ipairs, which iterates over consecutive keys and values starting from key 1. (Lua starts at 1, not 0. Lua also represents sequences as tables with numeric keys.)

Lua does have a way to associate “methods” with values, which is how objects are made, but for loops almost certainly came first. So iteration is almost always over a function call, not a bare value.

Also, because objects are built out of tables, having a default iteration behavior for all tables would mean having the same default for all objects. Nothing’s stopping you from using pairs on an object now, but at least that looks deliberate. It’s easy enough to give objects iteration methods and iterate over obj:iter(), though it’s slightly unfortunate that every type might look slightly different. Unfortunately, Lua has no truly generic interface for “this can produce a sequence of values”.

The iteration protocol is really just calling a function repeatedly to get new values. When the function returns nil, the iteration ends. (That means nil can never be part of an iteration! You can work around this by returning two values and making sure the first one is something else that’s never nil, like an index.) The manual explains the exact semantics of the generic for with Lua code, a move I wish every language would make.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
-- This:
for var_1, ···, var_n in explist do block end

-- Is equivalent to this:
do
    local _func, _state, _lastval = explist
    while true do
        local var_1, ···, var_n = _func(_state, _lastval)
        if var_1 == nil then break end
        _lastval = var_1
        block
    end
end

Important to note here is the way multiple-return works in Lua. Lua doesn’t have tuples; multiple assignment is a distinct feature of the language, and multiple return works exactly the same way as multiple assignment. If there are too few values, the extra variables become nil; if there are too many values, the extras are silently discarded.

So in the line local _func, _state, _lastval = explist, the “state” value _state and the “last loop value” _lastval are both optional. Lua doesn’t use them, except to pass them back to the iterator function _func, and they aren’t visible to the for loop body. An iterator can thus be only a function and nothing else, letting _state and _lastval be nil — but they can be a little more convenient at times. Compare:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
-- Usual approach: return only a closure, completely ignoring state and lastval
local function inclusive_range(start, stop)
    local nextval = start
    return function()
        if nextval > stop then
            return
        end
        local val = nextval
        nextval = nextval + 1
        return val
    end
end

-- Alternative approach, not using closures at all.  This is the function we
-- return; each time it's called with the same "state" value and whatever it
-- returned last time it was called.
-- This function could even be written exactly a method (a la Python's
-- __next__), where the state value is the object itself.
local function inclusive_range_iter(stop, prev)
    -- "stop" is the state value; "prev" is the last value we returned
    local val = prev + 1
    if val > stop then
        return
    end
    return val
end
local function inclusive_range(start, stop)
    -- Return the iterator function, and pass it the stop value as its state.
    -- The "last value" is a little weird here; on the first iteration, there
    -- is no last value.  Here we can fake it by subtracting 1 from the
    -- starting number, but in other cases, it might make more sense if the
    -- "state" were a table containing both the start and stop values.
    return inclusive_range_iter, stop, start - 1
end

-- 6 7 8 9 with both implementations
for n in inclusive_range(6, 9) do
    ...
end

Lua doesn’t have generators. Surprisingly, it has fully-fledged coroutines — call stacks that can be paused at any time. Lua sometimes refers to them as “threads”, but only one can be running at a time. Effectively they’re like Python generators, except you can call a function which calls a function which calls a function which eventually yields, and the entire call stack from that point up to the top of the coroutine is paused and preserved.

In Python, the mere presence of yield causes a function to become a generator. In Lua, since any function might try to yield the coroutine it’s currently in, a function has to be explicitly called as a coroutine using functions in the coroutine library.

But this post is about iterators, not coroutines. Coroutines don’t function as iterators, but Lua provides a coroutine.wrap() that takes a function, turns it into a coroutine, and returns a function that resumes the coroutine. That’s enough to allow a coroutine to be turned into an iterator. The Lua book even has a section about this.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
local function inclusive_range(start, stop)
    local val = start
    while val <= stop do
        coroutine.yield(val)
        val = val + 1
    end
end
-- Unfortunately, coroutine.wrap() doesn't have any way to pass initial
-- arguments to the function it wraps, so we need this dinky wrapper.
-- I should clarify that the ... here is literal syntax for once.
local function iter_coro(entry_point, ...)
    local args = {...}
    return coroutine.wrap(function()
        entry_point(unpack(args))
    end)
end

# 6 7 8 9
for n in iter_coro(inclusive_range, 6, 9) do
    ...
end

So, that’s cool. Lua doesn’t do a lot for you — unfortunately, list processing tricks can be significantly more painful in Lua — but it has some pretty interesting primitives that compose with each other remarkably well.

Perl 5

Perl has a very straightforward C-style for loop, which looks and works exactly as you might expect. my, which appears frequently in these examples, is just local variable declaration.

1
2
3
for (my $i = 0; $i < 10; $i++) {
    ...
}

Nobody uses it. Everyone uses the iteration-style for loop. (It’s occasionally called foreach, which is extra confusing because both for and foreach can be used for both kinds of loop. Nobody actually uses the foreach keyword.)

1
2
3
for my $value (@container) {
    ...
}

The iteration loop can be used for numbers, as well, since Perl has a .. inclusive range operator. For iterating over an array with indexes, Perl has the slightly odd $#array syntax, which is the index of the last item in @array. Creating something like Python’s enumerate is a little tricky in Perl, because you can’t directly return a list of lists, and the workaround doesn’t support unpacking. It’s complicated.

1
2
3
4
5
6
7
8
for my $i (1..10) {
    ...
}

for my $index (0..$#array) {
    my $value = $array[$index];
    ...
}

A hash (Perl’s mapping “shape”) can’t be iterated directly. Or, well, it can, but the loop will alternate between keys and values because Perl is weird. Instead you need the keys or values built-in functions to get the keys or values as regular lists. (These functions also work on arrays as of Perl 5.12.)

1
2
3
for my $key (keys %container) {
    ...
}

For iterating over both keys and values at the same time, Perl has an each function. The behavior is a little weird, since every call to the function advances an internal iterator inside the hash and returns a new pair. If a loop using each terminates early, the next use of each may silently start somewhere in the middle of the hash, skipping a bunch of its keys. This is probably why I’ve never seen each actually used.

1
2
3
while (my ($key, value) = each %container) {
    ...
}

Despite being very heavily built on the concept of lists, Perl doesn’t have an explicit iterator protocol, and its support for lazy iteration in general is not great. When they’re used at all, lazy iterators tend to be implemented as ad-hoc closures or callable objects, which require a while loop:

1
2
3
4
my $iter = custom_iterator($collection);
while (my $value = $iter->()) {
    ...
}

Here be dragons

It is possible to sorta-kinda fake an iterator protocol. If you’re not familiar, Perl’s variables come in several different “shapes” — hash, array, scalar — and it’s possible to “tie” a variable to a backing object which defines the operations for a particular shape. It’s a little like operator overloading, except that Perl also has operator overloading and it’s a completely unrelated mechanism. In fact, you could use operator overloading to make your object return a tied array when dereferenced as an array. I am talking gibberish now.

Anyway, the trick is to tie an array and return a new value for each consecutive fetch of an index. Like so:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
use v5.12;
package ClosureIterator;

# This is the tie "constructor" and just creates a regular object to store
# our state
sub TIEARRAY {
    my ($class, $closure) = @_;
    my $self = {
        closure => $closure,
        nextindex => 0,
    };
    return bless $self, $class;
}

# This is called to fetch the item at a particular index; for an iterator,
# only the next item is valid
sub FETCH {
    my ($self, $index) = @_;

    if ($index == 0) {
        # Always allow reading index 0, both to mean a general "get next
        # item" and so that looping over the same array twice will work as
        # expected
        $self->{nextindex} = 0;
    }
    elsif ($index != $self->{nextindex}) {
        die "ClosureIterator does not support random access";
    }

    $self->{nextindex}++;
    return $self->{closure}->();
}

# The built-in shift() function means "remove and return the first item", so
# it's a good fit for a general "advance iterator"
sub SHIFT {
    my ($self) = @_;
    $self->{nextindex} = 0;
    return $self->{closure}->();
}

# Yes, an array has to be able to report its own size...  but luckily, a for
# loop fetches the size on every iteration!  As long as this returns
# increasingly large values, such a loop will continue indefinitely
sub FETCHSIZE {
    my ($self) = @_;
    return $self->{nextindex} + 1;
}

# Most other tied array operations are for modifying the array, which makes no
# sense here.  They're deliberately omitted, so trying to use them will cause a
# "can't locate object method" error.


package main;

# Create an iterator that yields successive powers of 2
tie my @array, 'ClosureIterator', sub {
    # State variables are persistent, like C statics
    state $next = 1;
    my $ret = $next;
    $next *= 2;
    return $ret;
};

# This will print out 1, 2, 4, 8, ... 1024, at which point the loop breaks
for my $i (@array) {
    say $i;
    last if $i > 1000;
}

This transparently works like any other array… sort of. You can loop over it (forever!); you can use shift to pop off the next value; you can stop a loop and then continue reading from it later.

Unfortunately, this is just plain weird, even for Perl, and I very rarely see it used. Ultimately, Perl’s array operations come in a set, and this is an array that pretends not to be able to do half of them. Even Perl developers are likely to be surprised by an array, a fundamental “shape” of the language, with quirky behavior.

The biggest problem is that, as I said, Perl is heavily built on lists. Part of that design is that @arrays are very eager to spill their contents into a surrounding context. Naïvely passing an array to a function, for example, will expand its elements into separate arguments, losing the identity of the array itself (and losing any tied-ness). Interpolating an array into a string automatically space-separates its elements.

Unlike a for loop, these operations only ask the array for its size once — so rather than printing an infinite sequence, they’ll print a completely arbitrary prefix of it. In the case above, spilling a fresh array will read one item; spilling the array after the example loop will read eleven items. So while a tied array works nicely with a for loop, it’s at odds with the most basic rules of Perl syntax.

Also, Perl’s list-based nature means it’s attracted a lot of list-processing utilities — but these naturally expect to receive a spilled list of arguments and cannot work with a lazy iterator.

I found multiple mentions of the List::Gen module while looking into this. I’d never heard of it before and I’ve never seen it used, but it tries to fill this gap (and makes use of array tying, among other things). It’s a bit weird, and its source code is extremely weird, and it took me twenty minutes to figure out how it was using <...> as a quoting construct.

(<...> in Perl does filename globbing, so it’s usually seen as <*.txt>. The same syntax is used for reading from a filehandle, which makes this confusing and ambiguous, so it’s generally discouraged in favor of the built-in glob function which does the same thing. Well, it turns out that <...> must just call glob() at Perl-level, because List::Gen manages to co-opt this syntax simply by exporting its own glob function. Perl is magical.)

Perl 6

Perl 6, a mad experiment to put literally every conceivable feature into one programming language, naturally has a more robust concept of iteration.

At first glance, many of the constructs are similar to those of Perl 5. The C-style for loop still exists for some reason, but has been disambiguated under the loop keyword.

1
2
3
4
5
6
7
8
loop (my $i = 1; $i <= 10; $i++) {
    ...
}

# More interestingly, loop can be used completely bare for an infinite loop
loop {
    ...
}

The for block has slightly different syntax and a couple new tricks.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
# Unlike in Perl 5, $value is automatically declared and scoped to the block,
# without needing an explicit 'my'
for @container -> $value {
    ...
}

for 1..10 -> $i {
    ...
}

# This doesn't iterate in pairs; it reads two items at a time from a flat list!
for 1..10 -> $a, $b {
    ...
}

Not apparent in the above code is that ranges are lazy in Perl 6, as in Python; the elements are computed on demand. In fact, Perl 6 supports a range like 1..Inf.

Loop variables are also aliases. By default they’re read-only, so this appears to work like Python… but Perl has always had a C-like language-level notion of “slots” that Python does not, and it becomes apparent if the loop variable is made read-write:

1
2
3
4
5
6
7
8
my @fruits = «apple orange pear»;
for @fruits -> $fruit is rw {
    # This is "apply method inplace", i.e. shorthand for:
    # $fruit = $fruit.uc;
    # Yes, you can do that.
    $fruit .= uc;
}
say @fruits;  # APPLE ORANGE PEAR

For iterating with indexes, there’s a curious idiom:

1
2
3
4
5
6
7
# ^Inf is shorthand for 0..Inf, read as "up to Inf".
# Z is the zip operator, which interleaves its arguments' elements into a
# single flat list.
# This makes use of the "two at a time" trick from above.
for ^Inf Z @array -> $index, $value {
    ...
}

Iterating hashes is somewhat simpler; hashes have methods, and the .kv method returns the keys and values. (It actually returns them in a flat list interleaved, which again uses “two at a time” syntax. If you only use a single loop variable, your loop iterations will alternate between a key and a value. Iterating a hash directly produces pairs, which are a first-class data type in Perl 6, but I can’t find any syntax for directly unpacking a pair within a loop header.)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
for %container.kv -> $key, value {
    ...
}

# No surprises here
for %container.keys -> $key {
    ...
}
for %container.values -> $value {
    ...
}

Perl 6 is very big on laziness, which is perhaps why it took fifteen years to see a release. It has the same iterable versus iterator split as Python. Given a container (iterable), ask for an iterator; given an iterator, repeatedly ask for new values. When the iterator is exhausted, it returns the IterationEnd sentinel. Exactly the same ideas. I’m not clear on the precise semantics of the for block and can’t find a simple reference, but they’re probably much like Python’s… plus a thousand special cases.

Generators, kinda

Perl 6 also has its own version of generators, though with a few extra twists. Curiously, generators are a block called gather, rather than a kind of function — this means that a one-off gather is easier to create, but a gather factory must be explicitly wrapped in a function. gather can even take a single expression rather than a block, so there’s no need for separate “generator expression” syntax as in Python.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
sub inclusive-range($start, $stop) {
    return gather {
        my $val = $start;
        while $val <= $stop {
            take $val;
            $val++;
        }
    };
}

# 6 7 8 9
for inclusive-range(6, 9) -> $n {
    ...
}

Unlike Python’s yield, Perl 6’s take is dynamically scoped — i.e., take can be used anywhere in the call stack, and it will apply to the most recent gather caller. That means arbitrary-depth coroutines, which seems like a big deal to me, but the documentation mentions it almost as an afterthought.

The documentation also says gather/take can generate values lazily, depending on context,” but neglects to clarify how context factors in. The code I wrote above turns out to be lazy, but this ambiguity inclines me to use the explicit lazy marker everywhere.

Ultimately it’s a pretty flexible feature, but has a few quirks that make it a bit clumsier to use as a straightforward generator. Given that the default behavior is an eagerly-evaluated block, I think the original intention was to avoid the slightly unsatisfying pattern of “push onto an array every iteration through a loop” — instead you can now do this:

1
2
3
4
5
6
my @results = gather {
    for @source-data -> $datum {
        next unless some-test($datum);
        take process($datum);
    }
};

Using a simple (syntax-highlighted!) take puts the focus on the value being taken, rather than the details of putting it where it wants to go and how it gets there. It’s an interesting idea and I’m surprised I’ve never seen it demonstrated this way.

With gather and some abuse of Perl’s exceptionally compactable syntax, I can write a much shorter version of the infinite Perl 5 iterator above.

1
2
3
4
5
6
7
8
my @powers-of-two = lazy gather take (state $n = 1) *= 2 for ^Inf;

# Binds to $_ by default
for @powers-of-two {
    # Method calls are on $_ by default
    .say;
    last if $_ > 1000;
}

It’s definitely shorter, I’ll give it that. Leaving off the lazy in this case causes an infinite loop as Perl tries to evaluate the entire list; using a $ instead of a @ produces a “Cannot .elems a lazy list” error; using $ without lazy prints a ...-terminated representation of the infinite list and then hangs forever. I don’t quite understand the semantics of stuffing a list into a scalar ($) variable in Perl 6, and to be honest the list/array semantics seem to be far more convoluted than Perl 5, so I have no idea what’s going on here. Perl 6 has a lot of fascinating toys that are very easy to use incorrectly.

Nuts and bolts

Iterables and iterators are encoded explicitly as the Iterable and Iterator roles. An Iterable has an .iterator method that should return an Iterator. An Iterator has a .pull-one method that returns the next value, or the IterationEnd sentinel when the iterator is exhausted. Both roles offer several other methods, but they have suitable default implementations.

inclusive-range might be transformed into a class thusly:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class InclusiveRangeIterator does Iterator {
    has $.range is required;
    has $!nextval = $!range.start;

    method pull-one() {
        if $!nextval > $!range.stop {
            return IterationEnd;
        }

        # Perl people would probably phrase this:
        # ++$!nextval
        # and they are wrong.
        my $val = $!nextval;
        $!nextval++;
        return $val;
    }
}

class InclusiveRange does Iterable {
    has $.start is required;
    has $.stop is required;

    # Don't even ask
    method new($start, $stop) {
        self.bless(:$start, :$stop);
    }

    method iterator() {
        InclusiveRangeIterator.new(range => self);
    }
}

# 6 7 8 9
for InclusiveRange.new(6, 9) -> $n {
    ...
}

Can we use gather to avoid the need for an extra class, just as in Python? We sure can! The only catch is that Perl 6 iterators don’t also pretend to be iterables (remember, in Python, iter(it) should produce it), so we need to explicitly return a gather block’s iterator.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class InclusiveRange does Iterable {
    has $.start is required;
    has $.stop is required;

    # Don't even ask
    method new($start, $stop) {
        self.bless(:$start, :$stop);
    }

    method iterator() {
        gather {
            my $val = $!start;
            while $val <= $!stop {
                take $val;
                $val++;
            }
        }.iterator;  # <- this is important
    }
}

For sequences, Perl 6 has the Seq type. Curiously, even an infinite lazy gather is still a Seq. Indexing and length are not part of Seq — both are implemented as separate methods.

Curiously, even though Perl 6 became much stricter overall, the indexing methods don’t seem to be part of a role; you only need define them, much like Python’s __dunder__ methods. In fact, the preceding examples, does Iterator isn’t necessary at all; the for block will blindly try to call an iterator method and doesn’t much care where it came from.

I’m sure there are plenty of cute tricks possible with Perl 6, but, er, I’ll leave those as an exercise for the reader.

Ruby

Ruby is a popular and well-disguised Perl variant, if Perl just went completely all-in on Smalltalk. It has no C-style for, but it does have an infinite loop block and a very Python-esque for:

1
2
3
for value in sequence do
    ...
end

Nobody uses this. No, really, the core language documentation outright says:

The for loop is rarely used in modern ruby programs.

Instead, you’ll probably see this:

1
2
3
sequence.each do |value|
    ...
end

It doesn’t look it, but this is completely backwards from everything seen so far. All of these other languages have used external iterators, where an object is repeatedly asked to produce values and calling code can do whatever it wants with them. Here, something very different is happening. The entire do ... end block acts as a closure whose argument is value; it’s passed to the each method, which calls it once for each value in the sequence. This is an internal iterator.

Pass a block to a function which can then call it a lot” is a built-in syntactic feature of Ruby, so these kinds of iterators are fairly common. The upside is that they look almost like a custom block, so they fit naturally with the language. The downside is that all of these block-accepting methods are implemented on Array, rather than as generic functions: bsearch, bsearch_index, collect, collect!, combination, count, cycle, delete, delete_if, drop_while, each, each_index, fetch, fill, find_index, index, keep_if, map, map!, permutation, product, reject, reject!, repeated_combination, repeated_permutation, reverse_each, rindex, select, select!, sort, sort!, sort_by!, take_while, uniq, uniq!, zip. Some of those, as well as a number of additional methods, are provided by the Enumerable mixin which can express them in terms of each. I suppose the other upside is that any given type can provide its own more efficient implementation of these methods, if it so desires.

I guess that huge list of methods answers most questions about how to iterate over indices or in reverse. The only bit missing is that .. range syntax exists in Ruby as well, and it produces Range objects which also have an each method. If you don’t care about each index, you can also use the cute 3.times method.

Ruby blocks are a fundamental part of the language and built right into the method-calling syntax. Even break is defined in terms of blocks, and it works with an argument!

1
2
3
4
# This just doesn't feel like it should work, but it does.  Prints 17.
# Braces are conventionally used for inline blocks, but do/end would work too.
primes = [2, 3, 5, 7, 11, 13, 17, 19]
puts primes.each { |p| break p if p > 16 }

each() doesn’t need to do anything special here; break will just cause its return value to be 17. Somehow. (Honestly, this is the sort of thing that makes me wary of Ruby; it seems so ad-hoc and raises so many questions. A language keyword that changes the return value of a different function? Does the inside of each() know about this or have any control over it? How does it actually work? Is there any opportunity for cleanup? I have no idea, and the documentation doesn’t seem to think this is worth commenting on.)

Using blocks

Anyway, with block-passing as a language feature, the “iterator protocol” is pretty straightforward: just write a method that takes a block.

1
2
3
4
5
def each
    for value in self do
        yield value
    end
end

Be careful! Though it’s handy for iteration, that yield is not the same as Python’s yield. Ruby’s yield calls the passed-in block — yields control to the caller — with the given value(s).

I pulled a dirty trick there, because I expressed each in terms of for. So how does for work? Well, ah, it just delegates to each. Oops!

How, then, do you write an iterator completely from scratch? The obvious way is to use yield repeatedly. That gives you something that looks rather a lot like Python, though it doesn’t actually pause execution.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class InclusiveRange
    # This gets you a variety of other iteration methods, all defined in
    # terms of each()
    include Enumerable

    def initialize(start, stop)
        @start = start
        @stop = stop
    end
    def each
        val = @start
        while val <= @stop do
            yield val
            val += 1
        end
    end
end

# 6 7 8 9
# A `for` loop would also work here
InclusiveRange.new(6, 9).each do |n|
    ...
end

Enumerators

Well, that’s nice for creating a whole collection type, but what if I want an ad-hoc custom iterator? Enter the Enumerator class, which allows you to create… ah, enumerators.

Note that the relationship between Enumerable and Enumerator is not the same as the relationship between “iterable” and “iterator”. Most importantly, neither is really an interface. Enumerable is a set of common iteration methods that any collection type may want to have, and it expects an each to exist. Enumerator is a generic collection type, and in fact mixes in Enumerable. Maybe I should just show you some code.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def inclusive_range(start, stop)
    Enumerator.new do |y|
        val = start
        while val <= stop do
            y.yield val
            val += 1
        end
    end
end

# 6 7 8 9
inclusive_range(6, 9).each do |n|
    puts n
end

Enumerator turns a block into a fully-fledged data stream. The block is free to do whatever it wants, and whenever it wants to emit a value, it calls y.yield value. The y argument is a “yielder” object, an opaque magic type; y.yield is a regular method call, unrelated to the yield keyword. (y << value is equivalent; << is Ruby’s “append” operator. And also, yes, bit shift.)

The amazing bit is that you can do this:

1
2
# 6
puts inclusive_range(6, 9).first

Enumerator has all of the Enumerable methods, one of which is first. So, that’s nice.

The really amazing bit is that if you stick some debugging code into the block passed to Enumerator.new, you’ll find that… the values are produced lazily. That call to first() doesn’t generate the full sequence and then discard everything after the first item; it only generates the first item, then stops.

(Beware! The values are produced lazily, but many Enumerable methods are eager. I’ll get back to this in a moment.)

Hang on, didn’t I say yield doesn’t pause execution? Didn’t I also say the above yield is just a method call, not the keyword?

I did! And I wasn’t lying. The really truly amazing bit, which I’ve seen shockingly little excitement about while researching this, is that under the hood, this is all using Fibers. Coroutines.

Enumerator.new takes a block and turns it into a coroutine. Every time something wants a value from the enumerator, it resumes the coroutine. The yielder object’s yield method then calls Fiber.yield() to pause the coroutine. It works just like Lua, but it’s designed to work with existing Ruby conventions, like the piles of internal iteration methods developers expect to find.

So Enumerator.new can produce Python-style generators, albeit in a slightly un-native-looking way. There’s also one other significant difference: an Enumerator can restart itself for each method called on it, simply by calling the block again. This code will print 6 three times:

1
2
3
4
ir = inclusive_range(6, 9)
puts ir.first
puts ir.first
puts ir.first

For something like an inclusive range object, that’s pretty nice. For something like a file, maybe not so nice. It also means you need to be sure to put your setup code inside the block passed to Enumerator.new, or funny things will happen when the block is restarted.

Something like generators

But wait, there’s more. Specifically, this common pattern, which pretty much lets you ignore Enumerator.new entirely.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def some_iterator_method
    # __method__ is the current method name.  block_given? is straightforward.
    return enum_for(__method__) unless block_given?

    # An extremely accurate simulation of a large list.
    (1..1000).each do |item|
        puts "having a look at #{item}"
        # Blocks are invisible to `yield`; this will yield to the block passed
        # to some_iterator_method.
        yield item if item.even?
    end
end

# having a look at 1
# having a look at 2
# 2
puts some_iterator_method.first

Okay, bear with me.

First, some_iterator_method() is called. It doesn’t have a block attached, so block_given? is false, and it returns enum_for(...), whatever that does. Then first() is called on the result, and that produces a single element and stops.

The above code has no magic yielder object. It uses the straightforward yield keyword. Why doesn’t it loop over the entire range from 1 to 1000?

Remember, Enumerator uses coroutines under the hood. One neat thing coroutines can do is pause code that doesn’t know it’s in a coroutine. Python’s generators pause themselves with yield, and the mere presence of yield turns a function into a generator; but in Lua or Ruby or any other language with coroutines, any function can pause at any time. You can even make a closure that pauses, then pass that closure to another function which calls it, without that function ever knowing anything happened.

(This arguably has some considerable downsides as well — it becomes difficult to know when or where your code might pause, which makes reasoning about the order of operations much harder. That’s why Python and some other languages opted to implement async IO with an await keyword — anyone reading the code knows that it can only pause where an await appears.)

(Also, I’m saying “pause” here instead of “yield” because Ruby has really complicated the hell out of this by already having a yield keyword that does something totally different, and naming its coroutine pause function yield.)

Anyway, that’s exactly what’s happening here. enum_for returns an Enumerator that wraps the whole method. (It doesn’t need to know self, because enum_for is actually a method inherited from Object, goodness gracious.) When the Enumerator needs some items, it calls the method a second time with its own block, running in a coroutine, just like a block passed to Enumerator.new. Eventually the method emits a value using the regular old yield keyword, and that value reaches the block created by Enumerator, and that block pauses the call stack. It doesn’t matter that Range.each is eager, because its iteration is still happening in code somewhere, and that code is part of a call stack in a coroutine, so it can be paused. Eventually the coroutine is no longer useful and gets thrown away, so the eager each call simply stops midway through its work, unaware that anything unusual ever happened.

In fact, despite being an Object method, enum_for isn’t special at all. It can be expressed in pure Ruby very easily:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def my_enum_for(receiver, method)
    # Enumerator.new creates a coroutine-as-iteration-source, as above.
    Enumerator.new do |y|
        # All it does is call the named method with a trivial block.  Every
        # time the method produces a value with the `yield` keyword, we pass it
        # along to the yielder object, which pauses the coroutine.
        # This is nothing more than a bridge between "yield" in the Ruby block
        # sense, and "yield" in the coroutine sense.
        receiver.send method do |value|
            y.yield value
        end
    end
end

So, that’s pretty neat. Incidentally, several built-in methods like Array.each and Enumerable.collect act like this, returning an Enumerator if called with no arguments.

Full laziness

I mentioned above that while an Enumerator fetches items lazily, many of the methods are eager. To clarify what I mean by that, consider:

1
2
3
4
5
inclusive_range(6, 9000).collect {
    |n|
    puts "considering #{n}"
    "a" * n
}.first(3)

collect() is one of those common Enumerable methods. You might know it by its other name, map(). Ruby is big on multiple names for the same thing: one that everyone uses in practice, and another that people who don’t use Ruby will actually recognize.

Even though this code ultimately only needs three items, and even though there’s all this coroutine machinery happening under the hood, this still evaluates the entire range. Why?

The problem is that collect() has always returned an array, and is generally expected to continue doing so. It has no way of knowing that it’s about to be fed into first. Rather than violate this API, Ruby added a new method, Enumerable.lazy. This stops after three items:

1
2
3
4
5
inclusive_range(6, 9000).lazy.collect {
    |n|
    puts "considering #{n}"
    "a" * n
}.first(3)

All this does is return an Enumerator::Lazy object, which has lazy implementations of various methods that would usually do a full iteration. Methods like first(3) are still “eager” (in the sense that they just return an array), since their results have a fixed finite size.

This seems a little clunky to me, since the end result is still an object with a collect method that doesn’t return an array. I suspect the real reason is just that Enumerator was added first; even though the coroutine support was already there, Enumerator::Lazy only came along later. Changing existing eager methods to be lazy can, ah, cause problems.

The only built-in type that seems to have interesting lazy behavior is Range, which can be infinite.

1
2
3
4
# Whoops, infinite loop.
(1..Float::INFINITY).select { |n| n.even? }.first(5)
# 2 4 6 8 10
(1..Float::INFINITY).lazy.select { |n| n.even? }.first(5)

A loose end

I think the only remaining piece of this puzzle is something I stumbled upon but can’t explain. Enumerator has a next method, which returns the next value or raises StopIteration.

Wow, that sounds awfully familiar.

But I can’t find anything in the language or standard library that uses this, with one single and boring exception: the loop construct. It catches StopIteration and exits the block.

1
2
3
4
5
6
enumerator = [1, 2, 3].each
loop do
    while true do
        puts enumerator.next
    end
end

On the fourth call, next() will be out of items, so it raises StopIteration. Removing the loop block makes this quite obvious.

That’s it. That’s the only use of it in the language, as far as I can tell. It seems almost… vestigial. It’s also a little weird, since it keeps the current iteration state inside the Enumerator, unlike any of its other methods. But it’s also the only form of external iteration that I know of in Ruby, and that’s handy to have sometimes.

And, uh, so on

I intended to foray into a few more languages, including some recent lower-level friends like C++/Rust/Swift, but this post somehow spiraled out of control and hit nine thousand words. No one has read this far.

Handily, it turns out that the above languages pretty much cover the basic ways of approaching iteration; if any of this made sense, other languages will probably seem pretty familiar.

  • C++’s iteration protocol(s) has existed for a long time in the form of ++it to advance an iterator and *it to read the current item, though this was usually written manually in a C-style for loop, and loops were generally terminated with an explicit endpoint.

    C++11 added the range-based for, which does basically the same stuff under the hood. Idiomatic C++ is inscrutible, but maybe you can make sense of this project which provides optionally-infinite iterable ranges.

  • Rust has an entire (extremely well-documented) iter module with numerous iterators and examples of how to create your own. The core of the Iterator trait is just a next method which returns None when exhausted. It also has a lot of handy Ruby-like chainable methods, so working directly with iterators is more common in Rust than in Python.

  • Swift also has (well-documented) simple next-based iterators, though these return nil when exhausted, which means (like Lua) that an iterator cannot produce nil as a value. (This isn’t the case with Rust, where next returns an Option<T> — a valid None would be returned as Some(None).)

I could probably keep finding more languages indefinitely, so I’m gonna take a break from this now.

Iteration in one language, then all the others

Post Syndicated from Eevee original https://eev.ee/blog/2016/11/18/iteration-in-one-language-then-all-the-others/

You may have noticed that I like comparing features across different languages. I hope you like it too, because I’m doing it again.

Python

I’m most familiar with Python, and iteration is one of its major concepts, so it’s a good place to start and a good overview of iteration. I’ll dive into Python a little more deeply, then draw parallels to other languages.

Python only has one form of iteration loop, for. (Note that all of these examples are written for Python 3; in Python 2, some of the names are slightly different, and fewer things are lazy.)

1
2
for value in sequence:
    ...

in is also an operator, so value in sequence is also the way you test for containment. This is either very confusing or very satisfying.

When you need indices, or specifically a range of numbers, you can use the built-in enumerate or range functions. enumerate works with lazy iterables as well.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
# This makes use of tuple unpacking to effectively return two values at a time
for index, value in enumerate(sequence):
    ...

# Note that the endpoint is exclusive, and the default start point is 0.  This
# matches how list indexing works and fits the C style of numbering.
# 0 1 2 3 4
for n in range(5):
    ...

# Start somewhere other than zero, and the endpoint is still exclusive.
# 1 2 3 4
for n in range(1, 5):
    ...

# Count by 2 instead.  Can also use a negative step to count backwards.
# 1 3 5 7 9
for n in range(1, 11, 2):
    ...

dicts (mapping types) have several methods for different kinds of iteration. Additionally, iterating over a dict directly produces its keys.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
for key in mapping:
    ...

for key in mapping.keys():
    ...

for value in mapping.values():
    ...

for key, value in mapping.items():
    ...

Python distinguishes between an iterable, any value that can be iterated over, and an iterator, a value that performs the actual work of iteration. Common iterable types include list, tuple, dict, str, and set. enumerate and range are also iterable.

Since Python code rarely works with iterators directly, and many iterable types also function as their own iterators, it’s common to hear “iterator” used to mean an iterable. To avoid this ambiguity, and because the words are fairly similar already, I’ll refer to iterables as containers like the Python documentation sometimes does. Don’t be fooled — an object doesn’t actually need to contain anything to be iterable. Python’s range type is iterable, but it doesn’t physically contain all the numbers in the range; it generates them on the fly as needed.

The fundamental basics of iteration are built on these two ideas. Given a container, ask for an iterator; then repeatedly advance the iterator to get new values. When the iterator runs out of values, it raises StopIteration. That’s it. In Python, those two steps can be performed manually with the iter and next functions. A for loop is roughly equivalent to:

1
2
3
4
5
6
7
8
9
_iterator = iter(container)
_done = False
while not _done:
    try:
        value = next(_iterator)
    except StopIteration:
        _done = True
    else:
        ...

An iterator can only move forwards. Once a value has been produced, it’s lost, at least as far as the iterator is concerned. These restrictions are occasionally limiting, but they allow iteration to be used for some unexpected tasks. For example, iterating over an open file produces its lines — even if the “file” is actually a terminal or pipe, where data only arrives once and isn’t persistently stored anywhere.

Generators

A more common form of “only forwards, only once” in Python is the generator, a function containing a yield statement. For example:

1
2
3
4
5
6
7
8
9
def inclusive_range(start, stop):
    val = start
    while val <= stop:
        yield val
        val += 1

# 6 7 8 9
for n in inclusive_range(6, 9):
    ...

Calling a generator function doesn’t execute its code, but immediately creates a generator iterator. Every time the iterator is advanced, the function executes until the next yield, at which point the yielded value is returned as the next value and the function pauses. The next iteration will then resume the function. When the function returns (or falls off the end), the iterator stops.

Since the values here are produced by running code on the fly, it’s of course impossible to rewind a generator.

The underlying protocol is straightforward. A container must have an __iter__ method that returns an iterator, corresponding to the iter function. An iterator must have a __next__ method that returns the next item, corresponding to the next function. If the iterator is exhausted, __next__ must raise StopIteration. An iterator must also have an __iter__ that returns itself — this is so an iterator can be used directly in a for loop.

The above inclusive range generator might be written out explicitly like this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class InclusiveRange:
    def __init__(self, start, stop):
        self.start = start
        self.stop = stop

    def __iter__(self):
        return InclusiveRangeIterator(self)

class InclusiveRangeIterator:
    def __init__(self, incrange):
        self.incrange = incrange
        self.nextval = incrange.start

    def __iter__(self):
        return self

    def __next__(self):
        if self.nextval > self.incrange.stop:
            raise StopIteration

        val = self.nextval
        self.nextval += 1
        return val

This might seem like a lot of boilerplate, but note that the iterator state (here, nextval) can’t go on InclusiveRange directly, because then it’d be impossible to iterate over the same object twice at the same time. (Some types, like files, do act as their own iterators because they can’t meaningfully be iterated in parallel.)

Even Python’s internals work this way. Try iter([]) in a Python REPL; you’ll get a list_iterator object.

In truth, it is a lot of boilerplate. User code usually uses this trick:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class InclusiveRange:
    def __init__(self, start, stop):
        self.start = start
        self.stop = stop

    def __iter__(self):
        val = self.start
        while val <= self.stop:
            yield val
            val += 1

Nothing about this is special-cased in any way. Now __iter__ is a generator, and calling a generator function returns an iterator, so all the constraints are met. It’s a really easy way to convert a generator function into a type. If this class were named inclusive_range instead, it would even be backwards-compatible; consuming code wouldn’t even have to know it’s a class.

Reversal

But why would you do this? One excellent reason is to add support for other sequence-like operations, like reverse iteration support. An iterator can’t be reversed, but a container might support being iterated in reverse:

1
2
3
4
fruits = ['apple', 'orange', 'pear']
# pear, orange, apple
for value in reversed(fruits):
    ...

Iterating a lazy container doesn’t always make sense, but when it does, it’s easy to implement by returning an iterator from __reversed__.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class InclusiveRange:
    def __init__(self, start, stop):
        self.start = start
        self.stop = stop

    def __iter__(self):
        val = self.start
        while val <= self.stop:
            yield val
            val += 1

    def __reversed__(self):
        val = self.stop
        while val >= self.start:
            yield val
            val -= 1

Note that Python does not have “bi-directional” iterators, which can freely switch between forwards and reverse iteration on the fly. A bidirectional iterator is useful for cases like doubly-linked lists, where it’s easy to get from one value to the next or previous value, but not as easy to start from the beginning and get the tenth item.

Iteration is often associated with sequences, though they’re not quite the same. In Python, a sequence is a value that can be indexed in order as container[0], container[1], etc. (Indexing is implemented with __getitem__.) All sequences are iterable; in fact, if a type implements indexing but not __iter__, the iter function will automatically try indexing it from zero instead. reversed does the same, though it requires that the type implement __len__ as well so it knows what the last item is.

Much of this is codified more explicitly in the abstract base classes in collections.abc, which also provide default implementations of common methods.

Not all iterables are sequences, and not every value that can be indexed is a sequence! Python’s mapping type, dict, uses indexing to fetch the value for a key; but a dict has no defined order and is not a sequence. However, a dict can still be iterated over, producing its keys (in arbitrary order). A set can be iterated over, producing its values in arbitrary order, but it cannot be indexed at all. A type could conceivably use indexing for something more unusual and not be iterable at all.

A common question

It’s not really related to iteration, but people coming to Python from Ruby often ask why len() is a built-in function, rather than a method. The same question could be asked about iter() and next() (and other Python builtins), which more or less delegate directly to a “reserved” __dunder__ method anyway.

I believe the technical reason is simply the order that features were added to the language in very early days, which is not very interesting.

The philosophical reason, imo, is that Python does not reserve method names for fundamental operations. All __dunder__ names are reserved, of course, but everything else is fair game. This makes it obvious when a method is intended to add support for some language-ish-level operation, even if you don’t know what all the method names are. Occasionally a third-party library invents its own __dunder__ name, which is a little naughty, but the same reasoning applies: “this is a completely generic interface that some external mechanism is expected to use”.

This approach also avoids a namespacing problem. In Ruby, a Rectangle class might want to have width and length attributes… but the presence of length means a Rectangle looks like it functions as a sequence! Since “interface” method names aren’t namespaced in any way, there is no way to say that you don’t mean the same thing as Array.length.

It’s a minor quibble, since everything’s dynamically typed anyway, so the real solution is “well don’t try to iterate a rectangle then”. And Python does use keys as a method name in some obscure cases. Oh, well.

Some cute tricks

The distinction between sequences and iterables can cause some subtle problems. A lot of code that only needs to loop over items can be passed, e.g., a generator. But this can take some conscious care. Compare:

1
2
3
4
5
6
7
8
# This will NOT work with generators, which don't support len() or indexing
for i in range(len(container)):
    value = container[i]
    ...

# But this will
for i, value in enumerate(container):
    ...

enumerate also has a subtle, unfortunate problem: it cannot be combined with reversed. This has bit me more than once, surprisingly.

1
2
3
4
5
6
7
# This produces a TypeError from reversed()
for i, value in reversed(enumerate(container)):
    ...

# This almost works, but the index goes forwards while the values go backwards
for i, value in enumerate(reversed(container)):
    ...

The problem is that enumerate can’t, in general, reverse itself. It counts up from zero as it iterates over its argument; reversing it means starting from one less than the number of items, but it doesn’t yet know how many items there are. But if you just want to run over a list or other sequence backwards, this feels very silly. A trivial helper can make it work:

1
2
3
4
5
def revenum(iterable, end=0):
    start = len(iterable) + end
    for value in iterable:
        start -= 1
        yield start, value

I’ve run into other odd cases where it’s frustrating that a generator doesn’t have a length or indexing. This especially comes up if you make heavy use of generator expressions, which are a very compact way to write a one-off generator. (Python also has list, set, and dict “comprehensions”, which have the same syntax but use brackets or braces instead of parentheses, and are evaluated immediately instead of lazily.)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def get_big_fruits():
    fruits = ['apple', 'orange', 'pear']
    return (fruit.upper() for fruit in fruits)

# Roughly equivalent to:
def get_big_fruits():
    fruits = ['apple', 'orange', 'pear']
    def genexp():
        for fruit in fruits:
            yield fruit.upper()
    return genexp()

If you had thousands of fruits, doing this could save a little memory. The caller is probably just going to loop over them to print them out (or whatever), so using a generator expression means that each uppercase name only exists for a short time; returning a list would mean creating a lot of values all at once.

Ah, but now the caller wants to know how many fruits there are, with minimal fuss. Generators have no length, so that won’t work. Turning this generator expression into a class that also has a __len__ would be fairly ridiculous. So you resort to some slightly ugly trickery.

1
2
3
4
5
6
7
8
# Ugh.  Obvious, but feels really silly.
count = 0
for value in container:
    count += 1

# Better, but weird if you haven't seen it before.  Creates another generator
# expression that just yields 1 for every item, then sums them up.
count = sum(1 for _ in container)

Or perhaps you want the first big fruit? Well, [0] isn’t going to help. This is one of the few cases where using iter and next directly can be handy.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# Oops!  If the container is empty, this raises StopIteration, which you
# probably don't want.
first = next(iter(container))

# Catch the StopIteration explicitly.
try:
    first = next(iter(container))
except StopIteration:
    # This code runs if there are zero items
    ...

# Regular loop that terminates immediately.
# The "else" clause only runs when the container ends naturally (i.e. NOT if
# the loop breaks), which can only happen here if there are zero items.
for value in container:
    first = value
    break
else:
    ...

# next() -- but not __next__()! -- takes a second argument indicating a
# "default" value to return when the iterator is exhausted.  This only makes
# sense if you were going to substitute a default value anyway; doing this and
# then checking for None will do the wrong thing if the container actually
# contained a None.
first = next(iter(container), None)

Other tricks with iter and next include skipping the first item (or any number of initial items, though consider itertools.islice for more complex cases):

1
2
3
4
5
6
7
it = iter(container)
next(it, None)  # Use second arg to ignore StopIteration
for value in it:
    # Since the first item in the iterator has already been consumed, this loop
    # will start with the second item.  If the container had only one or zero
    # items, the loop will get StopIteration and end immediately.
    ...

Iterating two (or more) items at a time:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# Obvious way: call next() inside the loop.
it = iter(container)
for value1 in it:
    # With an odd number of items, this will raise an uncaught StopIteration!
    # Catch it or provide a default value.
    value2 = next(it)
    ...

# Moderately clever way: abuse zip().
# zip() takes some number of containers and iterates over them pairwise.  It
# stores an iterator for each container.  When it's asked for its next item, it
# in turn asks all of its iterators for their next items, and returns them as a
# set.  But by giving it the same exact iterator twice, it'll end up advancing
# that iterator twice and returning two consecutive items.
# Note that zip() stops early as soon as an iterator runs dry, so if the
# container has an odd number of items, this will silently skip the last one.
# If you don't want that, use itertools.zip_longest instead.
it = iter(container)
for line1, line2 in zip(it, it):
    ...

# Far too clever way: exactly the same as above, but written as a one-liner.
# zip(iter(), iter()) would create two separate iterators and break the trick.
# List multiplication produces a list containing the same iterator twice.
# One advantage of this is that the 2 can be a variable.
for value1, value2 in zip(*[iter(container)] * 2):
    ...

Wow, that got pretty weird towards the end. Somehow this turned into Stupid Python Iterator Tricks. Don’t worry; I know far less about these other languages.

C

C is an extreme example with no iterator protocol whatsoever. It barely even supports sequences; arrays are just pointer math. All it has is the humble C-style for loop:

1
2
3
4
5
int[] container = {...};
for (int i = 0; i < container_length; i++) {
    int value = container[i];
    ...
}

Unfortunately, it’s really the best C can do. C arrays don’t know their own length, so no matter what, the developer has to provide it some other way. Even without that, a built-in iterator protocol is impossible — iterators require persistent state (the current position) to be bundled alongside code (how to get to the next position). That pretty much means one of two things: closures or objects. C has neither.

Lua

Lua has two forms of for loop. The first is a simple numeric loop.

1
2
3
4
-- 1 3 5 7 9 11
for value = 1, 11, 2 do
    ...
end

The three values after the = are the start, end, and step. They work similarly to Python’s range(), except that everything in Lua is always inclusive, so for i = 1, 5 will count from 1 to 5.

The generic form uses in.

1
2
3
for value in iterate(container) do
    ...
end

iterate isn’t a special name here, but most of the time a generic for will look like this.

See, Lua doesn’t have objects. It has enough tools that you can build objects fairly easily, but the core language has no explicit concept of objects or method calls. An iterator protocol needs to bundle state and behavior somehow, so Lua uses closures for that. But you still need a way to get that closure, and that means calling a function, and a plain value can’t have functions attached to it. So iterating over a table (Lua’s single data structure) looks like this:

1
2
for key, value in pairs(container) do
    ...

pairs is a built-in function. Lua also has an ipairs, which iterates over consecutive keys and values starting from key 1. (Lua starts at 1, not 0. Lua also represents sequences as tables with numeric keys.)

Lua does have a way to associate “methods” with values, which is how objects are made, but for loops almost certainly came first. So iteration is almost always over a function call, not a bare value.

Also, because objects are built out of tables, having a default iteration behavior for all tables would mean having the same default for all objects. Nothing’s stopping you from using pairs on an object now, but at least that looks deliberate. It’s easy enough to give objects iteration methods and iterate over obj:iter(), though it’s slightly unfortunate that every type might look slightly different. Unfortunately, Lua has no truly generic interface for “this can produce a sequence of values”.

The iteration protocol is really just calling a function repeatedly to get new values. When the function returns nil, the iteration ends. (That means nil can never be part of an iteration! You can work around this by returning two values and making sure the first one is something else that’s never nil, like an index.) The manual explains the exact semantics of the generic for with Lua code, a move I wish every language would make.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
-- This:
for var_1, ···, var_n in explist do block end

-- Is equivalent to this:
do
    local _func, _state, _lastval = explist
    while true do
        local var_1, ···, var_n = _func(_state, _lastval)
        if var_1 == nil then break end
        _lastval = var_1
        block
    end
end

Important to note here is the way multiple-return works in Lua. Lua doesn’t have tuples; multiple assignment is a distinct feature of the language, and multiple return works exactly the same way as multiple assignment. If there are too few values, the extra variables become nil; if there are too many values, the extras are silently discarded.

So in the line local _func, _state, _lastval = explist, the “state” value _state and the “last loop value” _lastval are both optional. Lua doesn’t use them, except to pass them back to the iterator function _func, and they aren’t visible to the for loop body. An iterator can thus be only a function and nothing else, letting _state and _lastval be nil — but they can be a little more convenient at times. Compare:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
-- Usual approach: return only a closure, completely ignoring state and lastval
local function inclusive_range(start, stop)
    local nextval = start
    return function()
        if nextval > stop then
            return
        end
        local val = nextval
        nextval = nextval + 1
        return val
    end
end

-- Alternative approach, not using closures at all.  This is the function we
-- return; each time it's called with the same "state" value and whatever it
-- returned last time it was called.
-- This function could even be written exactly a method (a la Python's
-- __next__), where the state value is the object itself.
local function inclusive_range_iter(stop, prev)
    -- "stop" is the state value; "prev" is the last value we returned
    local val = prev + 1
    if val > stop then
        return
    end
    return val
end
local function inclusive_range(start, stop)
    -- Return the iterator function, and pass it the stop value as its state.
    -- The "last value" is a little weird here; on the first iteration, there
    -- is no last value.  Here we can fake it by subtracting 1 from the
    -- starting number, but in other cases, it might make more sense if the
    -- "state" were a table containing both the start and stop values.
    return inclusive_range_iter, stop, start - 1
end

-- 6 7 8 9 with both implementations
for n in inclusive_range(6, 9) do
    ...
end

Lua doesn’t have generators. Surprisingly, it has fully-fledged coroutines — call stacks that can be paused at any time. Lua sometimes refers to them as “threads”, but only one can be running at a time. Effectively they’re like Python generators, except you can call a function which calls a function which calls a function which eventually yields, and the entire call stack from that point up to the top of the coroutine is paused and preserved.

In Python, the mere presence of yield causes a function to become a generator. In Lua, since any function might try to yield the coroutine it’s currently in, a function has to be explicitly called as a coroutine using functions in the coroutine library.

But this post is about iterators, not coroutines. Coroutines don’t function as iterators, but Lua provides a coroutine.wrap() that takes a function, turns it into a coroutine, and returns a function that resumes the coroutine. That’s enough to allow a coroutine to be turned into an iterator. The Lua book even has a section about this.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
local function inclusive_range(start, stop)
    local val = start
    while val <= stop do
        coroutine.yield(val)
        val = val + 1
    end
end
-- Unfortunately, coroutine.wrap() doesn't have any way to pass initial
-- arguments to the function it wraps, so we need this dinky wrapper.
-- I should clarify that the ... here is literal syntax for once.
local function iter_coro(entry_point, ...)
    local args = {...}
    return coroutine.wrap(function()
        entry_point(unpack(args))
    end)
end

# 6 7 8 9
for n in iter_coro(inclusive_range, 6, 9) do
    ...
end

So, that’s cool. Lua doesn’t do a lot for you — unfortunately, list processing tricks can be significantly more painful in Lua — but it has some pretty interesting primitives that compose with each other remarkably well.

Perl 5

Perl has a very straightforward C-style for loop, which looks and works exactly as you might expect. my, which appears frequently in these examples, is just local variable declaration.

1
2
3
for (my $i = 0; $i < 10; $i++) {
    ...
}

Nobody uses it. Everyone uses the iteration-style for loop. (It’s occasionally called foreach, which is extra confusing because both for and foreach can be used for both kinds of loop. Nobody actually uses the foreach keyword.)

1
2
3
for my $value (@container) {
    ...
}

The iteration loop can be used for numbers, as well, since Perl has a .. inclusive range operator. For iterating over an array with indexes, Perl has the slightly odd $#array syntax, which is the index of the last item in @array. Creating something like Python’s enumerate is a little tricky in Perl, because you can’t directly return a list of lists, and the workaround doesn’t support unpacking. It’s complicated.

1
2
3
4
5
6
7
8
for my $i (1..10) {
    ...
}

for my $index (0..$#array) {
    my $value = $array[$index];
    ...
}

A hash (Perl’s mapping “shape”) can’t be iterated directly. Or, well, it can, but the loop will alternate between keys and values because Perl is weird. Instead you need the keys or values built-in functions to get the keys or values as regular lists. (These functions also work on arrays as of Perl 5.12.)

1
2
3
for my $key (keys %container) {
    ...
}

For iterating over both keys and values at the same time, Perl has an each function. The behavior is a little weird, since every call to the function advances an internal iterator inside the hash and returns a new pair. If a loop using each terminates early, the next use of each may silently start somewhere in the middle of the hash, skipping a bunch of its keys. This is probably why I’ve never seen each actually used.

1
2
3
while (my ($key, value) = each %container) {
    ...
}

Despite being very heavily built on the concept of lists, Perl doesn’t have an explicit iterator protocol, and its support for lazy iteration in general is not great. When they’re used at all, lazy iterators tend to be implemented as ad-hoc closures or callable objects, which require a while loop:

1
2
3
4
my $iter = custom_iterator($collection);
while (my $value = $iter->()) {
    ...
}

Here be dragons

It is possible to sorta-kinda fake an iterator protocol. If you’re not familiar, Perl’s variables come in several different “shapes” — hash, array, scalar — and it’s possible to “tie” a variable to a backing object which defines the operations for a particular shape. It’s a little like operator overloading, except that Perl also has operator overloading and it’s a completely unrelated mechanism. In fact, you could use operator overloading to make your object return a tied array when dereferenced as an array. I am talking gibberish now.

Anyway, the trick is to tie an array and return a new value for each consecutive fetch of an index. Like so:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
use v5.12;
package ClosureIterator;

# This is the tie "constructor" and just creates a regular object to store
# our state
sub TIEARRAY {
    my ($class, $closure) = @_;
    my $self = {
        closure => $closure,
        nextindex => 0,
    };
    return bless $self, $class;
}

# This is called to fetch the item at a particular index; for an iterator,
# only the next item is valid
sub FETCH {
    my ($self, $index) = @_;

    if ($index == 0) {
        # Always allow reading index 0, both to mean a general "get next
        # item" and so that looping over the same array twice will work as
        # expected
        $self->{nextindex} = 0;
    }
    elsif ($index != $self->{nextindex}) {
        die "ClosureIterator does not support random access";
    }

    $self->{nextindex}++;
    return $self->{closure}->();
}

# The built-in shift() function means "remove and return the first item", so
# it's a good fit for a general "advance iterator"
sub SHIFT {
    my ($self) = @_;
    $self->{nextindex} = 0;
    return $self->{closure}->();
}

# Yes, an array has to be able to report its own size...  but luckily, a for
# loop fetches the size on every iteration!  As long as this returns
# increasingly large values, such a loop will continue indefinitely
sub FETCHSIZE {
    my ($self) = @_;
    return $self->{nextindex} + 1;
}

# Most other tied array operations are for modifying the array, which makes no
# sense here.  They're deliberately omitted, so trying to use them will cause a
# "can't locate object method" error.


package main;

# Create an iterator that yields successive powers of 2
tie my @array, 'ClosureIterator', sub {
    # State variables are persistent, like C statics
    state $next = 1;
    my $ret = $next;
    $next *= 2;
    return $ret;
};

# This will print out 1, 2, 4, 8, ... 1024, at which point the loop breaks
for my $i (@array) {
    say $i;
    last if $i > 1000;
}

This transparently works like any other array… sort of. You can loop over it (forever!); you can use shift to pop off the next value; you can stop a loop and then continue reading from it later.

Unfortunately, this is just plain weird, even for Perl, and I very rarely see it used. Ultimately, Perl’s array operations come in a set, and this is an array that pretends not to be able to do half of them. Even Perl developers are likely to be surprised by an array, a fundamental “shape” of the language, with quirky behavior.

The biggest problem is that, as I said, Perl is heavily built on lists. Part of that design is that @arrays are very eager to spill their contents into a surrounding context. Naïvely passing an array to a function, for example, will expand its elements into separate arguments, losing the identity of the array itself (and losing any tied-ness). Interpolating an array into a string automatically space-separates its elements.

Unlike a for loop, these operations only ask the array for its size once — so rather than printing an infinite sequence, they’ll print a completely arbitrary prefix of it. In the case above, spilling a fresh array will read one item; spilling the array after the example loop will read eleven items. So while a tied array works nicely with a for loop, it’s at odds with the most basic rules of Perl syntax.

Also, Perl’s list-based nature means it’s attracted a lot of list-processing utilities — but these naturally expect to receive a spilled list of arguments and cannot work with a lazy iterator.

I found multiple mentions of the List::Gen module while looking into this. I’d never heard of it before and I’ve never seen it used, but it tries to fill this gap (and makes use of array tying, among other things). It’s a bit weird, and its source code is extremely weird, and it took me twenty minutes to figure out how it was using <...> as a quoting construct.

(<...> in Perl does filename globbing, so it’s usually seen as <*.txt>. The same syntax is used for reading from a filehandle, which makes this confusing and ambiguous, so it’s generally discouraged in favor of the built-in glob function which does the same thing. Well, it turns out that <...> must just call glob() at Perl-level, because List::Gen manages to co-opt this syntax simply by exporting its own glob function. Perl is magical.)

Perl 6

Perl 6, a mad experiment to put literally every conceivable feature into one programming language, naturally has a more robust concept of iteration.

At first glance, many of the constructs are similar to those of Perl 5. The C-style for loop still exists for some reason, but has been disambiguated under the loop keyword.

1
2
3
4
5
6
7
8
loop (my $i = 1; $i <= 10; $i++) {
    ...
}

# More interestingly, loop can be used completely bare for an infinite loop
loop {
    ...
}

The for block has slightly different syntax and a couple new tricks.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
# Unlike in Perl 5, $value is automatically declared and scoped to the block,
# without needing an explicit 'my'
for @container -> $value {
    ...
}

for 1..10 -> $i {
    ...
}

# This doesn't iterate in pairs; it reads two items at a time from a flat list!
for 1..10 -> $a, $b {
    ...
}

Not apparent in the above code is that ranges are lazy in Perl 6, as in Python; the elements are computed on demand. In fact, Perl 6 supports a range like 1..Inf.

Loop variables are also aliases. By default they’re read-only, so this appears to work like Python… but Perl has always had a C-like language-level notion of “slots” that Python does not, and it becomes apparent if the loop variable is made read-write:

1
2
3
4
5
6
7
8
my @fruits = «apple orange pear»;
for @fruits -> $fruit is rw {
    # This is "apply method inplace", i.e. shorthand for:
    # $fruit = $fruit.uc;
    # Yes, you can do that.
    $fruit .= uc;
}
say @fruits;  # APPLE ORANGE PEAR

For iterating with indexes, there’s a curious idiom:

1
2
3
4
5
6
7
# ^Inf is shorthand for 0..Inf, read as "up to Inf".
# Z is the zip operator, which interleaves its arguments' elements into a
# single flat list.
# This makes use of the "two at a time" trick from above.
for ^Inf Z @array -> $index, $value {
    ...
}

Iterating hashes is somewhat simpler; hashes have methods, and the .kv method returns the keys and values. (It actually returns them in a flat list interleaved, which again uses “two at a time” syntax. If you only use a single loop variable, your loop iterations will alternate between a key and a value. Iterating a hash directly produces pairs, which are a first-class data type in Perl 6, but I can’t find any syntax for directly unpacking a pair within a loop header.)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
for %container.kv -> $key, value {
    ...
}

# No surprises here
for %container.keys -> $key {
    ...
}
for %container.values -> $value {
    ...
}

Perl 6 is very big on laziness, which is perhaps why it took fifteen years to see a release. It has the same iterable versus iterator split as Python. Given a container (iterable), ask for an iterator; given an iterator, repeatedly ask for new values. When the iterator is exhausted, it returns the IterationEnd sentinel. Exactly the same ideas. I’m not clear on the precise semantics of the for block and can’t find a simple reference, but they’re probably much like Python’s… plus a thousand special cases.

Generators, kinda

Perl 6 also has its own version of generators, though with a few extra twists. Curiously, generators are a block called gather, rather than a kind of function — this means that a one-off gather is easier to create, but a gather factory must be explicitly wrapped in a function. gather can even take a single expression rather than a block, so there’s no need for separate “generator expression” syntax as in Python.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
sub inclusive-range($start, $stop) {
    return gather {
        my $val = $start;
        while $val <= $stop {
            take $val;
            $val++;
        }
    };
}

# 6 7 8 9
for inclusive-range(6, 9) -> $n {
    ...
}

Unlike Python’s yield, Perl 6’s take is dynamically scoped — i.e., take can be used anywhere in the call stack, and it will apply to the most recent gather caller. That means arbitrary-depth coroutines, which seems like a big deal to me, but the documentation mentions it almost as an afterthought.

The documentation also says gather/take can generate values lazily, depending on context,” but neglects to clarify how context factors in. The code I wrote above turns out to be lazy, but this ambiguity inclines me to use the explicit lazy marker everywhere.

Ultimately it’s a pretty flexible feature, but has a few quirks that make it a bit clumsier to use as a straightforward generator. Given that the default behavior is an eagerly-evaluated block, I think the original intention was to avoid the slightly unsatisfying pattern of “push onto an array every iteration through a loop” — instead you can now do this:

1
2
3
4
5
6
my @results = gather {
    for @source-data -> $datum {
        next unless some-test($datum);
        take process($datum);
    }
};

Using a simple (syntax-highlighted!) take puts the focus on the value being taken, rather than the details of putting it where it wants to go and how it gets there. It’s an interesting idea and I’m surprised I’ve never seen it demonstrated this way.

With gather and some abuse of Perl’s exceptionally compactable syntax, I can write a much shorter version of the infinite Perl 5 iterator above.

1
2
3
4
5
6
7
8
my @powers-of-two = lazy gather take (state $n = 1) *= 2 for ^Inf;

# Binds to $_ by default
for @powers-of-two {
    # Method calls are on $_ by default
    .say;
    last if $_ > 1000;
}

It’s definitely shorter, I’ll give it that. Leaving off the lazy in this case causes an infinite loop as Perl tries to evaluate the entire list; using a $ instead of a @ produces a “Cannot .elems a lazy list” error; using $ without lazy prints a ...-terminated representation of the infinite list and then hangs forever. I don’t quite understand the semantics of stuffing a list into a scalar ($) variable in Perl 6, and to be honest the list/array semantics seem to be far more convoluted than Perl 5, so I have no idea what’s going on here. Perl 6 has a lot of fascinating toys that are very easy to use incorrectly.

Nuts and bolts

Iterables and iterators are encoded explicitly as the Iterable and Iterator roles. An Iterable has an .iterator method that should return an Iterator. An Iterator has a .pull-one method that returns the next value, or the IterationEnd sentinel when the iterator is exhausted. Both roles offer several other methods, but they have suitable default implementations.

inclusive-range might be transformed into a class thusly:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class InclusiveRangeIterator does Iterator {
    has $.range is required;
    has $!nextval = $!range.start;

    method pull-one() {
        if $!nextval > $!range.stop {
            return IterationEnd;
        }

        # Perl people would probably phrase this:
        # ++$!nextval
        # and they are wrong.
        my $val = $!nextval;
        $!nextval++;
        return $val;
    }
}

class InclusiveRange does Iterable {
    has $.start is required;
    has $.stop is required;

    # Don't even ask
    method new($start, $stop) {
        self.bless(:$start, :$stop);
    }

    method iterator() {
        InclusiveRangeIterator.new(range => self);
    }
}

# 6 7 8 9
for InclusiveRange.new(6, 9) -> $n {
    ...
}

Can we use gather to avoid the need for an extra class, just as in Python? We sure can! The only catch is that Perl 6 iterators don’t also pretend to be iterables (remember, in Python, iter(it) should produce it), so we need to explicitly return a gather block’s iterator.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class InclusiveRange does Iterable {
    has $.start is required;
    has $.stop is required;

    # Don't even ask
    method new($start, $stop) {
        self.bless(:$start, :$stop);
    }

    method iterator() {
        gather {
            my $val = $!start;
            while $val <= $!stop {
                take $val;
                $val++;
            }
        }.iterator;  # <- this is important
    }
}

For sequences, Perl 6 has the Seq type. Curiously, even an infinite lazy gather is still a Seq. Indexing and length are not part of Seq — both are implemented as separate methods.

Curiously, even though Perl 6 became much stricter overall, the indexing methods don’t seem to be part of a role; you only need define them, much like Python’s __dunder__ methods. In fact, the preceding examples, does Iterator isn’t necessary at all; the for block will blindly try to call an iterator method and doesn’t much care where it came from.

I’m sure there are plenty of cute tricks possible with Perl 6, but, er, I’ll leave those as an exercise for the reader.

Ruby

Ruby is a popular and well-disguised Perl variant, if Perl just went completely all-in on Smalltalk. It has no C-style for, but it does have an infinite loop block and a very Python-esque for:

1
2
3
for value in sequence do
    ...
end

Nobody uses this. No, really, the core language documentation outright says:

The for loop is rarely used in modern ruby programs.

Instead, you’ll probably see this:

1
2
3
sequence.each do |value|
    ...
end

It doesn’t look it, but this is completely backwards from everything seen so far. All of these other languages have used external iterators, where an object is repeatedly asked to produce values and calling code can do whatever it wants with them. Here, something very different is happening. The entire do ... end block acts as a closure whose argument is value; it’s passed to the each method, which calls it once for each value in the sequence. This is an internal iterator.

Pass a block to a function which can then call it a lot” is a built-in syntactic feature of Ruby, so these kinds of iterators are fairly common. The upside is that they look almost like a custom block, so they fit naturally with the language. The downside is that all of these block-accepting methods are implemented on Array, rather than as generic functions: bsearch, bsearch_index, collect, collect!, combination, count, cycle, delete, delete_if, drop_while, each, each_index, fetch, fill, find_index, index, keep_if, map, map!, permutation, product, reject, reject!, repeated_combination, repeated_permutation, reverse_each, rindex, select, select!, sort, sort!, sort_by!, take_while, uniq, uniq!, zip. Some of those, as well as a number of additional methods, are provided by the Enumerable mixin which can express them in terms of each. I suppose the other upside is that any given type can provide its own more efficient implementation of these methods, if it so desires.

I guess that huge list of methods answers most questions about how to iterate over indices or in reverse. The only bit missing is that .. range syntax exists in Ruby as well, and it produces Range objects which also have an each method. If you don’t care about each index, you can also use the cute 3.times method.

Ruby blocks are a fundamental part of the language and built right into the method-calling syntax. Even break is defined in terms of blocks, and it works with an argument!

1
2
3
4
# This just doesn't feel like it should work, but it does.  Prints 17.
# Braces are conventionally used for inline blocks, but do/end would work too.
primes = [2, 3, 5, 7, 11, 13, 17, 19]
puts primes.each { |p| break p if p > 16 }

each() doesn’t need to do anything special here; break will just cause its return value to be 17. Somehow. (Honestly, this is the sort of thing that makes me wary of Ruby; it seems so ad-hoc and raises so many questions. A language keyword that changes the return value of a different function? Does the inside of each() know about this or have any control over it? How does it actually work? Is there any opportunity for cleanup? I have no idea, and the documentation doesn’t seem to think this is worth commenting on.)

Using blocks

Anyway, with block-passing as a language feature, the “iterator protocol” is pretty straightforward: just write a method that takes a block.

1
2
3
4
5
def each
    for value in self do
        yield value
    end
end

Be careful! Though it’s handy for iteration, that yield is not the same as Python’s yield. Ruby’s yield calls the passed-in block — yields control to the caller — with the given value(s).

I pulled a dirty trick there, because I expressed each in terms of for. So how does for work? Well, ah, it just delegates to each. Oops!

How, then, do you write an iterator completely from scratch? The obvious way is to use yield repeatedly. That gives you something that looks rather a lot like Python, though it doesn’t actually pause execution.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class InclusiveRange
    # This gets you a variety of other iteration methods, all defined in
    # terms of each()
    include Enumerable

    def initialize(start, stop)
        @start = start
        @stop = stop
    end
    def each
        val = @start
        while val <= @stop do
            yield val
            val += 1
        end
    end
end

# 6 7 8 9
# A `for` loop would also work here
InclusiveRange.new(6, 9).each do |n|
    ...
end

Enumerators

Well, that’s nice for creating a whole collection type, but what if I want an ad-hoc custom iterator? Enter the Enumerator class, which allows you to create… ah, enumerators.

Note that the relationship between Enumerable and Enumerator is not the same as the relationship between “iterable” and “iterator”. Most importantly, neither is really an interface. Enumerable is a set of common iteration methods that any collection type may want to have, and it expects an each to exist. Enumerator is a generic collection type, and in fact mixes in Enumerable. Maybe I should just show you some code.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def inclusive_range(start, stop)
    Enumerator.new do |y|
        val = start
        while val <= stop do
            y.yield val
            val += 1
        end
    end
end

# 6 7 8 9
inclusive_range(6, 9).each do |n|
    puts n
end

Enumerator turns a block into a fully-fledged data stream. The block is free to do whatever it wants, and whenever it wants to emit a value, it calls y.yield value. The y argument is a “yielder” object, an opaque magic type; y.yield is a regular method call, unrelated to the yield keyword. (y << value is equivalent; << is Ruby’s “append” operator. And also, yes, bit shift.)

The amazing bit is that you can do this:

1
2
# 6
puts inclusive_range(6, 9).first

Enumerator has all of the Enumerable methods, one of which is first. So, that’s nice.

The really amazing bit is that if you stick some debugging code into the block passed to Enumerator.new, you’ll find that… the values are produced lazily. That call to first() doesn’t generate the full sequence and then discard everything after the first item; it only generates the first item, then stops.

(Beware! The values are produced lazily, but many Enumerable methods are eager. I’ll get back to this in a moment.)

Hang on, didn’t I say yield doesn’t pause execution? Didn’t I also say the above yield is just a method call, not the keyword?

I did! And I wasn’t lying. The really truly amazing bit, which I’ve seen shockingly little excitement about while researching this, is that under the hood, this is all using Fibers. Coroutines.

Enumerator.new takes a block and turns it into a coroutine. Every time something wants a value from the enumerator, it resumes the coroutine. The yielder object’s yield method then calls Fiber.yield() to pause the coroutine. It works just like Lua, but it’s designed to work with existing Ruby conventions, like the piles of internal iteration methods developers expect to find.

So Enumerator.new can produce Python-style generators, albeit in a slightly un-native-looking way. There’s also one other significant difference: an Enumerator can restart itself for each method called on it, simply by calling the block again. This code will print 6 three times:

1
2
3
4
ir = inclusive_range(6, 9)
puts ir.first
puts ir.first
puts ir.first

For something like an inclusive range object, that’s pretty nice. For something like a file, maybe not so nice. It also means you need to be sure to put your setup code inside the block passed to Enumerator.new, or funny things will happen when the block is restarted.

Something like generators

But wait, there’s more. Specifically, this common pattern, which pretty much lets you ignore Enumerator.new entirely.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def some_iterator_method
    # __method__ is the current method name.  block_given? is straightforward.
    return enum_for(__method__) unless block_given?

    # An extremely accurate simulation of a large list.
    (1..1000).each do |item|
        puts "having a look at #{item}"
        # Blocks are invisible to `yield`; this will yield to the block passed
        # to some_iterator_method.
        yield item if item.even?
    end
end

# having a look at 1
# having a look at 2
# 2
puts some_iterator_method.first

Okay, bear with me.

First, some_iterator_method() is called. It doesn’t have a block attached, so block_given? is false, and it returns enum_for(...), whatever that does. Then first() is called on the result, and that produces a single element and stops.

The above code has no magic yielder object. It uses the straightforward yield keyword. Why doesn’t it loop over the entire range from 1 to 1000?

Remember, Enumerator uses coroutines under the hood. One neat thing coroutines can do is pause code that doesn’t know it’s in a coroutine. Python’s generators pause themselves with yield, and the mere presence of yield turns a function into a generator; but in Lua or Ruby or any other language with coroutines, any function can pause at any time. You can even make a closure that pauses, then pass that closure to another function which calls it, without that function ever knowing anything happened.

(This arguably has some considerable downsides as well — it becomes difficult to know when or where your code might pause, which makes reasoning about the order of operations much harder. That’s why Python and some other languages opted to implement async IO with an await keyword — anyone reading the code knows that it can only pause where an await appears.)

(Also, I’m saying “pause” here instead of “yield” because Ruby has really complicated the hell out of this by already having a yield keyword that does something totally different, and naming its coroutine pause function yield.)

Anyway, that’s exactly what’s happening here. enum_for returns an Enumerator that wraps the whole method. (It doesn’t need to know self, because enum_for is actually a method inherited from Object, goodness gracious.) When the Enumerator needs some items, it calls the method a second time with its own block, running in a coroutine, just like a block passed to Enumerator.new. Eventually the method emits a value using the regular old yield keyword, and that value reaches the block created by Enumerator, and that block pauses the call stack. It doesn’t matter that Range.each is eager, because its iteration is still happening in code somewhere, and that code is part of a call stack in a coroutine, so it can be paused. Eventually the coroutine is no longer useful and gets thrown away, so the eager each call simply stops midway through its work, unaware that anything unusual ever happened.

In fact, despite being an Object method, enum_for isn’t special at all. It can be expressed in pure Ruby very easily:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def my_enum_for(receiver, method)
    # Enumerator.new creates a coroutine-as-iteration-source, as above.
    Enumerator.new do |y|
        # All it does is call the named method with a trivial block.  Every
        # time the method produces a value with the `yield` keyword, we pass it
        # along to the yielder object, which pauses the coroutine.
        # This is nothing more than a bridge between "yield" in the Ruby block
        # sense, and "yield" in the coroutine sense.
        receiver.send method do |value|
            y.yield value
        end
    end
end

So, that’s pretty neat. Incidentally, several built-in methods like Array.each and Enumerable.collect act like this, returning an Enumerator if called with no arguments.

Full laziness

I mentioned above that while an Enumerator fetches items lazily, many of the methods are eager. To clarify what I mean by that, consider:

1
2
3
4
5
inclusive_range(6, 9000).collect {
    |n|
    puts "considering #{n}"
    "a" * n
}.first(3)

collect() is one of those common Enumerable methods. You might know it by its other name, map(). Ruby is big on multiple names for the same thing: one that everyone uses in practice, and another that people who don’t use Ruby will actually recognize.

Even though this code ultimately only needs three items, and even though there’s all this coroutine machinery happening under the hood, this still evaluates the entire range. Why?

The problem is that collect() has always returned an array, and is generally expected to continue doing so. It has no way of knowing that it’s about to be fed into first. Rather than violate this API, Ruby added a new method, Enumerable.lazy. This stops after three items:

1
2
3
4
5
inclusive_range(6, 9000).lazy.collect {
    |n|
    puts "considering #{n}"
    "a" * n
}.first(3)

All this does is return an Enumerator::Lazy object, which has lazy implementations of various methods that would usually do a full iteration. Methods like first(3) are still “eager” (in the sense that they just return an array), since their results have a fixed finite size.

This seems a little clunky to me, since the end result is still an object with a collect method that doesn’t return an array. I suspect the real reason is just that Enumerator was added first; even though the coroutine support was already there, Enumerator::Lazy only came along later. Changing existing eager methods to be lazy can, ah, cause problems.

The only built-in type that seems to have interesting lazy behavior is Range, which can be infinite.

1
2
3
4
# Whoops, infinite loop.
(1..Float::INFINITY).select { |n| n.even? }.first(5)
# 2 4 6 8 10
(1..Float::INFINITY).lazy.select { |n| n.even? }.first(5)

A loose end

I think the only remaining piece of this puzzle is something I stumbled upon but can’t explain. Enumerator has a next method, which returns the next value or raises StopIteration.

Wow, that sounds awfully familiar.

But I can’t find anything in the language or standard library that uses this, with one single and boring exception: the loop construct. It catches StopIteration and exits the block.

1
2
3
4
5
6
enumerator = [1, 2, 3].each
loop do
    while true do
        puts enumerator.next
    end
end

On the fourth call, next() will be out of items, so it raises StopIteration. Removing the loop block makes this quite obvious.

That’s it. That’s the only use of it in the language, as far as I can tell. It seems almost… vestigial. It’s also a little weird, since it keeps the current iteration state inside the Enumerator, unlike any of its other methods. But it’s also the only form of external iteration that I know of in Ruby, and that’s handy to have sometimes.

And, uh, so on

I intended to foray into a few more languages, including some recent lower-level friends like C++/Rust/Swift, but this post somehow spiraled out of control and hit nine thousand words. No one has read this far.

Handily, it turns out that the above languages pretty much cover the basic ways of approaching iteration; if any of this made sense, other languages will probably seem pretty familiar.

  • C++’s iteration protocol(s) has existed for a long time in the form of ++it to advance an iterator and *it to read the current item, though this was usually written manually in a C-style for loop, and loops were generally terminated with an explicit endpoint.

    C++11 added the range-based for, which does basically the same stuff under the hood. Idiomatic C++ is inscrutible, but maybe you can make sense of this project which provides optionally-infinite iterable ranges.

  • Rust has an entire (extremely well-documented) iter module with numerous iterators and examples of how to create your own. The core of the Iterator trait is just a next method which returns None when exhausted. It also has a lot of handy Ruby-like chainable methods, so working directly with iterators is more common in Rust than in Python.

  • Swift also has (well-documented) simple next-based iterators, which return nil when exhausted, effectively the same API as Rust.

I could probably keep finding more subsequent languages indefinitely, so I’m gonna take a break from this now.

CodePipeline Update – Build Continuous Delivery Workflows for CloudFormation Stacks

Post Syndicated from Jeff Barr original https://aws.amazon.com/blogs/aws/codepipeline-update-build-continuous-delivery-workflows-for-cloudformation-stacks/

When I begin to write about a new way for you to become more productive by using two AWS services together, I think about a 1980’s TV commercial for Reese’s Peanut Butter Cups! The intersection of two useful services or two delicious flavors creates a new one that is even better.

Today’s chocolate / peanut butter intersection takes place where AWS CodePipeline meets AWS CloudFormation. You can now use CodePipeline to build a continuous delivery pipeline for CloudFormation stacks. When you practice continuous delivery, each code change is automatically built, tested, and prepared for release to production. In most cases, the continuous delivery release process includes a combination of manual and automatic approval steps. For example, code that successfully passes through a series of automated tests can be routed to a development or product manager for final review and approval before it is pushed to production.

This important combination of features allows you to use the infrastructure as code model while gaining all of the advantages of continuous delivery. Each time you change a CloudFormation template, CodePipeline can initiate a workflow that will build a test stack, test it, await manual approval, and then push the changes to production.The workflow can create and manipulate stacks in many different ways:

As you will soon see, the workflow can take advantage of advanced CloudFormation features such as the ability to generate and then apply change sets (read New – Change Sets for AWS CloudFormation to learn more) to an operational stack.

The Setup
In order to learn more about this feature, I used a CloudFormation template to set up my continuous delivery pipeline (this is yet another example of infrastructure as code). This template (available here and described in detail here) sets up a full-featured pipeline. When I use the template to create my pipeline, I specify the name of an S3 bucket and the name of a source file:

The SourceS3Key points to a ZIP file that is enabled for S3 versioning. This file contains the CloudFormation template (I am using the WordPress Single Instance example) that will be deployed via the pipeline that I am about to create. It can also contain other deployment artifacts such as configuration or parameter files; here’s what mine looks like:

The entire continuous delivery pipeline is ready just a few seconds after I click on Create Stack. Here’s what it looks like:

The Action
At this point I have used CloudFormation to set up my pipeline. With the stage set (so to speak), now I can show you how this pipeline makes use of the new CloudFormation actions.

Let’s focus on the second stage, TestStage. Triggered by the first stage, this stage uses CloudFormation to create a test stack:

The stack is created using parameter values from the test-stack-configuration.json file in my ZIP. Since you can use different configuration files for each CloudFormation action, you can use the same template for testing and production.

After the stack is up and running, the ApproveTestStack step is used to await manual approval (it says “Waiting for approval above.”). Playing the role of the dev manager, I verify that the test stack behaves and performs as expected, and then approve it:

After approval, the DeleteTestStack step deletes the test stack.

Now we are just about ready to deploy to production. ProdStage creates a CloudFormation change set and then submits it for manual approval. This stage uses the parameter values from the prod-stack-configuration.json file in my ZIP. I can use the parameters to launch a modestly sized test environment on a small EC2 instance and a large production environment from the same template.

Now I’m playing the role of the big boss, responsible for keeping the production site up and running. I review the change set in order to make sure that I understand what will happen when I deploy to production. This is the first time that I am running the pipeline, so the change set indicates that an EC2 instance and a security group will be created:

And then I approve it:

With the change set approved, it is applied to the existing production stack in the ExecuteChangeSet step. Applying the change to an  existing stack keeps existing resources in play where possible and avoids a wholesale restart of the application. This is generally more efficient and less disruptive than replacing the entire stack. It keeps in-memory caches warmed up and avoids possible bursts of cold-start activity.

Implementing a Change
Let’s say that I decide to support HTTPS. In order to do this, I need to add port 443 to my application’s security group. I simply edit the CloudFormation template, put it into a fresh ZIP, and upload it to S3. Here’s what I added to my template:

      - CidrIp: 0.0.0.0/0
        FromPort: '443'
        IpProtocol: tcp
        ToPort: '443'

Then I return to the Console and see that CodePipeline has already detected the change and set the pipeline in to motion:

The pipeline runs again, I approve the test stack, and then inspect the change set, confirming that it will simply modify an existing security group:

One quick note before I go. The CloudFormation template for the pipeline creates an IAM role and uses it to create the test and deployment stacks (this is a new feature; read about the AWS CloudFormation Service Role to learn more). For best results, you should delete the stacks before you delete the pipeline. Otherwise, you’ll need to re-create the role in order to delete the stacks.

There’s More
I’m just about out of space and time, but I’ll briefly summarize a couple of other aspects of this new capability.

Parameter Overrides – When you define a CloudFormation action, you may need to exercise additional control over the parameter values that are defined for the template. You can do this by opening up the Advanced pane and entering any desired parameter overrides:

Artifact References – In some situations you may find that you need to reference an attribute of an artifact that was produced by an earlier stage of the pipeline. For example, suppose that an early stage of your pipeline copies a Lambda function to an S3 bucket and calls the resulting artifact LambdaFunctionSource. Here’s how you would retrieve the bucket name and the object key from the attribute using a parameter override:

{
  "BucketName" : { "Fn::GetArtifactAtt" : ["LambdaFunctionSource", "BucketName"]},
  "ObjectKey" : { "Fn::GetArtifactAtt" : ["LambdaFunctionSource", "ObjectKey"]}
}

Access to JSON Parameter – You can use the new Fn::GetParam function to retrieve a value from a JSON-formatted file that is included in an artifact.

Note that Fn:GetArtifactAtt and Fn::GetParam are designed to be used within the parameter overrides.

S3 Bucket Versioning – The first step of my pipeline (the Source action) refers to an object in an S3 bucket. By enabling S3 versioning for the object, I simply upload a new version of my template after each change:

If I am using S3 as my source, I must use versioning (uploading a new object over the existing one is not supported). I can also use AWS CodeCommit or a GitHub repo as my source.

Create Pipeline Wizard
I started out this blog post by using a CloudFormation template to create my pipeline. I can also click on Create pipeline in the console and build my initial pipeline (with source, build, and beta deployment stages) using a wizard. The wizard now allows me to select CloudFormation as my deployment provider. I can create or update a stack or a change set in the beta deployment stage:

Available Now
This new feature is available now and you can start using it today. To learn more, check out the CodePipeline Documentation.


Jeff;

 

In Case You Missed These: AWS Security Blog Posts from June, July, and August

Post Syndicated from Craig Liebendorfer original https://blogs.aws.amazon.com/security/post/Tx3KVD6T490MM47/In-Case-You-Missed-These-AWS-Security-Blog-Posts-from-June-July-and-August

In case you missed any AWS Security Blog posts from June, July, and August, they are summarized and linked to below. The posts are shown in reverse chronological order (most recent first), and the subject matter ranges from a tagging limit increase to recording SSH sessions established through a bastion host.

August

August 16: Updated Whitepaper Available: AWS Best Practices for DDoS Resiliency
We recently released the 2016 version of the AWS Best Practices for DDoS Resiliency Whitepaper, which can be helpful if you have public-facing endpoints that might attract unwanted distributed denial of service (DDoS) activity.

August 15: Now Organize Your AWS Resources by Using up to 50 Tags per Resource
Tagging AWS resources simplifies the way you organize and discover resources, allocate costs, and control resource access across services. Many of you have told us that as the number of applications, teams, and projects running on AWS increases, you need more than 10 tags per resource. Based on this feedback, we now support up to 50 tags per resource. You do not need to take additional action—you can begin applying as many as 50 tags per resource today.

August 11: New! Import Your Own Keys into AWS Key Management Service
Today, we are happy to announce the launch of the new import key feature that enables you to import keys from your own key management infrastructure (KMI) into AWS Key Management Service (KMS). After you have exported keys from your existing systems and imported them into KMS, you can use them in all KMS-integrated AWS services and custom applications.

August 2: Customer Update: Amazon Web Services and the EU-US Privacy Shield
Recently, the European Commission and the US Government agreed on a new framework called the EU-US Privacy Shield, and on July 12, the European Commission formally adopted it. AWS welcomes this new framework for transatlantic data flow. As the EU-US Privacy Shield replaces Safe Harbor, we understand many of our customers have questions about what this means for them. The security of our customers’ data is our number one priority, so I wanted to take a few moments to explain what this all means.

August 2: How to Remove Single Points of Failure by Using a High-Availability Partition Group in Your AWS CloudHSM Environment
In this post, I will walk you through steps to remove single points of failure in your AWS CloudHSM environment by setting up a high-availability (HA) partition group. Single points of failure occur when a single CloudHSM device fails in a non-HA configuration, which can result in the permanent loss of keys and data. The HA partition group, however, allows for one or more CloudHSM devices to fail, while still keeping your environment operational.

July

July 28: Enable Your Federated Users to Work in the AWS Management Console for up to 12 Hours
AWS Identity and Access Management (IAM) supports identity federation, which enables external identities, such as users in your corporate directory, to sign in to the AWS Management Console via single sign-on (SSO). Now with a small configuration change, your AWS administrators can allow your federated users to work in the AWS Management Console for up to 12 hours, instead of having to reauthenticate every 60 minutes. In addition, administrators can now revoke active federated user sessions. In this blog post, I will show how to configure the console session duration for two common federation use cases: using Security Assertion Markup Language (SAML) 2.0 and using a custom federation broker that leverages the sts:AssumeRole* APIs (see this downloadable sample of a federation proxy). I will wrap up this post with a walkthrough of the new session revocation process.

July 28: Amazon Cognito Your User Pools is Now Generally Available
Amazon Cognito makes it easy for developers to add sign-up, sign-in, and enhanced security functionality to mobile and web apps. With Amazon Cognito Your User Pools, you get a simple, fully managed service for creating and maintaining your own user directory that can scale to hundreds of millions of users.

July 27: How to Audit Cross-Account Roles Using AWS CloudTrail and Amazon CloudWatch Events
In this blog post, I will walk through the process of auditing access across AWS accounts by a cross-account role. This process links API calls that assume a role in one account to resource-related API calls in a different account. To develop this process, I will use AWS CloudTrail, Amazon CloudWatch Events, and AWS Lambda functions. When complete, the process will provide a full audit chain from end user to resource access across separate AWS accounts.

July 25: AWS Becomes First Cloud Service Provider to Adopt New PCI DSS 3.2
We are happy to announce the availability of the Amazon Web Services PCI DSS 3.2 Compliance Package for the 2016/2017 cycle. AWS is the first cloud service provider (CSP) to successfully complete the assessment against the newly released PCI Data Security Standard (PCI DSS) version 3.2, 18 months in advance of the mandatory February 1, 2018, deadline. The AWS Attestation of Compliance (AOC), available upon request, now features 26 PCI DSS certified services, including the latest additions of Amazon EC2 Container Service (ECS), AWS Config, and AWS WAF (a web application firewall). We at AWS are committed to this international information security and compliance program, and adopting the new standard as early as possible once again demonstrates our commitment to information security as our highest priority. Our customers (and customers of our customers) can operate confidently as they store and process credit card information (and any other sensitive data) in the cloud knowing that AWS products and services are tested against the latest and most mature set of PCI compliance requirements.

July 20: New AWS Compute Blog Post: Help Secure Container-Enabled Applications with IAM Roles for ECS Tasks
Amazon EC2 Container Service (ECS) now allows you to specify an IAM role that can be used by the containers in an ECS task, as a new AWS Compute Blog post explains. 

July 14: New Whitepaper Now Available: The Security Perspective of the AWS Cloud Adoption Framework
Today, AWS released the Security Perspective of the AWS Cloud Adoption Framework (AWS CAF). The AWS CAF provides a framework to help you structure and plan your cloud adoption journey, and build a comprehensive approach to cloud computing throughout the IT lifecycle. The framework provides seven specific areas of focus or Perspectives: business, platform, maturity, people, process, operations, and security.

July 14: New Amazon Inspector Blog Post on the AWS Blog
On the AWS Blog yesterday, Jeff Barr published a new security-related blog post written by AWS Principal Security Engineer Eric Fitzgerald. Here’s the beginning of the post, which is entitled, Scale Your Security Vulnerability Testing with Amazon Inspector:

July 12: How to Use AWS CloudFormation to Automate Your AWS WAF Configuration with Example Rules and Match Conditions
We recently announced AWS CloudFormation support for all current features of AWS WAF. This enables you to leverage CloudFormation templates to configure, customize, and test AWS WAF settings across all your web applications. Using CloudFormation templates can help you reduce the time required to configure AWS WAF. In this blog post, I will show you how to use CloudFormation to automate your AWS WAF configuration with example rules and match conditions.

July 11: How to Restrict Amazon S3 Bucket Access to a Specific IAM Role
In this blog post, I show how you can restrict S3 bucket access to a specific IAM role or user within an account using Conditions instead of with the NotPrincipal element. Even if another user in the same account has an Admin policy or a policy with s3:*, they will be denied if they are not explicitly listed. You can use this approach, for example, to configure a bucket for access by instances within an Auto Scaling group. You can also use this approach to limit access to a bucket with a high-level security need.

July 7: How to Use SAML to Automatically Direct Federated Users to a Specific AWS Management Console Page
In this blog post, I will show you how to create a deep link for federated users via the SAML 2.0 RelayState parameter in Active Directory Federation Services (AD FS). By using a deep link, your users will go directly to the specified console page without additional navigation.

July 6: How to Prevent Uploads of Unencrypted Objects to Amazon S3
In this blog post, I will show you how to create an S3 bucket policy that prevents users from uploading unencrypted objects, unless they are using server-side encryption with S3–managed encryption keys (SSE-S3) or server-side encryption with AWS KMS–managed keys (SSE-KMS).

June

June 30: The Top 20 AWS IAM Documentation Pages so Far This Year
The following 20 pages have been the most viewed AWS Identity and Access Management (IAM) documentation pages so far this year. I have included a brief description with each link to give you a clearer idea of what each page covers. Use this list to see what other people have been viewing and perhaps to pique your own interest about a topic you’ve been meaning to research. 

June 29: The Most Viewed AWS Security Blog Posts so Far in 2016
The following 10 posts are the most viewed AWS Security Blog posts that we published during the first six months of this year. You can use this list as a guide to catch up on your blog reading or even read a post again that you found particularly useful.

June 25: AWS Earns Department of Defense Impact Level 4 Provisional Authorization
I am pleased to share that, for our AWS GovCloud (US) Region, AWS has received a Defense Information Systems Agency (DISA) Provisional Authorization (PA) at Impact Level 4 (IL4). This will allow Department of Defense (DoD) agencies to use the AWS Cloud for production workloads with export-controlled data, privacy information, and protected health information as well as other controlled unclassified information. This new authorization continues to demonstrate our advanced work in the public sector space; you might recall AWS was the first cloud service provider to obtain an Impact Level 4 PA in August 2014, paving the way for DoD pilot workloads and applications in the cloud. Additionally, we recently achieved a FedRAMP High provisional Authorization to Operate (P-ATO) from the Joint Authorization Board (JAB), also for AWS GovCloud (US), and today’s announcement allows DoD mission owners to continue to leverage AWS for critical production applications.

June 23: AWS re:Invent 2016 Registration Is Now Open
Register now for the fifth annual AWS re:Invent, the largest gathering of the global cloud computing community. Join us in Las Vegas for opportunities to connect, collaborate, and learn about AWS solutions. This year we are offering all-new technical deep-dives on topics such as security, IoT, serverless computing, and containers. We are also delivering more than 400 sessions, more hands-on labs, bootcamps, and opportunities for one-on-one engagements with AWS experts.

June 23: AWS Achieves FedRAMP High JAB Provisional Authorization
We are pleased to announce that AWS has received a FedRAMP High JAB Provisional Authorization to Operate (P-ATO) from the Joint Authorization Board (JAB) for the AWS GovCloud (US) Region. The new Federal Risk and Authorization Management Program (FedRAMP) High JAB Provisional Authorization is mapped to more than 400 National Institute of Standards and Technology (NIST) security controls. This P-ATO recognizes AWS GovCloud (US) as a secure environment on which to run highly sensitive government workloads, including Personally Identifiable Information (PII), sensitive patient records, financial data, law enforcement data, and other Controlled Unclassified Information (CUI).

June 22: AWS IAM Service Last Accessed Data Now Available for South America (Sao Paulo) and Asia Pacific (Seoul) Regions
In December, AWS IAM released service last accessed data, which helps you identify overly permissive policies attached to an IAM entity (a user, group, or role). Today, we have extended service last accessed data to support two additional regions: South America (Sao Paulo) and Asia Pacific (Seoul). With this release, you can now view the date when an IAM entity last accessed an AWS service in these two regions. You can use this information to identify unnecessary permissions and update policies to remove access to unused services.

June 20: New Twitter Handle Now Live: @AWSSecurityInfo
Today, we launched a new Twitter handle: @AWSSecurityInfo. The purpose of this new handle is to share security bulletins, security whitepapers, compliance news and information, and other AWS security-related and compliance-related information. The scope of this handle is broader than that of @AWSIdentity, which focuses primarily on Security Blog posts. However, feel free to follow both handles!

June 15: Announcing Two New AWS Quick Start Reference Deployments for Compliance
As part of the Professional Services Enterprise Accelerator – Compliance program, AWS has published two new Quick Start reference deployments to assist federal government customers and others who need to meet National Institute of Standards and Technology (NIST) SP 800-53 (Revision 4) security control requirements, including those at the high-impact level. The new Quick Starts are AWS Enterprise Accelerator – Compliance: NIST-based Assurance Frameworks and AWS Enterprise Accelerator – Compliance: Standardized Architecture for NIST High-Impact Controls Featuring Trend Micro Deep Security. These Quick Starts address many of the NIST controls at the infrastructure layer. Furthermore, for systems categorized as high impact, AWS has worked with Trend Micro to incorporate its Deep Security product into a Quick Start deployment in order to address many additional high-impact controls at the workload layer (app, data, and operating system). In addition, we have worked with Telos Corporation to populate security control implementation details for each of these Quick Starts into the Xacta product suite for customers who rely upon that suite for governance, risk, and compliance workflows.

June 14: Now Available: Get Even More Details from Service Last Accessed Data
In December, AWS IAM released service last accessed data, which shows the time when an IAM entity (a user, group, or role) last accessed an AWS service. This provided a powerful tool to help you grant least privilege permissions. Starting today, it’s easier to identify where you can reduce permissions based on additional service last accessed data.

June 14: How to Record SSH Sessions Established Through a Bastion Host
A bastion host is a server whose purpose is to provide access to a private network from an external network, such as the Internet. Because of its exposure to potential attack, a bastion host must minimize the chances of penetration. For example, you can use a bastion host to mitigate the risk of allowing SSH connections from an external network to the Linux instances launched in a private subnet of your Amazon Virtual Private Cloud (VPC). In this blog post, I will show you how to leverage a bastion host to record all SSH sessions established with Linux instances. Recording SSH sessions enables auditing and can help in your efforts to comply with regulatory requirements.

June 14: AWS Granted Authority to Operate for Department of Commerce and NOAA
AWS already has a number of federal agencies onboarded to the cloud, including the Department of Energy, The Department of the Interior, and NASA. Today we are pleased to announce the addition of two more ATOs (authority to operate) for the Department of Commerce (DOC) and the National Oceanic and Atmospheric Administration (NOAA). Specifically, the DOC will be utilizing AWS for their Commerce Data Service, and NOAA will be leveraging the cloud for their “Big Data Project." According to NOAA, the goal of the Big Data Project is to “create a sustainable, market-driven ecosystem that lowers the cost barrier to data publication. This project will create a new economic space for growth and job creation while providing the public far greater access to the data created with its tax dollars.”

June 2: How to Set Up DNS Resolution Between On-Premises Networks and AWS by Using Unbound
In previous AWS Security Blog posts, Drew Dennis covered two options for establishing DNS connectivity between your on-premises networks and your Amazon Virtual Private Cloud (Amazon VPC) environments. His first post explained how to use Simple AD to forward DNS requests originating from on-premises networks to an Amazon Route 53 private hosted zone. His second post showed how you can use Microsoft Active Directory (also provisioned with AWS Directory Service) to provide the same DNS resolution with some additional forwarding capabilities. In this post, I will explain how you can set up DNS resolution between your on-premises DNS with Amazon VPC by using Unbound, an open-source, recursive DNS resolver. This solution is not a managed solution like Microsoft AD and Simple AD, but it does provide the ability to route DNS requests between on-premises environments and an Amazon VPC–provided DNS.

June 1: How to Manage Secrets for Amazon EC2 Container Service–Based Applications by Using Amazon S3 and Docker
In this blog post, I will show you how to store secrets on Amazon S3, and use AWS IAM roles to grant access to those stored secrets using an example WordPress application deployed as a Docker image using ECS. Using IAM roles means that developers and operations staff do not have the credentials to access secrets. Only the application and staff who are responsible for managing the secrets can access them. The deployment model for ECS ensures that tasks are run on dedicated EC2 instances for the same AWS account and are not shared between customers, which gives sufficient isolation between different container environments.

If you have comments  about any of these posts, please add your comments in the "Comments" section of the appropriate post. If you have questions about or issues implementing the solutions in any of these posts, please start a new thread on the AWS IAM forum.

– Craig

In Case You Missed These: AWS Security Blog Posts from June, July, and August

Post Syndicated from Craig Liebendorfer original https://aws.amazon.com/blogs/security/in-case-you-missed-these-aws-security-blog-posts-from-june-july-and-august/

In case you missed any AWS Security Blog posts from June, July, and August, they are summarized and linked to below. The posts are shown in reverse chronological order (most recent first), and the subject matter ranges from a tagging limit increase to recording SSH sessions established through a bastion host.

August

August 16: Updated Whitepaper Available: AWS Best Practices for DDoS Resiliency
We recently released the 2016 version of the AWS Best Practices for DDoS Resiliency Whitepaper, which can be helpful if you have public-facing endpoints that might attract unwanted distributed denial of service (DDoS) activity.

August 15: Now Organize Your AWS Resources by Using up to 50 Tags per Resource
Tagging AWS resources simplifies the way you organize and discover resources, allocate costs, and control resource access across services. Many of you have told us that as the number of applications, teams, and projects running on AWS increases, you need more than 10 tags per resource. Based on this feedback, we now support up to 50 tags per resource. You do not need to take additional action—you can begin applying as many as 50 tags per resource today.

August 11: New! Import Your Own Keys into AWS Key Management Service
Today, we are happy to announce the launch of the new import key feature that enables you to import keys from your own key management infrastructure (KMI) into AWS Key Management Service (KMS). After you have exported keys from your existing systems and imported them into KMS, you can use them in all KMS-integrated AWS services and custom applications.

August 2: Customer Update: Amazon Web Services and the EU-US Privacy Shield
Recently, the European Commission and the US Government agreed on a new framework called the EU-US Privacy Shield, and on July 12, the European Commission formally adopted it. AWS welcomes this new framework for transatlantic data flow. As the EU-US Privacy Shield replaces Safe Harbor, we understand many of our customers have questions about what this means for them. The security of our customers’ data is our number one priority, so I wanted to take a few moments to explain what this all means.

August 2: How to Remove Single Points of Failure by Using a High-Availability Partition Group in Your AWS CloudHSM Environment
In this post, I will walk you through steps to remove single points of failure in your AWS CloudHSM environment by setting up a high-availability (HA) partition group. Single points of failure occur when a single CloudHSM device fails in a non-HA configuration, which can result in the permanent loss of keys and data. The HA partition group, however, allows for one or more CloudHSM devices to fail, while still keeping your environment operational.

July

July 28: Enable Your Federated Users to Work in the AWS Management Console for up to 12 Hours
AWS Identity and Access Management (IAM) supports identity federation, which enables external identities, such as users in your corporate directory, to sign in to the AWS Management Console via single sign-on (SSO). Now with a small configuration change, your AWS administrators can allow your federated users to work in the AWS Management Console for up to 12 hours, instead of having to reauthenticate every 60 minutes. In addition, administrators can now revoke active federated user sessions. In this blog post, I will show how to configure the console session duration for two common federation use cases: using Security Assertion Markup Language (SAML) 2.0 and using a custom federation broker that leverages the sts:AssumeRole* APIs (see this downloadable sample of a federation proxy). I will wrap up this post with a walkthrough of the new session revocation process.

July 28: Amazon Cognito Your User Pools is Now Generally Available
Amazon Cognito makes it easy for developers to add sign-up, sign-in, and enhanced security functionality to mobile and web apps. With Amazon Cognito Your User Pools, you get a simple, fully managed service for creating and maintaining your own user directory that can scale to hundreds of millions of users.

July 27: How to Audit Cross-Account Roles Using AWS CloudTrail and Amazon CloudWatch Events
In this blog post, I will walk through the process of auditing access across AWS accounts by a cross-account role. This process links API calls that assume a role in one account to resource-related API calls in a different account. To develop this process, I will use AWS CloudTrail, Amazon CloudWatch Events, and AWS Lambda functions. When complete, the process will provide a full audit chain from end user to resource access across separate AWS accounts.

July 25: AWS Becomes First Cloud Service Provider to Adopt New PCI DSS 3.2
We are happy to announce the availability of the Amazon Web Services PCI DSS 3.2 Compliance Package for the 2016/2017 cycle. AWS is the first cloud service provider (CSP) to successfully complete the assessment against the newly released PCI Data Security Standard (PCI DSS) version 3.2, 18 months in advance of the mandatory February 1, 2018, deadline. The AWS Attestation of Compliance (AOC), available upon request, now features 26 PCI DSS certified services, including the latest additions of Amazon EC2 Container Service (ECS), AWS Config, and AWS WAF (a web application firewall). We at AWS are committed to this international information security and compliance program, and adopting the new standard as early as possible once again demonstrates our commitment to information security as our highest priority. Our customers (and customers of our customers) can operate confidently as they store and process credit card information (and any other sensitive data) in the cloud knowing that AWS products and services are tested against the latest and most mature set of PCI compliance requirements.

July 20: New AWS Compute Blog Post: Help Secure Container-Enabled Applications with IAM Roles for ECS Tasks
Amazon EC2 Container Service (ECS) now allows you to specify an IAM role that can be used by the containers in an ECS task, as a new AWS Compute Blog post explains.

July 14: New Whitepaper Now Available: The Security Perspective of the AWS Cloud Adoption Framework
Today, AWS released the Security Perspective of the AWS Cloud Adoption Framework (AWS CAF). The AWS CAF provides a framework to help you structure and plan your cloud adoption journey, and build a comprehensive approach to cloud computing throughout the IT lifecycle. The framework provides seven specific areas of focus or Perspectives: business, platform, maturity, people, process, operations, and security.

July 14: New Amazon Inspector Blog Post on the AWS Blog
On the AWS Blog yesterday, Jeff Barr published a new security-related blog post written by AWS Principal Security Engineer Eric Fitzgerald. Here’s the beginning of the post, which is entitled, Scale Your Security Vulnerability Testing with Amazon Inspector:

July 12: How to Use AWS CloudFormation to Automate Your AWS WAF Configuration with Example Rules and Match Conditions
We recently announced AWS CloudFormation support for all current features of AWS WAF. This enables you to leverage CloudFormation templates to configure, customize, and test AWS WAF settings across all your web applications. Using CloudFormation templates can help you reduce the time required to configure AWS WAF. In this blog post, I will show you how to use CloudFormation to automate your AWS WAF configuration with example rules and match conditions.

July 11: How to Restrict Amazon S3 Bucket Access to a Specific IAM Role
In this blog post, I show how you can restrict S3 bucket access to a specific IAM role or user within an account using Conditions instead of with the NotPrincipal element. Even if another user in the same account has an Admin policy or a policy with s3:*, they will be denied if they are not explicitly listed. You can use this approach, for example, to configure a bucket for access by instances within an Auto Scaling group. You can also use this approach to limit access to a bucket with a high-level security need.

July 7: How to Use SAML to Automatically Direct Federated Users to a Specific AWS Management Console Page
In this blog post, I will show you how to create a deep link for federated users via the SAML 2.0 RelayState parameter in Active Directory Federation Services (AD FS). By using a deep link, your users will go directly to the specified console page without additional navigation.

July 6: How to Prevent Uploads of Unencrypted Objects to Amazon S3
In this blog post, I will show you how to create an S3 bucket policy that prevents users from uploading unencrypted objects, unless they are using server-side encryption with S3–managed encryption keys (SSE-S3) or server-side encryption with AWS KMS–managed keys (SSE-KMS).

June

June 30: The Top 20 AWS IAM Documentation Pages so Far This Year
The following 20 pages have been the most viewed AWS Identity and Access Management (IAM) documentation pages so far this year. I have included a brief description with each link to give you a clearer idea of what each page covers. Use this list to see what other people have been viewing and perhaps to pique your own interest about a topic you’ve been meaning to research.

June 29: The Most Viewed AWS Security Blog Posts so Far in 2016
The following 10 posts are the most viewed AWS Security Blog posts that we published during the first six months of this year. You can use this list as a guide to catch up on your blog reading or even read a post again that you found particularly useful.

June 25: AWS Earns Department of Defense Impact Level 4 Provisional Authorization
I am pleased to share that, for our AWS GovCloud (US) Region, AWS has received a Defense Information Systems Agency (DISA) Provisional Authorization (PA) at Impact Level 4 (IL4). This will allow Department of Defense (DoD) agencies to use the AWS Cloud for production workloads with export-controlled data, privacy information, and protected health information as well as other controlled unclassified information. This new authorization continues to demonstrate our advanced work in the public sector space; you might recall AWS was the first cloud service provider to obtain an Impact Level 4 PA in August 2014, paving the way for DoD pilot workloads and applications in the cloud. Additionally, we recently achieved a FedRAMP High provisional Authorization to Operate (P-ATO) from the Joint Authorization Board (JAB), also for AWS GovCloud (US), and today’s announcement allows DoD mission owners to continue to leverage AWS for critical production applications.

June 23: AWS re:Invent 2016 Registration Is Now Open
Register now for the fifth annual AWS re:Invent, the largest gathering of the global cloud computing community. Join us in Las Vegas for opportunities to connect, collaborate, and learn about AWS solutions. This year we are offering all-new technical deep-dives on topics such as security, IoT, serverless computing, and containers. We are also delivering more than 400 sessions, more hands-on labs, bootcamps, and opportunities for one-on-one engagements with AWS experts.

June 23: AWS Achieves FedRAMP High JAB Provisional Authorization
We are pleased to announce that AWS has received a FedRAMP High JAB Provisional Authorization to Operate (P-ATO) from the Joint Authorization Board (JAB) for the AWS GovCloud (US) Region. The new Federal Risk and Authorization Management Program (FedRAMP) High JAB Provisional Authorization is mapped to more than 400 National Institute of Standards and Technology (NIST) security controls. This P-ATO recognizes AWS GovCloud (US) as a secure environment on which to run highly sensitive government workloads, including Personally Identifiable Information (PII), sensitive patient records, financial data, law enforcement data, and other Controlled Unclassified Information (CUI).

June 22: AWS IAM Service Last Accessed Data Now Available for South America (Sao Paulo) and Asia Pacific (Seoul) Regions
In December, AWS IAM released service last accessed data, which helps you identify overly permissive policies attached to an IAM entity (a user, group, or role). Today, we have extended service last accessed data to support two additional regions: South America (Sao Paulo) and Asia Pacific (Seoul). With this release, you can now view the date when an IAM entity last accessed an AWS service in these two regions. You can use this information to identify unnecessary permissions and update policies to remove access to unused services.

June 20: New Twitter Handle Now Live: @AWSSecurityInfo
Today, we launched a new Twitter handle: @AWSSecurityInfo. The purpose of this new handle is to share security bulletins, security whitepapers, compliance news and information, and other AWS security-related and compliance-related information. The scope of this handle is broader than that of @AWSIdentity, which focuses primarily on Security Blog posts. However, feel free to follow both handles!

June 15: Announcing Two New AWS Quick Start Reference Deployments for Compliance
As part of the Professional Services Enterprise Accelerator – Compliance program, AWS has published two new Quick Start reference deployments to assist federal government customers and others who need to meet National Institute of Standards and Technology (NIST) SP 800-53 (Revision 4) security control requirements, including those at the high-impact level. The new Quick Starts are AWS Enterprise Accelerator – Compliance: NIST-based Assurance Frameworks and AWS Enterprise Accelerator – Compliance: Standardized Architecture for NIST High-Impact Controls Featuring Trend Micro Deep Security. These Quick Starts address many of the NIST controls at the infrastructure layer. Furthermore, for systems categorized as high impact, AWS has worked with Trend Micro to incorporate its Deep Security product into a Quick Start deployment in order to address many additional high-impact controls at the workload layer (app, data, and operating system). In addition, we have worked with Telos Corporation to populate security control implementation details for each of these Quick Starts into the Xacta product suite for customers who rely upon that suite for governance, risk, and compliance workflows.

June 14: Now Available: Get Even More Details from Service Last Accessed Data
In December, AWS IAM released service last accessed data, which shows the time when an IAM entity (a user, group, or role) last accessed an AWS service. This provided a powerful tool to help you grant least privilege permissions. Starting today, it’s easier to identify where you can reduce permissions based on additional service last accessed data.

June 14: How to Record SSH Sessions Established Through a Bastion Host
A bastion host is a server whose purpose is to provide access to a private network from an external network, such as the Internet. Because of its exposure to potential attack, a bastion host must minimize the chances of penetration. For example, you can use a bastion host to mitigate the risk of allowing SSH connections from an external network to the Linux instances launched in a private subnet of your Amazon Virtual Private Cloud (VPC). In this blog post, I will show you how to leverage a bastion host to record all SSH sessions established with Linux instances. Recording SSH sessions enables auditing and can help in your efforts to comply with regulatory requirements.

June 14: AWS Granted Authority to Operate for Department of Commerce and NOAA
AWS already has a number of federal agencies onboarded to the cloud, including the Department of Energy, The Department of the Interior, and NASA. Today we are pleased to announce the addition of two more ATOs (authority to operate) for the Department of Commerce (DOC) and the National Oceanic and Atmospheric Administration (NOAA). Specifically, the DOC will be utilizing AWS for their Commerce Data Service, and NOAA will be leveraging the cloud for their “Big Data Project.” According to NOAA, the goal of the Big Data Project is to “create a sustainable, market-driven ecosystem that lowers the cost barrier to data publication. This project will create a new economic space for growth and job creation while providing the public far greater access to the data created with its tax dollars.”

June 2: How to Set Up DNS Resolution Between On-Premises Networks and AWS by Using Unbound
In previous AWS Security Blog posts, Drew Dennis covered two options for establishing DNS connectivity between your on-premises networks and your Amazon Virtual Private Cloud (Amazon VPC) environments. His first post explained how to use Simple AD to forward DNS requests originating from on-premises networks to an Amazon Route 53 private hosted zone. His second post showed how you can use Microsoft Active Directory (also provisioned with AWS Directory Service) to provide the same DNS resolution with some additional forwarding capabilities. In this post, I will explain how you can set up DNS resolution between your on-premises DNS with Amazon VPC by using Unbound, an open-source, recursive DNS resolver. This solution is not a managed solution like Microsoft AD and Simple AD, but it does provide the ability to route DNS requests between on-premises environments and an Amazon VPC–provided DNS.

June 1: How to Manage Secrets for Amazon EC2 Container Service–Based Applications by Using Amazon S3 and Docker
In this blog post, I will show you how to store secrets on Amazon S3, and use AWS IAM roles to grant access to those stored secrets using an example WordPress application deployed as a Docker image using ECS. Using IAM roles means that developers and operations staff do not have the credentials to access secrets. Only the application and staff who are responsible for managing the secrets can access them. The deployment model for ECS ensures that tasks are run on dedicated EC2 instances for the same AWS account and are not shared between customers, which gives sufficient isolation between different container environments.

If you have comments  about any of these posts, please add your comments in the “Comments” section of the appropriate post. If you have questions about or issues implementing the solutions in any of these posts, please start a new thread on the AWS IAM forum.

– Craig

I’ve bought some more awful IoT stuff

Post Syndicated from Matthew Garrett original https://mjg59.dreamwidth.org/43486.html

I bought some awful WiFi lightbulbs a few months ago. The short version: they introduced terrible vulnerabilities on your network, they violated the GPL and they were also just bad at being lightbulbs. Since then I’ve bought some other Internet of Things devices, and since people seem to have a bizarre level of fascination with figuring out just what kind of fractal of poor design choices these things frequently embody, I thought I’d oblige.

Today we’re going to be talking about the KanKun SP3, a plug that’s been around for a while. The idea here is pretty simple – there’s lots of devices that you’d like to be able to turn on and off in a programmatic way, and rather than rewiring them the simplest thing to do is just to insert a control device in between the wall and the device andn ow you can turn your foot bath on and off from your phone. Most vendors go further and also allow you to program timers and even provide some sort of remote tunneling protocol so you can turn off your lights from the comfort of somebody else’s home.

The KanKun has all of these features and a bunch more, although when I say “features” I kind of mean the opposite. I plugged mine in and followed the install instructions. As is pretty typical, this took the form of the plug bringing up its own Wifi access point, the app on the phone connecting to it and sending configuration data, and the plug then using that data to join your network. Except it didn’t work. I connected to the plug’s network, gave it my SSID and password and waited. Nothing happened. No useful diagnostic data. Eventually I plugged my phone into my laptop and ran adb logcat, and the Android debug logs told me that the app was trying to modify a network that it hadn’t created. Apparently this isn’t permitted as of Android 6, but the app was handling this denial by just trying again. I deleted the network from the system settings, restarted the app, and this time the app created the network record and could modify it. It still didn’t work, but that’s because it let me give it a 5GHz network and it only has a 2.4GHz radio, so one reset later and I finally had it online.

The first thing I normally do to one of these things is run nmap with the -O argument, which gives you an indication of what OS it’s running. I didn’t really need to in this case, because if I just telnetted to port 22 I got a dropbear ssh banner. Googling turned up the root password (“p9z34c”) and I was logged into a lightly hacked (and fairly obsolete) OpenWRT environment.

It turns out that here’s a whole community of people playing with these plugs, and it’s common for people to install CGI scripts on them so they can turn them on and off via an API. At first this sounds somewhat confusing, because if the phone app can control the plug then there clearly is some kind of API, right? Well ha yeah ok that’s a great question and oh good lord do things start getting bad quickly at this point.

I’d grabbed the apk for the app and a copy of jadx, an incredibly useful piece of code that’s surprisingly good at turning compiled Android apps into something resembling Java source. I dug through that for a while before figuring out that before packets were being sent, they were being handed off to some sort of encryption code. I couldn’t find that in the app, but there was a native ARM library shipped with it. Running strings on that showed functions with names matching the calls in the Java code, so that made sense. There were also references to AES, which explained why when I ran tcpdump I only saw bizarre garbage packets.

But what was surprising was that most of these packets were substantially similar. There were a load that were identical other than a 16-byte chunk in the middle. That plus the fact that every payload length was a multiple of 16 bytes strongly indicated that AES was being used in ECB mode. In ECB mode each plaintext is split up into 16-byte chunks and encrypted with the same key. The same plaintext will always result in the same encrypted output. This implied that the packets were substantially similar and that the encryption key was static.

Some more digging showed that someone had figured out the encryption key last year, and that someone else had written some tools to control the plug without needing to modify it. The protocol is basically ascii and consists mostly of the MAC address of the target device, a password and a command. This is then encrypted and sent to the device’s IP address. The device then sends a challenge packet containing a random number. The app has to decrypt this, obtain the random number, create a response, encrypt that and send it before the command takes effect. This avoids the most obvious weakness around using ECB – since the same plaintext always encrypts to the same ciphertext, you could just watch encrypted packets go past and replay them to get the same effect, even if you didn’t have the encryption key. Using a random number in a challenge forces you to prove that you actually have the key.

At least, it would do if the numbers were actually random. It turns out that the plug is just calling rand(). Further, it turns out that it never calls srand(). This means that the plug will always generate the same sequence of challenges after a reboot, which means you can still carry out replay attacks if you can reboot the plug. Strong work.

But there was still the question of how the remote control works, since the code on github only worked locally. tcpdumping the traffic from the server and trying to decrypt it in the same way as local packets worked fine, and showed that the only difference was that the packet started “wan” rather than “lan”. The server decrypts the packet, looks at the MAC address, re-encrypts it and sends it over the tunnel to the plug that registered with that address.

That’s not really a great deal of authentication. The protocol permits a password, but the app doesn’t insist on it – some quick playing suggests that about 90% of these devices still use the default password. And the devices are all based on the same wifi module, so the MAC addresses are all in the same range. The process of sending status check packets to the server with every MAC address wouldn’t take that long and would tell you how many of these devices are out there. If they’re using the default password, that’s enough to have full control over them.

There’s some other failings. The github repo mentioned earlier includes a script that allows arbitrary command execution – the wifi configuration information is passed to the system() command, so leaving a semicolon in the middle of it will result in your own commands being executed. Thankfully this doesn’t seem to be true of the daemon that’s listening for the remote control packets, which seems to restrict its use of system() to data entirely under its control. But even if you change the default root password, anyone on your local network can get root on the plug. So that’s a thing. It also downloads firmware updates over http and doesn’t appear to check signatures on them, so there’s the potential for MITM attacks on the plug itself. The remote control server is on AWS unless your timezone is GMT+8, in which case it’s in China. Sorry, Western Australia.

It’s running Linux and includes Busybox and dnsmasq, so plenty of GPLed code. I emailed the manufacturer asking for a copy and got told that they wouldn’t give it to me, which is unsurprising but still disappointing.

The use of AES is still somewhat confusing, given the relatively small amount of security it provides. One thing I’ve wondered is whether it’s not actually intended to provide security at all. The remote servers need to accept connections from anywhere and funnel decent amounts of traffic around from phones to switches. If that weren’t restricted in any way, competitors would be able to use existing servers rather than setting up their own. Using AES at least provides a minor obstacle that might encourage them to set up their own server.

Overall: the hardware seems fine, the software is shoddy and the security is terrible. If you have one of these, set a strong password. There’s no rate-limiting on the server, so a weak password will be broken pretty quickly. It’s also infringing my copyright, so I’d recommend against it on that point alone.

comment count unavailable comments

I’ve bought some more awful IoT stuff

Post Syndicated from Matthew Garrett original http://mjg59.dreamwidth.org/43486.html

I bought some awful WiFi lightbulbs a few months ago. The short version: they introduced terrible vulnerabilities on your network, they violated the GPL and they were also just bad at being lightbulbs. Since then I’ve bought some other Internet of Things devices, and since people seem to have a bizarre level of fascination with figuring out just what kind of fractal of poor design choices these things frequently embody, I thought I’d oblige.

Today we’re going to be talking about the KanKun SP3, a plug that’s been around for a while. The idea here is pretty simple – there’s lots of devices that you’d like to be able to turn on and off in a programmatic way, and rather than rewiring them the simplest thing to do is just to insert a control device in between the wall and the device andn ow you can turn your foot bath on and off from your phone. Most vendors go further and also allow you to program timers and even provide some sort of remote tunneling protocol so you can turn off your lights from the comfort of somebody else’s home.

The KanKun has all of these features and a bunch more, although when I say “features” I kind of mean the opposite. I plugged mine in and followed the install instructions. As is pretty typical, this took the form of the plug bringing up its own Wifi access point, the app on the phone connecting to it and sending configuration data, and the plug then using that data to join your network. Except it didn’t work. I connected to the plug’s network, gave it my SSID and password and waited. Nothing happened. No useful diagnostic data. Eventually I plugged my phone into my laptop and ran adb logcat, and the Android debug logs told me that the app was trying to modify a network that it hadn’t created. Apparently this isn’t permitted as of Android 6, but the app was handling this denial by just trying again. I deleted the network from the system settings, restarted the app, and this time the app created the network record and could modify it. It still didn’t work, but that’s because it let me give it a 5GHz network and it only has a 2.4GHz radio, so one reset later and I finally had it online.

The first thing I normally do to one of these things is run nmap with the -O argument, which gives you an indication of what OS it’s running. I didn’t really need to in this case, because if I just telnetted to port 22 I got a dropbear ssh banner. Googling turned up the root password (“p9z34c”) and I was logged into a lightly hacked (and fairly obsolete) OpenWRT environment.

It turns out that here’s a whole community of people playing with these plugs, and it’s common for people to install CGI scripts on them so they can turn them on and off via an API. At first this sounds somewhat confusing, because if the phone app can control the plug then there clearly is some kind of API, right? Well ha yeah ok that’s a great question and oh good lord do things start getting bad quickly at this point.

I’d grabbed the apk for the app and a copy of jadx, an incredibly useful piece of code that’s surprisingly good at turning compiled Android apps into something resembling Java source. I dug through that for a while before figuring out that before packets were being sent, they were being handed off to some sort of encryption code. I couldn’t find that in the app, but there was a native ARM library shipped with it. Running strings on that showed functions with names matching the calls in the Java code, so that made sense. There were also references to AES, which explained why when I ran tcpdump I only saw bizarre garbage packets.

But what was surprising was that most of these packets were substantially similar. There were a load that were identical other than a 16-byte chunk in the middle. That plus the fact that every payload length was a multiple of 16 bytes strongly indicated that AES was being used in ECB mode. In ECB mode each plaintext is split up into 16-byte chunks and encrypted with the same key. The same plaintext will always result in the same encrypted output. This implied that the packets were substantially similar and that the encryption key was static.

Some more digging showed that someone had figured out the encryption key last year, and that someone else had written some tools to control the plug without needing to modify it. The protocol is basically ascii and consists mostly of the MAC address of the target device, a password and a command. This is then encrypted and sent to the device’s IP address. The device then sends a challenge packet containing a random number. The app has to decrypt this, obtain the random number, create a response, encrypt that and send it before the command takes effect. This avoids the most obvious weakness around using ECB – since the same plaintext always encrypts to the same ciphertext, you could just watch encrypted packets go past and replay them to get the same effect, even if you didn’t have the encryption key. Using a random number in a challenge forces you to prove that you actually have the key.

At least, it would do if the numbers were actually random. It turns out that the plug is just calling rand(). Further, it turns out that it never calls srand(). This means that the plug will always generate the same sequence of challenges after a reboot, which means you can still carry out replay attacks if you can reboot the plug. Strong work.

But there was still the question of how the remote control works, since the code on github only worked locally. tcpdumping the traffic from the server and trying to decrypt it in the same way as local packets worked fine, and showed that the only difference was that the packet started “wan” rather than “lan”. The server decrypts the packet, looks at the MAC address, re-encrypts it and sends it over the tunnel to the plug that registered with that address.

That’s not really a great deal of authentication. The protocol permits a password, but the app doesn’t insist on it – some quick playing suggests that about 90% of these devices still use the default password. And the devices are all based on the same wifi module, so the MAC addresses are all in the same range. The process of sending status check packets to the server with every MAC address wouldn’t take that long and would tell you how many of these devices are out there. If they’re using the default password, that’s enough to have full control over them.

There’s some other failings. The github repo mentioned earlier includes a script that allows arbitrary command execution – the wifi configuration information is passed to the system() command, so leaving a semicolon in the middle of it will result in your own commands being executed. Thankfully this doesn’t seem to be true of the daemon that’s listening for the remote control packets, which seems to restrict its use of system() to data entirely under its control. But even if you change the default root password, anyone on your local network can get root on the plug. So that’s a thing. It also downloads firmware updates over http and doesn’t appear to check signatures on them, so there’s the potential for MITM attacks on the plug itself. The remote control server is on AWS unless your timezone is GMT+8, in which case it’s in China. Sorry, Western Australia.

It’s running Linux and includes Busybox and dnsmasq, so plenty of GPLed code. I emailed the manufacturer asking for a copy and got told that they wouldn’t give it to me, which is unsurprising but still disappointing.

The use of AES is still somewhat confusing, given the relatively small amount of security it provides. One thing I’ve wondered is whether it’s not actually intended to provide security at all. The remote servers need to accept connections from anywhere and funnel decent amounts of traffic around from phones to switches. If that weren’t restricted in any way, competitors would be able to use existing servers rather than setting up their own. Using AES at least provides a minor obstacle that might encourage them to set up their own server.

Overall: the hardware seems fine, the software is shoddy and the security is terrible. If you have one of these, set a strong password. There’s no rate-limiting on the server, so a weak password will be broken pretty quickly. It’s also infringing my copyright, so I’d recommend against it on that point alone.

comment count unavailable comments

Announcing Two New AWS Quick Start Reference Deployments for Compliance

Post Syndicated from Lou Vecchioni original https://blogs.aws.amazon.com/security/post/Tx1AAQ3GYTYNVSC/Announcing-Two-New-AWS-Quick-Start-Reference-Deployments-for-Compliance

As part of the Professional Services Enterprise Accelerator – Compliance program, AWS has published two new Quick Start reference deployments to assist federal government customers and others who need to meet National Institute of Standards and Technology (NIST) SP 800-53 (Revision 4) security control requirements, including those at the high-impact level. The new Quick Starts are AWS Enterprise Accelerator – Compliance: NIST-based Assurance Frameworks and AWS Enterprise Accelerator – Compliance: Standardized Architecture for NIST High-Impact Controls Featuring Trend Micro Deep Security. These Quick Starts address many of the NIST controls at the infrastructure layer. Furthermore, for systems categorized as high impact, AWS has worked with Trend Micro to incorporate its Deep Security product into a Quick Start deployment in order to address many additional high-impact controls at the workload layer (app, data, and operating system). In addition, we have worked with Telos Corporation to populate security control implementation details for each of these Quick Starts into the Xacta product suite for customers who rely upon that suite for governance, risk, and compliance workflows.

These two Quick Starts are designed to help various customers, including those who deploy systems that must:

  • Go through a NIST-based assessment and authorization (A&A).
  • Meet NIST SP 800-171 requirements related to Controlled Unclassified Information (CUI).
  • Provide Trusted Internet Connection (TIC) capabilities.
  • Meet Department of Defense (DoD) Cloud Security Requirements Guide (SRG) requirements for levels 4–5.

Each Quick Start builds a recommended architecture which, when deployed as a package, provides a baseline AWS security-related configuration, and for the NIST high-impact Quick Start, includes a Trend Micro Deep Security configuration. The architectures are instantiated by these Quick Starts through sets of nested AWS CloudFormation templates and user data scripts that build an example environment with a two-VPC, multi-tiered web service. The NIST high-impact version launches Trend Micro Deep Security and deploys a single agent with relevant security configurations on all Amazon EC2 instances within the architecture. For more information about Deep Security, go to Defend your AWS workloads.

The Quick Starts also include:

  • AWS Identity and Access Management (IAM) resources – Policies, groups, roles, and instance profiles.
  • Amazon S3 buckets – Encrypted web content, logging, and backup.
  • A bastion host for troubleshooting and administration.
  • An encrypted Amazon RDS database instance running in multiple Availability Zones.
  • A logging/monitoring/alerting configuration that makes use of AWS CloudTrail, Amazon CloudWatch, and AWS Config Rules.

The recommended architecture supports a wide variety of AWS best practices (all of which are detailed in the document) that include the use of multiple Availability Zones, isolation using public and private subnets, load balancing, and auto scaling.

Both Quick Start packages include a deployment guide with detailed instructions, and a security controls matrix that describes how NIST SP 800-53 controls are addressed by the deployment. The matrix should be reviewed by your IT security assessors and risk decision makers so that they can understand the extent of the implementation of the controls within the architecture. The security controls matrix also identifies the specific resources within the CloudFormation templates that affect each control, and contains cross-references to:

Though it is impossible to automatically implement all system-specific controls within a baseline architecture, these two Quick Start packages can help you address and document a significant portion of the technical controls (including up to 38% of the NIST high-impact controls, in the case of the NIST high-impact Quick Start variant).

In addition, Telos Corporation has integrated the controls compliance and guidance information from these packages into its Xacta product. This makes it simpler for you to inherit this information for your IT governance, risk, and compliance programs, and to document the differences or changes in your security compliance posture. For users of the Xacta product suite, this integration can reduce the effort required to produce bodies of evidence for A&A activities when leveraging AWS Cloud infrastructure. For more information about Telos and Xacta, see Telos and Amazon Web Services: Accelerating Secure and Compliant Cloud Deployments.

To access these new Quick Starts, see the Compliance, security, and identity management section on the AWS Quick Start Reference Deployments page.

If you have questions about these Quick Starts, please contact the AWS Compliance Accelerator team.

– Lou

MPAA Lobbyist / SOPA Sponsor to Draft Democratic Party Platform

Post Syndicated from Andy original https://torrentfreak.com/mpaa-lobbyist-sopa-sponsor-to-draft-democratic-party-platform-160531/

berman-smallLast week Hillary Clinton, Bernie Sanders and Democratic National Committee Chair Rep. Debbie Wasserman Schultz chose a panel of individuals to draft the party’s platform.

As previously reported, 15 were selected, with six chosen by Clinton, five chosen by Bernie Sanders and four chosen by Wasserman Schultz. While other publications will certainly pick over the bones of the rest of the committee, one in particular stands out as interesting to TF readers.

Howard L Berman is an attorney and former U.S. Representative. He’s employed at Covington & Burling as a lobbyist and represents the MPAA on matters including “Intellectual property issues in trade agreements, bilateral investment treaties, copyright, and related legislation.”

It will come as no surprise then that the major studios have been donors throughout Berman’s political career. As shown in the image below, the top five contributors are all major movie companies.

hberman1

Born in 1941, Berman’s work with the film industry earned him the nickname “the congressman from Hollywood” and over the years he’s been at the root of some of the most heated debates over the protection of intellectual property.

In 2007 and as later confirmed by Wikileaks, Berman was one of the main proponents of ACTA, the Anti-Counterfeiting Trade Agreement.

Just five short years later Berman was at the heart of perhaps the biggest copyright controversy the world has ever seen when he became a co-sponsor of the Stop Online Piracy Act (SOPA).

“The theft of American Intellectual Property not only robs those in the creative chain of adequate compensation, but it also stunts potential for economic growth, cheats our communities out of good paying jobs, and threatens future American innovation,” Berman said in the run-up to SOPA.

While these kinds of soundbites are somewhat common, it’s interesting to note that Berman showed particular aggression towards Google during hearings focusing on SOPA. On November 16, 2011, Berman challenged the search giant over its indexing of The Pirate Bay.

google-bayInsisting that there “is no contradiction between intellectual property rights protection and enforcement ensuring freedom of expression on the Internet,” Berman said that Google’s refusal to delist the entire site was unacceptable.

“All right. Well, explain to me this one,” Berman demanded of Google policy counsel Katherine Oyama.

“The Pirate Bay is a notorious pirate site, a fact that its founders proudly proclaim in the name of the site itself. In fact, the site’s operators have been criminally convicted in Europe. And yet…..U.S.-Google continues to send U.S. consumers to the site by linking to the site in your search results. Why does Google refuse to de-index the site in your search results?” he said.

Oyama tried to answer, noting that Google invests tens of millions of dollars into the problem. “We have hundreds of people around the world that work on it,” she said. “When it comes to copyright….”

Berman didn’t allow her to finish, repeating his question about delisting the whole site, again and again. Before Berman’s time ran out, Oyama was interrupted several more times while trying to explain that the DMCA requires takedowns of specific links, not entire domains. Instead, Berman suggested that Oyama should “infuse herself” with the notion that Google wanted to stop “digital theft.”

“[T]he DMCA is not doing the job. That is so obvious,” he said. “[Y]ou cannot look at what is going on since the passage of the DMCA and say Congress got it just right. Maintain the status quo.”

These arguments continue today in the “takedown, staydown” debate surrounding the ongoing review of the DMCA, with Hollywood lining up on one side and Google being held responsible for the actions of others on the other. But simply complaining about the DMCA is a little moderate for Berman.

Almost one and a half decades ago in the wake of Napster and before the rise of BitTorrent, Berman had a dream of dealing with peer-to-peer file-sharing by force. In 2002 he proposed the Peer To Peer Piracy Prevention Act, which would have allowed copyright holders to take extraordinary technical measures against file-sharers in order to stop the unauthorized distribution of their content.

H.R.5211 sought to amend Federal copyright law to protect a copyright owner from liability in any criminal or civil action “for impairing, with appropriate technology, the unauthorized distribution, display, performance, or reproduction of his or her copyrighted work on a publicly accessible peer-to-peer file trading network.”

The bill didn’t deal in specifics, but “impairing” was widely believed to be a euphemism for DDoS and poisoning attacks on individual file-sharers in order to make sharing impossible from their computers.

At the time “shared-folder” type sharing apps were still popular so bombarding networks with fake and badly named files would also have been fair game, although distributing viruses and malware were not on the table. Eventually, however, the bill died.

Berman, on the other hand, appears to be very much alive and will be soon helping to draft the Democratic Party platform. On past experience his input might not be too difficult to spot.

Source: TF, for the latest info on copyright, file-sharing, torrent sites and ANONYMOUS VPN services.

Perlin noise

Post Syndicated from Eevee original https://eev.ee/blog/2016/05/29/perlin-noise/

I used Perlin noise for the fog effect and title screen in Under Construction. I tweeted about my efforts to speed it up, and several people replied either confused about how Perlin noise works or not clear on what it actually is.

I admit I only (somewhat) understand Perlin noise in the first place because I’ve implemented it before, for flax, and that took several days of poring over half a dozen clumsy explanations that were more interested in showing off tech demos than actually explaining what was going on. The few helpful resources I found were often wrong, and left me with no real intuitive grasp of how and why it works.

Here’s the post I wish I could’ve read in the first place.

What Perlin noise is

In a casual sense, “noise” is random garbage. Here’s some visual noise.

white noise

This is white noise, which roughly means that all the pixels are random and unrelated to each other. The average of all these pixels should be #808080, a medium gray — it turns out to be #848484, which is pretty close.

Noise is useful for generating random patterns, especially for unpredictable natural phenomena. That image above might be a good starting point for creating, say, a gravel texture.

However, most things aren’t purely random. Smoke and clouds and terrain may look like they have elements of randomness, but they were created by a set of very complex interactions between lots of tiny particles. White noise is defined by having all the particles (or pixels) not depend on each other. To generate something more interesting than gravel, we need a different kind of noise.

That noise is often Perlin noise, which looks like this.

Perlin noise

That hopefully looks familiar, even if only as a Photoshop filter you tried out once. (I created it with GIMP’s Filters → Render → Clouds → Solid Noise.)

The most obvious difference is that it looks cloudy. More technically, it’s continuous — if you zoom in far enough, you’ll always see a smooth gradient. There are no jarring transitions from black to white. That makes it work surprisingly well when you want something “random”, but not, you know… too random. Here’s a quick sky, made from the exact same image.

Clouds derived from Perlin noise

All I did was add a layer of solid blue underneath; use Levels to chop off the darkest parts of the noise; and use what was left as a transparent white on top. It could be better, but it’s not bad for about ten seconds of work. It even tiles seamlessly!

Perlin noise from scratch

You can make Perlin noise in any number of dimensions. The above image is of course 2-D, but it’s much easier to explain in 1-D, where there’s only a single input and a single output. That makes it easy to illustrate with a regular old graph.

First, at every integer x = 0, 1, 2, 3, …, choose a random number between -1 and 1. This will be the slope of a line at that point, which I’ve drawn in light blue.

It doesn’t really matter how many points you choose. Each segment — the space between two tick marks — works pretty much the same way. As long as you can remember all the slopes you picked, you can extend this line as far as you want in either direction. These sloped lines are all you need to make Perlin noise.

Any given x lies between two tick marks, and thus between two sloped lines. Call the slopes of those lines a and b. The function for a straight line can be written as m(x – x₀), where m is the slope and x₀ is the x-value where the line crosses the x-axis.

Armed with this knowledge, it’s easy to find out where those two sloped lines cross a given x. For simplicitly, I’ll assume the tick mark on the left is at x = 0; that produces values of ax and b(x – 1) (because the rightmost line crosses the axis at 1, not 0).

I’ve drawn a bunch of example points in orange. You can see how they follow the two sloped lines on either side.

The question now becomes: how can these pairs of points combine into a smooth curve? The most obvious thing is to average them, but a quick look at the graph shows that that won’t work. The “average” of two lines is just a line drawn halfway between them, and the average line for each segment wouldn’t even touch its neighbor.

We need something that treats the left end as more important when we’re closer to the left end, and the right end as more important when we’re closer to the right end. The simplest way to do this is linear interpolation (sometimes abbreviated as “lerp”).

Linear interpolation is pretty simple: if you’re t of the way between two extremes A and B, then the linear interpolation is A + t(B – A) or, equivalently, A(1 – t) + Bt. For t = 0, you get A; for t = 1, you get B; for t = ½, you get ½(A + B), the average.

Let’s give that a try. I’ve marked the interpolated points in red.

Not a bad start. It’s not quite Perlin noise yet; there’s one little problem, though it may not be immediately obvious from just these points. I can make it more visible, if you’ll forgive a brief tangent.

Each of these curves is a parabola, given by (a – b)(x – x²). I wanted to be able to draw this exactly, rather than approximate it with some points, which meant figuring out how to convert it to a Bézier curve.

Bézier curves are the same curves you see used for path drawing in vector graphics editors like Inkscape, Illustrator, or Flash. (Or in the SVG vector format, which I used to make all these illustrations.) You choose a start and end points, and the program provides an extra handle attached to each point. Dragging the handles around changes the shape of the curve. Those are cubic Bézier curves, so called because the actual function contains a , but you can have a Bézier curve of any order.

As I looked into the actual math behind Bézier curves, I learned a few interesting things:

  1. SVG supports quadratic Bézier curves! That’s convenient, since I have a quadratic function.

  2. Bézier curves are defined by repeated linear interpolation! In fact, there’s such a thing as a linear Bézier “curve”, which is linear interpolation — a straight line between two chosen points. A quadratic curve has three points; you interpolate between the first/second and second/third, then interpolate the results together. Cubic has four points and goes one step further, and so on. Fascinating.

  3. The parabolas formed by the red dots are very easy to draw with Bézier curves — in fact, Perlin noise bears a striking similarity to Bézier curves! It makes sense, in a way. The first step produced values of ax and b(x – 1), which can be written -b(1 – x), and that’s reminiscent of linear interpolation. The second step was a straightforward round of linear interpolation. Two rounds of linear interpolation is how you make a quadratic Bézier curve.

I think I have a geometric interpretation of what happened here.

Pick a segment. It has a “half”-line jutting into it from each end. Mirror them both, creating two half-lines on each end. Add their slopes together to make two new lines, which are each other’s mirror images, because they were both formed from one line plus a reflection of the other. Draw a curve between those two lines.

I’ve illustrated this below. The dotted lines are the mirrored images; the darker blue lines are the summed new lines; the darker blue points are their intersections (and the third handle for a quadratic Bézier curve); and the red arc is the exact curve following the red points. If you know a little calculus, you can confirm that the slope on the left side is a – b and the slope on the right side is b – a, which indeed makes them mirror images.

Hopefully the problem is now more obvious: these curves don’t transition smoothly into each other. There’s a distinct corner at each tick mark. The one at the end, where both curves are pointing downwards, is particularly bad.

Linear interpolation, as it turns out, is not quite enough. Even as we get pretty close to one endpoint, the other endpoint still has a fairly significant influence, which pulls the slope of the curve away from the slope of the original random line. That influence needs to drop away more sharply towards the ends.

Thankfully, someone has already figured this out for us. Before we do the linear interpolation, we can bias t with the smoothstep function. It’s an S-shaped curve that’s similar to the straight diagonal line y = x, but at 0 and 1 it flattens out. Towards the middle, it doesn’t change a lot — ½ just becomes ½ — but it adds a strong bias near the endpoints. Put in 0.9, and you’ll get 0.972.

The result is quartic — t⁴, which SVG’s cubic Béziers can’t exactly trace — so the gray line is a rough approximation. I’ve compensated by adding many more points, which are in black. Those points came out of Ken Perlin’s original noise1 function, by the way; this is true Perlin noise.

The new dots are close to the red quadratic curves, but near the tick marks, they shift to follow the original light blue slopes. The midpoints have exactly the same values, because smoothstep doesn’t change ½.

(The function for each segment is now 2(a – b)x⁴ – (3a – 5b)x³ – 3bx² + ax, rather more of a mouthful. Feel free to differentiate and convince yourself that the slopes at the endpoints are, in fact, exactly a and b.)

If you want to get a better handle on how this feels, here’s that same graph, but live! Click and drag to mess with the slopes.

Octaves

You may have noticed that these valleys and hills, while smooth, don’t look much like the cloudy noise I advertised in the beginning.

In a shocking twist, the cloudiness isn’t actually part of Perlin noise. It’s a clever thing you can do on top of Perlin noise.

Create another Perlin curve (or reuse the same one), but double the resolution — so there’s a randomly-chosen line at x = 0, ½, 1, …. Then halve the output value, and add it on top of the first curve. You get something like this.

The entire graph has been scaled down to half size, but extended to the full range of the first graph.

You can repeat this however many times you want, making each graph half the size of the previous one. Each separate graph is called an octave (from music, where one octave has twice the frequency of the previous), and the results look nice and jittery after four or five octaves.

Extending to 2-D

The idea is the same, but instead of a line with some slopes on it, the input is a grid. Also, to extend the idea of “slope” into two dimensions, each grid point has a vector.

I shortened the arrows so they’d actually fit in the image and not overlap each other, but these are intended to be unit vectors — that is, every arrow actually has a length of 1, which means it only carries information about direction and not distance. I’ll get into actually generating these later.

It looks similar, but there’s a crucial difference. Before, the input was horizontal — the position on the x-axis — and the output was vertical. Here, the input is both directions — where are we?

A rough algorithm for what we did before might look like this:

  1. Find the distance to the nearest point to the left, and multiply by that point’s slope.
  2. Do the same for the point to the right.
  3. Interpolate those two values together.

This needs a couple major changes to work in two dimensions. Each point now has four neighboring grid points, and there still needs to be some kind of distance multiplication.

The solution is to use dot products. If you have two vectors (a, b) and (c, d), their dot product is the sum of the pairwise products: ac + bd. In the above diagram, each surrounding grid point now has two vectors attached to it: the random one, and one pointing at the chosen point. The distance multiplication can just be the dot product of those two vectors.

But, ah, why? Good question.

The geometric explanation of the dot product is that it’s the product of the lengths of the two vectors, times the cosine of the angle between them. That has never in my life clarified anything, and it’s impossible to make a diagram out of, but let’s think about this for a moment.

All of the random vectors are unit vectors, so their lengths are 1. That contributes nothing to the product. So what’s left is the (scalar) distance from a chosen point to the grid point, times the cosine of the angle between these two vectors.

Cosine tells you how small an angle is — or in this case, how close together two vectors are. If they’re pointing the same direction, then the cosine is 1. As they move farther apart, the cosine gets smaller: at right angles it becomes zero (and the dot product is always zero), and if they’re pointing in opposite directions then the cosine falls to -1.

To visualize what this means, I plotted only the dot product between a point and its nearest grid point. This is the equivalent of the orange dots from the 1-D graph.

That’s pretty interesting. Remember, this is a kind of top-down view of a 3-D graph. The x- and y-coordinates are the input, the point of our choosing, and the z-coordinate is the output. It’s usually drawn with a shade of gray, as I’ve done here, but you can also picture it as a depth. White points are coming out of the screen towards you, and black points are deeper into the screen.

In that sense, each grid point has a sloped plane stuck to it, versus the sloped lines we had with 1-D noise. The vector points towards the white end, the end that sticks out of the screen towards you. For points closer to the grid point, the dot product is close to zero, just like the 1-D graph; for points further away, the result is usually more extreme.

You may not be surprised to learn at this point that the random vectors are usually referred to as gradients.

Now, each point has four dot products, which need to be combined together somehow. Linear interpolation only works for exactly two values, so instead, we have to interpolate them in pairs. One round of interpolation will get us down to two values, then another round will produce a single value, which is the output.

I tried to make a diagram showing an intermediate state, to help demonstrate how the multiple gradients combine, but I couldn’t quite figure out how to make it work sensibly.

Instead, please accept this interactive Perlin noise grid, where you can once again drag the arrows around to see how it affects the resulting pattern.

3-D and beyond

From here, it’s not too hard to extend the idea to any number of dimensions. Pick more unit vectors in the right number of dimensions, calculate more dot products, and interpolate them all together.

One point to keep in mind: each round of interpolation should “collapse” an axis.

Consider 2-D, which requires dot products for each of the four neighboring points: top-left, top-right, bottom-left, bottom-right. There are two dimensions, so two rounds of interpolation are needed.

You might interpolate top-left with top-right and bottom-left with bottom-right; that would “collapse” the horizontal axis and leave only two values, top and bottom. Or you might do it the other way, top-left with bottom-left and top-right with bottom-right, collapsing the vertical axis and leaving left and right. Either is fine.

What you definitely can’t do is interpolate top-right with bottom-left and top-left with bottom-right. You need to know how much to interpolate by, which means knowing how far between points you are. Interpolating horizontally is fine, because we know our horizontal distance from that grid point. Interpolating vertically is fine, because we know our vertical distance from that grid point. Interpolating… diagonally? What does that mean? What’s our value of t? And how on Earth do we interpolate the two resulting values?

This is a little tricky to keep track of in three or more dimensions, so keep an eye out.

Variations

The idea behind Perlin noise is pretty simple, and you can modify almost any of it for various effects.

Picking the gradients

I know of three different ways to choose the gradients.

The most obvious way is to pick n random numbers from -1 to 1 (for n dimensions), use the Pythagorean theorem to get the length of that vector, then divide all the numbers by the length. Voilà, you have a unit vector. This is what Ken Perlin’s original code did.

That’ll work, but it’ll produce more vectors pointing diagonally than vectors pointing along an axis, for the same reason that rolling two dice produces 7 more than anything else. You really want a random angle, not a random coordinate.

For two dimensions, that’s easy: pick a random angle! Roll a single number between 0 and 2π. Call it θ. Your vector is (cos θ, sin θ). Done.

For three dimensions… uh.

Well, I looked this up on MathWorld and found a solution that I believe works in any dimension. It works exactly the same as before: pick n random numbers and scale down to length 1. The difference is that the numbers have to be normally distributed — that is, picked from a bell curve. In Python, there’s random.gauss() for this; in C, well, I think you can fake it by picking a lot of plain random numbers and adding them together. Again, same idea as rolling multiple dice.

This doesn’t work so well for one dimension, where dividing by the length will always give you 1 or -1, and your noise will look terrible. In that case, always just pick a single random number from -1 to 1.

The third method, as proposed in Ken Perlin’s paper “Improving Noise“, is to not choose random gradients at all! Instead, use a fixed set of vectors, and pick from among them randomly.

Why would you do this? Part of the reason was to address clumping, which I suspect was partly caused by that diagonal bias. But another reason was…

Optimization

I’ve neglected to mention a key point of Ken Perlin’s original implementation. It didn’t quite create a set of random gradients for every grid point; it created a set of random gradients of a fixed size, then used a scheme to pick one of those gradients given any possible grid point. It kept memory use low and was designed to be fast, but still allowed points to be arbitrarily high or low.

The “improved” proposal does away with the random gradients entirely, substituting (for the 3-D case) a set of 16 gradients where one coordinate is 0 and the other two are either -1 or 1. These aren’t unit vectors any more, but the dot products are much easier to compute. The randomness is provided by the scheme for picking a gradient given a grid point. For large swaths of noise, it turns out that this works just as well.

Neither optimization is necessary to have Perlin noise, but you might want to look into them if you’re generating a lot of noise in realtime.

Smootherstep

The choice of smoothstep is somewhat arbitrary; you could use any function that flattens out towards 0 and 1.

Improving Noise” proposes an alternative in smootherstep, which is 6x⁵ – 15x⁴ + 10x³. It’s possible to make higher-order polynomials the same way, though of course they get increasingly time-consuming to evaluate.

There’s no reason you couldn’t also adapt, say a sine curve: ½sin(π(x – ½)) + ½. Not necessarily practical, and almost certainly much slower than a few multiplications, but it’s perfectly valid.

Comparison of the three curves

Looks pretty similar to me. smootherstep has some harsher extremes, which is interesting.

Octaves

There’s nothing special about the way I did octaves above; it’s just a simple kind of fractal. As long as you keep adding more detailed noise with a smaller range, you’ll probably get something interesting.

This talk by Ken Perlin has some examples, such as taking the absolute value of each octave before adding them together to make a turbulent effect, or taking the sine to create a swirling marbled effect.

Throw math at it and see what happens. That’s what math is for!

Tiling

Make the grid of gradients tile, and the resulting noise will tile. Super easy.

Simplex noise

In higher dimensions, even finding the noise for a single point requires a lot of math. Even in 3-D, there are eight surrounding points: eight dot products, seven linear interpolations, three _smoothstep_s.

Simplex noise is a variation that uses triangles rather than squares. In 3-D, that’s a tetrahedron, which is only four points rather than eight. In 4-D it’s five points rather than sixteen.

I’ve never needed so much noise so fast that I’ve had reason to implement this, but if you’re generating noise in 4-D or 5-D (!), it might be helpful.

Some properties

The value of Perlin noise at every grid point, in any number of dimensions, is zero.

Perlin noise is continuous — there are no abrupt changes. Even if you use lots and lots of octaves, no matter how jittery it may look, if you zoom in enough, you’ll still have a smooth curve.

Contrary to popular belief — one espoused even by Ken Perlin! — the output range of Perlin noise is not -1 to 1. It’s ±½√n, where n is the number of dimensions. So a 1-D plane can never extend beyond -½ or ½ (which I bet you could prove if you thought about it), and the familiar 2-D noise is trapped within ±½√2 ≈ ±0.707 (which is also provable by extending the same thought a little further). If you’re using Perlin noise and expecting to span a specific range, make sure to take this into account.

Octaves will change the output range, of course. One octave will increase the range by 50%; two will increase it by 75%; three, by 87.5%; and so on.

The output of Perlin noise is not evenly distributed, not by a long shot. Here’s a histogram of some single-octave 2-D Perlin noise generated by GIMP:

I have no idea what this distribution is; it’s sure not a bell curve. Notice in particular that the top and bottom ⅛ of values are virtually nonexistent. If you play with the live 2-D demo, you can probably figure out why that happens: you only get a bright white if all four neighboring arrows are pointing towards the center of the square, and only get black if all four arrows are pointing away. Both of those cases are relatively unlikely.

If you want a little more weighting on the edges, you could try feeding the noise through a function that biases towards its endpoints… like, say, smoothstep. Just be sure you normalize to [0, 1] first.

Surprisingly, adding octaves doesn’t change the distribution all that much, assuming you scale back down to the same range.

There are quite a lot of applications for Perlin noise. I’ve seen wood grain faked by throwing in some modulus. I’ve used it to make a path through a roguelike forest. You can get easy clouds just by cutting it off at some arbitrary value. Under Construction‘s smoke is Perlin noise, where positive values are smoke and negative values are clear.

Because it’s continuous, you can use one axis as time, and get noise that also changes smoothly over time. Here’s a loop of some noise, where each frame is a 2-D slice of a (tiling) 3-D block of noise:

Give me some code already

Right, right, yes, of course. Here’s a Python implementation in a gist. I don’t know if I can justify turning it into a module and also I’m lazy.

Some cool features up in here:

  • Unlimited range
  • Unlimited dimensions
  • Built-in octave support
  • Built-in support for tiling
  • Lots of comments, some of which might even be correct
  • Probably pretty slow

Here’s the code that created the above animation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
from perlin import PerlinNoiseFactory
import PIL.Image

size = 200
res = 40
frames = 20
frameres = 5
space_range = size//res
frame_range = frames//frameres

pnf = PerlinNoiseFactory(3, octaves=4, tile=(space_range, space_range, frame_range))

for t in range(frames):
    img = PIL.Image.new('L', (size, size))
    for x in range(size):
        for y in range(size):
            n = pnf(x/res, y/res, t/frameres)
            img.putpixel((x, y), int((n + 1) / 2 * 255 + 0.5))

    img.save("noiseframe{:03d}.png".format(t))
    print(t)

Ran in 1m40s with PyPy 3.

Federal Appeals Court Decision in Oracle v. Google

Post Syndicated from Bradley M. Kuhn original http://ebb.org/bkuhn/blog/2014/05/10/oracle-google.html

[ Update on 2014-05-13: If you’re more of a listening
rather than reading type, you might
enjoy the Free as
in Freedom oggcast that
Karen Sandler and I recorded about this topic
. ]

I have a strange relationship with copyright law. Many copyright policies
of various jurisdictions, the USA in particular, are draconian at best and
downright vindictive at worst. For example, during the public comment
period on ACTA, I
commented that
I think it’s always wrong, as a policy matter, for
copyright infringement to carry criminal penalties.

That said, much of what I do in my work in the software freedom movement
is enforcement of copyleft: assuring that the primary legal tool, which
defends the freedom of the Free Software, functions properly, and actually
works — in the real world — the way it should.

As I’ve written
about before at great length
, copyleft functions primarily because it
uses copyright law to stand up and
defend the four
freedoms
. It’s commonly called a hack on copyright: turning the
copyright system which is canonically used to restrict users’ rights, into
a system of justice for the equality of users.

However, it’s this very activity that leaves me with a weird relationship
with copyright. Copyleft uses the restrictive force of copyright in the
other direction, but that means the greater the negative force, the more
powerful the positive force. So, as I read yesterday
the Federal
Circuit Appeals Court’s decision in Oracle v. Google
, I had that
strange feeling of simultaneous annoyance and contentment. In this blog
post, I attempt to state why I am both glad for and annoyed with the
decision.

I stated clearly
after Alsup’s decision NDCA decision in this case
that I never thought
APIs were copyrightable, nor does any developer really think so in
practice. But, when considering the appeal, note carefully that the
court of appeals wasn’t assigned the general job of considering whether
APIs are copyrightable. Their job is to figure out if the lower court
made an error in judgment in this particular case, and to
discern any issues that were missed previously. I think that’s what the
Federal Circuit Court attempted to do here, and while IMO they too erred
regarding a factual issue, I don’t think their decision is wholly useless
nor categorically incorrect.

Their decision is worth reading in full. I’d also urge anyone who wants
to opine on this decision to actually read the whole thing (which
so often rarely happens in these situations). I bet most pundits out there
opining already didn’t read the whole thing. I read the decision as soon
as it was announced, and I didn’t get this post up until early Saturday
morning, because it took that long to read the opinion in detail, go back
to other related texts and verify some details and then write down my
analysis. So, please, go ahead, read it now before reading this blog post
further. My post will still be here when you get back. (And, BTW, don’t
fall for that self-aggrandizing ballyhoo some lawyers will feed you that
only they can understand things like court decisions. In fact, I think
programmers are going to have an easier time reading decisions about this
topic than lawyers, as the technical facts are highly pertinent.)

Ok,
you’ve read
the decision now
? Good. Now, I’ll tell you what I think in detail: (As
always, my opinions on this are my own,
IANAL and
TINLA and these are my
personal thoughts on the question.)

The most interesting thing, IMO,
about this decision is that the Court focused on a fact from trial that
clearly has more nuance than they realize. Specifically, the Court claims
many times in this decision that Google conceded that it copied the
declaring code used in the 37 packages verbatim (pg 12 of the Appeals
decision).

I suspect the Court imagined the situation too simply: that there was a
huge body of source code text, and that Google engineers sat there, simply
cutting-and-pasting from Oracle’s code right into their own code for each of
the 7,000 lines or so of function declarations. However, I’ve chatted with
some people (including Mark
J. Wielaard
) who are much more deeply embedded in the Free Software Java
world than I am, and they pointed out it’s highly unlikely anyone did a
blatant cut-and-paste job to implement Java’s core library API, for various
reasons. I thus suspect that Google didn’t do it that way either.

So, how did the Appeals Court come to this erroneous conclusion? On page
27 of their decision, they write: Google conceded that it copied it
verbatim. Indeed, the district court specifically instructed the jury that
‘Google agrees that it uses the same names and declarations’ in
Android. Charge to the Jury at 10. So, I reread
page
10 of the final charge to the jury
. It actually says something much
more verbose and nuanced. I’ve pasted together below all the parts where
the Alsup’s jury charge mentions this issue (emphasis mine):

Google denies infringing any such copyrighted material … Google agrees
that the structure, sequence and organization of the 37 accused API packages
in Android is substantially the same as the structure, sequence and
organization of the corresponding 37 API packages in Java. …
The copyrighted Java platform has more than 37 API packages and so
does the accused Android platform. As for the 37 API packages that overlap,
Google agrees that it uses the same names and declarations but contends that
its line-by-line implementations are different … Google agrees that
the structure, sequence and organization of the 37 accused API packages in
Android is substantially the same as the structure, sequence and
organization of the corresponding 37 API packages in Java. Google states,
however, that the elements it has used are not infringing …
With respect to the API documentation, Oracle contends Google copied
the English-language comments in the registered copyrighted work and moved
them over to the documentation for the 37 API packages in Android. Google
agrees that there are similarities in the wording but, pointing to differences as
well, denies that its documentation is a copy. Google further asserts that the
similarities are largely the result of the fact that each API carries out the same
functions in both systems.

Thus, in the original trial, Google did not admit to
copying of any of Oracle’s text, documentation or code (other than the
rangeCheck thing, which is moot on the API copyrightability issue).
Rather, Google said two separate things: (a) they did not copy any material
(other than rangeCheck), and (b) admitted that the names and declarations
are the same, not because Google copied those names and
declarations from Oracle’s own work, but because they perform the same
functions. In other words, Google makes various arguments of why those
names and declarations look the same, but for reasons other than
“mundane cut-and-paste copying from Oracle’s copyrighted
works”.

For we programmers, this is of course a distinction without any
difference. Frankly, programmers, when we look at this situation, we’d
make many obvious logical leaps at once. Specifically, we all think APIs
in the abstract can’t possibly be copyrightable (since that’s absurd), and
we work backwards from there with some quick thinking, that goes something
like this: it doesn’t make sense for APIs to be copyrightable because if
you explain to me with enough detail what the API has to, such that I have
sufficient information to implement, my declarations of the functions of
that API are going to necessarily be quite similar to yours — so much
so that it’ll be nearly indistinguishable from what those function
declarations might look like if I cut-and-pasted them. So, the fact is, if
we both sit down separately to implement the same API, well, then we’re
likely going to have two works that look similar. However, it doesn’t mean
I copied your work. And, besides, it makes no sense for APIs, as a general
concept, to be copyrightable so why are we discussing this
again?0

But this is reasoning a programmer can love but the Courts hate. The
Courts want to take a set of laws the legislature passed, some precedents
that their system gave them, along with a specific set of facts, and then
see what happens when the law is applied to those facts. Juries, in turn,
have the job of finding which facts are accurate, which aren’t, and then
coming to a verdict, upon receiving instructions about the law from the
Court.

And that’s right where the confusion began in this case, IMO. The
original jury, to start with, likely had trouble distinguishing three
distinct things: the general concept of an API, the specification of the
API, and the implementation of an API. Plus, they were told by the judge
to assume API’s were copyrightable anyway. Then, it got more confusing
when they looked at two implementations of an API, parts of which looked
similar for purely mundane technical reasons, and assumed (incorrectly)
that textual copying from one file to another was the only way to get to
that same result. Meanwhile, the jury was likely further confused that
Google argued
various affirmative
defenses
against copyright
infringement in
the alternative
.

So, what happens with the Appeals Court? The Appeals court, of course,
has no reason to believe the finding of fact of the jury is wrong, and it’s
simply not the appeals court’s job to replace the original jury’s job, but to
analyze the matters of law decided by the lower court. That’s why I’m
admittedly troubled and downright confused that the ruling from the Appeals
court seems to conflate the issue of literal copying of text and
similarities in independently developed text. That is a factual issue in
any given case, but that question of fact is the central nuance to API
copyrightiable and it seems the Appeals Court glossed over it. The Appeals
Court simply fails to distinguish between literal cut-and-paste copying
from a given API’s implementation and serendipitous similarities that are
likely to happen when two API implementations support the same API.

But that error isn’t the interesting part. Of course, this error is a
fundamental incorrect assumption by the Appeals Court, and as such the
primary ruling are effectively conclusions based on a hypothetical fact
pattern and not the actual fact pattern in this case. However, after
poring over the decision for hours, it’s the only error that I found in
the appeals ruling. Thus, setting the fundamental error aside, their
ruling has some good parts. For example, I’m rather impressed and swayed
by their argument that the lower court misapplied the merger doctrine
because it analyzed the situation based on the decisions Google had with
regard to functionality, rather than the decisions of Sun/Oracle. To
quote:

We further find that the district court erred in focusing its merger analysis
on the options available to Google at the time of copying. It is
well-established that copyrightability and the scope of protectable activity
are to be evaluated at the time of creation, not at the time of infringement.
… The focus is, therefore, on the options that were available to
Sun/Oracle at the time it created the API packages.

Of course, cropping up again in that analysis is that same darned
confusion the Court had with regard to copying this declaration code. The
ruling goes on to say: But, as the court acknowledged, nothing prevented
Google from writing its own declaring code, along with its own implementing
code, to achieve the same result.

To go back to my earlier point, Google likely did write their own
declaring code, and the code ended up looking the same as the
other code, because there was no other way to implement the same API.

In the end, Mark J. Wielaard put it best when he read the decision,
pointing out to me that the Appeals Court seemed almost angry that the jury
hung on the fair use question. It reads to me, too, like Appeals Court is
slyly saying: the right affirmative defense for Google here is fair use,
and that a new jury really needs to sit and look at it.

My conclusion is that this just isn’t a decision about the copyrightable
of APIs in the general sense. The question the Court would need to
consider to actually settle that question would be: “If we believe an
API itself isn’t copyrightable, but its implementation is, how do we figure
out when copyright infringement has occurred when there are multiple
implementations of the same API floating around, which of course have
declarations that look similar?” But the court did not consider that
fundamental question, because the Court assumed (incorrectly)
there was textual cut-and-paste copying. The decision here, in my
view, is about a more narrow, hypothetical question that the Court decided
to ask itself instead: “If someone textually copies parts of your API
implementation, are
merger
doctrine
, scènes
à faire
,
and de
minimis
affirmative defenses like to succeed?“ In this
hypothetical scenario, the Appeals Court claims “such defenses rarely help you, but
a fair use defense might help you”.

However, on this point, in my copyleft-defender role, I don’t mind this
decision very much. The one thing this decision clearly seems to declare
is: “if there is even a modicum of evidence that direct textual
copying occurred, then the alleged infringer must pass an extremely high
bar of affirmative defense to show infringement didn’t occur”. In most GPL violation cases,
the facts aren’t nuanced: there is always clearly an intention to
incorporate and distribute large textual parts of the GPL’d code (i.e., not
just a few function declarations). As such, this decision is probably good
for copyleft, since on its narrowest reading, this decision upholds the
idea that if you go mixing in other copyrighted stuff, via copying and
distribution, then it will be difficult to show no copyright infringement
occurred.

OTOH, I suspect that most pundits are going to look at this in an overly
contrasted way: NDCA said API’s aren’t copyrightable, and the Appeals Court
said they are. That’s not what happened here, and if you look at the
situation that way, you’re making the same kinds of oversimplications that
the Appeals Court seems to have erroneously made.

The most positive outcome here is that a new jury can now narrowly
consider the question of fair use as it relates to serendipitous similarity
of multiple API function declaration code. I suspect a fresh jury focused
on that narrow question will do a much better job. The previous jury had
so many complex issues before them, I suspect that they were easily
conflated. (Recall that the previous
jury considered
patent questions as well
.) I’ve found that people who haven’t spent
their lives training (as programmers and lawyers have) to delineate complex
matters and separate truly unrelated issues do a poor job at such. Thus, I
suspect the jury won’t hang the second time if they’re just considering the
fair use question.

Finally, with regard to this ruling, I suspect this won’t become
immediate, frequently cited precedent. The case is remanded, so a new jury
will first sit down and consider the fair use question. If that jury finds
fair use and thus no infringement, Oracle’s next appeal will be quite weak,
and the Appeals Court likely won’t reexamine the question in any detail.
In that outcome, very little has changed overall: we’ll have certainty that
API’s aren’t copyrightable, as long as any textual copying that occurs
during reimplementation is easily called fair use. By contrast, if the new
jury rejects Google’s fair use defense, I suspect Google will have to
appeal all the way to SCOTUS. It’s thus going to be at least two years
before anything definitive is decided, and the big winners will be wealthy
litigation attorneys — as usual.

0This is of course true
for any sufficiently simple programming task. I used to be a high-school
computer science teacher. Frankly, while I was successful twice in detecting
student plagiarism, it was pretty easy to get false positives sometimes. And
certainly I had plenty of student programmers who wrote their function
declarations the same for the same job! And no, those weren’t the
students who plagiarized.

АСТА е мъртва, да живее АСТА?

Post Syndicated from Selene original https://nookofselene.wordpress.com/2012/07/05/acta-in-bulgaria-again/

Вчера хората, които излязохме през зимата да протестираме срещу АСТА, официално получихме това, което искаме – Европейският парламент отхвърли ратифицирането на така нареченото търговско споразумение за борба с фалшифицирането.
Това се случи след като стотици хиляди европейци изпълниха европейските площади и протестираха срещу АСТА и срещу така наречената „борба с пиратството“, в името на която се готвеше окупиране на Интернет – но не от движението „Окупирай Уолстрийт“, а от същите корпорации, които вече са окупирали почти всичко, намиращо се оффлайн и бързат да завземат и онлайн пространството.
Сред тези европейци бяхме и ние. На 11-ти февруари многохилядно шествие скандира „НЕ на ACTA“ по улиците на София и изпълни целия площад пред парламента, принуждавайки управляващите да обещаят, че ще „приемат споразумението с резерви“, а именно без частта за следенето на Интернет. Крайно недостатъчно, защото това споразумение или се приемаше цялото или не се приемаше цялото (да не говорим, че имаше ужасно гнили неща и сред незасягащите Интернет), но – забележете – поеха ангажимент да не осъществяват това следене на Интернет.
Сега, след като Европарламентът сложи край на цялото споразумение, би трябвало да си отдъхнем? Уви, не.
Защото проектът за нов Наказателен кодекс на България е предвидил нови драконовски мерки. Минимална предвидена присъда за т.нар. „пиратство“ е 1 година затвор или пробация, присъдата за масовия случай се вдига от 5 на 6 години, т.е. става тежко престъпление, щом е над 5 години затвор. Това означава, че „пиратстството“ се наказва в някои случаи по-строго от престъпления като изнасилване или от убийство по непредпазливост. Отпадат и административните наказания за „маловажни“ случаи – заменят се директно със затвор или пробация.
Ще цитирам конкретните членове от проекта за нов НК. Целият можете да прочетете тук.

Ползване на чужда интелектуална собственост
Чл. 195. (1) Който противозаконно записва или използва по какъвто и да е начин предмет по чл. 193 без съгласието на носителя на съответното право, се наказва с лишаване от свобода до пет години и с глоба.
(2) Който противозаконно държи носители на предмет по чл. 193 в големи размери или в голямо количество, или държи матрица за възпроизвеждане на такива носители, се наказва с лишаване от свобода от две до пет години и с глоба не по-малко от две хиляди лева.
(3) Когато предметът по ал. 2 е в особено големи размери, наказанието е лишаване от свобода от две до осем години и глоба от три хиляди до петнадесет хиляди лева, като съдът може да наложи и конфискация до една втора от имуществото на дееца.
(4) Когато с деянието по ал. 1 – 3 са причинени значителни вредни последици, наказанието е:
1. в случаите по ал. 1 или 2 – лишаване от свобода от една до шест години и глоба от три хиляди до десет хиляди лева;
2. в случаите по ал. 3 – лишаване от свобода от три до десет години, глоба от пет хиляди до двадесет хиляди лева и конфискация на част или на цялото имущество на дееца.
(5) Когато деянието по ал. 1 или 2 представлява маловажен случай, наказанието е лишаване от свобода до една година или пробация.
(6) Предметът на престъплението по ал. 2 и 3 се отнема в полза на държавата и се унищожава.

Извод 1 – ACTA официално е отхвърлена от цялата Европейска общност, но нашите управляващи са решили да си направят българска АCTA.
Извод 2 (нищо ново) – на думите на управляващите в България не може да се вярва.
Извод 3 – в името на интересите на малцина, се правят свръхнаказания и свръхмерки за ограничаване на свободата на информация и свободата в Интернет като цяло на всички останали. Защото както от опит знаем, борбата с пиратстото не се изчерпва само със защитаване на правата на (евентуално и хипотетично) ощетени творци. Обикновено тя бързо се изражда в перфектното оръжие срещу свободата на словото. И без този Наказателен кодекс все още да действа такива случаи вече има, просто без наказание за нещастния човек, който си е позволил да изкаже критика.
Извод 4 – ако искаме да спрем тази лудост, ще трябва отново да протестираме, отново за същото нещо. Имам чувството, че разчитат на нашата късопаметност, разсеяност и умора. Че очакват да ни писне, да вдигнем рамене и да кажем „Правете каквото искате, майната ви!!“. Само че аз не мисля, че това ще се случи.
А вие?

Everyone in USA: Comment against ACTA today!

Post Syndicated from Bradley M. Kuhn original http://ebb.org/bkuhn/blog/2011/02/15/acta.html

In the USA, the deadline for comments on ACTA
is today (Tuesday 15 February 2011) at 17:00 US/Eastern.
It’s absolutely imperative that every USA citizen submit a comment on
this. The Free
Software Foundation has details on how to do so
.

ACTA is a dangerous international agreement that would establish
additional criminal penalties, promulgate DMCA/EUCD-like legislation
around the world, and otherwise extend copyright law into places it
should not go. Copyright law is already much stronger than
anyone needs.

On a meta-point, it’s extremely important that USA citizens participate
in comment processes like this. The reason that things like ACTA can
happen in the USA is because most of the citizens don’t pay attention.
By way of hyperbolic fantasy, imagine if every citizen of the
USA wrote a letter today to Mr. McCoy about ACTA. It’d be a news story
on all the major news networks tonight, and would probably be in the
headlines in print/online news stories tomorrow. Our whole country
would suddenly be debating whether or not we should have criminal
penalties for copying TV shows, and whether breaking a DVD’s DRM should
be illegal.

Obviously, that fantasy won’t happen, but getting from where we are to
that wonderful fantasy is actually linear; each person who
writes to Mr. McCoy today makes a difference! Please take 15 minutes
out of your day today and do so. It’s the least you can do on this
issue.

The Free
Software Foundation has a sample letter you can use
if you don’t
have time to write your own. I wrote my own, giving some of my unique
perspective, which I include below.

The automated
system on regulations.gov
assigned this comment below the tracking
number of 80bef9a1 (cool, it’s in hex! 🙂

Stanford K. McCoy
Assistant U.S. Trade Representative for Intellectual Property and Innovation
Office of the United States Trade Representative
600 17th St NW
Washington, DC 20006

Re: ACTA Public Comments (Docket no. USTR-2010-0014)

Dear Mr. McCoy:

I am a USA citizen writing to urge that the USA not sign
ACTA. Copyright law already reaches too far. ACTA would extend
problematic, overly-broad copyright rules around the world and would
increase the already inappropriate criminal penalties for copyright
infringement here in the USA.

Both individually and as an agent of my employer, I am regularly involved
in copyright enforcement efforts to defend the Free Software license
called the GNU General Public License (GPL). I therefore think my
perspective can be uniquely contrasted with other copyright holders who
support ACTA.

Specifically, when engaging in copyright enforcement for the GPL, we treat
it as purely a civil issue, not a criminal one. We have been successful
in defending the rights of software authors in this regard without the
need for criminal penalties for the rampant copyright infringement that we
often encounter.

I realize that many powerful corporate copyright holders wish to see
criminal penalties for copyright infringement expanded. As someone who
has worked in the area of copyright enforcement regularly for 12 years, I
see absolutely no reason that any copyright infringement of any kind ever
should be considered a criminal matter. Copyright holders who believe
their rights have been infringed have the full power of civil law to
defend their rights. Using the power of government to impose criminal
penalties for copyright infringement is an inappropriate use of government
to interfere in civil disputes between its citizens.

Finally, ACTA would introduce new barriers for those of us trying to
change our copyright law here in the USA. The USA should neither impose
its desired copyright regime on other countries, nor should the USA bind
itself in international agreements on an issue where its citizens are in
great disagreement about correct policy.

Thank you for considering my opinion, and please do not allow the USA to
sign ACTA.

Sincerely,
Bradley M. Kuhn

Dear Lazyweb!

Post Syndicated from Lennart Poettering original http://0pointer.net/blog/mexico-lamp.html

Let’s see how well Lazyweb works for me!

One of the nicest types of lamps I know is depicted on this photo:

mexico lamp

This lamp is built from a number (16 or so, it’s so difficult to count) of
identical shapes which are put together (a mano) in a very simple, mathematical
fashion. No glue or anything else is need to make it a very robust object. The
lamp looks a little bit like certain Julia fractals, its geometrical structure
is just beautiful. Every mathematical mind will enjoy it.

This particular specimen has been bought from a street dealer in Mexico
City, and has been made of thin plastic sheets. I saw the same model made from
paper on a market near Barcelona this summer (during GUADEC). Unfortunately I
didn’t seize the chance to buy any back then, and now I am regretting it!

I’ve been trying to find this model in German and US shops for the last
months (Christmas is approaching fast!) but couldn’t find a single specimen. I
wonder who designed this ingenious lamp and who produces it. It looks like a
scandinavian design to me, but that’s just an uneducated guess.

If you have any information about this specific lamp model, or could even
provide me with a pointer where to buy or how to order these lamps in/from
Germany, please leave a comment to this blog story, or write me an email to
mzynzcr (at) 0pointer (dot) de! Thank you very much!

Dear Lazyweb!

Post Syndicated from Lennart Poettering original http://0pointer.net/blog/mexico-lamp.html

Let’s see how well Lazyweb works for me!

One of the nicest types of lamps I know is depicted on this photo:

mexico lamp

This lamp is built from a number (16 or so, it’s so difficult to count) of
identical shapes which are put together (a mano) in a very simple, mathematical
fashion. No glue or anything else is need to make it a very robust object. The
lamp looks a little bit like certain Julia fractals, its geometrical structure
is just beautiful. Every mathematical mind will enjoy it.

This particular specimen has been bought from a street dealer in Mexico
City, and has been made of thin plastic sheets. I saw the same model made from
paper on a market near Barcelona this summer (during GUADEC). Unfortunately I
didn’t seize the chance to buy any back then, and now I am regretting it!

I’ve been trying to find this model in German and US shops for the last
months (Christmas is approaching fast!) but couldn’t find a single specimen. I
wonder who designed this ingenious lamp and who produces it. It looks like a
scandinavian design to me, but that’s just an uneducated guess.

If you have any information about this specific lamp model, or could even
provide me with a pointer where to buy or how to order these lamps in/from
Germany, please leave a comment to this blog story, or write me an email to
mzynzcr (at) 0pointer (dot) de! Thank you very much!