## Friday, March 23, 2007

### 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.

## Sunday, March 18, 2007

### 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.

And the grammar to use with fsyacc.

Module

{

// 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

%tokenID

%tokenLIT

%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()

## Sunday, March 11, 2007

### 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())

## Friday, March 9, 2007

### 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.

Be sure to read Oleg's comments about it.

## Wednesday, March 7, 2007

### EOPL - 2.3.4 - Exercise 2.25

Using the data type definitions from the previous exercise, it's easy to define the necessary additional operations and then complete the definition of the unification function.

The occurs check is necessary, of course, to avoid infinity. I won't say more than that, to force people that arrive here looking for solutions to EOPL's exercises to think a little about it, at least.

And this concludes Chapter 2.

let is_var_term t =

match t with Id _ -> true | _ -> false

let unit_subst i t =

extend_subst i t (empty_subst ())

let rec compose_substs s1 s2 =

match s1 with

EmptySub -> s2

| ExtendedSub (i, t, s) -> ExtendedSub (i, t, compose_substs s s2)

let rec unify_term t u =

match t with

Id tid -> if (is_var_term u) ||

(not (List.mem tid (term_all_ids u))) then

Some (unit_subst tid u)

else

None

| _ -> match u with

Id _ -> unify_term u t

| Constant udat ->

(match t with

Constant tdat when tdat = udat -> Some (empty_subst ())

| _ -> None)

| App us -> (match t with

App ts -> unify_terms ts us

| _ -> None)

and unify_terms ts us =

match ts, us with

[], [] -> Some (empty_subst ())

| ([], _) -> None

| (_, []) -> None

| (t :: ts', u :: us') ->

let subst_car = unify_term t u in

match subst_car with

None -> None

| Some s -> let new_ts = subst_in_terms ts' s in

let new_us = subst_in_terms us' s in

let subst_cdr = unify_terms new_ts new_us in

match subst_cdr with

None -> None

| Some s' -> Some (compose_substs s s')

The occurs check is necessary, of course, to avoid infinity. I won't say more than that, to force people that arrive here looking for solutions to EOPL's exercises to think a little about it, at least.

And this concludes Chapter 2.

### EOPL - 2.3.4 - Exercise 2.24

This exercise asks for an implementation of substitutions on terms, the terms being defined by a previous exercise (2.13). In F#, they are thus defined:

Function

With the substitution data type completed, we can write a substitution function without any difficulties.

I guess

type Value = Integer of int | String of string

type Term = Id of string | Constant of Value | App of Term list

let rec term_all_ids t =

match t with

Id s -> [s]

| Constant _ -> []

| App tl -> List.concat (List.map term_all_ids tl)

Function

`term_all_ids`

gets all identifiers from a term, also part of exercise 2.13. Then for the part specific to exercise 2.24, which are substitutions. I chose to use an abstract syntax tree representation, because it is more convenient in F#. Using the definition, it was easy to write the operations on substitutions.

type Subst = EmptySub | ExtendedSub of string * Term * Subst

let empty_subst () =

EmptySub

let extend_subst i t s =

ExtendedSub (i, t, s)

let rec apply_subst s i =

match s with

EmptySub -> Id i

| ExtendedSub (i', t, s') when i = i' -> t

