50 PRINT “HAPPY BIRTHDAY”

I think BASIC’s greatest strength may be that it was something that many people — not just those with a particular background — could learn. There was no gatekeeper, either literally or figuratively: you didn’t have to push punchcards under a bank-teller window nor did you have to learn recursion before learning recursion. In the 80s, virtually every machine ran BASIC and learning how to login and start the interpreter was generally the hardest part of beginning to “program an X machine.”

People get drop-through imperative programming: either the line-by-line flexibility of BASIC or the blocks of FORTRAN and Flash (I didn’t understand Flash until I realized that it’s just FORTRAN with worse numerics and better graphics). You don’t have to be a born programmer to understand:

 10 PRINT "HELP! I AM CAUGHT IN A PROGRAM LOOP!"
 20 GOTO 10

I imagine that 95% of the people who got a passing grade in their BASIC programming class or typed in a few games from the back of COMPUTE! magazine never wrote themselves another program. But the 5% who did found that personal computers could help them in their job. And the 1-in-100 or 1-in-1000 who went beyond that found themselves in a community where only drive and talent mattered and credentials meant nothing.

I’m a college dropout and never took a CS course in my life. At 25 I was hired as Technical Editor for a magazine that specialized in Artificial Intelligence and for Computer Language, the best programming magazine of all time (as far as size or circulation goes, we were the “We Try Harder” Avis to Dr. Dobb’s Journal‘s Hertz).

Today, the design of programming languages is discussed at sites like Lambda the Ultimate and while I can muddle through even some of the more arcane papers, and while I understand the value of a dense, high signal-to-noise ratio on certain topics, it seems to me that there’s not nearly enough reflection on the market triumphs of popular languages. I’m not advocating a return to the line-numbered BASIC interpreters (single-threaded, as if that had to be mentioned!) of my youth, but I am saying that 50 years ago, Kemeny, Kurtz, and colleagues captured lightning in a bottle. So did Dan Bricklin, inventor of the computerized spreadsheet, another tool for manipulating data and calculations that empowered an audience vastly larger than that emerging from the bottleneck of “Computer Science courses at good universities.”

I’m not suggesting that marketshare is the only, or even dominant, factor in assessing a language’s quality. In the case of JavaScript, for instance, I see an example of the contingent nature of history, as discussed in Steven Jay Gould’s classic Wonderful Life. JavaScript is a market triumph, it behooves all professional programmers to master it, but I think it’s fair to say that it has some flaws as a programming language.

Nor am I saying that there’s not a lot of discussion of “beginner’s languages.” I volunteer at a local school and am tremendously impressed by Scratch, for instance. Because Scratch is accessible at such a young age, it may generate the same kind of nostalgia that some of us share for BASIC. But I don’t suspect that it will have the truly broad, industry-expanding impact of BASIC or Flash.

Today, there’s some talk of functional programming sweeping over the industry in the same way that object-orientation did in the early 1990s. I am not a functional programming True Believer, but I truly believe that functional programming has advantages. And it seems to me that languages such as F# on the CLR and Scala on the JVM have a “you can have it all” aspect (no-hassle availability of libraries, the ability to integrate with legacy code, object-functional hybrid type-systems) that at the very least make them appealing to some teams.

But, although perhaps not as broadly accessible as line numbers and GOTO, OOP has something of BASIC’s “learnability.” We can teach OOP to a lot of people, without a lot of preliminaries. And some will struggle through, and some will have a comfortable understanding, and some will have taken a step towards design and architecting large systems. With Functional Programming, it’s not as clear to me that there’s that same “muddle through” path. It’s hard for me to imagine a better introduction to functional ideas than the early chapters of Structure and Interpretation of Computer Programs, but I think of that as a text that weeds out, not one that expands the base. If you’re a natural-born programmer with a semester in front of you SICP is a great book. But if you “just” have potential or are a working developer with a “where does this help my day-to-day problems?” pragmatism, I don’t know what you should read.

Goto 10

BASIC was the first programming language for most of those in my generation. We sat in front of green- and amber-texted monitors or machines that spooled seemingly infinite reams of paper. We typed on chiclet keys and teletypes, punched papertape and cards and threaded magnetic reels. Compared to today’s machines we had indistinguishable-from-0 working memory or horsepower.

You have no idea how fun it was.

Getting To Know Scala: Project Euler Primes

Prime numbers are not my thing, but generating them is a common task in the early Project Euler problems. The one algorithm I know for generating primes is the Sieve of Eratosthenes, which I defined in Scala as:

[sourcecode lang=”scala”]
def successor(n : Double) : Stream[Double] = Stream.cons(n, successor(n + 1))

def sieve(nums : Stream[Double]) : Stream[Double] = Stream.cons(nums.head, sieve ((nums tail) filter (x => x % nums.head != 0)) )

val prime_stream = sieve(successor(2))
[/sourcecode]

The first function is the only function that I’ve ever written that I’m sure is properly “functional.” It’s stuck in my head from circa 1982 LISP. It uses Scala’s Stream class, which is like a List but is “lazily evaluated,” in other words, it only calculates the next value in the List when it’s needed (the Stream pattern is to create a List whose head is the next value and whose tail is a recursive call that, when executed will produce the next value).

The 2nd function sieve is my take on the Sieve of Eratosthenes. It too returns a Stream of primes. (By the way, the reason I use Double rather than an Int or Long is that one of the early Project Euler problems involves a prime larger than LONG_MAX.)

In case you’re not familiar with the algorithm, the Sieve is conceptually simple. Begin with a list containing all positive integers starting at 2 (the first prime) [2, 3, 4, …] . Remove from the list every multiple of your current prime. The first number remaining is the next prime. For instance, after removing [2, 4, 6, … ], the first number remaining is 3. Prime! So remove [3, 6 (already removed), 9, … ]. Since 4 was removed as a multiple of 2, the next available is 5. Prime! Remove [5, 10 (already removed), 15 (already removed), …] …

The 7th Project Euler problem is “What is the 10001st prime number?” Unfortunately,

[sourcecode]
scala> prime_stream take 10001 print
2.0, 3.0, 5.0, 7.0, …SNIP … 29059.0, 29063.0, java.lang.OutOfMemoryError: Java heap space
at scala.Stream$cons$.apply(Stream.scala:62)
at scala.Stream.filter(Stream.scala:381)
at scala.Stream$$anonfun$filter$1.apply(Stream.scala:381)
at scala.Stream$$anonfun$filter$1.apply(Stream.scala:381)
at scala.Stream$cons$$anon$2.tail(Stream.scala:69)
at scala.Stream$$anonfun$filter$1.apply(Stream.scala:381)
at scala.Stream$$anonfun$…
[/sourcecode]

That will never do. Obviously, I could run Scala with more heap space, but that would only be a bandage. Since a quick Google search shows that the 1000th prime number is 104,729 and I’m running out of heap space near 30K, it seems that “messing around with primes near the 10Kth mark” requires some memory optimization.

Converting the Sieve

If I really wanted to work with very large sequences of primes, I should certainly move away from the Sieve of Eratosthenes. But I’m not really interested in prime number algorithms, I’m interested in the characteristics of the Scala programming language, so I’m going to intentionally ignore better algorithms.

My first thought was “OK, I’ll allocate a chunk of memory and every time I find a prime, I’ll set every justFoundPrime-th bit to 1.” But that would depend upon my allocated memory being sufficient to hold the nth prime. With my Google-powered knowledge that the 10001st prime is only 100K or so, that would be easy enough, but (a) it seemed like cheating and (b) it would require a magic number in my code.

My next thought was “OK, when I run out of space, I’ll dynamically allocate double the space– no, wait, I only need justFoundPrime-(2 * justFoundPrime) space, since I’ve already checked the numbers up to justFoundPrime.”
My next thought was “And really I only need half that space, since I know 2 is a prime and I can just count by 2…And, y’know, I know 3 is prime too, so I can check–” At which point, I engaged in a mental battle over what was appropriate algorithmic behavior.

On the one hand, I didn’t want to change algorithms: if I moved from the Sieve to a slightly better algorithm, then wasn’t it Shameful not to move to at least a Quite Good algorithm? On the other hand, the instant I opened the door to allocating new memory, I committed to keeping around the list of already-discovered primes, since I would have to apply that list to my newly-allocated memory. But if you have a list of numbers, checking if your candidate number is a multiple of any of them can be done without consuming any additional memory. But is it the same algorithm? Isn’t the Sieve fundamentally about marking spots in a big array?

Finally, I decided that checking a candidate number against the list of already-discovered primes was the Sieve algorithm, just with a smallest possible amount of memory allocation — one number. (By the way, did you read the article in which scientists say that rational thought is just a tool for winning arguments to which you’re already emotionally committed?)

Here then, is what I wrote:

[sourcecode lang=”scala”]
def multiple_of = (base : Long, target : Long) => target % base == 0;

