Just wanted to share this new edX course on F# really quick: https://www.edx.org/course/programming-f-microsoft-dev207-1x

comp.sci
computer science for geeks

Just wanted to share this new edX course on F# really quick: https://www.edx.org/course/programming-f-microsoft-dev207-1x

When faced with the challenge of designing a domain-specific language for validating a document and enforcing certain behavioural policies on it, performance springs to mind. Documents that mandate such sophisticated validation set-ups typically come with a comparatively large set of fields that may change and in turn effect more changes. Since validation (usually) is a strictly functional process (i.e. validate is a function that takes an input and gives its validity), an expression-based language seemed like the most logical choice.

**1. Expressions and the stack**

If the most abstract type of node in an object graph modeling the syntax tree is an expression (i.e. there are no statements and no *blocks*), we don’t need a stack. If you don’t need a stack, things become very easy to parallelize. The consumers of the stack do intrinsically rely on a certain order of execution. If you can not rely on a **pop **yielding the value that you **push**ed just before, things get messy and (rightfully) break.

When looking at programs as functions, we do no longer have this problem. Take any binary expression (e.gyou . and) and make its operands expressions, and you’re looking at a function that takes two expressions and gives a boolean; this corresponds to prefix notation (i.e. *and(1, 0) = 0*).

**2. Observable<T> vs Future<T>**

The first problem with the above model arises when you need to react to specific events (e.g. *if *X occurs *then *do Y). In this domain, the most common event one needs to react to is the change of some property (field) of the document. This is where the absence of a stack starts to create some unnecessary roadblocks. We would probably like to be able to model something like this:

1 2 3 |
If ValueOf(Field_A) != KnownValueOf(Field_A) Then If ValueOf(Field_A) = '123' And CheckedStateOf(Checkbox_A) = Checked Then SetCheckedStateOf(Checkbox_B) |

We subscribe to the value of *Field_A*, if we observe a change and the state of *Checkbox_A *is checked, then we want to set *Checkbox_B* to checked as well. The problem that might not be immediately apparent is the transport of the value of Field_A to the observer of the former. We either need a named value (some structure akin to the free store), or we need a stack so that we can pop the observed value as needed.

If, however, we make a function ChangedValueOf which promises to return a T, we can rewrite the above algorithm like this:

1 2 3 4 5 6 7 |
SetCheckedStateIf( Checkbox_B, And( Equals(ChangedValueOf(Field_A, '123')), CheckedStateOf(Field_B) ) ) |

We no longer have a problem. Of course, writing policies like this will quickly get ugly, which is why our parser should be able to take a prettier (less deeply nested) representation of the above and build the AST accordingly. The invocation of *Equals *equality check function becomes the continuation of the Future<T> given by *ChangedValueOf*. The trick is to block the future until the value actually changed. Since we are working with snapshots of the document (in order to avoid progressively polluting the rulesets input with changes made as a result of its own evaluation), this becomes difficult to model.

So what do we do?

**3. Ad-hoc rewriting the AST**

The only solution I could come up with is rewriting the AST as-needed. We need to be able to take any expression and change it on-the-fly.

Posted in Computer Science, Functional Programming

Today I decided that it would be a good idea to repurpose my 2011 Raspberry Pi as a lean web- and Linux-development system. I also decided that it would be a good idea to store any data off-device on my Synology NAS. The RPi was outfitted with Raspbian using the NOOBS Setup toolchain. After initial setup I disconnected the RPi from all input peripherals and the screen and hooked it up to my switch instead.

**Step 1.) Networking setup**

The RPi will by default use my router’s DHCP server to find its IP. This is not strictly what I want, as I sometimes use a different network setup and would prefer to have the RPi to have a static IP in my reserved server range (192.168.192.100/30), where my Synology amongst other devices is also situated.

Quickly asserting that the RPi can see the DS:

1 2 3 4 5 6 7 |
root@raspberrypi:/home# ping -c1 192.168.192.100 PING 192.168.192.100 (192.168.192.100) 56(84) bytes of data. 64 bytes from 192.168.192.100: icmp_req=1 ttl=64 time=0.752 ms --- 192.168.192.100 ping statistics --- 1 packets transmitted, 1 received, 0% packet loss, time 0ms rtt min/avg/max/mdev = 0.752/0.752/0.752/0.000 ms |

I continued to configure the *interfaces (5)*:

1 2 3 4 5 6 7 8 9 10 11 12 |
pi@raspberrypi ~ $ cat /etc/network/interfaces # loopback interface auto lo iface lo inet loopback # ethernet interface iface eth0 inet static address 192.168.192.101 gateway 192.168.192.1 netmask 255.255.255.0 network 192.168.192.0 broadcast 192.168.192.255 |

**Step 2.) Setting up everything on the Synology side of things**

Next, I set up a new share and a user in my Synology DS (cleverly called “rpi”):

**Step 3.) (Auto-)Mounting the network share on the RPi **

And finally, I mounted the CIFS share, following the steps described in this Synology wiki article. Which basically boiled down to:

1 |
//192.168.192.100/rpi-root /mnt/synology-store cifs user,uid=root,gid=users,rw,suid,credentials=/etc/cifspwd 0 0 |

This *fstab (5) *configuration. The ultimate result can be marvelled at here:

Next steps:

- Setting up nginx and various interpreters for languages (PHP, Python, etc.) via FastCGI, running on the RPi using the synology-store for storage
- Setting up redis, MySQL and various other RDBMS on the Synology – or perhaps a second RPi
- Start playing!

Posted in Computer Science, Media

Here’s my solution for the sixth Project Euler problem. I do not really see how this is hard. Perhaps there is a smarter way of solving this? Looking forward to your feedback.

1 2 3 4 5 |
let square n = n * n let sumOfSquares n = {1..n} |> Seq.map square |> Seq.sum let squareOfSum n = {1..n} |> Seq.sum |> square let solution = squareOfSum 100 - sumOfSquares 100 |

I just remembered that there is a formula for finding the sum of a series of natural numbers. I am going to try and see if I can work with that to find a more efficient solution.

Posted in Functional Programming, Project Euler

So here’s my brute force solution for the fifth Project Euler problem in F#.

1 2 |
let solution = Seq.initInfinite (fun i -> 20 * (i+1)) |> Seq.find (fun n -> {2..20} |> Seq.forall (fun x -> n % x = 0)) |

I did not really understand this problem. Perhaps certainly there is a more efficient solution. Either way, the code works 🙂

Posted in Functional Programming, Project Euler

Today, I’m going to attempt to solve the fourth Project Euler problem in F#. I only have about 15 minutes before I need to get back to doing something different, so I’ll probably just leave this post hanging until I find time to advance the code.

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.

So, the first function I am going to write is “palindrome of n” (i.e. produce 9009 from 90):

1 2 3 4 |
let palindrome n = let reverse (s:string) = new string(Array.rev(s.ToCharArray())) let s = n.ToString() int64 (s + reverse(s)) |

The largest product of any 3-digit number is 999² = 998001; this means that the upper bound of palindromes we need to test against is 997799. So here’s the generator for the series of palindromes we need to factorize:

1 2 |
let palindromes = seq {997L .. -1L .. 100L} |> Seq.map palindrome |

Update 2015-05-02: Finally found some time to finish this. I basically wrote a function that will spit out all factors of n where every factor is element of the set {100..999}. Here goes:

1 2 |
let threeDigitFactors n = seq {999L .. -1L .. 100L} |> Seq.where (fun x -> n%x=0L) |

I then wrote another function which applies threeDigitFactors to all palindromes and finds the largest sum of factors:

1 2 3 |
let thePalindrome = palindromes |> Seq.map threeDigitFactors |> Seq.maxBy (fun x -> Seq.sum x) |

Which yielded:

1 2 |
> thePalindrome;; val it : seq<int64> = seq [993L; 913L] |