| ExtendedSub (_, _, s') -> apply_subst s' i

With the substitution data type completed, we can write a substitution function without any difficulties.

let rec subst_in_term s t =

match t with

Id i -> apply_subst s i

| Constant _ -> t

| App tl -> App (List.map (subst_in_term s) tl)

let subst_in_terms lt s =

List.map (subst_in_term s) lt

I guess

`subst_in_terms`

might have been intended as a little more difficult to write. I don't know. In any case, it's just a `map`

.
## Tuesday, March 6, 2007

### EOPL - 2.3.4 - Alternative Representation

A simple representation of environments as a list of pairs

`(syms, vals)`

where `syms`

is a list of symbols and `vals`

is a list of values positionally associated with the symbols.

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

### EOPL - 2.3.3 - Exercise 2.20

It's simple to add new operations when the data is represented as an abstract syntax tree. Here's the operation

`has_association`

for stacks as defined in the previous exercise:

// Exercise 2.20

let rec has_association env sym =

match env with

EmptyEnv -> false

| ExtendedEnv (syms, vals, env') -> (List.mem sym syms) ||

(has_association env' sym)

### EOPL - 2.3.3 - Exercise 2.19

Another simple exercise.

// Exercise 2.19

type 'a Stack = EmptyStack | ExtendedStack of 'a * 'a Stack

let empty_stack () =

EmptyStack

let push elt stk =

ExtendedStack (elt, stk)

let pop stk =

match stk with

EmptyStack -> failwith "Stack empty"

| ExtendedStack (_, s) -> s

let top stk =

match stk with

EmptyStack -> failwith "Stack empty"

| ExtendedStack (e, _) -> e

let is_stack_empty stk =

stk = EmptyStack

### EOPL - Section 2.3.3

The abstract syntax tree representation for environments is quite straightforward in F#; it is shown below.

type Value = Integer of int | String of string

type Environment = EmptyEnv

| ExtendedEnv of string list *

Value list *

Environment

// helper function

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 () =

EmptyEnv

let extend_env syms vals env =

ExtendedEnv (syms, vals, env)

let rec apply_env env sym =

match env with

EmptyEnv -> failwith (sprintf "No binding for %s" sym)

| ExtendedEnv (syms, vals, env') ->

match list_find_position sym syms with

None -> apply_env env' sym

| Some i -> List.nth vals i

## Monday, March 5, 2007

### EOPL - 2.3.2 - Exercise 2.16

Easy one, in two versions.

Version 1

Version 2

Version 2 was obtained by observing similarities in Version 1. The idea appeared in previous examples: pattern guards do not always lead to shorter code.

Version 1

let rec list_find_last_position sym los =

match los with

[] -> None

| (s :: los') when s = sym ->

(match list_find_last_position sym los' with

None -> Some 0

| Some i -> Some (i + 1))

| (s :: los') ->

(match list_find_last_position sym los' with

None -> None

| Some i -> Some (i + 1))

Version 2

let rec list_find_last_position sym los =

match los with

[] -> None

| (s :: los') ->

match list_find_last_position sym los' with

None -> if s = sym then Some 0 else None

| Some i -> Some (i + 1)

Version 2 was obtained by observing similarities in Version 1. The idea appeared in previous examples: pattern guards do not always lead to shorter code.

### EOPL - 2.3.2 - Exercise 2.15

I solved this exercise in quite a "lispy" way, so it's a bit alien in F#. It works, but in a quite awkward way. The idea was to maintain the stack as a pair containing the current top element and the old stack, and this means that, in F#, each operation that adds or removes elements produces a stack with a different type than the original. An interesting consequence of this is that the stack size is reflected in its type, so that we could define functions that work on "stacks of size 3" or so on. Who needs dependent types? :)

So here's the code. It first defines a type synonym to ease working with stacks, and then the functions that implement basic operations.

And it is used like this: you must assign a type for the

Then you can push elements into

If you pop elements, the types get back to what they were, obviously. A funny side-effect of this strange definition is that

There must be a more type-friendly implementation of stacks using a procedural representation, but I decided to leave it for now and publish this solution because it is quite interesting by itself (although almost unusable in real code).

So here's the code. It first defines a type synonym to ease working with stacks, and then the functions that implement basic operations.

type 'a stack = (unit -> 'a) * (unit -> bool)

let empty_stack () =

let top () = failwith "The stack is empty, no top element" in

let is_empty_stack () = true in

(top, is_empty_stack)

let push elt stk =

let top () = (elt, stk) in

let is_empty_stack () = false in

(top, is_empty_stack)

let pop stk =

let oldstk : 'a stack = snd ((fst stk) ()) in

let top = fst oldstk in

let is_empty_stack = snd oldstk in

(top, is_empty_stack)

let is_empty_stack stk =

let empty = snd stk in empty ()

let top stk =

let t = fst stk in fst (t ())

And it is used like this: you must assign a type for the

`empty_stack`

call, otherwise you are nagged by the value restriction again. That's where the type synonym comes in handy:

> let (x : int stack) = (empty_stack());;

val x : int stack

Then you can push elements into

`x`

. Note how the type of the result is different from `int stack`

, even considering type synonyms.

> push 3 x;;

val it : (unit -> int * int stack) * (unit -> bool)

= (<fun:push@173>, <fun:push@174>)

> push 4 (push 3 x);;

val it : (unit -> int *

((unit -> int * int stack) * (unit -> bool))) *

(unit -> bool)

= (<fun:push@173>, <fun:push@174>)

>

If you pop elements, the types get back to what they were, obviously. A funny side-effect of this strange definition is that

`top`

and `pop`

don't work on empty stacks because of type-checking, not any run-time checking -- so that the `failwith`

in the definition of `empty_stack`

will never be executed. Empty stacks have actually a different type. There must be a more type-friendly implementation of stacks using a procedural representation, but I decided to leave it for now and publish this solution because it is quite interesting by itself (although almost unusable in real code).

### EOPL - 2.3.2 - Procedural Representation

Section 2.3 is about strategies for representing data types. In section 2.3.1 an abstract interface for environments is presented, and then in section 2.3.2, Figure 2.3 shows a procedural implementation for the environment interface. Translated into F#, Figure 2.3 would be like the following:

In this case, function

let find_index a lst =

let rec loop l =

match l with

[] -> raise Not_found

| (x :: l') when x = a -> List.length l'

| (x :: l') -> loop l' in

loop (List.rev lst)

let list_find_position sym los =

if List.mem sym los then

Some (find_index sym los)

else

None

let empty_env () =

fun sym -> failwith (sprintf "No binding for %s" sym)

let apply_env env sym =

env sym

let extend_env syms vals env =

fun sym -> match list_find_position sym syms with

None -> apply_env env sym

| Some i -> List.nth vals i

In this case, function

`find_list_position`

is redundant, because `find_index`

does not take a predicate, so it's less generic than the version in the book. It shouldn't be a problem at this point, though. Function `find_index`

reverses the list, we can write a version that does without that:

let rec find_index2 a lst =

match lst with

[] -> raise Not_found

| (x :: lst') when x = a -> 0

| (x :: lst') -> 1 + find_index2 a lst'

Subscribe to:
Posts (Atom)