Functional programming in Wall Street

The latest issue of Monad.Reader (a electronic magazine about Haskell) includes an interesting article about Jane Street Capital (a Wall Street trading company) and its use of OCaml. The author points good and bad things about the language; these aren't new, in fact the things pointed are well-known by the community, but it's good to hear them from someone using the language in a production setting.

Anyway, it's a case of large-scale adoption -- in the sense of using it as the main language for all development -- of a functional programming language, which is still rare, unfortunately.

One Language to Rule Them All

A discussion on LtU about the Next Big language, the next Java or something like it. Links to the post by Steve Yegge too. Once again Scala is mentioned as a fine language that anyone needing to develop for the JVM should try.

I don't believe Scala will be the next big language, but it really is fine. At the moment I'm finishing implementation of a simple distributed system written in Scala. It had to run on the JVM to communicate with other Java programs. It was a breeze to do, thanks to the Actors library. Scala's type system is quite interesting too, I plan on giving more attention to it when I have the time.

EOPL - 3.2 - Exercise 3.5

Exercise 3.5 asks you to add a print primitive to the language, which prints its argument and returns the value 1. The relevant changes are simple. In module Eopl_3 only the definition of type Primitive and function apply_primitive are different:

// in eopl_3.fs (module Eopl_3)
type Primitive = AddPrim | SubtractPrim | MultPrim | IncrPrim 
               | DecrPrim | PrintPrim

let apply_primitive prim args = 
    match (prim, args) with
      (AddPrim, [a; b]) -> a + b
    | (SubtractPrim, [a; b]) -> a - b
    | (MultPrim, [a; b]) -> a * b
    | (IncrPrim, [a]) -> a + 1
    | (DecrPrim, [a]) -> a - 1
    | (PrintPrim, [a]) -> (print_endline (string_of_int a); 1)
    | _ -> failwith "Incorrect argument list for primitive" 

In the lexer specification a token for the print primitive is added:

rule token = parse
| whitespace { token lexbuf }
| '%' [^ '\n']* { token lexbuf } 
| newline       { record_newline lexbuf; token lexbuf }
| "+"         { PLUS }
| "-"         { MINUS }
| "*"  { MULT }
| "("           { LPAREN }
| ")"         { RPAREN }
| ","           { COMMA  }
| "add1" { INCR }
| "sub1" { DECR }
| "print"       { PRINT }
| id         { ID(lexeme lexbuf) }
| ['-']?digit+  { LIT (Int32.Parse(lexeme lexbuf)) }
| eof   { EOF }

And, in the parser, this token must be declared and dealt with:

%token PRINT INCR DECR LPAREN RPAREN PLUS MINUS MULT COMMA EOF

Prim: PLUS                        { AddPrim }
    | MINUS                       { SubtractPrim }
    | MULT                        { MultPrim }
    | INCR                        { IncrPrim }
    | DECR                        { DecrPrim }
    | PRINT                       { PrintPrim }

The remaining parts of these three files are the same as the previous two posts.

Scala web programming

A post on Lambda the Ultimate pointing to this post on David Pollak's blog. In a comment on the Lambda thread, he writes some points about what makes Scala a good language for web programming, comparing with Java and Ruby (with Rails). Having used all three, he gets to the conclusion that Scala has the best of the other two.

EOPL - 3.2 - Front-end for the first interpreter

The previous post showed the code for the interpreter, working on an abstract syntax representation of the interpreted programs. In section 3.2 a front-end is presented to permit working with a concrete syntax. The book uses SLLGEN, a tool developed by the PLT Scheme group, to generate lexers and parsers. I used fslex and fsyacc, the standard tools of F# for such purposes. Here's the lexical specification.

{
// eopl1_lex.fsl
//
// Lexical specification for the first interpreter 
// in EOPL (Essentials of Programming Languages)

open System
open Eopl1_par
open Lexing

let record_newline (lexbuf : lexbuf) = 
    lexbuf.EndPos <- lexbuf.EndPos.AsNewLinePos()

}

// These are some regular expression definitions
let digit = ['0'-'9']
let id = ['a'-'z'] ['a'-'z' '0'-'9']*
let whitespace = [' ' '\t' ]
let newline = ('\n' | '\r' '\n')

rule token = parse
| whitespace { token lexbuf }
| '%' [^ '\n']* { token lexbuf } 
| newline       { record_newline lexbuf; token lexbuf }
| "+"         { PLUS }
| "-"         { MINUS }
| "*"  { MULT }
| "("           { LPAREN }
| ")"         { RPAREN }
| ","           { COMMA  }
| "add1" { INCR }
| "sub1" { DECR }
| id         { ID(lexeme lexbuf) }
| ['-']?digit+  { LIT (Int32.Parse(lexeme lexbuf)) }
| eof   { EOF }

And the grammar to use with fsyacc.

