Saturday, July 27, 2013

REBOL Without A Cause

So Thursday was this months' Code Retreat over at Bento. We were solving the Poker Hands kata that I've already written about, so Gaelan and I decided to make an attempt using REBOL3. Because I've already written about it, I'm not going to explain the problem, or go very deeply into code-review-style exposition.

I'll show you some REBOL3 code, point out the highlights and the confusing bits, and call it a day. Hit up the chat room if you have questions.

The First Crack

REBOL []

map-f: func [ fn a-list ] [
    res: make block! 5
    foreach elem a-list [ append res do [fn elem] ]
    res    
]

group: func [ a-list ] [
    res: make map! 5
    foreach elem a-list [
        either res/(elem)
        [ poke res elem res/(elem) + 1 ]
        [ append res reduce [ elem 1 ]]
    ]
    res
]

test-hand: [[ 1  hearts ] [ 2 clubs ] [ 3 clubs ] [ 4 diamonds ] [ 5 hearts ]]
test-flush: [[ 1  hearts ] [ 2 hearts ] [ 3 hearts ] [ 4 hearts ] [ 5 hearts ]]

group-by-rank: func [ hand ] [
    group map-f func [ a ] [ first a ] hand
]

group-by-suit: func [ hand ] [
    group map-f func [ a ] [ second a ] hand
]

is-flush: func [ hand ] [
    1 = length? group-by-suit hand
]

is-pair: func [ hand ] [
    grouped: group-by-rank hand
    foreach k grouped [
        if grouped/(k) = 2
    ]
]

Our first attempt was pretty pathetic, all things considered. Most of that comes down to lack of familiarity with the language, and a desire on my part to do things functionally. The first meant that we spent about 15 minutes trying to figure out how to set the value of a particular map slot[1]. The second meant that I had to implement a couple of basics myself, one of which I was used to having provided even in batteries-not-included languages like Common Lisp. The above isn't actually a valid approach because of r3's default scope. Which means

>> do %poker-hands.r
do %poker-hands.r
Script: "Untitled" Version: none Date: none
>> res: "Foobarbaz"
res: "Foobarbaz"
== "Foobarbaz"

>> map-f func [ a ] [ a + 1 ] [ 1 2 3 4 5 ]
map-f func [ a ] [ a + 1 ] [ 1 2 3 4 5 ]
== [2 3 4 5 6]

>> res
res
== [2 3 4 5 6]

Don't worry; there's a way around this which I'll discuss later. After the event, I made a few refinements and got it up to

The Second Crack

REBOL []

fn: make object! [
    map: func [ fn a-list ] [
        res: make block! 5
        foreach elem a-list [ append res do [fn elem] ]
        res
    ]
    range: func [ start end ] [
        res: make block! 10
        step: either start < end [ 1 ] [ -1 ]
        for i start end step [ append res i ]
        res
    ]
    frequencies: func [ a-list ] [
        res: make map! 5
        foreach elem a-list [
            either res/(elem)
            [ poke res elem res/(elem) + 1 ]
            [ append res reduce [ elem 1 ]]
        ]
        res
    ]
    val-in?: func [ val map ] [
        foreach k map [
            if map/(k) = val [ return true ]
        ]
        return false
    ]
]

hands: make object! [
    straight: [[ 1  hearts ] [ 2 clubs ] [ 3 clubs ] [ 4 diamonds ] [ 5 hearts ]]
    straight-flush: [[ 1  hearts ] [ 2 hearts ] [ 3 hearts ] [ 4 hearts ] [ 5 hearts ]]
    pair: [[ 2  hearts ] [ 2 clubs ] [ 3 clubs ] [ 4 diamonds ] [ 5 hearts ]]
    two-pair: [[ 2  hearts ] [ 2 clubs ] [ 3 clubs ] [ 3 diamonds ] [ 5 hearts ]]
]

ranks: func [ hand ] [ fn/map func [ a ] [ first a ] hand ]
suits: func [ hand ] [ fn/map func [ a ] [ second a ] hand ]

count-ranks: func [ hand ] [ fn/frequencies ranks hand ]
count-suits: func [ hand ] [ fn/frequencies suits hand ]


has-flush: func [ hand ] [
    1 = length? group-by-suit hand
]

has-straight: func [ hand ] [
    rs: sort ranks hand
    rs = fn/range rs/1 (rs/1 + (length? rs) - 1)
]

