TITLE: Special Numbers in a Simple Language AUTHOR: Eugene Wallingford DATE: September 20, 2018 4:44 PM DESC: ----- BODY: This fall I am again teaching our course in compiler development. Working in teams of two or three, students will implement from scratch a complete compiler for a simple functional language that consists of little more than integers, booleans, an if statement, and recursive functions. Such a language isn't suitable for much, but it works great for writing programs that do simple arithmetic and number theory. In the past, I likened it to an integer assembly language. This semester, my students are compiling a Pascal-like language of this sort that call Flair. If you've read my blog much in the falls over the last decade or so, you may recall that I love to write code in the languages for which my students write their compilers. It makes the language seem more real to them and to me, gives us all more opportunities to master the language, and gives us interesting test cases for their scanners, parsers, type checkers, and code generators. In recent years I've blogged about some of my explorations in these languages, including programs to compute Farey numbers and excellent numbers, as well as trying to solve one of my daughter's AP calculus problems. When I run into a problem, I usually get an itch to write a program, and in the fall I want to write it in my students' language. Yesterday, I began writing my first new Flair program of the semester. I ran across this tweet from James Tanton, which starts:
N is "special" if, in binary, N has a 1s and b 0s and a & b are each factors of N (so non-zero).So, 10 is special because:
return divides(count(1, to_binary(n)), n) and divides(count(0, to_binary(n)), n)Calling to_binary on the same argument is wasteful, but Flair doesn't have local variables, either. So I added one more helper to implement the design pattern "Function Call as Variable Assignment", apply_definition:
function apply_definition(binary_n : integer, n : integer) : booleanand called it from the program's main:
return apply_definition(to_binary(n), n)This is only the beginning. I still have a lot of work to do to implement to_binary, count and divides, using recursive function calls to simulate loops. This is another essential design pattern in Flair-like languages. As I prepared to discuss my new program in class today, I found bug: My divides test was checking for factors of binary_n, not the decimal n. I also renamed a function and one of its parameters. Explaining my programs to students, a generalization of rubber duck debugging, often helps me see ways to make a program better. That's one of the reasons I like to teach. Today I asked my students to please write me a Flair compiler so that I can run my program. The course is officially underway. -----