tag:blogger.com,1999:blog-81442854050795381812024-03-04T23:07:25.512-08:00MOVED TO: raichoo.github.ioraichoohttp://www.blogger.com/profile/05235774661802634100noreply@blogger.comBlogger119125tag:blogger.com,1999:blog-8144285405079538181.post-32803748648070448342013-06-24T12:13:00.001-07:002013-06-24T12:13:26.702-07:00Moving to raichoo.github.ioHi,
I've decided to move this blog to <a href="http://raichoo.github.io">raichoo.github.io</a>.
Cya there!raichoohttp://www.blogger.com/profile/05235774661802634100noreply@blogger.com0tag:blogger.com,1999:blog-8144285405079538181.post-43697192949012291272013-05-31T09:54:00.000-07:002013-05-31T09:54:23.531-07:00Calling Idris from Javascript and vice-versa.Until now the JavaScript backend for Idris has been a nice little gimmick to play around with, but when it comes to writing real applications it's pretty limited.<br />
The limitations originates from the way how the FFI interacts with JavaScript. Until now it was not possible to call Idris code from within JavaScript which is essential when you want to register callbacks. In this blogpost I present my current work on the Idris FFI and JavaScript backend which enables this functionality. (Until these features have been merged into master you can track the development <a href="https://github.com/raichoo/Idris-dev/commits/javascript">here</a>)<br />
<br />
Let's write a very simple piece of code that just changes a text label when it gets<br />
clicked.<br />
<br />
To do this we will need to define our onclick function. It'll look like this:<br />
<br />
<code></code><br />
<pre><code>setOnClick : HTMLElement -> (() -> IO ()) -> IO ()
setOnClick (Elem p) f =
mkForeign (FFun ".onclick=" [FPtr, FFunction FUnit (FAny (IO ()))] FUnit) p f</code></pre>
<pre><code>
</code></pre>
Let's break down what happens here. We are defining a function that takes an HTMLElement and a function that performs a side effect that should get executed whenever we click on the element. I'm using the FPtr type to represent a element. The name of the function tells the FFI that "onclick" is a field of an element. Whenever a name starts with a dot the FFI concludes that the first argument has to be an object and the name of the function is one of its fields. When the name ends with an equals sign it concludes that we are dealing with an assignment. In <a href="http://raichoo.blogspot.de/2013/01/idris-to-javascript-playing-with-ffi.html">my previous blogposts</a> I'm explaning how these mechanisms are used.<br />
The second argument of our onclick function is of type "FFunction" takes an FUnit and returns a FAny (IO ()). mkForeign translates this into a function of type () -> IO (). For more information about the Idris FFI take a look at the <a href="http://www.cs.st-andrews.ac.uk/~eb/writings/idris-tutorial.pdf">tutorial</a>.
I've got a little bit of code on my <a href="https://gist.github.com/raichoo/5686199">gist</a> that shows the FFI in action.<br />
<br />
Have fun with calling functions back and forth :3
<br />
<br />
<br />
<div style="text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEisw2Po2StJT9udJCAhaoXwdnMcMkhC1410R9GbmbN7YB04SWvLWIj0pEGZgH9GJT8a_a9cbKwdxIs-zzkYV4nt4OqSMVIv7O5sV9_eP61rfBbIhSUUweh_O6RI_JeB_dXfJuVd85kAO0ro/s1600/38284960.jpg" imageanchor="1"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEisw2Po2StJT9udJCAhaoXwdnMcMkhC1410R9GbmbN7YB04SWvLWIj0pEGZgH9GJT8a_a9cbKwdxIs-zzkYV4nt4OqSMVIv7O5sV9_eP61rfBbIhSUUweh_O6RI_JeB_dXfJuVd85kAO0ro/s320/38284960.jpg" /></a>
</div>
raichoohttp://www.blogger.com/profile/05235774661802634100noreply@blogger.com2tag:blogger.com,1999:blog-8144285405079538181.post-46344241308918754112013-02-13T09:36:00.001-08:002013-02-13T09:36:45.335-08:00Shrinking Idris JavaScript with Closure Compiling Idris to JavaScript can result in some pretty large files. In fact, small Idris programs can become so large that one might consider to fall back to JavaScript because it's just not worth it.
<br />
<br />
Let's take a look at a very simple example:
<br />
<blockquote class="tr_bq">
<code>
main : IO ()<br />main = do<br /> print l<br />where<br /> l : List Nat<br /> l = [1,2,3,4,5]</code></blockquote>
Let's compile this program and take a look at the size of the generated JavaScript.
<br />
<blockquote class="tr_bq">
<code>
raichoo@lain tmp» ls -lh test1.js<br />-rw-r--r-- 1 raichoo users 35K Feb 13 17:40 test1.js<code></code></code></blockquote>
35K of code is actually quite a lot for such a small program, but let's take into account that the file contains the whole runtime plus all needed parts of the standard library.
<br />
<br />
However, it gets even worse. The above program can be written in a different way. Let's give it a try.
<br />
<blockquote class="tr_bq">
<code>
module Main<br />
<br />
main : IO ()<br />
main = do<br />
print l<br />
where<br />
l : List Nat<br />
l = [1..5]</code></blockquote>
Just a small change. Instead of writing down the whole List we are using a range. Now let's take a look at the output.<br />
<blockquote class="tr_bq">
<code>
raichoo@lain tmp» ls -lh test2.js<br />-rw-r--r-- 1 raichoo users 99K Feb 13 17:45 test2.js<code></code></code></blockquote>
<div>
Yikes, 99K! How did that happen?<br />
<br />
Ranges are not built in, they are just a syntax extension that has been defined in the standard library and it uses a couple of functions to do what it does. We are now pulling in even more of the standard library.<br />
<br />
Anyway, a simple change and the code grows by a factor of almost 3. Granted, there is an upper bound to the amount of code we can pull in from the library, but that's not very comforting.<br />
<br />
Is there something we can do about this?<br />
<br />
Yes. The <a href="https://developers.google.com/closure/">Google Closure</a> compiler can do a whole lot of optimizations on JavaScript. Apart from the usual minifying it also can do inlining and dead code elimination.<br />
<br />
Running Closure on our JavaScript files yields the following results:
<br />
<blockquote class="tr_bq">
<code>
raichoo@lain tmp» closure test1.js > test1-cl.js<br />raichoo@lain tmp» closure test2.js > test2-cl.js<br />raichoo@lain tmp» ls -lh test?-cl.js<br />-rw-r--r-- 1 raichoo users 20K Feb 13 18:12 test1-cl.js<br />-rw-r--r-- 1 raichoo users 63K Feb 13 18:13 test2-cl.js</code></blockquote>
<div>
That's smaller, but we can do even better. Idris targets Closure's advanced optimizations which can be enabled with the <code>--compilation_level=ADVANCED_OPTIMIZATIONS</code> flag (e.g. <code>closure --compilation_level=ADVANCED_OPTIMIZATIONS</code>). We don't need to take care of the <a href="http://google-styleguide.googlecode.com/svn/trunk/javascriptguide.xml">Closure Guidelines</a> ourselves, Idris does that for us.<br />
<br />
Here's the result:
<br />
<blockquote class="tr_bq">
<code>
raichoo@lain tmp» ls -lh test?-cla.js<br />-rw-r--r-- 1 raichoo users 7.9K Feb 13 18:18 test1-cla.js<br />-rw-r--r-- 1 raichoo users 34K Feb 13 18:18 test2-cla.js</code></blockquote>
<br />
Now that's A LOT better. While Closure cannot get rid of the additional library code, it can eliminate code from Idris' runtime (we don't need big integers in this example, therefore Closure just get's rid of the code). Names get compressed and inlining takes place, etc etc.<br />
<br />
I hope this shows that's Idris can create reasonably sized JavaScript files with a little help from it's friends.<br />
<br />
Have fun with that!</div>
</div>
raichoohttp://www.blogger.com/profile/05235774661802634100noreply@blogger.com0tag:blogger.com,1999:blog-8144285405079538181.post-79173569122382602732013-01-21T12:42:00.003-08:002013-06-03T00:16:22.555-07:00Idris to JavaScript: Playing with the FFIUntil now the FFI for the JavaScript backend for Idris is quite primitive and somehow I'd like to keep it that way since I don't want to make invasive changes to the language just because of a different target. Therefore a started a little experiment to see how far one can get with the current FFI.<br />
In JavaScript can have fields of objects, methods, functions, arrays etc etc. and we need to cover all these cases. Let's start with a little case study. We want to manipulate the DOM. Here is a little HTML snippet to begin with:<br />
<br />
<pre><span class="hs-varop"><</span><span class="hs-varid">html</span><span class="hs-varop">></span>
<span class="hs-varop"><</span><span class="hs-varid">head</span><span class="hs-varop">></span>
<span class="hs-varop"></</span><span class="hs-varid">head</span><span class="hs-varop">></span>
<span class="hs-varop"><</span><span class="hs-varid">body</span><span class="hs-varop">></span>
<span class="hs-varop"><</span><span class="hs-varid">div</span> <span class="hs-varid">id</span><span class="hs-keyglyph">=</span><span class="hs-str">"test"</span><span class="hs-varop">></span><span class="hs-conid">Foobar</span><span class="hs-varop"></</span><span class="hs-varid">div</span><span class="hs-varop">></span>
<span class="hs-varop"><</span><span class="hs-varid">script</span> <span class="hs-varid">src</span><span class="hs-keyglyph">=</span><span class="hs-str">"test.js"</span><span class="hs-varop">></</span><span class="hs-varid">script</span><span class="hs-varop">></span>
<span class="hs-varop"></</span><span class="hs-varid">body</span><span class="hs-varop">></span>
<span class="hs-varop"></</span><span class="hs-varid">html</span><span class="hs-varop">></span>
</pre>
Now we want to replace the text of the Node with the id <code>test</code><br />
<br />
<code><pre>
module Main
data HTMLElement : Type where
Elem : Ptr -> HTMLElement
data NodeList : Type where
Nodes : Ptr -> NodeList
query : String -> IO NodeList
query q = do
e <- mkForeign (FFun "document.querySelectorAll" [FString] FPtr) q
return (Nodes e)
item : NodeList -> Int -> IO HTMLElement
item (Nodes p) i = do
i <- mkForeign (FFun ".item" [FPtr, FInt] FPtr) p i
return (Elem i)
getId : HTMLElement -> IO String
getId (Elem p) = mkForeign (FFun ".id" [FPtr] FString) p
setText : HTMLElement -> String -> IO ()
setText (Elem p) s =
mkForeign (FFun ".textContent=" [FPtr, FString] FUnit) p s
main : IO ()
main = do
e <- query "#test"
i <- item e 0
s <- getId i
setText i (s ++ ": SUPERFOO!!!")
</pre></code>
<br />
In this example I'm using the Ptr type for raw JavaScript values and wrap them in ADTs. The interesting part is in the definition of the foreign functions. Functions starting with "." are methods or fields, that means that the first argument of the function is handled as and object and the function call gets translated into a method
or field name. Functions ending with "=" are turned into assignments<br />
<br />
Another thing we have to consider is that sometimes we want to refer to a method with no arguments, therefore we have to distinguish them from reading a field. In our example we read the value of the field <code>id</code>. If we wanted to turn that into a method call we need to declare it like this:<br />
<code></code><br />
<pre><code>mkForeign (FFun ".id" [FPtr, FUnit] FString) p ()
</code></pre>
<code>
</code>
We simply add an argument of type FUnit to the argument list and apply ().<br />
Operations on arrays are declared like this:<br />
<code></code><br />
<pre><code>mkForeign (FFun ".id[]" [FPtr, FInt] FString)
mkForeign (FFun ".id[]=" [FPtr, FInt, FString] FString)
</code></pre>
<code>
</code>
The second argument is treated as an index<br />
Working with the FFI is still dangerous, I'm currently unaware of a different way to do this without changing Idris' FFI which is something I don't want to. Another thing I don't want to do is making the FFI overly complex, it should be very low level and provide the basic building blocks for interacting with JavaScript. Anyway, patches are welcome ^^
<br />
One thing that might be worth considering is a way to declare safe foreign calls that do not need to be wrapped in IO.<br />
<pre><code><!-----><!-----></code></pre>
<code>
</code>raichoohttp://www.blogger.com/profile/05235774661802634100noreply@blogger.com3tag:blogger.com,1999:blog-8144285405079538181.post-29722022021682073932013-01-18T14:11:00.001-08:002013-02-26T09:24:04.001-08:00Towards dependently typed webprogramming with IdrisJavaScript pretty much has become the lingua franka of the web. It runs in the browser, and since <a href="http://nodejs.org/">nodejs</a> it's also possible to write server applications. However, it lacks a powerful type-system, and type-systems are something a lot of us have come to love. Anyway, this is not the time for the usual "dynamic vs. static" and "weak vs. strong typing" blog post. Today I want to write about <a href="https://github.com/raichoo/Idris-dev/commits/javascript">a project I've started working on</a> which brings <a href="http://en.wikipedia.org/wiki/Dependent_type">dependent types</a> to the JavaScript ecosystem meaning a JavaScript backend for the <a href="http://idris-lang.org/">Idris</a> compiler.<br />
The foundation of this effort, the programming language Idris by Edwin Brady. Idris is basically the answer to the question: "What would Haskell look like if it had full dependent types?" It has strict semantics but also offers annotations for non-strict evaluation. If you want to know more about Idris can highly recommend <a href="http://www.cs.st-andrews.ac.uk/~eb/writings/idris-tutorial.pdf">the tutorial</a>. Sadly there is not a lot of material out there to learn about programming with dependent types but I will link some resources in this blog post.<br />
The backend itself compiles a large set of the language into a self contained Javascript file and offers a simple FFI to communicate with other libraries. It's still every experimental and I would not recommend to use it in your dayjob. However, if you feel like it feel free to contribute libraries and patches to complete the experience and transform Idris into a suitable language for web programming :)<br />
<br />
How to use it:<br />
Let's write a little Idris program and compile it to JavaScript:<br />
<code></code><br />
<pre><code>module Main
product : List Integer -> Integer
product = foldl (*) 1
fac : Integer -> Integer
fac n = product [1..n]
main : IO ()
main = print (fac 300)
</code></pre>
<code>
</code>
and compile it<br />
<code></code><br />
<pre><code>> idris --target javascript test.idr -o test.js
</code></pre>
<code>
</code>
and run it<br />
<code></code><br />
<pre><code>> node test.js
… long output is long …
</code></pre>
<code>
</code>
As you can see, the backend also supports big integers. The generated file is completely self contained including code from the standard library like typeclasses etc. (not everything but the code you need).<br />
Now lets use the FFI to call into JavaScript land!<br />
<code></code><br />
<pre><code>module Main
product : List Integer -> Integer
product = foldl (*) 1
fac : Integer -> Integer
fac n = product [1..n]
alert : String -> IO ()
alert s = mkForeign (FFun "alert" [FString] FUnit) s
main : IO ()
main = alert $ show (fac 300)
</code></pre>
<code>
</code>
Compile and run it in a browser of your choice ^^<br />
This is just a little fraction of what you can do with the backend. Currently there is no support for types like Word8 and Word16 because it would not really make sense in a JavaScript context. There is also no support for filesystem operations. The code that gets generated is still rather large but with the google closure compiler you can reduce the size by a factor of 2 (advanced compilation is not supported at the moment).<br />
<br />
<br />
References:
<br />
<br />
<ul>
<li><a href="http://adam.chlipala.net/cpdt/">Certified Programming With Dependent Types</a></li>
<li><a href="http://www.youtube.com/watch?v=CmPw7eo3nQI">Talk by Andreas Bogk at Chaos Communication Camp 2011</a></li>
<li><a href="http://wiki.portal.chalmers.se/agda/pmwiki.php">Agda Wiki</a></li>
</ul>
<br />
<br />
<br />
<br />raichoohttp://www.blogger.com/profile/05235774661802634100noreply@blogger.com5tag:blogger.com,1999:blog-8144285405079538181.post-89937900722698535772012-02-04T14:21:00.000-08:002012-02-06T00:26:15.413-08:00Setting up a Tor Bridge Relay on illumosTimes are getting rough again. There are regimes out there that censor the ability of their citizens to express themselves or communicate with each other, sometimes even lives are at stake. Communication isn't a luxury, it's what makes us human, it empowers us, tears down walls between people and helps us to understand each other. Censorship and total surveillance is a violation of human rights, it's something we need to fight.
One way of doing this is to support the <a href="http://www.torproject.org/">Tor Project</a>. In this blogpost I will show how to set up a so called <a href="https://www.torproject.org/docs/bridges.html.en">bridge relay</a> on <a href="http://www.illumos.org">illumos</a>, an entry point to the tor network which empowers people that suffer under the influence of censorship and surveillance to access the internet.<br />
<br />
<b>Step 1: Building Tor under illumos</b><br />
<br />
Building Tor is easy as pie. All you need is the <a href="http://libevent.org/">libevent src</a> and the <a href="https://www.torproject.org/download/download.html.en">Tor src</a>.<br />
<br />
<b>Step 2: Setting up an illumos zone</b><br />
<br />
Since illumos inherits all the awesome features of OpenSolaris we can isolate our Tor bridge inside of a zone. We will create a zone with the name "tor".<br /><br />
Before we start we need to create a zfs dataset for our zone. I usually put mine in </code>/export/zones</code> (which itself is a dataset) like so:
<pre><code><code>[root@lain:~]> zfs create rpool/export/zones/tor</code></code></pre>
Now, let's set up the zone:
<pre><code>[root@lain:~]> zonecfg -z tor</code></pre>
<pre><code>tor: No such zone configured
Use 'create' to begin configuring a new zone.
zonecfg:test> create
zonecfg:test> set zonepath=/export/zones/tor</code></pre>
<pre><code>zonecfg:test> verify
zonecfg:test> commit
zonecfg:test> exit
[root@lain:~]> zoneadm list -cv
ID NAME STATUS PATH BRAND IP
0 global running / native shared
- test configured /export/zones/tor ipkg shared</code></pre>
<pre><code> <code> </code></code></pre>
Now we install our virtual illumos inside of the zone, this might take a few minutes.
<br />
<pre><code><code>[root@lain:~]> zoneadm -z tor install</code></code></pre>
And boot the bugger.
<br />
<pre><code><code></code><code>[root@lain:~]> zoneadm -z tor boot</code></code></pre>
Everything is set up and ready to go. We have a virtual instance of illumos running inside of a container. Time
to log into it.
<br />
<pre><code><code>
[root@lain:~]> zlogin -C tor</code></code></pre>
<br />
<b>Step 3: Setup TOR</b><br />
<br />
Time to get serious. After building Tor and putting it into our zone we now need to configure Tor to function as a Bridge Relay. Here we set up our bridge to listen on port 443. Since Tor traffic looks a lot like SSL it's a good place to run. Our <code>torrc</code> should look like this:<br />
<br />
<pre><code>SocksPort 0
ORPort 443
BridgeRelay 1
Exitpolicy reject *:*</code></pre>
<br />
I recommend that you set up a tor user to avoid running as root. The problem is that you cannot run run a server on a privileged port when you are a mere user. We can use RBAC to give the tor user a profile that allows it to run services on such ports. <br />
<pre><code><code>
[root@tor:~]> usermod -K defaultpriv=basic,net_privaddr tor</code></code></pre>
To start up tor simple we simply issue:
<pre><code><code>
[tor@tor:~]> pfexec tor -f torrc</code></code></pre>
We are ready to go!
If you've got questions or more ideas, leave me a comment.
<br/><br />
If you want to know more about the Tor Project, I recommend you this talk:<br/>
<br />
<iframe width="560" height="315" src="http://www.youtube.com/embed/GwMr8Xl7JMQ" frameborder="0" allowfullscreen></iframe>raichoohttp://www.blogger.com/profile/05235774661802634100noreply@blogger.com0tag:blogger.com,1999:blog-8144285405079538181.post-5900352345202602322012-01-04T08:20:00.000-08:002012-01-04T08:20:40.496-08:00Building GHC under Illumos<p>I like the bleeding edge, that's why I always want to have the newest compilers for my favorite languages and Haskell is one of those languages. In this blogpost I'm going to show you how to build the latest and greatest GHC on the <a href="https://www.illumos.org/">Illumos</a> distribution <a href="http://openindiana.org/">OpenIndiana</a>. If you don't want to build it yourself you can pick up a fairly recent version of GHC from the <a href="http://wiki.openindiana.org/oi/Spec+Files+Extra+Repository">SFE Repository</a>.</p>
<p>To make things easier let's get our hand on a GHC binary from which we can bootstrap our environment, luckily there is a package for <a href="http://www.haskell.org/ghc/dist/7.0.3/maeder/ghc-7.0.3-i386-unknown-solaris2.tar.bz2">GHC 7.0.3 for Solaris</a> which works just fine under Illumos. Just install it and put it in your PATH environment variable.</p>
<p>Due to it's Solaris heritage, Illumos currently ships with a pretty outdated version of GCC. I recommend that you install the GCC provided by the <a href="http://wiki.openindiana.org/oi/Spec+Files+Extra+Repository">SFE Repository</a> since the shipped version causes some linking problems when dealing with the hidden attribute. If you have to use the old compiler you can get rid of this issue by using this quick and dirty patch which just gets rid of some pragmas and macros:
<pre><code>
diff --git a/includes/Rts.h b/includes/Rts.h
index 91ec76d..adbbe54 100644
--- a/includes/Rts.h
+++ b/includes/Rts.h
@@ -52,7 +52,7 @@ extern "C" {
// with visibility "hidden" to hide them outside the RTS shared
// library.
#if defined(HAS_VISIBILITY_HIDDEN)
-#define RTS_PRIVATE GNUC3_ATTRIBUTE(visibility("hidden"))
+#define RTS_PRIVATE //GNUC3_ATTRIBUTE(visibility("hidden"))
#else
#define RTS_PRIVATE /* disabled: RTS_PRIVATE */
#endif
diff --git a/rts/BeginPrivate.h b/rts/BeginPrivate.h
index 6471b92..1af4c90 100644
--- a/rts/BeginPrivate.h
+++ b/rts/BeginPrivate.h
@@ -6,5 +6,5 @@
error: visibility attribute not supported in this configuration; ignored
*/
#if defined(HAS_VISIBILITY_HIDDEN) && !defined(freebsd_HOST_OS)
-#pragma GCC visibility push(hidden)
+//#pragma GCC visibility push(hidden)
#endif
diff --git a/rts/EndPrivate.h b/rts/EndPrivate.h
index 4cfb68f..c2e3154 100644
--- a/rts/EndPrivate.h
+++ b/rts/EndPrivate.h
@@ -1,3 +1,3 @@
#if defined(HAS_VISIBILITY_HIDDEN) && !defined(freebsd_HOST_OS)
-#pragma GCC visibility pop
+//#pragma GCC visibility pop
#endif
</code></pre></p>
<p>Now we are good to go. Get your hands on some fresh tarball, perhaps the latest and greatest RC.
To configure your future GHC just run something like:
<pre><code>
./configure --prefix=~/Library/GHC/version --with-gmp-includes=/usr/include/gmp
</code></pre>
I usually install self compiled software in <code>~/Library/program/version</code>. From here I can manage everything using softlinks but feel free to use any other prefix.</p>
<p>Be sure to run the GNU Make (<code>gmake</code>) command and not the Illumos one. Sadly <code>gmake</code> seems to be unable to handle multiple jobs when compiling GHC so our final step looks like this:
<pre><code>
gmake && gmake install
</code></pre></p>
<p>From here on you should be able to build pretty much every version you wish for. If you pick a version that is supported by <code>cabal-install</code> installing additional packages from <a href="http://hackage.haskell.org/packages/hackage.html">hackage</a> is a piece of cake. I usually have more than one GHC installed, the one that is shipped with the current <a href="http://hackage.haskell.org/platform/">Haskell Platform</a> and the latest version with all the hot new features.</p>
<p>Illumos has the potential to be one of the best platforms for developing Haskell since it has exquisite <a href="http://de.wikipedia.org/wiki/DTrace">DTrace</a> support. If you want to help to improve the Haskell experience on Illumos, feel free to contact me in #openindiana on freenode.</p>raichoohttp://www.blogger.com/profile/05235774661802634100noreply@blogger.com2tag:blogger.com,1999:blog-8144285405079538181.post-11811922781709392552011-08-24T11:21:00.000-07:002011-08-28T04:39:39.912-07:00More Fun with Scala "Dependent" TypesIn <a href="http://raichoo.blogspot.com/2011/08/taste-of-dependent-types-in-scala.html">my last post</a> I wrote about lists that encode their length within their type and the possibilities that gives us to ensure correctness of our code. In this post I want to expand these ideas.
<br />
<br />Let's assume that we have a list with an even number of elements. By knowing that the length is even we could do various things like extracting pairs. Odd length is not very suitable for this… no shit Sherlock!
<br />
<br />To make this happen we first need boolean values in the type system to represent that a proposition is actually true and we need to be able to negate them.
<br />
<br /><pre><code><blockquote><font color="#ff9900">sealed</font> <font color="#ff9900">trait</font> Bool {
<br /> <font color="#ff9900">type</font> Not <: Bool
<br />}
<br /><font color="#ff9900">sealed</font> <font color="#ff9900">trait</font> True <font color="#ff9900">extends</font> Bool {
<br /> <font color="#ff9900">type</font> Not = False
<br />}
<br /><font color="#ff9900">sealed</font> <font color="#ff9900">trait</font> False <font color="#ff9900">extends</font> Bool {
<br /> <font color="#ff9900">type</font> Not = True
<br />}</blockquote></code></pre>
<br />In the next step we have to extend our type-level natural numbers. Let's give them a predecessor and a property that indicates if a number is even.
<br /><pre><code><blockquote>
<br /><font color="#ff9900">sealed</font> <font color="#ff9900">trait</font> Nat {
<br /> <font color="#ff9900">type</font> IsEven <: Bool
<br /> <font color="#ff9900">type</font> Pred <: Nat
<br />}
<br /><font color="#ff9900">sealed</font> <font color="#ff9900">trait</font> Z <font color="#ff9900">extends</font> Nat {
<br /> <font color="#ff9900">type</font> IsEven = True
<br /> <font color="#ff9900">type</font> Pred = Z
<br />}
<br /><font color="#ff9900">sealed</font> <font color="#ff9900">trait</font> S[A <: Nat] <font color="#ff9900">extends</font> Nat {
<br /> <font color="#ff9900">type</font> IsEven = A#IsEven#Not
<br /> <font color="#ff9900">type</font> Pred = A
<br />}
<br /></blockquote></code></pre>
<br />To make it a little nicer to read and write we will add a witness that represents that a natural number is even we check this with the <code>=:=</code> type constraint which witnesses that two types are equal.
<br /><pre><code><blockquote>
<br /><font color="#ff9900">sealed</font> <font color="#ff9900">trait</font> Even[A <: Nat]
<br /><font color="#ff9900">object</font> Even {
<br /> <font color="#ff9900">implicit</font> <font color="#ff9900">def</font> isEven[A <: Nat](<font color="#ff9900">implicit</font> e: A#IsEven =:= True): Even[A] =
<br /> <font color="#ff9900">new</font> Even[A]{}
<br />}
<br /></blockquote></code></pre>
<br />Now the fun part. We now start building our list with a getPairs method that only works on lists with an even length. Here is our interface for this NList:
<br /><pre><code><blockquote>
<br /><font color="#ff9900">sealed</font> <font color="#ff9900">trait</font> NList[A <: Nat, +B] {
<br /> <font color="#ff9900">type</font> Length = A
<br /> <font color="#ff9900">def</font> getPairs(<font color="#ff9900">implicit</font> e: Even[Length]): List[(B, B)]
<br /> <font color="#ff9900">def</font> head: B
<br /> <font color="#ff9900">def</font> tail: NList[Length#Pred, B]
<br />}
<br /></blockquote></code></pre>
<br />The first case again is trivial, we are dealing with an empty list, the only thing that we can extract is an empty list.
<br /><pre><code><blockquote>
<br /><font color="#ff9900">case</font> <font color="#ff9900">object</font> NNil <font color="#ff9900">extends</font> NList[Z, Nothing] {
<br /> <font color="#ff9900">def</font> getPairs(<font color="#ff9900">implicit</font> e: Even[Length]): List[(Nothing, Nothing)] =
<br /> Nil
<br /> <font color="#ff9900">def</font> head = sys.error("empty list")
<br /> <font color="#ff9900">def</font> tail = sys.error("empty list")
<br />}
<br /></blockquote></code></pre>
<br />Now this one is a little more tricky, we might know that a natural number <code>A</code> is even but what the typesystem does not know if <code>A#Pred#Pred</code> is also even when we call <code>getPairs</code> recursively. We now need to to create a witness that <code>A#Pred#Pred</code> is even when <code>A</code> is even. We can do this with another method that generates a witness when you hand it the witness for <code>A</code>'s evenness, let's call that method <code>predPredEven</code>.
<br /><pre><code><blockquote>
<br /><font color="#ff9900">sealed</font> <font color="#ff9900">case</font> <font color="#ff9900">class</font> NCons[A <: Nat, B](h: B, t: NList[A, B])
<br /><font color="#ff9900">extends</font> NList[S[A], B] {
<br /> <font color="#ff9900">private</font> <font color="#ff9900">def</font> predPredEven[A](e: Even[Length]): Even[Length#Pred#Pred] =
<br /> <font color="#ff9900">new</font> Even[Length#Pred#Pred]{}
<br /> <font color="#ff9900">def</font> getPairs(<font color="#ff9900">implicit</font> e: Even[Length]): List[(B, B)] =
<br /> (head, tail.head) :: tail.tail.getPairs(predPredEven(e))
<br /> <font color="#ff9900">def</font> head: B = h
<br /> <font color="#ff9900">def</font> tail: NList[Length#Pred, B] = t
<br />}
<br /></blockquote></code></pre>
<br />That's all. How does this look when we put it into action?
<br /><pre><code><blockquote>
<br />scala> val lo = NCons(1, NNil)
<br />lo: nlist.NCons[nlist.Z,Int] = NCons(1,NNil)
<br />scala> le.getPairs
<br />res0: List[(Int, Int)] = List((1,2))
<br />scala> NNil.getPairs
<br />res1: List[(Nothing, Nothing)] = List()
<br />scala> lo.getPairs
<br /><console>:12: error: could not find implicit value for parameter e: nlist.Even[lo.Length]
<br /> lo.getPairs
<br /> ^
<br /></console></blockquote></code></pre>
<br />Very nice! <code>getPairs</code> only works on lists with an even length, otherwise we get a compile error. Once again: If you want to play with this code check out this <a href="https://gist.github.com/1168922">gist</a>.
<br />
<br />In future blogposts I'd like to show you how a language that bears these techniques in mind handles these problems.raichoohttp://www.blogger.com/profile/05235774661802634100noreply@blogger.com0tag:blogger.com,1999:blog-8144285405079538181.post-58504877879976715442011-08-22T11:43:00.001-07:002011-08-22T14:19:41.747-07:00A Taste of Dependent Types in ScalaOne thing starts to cross my way very frequently is dependent typing. While I'm not an expert on this topic I found some very interesting things in various papers that I would like to be able to do in Scala. Dependent types help to verify that your program does what it's supposed to do by proving theorems.
<br />Since Scala is not dependently typed we need to become a little tricky, but let's give it a try.
<br />
<br />Think about the type signature of the following method called <code>zap</code> (which stands for zip-apply):
<br /><pre><code>
<br /><blockquote>def zap[A, B](l: List[A], fs: List[A => B]): List[B]</blockquote>
<br /></code></pre>
<br />By looking at the signature it should become obvious what the method does. You have a list <code>l</code> that provides elements of type <code>A</code> and a list <code>fs</code> that provides a function from <code>A</code> to <code>B</code> for each element in <code>l</code>. Lets look at the implementation:
<br /><pre><code>
<br /><blockquote>def zap[A, B](l: List[A], fs: List[A => B]): List[B] =
<br /> (l, fs) match {
<br /> case (_, Nil) | (Nil, _) => Nil
<br /> case (a :: as, b :: bs) => b(a) :: zap(as, bs)
<br /> }</blockquote>
<br /></code></pre>
<br />That's a pretty straight forward example, but there is a problem with this code. What if we do provide lists with different length? In one case we would not execute some functions in the other case we would lose data. So what can we do? We could throw an exception but that's already to late, our program is already in a state where things don't make sense anymore, we have to avoid this situation at all and the best thing to achieve this is that such code does not compile at all.
<br />
<br />In a dependently typed language we could create a list that encodes it's length within the type of the list itself and write <code>zap</code> in a way so that it would only accept lists of the same length. But since we are not in a dependently typed language we cannot do that, this concludes this blogpost, see you in another episode… ok, just kidding. We actually CAN do that in Scala. Here is how:
<br />
<br />The first thing we need is: natural numbers in the type system to encode the length of our list. That is easy:
<br /><pre></code>
<br /><blockquote>sealed trait Nat
<br />sealed trait Z extends Nat
<br />sealed trait S[A <: Nat] extends Nat</blockquote>
<br /></code></pre>
<br /><code>Z</code> is our zero here and <code>S[A <: Nat]</code> is the successor of the natural number <code>A</code>, so we can create the natural numbers recursively: <code>Z</code> == 0, <code>S[Z]</code> == 1, <code>S[S[Z]]</code> == 2 etc.
<br />
<br />Now let's start with the fun part, the list itself.
<br />
<br />The first thing we need is the <code>trait</code> for our <code>NList</code>.
<br /><pre><code>
<br /><blockquote>trait NList[A <: Nat, +B] {
<br /> type Length = A
<br /> def zap[C](l: NList[Length, B => C]): NList[Length, C]
<br />}</blockquote>
<br /></code></pre>
<br />We can now see that the type of <code>zap</code> enforces that the both lists need to have the same length <code>A</code>. We can now create our first case where we are zapping two lists of length 0 (or <code>Z</code>). The implementation is rather trivial.
<br /><pre><code>
<br /><blockquote>case object NNil extends NList[Z, Nothing] {
<br /> def zap[A](l: NList[Length, Nothing => A]): NNil.type =
<br /> NNil
<br />}</blockquote>
<br /></code></pre>
<br />The next case is not as simple (if someone has a better idea of how to implement this, I would love to see it. Please drop a comment).
<br /><pre><code>
<br /><blockquote>case class NCons[A <: Nat, B](head: B, tail: NList[A, B])
<br />extends NList[S[A], B] {
<br /> def zap[C](l: NList[Length, B => C]): NList[Length, C] =
<br /> l match {
<br /> case NCons(f, fs) =>
<br /> NCons(f(head), tail zap fs)
<br /> }
<br />}</blockquote>
<br /></code></pre>
<br />We can see that our <code>NCons</code> is actually a <code>NList</code> that is one element longer
<br />than it's tail which has length <code>A</code>, the pattern match inside our zap method only has to handle the cons case since the type signature does not allow anything else.
<br />
<br />Now let's put that little bugger to the test:
<br />
<br />First lets define some <code>NList</code>s
<br /><pre><code>
<br /><blockquote>scala> val l1 = NCons(1, NCons(2, NCons(3, NNil)))
<br />scala> val l2 = NCons(1, NCons(2, NNil))
<br />scala> val f = (_: Int) + 1
<br />scala> val f1 = NCons(f, NCons(f, NCons(f, NNil)))
<br />scala> val f2 = NCons(f, NCons(f, NNil))</blockquote>
<br /></code></pre>
<br />Zapping lists with the same length:
<br /><pre><code>
<br /><blockquote>scala> l1 zap f1
<br />res1: nlist.NList[l1.Length,Int] = NCons(2,NCons(3,NCons(4,NNil)))
<br />
<br />scala> l2 zap f2
<br />res2: nlist.NList[l2.Length,Int] = NCons(2,NCons(3,NNil))</blockquote>
<br /></code></pre>
<br />This works just fine, now lets see what happens if we <code>zap</code> two lists with a different length:
<br /><pre><code>
<br /><blockquote>scala> l1 zap f2
<br /><console>:14: error: type mismatch;
<br /> found : nlist.NCons[nlist.S[nlist.Z],Int => Int]
<br /> required: nlist.NList[l1.Length,Int => ?]
<br /> l1 zap f2</blockquote>
<br /></code></pre>
<br />Exactly what we wanted! This code does not even compile since it doesn't make any sense.
<br />This is a very basic example of what we can do with the Scala type system. Stay tuned for more!
<br />
<br />If you would like to play around with the code check out my <a href="https://gist.github.com/1163522">gist</a>raichoohttp://www.blogger.com/profile/05235774661802634100noreply@blogger.com4tag:blogger.com,1999:blog-8144285405079538181.post-39649854497966483202011-07-10T04:08:00.000-07:002013-03-27T06:36:06.793-07:00From Functions to Monads in Scala"Monad" that's a word you hear quite often these days. There is a lot of unjustified FUD whenever this word pops up. People seem to be downright scared about it. You can tell by the amount of rhetorical trick words people use to scare others away from trying to understand monads at all. "Academic", "no use in real world programming" etc etc. I find it quite frustrating to hear something like that even within the Scala community from time to time (even though this is getting rarer and rarer), since these are the "arguments" people bring up when they try to scare others away from Scala.
<br />
<br />
First of all, I'm not a category theorist. These things just fascinate me, and I enjoy reading about this in my free time. I'm your ordinary "Joe, the programmer" working at a small software company.
<br />
<br />
Still, I find these things useful in my day job. Why? Because as a programmer I'm building mathematical machines (namely software) all day long and these concepts help me to order my thoughts and make at easier to reason about my software and design stuff.
<br />
<br />
In this blogpost I want to show how to derive Monads from what you already know and give names to things you maybe never even thought about.
<br />
<br />
<b>Categories</b>
<br />
<br />
Since monads come from Category Theory we first have to define what a <b>category</b> is.
<br />
<br />
A category <b><i>C</i></b> basically consists of 2 sets <i>ob</i>(<i><b>C</b></i>) and <i>hom</i>(<i><b>C</b></i>) where we call <i>ob</i>(<i><b>C</b></i>) the <b>objects</b> of <b><i>C</i></b> and <i>hom</i>(<i><b>C</b></i>) the <b>morphisms</b> of <b><i>C</i></b>. Morphisms are maps that go between objects.
<br />
<br />
Never saw a <b>Category</b> in your every day programming? Sure? There is a <b>Category</b> called <b><i>Hask</i></b>, its objects are the Haskell types and its morphisms are Haskell functions. So you can think about that in a Scala context:
<br />
<br />
Let <code>f</code> be a function of type <code>Int => String</code>. <code>Int</code> and <code>String</code> are both elements of <i>ob</i>(<i><b>C</b></i>) and <code>f</code> is an element of <i>hom</i>(<i><b>C</b></i>).
<br />
<br />
There's more to a <b>Category</b>, we need to be able to compose morphisms and there has to be a special element called <b>identity</b>. Lets looks at composition first.
<br />
<br />
Let f and g be functions:
<br />
<pre><code>
f: A => B
g: B => C
</code></pre>
<br />
We can compose those 2 functions in Scala by using the <code>compose</code> method to get a new function.
<br />
<pre><code>
g compose f // yields a function of type A => C
</code></pre>
<br />
OK, that's half the rent. Now we just need the special element called <b>identity</b> which basically is a function that does nothing. It just takes a value and returns it unmodified. So when we <code>compose</code> a function <code>f</code> with <code>identity</code> we get back a function that is equivalent to <code>f</code> and it should not matter if we compose <code>f</code> with <code>identity</code> or <code>identity</code> with <code>f</code>.
<br />
<br />
In short: The following 3 functions are equivalent (which means: when fed with the same input values they will yield the exact same result)
<br />
<pre><code>
f // A => B
f compose id // A => B
id compose f // A => B
</code></pre>
<br />
Now we know that a <b>Category</b> is (well, at least we know enough to start, a real category theorist can take you on a breathtaking journey from here :)). Let's move on!
<br />
<br />
<b>Enter Higher-Kinded-Types</b>
<br />
<br />
Next "scary word", but again: You use them all the time. First we need to know what a <b>kind</b> is. We know what types and values are. You can think of them as levels. A value like <code>1</code> and <code>x => x</code> (that's a function value, yes those are values too!) live a the value level while types like <code>Int</code> and <code>Int => Int</code> live at the type level. We group values into types. <code>true</code> and <code>false</code> are both values of type <code>Boolean</code> (think of types as sets of values).
<br />
<br />
OK, if we group values into types, can we group types? Yes, we can! We can group types into… *drumroll* KINDS! Now we have a third level and our world looks something like this:
<br />
<pre><code>
kinds
---------
types
---------
values
</code></pre>
<br />
In most languages we only deal with one kind called <code>*</code> (pronounced <i>type</i>) that groups all types, but there are languages that allow infinite levels (I might cover one of them in future blog posts).
<br />
<br />
We now have a basic idea of what kinds are, so what are <b>higher kinded types</b>? Like High-Order-Functions (functions that take functions as arguments and yield functions e.g. compose)
<br />
higher kinded types are <b>type constructors</b> that take type constructors as arguments and yield types (or maybe even <b>type constructors</b>).
<br />
<br />
"Wait a minute… are you talking about generics?"
<br />
<br />
Think about <code>List</code>. It's not a type by itself, you need to feed it a type as an argument to get a type. This is called a <b>Type Constructor</b>.<code>List</code> takes one type and returns a type, hence <code>List</code> has the kind <code>* -> *</code> (this notation is borrowed from Haskell). The Scala notation for a <b>type constructor</b> like <code>List</code> is <code>List[_]</code>.
<br />
<br />
So a <b>higher kinded type</b> looks something like this: <code>trait Functor[F[_]]</code> where F could be a <code>List</code>, <code>Option</code> or any other <b>type constructor</b> that takes one argument.<br />
<br />
<b>Functors</b>
<br />
<br />
Now that we have <b>higher kinded types</b>, let's take a look at our functions <code>f</code> and <code>g</code> from the beginning and lets add a <b>type constructor</b> <code>F[_]</code> to the mix (this is Scala notation and means: takes one type and yields a type). We can now produce a whole new set of types with this higher kind (e.g. <code>F[Int]</code>, <code>F[String]</code> etc.). We could now create functions that work with these types… hey I know this. This sounds like… a <b>Category</b>! Yes, it is! It's actually a <b>Subcategory</b> of our <b>Hask</b> <b>Category</b> we introduced at the beginning. Let's call this new <b>Category</b> <b><i>D</i></b> (so we don't confuse it with the <b>type constructor</b> F). So elements of <i>ob</i>(<i><b>D</b></i>) would be something like F[A] and for <i>hom</i>(<i><b>D</b></i>) it would be something like F[A] => F[B].
<br />
<br />
Now wouldn't it be cool if there was a morphism between those two categories, one that preservers composition and the identity rule? Something that could map a function of type <code>A => B</code> to a function of type <code>F[A] => F[B]</code>? That's what's we call a <b>Functor</b>, it's a morphism between categories.
<br />
<br />
"Why is this useful?" you might ask. Just think about the kind of code reuse you could achieve. Let's look at <code>Option</code> as a concrete example. It's a <b>type constructor</b>. So how do we map a function of type <code>Int => Int</code> to a function of type <code>Option[Int] => Option[Int]</code>? Can't you tell by now? The answer is the <code>map</code> method of Option ;).
<br />
<br />
Let's check it out:
<br />
<pre><code>
scala> val f = (_: Int) + 1
f: (Int) => Int = <function1>
scala> Some(1) map f
res0: Option[Int] = Some(2)
</code></pre>
<br />
We could now reuse our function <code>f</code> with <code>Option</code>, there was no need to write a special version of <code>f</code> that works with <code>Option</code>.
<br />
<br />
The second ingredient we need to make our <b>Functor</b> complete is a morphism that maps a value of type <code>A</code> to a value of type <code>F[A]</code>. In the case of <code>Option</code> this is just the factory function:
<br />
<pre><code>
scala> Some(_: Int)
res0: (Int) => Some[Int] = <function1>
scala> Option(_: Int)
res1: (Int) => Option[Int] = <function1>
scala> Option(1)
res2: Option[Int] = Some(1)
scala> Some(1)
res3: Some[Int] = Some(1)
</function1></function1></code></pre>
<br />
<br />
<b>Endofunctors</b>
<br />
<br />
Now, let's assume that we want something like this:
<br />
<pre><code>
scala> Some(1) map {
| case x if x % 2 == 0 => Some("YES!")
| case _ => None
| }
res1: Option[Option[java.lang.String]] = Some(None)
</code></pre>
<br />
We want to use a function of type <code>Int => Option[String]</code> with <code>Option</code>'s <code>map</code> method. But what's that? We get an <code>Option[Option[String]]</code>. That's stupid, now I have to unpack one <code>Option</code> to get the result I actually wanted.
<br />
<br />
What happened here? Remember how we mapped a function of type <code>A => B</code> to a function of type <code>F[A] => F[B]</code> in the previous section about functors? What we did now is: we mapped a function of type <code>Int => Option[String]</code> to a function of <code>Option[Int] => Option[Option[String]]</code>. Yikes, we went a little bit over the top here, huh? We kind of like mapped something into an <code>Option</code> and into an <code>Option</code> this is how we ended up with an <code>Option[Option[String]]</code>. You can think of this as a result of a composition of 2 <code>Option</code> <b>Functors</b>.
<br />
<br />
This is a special kind of <b>Functor</b> that maps a category into itself and is called an <b>Endofunctor</b>
<br />
<br />
<b>Natural Transformations</b>
<br />
<br />
Now that we have morphisms between objects of a <b>Category</b> which are Scala functions and <b>Functors</b> which are basically morphisms between categories it's time to introduce morphisms between <b>Functors</b>.
<br />
<br />
Why do we need this? Well in the last example we ended up with an <b>Endofunctor</b> (we mapped a <b>Category</b> into itself). We need to get rid of one of the <code>Option</code>s. We do this with a morphism that maps the composition of 2 <b>Functors</b> <i><b>F</b></i> (<i><b>F</b></i> composed with <i><b>F</b></i>) to the <b>Functor</b> <i><b>F</b></i>.
<br />
<br />
Lets do a concrete example that involves <code>List</code>
<br />
<pre><code>
scala> List(1,2,3) map { x => List(x + 1) }
res0: List[List[Int]] = List(List(2), List(3), List(4))
</code></pre>
<br />
It happened again, but this time we ended up with a <code>List[List[Int]]</code>! We now need a <b>Natural Transformation</b> to join those lists together, this <b>Natural Transformation</b> is called <code>flatten</code> in Scala.
<br />
<pre><code>
scala> List(1,2,3) map { x => List(x + 1) } flatten
res1: List[Int] = List(2, 3, 4)
</code></pre>
<br />
<code>List</code> comes with a method that does both in one step, it's called <code>flatMap</code>.
<br />
<pre><code>
scala> List(1,2,3) flatMap { x => List(x + 1) }
res2: List[Int] = List(2, 3, 4)
</code></pre>
<br />
This enables us to chain functions together in a very convenient way.
<br />
<pre><code>
scala> Some(1) flatMap { x => Some(2) flatMap { y => Some(x + y) } }
res3: Option[Int] = Some(3)
</code></pre>
<br />
or a little more concise
<br />
<pre><code>
scala> Some(1) flatMap { x => Some(2) map { y => x + y } }
res4: Option[Int] = Some(3)
</code></pre>
<br />
<br />
<b>Monads</b>
<br />
<br />
This is actually what makes up a <b>Monad</b>. It's an Endofunctor with two <b>Natural Transformations</b> called <i>unit</i> and <i>join</i> (which is called <code>flatten</code> in Scala). They are such a fundamental concept that Scala features a syntactic sugar for them, the <code>for</code>-comprehension. Do NOT confuse this with a mere <code>for</code>-loop, this is a different animal. The last example above can be written in the following way:
<br />
<pre><code>
scala> for {
| x <- br="" some=""> | y <- br="" some=""> | } yield x + y
res5: Option[Int] = Some(3)
//translates to
scala> Some(1) flatMap { x => Some(2) map { y => x + y } }
res6: Option[Int] = Some(3)
<!-----><!-----><!-----><!-----><!-----><!-----><!-----><!-----></-></-></code></pre>
<br />
<br />
<b>Conclusion</b>
<br />
<br />
This is an introduction on how to think about <b>monads</b> and how to derive them from simple building blocks. They are a very powerful abstraction that pops up all the time. You use them all the time without knowing. Since programming is all about abstraction it's useful to recognize those underlying patterns. Don't let others fool you into believing that this is just some bizarre functional stuff that has no use in the real world. This is just the tip of the iceberg, an amazing journey lies ahead. Let's learn!raichoohttp://www.blogger.com/profile/05235774661802634100noreply@blogger.com7tag:blogger.com,1999:blog-8144285405079538181.post-25433220743432928972011-07-09T05:45:00.000-07:002011-07-09T15:01:08.152-07:00DTrace and it's impact on JVM performanceSo, I did this <a href="http://raichoo.blogspot.com/2011/07/dtrace-and-scala.html">blogpost</a> that gave a very shallow introduction to what DTrace can do with the JVM and I got an amazing feedback after that. Actually I'm quite flattered that it had such an impact. <br /><br />One message I received pointed out that DTrace probes are having a significant impact on the JVM's performance, he (the author) would never recommend using the DTrace JVM integration, and then he pointed me… well, a product by his own company (which shall remain nameless, since I don't want to advertise commercial products on this blog). To be fair: I admit that I would do the same. When you put a lot of effort into a piece of software you do it for reasons you believe in.<br /><br />However, he gave me a link to some benchmarks that showed some impressive results and diagrams about how much the performance of the JVM suffers when DTrace probes are enabled. The bar diagrams were scary, DTrace looked pretty bad compared to the "rival" technology (you can't really call it a rival since DTrace has a completely different objective). But something was fishy about this, and that was: the axes of the diagrams were not labeled. They did show a small blue bar and a big green bar and nothing else. The code for the test case was provided as a gif (no copy and paste to reproduce the results nice and easy). Numbers were not put into any perspective. And blog comments were disabled.<br /><br />None the less, this was interesting enough to start a little bit of research on the topic.<br /><br />The benchmarks seemed to focus on how much enabled probes did slow down method calls. I personally don't like benchmarks that use extremely unrealistic cases as a foundation (look how fast I can increment them integers in a tight loop suckaz! Mah language iz teh fast!) but this time I will just go with the flow because this is pretty much what they did in that benchmark (don't try this at home kids, use realistic conditions to benchmark your stuff). I'm not using the same test code here but the idea seems to be pretty much the same.<br /><br />The system I'm running this on is a Thinkpad X201 with a core i7 and 8 gigs of RAM (yeah I know, I'm just compensating, get over it ;)). The operating system is OpenIndiana Build 151-beta with DTrace 1.7. Java is at 1.6.0_25.<br /><br />The stupid test case I will be using is this Java program:<br /><pre><code><br />class Test {<br /><br /> public int callTest(int i) {<br /> if (i != 0)<br /> callTest(i - 1);<br /><br /> return i;<br /> }<br /><br /> public static void main(String[] args) {<br /> Test t = new Test();<br /><br /> long starttime = System.currentTimeMillis();<br /> for (int i = 0; i < 1000000; i++)<br /> callTest(100)<br /> long endtime = System.currentTimeMillis();<br /><br /> System.out.println(endtime - starttime);<br /> }<br />}<br /></code></pre><br />Once again, this is not a realistic example. I will just use it to demonstrate that there really is an impact.<br /><pre><code><br />> java Test<br />118<br />> java -XX:+ExtendedDTraceProbes Test<br />4106<br /></pre></code><br />Wow, this really seems to hurt… the programm is about 35 times slower with DTrace probes enabled.<br /><br />To put this into perspective I will commit a capital crime in programming. I will compare this stupid program in language A to the same stupid program written in language B. Let language B be Python in this case. To be crystal clear about this: this is NOT a comparison of Python and Java performance. I just need some landmarks to make all those numbers meaningful (at least to some extent since this is a very badly chosen scenario to begin with).<br /><br />Here is our Python test case.<br /><pre><code><br />import time <br /><br />def callTest(i):<br /> if not i == 0:<br /> callTest(i - 1)<br /><br /> return i<br /><br />r = range(0,1000000)<br /><br />starttime = time.time()<br /><br />for i in r:<br /> callTest(100)<br /><br />endtime = time.time()<br />print (endtime - starttime)<br /></code></pre><br />And the result:<br /><pre><code><br />> python test.py<br />21.9892270565<br /></code></pre><br /><br />OK, our software runs slower with probes enabled, but we are still faster than Python and Python's performance is acceptable for a lot of use cases. We now have a slower JVM that can be instrumented. So I'd say: No real harm done.<br /><br />Now let's use those probes and aggregate some real data. For this test I will use a slightly modified version of <code>j_methodcalls.d</code>, a script by <a href="http://twitter.com/brendangregg">Brendan Gregg</a> that is shipped with the <a href="http://hub.opensolaris.org/bin/view/Community+Group+dtrace/dtracetoolkit">DTrace Toolkit</a>. <font color="red">The script is licensed under <a href="http://opensource.org/licenses/CDDL-1.0">CDDL</a></font> but I did remove the license header here to make it more concise and blog-friendly.<br /><pre><code><br />#!/usr/sbin/dtrace -Zs <br /><br />hotspot$target:::method-entry<br />{<br /> this->class = (char *)copyin(arg1, arg2 + 1); <br /> this->class[arg2] = '\0';<br /> this->method = (char *)copyin(arg3, arg4 + 1); <br /> this->method[arg4] = '\0';<br /> this->name = strjoin(strjoin(stringof(this->class), "."),<br /> stringof(this->method));<br /> @calls[pid, this->name] = count();<br />}<br /></code></pre><br />Let's run it!<br /><pre><code><br />> pfexec ./j_methodcalls.d -c "java -XX:+ExtendedDTraceProbes Test"<br />[…snip…]<br />249126<br /></code></pre><br />OK, this is A LOT slower, even slower than Python. 4 Minutes!<br /><br />We are now aggregating data and that means we are copying data from userspace into kernelspace from where it can be fetched by DTrace consumers (in our case the <code>dtrace</code> command line tool). What data did we get in this amount of time? Actually: A LOT. It flooded my terminal and I had to pipe the result into <code>less</code> to be able to read all of it. DTrace recorded every method call that happened in the JVM while the program was running. It counted the calls per method, and the class the method belongs to. Keep in mind that we did not need to modify our code to get these results. We don't even need to restart a running JVM to enable the probes we can activate them by using the <code>jinfo</code> command. And we could have used DTrace to gather system wide data in the same script (something I might demonstrate sometime on this blog)<br /><br />Now lets use the most naive debugging technique on earth. We will print out "CALLED!" every time our <code>callTest</code> method gets called (if you ever did this before you know how disastrous the result well be). This gives us pretty much no information. We just know that a particular method has been called and we need to modify our code, recompile and load it into running JVM. <br /><pre><code><br />> time java Test<br />[…snip…]<br />CALLED!<br />5958514<br /><br />real 1h39m18.15s<br />user 3m53.29s<br />sys 7m55.68s<br /></code></pre><br />As we expected, the result is a disaster. Calling print in a tight loop is an extremely stupid thing to do. We could have used a counter that get incremented with every method call, proxy objects, interceptors etc. (all of them would have been significantly faster).<br /><br />To do something similar like the print example with DTrace I just a another clause to the script:<br /><pre><code><br />tick-1s {<br /> printa(@calls);<br /> trunc(@calls);<br />}<br /></code></pre><br />This addition prints out what happened in 1 second intervals<br /><pre><code><br /> 1 75779 :tick-1s <br /> 4028 Test.callTest 400379<br /><br /> 1 75779 :tick-1s <br /> 4028 Test.callTest 404720<br /><br /> 1 75779 :tick-1s <br /> 4028 Test.callTest 402135<br /><br /> 1 75779 :tick-1s<br /> 4028 Test.callTest 398934<br /><br />253064<br />dtrace: pid 4028 has exited<br /><br /><br />real 4m14.23s<br />user 4m13.89s<br />sys 0m0.46s<br /></code></pre><br />The performance impact stays pretty much the same with DTrace, we are done in 4 Minutes while we are presented with a readable stream of information.<br /><br />There are a lot of ways to generate similar data, but most of them require code changes, are not able to do system wide tracing, are limited to one process and/or just one specific runtime.<br /><br /><b>Conclusion</b><br /><br />Tracing the JVM costs (this shows especially in this pathological use case), but DTrace provides us with a very broad spectrum of probes. The JVM ones are just one source of data. We can actually instrument every part of the system with our DTrace script. Maybe a problem is not even related to our program at all, maybe it's NFS misbehaving, something is wrong with the database or there is some heavy IO going on. With DTrace the whole system becomes transparent. This changes the whole "blame game" and that's the whole point of DTrace. Looking at the system as a whole.<br /><br />The bottom line is: trace the JVM only if you need to and be aware of the performance impact. This tool is for hunting down problems that are very hard or even impossible to analyze with traditional tools. I did use it to trace obscure memory leaks and dead-locks (both in non-Java contexts) and I was able to exactly pinpoint the culprit.<br /><br />Don't use DTrace when there is a tool that does a better job for this specific task. Use it wisely. Anyway, it's a great utility to have in your toolbox.<br /><br />Last but not least: use realistic use cases for benchmarking, label your diagram axes, and compare tools that have the same objective.raichoohttp://www.blogger.com/profile/05235774661802634100noreply@blogger.com0tag:blogger.com,1999:blog-8144285405079538181.post-9800409173909593662011-07-06T11:48:00.000-07:002011-07-06T14:15:07.284-07:00DTrace and Scala<a href="http://en.wikipedia.org/wiki/DTrace">DTrace</a> is one of my favorite technologies ever, it absolutely redefined my view on software and how it can be debugged. In a lot of situations you are basically forced to debug your software by vomiting print-statements just all over the place. To make things worse you have to take them out when you are actually shipping your software, leaving you blind to errors to come. In other cases you probably are missing some print-statements to trace down a very nasty bug, or the bug is hidden in some 3rd-party lib that would take hours to recompile with your new print statement (don't start thinking about libs that you don't have the code of…). In most cases this can become a very unpleasant situation (to put it mildly). DTrace takes a lot of the hassle away by providing you with a mechanism that can modify your program while it's running without stopping it.<br />Pretty amazing, huh? Wait, it gets better. You can even trace into the runtime of some high level languages (if they provide the probes). This is also true for the JVM, and that means we can instrument a running Scala program.<br /><br />In this post I will walk you through a very basic script that shows what methods from <code>Predef</code> get called by your program. DTrace is a tool that reaches deep down into the lower levels of your machine. Sounds scary? Nah not really, one of the design goals of DTrace is safety. Your scripts run in a managed environment that keeps it from doing harmful things.<br /><br />OK, enough sweet-talk. Time to get our hands dirty by writing a very simple Scala program:<br /><pre><code><br />import scala.annotation.tailrec<br /><br />object Main {<br /> @tailrec<br /> def sayHallo() {<br /> println("HALLO!")<br /> Thread.sleep(1000)<br /> sayHallo()<br /> }<br /> <br /> def main(args: Array[String]) {<br /> sayHallo()<br /> }<br />}<br /></code></pre><br />This just prints out "HALLO!" in 1 second intervals (not exactly rocket science, but I put a little sugar on top of it by replacing the while loop with a tail recursive function for fun and profit).<br /><br />What's that? When running my program DTrace is not showing me ANY probes!!?!?! FFFFUUUUUUUU! That's because we have to enable them first, we can instruct a running JVM to do this by using <code>jinfo</code>. Since I only got one JVM running on this box I will fetch the PID with <code>pgrep</code>.<br /><pre><code><br />jinfo -flag +ExtendedDTraceProbes $(pgrep java)<br /></code></pre><br />The JVM probes are now armed and "dangerous" (just kiddin') and you will have access to the <code>hotspot</code> provider.<br /><br />Now lets write the DTrace script. Keep in mind: this script is running in kernel space, so we have to copy in some information from userspace, we do this by using <code>copyin</code> and we have to <code>NULL</code>-terminate the strings ourselves. Yep, this is what it feels like to program low-level stuff, it's not as pretty as FP but aaaaaaaaaanyway, here is the little bugger.<br /><pre><code><br />#!/usr/sbin/dtrace -s <br /><br />#pragma D option quiet<br /><br />hotspot$$target:::method-entry<br />{<br /> this->class = (char *) copyin(arg1, arg2 + 1); <br /> this->class[arg2] = '\0';<br /> self->tracefunc = stringof(this->class);<br />}<br /><br />hotspot$$target:::method-entry<br />/self->tracefunc == "scala/Predef$"/<br />{<br /> this->method = (char *) copyin(arg3, arg4 + 1); <br /> this->method[arg4] = '\0';<br /> printf("%s %Y\n", stringof(this->method), walltimestamp);<br /> self->tracefunc = 0;<br />}<br /><br />hotspot$$target:::method-entry<br />/self->tracefunc/<br />{<br /> self->tracefunc = 0;<br />}<br /></code></pre><br />This thing will fire whenever a function from <code>Predef</code> is called and will give us the function name (in our test case this is just <code>println</code>) and the time when this function was being called. I run this on <a href="http://www.openindiana.org">OpenIndiana</a> build151-beta by issuing <code>pfexec dtrace ./tracescript.d -p $(pgrep java)</code> after I enabled the <code>hotspot</code> provider on the JVM. (<code>pfexec</code> is kind of like <code>sudo</code>, just use whatever gives you the permission to run <code>dtrace</code> on your box)<br />The output will look like this:<br /><pre><code><br />println 2011 Jul 6 21:27:34<br />println 2011 Jul 6 21:27:35<br />println 2011 Jul 6 21:27:36<br />println 2011 Jul 6 21:27:37<br />println 2011 Jul 6 21:27:38<br />println 2011 Jul 6 21:27:39<br />println 2011 Jul 6 21:27:40<br />println 2011 Jul 6 21:27:41<br />println 2011 Jul 6 21:27:42<br />println 2011 Jul 6 21:27:43<br />println 2011 Jul 6 21:27:44<br />println 2011 Jul 6 21:27:45<br />println 2011 Jul 6 21:27:46<br />println 2011 Jul 6 21:27:47<br />println 2011 Jul 6 21:27:48<br />println 2011 Jul 6 21:27:49<br />println 2011 Jul 6 21:27:50<br />println 2011 Jul 6 21:27:51<br />println 2011 Jul 6 21:27:52<br />println 2011 Jul 6 21:27:53<br />println 2011 Jul 6 21:27:54<br />println 2011 Jul 6 21:27:55<br /></code></pre><br /><br />WTF IS THIS I DON'T EVEN!?!?!? TL;DR<br /><br />OK, this is not even the tip of the iceberg but I think I will wrap it up because there is a lot of ground to cover when it comes to DTrace. If you are hungry for more you should check out the "<a href="http://www.youtube.com/watch?v=6chLw2aodYQ">DTrace Review</a>" by <a href="http://twitter.com/bcantrill">@bcantrill</a>, this stuff will blow your mind (seriously, WATCH IT!) or buy the <a href="http://www.amazon.com/DTrace-Dynamic-Tracing-Solaris-FreeBSD/dp/0132091518/ref=sr_1_1?ie=UTF8&qid=1309980847&sr=8-1">book</a> by <a href="http://twitter.com/brendangregg">@brendangregg</a>. I will make sure to dig deeper on the topic, so stay tuned. Tell me what you think, good tool or best tool? :Praichoohttp://www.blogger.com/profile/05235774661802634100noreply@blogger.com0tag:blogger.com,1999:blog-8144285405079538181.post-165242063487152262011-07-06T10:56:00.000-07:002011-07-06T15:01:53.638-07:00English, please!It took me quite some time to make up my mind about this… should I switch the language of this blog to English or should leave it just the way it is. I think it's worth to give this a try, since twitter brought me towards a mostly non-German audience which I also would like to address. This is also a great opportunity to polish my language skills a little since they got kind of neglected in the last few years (so bear with me ;)<br /><br />So, to all my new readers, here is a little overview on what this blog is about. I work as a developer at a German software company so quite a lot of stuff you will find here will focus on programming and debugging. In my free time I like to play around with different operating systems (mainly <a href="http://www.illumos.org">Illumos</a>, <a href="http://www.freebsd.org">FreeBSD</a> and <a href="http://www.dragonflybsd.org">DragonFlyBSD</a>) so this place will be stuffed with information about OS specific wizardry :3<br /><br />OK, folks! Let's give this a shot!raichoohttp://www.blogger.com/profile/05235774661802634100noreply@blogger.com0tag:blogger.com,1999:blog-8144285405079538181.post-38724817086687229282011-02-23T05:30:00.001-08:002011-02-23T13:51:27.318-08:00Dynamic-Dispatch in ScalaIch bin ja hin und wieder schon mal richtig neidisch auf <a href="http://clojure.org/multimethods">Clojures Multimethods</a>, möchte aber nicht wirklich meine statisch typisierte Welt verlassen (auch wenn Clojure vermutlich die einzige Sprache wäre die ich von allen dynamischen Sprachen wählen würde).<br /><br />Lange Rede, kurzer Unsinn: Ich will Multimethods in Scala! Auf den ersten Blick klingt das als würde man sich eine Sprache zu etwas hinbiegen wollen was sie gar nicht ist, aber in Scala geht das ganze erschreckend schmerzlos.<br /><br />Zum dispatchen verwende ich einfach ein paar partielle Funktionen die man mit <code>orElse</code> beliebig aneinanderketten kann. Der Vorteil davon ist das ich keinen Code aufmachen muss wenn ich einen weiteren Fall hinzufügen will sondern durch Komposition zum Ziel komme.<br /><pre><code><br />trait Dynamic<br /><br />class A extends Dynamic<br />class B extends Dynamic<br /><br />object Dynamic {<br /> // 2 dynamische argumente<br /> type Dyn2 = (Dynamic, Dynamic)<br /><br /> // infix notation fuer PartialFunction<br /> type ~>[A, B] = PartialFunction[A, B]<br /> <br /> val f: Dyn2 ~> String = {<br /> case (a: A, b: A) => "A A"<br /> }<br /><br /> val g: Dyn2 ~> String = {<br /> case (a: A, b: B) => "A B"<br /> }<br /><br /> // d ist die dispatchfunktion<br /> def dispatch[A, B](d: A ~> B, a: A): Option[B] =<br /> if (d.isDefinedAt(a)) Some(d(a))<br /> else None<br />}<br /></pre></code><br />In Aktion sieht das Ganze so aus:<br /><pre><code><br /><br />scala> :l ./dynamic.scala <br />Loading ./dynamic.scala...<br />defined trait Dynamic<br />defined class A<br />defined class B<br />defined module Dynamic<br /><br />scala> import Dynamic._<br />import Dynamic._<br /><br />scala> dispatch(f, (new A, new A))<br />res0: Option[String] = Some(A A)<br /><br />scala> dispatch(f, (new A, new B))<br />res1: Option[String] = None<br /><br />scala> dispatch(f orElse g, (new A, new B))<br />res2: Option[String] = Some(A B)<br /></pre></code><br />Wie man schön sehen kann werden auch die nicht abgedeckten Fälle behandelt indem wir einfach eine <code>Option </code> verwenden, dadurch könnten wir unseren Dispatch auch in einer <code>for</code>-Comprehension verwenden (Monaden für den Gewinn!)<br /><br />Viel Spass beim ausprobieren ;)<br /><br />Hier <a href="http://nice.sourceforge.net/visitor.html">ein kleiner Nachtra</a>g wozu Multimethods gut sind. Für alle die Das Visitorpattern schon immer gehasst haben ;)raichoohttp://www.blogger.com/profile/05235774661802634100noreply@blogger.com0tag:blogger.com,1999:blog-8144285405079538181.post-79775713512722806692011-02-21T13:54:00.000-08:002011-02-21T14:14:04.542-08:00Scala: Besseres Pattern-Matching mit Sealed ClassesNeulich bin ich auf eine <a href="http://www.mail-archive.com/jvm-languages@googlegroups.com/msg00121.html">recht interessante Mai</a>l in der jvm-languages Google Group gestossen. Ein Vergleich von Scala und OCaml! Wie spannend!<br />Besonders interessant fand ich folgendes Beispiel:<br /><pre><code><br /># let foo = function<br /> | true, _ -> 0<br /> | _, false -> 1;; <br />Warning P: this pattern-matching is not exhaustive.<br />Here is an example of a value that is not matched:<br />(false, true)<br />val foo : bool * bool -> int = <fun><br /></code></pre><br />OCaml liefert hier beim kompilieren einen Fehler: Das Patternmatching würde nicht alle Möglichkeiten erschöpfen. Zusätzlich bekommt man noch ein Beispiel wo der Match fehlschlägt. Tolle Sache! Das Scala Beispiel sieht hier doch eher ernüchternd aus.<br /><pre><code><br />scala> def foo(b: (Boolean, Boolean)): Int = b match {<br /> | case (true, _) => 0<br /> | case (_, false) => 0<br /> | }<br />foo: ((Boolean, Boolean))Int<br /><br />scala> foo(false, true)<br />scala.MatchError: (false,true)<br /> at .foo(<console>:4)<br /> at .<init>(<console>:5)<br /> at .<clinit>(<console>)<br /> at java.lang.Class.initializeClass(libgcj.so.81)<br /> at RequestResult$.<init>(<console>:3)<br /> at RequestResult$.<clinit>(<console>)<br /> at java.lang.Class.initializeClass(libgcj.so.81)<br /> at RequestResult$result(<console>)<br /> at java.lang.reflect.Method.invoke(libgcj.so.81)<br /> ...<br /></pre></code><br />Anscheinend ist Scala wohl nicht in der Lage herauszufinden welche Fälle möglich sind und kann so nicht testen ob das Matching auch wirklich alle Möglichkeiten ausschöpft. Aber genau dieser Effekt lässt sich mit Sealed Classes erreichen.<br /><br />Als Beispiel definiere ich einen eigenen Booltypen mit einem Subtypen für jeweils true und false (ich nehme hier Objects da wir nicht mehr als eine Instanz von True bzw. False brauchen). Das gleiche Beispiel schlägt hier mit einer ähnlichen Fehlermeldung wie bei OCaml fehl:<br /><pre><code><br />abstract sealed class MyBool<br />case object True extends MyBool<br />case object False extends MyBool<br /><br />object MyBool {<br /> def test(a: (MyBool, MyBool)): Unit = a match {<br /> case (True, _) => ()<br /> case (_, False) => ()<br /> }<br />} <br /><br />MyBool.scala:6: warning: match is not exhaustive!<br />missing combination False True<br /><br /> def test(a: (MyBool, MyBool)): Unit = a match {<br /> ^<br />one warning found<br /></pre></code><br />Die Sealed Class hat zur Folge das wir keine weiteren Subtypen außerhalb unser Quelldatei anlegen können, der Compiler hat jetzt also alle Information die er braucht um den Match zu prüfen.<br /><br />Mehr zum diesem Thema gibt es wieder mal <a href="http://gleichmann.wordpress.com/2011/02/05/functional-scala-algebraic-datatypes-sum-and-product-types/">bei Mario Gleichmann</a>.raichoohttp://www.blogger.com/profile/05235774661802634100noreply@blogger.com0tag:blogger.com,1999:blog-8144285405079538181.post-24972186153901956642011-01-31T10:36:00.000-08:002011-01-31T11:09:00.873-08:00Scala: Spass mit StreamsIch wurde ja neulich mal gefragt ob ich mal was über Streams in Scala bloggen könnte (auch wenn es hier eher um IO ging). Da mir da allerdings ein gutes Beispiel gefehlt hat, habe ich das erst einmal auf die lange Bank geschoben (irgendwie blogge ich derzeit glaub ich etwas zu wenig :/).<br /><br />Aber ok, dank eines <a href="http://gleichmann.wordpress.com/2011/01/30/functional-scala-algebraic-datatypes-enumerated-types/">hervorragenden Posts von Mario Gleichmann</a> bin ich dann doch noch auf eine ganz brauchbare Idee gekommen. (Schon allein Vollständigkeit halber empfehle ich den Post von Mario zu lesen!)<br /><br />Im folgenden Code geht es einfach nur darum die nachfolgende Jahreszeit zu bestimmen.<br /><code><pre><br />sealed abstract class Season<br />case object Spring extends Season<br />case object Summer extends Season<br />case object Fall extends Season<br />case object Winter extends Season<br /><br />object Main {<br /> lazy val seasons: Stream[Season] =<br /> Spring #:: Summer #:: Fall #:: Winter #:: seasons<br /><br /> def nextSeason(now: Season): Season = {<br /> @scala.annotation.tailrec<br /> def getNextFromStream(s: Stream[Season]): Season = <br /> s match {<br /> case a @ x #:: y #:: _ =><br /> if (now eq x)<br /> y<br /> else<br /> getNextFromStream(a tail)<br /> }<br /> getNextFromStream(seasons)<br /> }<br /><br /> def main(args: Array[String]): Unit = { <br /> println(nextSeason(Spring))<br /> println(nextSeason(Summer))<br /> println(nextSeason(Fall))<br /> println(nextSeason(Winter))<br /> }<br />}<br /></pre></code><br />Um die Jahreszeiten abzubilden nutze ich hier einen Stream (also eine unendliche Liste) die ich rekursiv durchgehe bis ich die aktuelle Jahreszeit gefunden habe und einfach die Nächste ausgebe.<br /><br />Dieses Beispiel wirkt zugegebenermaßen etwas wie mit Kanonen auf Spatzen zu schiessen, zeigt aber die Ausdrucksstärke von Streams und Lazy-Evaluation. Ein sehr realer Anwendungsfall ist hier z.B. ein Roundrobin-Verfahren. Anstelle also stumpf eine Liste durchzugehen und am Ende wieder an den Anfang springen in Zukunft einfach mal über einen Stream nachdenken ;)raichoohttp://www.blogger.com/profile/05235774661802634100noreply@blogger.com4tag:blogger.com,1999:blog-8144285405079538181.post-77783154908268734572010-12-25T05:57:00.000-08:002010-12-25T07:06:39.077-08:00Die Sache mit Apple"Hallo, ich bin raichoo und ich habe ein MacBook". Das sind Sätze mit denen man in vielen Kreisen schnell Freunde finden kann (Vorsicht Ironie!). Aber mal ehrlich, in den letzten Tagen kann man sich besonders schöne Kommentare gefallen lassen. Mein Favorit ist hier "Apfelnazi" (Goodwin's Law lässt grüßen). Die Diskussionskultur lässt hier ziemlich zu wünschen übrig, wer Leute nach dem Betriebssystem beurteilt hat in meinen Augen doch eher einen massiven Schaden.<br /><br />Aber was bewegt die Leute dazu so zu reagieren? Auf der einen Seite mag das ganze auf einem pseudoelitären Gefühl basieren. Apple ist Mainstream. Gegen Mainstream sein ist rebellisch, cool und was weiß ich noch alles. Ich bin ja selber keine Ausnahme, meine Lebensweise ist sicherlich nicht die eines Ottonormalverbrauchers. Aber diese extremen Anfeindungen gehen doch echt schon zu weit.<br />Doch zurück zu den Beweggründen. Wikileaks ist im Moment sicherlich ein sehr bewegendes Thema, und das Verhalten vieler Firmen wie Visa, Paypal, Mastercard und auch Apple ist nicht nur verwerflich, es ist in meinen Augen auch undemokratisch.<br />Was also machen? Boykottieren? Guter Plan, Boykott war immer schon die wirksamste Waffe des Verbrauchers, denkt man sich. Die Problematik die sich hieraus aber ergibt ist folgende: der überwiegende Großteil der Firmen wird so reagieren. Ein bisschen Druck vom Staat eventuell noch ein paar Zuwendungen unter der Hand und schon wird der Stecker gezogen. Unsere Freiheit wird also potentiell von jeder Firma beschnitten die nur den nötigen Einfluss hat, oben genannte Beispiele befinden sich nur gerade in dieser Situation besonders in so einer Position. Man kann sich also praktisch totboykottieren, der Hydra wachsen die Köpfe einfach nach.<br /><br />Wie also reagieren? Alle Apple Produkte aus dem Fenster werfen in den nächsten Mediamarkt rennen, ein Plastikwaffeleisen kaufen das nach einem Jahr auseinanderfällt und Ubuntu installieren? Ich sag es ehrlich: Linux ist derzeit einfach technisch keine Alternative für mich, und FreeBSD's Treibersituation auf Notebooks ist auch nicht wirklich berauschend. Windows mag ich nicht, usw.. Erreicht wird damit doch praktisch eh nichts. In meinen Augen ist beim Thema Wikileaks das effektivste Mittel doch eh: so hartnäckig spenden wie es nur geht. Wege dafür gibt es genug. Unterstützung ist weitaus mächtiger als Boykott.<br /><br />Wenn mir also jemand ein Notebook mit 13" Formfaktor, 6 Stunden+ Akkulaufzeit, Alugehäuse, großen Touchpad auf dem mindestens ein FreeBSD rennt (damit meine ich das ALLE Komponenten auch zuverlässige Treiber haben) und das dazu auch noch KEINERLEI Komponenten von irgendeiner Firma enthält die irgendwo mal Scheisse gebaut hat zeigen kann, bring it on. (Das ist ernst gemeint, würde mich interessieren ob es da draußen irgendwas gibt was dem auch nur ansatzweise entspricht)raichoohttp://www.blogger.com/profile/05235774661802634100noreply@blogger.com2tag:blogger.com,1999:blog-8144285405079538181.post-64941405726126899372010-09-20T10:39:00.000-07:002010-09-20T14:05:36.416-07:00Scala: Klassen erweitern mal andersDatentypen erweitern ist mehr oder weniger etwas das man des öfteren machen muss, und das ist nicht umbedingt immer unproblematisch. Nehmen wir mal an wir hätten folgende Klasse:<br /><code><pre><br />class Test(val x: Int)<br /></pre></code><br />Ganz klar: hochkomplizierter Code. <code>Test</code> quillt an Features nur so über, aber uns fehlt gerade eine Methode damit<br />wir Objekte dieser Klasse in unserem Code nahtlos verwenden können. Diese Methode nennen wir <code>bla</code>. Das Problem ist allerdings: Wir haben den Code von <code>Test</code> nicht und können ihn deswegen nicht um bla erweitern.<br />Jetzt gibt es verschiedene Wege wie wir diese Methode in <code>Test</code> einbinden könnten. Der offensichtlichste ist sicherlich Vererbung. Blöd ist nur: Wir haben <code>bla</code> schon geschrieben und würden ihn ungern duplizieren, vor allem weil wir den Code bereits schön generalisiert haben.<br /><br />Eine Lösung ist hier ziemlich elegant mit Traits, Selftyping und Structural Types zu machen.<br /><br />Als erstes definieren wir einen Structural Type der eine genaue Schnittstelle definiert. Wir nennen ihn <code>xAble</code> und er macht nichts weiter als zu definieren das alle Klassen die eine Methode <code>x</code> anbieten vom Typ <code>xAble</code> sind.<br /><code><pre><br />type xAble = { def x: Int }<br /></pre></code><br />Was wir jetzt brauchen ist unsere generalisierte Implementation von <code>bla</code>. Hier verwenden wir, Selftyping. Das ist ein Feature das es uns erlaubt innerhalb eines Traits so zu tun als wäre es von einem bestimmten Typ ohne davon zu erben.<br /><code><pre><br />trait Gimme[A <: xAble] {<br /> self: A =><br /> def bla(): Unit = println(self.x + 1) <br />}<br /></pre></code><br />Wie man sieht muss der muss der Typparameter <code>A</code> ein Subtyp von <code>xAble</code> sein, also die methode <code>x</code> liefern.<br /><br />Alles was wir jetzt noch machen müssen ist das Trait <code>Gimme</code> in das Objekt des Typs <code>Test</code> zu mischen und wir haben das ganze um <code>bla</code> erweitert.<br /><code><pre><br />object Main {<br /><br /> class Test(val x: Int)<br /><br /> type xAble = { def x: Int }<br /><br /> trait Gimme[A <: xAble] {<br /> self: A =><br /> def bla(): Unit = println(self.x + 1)<br /> }<br /><br /> def main(args: Array[String]): Unit = {<br /> val t = new Test(666) with Gimme[Test] <br /> t.bla()<br /> }<br />}<br /></pre></code><br />Das ganze Zeit mal wieder wie extrem mächtig das Scala Typsystem ist und was für elegante Features die Sprache zum lösen immer wiederkehrender Probleme bietet. Ich hoffe dieses Beispiel gibt euch eine kleine Idee was man damit machen kann. ;)raichoohttp://www.blogger.com/profile/05235774661802634100noreply@blogger.com3tag:blogger.com,1999:blog-8144285405079538181.post-89244687822162306672010-06-24T12:58:00.000-07:002010-06-24T13:04:17.590-07:00FreeBSD 8.1 und die JVMAlios hat gerade seinen Server auf den neusten Stand gebracht und prompt funktionierte Sakura natürlich wieder nicht. Das Problem war das die JVM wohl anscheinen den IPv6 Stack genommen hat und sich damit nicht verträgt, ein Workaround ist die JVM einfach dazu zu zwingen den IPv4 Stack zu nehmen. Das geht mit der <code>-Djava.net.preferIPv4Stack=true</code> Option.<br /><br />Wenn euch also das nächste mal ein Socket beim Connect aus unerfindlichen Gründen abraucht, versucht es mal damit.raichoohttp://www.blogger.com/profile/05235774661802634100noreply@blogger.com0tag:blogger.com,1999:blog-8144285405079538181.post-5654416328170873322010-06-24T12:56:00.001-07:002010-06-24T12:56:34.621-07:00100 Posts!<object width="480" height="385"><param name="movie" value="http://www.youtube.com/v/YFqtye2_3E4&hl=en_US&fs=1&"></param><param name="allowFullScreen" value="true"></param><param name="allowscriptaccess" value="always"></param><embed src="http://www.youtube.com/v/YFqtye2_3E4&hl=en_US&fs=1&" type="application/x-shockwave-flash" allowscriptaccess="always" allowfullscreen="true" width="480" height="385"></embed></object>raichoohttp://www.blogger.com/profile/05235774661802634100noreply@blogger.com0tag:blogger.com,1999:blog-8144285405079538181.post-48921649002769589202010-06-21T09:09:00.000-07:002010-06-21T09:24:49.932-07:00Spass mit Scala InfixtypenIn Scala gibt es das interessante Konzept der Infix Typen, dabei handelt es sich um nichts weiter als Typen die zwei Parameter erwarten. Scala erlaubt hier Infix Notation.<br /><code><pre><br />object Main {<br /> class FooBar[A, B]<br /><br /> def main(args: Array[String]): Unit = { <br /> //zwei unterschiedliche Schreibweisen die das gleiche<br /> //meinen<br /> var x: FooBar[Int, BigInt] = null<br /> var y: Int FooBar BigInt = null<br /> }<br />}<br /></pre></code><br />Damit eröffnen sich interessante Möglichkeiten des Typsystems, z.B: "Operatoren" aus Typen erstellen die wiederum Typen erstellen. Verwirrt? In Scala gibt es bereits <code>=:=,</code> <code><:<</code> und <code><%<</code>, diese Konstrukte kann man sich unter anderem auch selbst zusammenbasteln, im folgenden Beispiel bauen wir uns einen <code><@@@<</code> "Operator"<br /><code><pre><br />abstract class <@@@<[A, B] extends (A => B)<br /><br />class Test[T <: (Int => Int)]<br /><br />object Main {<br /> def main(args: Array[String]) = { <br /> val t = new Test[Int <@@@< Int]<br /> }<br />}<br /></pre></code><br />Ziemlich cool, jetzt kann man sich Operatoren basteln die Typen erstellen und sich anfühlen wie native Features der Sprache :)raichoohttp://www.blogger.com/profile/05235774661802634100noreply@blogger.com0tag:blogger.com,1999:blog-8144285405079538181.post-65982454893073195122010-06-02T13:11:00.000-07:002010-06-02T14:46:28.475-07:00Paralleles Primzahlsieb in ScalaNach der Präsentation von Google Go habe ich mich gefragt ob man das parallele Primzahlsieb auch in Scala so machen kann. Ich muss sagen das ich das Resultat sogar einfacher und eleganter finde als die Go Implementation. Sicherlich gibt es performantere Algorithmen aber hier geht es einfach um das Prinzip zu zeigen wie einfach man Parallelisieren kann.<br /><br />HINWEIS: Das Programm terminiert nicht, da für jede Primzahl ein eigener "Thread" (Actors die per react warten verhalten sich nicht ganz so wie Threads die in einem Loop warten, sondern sind leichtgewichtiger) gestartet wird und diese weiter auf Futter warten. Es ist auf jeden Fall möglich das das ganze anhält, ich will lediglich das Prinzip zeigen und das Beispiel nicht unnötig aufblasen.<br /><br /><code><pre><br />import scala.actors.Actor<br />import scala.actors.Actor._<br /><br />class Prime(value: Int) extends Actor {<br /> var next: Option[Prime] = None<br /><br /> println(value)<br /> start<br /><br /> def act(): Unit = loop {<br /> react {<br /> case x: Int if ((x % value) != 0) => <br /> next match {<br /> case Some(p: Prime) => p ! x <br /> case None => next = Some(new Prime(x))<br /> } <br /> } <br /> } <br />}<br /><br />object Main {<br /> def main(args: Array[String]): Unit = { <br /> val primer = new Prime(2)<br /> 3 to args(0).toInt map (primer ! _)<br /> }<br />}<br /></pre></code>raichoohttp://www.blogger.com/profile/05235774661802634100noreply@blogger.com0tag:blogger.com,1999:blog-8144285405079538181.post-61657703390659150472010-05-10T13:26:00.000-07:002010-05-10T13:29:49.980-07:00Mergesort in ScalaUnd aus der Kategorie "Sortieren für Besessene" kommt heute mal wieder ein Beispiel, aber ausnahmsweise kein Quicksort ;)<br /><br />Was ich besonders toll an diesem Beispiel finde ist das auf gleich 2 Listen gleichzeitig gematcht wird wie es auch in Haskell geht. Da hat Scala mal wieder richtig Spass gemacht.<br /><br /><code><pre><br />object Main {<br /><br /> def merge[T <% Ordered[T]](l: List[T], r: List[T]): List[T] = <br /> (l,r) match {<br /> case (x::xs, y::ys) => if (x < y)<br /> x::(merge(xs, r)) <br /> else<br /> y::(merge(l, ys))<br /> case (xs, Nil) => xs<br /> case (Nil, ys) => ys<br /> } <br /><br /> def mergesort[T <% Ordered[T]](list: List[T]): List[T] = <br /> if (list.length > 1) { <br /> val (l, r) = list splitAt (list length)/2<br /> merge(mergesort(l), mergesort(r))<br /> } else list<br /><br /> def main(args: Array[String]): Unit = { <br /> println(mergesort(List(4,5,9,1,2,4,5,9,8,7)))<br /> }<br />}<br /></pre></code>raichoohttp://www.blogger.com/profile/05235774661802634100noreply@blogger.com0tag:blogger.com,1999:blog-8144285405079538181.post-50042033684297635312010-05-08T17:22:00.000-07:002010-05-08T17:24:01.536-07:00Scala in der Warpzone<object width="400" height="300"><param name="allowfullscreen" value="true" /><param name="allowscriptaccess" value="always" /><param name="movie" value="http://vimeo.com/moogaloop.swf?clip_id=11585013&server=vimeo.com&show_title=1&show_byline=1&show_portrait=0&color=&fullscreen=1" /><embed src="http://vimeo.com/moogaloop.swf?clip_id=11585013&server=vimeo.com&show_title=1&show_byline=1&show_portrait=0&color=&fullscreen=1" type="application/x-shockwave-flash" allowfullscreen="true" allowscriptaccess="always" width="400" height="300"></embed></object><p><a href="http://vimeo.com/11585013">Scala in der warpzone Münster</a> from <a href="http://vimeo.com/user3772791">raichoo</a> on <a href="http://vimeo.com">Vimeo</a>.</p>raichoohttp://www.blogger.com/profile/05235774661802634100noreply@blogger.com0tag:blogger.com,1999:blog-8144285405079538181.post-48936679071992318322010-04-17T01:43:00.001-07:002010-04-17T01:51:57.930-07:00Git-Mode für die KSHIch habe gerade mal meine Git Erweiterung für die <a href="http://kornshell.org/">Kornshell</a> in meinen <a href="http://bitbucket.org/raichoo/">Bitbucket</a> gestellt. Das ganze liegt zwar noch unter "Mercurial-Integration" aber sollte zu finden sein ;). Wie schon beim <a href="http://raichoo.blogspot.com/2010/02/ksh93-mercurial-promptmode.html">Mercurial mode</a> wechselt man mit <code>mode git</code> in den entsprechenden Modus. Die Farbe der Commit ID wechselt von Rot (uncommited changes) zu Gelb (nicht die aktuellste Revision) zu Grün (aktuellste Revision und nichts zu commiten). Außerdem wird der aktuelle Branch angezeigt und im Falle eines "detached HEAD" Zustands visuell gewarnt. Viel Spass damit!<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg1z_KCP63n8h8CSmzS4qKAuiKVHVpF04r4xRPTwbczLi99iZvSj2xZD24WWPlfj6CN4aJF_KqmiLN31I7YK8hQ6QFGouX9y1h3BaQYlKbx8mg4eRfJHe_wdHArIZdNgBxJNh77hoAsRrOf/s1600/Screen+shot+2010-04-17+at+10.25.57+AM.png"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 320px; height: 214px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg1z_KCP63n8h8CSmzS4qKAuiKVHVpF04r4xRPTwbczLi99iZvSj2xZD24WWPlfj6CN4aJF_KqmiLN31I7YK8hQ6QFGouX9y1h3BaQYlKbx8mg4eRfJHe_wdHArIZdNgBxJNh77hoAsRrOf/s320/Screen+shot+2010-04-17+at+10.25.57+AM.png" border="0" alt=""id="BLOGGER_PHOTO_ID_5461025051720848514" /></a>raichoohttp://www.blogger.com/profile/05235774661802634100noreply@blogger.com0