Asocial networking

[dmbaturin]

Design for partial application

In languages that don't support partial application or don't make it convenient enough for frequent use, order of arguments is not very important.

When it's handy to use, it's a good idea to use argument order that facilitates partial application.

Consider these functions:

val filter : (α → bool) → α list → α list val filter' : α list → (α → bool) → α list

The first one makes it easy to do something like

let only_even xs = filter (fun x → x mod 2 = 0) xs

The other one is cumbersome to use this way. Sometimes it's not immediately obvious which argument is likely to stay the same in multiple calls, so it's probably worth it to stop and think it through rather than write arguments in the order they come to mind.

[dmbaturin]

OCaml and SML signature ascription

Sometimes you find yourself writing one language in another (Fortran77 programmers can write Fortran77 in any language). If, for whatever reason, I write SML, I usually find myself writing OCaml in it. Most of the time no one would notice because they are similar, but sometimes it means ignoring a difference that I could possibly take advantage of. Anyway, what I remembered and decided to look into is signature ascription.

In OCaml, there's only one way to say "module Foo implements signature FOO". In SML there are two ways to do it.

One way, shared by both languages, is opaque ascription. It hides any abstract types and makes them incompatible with their concrete counterparts defined outside the module. This is what I learn first, that "structure Foo :> FOO" in SML is the same thing as "module Foo : FOO" in OCaml. A simple example of what opaque means:

(* SML *) signature FOO = sig type t val f : t -> t end structure IntFooOpaque :> FOO = struct type t = int fun f x = x + 1 end (* OCaml *) module type FOO = sig type t val f : t -> t end module IntFooOpaque : FOO = struct type t = int let f x = x + 1 end

If we try to use IntFooOpaque.t as int (as in IntFooOpaque.f 0), it doesn't typecheck, which is expected since this construct is supposed to enforce data abstraction. This could become a problem if all we want from a signature is to ensure a module implements certain functions, but in practice it doesn't, since functors take structures as arguments, and we can always make a module with a concrete type and use a functor to produce what we need.

In SML, however, there's also transparent ascription that doesn't enforce abstraction.

structure IntFoo : FOO = struct type t = int fun f x = x + 1 end (* IntFoo.t can be used anywhere where int would do! *) > IntFoo.f 9 ; val it = 10: IntFoo.t

I'm not really sure how I feel about it, since it complicates the language, but I think there are cases where it could make things simpler and more expressive. SML functors can also be transparent, but I didn't look deep into it yet.

[dmbaturin]

IPv6 internet map, 2015 edition.

Compared to my previous map from 2012, it looks like IPv6 internet became more well connected. Both maps were made from the same AS BGP dump. Every dot is an autonomous system.

I tried to make its IPv4 counterpart too, but this time it required more memory than I have in my desktop, so I'll have to come up with something before I can make the IPv4 graph.

You can get a bigger image here (about 3000x3000).

The original graphviz output is a 65Mbyte 15506x14238 PNG, that file and the graphviz script are available upon request if anyone is interested.

How it was made

Routes that routers advertise to each other via BGP include a prefix (e.g. "2001:db8::/32") and an AS path (e.g. "24785 20562 6939 23911 9406"). When re-advertising a route learnt from a peer, routers prepend their own autonomous system number to the path, so a path shows what autonomous systems will the traffic go through. BGP itself uses it to select shortest paths. We can easily translate a set of AS paths extracted from the BGP table to a graph where AS numbers are nodes and their adjacencies in paths are edges.

Since every network may have a large number of routers that all use the same AS number, it only shows what networks communicate routes to one another, not how they are physically connected. Also, routers only re-advertise best known paths, so some connections may not be visible, and the picture may be different for different parts of the net.

[dmbaturin]

Create your own interpreter directives in OCaml

Like preprocessor directives in C, OCaml interpreter directives are not a part of the language. What is interesting though is that you can create your own.

"#require" is the most widely used example probably. It is defined in findlib, so you need to load a module before you can use it.

Thanks to findlib source code and whitequark, I've figured how to add my own. The interpreter stores directive names and functions in a Hashtbl, which is mutable. The only pitfall is that it requires Toploop module from compiler-libs which interacts with the interpreter in an unusual way and loading it the usual way doesn't work.

Now we'll create "#testdirective" directive that simply prints its argument.

#directory "+compiler-libs";; let () = Hashtbl.add Toploop.directive_table "testdirective" (Toploop.Directive_string (fun s -> Printf.printf "Test directive called with argument <%s>\n" s))

If you load it in the toplevel, the directive becomes available:

$ ocaml OCaml version 4.01.0 # #use "testdirective.ml";; # #testdirective "some argument";; Test directive called with argument <some argument>

[dmbaturin]

Operator overloading in MLton

StandardML uses overloaded arithmetics operators, so its compilers support function overloading deep inside, but since it's not really a part of the language, they don't make the overloading mechanism available to the user.

MLton, however, doesn't try too hard at hiding it and it's fairly easy to figure it out by reading the source.

It doesn't mean you should be doing this in real code, but what can be abused for fun, will be abused.

We'll make a "^+" operator and make it mean addition for integers and concatenation for strings. To do it, we'll need two modules and some magic.

signature FOO = sig val ^+ : int * int -> int end structure Foo : FOO = struct val ^+ = fn (x, y) => x + y end signature BAR = sig val ^+ : string * string -> string end structure Bar : BAR = struct val ^+ = fn (x, y) => x ^ y end (* Magic begins here *) _overload ^+ : ('a * 'a -> 'a) as Foo.^+ and Bar.^+ (* Magic ends here *) infix 6 ^+ val () = print ("hello " ^+ "world\n") val () = print ((Int.toString (3 ^+ 4)) ^ "\n")

Now we need to compile it. Compiling with default options fails:

$ mlton ./test.sml Error: test.sml 17.1. _overload disallowed. compilation aborted: parseAndElaborate reported errors

We need another bit of magic:

mlton -default-ann 'allowOverload true' ./test.sml

Now it works:

$ ./test hello world 7

[dmbaturin]

Programming languages and wall sockets

Suppose you move to a new house and there're no wall sockets or switches. All you have is a bunch of wires sticking out of the walls and a reference card. As a smart person, you can sure figure it out. To switch the light on, you just need to short the wire 10A with the wire 10B. To connect your phone to your landline you just need to solder its cord to the wires 31A and 31B. Don't confuse them with 32A and 32B, that's just DC power (why it's even there?).

A better solution is to buy and install some wall sockets and switches. This way you can express it unambiguously that this thing is a 220 (or 110) AC socket, and that one is a phone socket. A nice side effect is that it also makes it physically impossible to accidentally plug your phone into a 220AC socket. Any objections?

Oh, yes, it makes it cumbersome to power your nightlight from a phone line. You don't need a landline and the nightlight can work with 50V DC just fine, why use a 220AC socket?

No electrician would find this objection reasonable. However, this attitude is common among programmers who insist that everything should be written in languages with type coercions all over. Some insist that everything should be written in languages with type coercions and manual memory management. Some are even proud of doing a lot of extra work to achieve their task.

Maybe it's because few people know that pointers and ability to run on bare metal don't always come with weak typing. Or that static type checking doesn't always come with manually written type annotations. Or that higher-order functions are not limited to interpreted languages. Or something else.

Note: I didn't touch performance on purpose: sometimes it's a valid point, sometimes it's not, and sometimes it has nothing to do with type system expressiveness because type checks can be entirely compile-time. Just a couple of fun facts specifically for proponents of low level languages: the fastest Fourier transform library is not really written in C, it's generated with an ML program. Another fun fact: I've seen a group or researchers using a numerical routine library written in a mix of Pascal and x86 assembly from i486 era, while then-widespread CPUs all had at least MMX. If it was written in pure Pascal, FreePascal would do a better job at optimizing it than they did.

[dmbaturin]

Understanding the OCaml hello world

The canonical OCaml helloworld reads

let () = print_endline "hello world"

and exact meaning of the "let () =" part is often confusing to beginners (it was once confusing to me as well). So I'm creating a reusable answer for the cases when I'm asked about it.

The print_endline part seems obvious. What may not be obvious is that print_endline does not "return nothing". It returns a value of type unit, which has only one value that is written as "()", and has type string → unit

The left hand side is more interesting. The point is that the left hand side of a let expression can be any pattern (a constant, a name, a data constructor...). This fact allows you to do neat things like deconstructing tuples and records in one move, as in

let x = (1, 2) let y, z = x (* y is bound to 1, z to 2 *)

A match can create any number of new bindings, including zero. In case expressions it doesn't look confusing at all, like in this function that makes a list with single element from (Some x) and an empty list from None:

let list_of_option x : 'a option -> 'a list = match x with Some x -> [x] | None -> []

Since let expression is pattern matching too, it may also not create any bindings, even though it's often used precisely for it. Therefore, even something like "let () = ()" is perfectly valid (it always succeeds but doesn't create bindings).

Now we can tell what exactly that helloworld is doing:

Evaluates print_endline "hello world".

