Smalltalk - gregorymorrison/euler1 GitHub Wiki

Smalltalk is the first Object-Oriented language. Introduced in 1972, it was widely regarded at the time as a great language, but due to various circumstances time has passed it by. In Smalltalk, everything is an object, and every communication between objects is a message. Here is a version of Euler1 in which I extend the parent class Integer to include a new method - a Haskell-style algorithm. It has an range iterator with self as its upper bound, and here the caret is a return operator:

"Euler1 in Smalltalk"

Integer extend [
    Euler1 [
        ^ ((1 to: self)
            select: [:x | ((x \\ 3) = 0 or: [(x \\ 5) = 0])])
            fold: [ :x :y | x + y ]
    ]
]

(999 Euler1) displayNl

Since everything is an object, my algorithm has to inherit from some parent class. I chose class Integer, since the result will be an integer. It feels like an abuse of design, but it works fine. Any Smalltalkers out there know if this is good or bad design? Smalltalk's overall feel is pretty weird, though it's strict purity is attractive. The last line above has the method Euler1 being a message sent to class instance 999. The integer's instantiation returns a value which is then sent as a message to the IO routine displayNl. Everything is chained together in this manner.

Since everything in Smalltalk is an object, even standalone functions must be construed as objects - called blocks. Here is Euler1 as a block which implements the brute-force solution of looping through numbers manually and checking each one. The default return value of a block is the value evaluated on the last line:

"Euler1 in Smalltalk"

Euler1 := [ :size | 
    result := 0.

    0 to: size do: [:i |
        (i \\ 3 = 0 or: [i \\ 5 = 0])
        ifTrue: 
            [result := result + i].
    ].

    result.
].

(Euler1 value: 999) displayNl

Smalltalk has Functional programming constructs baked right in. Here are the canonical collect/select/inject; collect does nothing and is included only for illustration. Euler1 is a lambda- an anonymous function, though I happened to name it. One of the main points of Functional programming is that the program is deterministic – it will always return the same output for a given input. This is illustrated in the block Euler1 by the absence of any variable manipulation – there are instead only methods which return values. As a matter of fact, it's simply one statement - a bunch of methods chained together using parentheses:

"Euler1 in Smalltalk"

Euler1 := [ :size |
  (((1 to: size)
    collect: [:x | x])
      select: [:x | ((x \\ 3) = 0 or: [(x \\ 5) = 0])])
        inject: 0 into: [:x :y | x + y]
].

(Euler1 value: 999) displayNl

Here’s a functional version that uses tail recursion with an accumulator. Tail recursion is a technique that allows an intelligent compiler to optimize its stack usage to be O(n) instead of O(n!). In English, this means that your program will probably not crash even for hugely recursive calls. Note here how arguments are passed to functions. The function instance is passed the message value with its value being the argument, and these are simply chained one after the other.

"Euler1 in Smalltalk"

Euler := [ :n :acc |
    (n = 1)
    ifTrue:
        [acc]
    ifFalse: [
        (n \\ 3 = 0 or: [n \\ 5 = 0])
        ifTrue: 
            [Euler value: (n-1) value: (acc+n)]
        ifFalse: 
            [Euler value: (n-1) value: acc].
    ].
].

Euler1 := [ :n | Euler value: n value: 0 ].

(Euler1 value: 999) displayNl

Here’s another version using a Quicksort-based algorithm. Here we recursively break the list up in half and then reassemble it. Instead of sorting each half, though, we’ll filter the pivot value, converting it to 0 if it’s not divisible. Here, Euler() returns Euler() calculated on the half of the list before the pivot element, Euler() calculated on the half of the list after the pivot element, and the pivot element or 0, all added together. This code demonstrates Smalltalk's range generation and array slicing. Arrays in Smalltalk are 1-based. Be careful with this code - Smalltalk's stack frames seem to not be isolated the way I expected. Calling Euler recursively for pre and post here actually affects the value of local variables pivotVal and i following it. To address this, I simply moved their definitions pre and post instead of before. This seems like a bug in Smalltalk, but I'll assume it's ignorance on my part.

This example actually fails - it appears that Smalltalk cannot handle this much recursion, and simply hangs for size=1000. Even for size=100, Smalltalk returns the correct result, although it still produces a cryptic error message. :

"Euler1 in Smalltalk"

Euler := [ :L |
    (L isEmpty)
    ifTrue:
        [ 0 ]
    ifFalse: [
        pivot := ((L size) // 2) max: 1.

        pre  := Euler value: (L copyFrom: 1 to: (pivot-1)).
        post := Euler value: (L copyFrom: (pivot+1) to: (L size)).

        pivotVal := L at: pivot.
        i := 0.
        (pivotVal \\ 3 = 0 or: [pivotVal \\ 5 = 0])
        ifTrue: 
            [i := pivotVal].

        i + pre + post.
    ].
].

Euler1 := [ :n | Euler value: (1 to: n) ].

(Euler1 value: 999) displayNl

Here's an elegant algorithm based on an observation by little Carl Friedrich Gauss. It operates in O(1) constant time. Don’t sweat it if this seems inscrutable; click the blog link above for an explanation.

"Euler1 in Smalltalk"

mySum := [ :n :size | 
    (((size//n) raisedTo: 2) + (size//n)) * n // 2
].

Euler1 := [ :size |
    (mySum value:  3 value: size) +
    (mySum value:  5 value: size) -
    (mySum value: 15 value: size)
].

(Euler1 value: 999) displayNl

This language was a bit of a headscratcher for me. It took about an hour each to figure out how to do simple things such as print an integer or define a function. And it took me several hours just to figure out how to return a goddamn value from a function. The compiler messages are just okay, and the compiler is quite unforgiving about syntax. For example, version one above compiles fine with no periods following the closing square brackets, while version two does not. Expect a bit of a learning curve. One of the things Smalltalk is known for is being a complete programming environment. It's not just an IDE - it's a complete windowing environment with its own text editor, GUI designer, etc. Normally if you want to write Smalltalk, you have to use its editor. Well, GNU has a version of Smalltalk - gnu-smalltalk, which lets you use Smalltalk's syntax and compiler on text files outside of an IDE. To run your code in gnu-smalltalk, simply invoke gst, passing it your code as an argument:

$ gst euler1.st
233168
$