// eopl1_par.fsy 
// Parser for the first interpreter 
// in EOPL (Essentials of Programming Languages)

%{

open Eopl_3

%}

%start start

// terminal symbols
%token  ID
%token  LIT
%token INCR DECR LPAREN RPAREN PLUS MINUS MULT COMMA EOF

%type < Eopl_3.Program > start

%%

start: Prog {  $1 }

Prog: Expr                        { Exp ($1)   }

Expr: ID                          { VarExp($1) }
    | LIT                         { LitExp($1) }
    | Prim LPAREN ArgList RPAREN  { PrimAppExp ($1, List.rev $3) }

Prim: PLUS                        { AddPrim }
    | MINUS                       { SubtractPrim }
    | MULT                        { MultPrim }
    | INCR                        { IncrPrim }
    | DECR                        { DecrPrim }
    
ArgList: Expr                     { [$1] }
       | ArgList COMMA Expr       { $3 :: $1 }

Module Eopl_3 contains all the code from the previous post, including a definition of the abstract syntax. Both specifications above were adapted from an example included in the distribution. Now we only need to run these specifications into fslex and fsyacc, and write a driver for the interpreter, a simple read-eval-print loop. Here it is.

// eopl1_main.fs
//
// Driver for the first interpreter in EOPL
// (Essentials of Programming Languages)

#light 

open Eopl_3
open Eopl1_par

open Lexing

let parse str = 
    let lexbuf = Lexing.from_string str
    let prog = 
        try
            Some (Eopl1_par.start Eopl1_lex.token lexbuf)
        with e -> 
            let pos = lexbuf.EndPos
            printf "error near line %d, character %d\n%s\n" 
                   pos.pos_cnum 
                   (pos.pos_cnum - pos.pos_bol) (e.ToString());
            None
    prog
            
let rec read_eval_print prompt = 
    let _ = print_string prompt 
    let line = read_line ()
    match line with
      "#quit" -> ()
    | _ -> match parse line with
             None -> read_eval_print prompt
           | Some p -> let v = Eopl_3.eval_program p in 
                       (print_endline (string_of_int v); 
                        read_eval_print prompt)
           
let main() = 
    read_eval_print "--> " 
    
do main()

EOPL - Section 3.1

This is the first interpreter from Chapter 3, shown in Section 3.1. It needs an implementation of environments, I chose the simplest one and attached it before the code for the interpreter.

// implementation of environments 
// (represented as lists of pairs; the first in pair is 
//  a list of symbols, the second is a list of associated values)
let list_find_position a lst = 
    let rec loop l = 
        match l with
          [] -> None
        | (x :: l') when x = a -> Some (List.length l')
        | (x :: l') -> loop l' in
    loop (List.rev lst)

let empty_env () = 
    []
    
let extend_env syms vals env =
    (syms, vals) :: env
    
let rec apply_env env sym = 
    match env with
      [] -> failwith (sprintf "No binding for %s" sym)
    | (syms, vals) :: env' -> 
        match list_find_position sym syms with 
          None -> apply_env env' sym
        | Some i -> List.nth vals i
        
// types for primitives, expressions and programs
type Primitive = AddPrim | SubtractPrim | MultPrim | IncrPrim | DecrPrim
type Expression = LitExp of int | VarExp of string 
                | PrimAppExp of (Primitive * Expression list)
type Program = Exp of Expression

let apply_primitive prim args = 
    match (prim, args) with
      (AddPrim, [a; b]) -> a + b
    | (SubtractPrim, [a; b]) -> a - b
    | (MultPrim, [a; b]) -> a * b
    | (IncrPrim, [a]) -> a + 1
    | (DecrPrim, [a]) -> a - 1
    | _ -> failwith "Incorrect argument list for primitive" 

let init_env () = 
    extend_env ["i"; "v"; "x"] [1; 5; 10] (empty_env ())
    
let rec eval_expression exp env = 
    match exp with
      LitExp datum -> datum
    | VarExp id -> apply_env env id
    | PrimAppExp (prim, rands) -> let args = eval_rands rands env in 
                                  apply_primitive prim args
and eval_rands rands env = 
    List.map (eval_rand env) rands
and eval_rand env rand = 
    eval_expression rand env

let eval_program pgm = 
    match pgm with
      Exp body -> eval_expression body (init_env()) 

Scheme programming in ML

As I'm constantly bumping into typing issues when converting EOPL's examples and exercises from Scheme to F# (a ML language), I found this code/article by Oleg Kyseliov relevant. It embeds a Scheme-like language into OCaml, using variant types, and defines functions used in Scheme. The scheme.ml file is quite interesting for going all the way with the Scheme conversion, but the use of variant types to capture the need to work with different types in the same context is known to every ML programmer. I even did it sometimes in the EOPL programs.

Be sure to read Oleg's comments about it.