val twoFilter = multiple_of(2, _ : Long)
val threeFilter = multiple_of(3, _ : Long)

println(twoFilter(4))
println(twoFilter(5))
println(twoFilter(6))
println(threeFilter(4))
println(threeFilter(5))
println(threeFilter(6))
[/sourcecode]

The first function multiple_of is a function literal (?) that returns true if the target is a multiple of the base. The next two lines, where I define twoFilter and threeFilter are  an example of the functional idiom of partial function application (I think — “currying” is the use of partial function application to accomplish a goal, right?).

This is an undeniably cool feature of functional languages. Without any fuss, these lines create new functions that require one less argument to have their needed context. Once you have a twoFilter, you don’t need to keep the value “2” around to pass in. Which might not seem like a big win, since a function named twoFilter or threeFilter is no more compact than calling multiple_of(2, x) or multiple_of(3,x). But…

[sourcecode lang=”scala” firstline=”12″]
def filter = (x : Long) => multiple_of(x, _ : Long);

val fs = List(filter(2), filter(3))
for(f <- fs){
println("Eight is a multiple of this filter: " + f(8))
}
[/sourcecode]

OK, now that’s nice and compact! Now we have a new tk function literal? tk called filter and rather than have a bunch of variables called twoFilter and threeFilter and fiveFilter, we just have a List of filters. With such a list in hand, it’s easy to figure out which numbers in a list are relatively prime:

[sourcecode lang=”scala” firstline=”18″]
def relatively_prime(fs : List[(Long)=>Boolean], target : Long) : Boolean = {
for(f <- fs){
if(f(target)){
return false;
}
}
return true;
}

println("4 is prime? " + relatively_prime(fs, 4))
println("5 is prime? " + relatively_prime(fs, 5))