...which produces a side effect and evaluates to ().

Matches () with (), match succeeds.

Does nothing else.

An alternative way to write it is

let _ = print_endline "hello world"

The problem with it is that in the absense of other cases matching something with the wildcard pattern (_) passes the type checks regardless of the type of the right hand side, so it's easy to write expressions that don't make any sense, like

let _ = print_endline

This doesn't do anything meaningful, but doesn't produce a type error either. If you matched it with (), it would not typecheck because types unit and (string → unit) are obviously not the same.

[dmbaturin]

Polymorphic curry function in SML

I was asked how to write a function that transforms a tupled function into a curried one (specifically, α × β → γ into α → β → γ).

It's a straightforward task in OCaml and Haskell, but has some pitfalls in SML.

$ sml Standard ML of New Jersey v110.74 [built: Sat Oct 6 01:32:27 2012] - fun curry f x y = f (x, y); val curry = fn : ('a * 'b -> 'c) -> 'a -> 'b -> 'c

Looks good so far. Now try to apply it to something.

- fun add (x, y) = x + y; val add = fn : int * int -> int - val add' = curry add ; val add' = fn : int -> int -> int - add' 3 4; val it = 7 : int

But when we apply it to polymorphic functions this way, interesting things happen.

- val nth = curry List.nth; stdIn:6.5-6.25 Warning: type vars not generalized because of value restriction are instantiated to dummy types (X1,X2,...) val nth = fn : ?.X1 list -> int -> ?.X1 - nth [1, 2, 3] 2; stdIn:7.1-7.16 Error: operator and operand don't agree [literal] operator domain: ?.X1 list operand: int list in expression: nth (1 :: 2 :: 3 :: nil)

The reason is that the result of applying curry to List.nth is polymorphic and within the SML approach to value restriction (that is meant to protect ref cells from changing their type) it can't be a value. OCaml uses a different approach, so you can get away with it there, but in SML you have to make it a value by wrapping it in a function (the fancy name for this trick is "η-expansion").

- val nth' = fn xs => fn x => curry List.nth xs x; val nth' = fn : 'a list -> int -> 'a - nth' [1, 2, 3] 2; val it = 3 : int

Alternatively, we could use the "fun" syntactic sugar for it:

fun nth xs x = curry List.nth xs x

Moral: polymorphism ain't easy. Or, learning another language always tells you something about those you already know.

[dmbaturin]

Object-oriented Peano arithmetic

I'm not sure what would be the best way to represent Peano arithmetic in Python (or another language without algebraic types), but I think the funniest way to do it is to represent numbers as classes with succ() class method that dynamically creates a randomly named subclass of the class it's called from. Calculating a predecessor of a number is trivial, just lookup its superclass.

import uuid # Axiom 0: every language feature can # and will be misused. # Axiom 1: Zero is a natural number class Zero(object): # Axiom 2: for every natural number N, # succ(N) is a natural number @classmethod def succ(self): # Class names don't matter but must be unique name = str(uuid.uuid4()) # By successor Peano meant a subclass, right? return type(name, (self,), {}) @classmethod def add(self, x): if self == Zero: return x else: return self.__bases__[0].add(x.succ()) @classmethod def str(self): if self == Zero: return "O" else: return "S({0})".format(self.__bases__[0].str()) if __name__ == '__main__': one = Zero.succ() two = Zero.succ().succ() three = Zero.succ().succ().succ() print("{0} + {1} = {2}".format(Zero.str(), Zero.str(), Zero.add(Zero).str())) print("{0} + {1} = {2}".format(Zero.str(), one.str(), Zero.add(one).str())) print("{0} + {1} = {2}".format(two.str(), three.str(), two.add(three).str())) print("{0} + {1} = {2}".format(three.str(), two.str(), three.add(two).str()))

As expected,

$ python ~/peano.py O + O = O O + S(O) = S(O) S(S(O)) + S(S(S(O))) = S(S(S(S(S(O))))) S(S(S(O))) + S(S(O)) = S(S(S(S(S(O)))))

[dmbaturin]

[dmbaturin]

Postcards time.

[dmbaturin]

Switching from OCaml to Standard ML

I decided to take a closer look at "the other ML", so I signed up for a course (the course is way more than just ML, you absolutely should enroll, but it's a different story).

Overall impression

Since they are conceptually similar, you can start writing in the other in several hours. For exact this reason those several hours will be very annoying though.

Even though SML is kinda less practical than OCaml (in sense of libraries and tools), I think it helped me to understand the design of both languages better.

Implementations

There are multiple SML implementations, each of them not perfect in its own way.

Standard ML of New Jersey

Old, still popular. 32-bit only, for this reason absent from some distros that prefer something that can be built natively for multiple architectures. Intepreter only.

Poly/ML

Includes both compiler and interpreter, works on 64-bit, but editor integration tools may not work with it out of the box.

MLton

Compiler only. Painfully slow. Said to be a whole program optimizing compiler, so probably is of greatest theoretical interest.

Syntax

Subtle syntax differenced is what makes switching so annoying. Here's what I wish I have known (read: looked up in the docs) before starting.

Currying

Most standard library functions are not curried. For example, List.nth is α list * int → α rather than α list → int → α. Function arguments of higher-order functions also may not be curried, for example, the argument of List.foldl is α * β → β. In general, it looks like SML programmers tend to use tuples rather than using curried functions wherever possible.

Binding

There are several binding words: val for values; fun, an alias for val rec; and let for binding groups.

val x = 10 val incall = List.map (fn x => x + 1) fun fact x = case x of 0 => 1 | x => x * fact (x-1) val rec fact' = fn 0 => 1 | x => x * fact' (x - 1)

Nested bindings are very uncommon in SML because let/in pairs may contain multiple expressions.

let val x = 10 val y = x + 2 in x * y end

Types

The word type is only for creating type aliases, while datatype is for creating new types.

Sequence

Semicolon-separated expressions do not create a sequence in the imperative sense. You need parens.

fun hello () = (print "hello"; print " world\n")

Pattern matching

Case expressions and match x with only differ in words and single vs. double arrows. The biggest difference is that you can use matching inside anonymous functions without any additional keywords.

val f = fn 0 => 1 | _ => 2

Data constructors

SML has first class constructors. Something like this will work fine:

map SOME [1,2,3] (* Gives [SOME 1, SOME 2, SOME 3] *)

[dmbaturin]

Tail recursion for dummies

Tail recursion is sometimes explained in confusing ways, even though the concept is simple. I tried to write a simple explanation.

In a nutshell: tail call means calling a function recursively and passing all intermediate results to it as arguments so keeping state between calls is not necessary..

Let's look at the classic recursive factorial function:

fun fact n = if n = 0 then 1 else n * fact (n - 1)

When we call it, it keeps calling itself with decreasing argument until it hits the base case (n = 0), then unwinds. The outermost call cannot complete without all inner calls. Inner calls only know their current argument, but they have no idea what their return value will be multiplied by. Computers have to remember way more than just calculation result to perform a function call, so every new call needs memory allocation, and that memory can't be reclaimed until the last call returns and it unwinds. There for it takes many times more memory than a non-recursive function.

In imperative style we would use a mutable variable to avoid it.

def fact(n): result = 1 while n > 0: result = result * n n = n - 1 return result

The variable "result" serves as accumulator and stores intermediate resulsts. To avoid using mutable state, we can use an additional argument as accumulator and pass intermediate calculation resulsts to the next call this way.

fun fact acc n = if n = 0 then acc else fact (acc * n) (n - 1)

Now it's organized as recursive, but all information is passed to every call. It doesn't even need to unwind really: the last call return value is the result we need. A compiler can abuse this fact and turn it into iteration when translating it to machine code. Therefore it gives us all the benefits of recursion without usual performance penalties.

By using a nested function or making the acc argument optional with default value, it can be easily made seemless so you can call it as just "fact n".

Tail call elimination needs compiler support! Do not try it in compilers that do not support it, or it will be just as bad as usual recursion.

[dmbaturin]

Limiting the number of calls for all but certain address in FreeSWITCH

I needed to limit the number of calls for everyone but certain trusted adresses. This is the solution that (apparently) worked. Depends on the "hash" module, don't forget to load it.

acl.conf.xml: <network-lists> <list name="good_addresses" default="allow"> <node type="deny" cidr="192.0.2.10/32" /> <node type="deny" cidr="192.0.2.15/32" /> </list> </network-lists> dialplan.conf.xml: <extension name="foo"> <condition field="destination_number" expression="^$(12345.*)$"> <condition field="${acl(${network_addr} good_addresses)}" expression="true"> <action application="limit" data="hash public my_trunk 10 !CALL_REJECTED" /> </condition> <action application="bridge" data="sofia/gateway/mygw/$1"/> </condition> </extension>

Where "public" in the limit statement is a randomly chosen "realm" and "my_trunk" is just as randomly chosen hash identifier.

[dmbaturin]

Oasis, ocamlbuild, menhir, and external tokens

Having to run ocamlbuild manually every time is annoying, so I decided to add oasis to the project. The project uses menhir with external tokens. And the external tokens part is what made it tricky, to my surprise.

Before oasis, I used to build it with:

ocamlbuild -use-menhir -menhir "menhir -v --external-tokens Lexer" main.native

Main module depends on Parser and Lexer, which in turn depend on Grammar, and Parser wants Lexer for its tokens.

First I wrote a pretty simple _oasis file.

Library parser Modules: Parser Path: src/ BuildTools: ocamlbuild BuildDepends: grammar, lexer CompiledObject: best Install: false Library lexer Modules: Lexer Path: src/ BuildTools: ocamlbuild BuildDepends: grammar CompiledObject: best Install: false

Then I have added this to the _tags file created by oasis:

true: use_menhir

It didn't work, however. Oasis didn't figure out the need for external tokens (well, how would it?) and thus didn't pass the external tokens menhir option to ocamlbuild.

The solution

I have added a new flag to the myocamlbuild.ml file generated by ocamlbuild and then used that flag in _tags:

myocamlbuild.ml: flag ["ocaml"; "menhir"; "extern_tokens"] & S[A"--external-tokens"; A"Lexer"]; _tags: true: use_menhir, extern_tokens

Now "ocaml setup.ml -build" doesn't complain and the executable it produces works fine. Provided I just started using oasis, the solution can be less than optimal of course.

[dmbaturin]

Smileys in OCaml

OCaml already supports ";;" and "^^" asian style smileys (expression terminator and format string concatenation respecitively), but support for user-defined operators allows you to add some missing ones.

(* Meaning assigned at random *) let (=^.^=) x y = if (x mod 10) = (y mod 10) then true else false ;; let (><) x y = if (x mod 10) <> (y mod 10) then true else false ;;

You can try those immediately in top level loop:

# 11 =^.^= 21 ;; - : bool = true # 11 >< 21 ;; - : bool = false

[dmbaturin]

Traces of DEC in IOS

When I got my hands on DEC systems (TOPS-20 and VMS), some things reminded me of IOS. Then I figured out it's actually the other way around: IOS borrowed them from DEC. Some say early IOS versions were developed on DEC machines (later then moved to Solaris and then to Linux). UNIX obviously had influence on it too though (mkdir, rmdir, cd, pwd etc.).

Here's some examples.

?-completion

IOS:

switch#? Exec commands: <1-99> Session number to resume access-enable Create a temporary Access-List entry access-template Create a temporary Access-List entry archive manage archive files cd Change current directory [SNIP] switch# show interfaces FastEthernet ? <0-0> FastEthernet interface number

TOPS-20:

@? Command, one of the following: ACCESS ADVISE APPEND ARCHIVE ASSIGN ATTACH BACKSPACE BLANK BREAK BUILD CANCEL CD CLOSE COMPILE CONNECT CONTINUE COPY CREATE CREF CSAVE DAYTIME DDT DEASSIGN DEBUG DECLARE [SNIP] or system program name @type ? FILE NAME @daytime ? Confirm with carriage return @talk ? User name or terminal number

TOPS-20, apparently, was the first system to have this type of completion. Note that it even had top-level completion for built-in commands. Oddly enough, there is no Tab-completion for commands and file named.

Interesting that OpenVMS still doesn't have any type of completion, even in the most recent versions, and unlike TOPS-20 it's still supported and gets updates.

systat

Most people (including me) probably use "show users" instead, but there's a DEC-inspired alias for it.

IOS:

switch#systat Line User Host(s) Idle Location * 2 vty 1 dmbaturin idle 00:00:00

TOPS-20:

@systat Thu 26-Jun-2014 17:16:47 Up 5794:02:31!!!!! 1+9 Jobs Load av 0.02 0.02 0.02 No operator in attendance System is remedial Job Line Program User Origin 10* 44 SYSTAT DMBATURIN 46.xxx.xxx.210(TCP) 1 13 OPR OPERATOR 2 DET SYSJB1 OPERATOR 3 14 RESOLV OPERATOR 4 15 NETSRV OPERATOR 5 16 SMTJFN OPERATOR 6 17 MMAILR OPERATOR 7 20 IMAPSV OPERATOR 8 21 FTS OPERATOR 9 22 WEBSRV OPERATOR

Ctrl-W behaviour

This is hard to show with text (video could help perhaps). In UNIX shells, ^W deletes everything to the nearest whitespace character. In IOS it deletes everything to the nearest delimiter, whether it's whitespace, a dor, or a slash. This is the same to the TOPS-20 shell behaviour.

Misc

dir, delete, and rename are probably also from there (DOS borrowed them from DEC too).