has-straight-flush: func [ hand ] [
    all [ has-straight hand has-flush hand ]
]

has-group-of: func [ size hand ] [
    fs: count-ranks hand
    fn/val-in? size fs
]

has-pair: func [ hand ] [ has-group-of 2 hand ]
has-three: func [ hand ] [ has-group-of 3 hand ]
has-four: func [ hand ] [ has-group-of 4 hand ]
has-two-pair: func [ hand ] [
    fs: fn/frequencies values-of count-ranks hand
    2 = fs/2
]
has-full-house: func [ hand ] [ all [ has-pair hand has-three hand ]]

Not much trouble taking that step, once I kind of sort of got what I was doing, but I'd be coding along and occasionally get invalid argument errors. And it would always turn out to be a problem with the separation of arguments and calls. It happened in quite a few places, but the worst offender was

has-straight: func [ hand ] [
    rs: sort ranks hand
    rs = fn/range rs/1 (rs/1 + (length? rs) - 1)
]

That line starting with rs = , specifically. Initially, it read rs = fn/range rs/1 rs/1 + length? rs - 1. Interpreter says: WTFYFWWYETT?[2]. What the snippet means is what you can read from the parenthesized version above. That is,

Apply the function fn/range to the argument "rs/1" and the argument "one less than the length? of rs added to rs/1".

This is probably an expressive edge-case, but it's slightly concerning that I ran into it so soon. That scope issue is still outstanding, by the way. Object!s don't have internal scope by default either, which begs the question of why they're called "Objects", so the net effect is still the same.

>> do %poker-hands.r
do %poker-hands.r
Script: "Untitled" Version: none Date: none
>> res: "Foobarbaz"
res: "Foobarbaz"
== "Foobarbaz"

>> fn/map func [ a ] [ a + 1 ] [ 1 2 3 4 5 ]
fn/map func [ a ] [ a + 1 ] [ 1 2 3 4 5 ]
== [2 3 4 5 6]

>> res
res
== [2 3 4 5 6]

Anyhow, it technically runs. As long as you don't nest map or frequency calls. After a trip over to the Rebol/Red chat room on SO for some quick review by actual rebollers[3], I got to

The Third Crack

REBOL []

fn: context [
    map: funct [ fn a-list ] [
        res: make block! 5
        foreach elem a-list [ append/only res do [fn elem] ]
        res
    ]
    range: funct [ start end ] [
        res: make block! 10
        step: either start < end [ 1 ] [ -1 ]
        for i start end step [ append res i ]
        res
    ]
    frequencies: funct [ a-list ] [
        res: make map! 5
        foreach elem a-list [
            either res/(elem)
            [ poke res elem res/(elem) + 1 ]
            [ append res reduce [ elem 1 ]]
        ]
        res
    ]
    val-in?: funct [ val map ] [
        foreach k map [
            if map/(k) = val [ return true ]
        ]
        return false
    ]
]

hands: make object! [
    straight: [ ♥/1  ♣/2  ♣/3  ♦/4  ♠/5 ]
    straight-flush: [ ♥/1  ♥/2  ♥/3  ♥/4  ♥/5 ]
    pair: [ ♥/2  ♣/2  ♣/3  ♦/4  ♠/5 ]
    two-pair: [ ♥/2  ♣/2  ♣/3  ♦/3  ♠/5 ]
]