val list = List[Long](2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
println(list.map(relatively_prime(fs, _)))

[/sourcecode]

Which leads to a simple recursive function to find the next prime:

[sourcecode lang=”scala” firstline=”32″]
def next_prime(fs : List[(Long)=>Boolean], x : Long) : Long = {
if (relatively_prime(fs, x)) {
return x
}
return next_prime(fs, x + 1)
}

println(next_prime(fs, 4))
println(next_prime(fs, 8))
[/sourcecode]

Which leads to our solution:

[sourcecode lang=”scala” firstline=”41″]
def primes(fs : List[(Long)=>Boolean], ps: List[Long], x : Long, nth : Long) : List[Long] = {
if(ps.size == nth){
return ps;
}

val np = next_prime(fs, x)
val sieve = fs ::: List(filter(np));
primes(sieve, ps ::: List(np), np + 1, nth);
}

println("Missing 3 because its in fs" + primes(fs, List[Long](2L), 2, 8))
println((primes(List(filter(2)), List(2L), 2, 8) reverse) head)

def nth_prime(nth : Long) : Long = {
(
primes(
List(filter(2)),
List(2L),
2,
nth
) reverse
) head
}

println(nth_prime(8))
println("The 10001st prime is " + nth_prime(10001))
[/sourcecode]

Knowing Scala (Intermission)

I’m getting to the point in my Scala understanding where I’m making small commits to our Very Important Project at work. I ended up wasting four hours of work the other day because I put stuff in the wrong place and then spent a lot of time reorganizing things. In the context of FP, which puts such an emphasis on composition, “reorganizing” seems to this learner more tedious than reorganizing an OOP program.

Where to put your stuff” is a big deal for a programming paradigm, and it seems to me that OOP is significantly better than FP in guiding you towards structure. The FP proponents are always talking about keeping things small, but a real system is going to be large and it seems to me that OOP class structures provide a lot of guidance.

Since my organization has chosen Scala as our language, I can use OOP. But when you’re learning the FP mindset, there’s so much emphasis on compressing functions and minimizing your working set that it’s very natural to make a mistake, and write a series of functions that combine to do the operation at hand only to realize (as I did) that if only you had located the function over here, in this class, you could write fewer functions, with simpler combinations, to accomplish the same goal.

Hmm…

I always try to remember my experience learning OOP. I was a C programmer and had just been hired as the Product Review Editor at Computer Language Magazine. OOP was the hot new thing and I installed a brand new copy of Smalltalk/V 286 and diligently worked through the tutorial (which involved turtle graphics, as I recall). Everytime I had a few minutes I’d sit and try to understand “where the main() is.” And I just didn’t get it. I could type in code and it would work but I just had no idea how it was supposed to help my programming.

After about six weeks I was panicked, thinking “OMG, I don’t understand this subject that’s the topic of more and more of our articles.” I decided to break the shrink-wrap on Zortech C++ (the first C++ compiler for DOS) and simply use C and laugh knowingly every time someone mentioned OOP. And from almost the first minute of firing up the C++ compiler, I got objects. What had been obscure in a pure environment was crystal clear in a hybrid environment where what had seemed like obscure topics could be applied to the everyday challenges of writing C code.

And even more interesting, after working in C++ for awhile, when I fired up my Smalltalk environment again (perhaps for the Smalltalk/v 386 release), I absolutely loved it. It took C++ for me to understand the programming value of OOP and, once that was internalized, the environmental benefits of Smalltalk were many and obvious.

I try to keep this in mind with Scala. Right now, I’ll admit to not feeling enthusiastic about Scala. I’ve yet to feel “Oh, I couldn’t have done that in Ruby” while it seems like I bump into type-system limits and syntactical weirdness quite often (the type-erasure of generics in the JVM seems to mean that “finger typing” is not uncommon and I’ve yet to internalize Scala’s logic about parentheses, braces, and new-lines). But, if history is a guide, perhaps I’ll return to Ruby in a few months and suddenly say “OMG, in Scala I could just…”

We’ll see.

Knowing Scala: Exercise 1

Taking my own 15 Exercises to Know A Programming Language as a starting point for my exploration of Scala…

The first set of exercises are right up the alley of a language with pattern-matching and list-processing:

Write a program that takes as its first argument one of the words ‘sum,’ ‘product,’ ‘mean,’ or ‘sqrt’ and for further arguments a series of numbers. The program applies the appropriate function to the series.

The first thing I did was write the functions:

[sourcecode lang=”scala”]
val args = List(1, 2, 3, 4, 5)
args.foldLeft(0)(_+_) //Sum
args.foldLeft(1)(_*_) //Product
args.sort(_ < _)(if(args.length % 2 == 0) args.length / 2 – 1 else args.length / 2) //Median
args.map(Math.sqrt(_)) //Sqrt
[/sourcecode]

Here the list-processing functions (highlighted in red) shine. The foldLeft() family of functions, also known as reduce, inject, or aggregate, applies a predicate to the elements of a data structure, accumulating a value. It’s hard to imagine cleaner code than what we have for the ‘sum’ and ‘product’ challenges. Similarly, the map() function is similarly clean-as-a-whistle for the ‘sqrt’ challenge. The ‘median’ challenge I’m less thrilled about: Passing in a custom comparator predicate to sort() is lovely, but my fingers typed in the C-language ternary operator :? and I was sorry to find that Scala doesn’t have it.

A big win for Scala is that I typed these in the Read-Evaluate-Print-Loop aka interactive console rather than having to deal with the overhead of a ‘real’ program and a edit-compile-test loop.

Moving on, the complete program follows:

[sourcecode lang=”scala”]
object Main
{
def main(args : Array[String])
{
val argList = List.fromArray(args)
val op = opMatch(argList.head)
val numList = argList.tail.map(java.lang.Double.parseDouble(_))
val result = op(numList)
print(result)
}

def sum(args : List[Double]) : Double = { args.foldLeft(0.0)(_+_) }

def product(args : List[Double]) : Double = { args.foldLeft(1.0)(_*_) }

def median(args : List[Double]) : Double =
{
args.sort(_ < _)(if(args.length % 2 == 0) args.length / 2 – 1 else args.length / 2)
}

def sqrt(args : List[Double]) : List[Double] = { args.map(Math.sqrt(_)) }

def opMatch(arg : String) : (List[Double]) => Any =
{
arg match
{
case "sum" => return sum
case "product" => return product
case "median" => return median
case "sqrt" => return sqrt
_ => throw new java.lang.IllegalArgumentException("Unrecognized operator " + arg)
}
}
}
[/sourcecode]

Let’s see… The translation of the REPL code into functions was very straightforward, although I have to admit to being somewhat disappointed that I could not use a type more abstract than Double. I don’t know if I could define a trait and then apply it retroactively to types in the java.lang package.

opMatch() shows some functional goodness — it’s declared as a function that takes a String and return a function that takes a List of Doubles and returns Any kind of object.

I’m not sure if I could do something more precise for my needs, like “returns a Double or List[Double]”. The pattern-matching in opMatch() is nice but not advanced.

If you have any observations to share, please comment below…