Fork me on GitHub

Code Snippet:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
let bitlength (x:bigint) =
  let xs  = x.ToByteArray()
  let n   = xs |> Array.length
  let msb = xs.[n-1]
  let rec bitlength' a = function
    | 0uy  -> a
    | msb' -> (a+1,msb' >>> 1) ||> bitlength'
  ((n-1)*8,msb) ||> bitlength'

let split (x:bigint) m =
  let y = x >>> m
  y,(x - (y <<< m))

let karatsuba x y =
  let r = 1 <<< 10
  let leq x y = (x |> bitlength) <= y
  let rec karatsuba' = function
    | (x',y') when (x',r) ||> leq || (y',r) ||> leq -> (x' * y')
    | (x',y') ->
      let n = (x' |> bitlength, y' |> bitlength) ||> max
      let m = n >>> 1
      let h1,l1 = (x',m) ||> split
      let h2,l2 = (y',m) ||> split 
      let z0 = (l1,l2)       |> karatsuba'
      let z1 = (l1+h1,l2+h2) |> karatsuba'
      let z2 = (h1,h2)       |> karatsuba'   
      (z2 <<< (2 * m)) + ((z1 - z0 - z2) <<< m) + z0
  (x,y) |> karatsuba'

let fib n = // tail-recursive with two accs
  let rec fib' a1 a2 = function
    | 0 -> 0I
    | 1 -> a1 + a2
    | i -> fib' a2 (a1 + a2) (i - 1)
  fib' 1I 0I n

let fibfast n =
  let inline inner x y i =
    let a = x * (2I * y - x)
    let b = y * y + x * x
    match i % 2 = 0 with | true -> (a,b) | false -> (b, a+b)
  let rec fibfast' k = function
    | 0 -> k (0I,1I)
    | i -> fibfast' (fun (x,y) -> k((x,y,i) |||> inner)) (i >>> 1)
  (id,n) ||> fibfast' |> fst

let fibfastkarat n =
  let inline inner x y i =
    let a = (x,((2I,y) ||> karatsuba) - x) ||> karatsuba
    let b = ((y,y) ||> karatsuba) + ((x,x) ||> karatsuba)
    match i % 2 = 0 with | true -> (a,b) | false -> (b, a+b)
  let rec fibfastkarat' k = function
    | 0 -> k (0I,1I)
    | i -> fibfastkarat' (fun (x,y) -> k((x,y,i) |||> inner)) (i >>> 1)
  (id,n) ||> fibfastkarat' |> fst

Code output:

> val bitlength : x:bigint -> int
> val split : x:bigint -> m:int32 -> bigint * System.Numerics.BigInteger
> val karatsuba : x:bigint -> y:bigint -> System.Numerics.BigInteger
> val fib : n:int -> System.Numerics.BigInteger
> val fibfast : n:int -> System.Numerics.BigInteger
> val fibfastkarat : n:int -> System.Numerics.BigInteger

Correctness test:

1
2
3
4
5
let correctness =
  ((10. ** 6. |> int |> fib),
   (10. ** 6. |> int |> fibfast),
   (10. ** 6. |> int |> fibfastkarat))
  |> fun (x,y,z) -> x = y && x = z;;

Correctness output:

> val correctness : bool = true

Performance test:

1
2
3
4
5
6
7
8
9
let duration f =
  let t = System.Diagnostics.Stopwatch()
  t.Start()
  let x = f()
  x,t.ElapsedMilliseconds |> float

duration(fun _ -> 10. ** 6. |> int |> fib)          |> snd;;
duration(fun _ -> 10. ** 6. |> int |> fibfast)      |> snd;;
duration(fun _ -> 10. ** 6. |> int |> fibfastkarat) |> snd;;

Performance output:

> val duration : f:(unit -> 'a) -> 'a * float
> val it : float = 198480.0
> val it : float = 4623.0
> val it : float = 1082.0

References:

rename.fsx:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
// -------------------------------------------------------------------------------
// Initial rename of library and project script
// -------------------------------------------------------------------------------

// Bind operator
let (>>=) m f = Option.bind f m

// Args function that parses command line arguments
let getArg argv key =
  let arg = Array.tryFind(fun (a:string) -> a.StartsWith(key)) argv
  match arg with
  | Some x -> x.Replace(key, "") |> Some
  | None -> None

// Thread-safe console logger
let ts () = System.DateTime.Now.ToString("o")           // ISO-8601
let cw (s:string) = System.Console.WriteLine(s)         // Threadsafe console writer
let cew (s:string) = System.Console.Error.WriteLine(s)  // Threadsafe console error writer
type LogLevel = Info | Warning | Error
let log level x y =
  let msg = sprintf "%s - %A: %A (%A)" (ts()) level x y
  match level with
  | LogLevel.Error -> cew msg
  | LogLevel.Info | LogLevel.Warning -> cw msg

// Generic process executer (needed for "git mv source target")
let executeProcess exe args dir =
  try
    let psi = new System.Diagnostics.ProcessStartInfo(exe,args) 
    psi.CreateNoWindow <- true        
    psi.UseShellExecute <- false
    psi.RedirectStandardOutput <- true
    psi.RedirectStandardError <- true
    psi.WorkingDirectory <- dir
    let p = System.Diagnostics.Process.Start(psi)
    let o = new System.Text.StringBuilder()
    let e = new System.Text.StringBuilder()
    p.OutputDataReceived.Add(fun x -> o.AppendLine(x.Data) |> ignore)
    p.ErrorDataReceived.Add(fun x -> e.AppendLine(x.Data) |> ignore)
    p.BeginErrorReadLine()
    p.BeginOutputReadLine()
    p.WaitForExit()
    (p.ExitCode, o.ToString(), e.ToString()) |> Some
  with ex -> log LogLevel.Error (exe,args,dir) ex; None

// Scaffold & Template
let scaffold = "FSharp.ProjectScaffold"
let template = "FSharp.ProjectTemplate"

// The name of the library (will replace "FSharp.ProjectScaffold")
let lib = 
  ((fsi.CommandLineArgs,"lib=") ||> getArg, "FSharp.Foo")
  ||> defaultArg

// The name of the project (will replace "FSharp.ProjectTemplate")
let proj =
  ((fsi.CommandLineArgs,"proj=") ||> getArg, "FSharp.Bar")
  ||> defaultArg

// Folder & file helper functions
let root = __SOURCE_DIRECTORY__
let recursively = System.IO.SearchOption.AllDirectories
let pattern filter = "*" + filter + "*"
let pattern' filter = "*" + filter
let dirs path filter =
  System.IO.Directory.EnumerateDirectories(path,filter,recursively)
let files path filter =
  System.IO.Directory.EnumerateFiles(path,filter,recursively)
let rev (s:string) =
  s |> Seq.toArray |> Array.fold(fun a x -> (x |> string) + a) ""
let replaceFirst input from to' =
  let r = new System.Text.RegularExpressions.Regex(from)
  r.Replace(input = input,replacement = to', count = 1)
let isGit =
  let exe  = "git"
  let args = sprintf "status"
  let git  = (exe,args,root) |||> executeProcess
  git |> function | Some (x,y,z) -> x = 0 | None -> false
let renameGit path path' =
  let exe  = "git"
  let args = sprintf "mv \"%s\" \"%s\"" path path'
  (exe,args,root) |||> executeProcess, path, path'
let renameDirs path path' =
  System.IO.Directory.Move(path,path') |> ignore
  (0,"","") |> Some,path,path'
let renameFiles path path' =
  System.IO.File.Move(path,path') |> ignore
  (0,"","") |> Some,path,path'
let rename' path path' =
  match isGit with
  | true -> (path,path') ||> renameGit
  | false ->
    match System.IO.File.GetAttributes(path) with
    | System.IO.FileAttributes.Directory -> (path,path') ||> renameDirs 
    | _ -> (path,path') ||> renameFiles
let rename (path:string) from to' =
  let from' = from  |> rev
  let to''  = to'   |> rev
  let path' = (path |> rev, from', to'') |||> replaceFirst |> rev
  (path,path') ||> rename'
let rollback xs = xs |> List.iter(fun (x,y) -> (y,x) ||> rename' |> ignore)

// File content helper functions
let utf8 = System.Text.UTF8Encoding.UTF8
let readLines path = System.IO.File.ReadLines(path,utf8)
let writeLines path (contents:string seq)  =
  System.IO.File.WriteAllLines(path,contents,utf8)
let copy from to' =
  System.IO.File.Copy(from,to',true)
let delete path = System.IO.File.Delete(path)
let extensions = [ ".sln"; ".fs"; ".fsx"; ".fsproj"; ".nuspec"; ".md" ]

// Rename files or directories
let renameIO from to' fn atomic' =
  try
      (root,from |> pattern) ||> fn
      |> Seq.map(fun x -> (x,from,to') |||> rename)
      |> Seq.fold(fun (i,acc) (x,y,z) ->
                  let i' =
                    match x with
                    | Some (a,b,c) -> a
                    | None -> 1
                  (i+i',(y,z)::acc)) (0,[])
      |> fun (x,y) ->
        match x with
        | 0 -> (y,atomic') ||> List.append |> Some
        | _ -> atomic' |> rollback; None
  with ex -> log LogLevel.Error (atomic',from,to') ex; None

// Update files content
let updateContent exts atomic' =
  try
    exts
    |> Seq.map(fun x -> (root,x |> pattern') ||> files)
    |> Seq.fold(fun a x -> (x,a) ||> Seq.append) Seq.empty
    |> Seq.filter(fun x -> not (x.Contains "rename.fsx"))
    |> Seq.fold(fun a x ->
                let x' = x + "_"
                x |> readLines
                  |> Seq.map(fun y -> y.Replace(scaffold,lib)
                                       .Replace(template,proj))
                  |> writeLines x'
                (x,x')::a) []
    |> Seq.iter(fun (x,y) -> (y,x) ||> copy; y |> delete)
    |> Some
  with ex ->
    let git =
      match isGit with
      | false -> (0,"","") |> Some // Not really rollback but ...
      | true ->
        let exe  = "git"
        let args = sprintf "checkout -- *"
        (exe,args,root) |||> executeProcess
    atomic' |> rollback
    log LogLevel.Error (exts,git) ex; None

// Rename with atomicity "git mv file2 file1"
[] |> Some >>= (renameIO scaffold lib dirs)
           >>= (renameIO template proj dirs)
           >>= (renameIO scaffold lib files)
           >>= (renameIO template proj files)

// Update content
           >>= (updateContent extensions)

rename.cmd:

@echo off
:: Add the paths for the F# SDK 3.x (from higher version to lower)
set FSHARPSDK=^
C:\Program Files (x86)\Microsoft SDKs\F#\3.1\Framework\v4.0\;^
C:\Program Files (x86)\Microsoft SDKs\F#\3.0\Framework\v4.0\

cls
:: Execute the script "only" with the first "fsianycpu.exe" found
for %%i in (fsianycpu.exe) do "%%~$FSHARPSDK:i" rename.fsx %*

pause

rename.sh:

#!/bin/bash
#workaround to handle different path for fsi
export FSHARPI=`which fsharpi`
cat - > fsharpi <<"EOF"
#!/bin/bash
$FSHARPI $@
EOF
chmod +x fsharpi
fsharpi rename.fsx $@
rm fsharpi

Git clone FSharp.ProjectScaffold

[ mon@mbai7 rename ] git clone git@github.com:fsprojects/FSharp.ProjectScaffold.git
Cloning into 'FSharp.ProjectScaffold'...
remote: Reusing existing pack: 674, done.
remote: Total 674 (delta 0), reused 0 (delta 0)
Receiving objects: 100% (674/674), 593.40 KiB | 375.00 KiB/s, done.
Resolving deltas: 100% (342/342), done.
Checking connectivity... done.
[ mon@mbai7 rename ] cd FSharp.ProjectScaffold/

Grep for FSharp.ProjectScaffold and FSharp.ProjectTemplate:

[ mon@mbai7 FSharp.ProjectScaffold ] grep -R "FSharp.ProjectScaffold" .
./build.fsx:let solutionFile  = "FSharp.ProjectScaffold"
./build.fsx:let gitName = "FSharp.ProjectScaffold"
./docs/content/index.fsx:  [content]: https://github.com/fsprojects/FSharp.ProjectScaffold/tree/master/docs/content
./docs/content/index.fsx:  [gh]: https://github.com/fsprojects/FSharp.ProjectScaffold
./docs/content/index.fsx:  [issues]: https://github.com/fsprojects/FSharp.ProjectScaffold/issues
./docs/content/index.fsx:  [readme]: https://github.com/fsprojects/FSharp.ProjectScaffold/blob/master/README.md
./docs/content/index.fsx:  [license]: https://github.com/fsprojects/FSharp.ProjectScaffold/blob/master/LICENSE.txt
./docs/tools/generate.fsx:let website = "/FSharp.ProjectScaffold"
./docs/tools/generate.fsx:let githubLink = "http://github.com/fsprojects/FSharp.ProjectScaffold"
./docs/tools/generate.fsx:  [ "project-name", "FSharp.ProjectScaffold"
./docs/tools/generate.fsx:    "project-nuget", "http://nuget.com/packages/FSharp.ProjectScaffold" ]
./nuget/FSharp.ProjectTemplate.nuspec:    <licenseUrl>http://github.com/fsprojects/FSharp.ProjectScaffold/blob/master/LICENSE.txt</licenseUrl>
./nuget/FSharp.ProjectTemplate.nuspec:    <projectUrl>http://fsprojects.github.com/FSharp.ProjectScaffold</projectUrl>
./nuget/FSharp.ProjectTemplate.nuspec:    <iconUrl>https://raw.github.com/fsharp/FSharp.ProjectScaffold/master/nuget/logo.png</iconUrl>
./README.md:FSharp.ProjectScaffold
./README.md:      <td><a href="FSharp.ProjectScaffold.sln">FSharp.ProjectScaffold.sln</a></td>
./README.md:<a href="http://fsprojects.github.io/FSharp.ProjectScaffold" target="_blank">Sample API documents available here.</a>
./RELEASE_NOTES.md:* Changed name from fsharp-project-scaffold to FSharp.ProjectScaffold
./rename.fsx:let scaffold = "FSharp.ProjectScaffold"
./rename.fsx:// The name of the library (will replace "FSharp.ProjectScaffold")
./tests/FSharp.ProjectTemplate.Tests/Tests.fs:module FSharp.ProjectScaffold.Tests
[ mon@mbai7 FSharp.ProjectScaffold ] grep -R "FSharp.ProjectTemplate" .
./build.fsx:let project = "FSharp.ProjectTemplate"
./docs/content/index.fsx:      The F# ProjectTemplate library can be <a href="https://nuget.org/packages/FSharp.ProjectTemplate">installed from NuGet</a>:
./docs/content/index.fsx:      <pre>PM> Install-Package FSharp.ProjectTemplate</pre>
./docs/content/index.fsx:#r "FSharp.ProjectTemplate.dll"
./docs/content/index.fsx:open FSharp.ProjectTemplate
./docs/content/tutorial.fsx:#r "FSharp.ProjectTemplate.dll"
./docs/content/tutorial.fsx:open FSharp.ProjectTemplate
./docs/tools/generate.fsx:let referenceBinaries = [ "FSharp.ProjectTemplate.dll" ]
./FSharp.ProjectScaffold.sln:Project("{F2A71F9B-5D33-465A-A702-920D77279786}") = "FSharp.ProjectTemplate", "src\FSharp.ProjectTemplate\FSharp.ProjectTemplate.fsproj", "{7E90D6CE-A10B-4858-A5BC-41DF7250CBCA}"
./FSharp.ProjectScaffold.sln:																									 	 nuget\FSharp.ProjectTemplate.nuspec = nuget\FSharp.ProjectTemplate.nuspec
./FSharp.ProjectScaffold.sln:Project("{F2A71F9B-5D33-465A-A702-920D77279786}") = "FSharp.ProjectTemplate.Tests", "tests\FSharp.ProjectTemplate.Tests\FSharp.ProjectTemplate.Tests.fsproj", "{E789C72A-5CFD-436B-8EF1-61AA2852A89F}"
./nuget/FSharp.ProjectTemplate.nuspec:    <file src="..\bin\FSharp.ProjectTemplate.dll" target="lib/net40" />
./README.md:        A good way to get started is to rename the project included in this sample (FSharp.ProjectTemplate). 
./rename.fsx:let template = "FSharp.ProjectTemplate"
./rename.fsx:// The name of the project (will replace "FSharp.ProjectTemplate")
./src/FSharp.ProjectTemplate/AssemblyInfo.fs:[<assembly: AssemblyTitleAttribute("FSharp.ProjectTemplate")>]
./src/FSharp.ProjectTemplate/AssemblyInfo.fs:[<assembly: AssemblyProductAttribute("FSharp.ProjectTemplate")>]
./src/FSharp.ProjectTemplate/FSharp.ProjectTemplate.fsproj:    <RootNamespace>FSharp.ProjectTemplate</RootNamespace>
./src/FSharp.ProjectTemplate/FSharp.ProjectTemplate.fsproj:    <AssemblyName>FSharp.ProjectTemplate</AssemblyName>
./src/FSharp.ProjectTemplate/FSharp.ProjectTemplate.fsproj:    <Name>FSharp.ProjectTemplate</Name>
./src/FSharp.ProjectTemplate/FSharp.ProjectTemplate.fsproj:    <DocumentationFile>bin\Debug\FSharp.ProjectTemplate.xml</DocumentationFile>
./src/FSharp.ProjectTemplate/FSharp.ProjectTemplate.fsproj:    <DocumentationFile>..\..\bin\FSharp.ProjectTemplate.xml</DocumentationFile>
./src/FSharp.ProjectTemplate/Library.fs:namespace FSharp.ProjectTemplate
./src/FSharp.ProjectTemplate/Script.fsx:open FSharp.ProjectTemplate
./tests/FSharp.ProjectTemplate.Tests/FSharp.ProjectTemplate.Tests.fsproj:    <RootNamespace>FSharp.ProjectTemplate.Tests</RootNamespace>
./tests/FSharp.ProjectTemplate.Tests/FSharp.ProjectTemplate.Tests.fsproj:    <AssemblyName>FSharp.ProjectTemplate.Tests</AssemblyName>
./tests/FSharp.ProjectTemplate.Tests/FSharp.ProjectTemplate.Tests.fsproj:    <Name>FSharp.ProjectTemplate.Tests</Name>
./tests/FSharp.ProjectTemplate.Tests/FSharp.ProjectTemplate.Tests.fsproj:    <DocumentationFile>bin\Release\FSharp.ProjectTemplate.Tests.xml</DocumentationFile>
./tests/FSharp.ProjectTemplate.Tests/FSharp.ProjectTemplate.Tests.fsproj:    <ProjectReference Include="..\..\src\FSharp.ProjectTemplate\FSharp.ProjectTemplate.fsproj">
./tests/FSharp.ProjectTemplate.Tests/FSharp.ProjectTemplate.Tests.fsproj:      <Name>FSharp.ProjectTemplate</Name>
./tests/FSharp.ProjectTemplate.Tests/Tests.fs:open FSharp.ProjectTemplate

Rename FSharp.ProjectScaffold and FSharp.ProjectTemplate:

[ mon@mbai7 FSharp.ProjectScaffold ] cp ../rename.* .
‘../rename.cmd’ -> ‘./rename.cmd’
‘../rename.fsx’ -> ‘./rename.fsx’
‘../rename.sh’ -> ‘./rename.sh’
[ mon@mbai7 FSharp.ProjectScaffold ] chmod +x rename.sh 
[ mon@mbai7 FSharp.ProjectScaffold ] ./rename.sh lib=Stermon.Foo proj=Stermon.Bar

Grep for FSharp.ProjectScaffold and FSharp.ProjectTemplate (again):

[ mon@mbai7 FSharp.ProjectScaffold ] grep -R "FSharp.ProjectScaffold" .
./rename.fsx:let scaffold = "FSharp.ProjectScaffold"
./rename.fsx:// The name of the library (will replace "FSharp.ProjectScaffold")
[ mon@mbai7 FSharp.ProjectScaffold ] grep -R "FSharp.ProjectTemplate" .
./rename.fsx:let template = "FSharp.ProjectTemplate"
./rename.fsx:// The name of the project (will replace "FSharp.ProjectTemplate")

Build FSharp.ProjectScaffold:

[ mon@mbai7 FSharp.ProjectScaffold ] chmod +x build.sh 
[ mon@mbai7 FSharp.ProjectScaffold ] ./build.sh 
Installing 'FAKE 2.15.2'.
Successfully installed 'FAKE 2.15.2'.
fsharpi build.fsx
Building project with version: LocalBuild
Shortened DependencyGraph for Target All:
<== All
<== RunTests
<== Build
<== AssemblyInfo
<== RestorePackages
      <== Clean

The resulting target order is:
 - Clean
 - RestorePackages
 - AssemblyInfo
 - Build
 - RunTests
 - All
Starting Target: All (==> RunTests)
Starting Target: RunTests (==> Build)
Starting Target: Build (==> AssemblyInfo)
Starting Target: AssemblyInfo (==> RestorePackages)
Starting Target: RestorePackages (==> Clean)
Starting Target: Clean 
Deleting contents of bin
Deleting contents of temp
Finished Target: Clean

...

Execution Runtime: mono-3.5
***** Stermon.Foo.Tests.hello returns 42
42

Tests run: 1, Errors: 0, Failures: 0, Inconclusive: 0, Time: 0.0387905 seconds
  Not run: 0, Invalid: 0, Ignored: 0, Skipped: 0

Finished Target: RunTests
Finished Target: All
Killing all processes that are created by FAKE and are still running.

---------------------------------------------------------------------
Build Time Report
---------------------------------------------------------------------
Target            Duration
------            --------
Clean             00:00:00.0043722
RestorePackages   00:00:02.4633336
AssemblyInfo      00:00:00.0062624
Build             00:00:05.3281672
RunTests          00:00:01.1349369
All               00:00:00.0000441
Total:            00:00:08.9734871
Status:           Ok
---------------------------------------------------------------------

Stermon.Foo and Stermon.Bar:

[ mon@mbai7 FSharp.ProjectScaffold ] ll . bin/ src/ tests/
.:
total 64K
-rw-r--r--  1 mon staff 1.2K Apr 25 18:20 LICENSE.txt
-rw-r--r--  1 mon staff  16K Apr 25 18:45 README.md
-rw-r--r--  1 mon staff  374 Apr 25 18:45 RELEASE_NOTES.md
-rw-r--r--  1 mon staff 3.2K Apr 25 18:45 Stermon.Foo.sln
-rw-r--r--  1 mon staff 1.7K Apr 25 18:48 TestResults.xml
drwxr-xr-x  5 mon staff  170 Apr 25 18:48 bin/
-rw-r--r--  1 mon staff  182 Apr 25 18:20 build.cmd
-rw-r--r--  1 mon staff 5.6K Apr 25 18:45 build.fsx
-rwxr-xr-x  1 mon staff  398 Apr 25 18:20 build.sh*
drwxr-xr-x  6 mon staff  204 Apr 25 18:20 docs/
drwxr-xr-x  3 mon staff  102 Apr 25 18:45 lib/
drwxr-xr-x  5 mon staff  170 Apr 25 18:45 nuget/
drwxr-xr-x 10 mon staff  340 Apr 25 18:48 packages/
-rw-r--r--  1 mon staff   39 Apr 25 18:44 rename.cmd
-rw-r--r--  1 mon staff 5.2K Apr 25 18:44 rename.fsx
-rwxr-xr-x  1 mon staff   59 Apr 25 18:44 rename.sh*
drwxr-xr-x  3 mon staff  102 Apr 25 18:41 src/
drwxr-xr-x  2 mon staff   68 Apr 25 18:48 temp/
drwxr-xr-x  3 mon staff  102 Apr 25 18:41 tests/

bin/:
total 12K
-rwxr-xr-x 1 mon staff 4.0K Apr 25 18:48 Stermon.Bar.dll*
-rw-r--r-- 1 mon staff  276 Apr 25 18:48 Stermon.Bar.dll.mdb
-rw-r--r-- 1 mon staff  196 Apr 25 18:48 Stermon.Bar.xml

src/:
total 0
drwxr-xr-x 7 mon staff 238 Apr 25 18:48 Stermon.Bar/

tests/:
total 0
drwxr-xr-x 7 mon staff 238 Apr 25 18:48 Stermon.Bar.Tests/

Git status:

[ mon@mbai7 FSharp.ProjectScaffold ] git status
On branch master
Your branch is up-to-date with 'origin/master'.

Changes to be committed:
  (use "git reset HEAD <file>..." to unstage)

	renamed:    FSharp.ProjectScaffold.sln -> Stermon.Foo.sln
	renamed:    nuget/FSharp.ProjectTemplate.nuspec -> nuget/Stermon.Bar.nuspec
	renamed:    src/FSharp.ProjectTemplate/AssemblyInfo.fs -> src/Stermon.Bar/AssemblyInfo.fs
	renamed:    src/FSharp.ProjectTemplate/Library.fs -> src/Stermon.Bar/Library.fs
	renamed:    src/FSharp.ProjectTemplate/Script.fsx -> src/Stermon.Bar/Script.fsx
	renamed:    src/FSharp.ProjectTemplate/FSharp.ProjectTemplate.fsproj -> src/Stermon.Bar/Stermon.Bar.fsproj
	renamed:    tests/FSharp.ProjectTemplate.Tests/FSharp.ProjectTemplate.Tests.fsproj -> tests/Stermon.Bar.Tests/Stermon.Bar.Tests.fsproj
	renamed:    tests/FSharp.ProjectTemplate.Tests/Tests.fs -> tests/Stermon.Bar.Tests/Tests.fs
	renamed:    tests/FSharp.ProjectTemplate.Tests/packages.config -> tests/Stermon.Bar.Tests/packages.config

Changes not staged for commit:
  (use "git add/rm <file>..." to update what will be committed)
  (use "git checkout -- <file>..." to discard changes in working directory)

	modified:   README.md
	modified:   RELEASE_NOTES.md
	modified:   Stermon.Foo.sln
	deleted:    bin/README.md
	modified:   build.fsx
	modified:   build.sh
	modified:   docs/content/index.fsx
	modified:   docs/content/tutorial.fsx
	modified:   docs/output/README.md
	modified:   docs/tools/generate.fsx
	modified:   lib/README.md
	modified:   nuget/README.md
	modified:   nuget/Stermon.Bar.nuspec
	modified:   packages/README.md
	modified:   src/Stermon.Bar/AssemblyInfo.fs
	modified:   src/Stermon.Bar/Library.fs
	modified:   src/Stermon.Bar/Script.fsx
	modified:   src/Stermon.Bar/Stermon.Bar.fsproj
	deleted:    temp/README.md
	modified:   tests/Stermon.Bar.Tests/Stermon.Bar.Tests.fsproj
	modified:   tests/Stermon.Bar.Tests/Tests.fs

Untracked files:
  (use "git add <file>..." to include in what will be committed)

	rename.cmd
	rename.fsx
	rename.sh

References:

Background

A couple of years ago when I studied a semester abroad at Pisa University I took the following course Algorithm Engineering taught by Paolo Ferragina. On the tenth lecture we learned about Bloom filters, a space-efficient probabilistic data structure, that is used to test whether an element is a member of a set.

The data-structure is space-efficient as it saves the necessary information in bits where HashTables will store the information in at least a bool, but will only use one of the bits while the rest are unused. See my previous code snippet F# Storage boolean vs. bits/bytes where I point out the memory waste.

With regard to test if an element is in the set, the bloom filter can only warranty that an element definitely is not in set while if an element is in the filter, it still has to make a lookup on the underlying data-structure. There is a probability that an element is in the filter but it isn’t in the underlying data-structure (False positives). The False positives are due to the set of hashes can set the same bit for different words. This is why it’s very important to choose a set of hashes that uniformly distribute the values across the filter:

All

For more information on how to choose the most space-efficient size of bits, m, in relation to the probability of false positives, p, while choosing the optimal number of hash functions, k, please read the Bloom filters article.

Implementation

Due to we soon at work are going to make native apps for several devices where we need to synchronize data in order to use the apps when they are offline and because we are going to use F#/C#, I thought to myself:“Why not implement a usable Bloom filter in F#?”, just for fun of course :-)

At Pisa we only studied the theory behind the data structure, but we never really implemented it so I didn’t had to much to start from. A search on Google brought me to Wikipedia and Bill Mills Bloom Filters by Example. I saw Bill implemented both the FNV-1 and MurmurHash2 hashes. In order to make this task challenging, I decided to firstly implement the FNV-1a as the author recommends to use this instead of the FNV-1 due to the final octet is not as well dispersed. And afterwards, I soon found out that I would also need to implement the MurmurHash3 algorithm as it has support for a seed which can be used to generate different hashes for the same key by re-using the same algorithm. A few more searches on Google, Google’s CityHash and Which hashing algorithm is best for uniqueness and speed?, and I was convinced that MurmurHash3 was the right choice (CityHash uses MurMurs Magic numbers).

After implementing the hash functions I knew that I also was going to need some functions that could get/set a bit in a byte. Very straightforward and fun task. I tried to make a byte pretty-printer, see my code snippet F# Storage boolean vs. bits/bytes but I soon saw it would not be usable when the sizes of the arrays would become big enough. So I implemented a bits2png function, I got a bit inspired by Which hashing algorithm is best for uniqueness and speed? on the way he represents the distribution of the hashes in pictures.

The task of implementing the Bloom filter was straight forward once the other bit/byte and hash functions were implemented. I added a ceilPow function in order to ceil up to nearest power of 2. This way &&& (n-1) can be used instead of % n as modulo is a division operation and should be more expensive than a bitwise operation. I out-commented it as this wouldn’t give the optimal size of m, but if size isn’t important and performance is, please out-comment the lines

Finally the last task, was to implement some IO functions that could count the lines of a file and find a specific word in a file.

Byte/bit functions:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
let gbit = function
  | (b,n) when n < 8 && n >= 0 ->
    System.Convert.ToString(0uy+b, 2).PadLeft(8,'0').[n] |> string |> int
  | _ -> failwith "There are only 8-bits in a byte"

let sbit = function
  | (b,n) when n < 8 && n >= 0 -> b ||| byte (1 <<< (7-n))
  | _ -> failwith "There are only 8-bits in a byte"

let pbyte' byte a b =
  System.Convert.ToString(0uy+byte, 2).PadLeft(8,'0')
  |> Seq.map(fun x -> x |> function | '0' -> a | _ -> b)
let pbyte byte = (byte,"□","■") |||> pbyte' |> Seq.reduce(+)

let html2color html = System.Drawing.ColorTranslator.FromHtml(html)

let bits2png (bytes:byte[]) =
  let black  = System.Drawing.Color.Black
  let green = "#66ED11" |> html2color
  let ts = System.DateTime.Now.ToString("o").Replace(':','.')

  let n = bytes.Length * 8 |> float |> fun x -> x / 2048. |> ceil |> int
  use bmp = new System.Drawing.Bitmap(2048,n)
  let w,h = bmp.Width-1,bmp.Height-1
  
  let rec background color = function
    | (0,0) -> ()
    | (x,0) -> bmp.SetPixel(x,0,color); background color (x-1,h)
    | (x,y) -> bmp.SetPixel(x,y,color); background color (x,y-1)
  (w,h) |> background black
  
  let chunkpixel i =
    let chunk = i >>> 11
    let pixel = i - (chunk <<< 11)
    chunk,pixel
    
  bytes
  |> Array.map(fun x -> (x,black,green) |||> pbyte')
  |> Array.iteri(
    fun i xs -> i * 8 |> chunkpixel |> fun (y,z) ->
    xs |> Seq.iteri(fun j x -> bmp.SetPixel(z+j,y,x)))
  
  bmp.Save(ts + @"_bits2png.png", System.Drawing.Imaging.ImageFormat.Png)

Hash functions:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
let stb s = System.Text.Encoding.UTF8.GetBytes(s = s)

// [ mon@mbai7 fnv ] ./fnv1a32 -s foo => 0xa9f37ed7
let fnv1aHash key =
  let fnvp  = (1 <<< 24) + (1 <<< 8) + 0x93 |> uint32
  let fnvob = 2166136261u
  
  let b = key |> stb
  
  let rec fnv1Hash' h = function
    | i when i < (b.Length) ->
      let h'  =
        h ^^^ (b.[i] |> uint32)
        |> fun x -> x * fnvp
      fnv1Hash' h' (i+1)
    | _ -> h
  fnv1Hash' fnvob 0

// [ mon@mbai7 murmur3-master ] ./example foo => x86_32: b12f489e (seed 42)
let murmur3Hash seed key =
  let rotl x r = (x <<< r) ||| (x >>> (32 - r))
  let fmix h =
    h
    |> fun x -> x ^^^ (x >>> 16)
    |> fun x -> x * 0x85ebca6bu
    |> fun x -> x ^^^ (x >>> 13)
    |> fun x -> x * 0xc2b2ae35u
    |> fun x -> x ^^^ (x >>> 16)
  let getblock b i = System.BitConverter.ToUInt32(value = b, startIndex = i)
  
  let data    = key  |> stb
  let len     = data |> Array.length
  let nblocks = len >>> 2 // equivalent to len/4 but faster
  let h1      = seed
  let c1      = 0xcc9e2d51u
  let c2      = 0x1b873593u
  
  // body
  let rec body h = function
    | i when i < nblocks ->
      let k1 =
        getblock data (i * 4)
        |> fun x -> x * c1
        |> fun x -> rotl x 15
        |> fun x -> x * c2
      let h' =
        h ^^^ k1
        |> fun x -> rotl x 13
        |> fun x -> x * 5u + 0xe6546b64u
      body h' (i+1)
    | _ -> h
  let h1' = body h1 0
  
  // tail
  let tail = nblocks * 4
  let rec tail' (k,h) = function
    | 0 -> h
    | 1 -> 
      let k' =
        k ^^^ (uint32 data.[tail])
        |> fun x -> x * c1
        |> fun x -> rotl x 15
        |> fun x -> x * c2
      let h' = h ^^^ k'
      tail' (k',h') (0)
    | i ->
      let k' =
        (uint32 data.[tail + (i - 1)]) <<< (1 <<< (i + 1))
        |> fun x -> k ^^^ x
      tail' (k',h) (i-1)
  let h1'' = tail' (0u,h1') (len &&& 3)
  
  // finalization
  h1'' ^^^ (uint32 len)
  |> fun x -> x |> fmix

Bloom filter:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
let rand  = System.Random()

// http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2Float
let ceilPow (x:uint32) =
  x
  |> fun x -> x-1u
  |> fun x -> x ||| (x >>> 1)
  |> fun x -> x ||| (x >>> 2)
  |> fun x -> x ||| (x >>> 4)
  |> fun x -> x ||| (x >>> 8)
  |> fun x -> x ||| (x >>> 16)
  |> fun x -> x+1u

// ISO 31-11
let ln x = x |> log
let lb x = System.Math.Log(x,2.)
let lg x = System.Math.Log10(x)

type BloomFilter(n:uint32, p) =
  let m = // ceil up to nearest 2^n in order to use &&& (n-1) instead of % n
    let n'  = n |> float
    let lnp = ln p
    let ln2 = ln 2.
    -(n' * lnp) / (ln2 ** 2.)
    |> fun x -> x |> uint32
    //|> fun x -> x |> ceilPow
    //|> fun x -> x |> int 
    |> fun x -> x >>> 3 <<< 3 // round to nearest byte/bit
  let bits = Array.init (m >>> 3 |> int) (fun i -> 0uy)
  let seeds =
    let m'  = m |> float
    let n'  = n |> float
    let ln2 = ln 2.
    let k   = (m'/n') * ln2
    let k'  = k |> ceil |> int
    Array.init (k') (fun i -> rand.Next() |> uint32)
  let hashes = seeds |> Array.map(fun x -> x |> murmur3Hash)
  let bytebit hash =
    let byte = hash >>> 3
    let bit = hash - (byte <<< 3)
    byte,bit
  member x.add key =
    hashes
    |> Array.map(fun f -> f(key) % m |> int |> bytebit)
    |> Array.iter(fun (x,y) -> bits.[x] <- (bits.[x],y) |> sbit)
  member x.query key =
    hashes
    |> Array.map(fun f -> f(key) % m |> int |> bytebit)
    |> Array.fold(fun a (x,y) -> (((bits.[x],y) |> gbit) = 1) && a) true
  member x.print = bits |> bits2png
  member x.info =
    printfn "p: %e" p
    printfn "m: %u" ((bits |> Array.length) |> uint32 |> fun x -> x * 8u)
    printfn "k: %i" (hashes |> Array.length)
    printfn "seeds: %A" (seeds)

File functions (IO):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
let lines file = System.IO.File.ReadLines(file)

let count file = file |> lines |> Seq.length

let find word file =
  use reader = System.IO.File.OpenText(file)
  
  let rec find' = function
    | true -> false
    | false ->
      match reader.ReadLine().Equals(word) with
        | true -> true
        | false -> find' reader.EndOfStream
  find' reader.EndOfStream

An English dictionary with +235.000 words

Once the code is implemented, let’s use the built-in English dictionary on my Mac with the File (IO) functions to test the Bloom Filter:

 @"/usr/share/dict/words" |> count;;
(@"Zyzzogeton",@"/usr/share/dict/words") ||> find;;
(@"gentauro",@"/usr/share/dict/words") ||> find;;

For a file with +235.000 lines, both the count and the find functions are very fast:

> #time;; 
> Real: 00:00:00.066, CPU: 00:00:00.068, GC gen0: 2, gen1: 0
val it : int = 235886
> Real: 00:00:00.054, CPU: 00:00:00.054, GC gen0: 3, gen1: 0
val it : bool = true
> Real: 00:00:00.050, CPU: 00:00:00.050, GC gen0: 2, gen1: 0
val it : bool = false

Now that we have the number of elements, n, let’s choose a probability of 0.1%. For more information on how to choose the probability, check these tables Bloom Filters - the math:

let bloom = new BloomFilter(235886u, 1.e-3);; // Ex: 1.e-3 for a 0.1 %
bloom.info;;
bloom.printf;;

The optimal number of hashes, k, is set to 10. The seeds values used for the hash functions are also printed out in order to reproduce results. And finally the initial set of bits is printed out as an .png file. Initially it will be empty.

val bloom : BloomFilter
p: 1.000000e-003
m: 3391464
k: 10
seeds: [|209312772u; 1554706806u; 1919816475u; 2123757442u; 1979313534u;
  1239494964u; 585019070u; 384168856u; 1683270745u; 1807577208u|]
val it : unit = ()

All

@"Zyzzogeton" |> bloom.query;;

If we query the data-structure for a word we know exists in the dictionary, it will return false as it’s initially empty:

val it : bool = false

But if we populate the Bloom filter with all the words contained in the dictionary, and we then query for the same word, we can see that know the query will return true. For a word that we for sure know that is not in the dictionary and hereby not in the filter, we can see that the result is false:

@"/usr/share/dict/words" |> lines |> Seq.iter(fun x -> x |> bloom.add);;
@"Zyzzogeton" |> bloom.query;;
@"gentauro" |> bloom.query;;
bloom.print;;
val it : unit = ()
val it : bool = true
val it : bool = false
val it : unit = ()

Now when we print again the bits to a .png file, it’s possible to view how the different values are evenly distributed across the data-structure:

All

Correct way to handle values (including False Positives):

As stated at the beginning, just because a key returns true, it doesn’t mean that the underlying data-structure will contain the item (False positives). The correct way to handle the return values is to write the following code:

@"Zyzzogeton"
|> fun x ->
  x |> bloom.query |> function
    | false -> false
    | true -> (x,@"/usr/share/dict/words") ||> find
@"gentauro"
|> fun x ->
  x |> bloom.query |> function
    | false -> false
    | true -> (x,@"/usr/share/dict/words") ||> find
val it : bool = true
val it : bool = false

Where the first function will need to check the value against the file and the second function doesn’t need to, as the key is definitely is not in set.

When size matters (+152.000.000 leaked e-mails in a 3.2 GB file)

You might argue that the lookups to the dictionary file aren’t that expensive right? Why all the headache implementing this extra data-structure/filter on top of the original data-structure. If you still aren’t convinced of why Bloom filters are awesome, lets go through the following example. Inspired by a Company Friday Talk @ Delegate A/S where one of my co-workers showed how somebody had stored the password on Windows Azure and provided a website to check whether an e-mails was compromised or not.

Like anything on the Internet, once it’s out there, it’s very easy to get access to it Reddit - Hacking. I downloaded the file and made a few grep/sed operations in order to only have e-mails in the file. I then appended an e-mail to the file in order for the linear search to take the most time and also avoid using a real e-mail in this blog post. The result are the following when applying the same File (IO) functions from before:

 @"leaks/emails.txt" |> count;;
(@"bloom.filter@mail.co.dk",@"leaks/emails.txt") ||> find;;
(@"u.mad@mail.co.dk",@"leaks/emails.txt") ||> find;;

We can now see that all the call are about one minute. We can all agree that this is a very expensive call right?

> #time;;
> Real: 00:00:59.585, CPU: 00:00:58.653, GC gen0: 2215, gen1: 0
val it : int = 152448315
> Real: 00:01:03.203, CPU: 00:01:01.542, GC gen0: 2216, gen1: 0
val it : bool = true
> Real: 00:00:55.632, CPU: 00:00:55.446, GC gen0: 2216, gen1: 0
val it : bool = false

Now lets instantiate the Bloom filter with the given n and a probability of 1% (any value here less than one percent, crashes my application, but the one percent is OK for this example):

let bloom = new BloomFilter(153u*1000u*1000u, 1.e-2);;
bloom.info;;
@"leaks/emails.txt" |> lines |> Seq.iter(fun x -> x |> bloom.add);;

As before we populate the filter with the file content.

val bloom : BloomFilter
p: 1.000000e-002
m: 1466513928
k: 7
seeds: [|2143730668u; 2132815355u; 1369875737u; 1908004139u; 496837579u;
  406257522u; 1163911365u|]
val it : unit = ()
val it : unit = ()

Remark: Good luck populating a HashTable with 3.2 GB worth of data

@"bloom.filter@mail.co.dk" |> bloom.query;;
@"u.mad@mail.co.dk" |> bloom.query;;

Now we can make queries as before and we can see that both are constant calls, O(1). We now have a service that can tell a user almost instantly if his e-mail isn’t leaked. Pretty cool right?

> #time;;
> Real: 00:00:00.002, CPU: 00:00:00.006, GC gen0: 0, gen1: 0
val it : bool = true
> Real: 00:00:00.000, CPU: 00:00:00.000, GC gen0: 0, gen1: 0
val it : bool = false

Remark: Once again, as stated at: “Correct way to handle values (including False Positives)”, only the last value can be used. The first one still has to make a lookup to the underlying data-structure. A few ideas on how to optimize the file calls could be to split up the three major e-mail providers: Gmail, Yahoo and Hotmail into separate files and the rest in a fourth file. This approach with an async process that would return the second call would make the user experience more smooth for the end-user.

Code Snippet:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
let pbyte b =
  System.Convert.ToString(0uy+b, 2).PadLeft(8,'0')
  |> Seq.map(fun x -> x |> function | '0' -> "□" | _ -> "■")
  |> Seq.reduce(+)

let rand  = System.Random()

sizeof<bool>;;
sizeof<byte>;;

// Array of random booleans
Array.init (1<<<6) (
  fun _ -> System.Convert.ToBoolean(rand.Next(0,2))
           |> fun x -> System.Convert.ToByte(x) |> pbyte);;

// Array of random bytes
Array.init (1<<<6) (fun _ -> byte(rand.Next(0,256)))
|> Array.map(fun x -> x |> pbyte);;

Code output:

> val it : int = 1
> val it : int = 1
> val it : string [] =
  [|"□□□□□□□□"; "□□□□□□□■"; "□□□□□□□□"; "□□□□□□□■"; "□□□□□□□□"; "□□□□□□□□";
    "□□□□□□□□"; "□□□□□□□■"; "□□□□□□□■"; "□□□□□□□□"; "□□□□□□□■"; "□□□□□□□□";
    "□□□□□□□□"; "□□□□□□□□"; "□□□□□□□■"; "□□□□□□□□"; "□□□□□□□□"; "□□□□□□□■";
    "□□□□□□□■"; "□□□□□□□■"; "□□□□□□□■"; "□□□□□□□■"; "□□□□□□□■"; "□□□□□□□■";
    "□□□□□□□□"; "□□□□□□□■"; "□□□□□□□□"; "□□□□□□□■"; "□□□□□□□□"; "□□□□□□□□";
    "□□□□□□□□"; "□□□□□□□□"; "□□□□□□□■"; "□□□□□□□■"; "□□□□□□□□"; "□□□□□□□■";
    "□□□□□□□■"; "□□□□□□□□"; "□□□□□□□■"; "□□□□□□□□"; "□□□□□□□■"; "□□□□□□□□";
    "□□□□□□□■"; "□□□□□□□□"; "□□□□□□□□"; "□□□□□□□■"; "□□□□□□□□"; "□□□□□□□■";
    "□□□□□□□■"; "□□□□□□□□"; "□□□□□□□□"; "□□□□□□□□"; "□□□□□□□□"; "□□□□□□□■";
    "□□□□□□□■"; "□□□□□□□■"; "□□□□□□□■"; "□□□□□□□■"; "□□□□□□□■"; "□□□□□□□■";
    "□□□□□□□■"; "□□□□□□□■"; "□□□□□□□■"; "□□□□□□□■"|]
> val it : string [] =
  [|"■■□■□■■□"; "■□■□■□■■"; "□□□■■□■■"; "■■■■■■■■"; "■■□■□■□■"; "■■■■□□□□";
    "■■■■□■□■"; "□■■□■□■■"; "■■■□□□□■"; "□■■■□■□□"; "□■■■□■■■"; "□■□□■□□■";
    "■□□■□■□■"; "□□■□□■■□"; "□□□□□□□■"; "□□■■■□□□"; "■■□■□□■■"; "□□□■■■■■";
    "□■□□□■□□"; "□■□■■□■□"; "■■□□■□■■"; "□■■■□□■□"; "■□□□■■■□"; "■■■■□■□□";
    "■□■□■■■■"; "■□□■■□■■"; "■□■□■□■□"; "■□□■■■□□"; "■□■□□□■■"; "■■■□■■■□";
    "□□□■□□■□"; "□□■□■□□□"; "□■■■□□□□"; "■□□□□□□■"; "■□■■■■□■"; "■■■■□■□■";
    "□□□■■□□□"; "□■□■□■□□"; "■□■□■□□□"; "■□□□■■■□"; "■□■□□□■□"; "□□□■■■■□";
    "□□■□■■■□"; "■■□□□■■□"; "□□□□□□□□"; "□□□□■■■□"; "□■■□□□■■"; "■■■□■□□■";
    "□□■■□■■□"; "■■■■□■□■"; "□□□□□■■■"; "□□□□□□□□"; "□■□■□□■■"; "■■□□■■□■";
    "■■□■□■□■"; "■□■□■■■□"; "□□■■■□■■"; "■□□■■□■□"; "□■□□□□■□"; "■■■□□□□□";
    "■■□■□■■■"; "■□■□□□□■"; "■■□□□□■■"; "□■□■□□■□"|]

Last year the Human Rights Campaign created the Marriage Equality logo:

All

I thought to myself, why not make a logo for the ƒuntional people who want to create ƒunctional applications but aren’t allowed to do it because of the old fashioned and conservative software industry. So I made this logo:

All

Well I made the logo but forgot to write a blog post about it. But now and coinciding with the 1 year anniversary of the Marriage Equality logo, 2013-03-25, why not bring up the issue with this logo so people who want to make ƒuntional software can do it without being worried or persecuted by the masses.

If you have a little ƒuntional programmer in you, now it’s the time to come out of the closet :-)

Bret Victor The Future of Programming