I refactored the previous solution and extracted such library functions, they could be useful in future:

I think for these algoritms, where we have to iterate through large lists of numbers, the laziness (e.g. in Haskell) would give slightly more elegant code at certain places.

The first problem solution now becomes:

For a list of divisors with length k the number of operations will be k*n. Actually, less than that because of shortcut (exists). Assuming k fixed and small, the complexity is still O(n). We could make use of the not yet written (create-numbers-list) function and filter that afterwards instead of the (create-filtered-numbers-list) function, but let us take less space in memory at once.

It took me quite a while to understand. Today I'm using a laptop with Windows, so here is solution for the windows-version of the PLT Scheme implementation. Under Linux it will not differ much. By the way, to use R6RS in PLT DrScheme you need to choose Module language (Ctrl+L) and write #!r6rs in the beginning of each program.

First, write your own library. I separated the function (divides?) from the previous program:

Second, save it under the path, for example, C:\Projects\projecteulersolutions\project-euler-lib.scm and, as it is explained in "C:\Program Files\PLT\doc\r6rs\Installing_Libraries.html", compile and install the library into collections folder by running the command (the first way explained there seems not to be working):

"C:\Program Files\PLT\plt-r6rs.exe" --install C:\Projects\projecteulersolutions\project-euler-lib.scm

Some files drop into the directory "C:\Users\User\AppData\Roaming\PLT Scheme\4.1.4\collects\project-euler-lib"

Third, you connect it to the program by replacing (import (rnrs)) clause with (import (rnrs) (project-euler-lib)). And, of course, delete (divides?) function form the top-level program body.

Fourth, before recompiling a library, don't forget to clean the folder:

rmdir /s /q "C:\Users\User\AppData\Roaming\PLT Scheme\4.1.4\collects\project-euler-lib"


Let us start with solutions to Project Euler problems. I will always start with brute-force solutions if those are possible and later on post optimized solutions. Every solution will be given in Scheme (R6RS) along with quick estimate of complexity. The reason for solving those problems is training myself in Scheme and, of course, fun.

Find the sum of all the multiples of 3 or 5 below 1000.

Solution:

This is the simplest straightforward approach. Backward-recursion is used, with tail-recursion optimization, which is obligatory for all Scheme implementations, will be transformed into iteration. Backward direction is to simplify a function signature (otherwise an extra parameter is needed).

The complexity is O(n), assuming the (mod) operation is atomic. More strictly, the number of operations is 2*n. By the way, in R5RS (mod) is called (remainder).

The most easy-to-use Scheme compiler/interpreter is PLT, simple IDE is included. Emerging the latest ebuild gives errors under -O3 optimization flag, I confirmed it at the bugtracker. The solution is to switch temporarily to -O2.

Nemerle is waiting, but it have to wait more, while I'm learning Scheme. I have a plan to solve some problems from Project Euler, first with brute-force (however, it is not always possible), then using smarter ways, and post some solutions here under the tags "projecteuler" and "scheme".

Another thing, I am setting up currently a Gentoo Linux system on my workstation, so, some postings about this will come under the tag "gentoo". One of the reasons to install it is an unexpected difficulty with SATA-drives under Windows. The motherboard (Asus M3N78-VM) supports SATA-devices in three modes: SATA (only three accessible), RAID and AHCI. The latest is preferable for me, as I need more than three drives.

It was understandable when WinXP 64-bits (I didn't try any 32-bits systems, as I need more than 4 Gb of RAM) refused to work in AHCI-mode despite all my tricks with this and that, particlularly, manufacturer's drivers embedding with the nLite tool. But when Vista x64 with proper drivers could not load after switching m/b into AHCI, I decided that it's time to try Linux again. I prefer Gentoo, one of the most hardcore distributions available.

Just updated the compiler and integration from revision 7860 to 8060. Had no chances to look carefully for changes in this big gap, only read the log, and what I noticed is the following.

Compiler: a fix for incremental rebuild (7883), which should preserve a bit more time while building now. Extension methods should be now externally visible (7893). Filter method for Hashtable is implemented (7917). Some tweaks for locations (7956, 7970, 7980, 7982), some changes for literals parsing (8045), those should be good for refactoring features. The integration is merged into the compiler trunk (8060)!

Integration: new batch for building appeared (7952). Highlights for tail calls (7967). Rename refactoring (7968 etc.): good work by Sergei Tulentsev, regardless of the feature maturity (I'll check it out later). 'Go to type' navigation feature (7969). Inline refactoring (7990), I'm already interested. Some WPF support (8017). April CTP (8018), currently the last, I guess. VS2005 support is dropped (8018), quite a decision, I'd rather say.

Building of the compiler (with help of Compiler\buildandreg.cmd) passed all the stages flawlessly. Compiling the integration (Compiler\VsIntegration\build_dev.cmd), there are warnings about circular dependencies, but as I remember, that's some glitch from the past that is not breaking anything, but hard to circumvent. In other respects the integration builds without obstacles, that's good.

Opening my pet project under VS2008 with an experimental hive ("C:\Program Files\Microsoft Visual Studio 9.0\Common7\IDE\devenv.exe" my-pet-project.sln /rootsuffix Exp /RANU)... success. Building... errors... obviously, some references fell off (referenced namespace 'System.Runtime.Serialization.Formatters.Soap' does not exist). Adding them back, compiling, success.

Jumping from Error List and Output windows to a source doesn't work now. Checking out Rename refactoring for a local variable: it's working, cool! Inline refactoring: doesn't work. Anyway, that's a good
startup. Ok, I'll proceed another day.

This blog will be devoted solely to my programming trials, in particularly with the Nemerle programming language and its integration subproject with Visual Studio. I have little time now for doing that, as I am currently a Ph.D. student in the Netherlands (mathematical physics), but I'm interested very much e.g. in implementing refactoring for Nemerle.

I already spent around a year (of leisurely work) for the Nemerle integration project and implemented for instance such features, as Find usages, Highlight symbol and a mini-framework for extensive testing of such stuff. Then I made a large break in playing with the integration (however, continuing with Nemerle itself) lasting up to now, and I'm planning to proceed with it, contributing from time to time.