I do realize that this is inefficient, but I am not too maths-savvy to come up with a better solution at this point.

Posted in Functional Programming, Project Euler

Before heading back into the real world, I am going to attempt to solve the third Project Euler problem.

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

I currently have no idea how to implement prime decomposition efficiently in * any *language. I do however know that n is prime if not a multiple of any number [2..sqrt(n)] , so this seems like the most logical starting point.

1 2 3 4 |
// Returns true iff n is prime let isPrime n = seq {2L .. n |> float |> sqrt |> int64} |> Seq.exists (fun x -> n % x = 0L) |> not |

I have had quite a hard time trying to implement [2 .. sqrt n], let me know if there is a better way of doing this. Next, I wrote a function to find all the factors of a number:

1 2 |
// Returns the factors for n let factors n = seq {for i in 2L .. n/2L do if n % i = 0L then yield i} |

Originally, I had attempted to use this directly with the “isPrime” function in order to yield the largest prime using Seq.max:

1 2 3 |
let maxPrimeFactor n = factors n |> Seq.where isPrime |> Seq.max |

This kept resulting in System.OutOfMemoryException: Exception of type 'System.OutOfMemoryException' was thrown. because it naturally attempted to check all of the resulting factors for (a) their primeness and then find out the maximum value. So I went and wrote another function “factorsReverse”, so that we may use Seq.find (which returns as soon as the given _ -> bool evaluates to true):

1 |
let factorsReverse n = factors n |> Seq.map (fun m -> n / m) |

Runtime was immensely reduced and there were no more Out-of-Memory exceptions!

1 2 |
> maxPrimeFactor 600851475143L;; val it : int64 = 6857L |

Posted in Functional Programming, Project Euler

In continuation of my F# efforts, I am going to try and solve the second Project Euler Problem. Here’s the problem:

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Just like for problem 2, the last sentence of the problem is basically the final code:

1 2 3 4 |
let fibSum = Seq.unfold (fun (n, m) -> Some(n+m, (m, n+m))) (0,1) |> Seq.takeWhile (fun n -> n <= 4000000) |> Seq.filter (fun n -> n % 2 = 0) |> Seq.sum |

This was fun to implement. Originally I had made a recursive sequence generator for the fibonacci series (the rest of the code was basically the same however). Seq.unfold basically unfolds a given generator (which in this case is a lambda expression) into a sequence given initial state (0, 1).

Posted in Functional Programming, Project Euler

Whenever I am trying to learn a language that I have no clue about, I like solving the Project Euler problems with it. I’m going to share my solutions here and hope that I can either help somebody understand the problem / solution or the language or if someone gave me feedback on how to improve!

The problem I’m going to solve in this post is “Problem 1: Multiples of 3 and 5“.

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

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

Basically, the last sentence “sum of all multiples of 3 or 5 below 1000” already seems like it could be actual source code of a rather expressive programming language. What we have here is a set of numbers where every number is divisible by 3 or 5. In order to determine whether a number is divisible by 3 or 5 we need to write ourselves a function that can determine whether a number is divisble by another number. We can then use this function to build a new function that will tell whether its input is divisible by either 3 or 5.

1 2 3 4 5 |
// Returns true iff n is a multiple of d let isMultiple n d = (n % d) = 0 // Returns true iff n is a multiple of 3 or 5 let isMultipleOf3Or5 n = isMultiple n 3 || isMultiple n 5 |

Based on this we then get the sequence “all multiples of 3 or 5 below 1000”:

1 2 |
let sumOfMultiples = seq { for n in 1..1000 do if isMultipleOf3Or5 n then yield n } |> Seq.sum |

Executing the FSX script yielded the correct answer: val sumOfMultiples : int = 233168. In retrospect I would probably have preferred to have a generalized isMultipleOf3Or5 accepting a list for the “d” parameter. I am quite satisfied with my first F# program taking me less than 5 minutes to get correct, however.

On to the next problem!

Posted in Functional Programming, Project Euler

## Recent Comments