read-hand: func [ hand-string ] [
    suits-table: [ #"H" ♥  #"C" ♣  #"D" ♦  #"S" ♠ ]
    ranks-table: "--23456789TJQKA"
    fn/map func [ c ] [
        to-path reduce [ 
            select suits-table c/2 
            offset? ranks-table find c/1 ranks-table ]
    ] parse hand-string " "
]

ranks: func [ hand ] [ fn/map func [ c ] [ probe second c] hand ]
suits: func [ hand ] [ fn/map func [ c ] [ probe first c ] hand ]

count-ranks: func [ hand ] [ fn/frequencies ranks hand ]
count-suits: func [ hand ] [ fn/frequencies suits hand ]


has-flush: func [ hand ] [
    1 = length? group-by-suit hand
]

has-straight: func [ hand ] [
    rs: sort ranks hand
    rs = fn/range rs/1 (rs/1 + (length? rs) - 1)
]

has-straight-flush: func [ hand ] [
    all [ has-straight hand has-flush hand ]
]

has-group-of: func [ size hand ] [
    fs: count-ranks hand
    fn/val-in? size fs
]

has-pair: func [ hand ] [ has-group-of 2 hand ]
has-three: func [ hand ] [ has-group-of 3 hand ]
has-four: func [ hand ] [ has-group-of 4 hand ]
has-two-pair: func [ hand ] [
    fs: fn/frequencies values-of count-ranks hand
    2 = fs/2
]
has-full-house: func [ hand ] [ all [ has-pair hand has-three hand ]]

Note that the definitions of fn, and in particular fn/map have changed subtly. The change to fn in general is that each of its functions is now a funct instead of just a func. This is the solution to that scope problem from earlier; funct provides an implicit scope for its body block where func doesn't. Meaning that if you define fn in this new way, you can now actually do

>> res: "Foobarbaz"
res: "Foobarbaz"
== "Foobarbaz"

>> fn/map func [ a ] [ a + 1] [ 1 2 3 4 5 ]
fn/map func [ a ] [ a + 1] [ 1 2 3 4 5 ]
== [2 3 4 5 6]

>> res
res
== "Foobarbaz"

>> 

and you can safely nest fn/map/fn/frequencies calls.

The other subtle change to fn/map specifically is that it now uses append/only rather than append. The reason for this is that append implicitly splices its arguments. That is

>> do %poker-hands.r ;; map defined with plain append
do %poker-hands.r ;; map defined with plain append
Script: "Untitled" Version: none Date: none
>> read-hand "1H 2C 3C 4D 5S"
read-hand "1H 2C 3C 4D 5S"
== [♥ 1 ♣ 2 ♣ 3 ♦ 4 ♠ 5]

>> do %poker-hands.r ;; changed to append/only
do %poker-hands.r ;; changed to append/only
Script: "Untitled" Version: none Date: none
>> read-hand "1H 2C 3C 4D 5S"
read-hand "1H 2C 3C 4D 5S"
== [♥/1 ♣/2 ♣/3 ♦/4 ♠/5]

>> 

Apparently the original author found that he was doing sequence splicing more than actual appending. But instead of writing a separate splice function, or maybe a /splice refinement to append, he made splicing appends' default behavior. No, I have no idea what he was smoking at the time.

In order to get the behavior you'd probably expect from plain append, you have to run the refinement /only, which as far as I can tell, generally means "do what you actually wanted to do" on any function it's provided for. A guy calling himself Hostile Fork says it better than I could:

We don't tell someone to take out the garbage and then they shoot the cat if you don't say "Oh...wait... I meant ONLY take out the garbage"! The name ONLY makes no semantic sense; if it did make sense, then it's what should be done by the operation without any refinements!-Hostile Fork

Afermath

So that's that. I didn't get to a working solution yet, because this script doesn't compare two hands to determine a winner (or a draw), and it doesn't handle the aces-low edge case, but I'll leave those as an exercise for the reader. It'll tell you what hand you have, and it can elegantly read the specified input. At the language level, REBOL3 is interesting. And the community is both enthusiastic and smart. And I really hope the r2/3 transition gives them the excuse to clean up the few counter-intuitive things that slipped in over time. It's enough that I'm making an addition to the logo bar, which I don't do lightly[4].

This series of tinkering had no particular cause. I was just playing around with a problem I had lying around in a language I was curious about. Next time, I'll pick one, probably some kind of lightweight application server, and see how far I can push it. Hopefully that doesn't get too far in the way of my LISP project...


Footnotes

1 - [back] - Using poke, in case you're curious.

2 - [back] - What The Fuck You Fucker, Why Would You Ever Type That?

3 - [back] - I have no idea why they don't just call themselves "rebels".

4 - [back] - PHP logo notwithstanding.

Thursday, July 25, 2013

Dear The Internet

Dear The Internet,

I see you're having security problems, so I'm going to let you in on a technique for doing proper authentication. I've discussed it before, but I get the feeling you thought I was trafficking in trade secrets, and scrupulously decided not to hear too much. Let me be clear that this is public knowledge, and is meant for sharing.

Proper Authentication

To start with, your server should have a public/private keypair, and so should your users. When a user registers, ask them for their public key, and publish the server's public key in a few disparate places on the web. Then, when a user wants to log in

  1. the user specifies their account with an account name
  2. the server generates a piece of random state, encrypts it with the accounts' public key, signs it, and sends both the cyphertext and the signature to the client
  3. the client verifies the signature, decrypts the cyphertext message, signs the resulting cleartext and sends the signature back to the server
  4. the server verifies the signature against the state it sent out for that account

Assuming everything went well, the server can act on a successful authentication.

What just happened?

  • The user knows that the server they're communicating with has access to the private key they expect
  • The server knows that the user they're speaking to has access to the private key that corresponds to the user account asking for authentication
  • Finally, critically, neither has enough information to allow impersonation of the other

There! That's the secret! Now you'll never fuck it up again!

This is a way to prevent any further "Oh noez, our server got hacked!" garbage forever, because if a server using this auth method got hacked, all the hackers actually got is information that's already public, or can reasonably be.

Before you pipe up with the "But users are too stupid to use private keys" thing, shut up.

Just shut up.

The user doesn't have to do this manually; it's easy to imagine a series of plugins, one for each browser, that implement key generation, encryption and management for a user without them having to really understand what's inside the black box. More importantly, even a stupid, simplified, operationally insecure PK authentication system with full focus on ease-of-use would be better than using passwords on the server side.

Please please consider this, The Internet, I'm getting really worried about you.

Sincerely yours,

-Inaimathi

Saturday, July 20, 2013

REBOL

One of the things we talk about at the Toronto Common Lisp User Group meetings is, possibly surprisingly, other interesting languages, whether classical or up-and-coming.

REBOL (pronounced the same as "rebel") is one that got mentioned a few times. And it sounded quite interesting. But I never talked about it here because it was released under a proprietary license, and as you've probably guessed if this blog wasn't evidence enough, I'm a GPL nerd. Well, as of REBOL3, the language is released under the Apache v2.0 license, which officially makes it Free Software. You can find the complete source here.

It's a fairly recent development, so this isn't one you can apt-get install quite yet. So, here's how you go about building it on Debian.

Before We Get Started...

You'll obviously need git and make installed.

apt-get install git make

Then...

...you'll need to clone the REBOL3 repo.

git clone https://github.com/rebol/r3.git

And then you'll need to download the r3 binary from this page. If you're on an x86 linux machine, you have a choice of three depending on what version of libc you have installed. To find that out, run ldd --version[1]. Once you've go that, unpack it, and rename the new r3 file to r3-make.

On 32-bit machines...

You're pretty much done. Enter

make make # re-generate the makefile
make prep # generate relevant header files
make      # compile REBOL

After a minute or so, you should have a binary file called r3 that you can add to your path as a REBOL3 interpreter.

On 64-bit machines...

... you have a couple more things to do. Specifically, you need to run this as root[2]

dpkg --add-architecture i386
aptitude update
apt-get install ia32-libs 
apt-get install libc6-dev-i386

That will add the 32-bit versions of libc and some other libraries so that you can actually run the compilation step.

Now Then

You can find the basic primer here, but the thing that most interests me about REBOL so far is its implementation and use of parse, which you can see demonstrated here, here and here, though there have been changes between REBOL2 and REBOL3. You can find the appropriate Emacs mode here, and I'm already thinking of the changes I want to make to it. Other interesting documentation includes the REBOL3 guide, the list of REBOL3 functions and this SO answer which includes a quick REBOL3 CGI script, though really, anything in the rebol3 tag is pretty interesting.


Footnotes

1 - [back] -Note that if you're just out to use the language, and don't really care about any of this Software Freedom business, you've already wasted some time. You can just get the appropriate binary and call it a day. I'm getting it because REBOL3 builds part of itself using REBOL3 scripts. And I'm compiling my own because I like being able to see inside of the languages I use, and I'm a big enough nerd to actually do it from time to time, and I've probably spent more time than is strictly healthy listening to Richard Stallman. Proceed or ignore the remaining parts of the process at your discretion.

2 - [back] -Thank you user Fork from this thread.

Thursday, July 18, 2013

Ping

I'm still alive, just so you know.

LISP Contest

The past little while has seen me refine my entry to the Lisp In Summer Projects contest. You can find the code here, in case you'd like to keep an eye on progress, but it's not playable yet, and I don't want to talk about it until I've at least ironed out some of the big questions. Don't worry, I'm keeping a journal, so you'll see all the gory details rather than just a finished product, but I want to have a product before I show it off. On a related note, I've been told that there's a local Bento-based group called Games With Friends that regularly tests tabletop card and board games in meatspace. I'm seriously considering dropping by, both before and after I get a working system together.

Work

I've started my new job, and it's fun so far. On a scale of 1 to 10, the levels of paranoia and bureaucracy here are Dilbert, and apparently that's all I'll be able to tell you. Not that I ever blogged about the actual systems I was working on at my old job, but we're going to be doing some very interesting things here[1] and I was looking forward to being able to talk about them. I won't though; anything past what I've already said could compromise some of my employers' IP, or at least run a significant risk of doing so, and no offense, but that risk isn't worth it for the sake of a hobby blog. So that's that.

  • We're doing R&D work
  • It involves embedded systems
  • It's very interesting
  • Lots of the locals are severely, sometimes paralyzingly, paranoid about security
  • It's sometimes necessary to requisition a requisition-form-requisition form

...and you won't hear anything else about what I'm working on at work until I start working somewhere else.

Fiction

I just finished reading Neptune's Brood by Charlie Stross, which can best be thumbnailed as "Accountants In Spaaaaace!", and it was an excellent read. This is the sort of stuff I go to Stross for; not the usual Star-Wars-esque naval battles in 3 dimensions, but a hard look at what space battles would actually look like in the absence of hand-waivium and plottite. I'm not sure how sympathetic the characters are since I'm a lousy judge of these things[2], but the world and in particular its finance system is constructed in such a way as to make space-colonization by humans[3] plausible both in the physics and economics senses. The societal implications about our deep future are less than encouraging, but I don't want to spoiler any part of this before anyone reading this has likely gotten a chance to read it. I got the hard-back through an Amazon pre-order, but you can probably walk into your local Chapters and just pick up a fresh one by this point.


Footnotes

1 - [back] - Well, by my definition of "very" and "interesting" at any rate.

2 - [back] - I thought the crew of Blindsight was very well thought out and understandable in the human sense, only to find out that the author had gotten feedback about how un-cuddly they were. That's another very interesting piece of non-hand-wavium sci-fi that I can recommend, by the way. Easily the best vampire story I've ever read.

3 - [back] - Or at least post-humans.

Thursday, July 11, 2013

Bittersweet

So I'm leaving another company today.

It's ok, everyone knows.

Actually, they knew about four weeks ago, I gave them ample notice because I genuinely liked working with them. They're on the market for a Common Lisp/Python/JavaScript developer, by the by. Company details here if you're both "in Toronto" and "interested". There's an Employment link at the bottom of the sidebar.

This is probably the first time I've left an employer with, on balance, positive feelings. I don't think there's anything here I'm glad to be getting away from, unlike last time. I mean, you know, all the usual complaints that apply to any less-than-10-man shop, but nothing that actually prevented me from enjoying damn-near all of it. We made our best effort at avoiding the classic Agile tar-pit, we put together the best practices we could, including source-control, bug-tracking and project wikis. We used tools appropriate to the situation, and tried to solve problems in scalable, reliable and secure ways. If there was anyone other than me there who knew Common Lisp and Python, we'd have done extensive code-reviews too.

We didn't GPL any of our code, which always disappointed me, because it meant that I

  • couldn't get an outside opinion without collecting NDAs, which I don't like doing
  • won't be able to reasonably work on the projects any more after I leave

That's in addition to the usual argument about how sufficiently interesting projects are just plain better off becoming open source, so that they can leverage as many developers as they can attract, rather than merely as many as their owners can pay for. There's a threshold at which the first number is so much larger than the second that it really doesn't make sense to keep secrets, and I think at least two of the projects I shepherded could cross it given the chance. Such is life, I suppose.

The new place is going to offer some serious challenges. Starting with, I'm sure, a week or two of severe culture-shock. You see, I've never actually worked at a company with more than about 200 employees. I mean, my employers have contracted for various bureaucracies, ranging from multi-national food chains, to hardware suppliers, to actual governments, but I've always been the visiting contractor or IT consultant. I'm not sure I'll like it, but I'll try almost anything once.

The work will be different. Instead of a bunch of projects, we have The Project, and from what I understand it's a fairly ambitious piece of R&D/prototyping work that has a good chance of changing the world by end of next year. In a good way, I think. The other really big draw for me is that I get to work with people who are, by my reckoning, much more skillful developers than I am. It's been a really long time since I've done that, and I wasn't far enough along my learning process that I could take advantage of it last time.

I've been told not to worry about the culture, and that the biggest challenge will be learning about systems and techniques. Which is not a problem, as you know if you've met me.

"Learning things" is my default state.