When Armando Solar-Lezama was a third grader in Mexico City, his science class did a unit on electrical circuits. The students were divided into teams of three, and each team member had to bring in a light bulb, a battery, or a switch.
Solar-Lezama, whose father worked for an electronics company, volunteered to provide the switch. Using electrical components his father had brought home from work, Solar-Lezama built a “flip-flop” circuit and attached it to a touch-sensitive field effect transistor. When the circuit was off, touching the transistor turned it on, and when it was on, touching the transistor turned it off. “I was pretty proud of my circuit,” says Solar-Lezama, now an MIT professor of electrical engineering and computer science.
By the time he got to school, however, one of his soldered connections had come loose, and the circuit’s performance was erratic. “They failed the whole group,” Solar-Lezama says. “And everybody was like, ‘Why couldn’t you just go to the store and get a switch like normal people do?’”
The next year, in an introductory computer science class, Solar-Lezama was assigned to write a simple program that would send a few lines of text to a printer. Instead, he wrote a program that asked the user a series of questions, each question predicated on the response to the one before. The answer to the final question determined the text that would be sent to the printer.
This time, the program worked perfectly. But “the teacher failed me because that’s not what the assignment was supposed to be,” Solar-Lezama says. “The educational system was not particularly flexible.”
At that point, Solar-Lezama abandoned trying to import his extracurricular interests into the classroom. “I sort of brushed it off,” he recalls. “I was doing my own thing. As long as school didn’t take too much of my time, it was fine.”
So, in 1997, when Solar-Lezama’s father moved the family to College Station, Texas — the Mexican economy was still in the throes of the three-year-old Mexican peso crisis — the 15-year-old Armando began to teach himself calculus and linear algebra.
Accustomed to the autonomy of living in a huge city with a subway he could take anywhere, Solar-Lezama bridled at having to depend on rides from his parents to so much as go to the library. “For the first three years that I was in Texas, I was convinced that as soon as I turned 18, I was going to go back to Mexico,” he says. “Because what was I doing in this place in the middle of nowhere?” He began systematically educating himself in everything he would need to ace the Mexican college entrance exams.
At his Texan high school, however, he was placed by default in the lowest of the school’s three academic tracks, which is where most immigrants with imperfect English found themselves. Against the recommendations of the school administrators, he insisted on taking physics; within two weeks, his physics teacher had moved him up to a higher-level class.
By his junior year, Solar-Lezama was enrolled in the most demanding math and science classes the school offered, in most of which his classmates were seniors. But in the humanities, where he still struggled with the language — and, he admits, his own lack of interest — he remained on the lower track.
“In the time I was there, I got to move from one track to the other,” Solar-Lezama says. “It was really shocking to realize how different these tracks were.”
Outside the classroom, Solar-Lezama was a member of a team that finished second in the nation in the Department of Energy’s Science Bowl competition. He also won a regional science fair held at Texas A&M with a computer simulation he’d whipped up in an afternoon, when he and some friends realized that they wouldn’t be able to get a scrap-built hovercraft working by the fair deadline. And he started working for a local software startup, doing database coding.
But inside the classroom, “my record was very bimodal,” he says. Though he excelled in math and science, he ended his senior year ranked only about 100th in a class of 400.
Still, he decided to put his return to Mexico on hold. “By the time I was a senior in high school, I sort of found my place,” he says. “I was learning lots of things that I was interested in, and I decided that, ‘Okay, maybe I’ll stay here for college, and then I’ll go back.’”
His spotty academic performance, however, was an obstacle. MIT was one of several universities that denied him undergraduate admission. But the father of one of his Science Bowl teammates taught nuclear engineering at Texas A&M and, recognizing Solar-Lezama’s talent, encouraged him to apply for a generous scholarship offered through the department.
To ensure that international students could navigate the transition to a new educational system and, often, a new language, the university restricted the number of units they could carry as freshmen, and Solar-Lezama, his three years of American high school notwithstanding, counted as an international student. So to keep himself busy, he audited several courses outside the nuclear-engineering curriculum.
One of these was Introduction to Algorithms. Although he wasn’t formally enrolled at the time, Solar-Lezama did all the homework and took all the exams, and he ended up with the highest grade in the class.
“Before that point, I thought of programming as a useful skill,” Solar-Lezama says. “One of the things that really excited me about this class was that you could prove things about algorithms and get some guarantees about how something is going to work, and I found that extremely appealing. So I decided to switch majors to computer science.”
Graduating in three years, Solar-Lezama decided to postpone his return to Mexico a little longer, applying to graduate programs at MIT, Carnegie Mellon University, and the University of California at Berkeley. “I thought, if I don’t get in to any of them, fine, I’ll go back to Mexico,” he says. Once again, MIT turned him down, as did CMU. But he got into Berkeley.
Solar-Lezama arrived at Berkeley planning to continue his work on large parallel computing systems, but his conversations with his advisor, Ras Bodik, quickly took a different turn. Different types of simulations generally required different computational strategies. But implementing those strategies often required reshuffling the same low-level processes. Was it possible, Bodik and Solar-Lezama wondered, to devise a way to formulate the strategies broadly and automate the reshuffling?
Solar-Lezama thus found himself part of a small community of researchers working on “program synthesis,” or the automatic generation of computer programs. His thesis project was a language called Sketch, which lets programmers describe program functionality in general terms and automatically fills in the computational details.
Sketch treats program synthesis as a search problem: The task is to search the space of all possible programs for one that can meet the requirements imposed by the general description. The chief innovation behind Sketch was a set of algorithms for rapidly paring down the search space, so that a satisfactory program could be found in real time.
“There were three or four of us who were pushing this area and telling everybody who would listen that this was the right direction for programming systems research, and for a long time there was a lot of hostility toward these kinds of ideas,” Solar-Lezama says. “Little by little, we started converting a few more people, and all of a sudden they reached a critical mass, and now it’s an extremely active area of research.”
After graduating from Berkeley, Solar-Lezama went on the job market, and MIT finally made him an offer. In his seven years at the Institute, where he recently earned tenure, Sketch has remained the foundation of his research, which has developed along three parallel tracks.
The first track is the extension of Sketch, so that it can handle more diverse and complex computations. The second is the application of Sketch and its underlying machinery to particular problems — such as orienting new members of large programming teams toward the existing code base, automatically grading programming homework, and parallelizing code for faster execution on multicore chips.
Recently, Solar-Lezama’s group has also begun investigating the application of program synthesis to machine learning. Machine learning involves teaching a computer system to perform some classification task by presenting it with training examples. But suppose that the training data consists of a row of three squares and a row of three circles. Which image belongs to the same class, a row of three stars or four circles arranged in a square?
Existing machine-learning systems are good at learning to recognize circles from examples of circles, but they’re not as good at the kind of abstract pattern matching that humans do intuitively. A program synthesizer, however, is much more likely to converge on a program for producing three-object rows than one that sometimes produces rows and sometimes produces squares.
Having finally made it to city with a good subway system, Solar-Lezama no longer has any plans to move back to Mexico. His wife has a Mexican father and spent much of her childhood in Mexico, but her mother is from Minnesota, and she had planned on settling in the U.S. when she and Solar-Lezama met in Berkeley. Their children, ages 6 and 3, might also find it hard to adjust to life in Mexico. Although they speak Spanish exclusively at home, they speak English at their school in Medford, Massachusetts, and, says Solar-Lezama, “they’re developing a Boston accent.”