Phillip Trelford's Array

POKE 36879,255

Finding least common multiples by prime factorization

Least Common Multiple on Wikipedia.

How well can the prime factorization method be expressed in F#? This is my first solution and just for fun:

open System
 
/// Generate sequence of all integer primes
let primes =
    let isPrime x =
        let rec test = function
            | 1 -> true
            | n -> if x % n = 0 then false else test (n-1)
        test (x/2)
    seq {        
        yield! [1;2;3;5;7]
        for n in 11..2..Int32.MaxValue do
            if isPrime n then yield n
        done
    }

/// Compute prime factors
/// <returns>
/// Sequence of prime number powers (x^y) as tuple of (x,y)
/// </returns>
let primefactors x =
    /// Compute prime factor
    let primefactor x =
        primes
        |> Seq.skip 1
        |> Seq.takeWhile (fun prime -> prime <= x)
        |> Seq.tryFind (fun prime -> (x % prime) = 0)
    /// Compute list of prime factors 
    let rec fold acc x =
        match primefactor x with
        | Some factor -> fold (factor::acc) (x/factor)
        | None -> acc
    fold [] x
    |> Seq.countBy (fun x -> x)
    
/// Compute lowest common multiple    
let lcm xs =       
    xs                              // {8;9;21}
    |> Seq.map primefactors         // {{2^3};{3^2};{3^1;7^1}}
    |> Seq.concat                   // {2^3;3^2;3^1;7^1}
    |> Seq.groupBy (fun (x,y) -> x) // {{2;{2^3}};{3;{3^1;3^2}};{7;{7^1}}}
    |> Seq.map (fun (x,xys) ->       
        x,                          // 3
            xys                     // {3^1;3^2}
            |> Seq.map snd          // {1;2}
            |> Seq.max              // 2
    )                               // {2^3;3^2;7^1}
    |> Seq.map (fun (x,y) ->
        pown x y                    // {8;9;7}
    )
    |> Seq.reduce (*)               // 504

do  lcm [8;9;21] |> printf "%d"     // yields 504

C# Scripting

The .Net Framework ships with a C# code compiler that lets you generate in-memory assemblies. This can be used to run C# scripts without the need for the installation of a large application like PowerShell. The following code, which targets .Net 2.0, builds into a 7K executable, and is all that is needed to run C# source files from the command line:

using System;
using System.CodeDom.Compiler;
using System.Collections.Specialized;
using System.Diagnostics;
using System.IO;
using System.Text.RegularExpressions;
using Microsoft.CSharp;
using System.Collections.Generic;

static class Program
{
    /// <summary>
    /// Executes specified C# script file
    /// </summary>
    /// <param name="args">Path of C# script file</param>
    static void Main(string[] args)
    {
        // Check parameters
        if (args.Length == 0)
        {
            Console.WriteLine("Please specify a C# script file");
            Environment.Exit(-1);
        }
        // First parameter is source file path
        string path = args[0];
        // Check file exists 
        if (!File.Exists(path))
        {            
            Console.WriteLine("Specified file does not exist");            
            Environment.Exit(-1); 
        }
        // Read source from file
        string source = ReadFile(path);
        // Initialize compiler options
        CompilerParameters compilerParameters = 
            new CompilerParameters();      
        compilerParameters.GenerateExecutable = true;
        compilerParameters.GenerateInMemory = true;
        compilerParameters.TreatWarningsAsErrors = true;
        compilerParameters.CompilerOptions = "/nowarn:1633"; // unrecognized pragmas
        // Prepass source for #pragma reference statements        
        StringReader reader = new StringReader(source);       
        while (true)
        {
            string line = reader.ReadLine();
            if (line == null) break;            
            string pattern = 
                "\\s*#pragma\\s+reference\\s+\"(?<path>[^\"]*)\"\\s*";
            Match match = Regex.Match(line, pattern);                   
            if (match.Success)            
                compilerParameters.ReferencedAssemblies.Add
                    (match.Groups["path"].Value);            
        }
        // Specify .NET version
        Dictionary<string, string> providerOptions =
            new Dictionary<string, string>();
        providerOptions.Add("CompilerVersion", "v3.5");
        CSharpCodeProvider provider = new CSharpCodeProvider(providerOptions); 
        // Compile source           
        CompilerResults results =
                provider.CompileAssemblyFromSource(
                    compilerParameters,
                    new string[] { source });
        // Show errors
        if (results.Errors.HasErrors)
        {
            Console.WriteLine("Errors Building " + path);
            foreach (var err in results.Errors)
                Console.WriteLine(err);
            Environment.Exit(-1);
        }
        // Extract argument tail
        string[] parameters = new string[args.Length - 1];
        Array.Copy(args, 1, parameters, 0, args.Length-1);
        // Invoke compiled assembly's entry point
        results.CompiledAssembly.EntryPoint.Invoke
            (null, new object[1] { parameters });        
    }
    
    private static string ReadFile(string path)
    {
        using (StreamReader reader = File.OpenText(path))
            return reader.ReadToEnd();
    }
}

 

Script files look just like Console applications:

using System;

public class Class1
{
    static void Main(string[] args)
    {
        Console.WriteLine("Hello World");
    }
}

 

Finally additional assemblies can be referenced using #pragma directives:

#pragma warning disable 1633 // disable unrecognized pragma directive warning
#pragma reference "System.Windows.Forms.dll"

using System.Windows.Forms;

public class Class1
{
    static void Main(string[] args)
    {
        MessageBox.Show("Hello World");
    }
}

F# Units of Measure talk at Open Source eXchange III

The Open Source eXchange III was a mini-conference where members of the ALT.NET community talked about their favourite alternative .NET tools that increase programmer productivity. Units of Measure is a cool language feature in F#, developed by Andrew Kennedy, that lets you easily annotate values with units like metres, kilograms or seconds. Then F# type inference kicks in to give you automatic checking of your unit types at design and compile time, but cost you nothing at run time, e.g.

  let gravityOnEarth = 9.8f<m/s^2> // Acceleration

Following a bit of a Apollo 40th Anniversary theme, I presented 3 code samples (attached):

  • Statistics
  • Orbital Mechanics
  • Lunar Lander

Resources:

Further reading: