Code Miscellany

Brute force SAT solver in Haskell

2008-03-15T00:02:00.000-07:00

Sometimes people get wrong impressions after a Theory of Computation course. A "hard" problem there is not necessarily hard to solve with a program, just hard to solve well in realistic circumstances. Take SAT, for example, the boolean satisfiability problem for propositional logic. It's a classic example of a NP-complete problem, whose naive solution -- generate all possible combinations of truth-values for each atomic proposition and then calculate the value for the whole formula -- is clearly exponential. But this naive solution is very easy to write. For example, in Haskell we get something like the following:


import Data.List  ( nub )
import Data.Maybe ( fromJust )

data Formula = Var String | And Formula Formula |
              Or Formula Formula | Not Formula

getVarsDup (Var v)     = [v]
getVarsDup (And f1 f2) = (getVarsDup f1) ++ (getVarsDup f2)
getVarsDup (Or f1 f2)  = (getVarsDup f1) ++ (getVarsDup f2)
getVarsDup (Not f)     = getVarsDup f

genValues n = genAux $ [replicate n True]
   where genAux (v:vs)     = if not $ or $ v then v:vs
                             else genAux ((next v) : v : vs)
         next (True : ts)  = (False : ts)
         next (False : ts) = (True : (next ts))

solveFormula (Var v) env     = fromJust $ lookup v env
solveFormula (And f1 f2) env = (solveFormula f1 env) &&
                              (solveFormula f2 env)
solveFormula (Or f1 f2) env  = (solveFormula f1 env) ||
                              (solveFormula f2 env)
solveFormula (Not f) env     = not $ solveFormula f env

allSolutions f = map (solveFormula f) (map (zip vars) vals)
   where vars = nub $ getVarsDup f
         vals = genValues (length vars)

-- solve the SAT problem
sat f = or $ allSolutions f

-- pointfree!
sat2 = or . allSolutions

The idea is the same as creating a truth-table for the formula and then looking for a T in the possible values for it. Function genValues generates all possible values for the atomic propositions, and this is fed into solveFormula. It would be very easy to alter the code to output the complete truth-table; I leave it as an exercise to the reader. Another standard exercise in logic textbooks is to prove that if a formula contains n atomic propositions, the truth-table will have 2^n lines. Thus, generating all combinations is easily seen to be exponential in time.

But the fact that it is hard for the computer to solve doesn't mean that it's hard for someone to write a (naive) program to solve it. In practical applications, like circuit design, we may need to solve SAT for thousands of variables, and the naive algorithm would not work. For this we must use a more clever technique, like Binary Decision Diagrams. They're not that hard to code either; the book Expert F# includes an example of BDDs in F#.

Tumbalalaika

2008-03-05T08:40:00.000-08:00

It's probably too late to be hip because of this now, but I have created a tumblelog. It's easier to post there, so it should be updated more often than this blog. I'll probably post a good number of links in common with anarchaia.

Functional programming in the mainstream

2008-01-23T07:05:00.000-08:00

Here is a bit from Ted Neward, commenting on the outcome of his predictions for 2007:

THEN: Languages: Interest in functional-object hybrid languages will grow. Scala, Jaskell, F#, and others not-yet-invented will start to capture developers' attention, particularly when they hear the part about functional languages being easier to use in multi-core systems because it encourages immutable objects and discourages side effects (meaning we don't have to worry nearly so much about writing thread-safe code). NOW: It grew, and it continues to grow. New languages in general are being released (see Clojure, Jaskell, dynalang, and others), and lots of them are incorporating functional language concepts. If you've never programmed in Haskell, now's a good time to learn, because those concepts and syntax are fast making their way towards you...

Book review: Expert F#

2008-01-17T13:54:00.000-08:00

Expert F#, by Don Syme, Adam Granicz and Antonio Cisternino, Apress

When a new programming language arrives and manages to make an impact, books about it will certainly appear. However, most often the books will be geared to beginners, to people that is either not very experienced in programming or in the programming paradigms embodied by the language. For a experienced programmer, these books stop right when the fun would begin: the advanced stuff, the corners, the details are left out.

Expert F#, as suggested by its title, is not like this: it is aimed at more experienced programmers. The book will not teach you, for instance, what is functional programming or hammer to your head the best ways to use lists, an ubiquitous data structure in functional languages. But it explains how the things work in F#, so that programmers already familiar with other functional languages will have no trouble picking it up. F# also has object-oriented capabilities, which are explained in a chapter, without however going much deep into OO concepts; the book is about the language, not the paradigms.

And it does this well. Roughly half of the book is about the language itself, the other half are examples of applications and how to use some important libraries. As I was already familiar with OCaml and Haskell, I mostly skimmed through chapters 1 to 4, reading more closely from chapters 5 (generic types) and 6 (how objects fit into F#). From chapter 7 (encapsulating and packaging your code) on, the book starts to get really interesting; the next one is about common techniques, and chapter 9 is the best in the first part, explaining language-oriented programming, an area where functional languages really shine.

There are mandatory chapters about Windows Forms (11), Web programming (14) using .NET and data access, including how to use LINQ in F#, but I really liked chapters 12 (working with symbolic representations), and 13 (concurrency and asynchronous workflows). The former includes two cool examples: a symbolic differentiator and a verifier for logic circuits based on BDDs (Binary Decision Diagrams). There are other important and advanced chapters treating topics like interoperation with C and COM, debugging and testing F# programs, and F# library design.

All in all a very good book about the best current functional language to use in the Windows platform. I have two minor quibbles about it, though: the first few chapters about the language really could be made more interesting (although it didn't affect me much, as I only skimmed them) and some of the more exciting new features of F# could be explained in more detail. Specifically, workflows and active patterns. They are quite recent additions to the language, however, and there is some additional material promised to feature in the book's site.

Anyway, I will keep this book nearby when programming in F#. It is this kind of book that you'd want to keep around, even after learning the language.

Do it yourself: Visual F# Express 2008

2007-12-11T09:49:00.001-08:00

As noted in this post, if you want Visual Studio just to have an IDE to work with F#, you can get it for free. Now with Visual Studio 2008, Microsoft has released a bare-bones VS, without any language, that can be used with language extensions and plugins, as is the case of F#. This bare-bones VS is called Visual Studio 2008 Shell (integrated mode).

After downloading and installing VS 2008 Shell (it takes a lot of unpacking and installing), you can install F# 1.9.3.7 and voilà, you have a pretty good F# IDE in your box, without having to shell out any cash.

I tested it with F# version 1.9.3.7 in a machine running Windows XP SP2 and no previous version of Visual Studio installed, and it worked. I even compiled and ran some test projects. If it doesn't work at first, take a look at the original post.

Further news on World Domination

2007-10-17T12:17:00.000-07:00

Don Syme blogs about taking F# forward, which means, it seems, that F# will leave the confines of MS Research and be fully integrated into Visual Studio, as a product. If this is right, it's a great step for F# as a language and for functional programming in general, as we'll have a first-class IDE, by a major vendor, shipping with a functional programming language.

F# is already a great language to use, so I look forward to it getting still greater. The next step for Microsoft is to embrace Visual Haskell and fully integrate Haskell in Visual Studio too :)

Review: OCaml for Scientists

2007-09-24T19:53:00.000-07:00

When we think about what makes a programming book good, what separates a classic from a run-of-the-mill for-dummies-learn-in-X-days book, it's not hard to get to the conclusion that the examples are an important piece of what we perceive as quality. I would say that this is even more so for books on programming languages: K&R had great examples; Practical Common Lisp has great examples that are now being copied by many authors; the list could go on.

So it was not that surprising to discover that one of the reasons of all the praise received by Dr. Jon Harrop's book OCaml for Scientists is its set of examples. There are even two entire chapters devoted to examples, the first for simple and the second for more significative ones. They are really good: well-chosen, interesting and well-written. Most of them have a scientific flavor, in keeping with the book's title, but to me this is a plus. Also, I don't recall seeing wavelet transforms as examples in a programming language book before; originality also counts.

The book's title is accurate: it is a book about OCaml primarily targeted for scientific applications. But most of the topics covered are really useful to anyone wanting to learn the OCaml language. Of all the ten chapters, I would say only one -- Chapter 4, Numerical Analysis -- is mostly directed to scientists. Well, probably game programmers too. And programmers of computer graphics applications, and anyone using floating-point arithmetic. Anyway, the other chapters that have somewhat of a scientific bent are: Chapter 6, Visualization, which is really about how to use OpenGL and GLUT in OCaml, which is quite cool in itself; and Chapter 10, Complete Examples, but each example is well explained and can be (mostly) understood without previous knowledge.

To give some idea about the book's contents, here is a quick tour: Chapter 1 is a quick introduction, covering most important concepts of the core language. Chapter 2 is about how to structure bigger programs, including function nesting, modules, objects, and how to manage dependencies and compilation. Chapter 3 is a very interesting chapter on data structures in OCaml, beginning with a section on algorithmic complexity; it covers the more important containers provided in the library, and also how to implement and work with trees. Chapter 4 is the one about numerical analysis, covering the basics about doing calculations with limited-precision numbers, and how to use more precise forms of arithmetic. Chapter 5 tackles input and output in OCaml, going beyond the call of duty to present the lexer generator (ocamllex) and parser generator (ocamlyacc) in the OCaml toolset. Chapter 6 is about visualization with OpenGL and GLUT, Chapter 7 is a very good one about optimization, and Chapter 8 a very useful one about libraries. The final two chapters have examples, and don't be fooled by the title of Chapter 9, Simple Examples. There is good stuff there. There are also two appendices, about more advanced features and troubleshooting advice respectivelly.

To be fair, the book has some small weaknesses that, in the end, are not that important, if you consider its target audience and what's common OCaml style. One is the treatment of objects: it is very cursory, and one of the examples (about real and complex numbers) could easily be considered a bad case of OO design. Considering most OCaml programmers rarely use objects, this is not so troubling. The other weakness I'd like to cite is more of a wish from my part: I wish there were more about advanced topics, especially functors (only very lightly touched in Appendix A).

But it's really a very good book about OCaml, both for beginners and for people with some previous exposure to it. It has advice on good programming style throughout, great examples (shown in color, properly syntax-highlighted), and distilled practical experience on some important topics (optimization, using libraries) that is hard to get elsewhere. It is remarkable not only in the very restricted universe of OCaml books, but as a programming book, in general: it stands between the best I've seen.

Monads in OCaml

2007-08-21T10:14:00.000-07:00

So, there. Someone who has never programmed in Haskell probably never encountered the idea of monads -- unless it is someone who works in semantics and has read Moggi's works; but I digress. An interesting way to tackle the idea of monads is to look at them outside of Haskell, and see how it works in other languages. Often, other languages don't have what it takes to express the concept of a monad in its full generality, but specific monads can always be implemented. In this regard, there's this page by oleg, and there's this other one about monads in Ruby. I remember seeing somewhere a page that compiled monad implementations in various languages, but I can't seem to find it now.

Anyhow, Brian Hurt has written a very nice tutorial about monads in OCaml. It uses the module system and functors (see comments) to define a reasonably general monad concept in OCaml. It's a good read.

Towards Global Domination

2007-08-07T18:57:00.000-07:00

If you haven't yet seen them or heard about them somewhere else, it seems that the videos of Simon Peyton-Jones' talks at OSCON are quite a hit.

And people still look at me funny when I say that functional programming is going to take over the world.

Battle of the OCaml plugins for Eclipse

2007-07-13T13:24:00.000-07:00

A new OCaml plugin for Eclipse, called OcaIDE, has just been announced. Apparently, it has been under development for a long time. It seems to be quite complete in features, although I didn't try it yet. The question is that this is the third OCaml plugin being developed currently; there's ODT, about which I talked in a earlier post, and another one being developed as one of the OCaml projects in the Google Summer of Code. The competition is good in some ways, but on the other hand the resulting fragmentation can be a problem to a small community like that of OCaml. It would be best if the teams managed to combine their efforts in some way. Let's see how this plays out.

Speaking of collaboration, there's mention on OcaIDE's site about a free-software license, but the source code doesn't seem to be available.

UPDATE: As someone pointed in the comments, the source is available together with the plugin. See here.

Review: Practical OCaml

2007-07-05T18:23:00.000-07:00

Executive summary: this is not Practical Common Lisp for OCaml. It's ambitious but disappointing. However, it's not so bad as it seems at first sight.

OCaml is a sexy language that combines the expressiveness and terseness of scripting languages with the static type checking and performance of languages like C++ and Java. A book may be a good investment to learn a new language, and this is one of the few books available on the language. How does it fare?

This book has received very harsh criticism overall, and it mostly deserves it; it is somewhat of a mess. But it is not uniformly bad: some chapters are very bad, others are acceptable or interesting, depending on your background. The problem seems to be that the worst chapters come first; although it shows signs of bad editing throughout, the first few chapters are especially bad. And I mean really bad: bad text, bad editing, bad examples, lots of senseless repetition, conceptual errors, using language features not yet introduced (and that go unexplained), the list goes on. Later chapters are considerably less irritating.

Clearly inspired by Peter Seibel's terrific book Practical Common Lisp, the chapters on this one are divided in two types: the ones that explain the language, and the "Practical" ones, containing extended examples. This is a great idea, and even badly executed as it may be in Practical OCaml, it still results in interesting chapters. Actually, the Practical chapters are overall better than the language ones; from them, a reader can get a real sense of using OCaml in simple but realistic projects, integrating many different libraries and tools, some of them not contained in the standard OCaml distribution. Still, the code in these chapters can be criticized for their style. For one thing, I think the author uses classes and other OO features much more often than they appear on real OCaml programs. Nonetheless, an experienced programmer could get a lot of interesting pointers from these chapters, by knowing what to salvage and what not to replicate from the code.

But the rest of the book, the OCaml chapters, are in really bad shape. They don't explain things very well, and fails miserably at the more difficult aspects of the language. The chapter on modules and functors is so bad as to be almost useless; don't try to learn about functors from this book. Camlp4, the nifty tool for metaprogramming and extension, is other subject with a bad treatment. The chapter on Threads could be improved a lot, but it still gives a general idea of how multithreaded programming in OCaml is. Again, for experienced developers, it should provide pointers for further study.

If experienced developers can get something from this book, novice ones should stay away from it. Not only is the text confusing, but there are a lot of glaring conceptual errors. Maybe some errors are to be expected from a trade book, from an author that is not an academic, but there
are things that are completely confusing. For example, this is the definition of type (page 24): "A type is a thing (or a collection of things) or value." And there is a lot more like this, unfortunately.

Overall, it has interesting parts, but surely not enough to make worth the full cover price. For experienced programmers and people already familiar with other typed functional programming languages (Haskell, F#, SML, etc), the book could serve as an initial guide for OCaml programming, but there are better alternatives around.

F# Performance

2007-06-17T10:54:00.000-07:00

There's a comparison of F# versus IronPython in Robert Pickering's blog. The results show that F# has roughly the same level of conciseness and terseness of Python, while being close in performance to C#. This is a .NET-based comparison, but it would be interesting to compare F# with CPython to see where it stands. If we are to believe this discussion on the python-dev mailing list, it seems that IronPython's performance must be comparable to CPython's, so there we have it: .NET or not, F# strikes an interesting balance in the expressiveness versus performance trade-offs.

This is also my personal experience with OCaml: performance roughly comparable to C/C++, but expressive and concise like scripting languages. It is this interesting position in the expressiveness x performance curve that makes both F# and OCaml very worthwhile languages to learn and use today.

The EOPL in F# wiki

2007-06-09T17:02:00.000-07:00

I've started moving the content for the "EOPL in F#" translation to a wiki. Unfortunately, I have also been insanely busy as of late, so there's only the beginning there. However, as I'll have more free time from now on, I intend to catch up with what's already here and then start posting more sections that I already translated. I also noticed I never posted some parts because I forgot to, so it will be added to the wiki as well. Anyway, here is the link:

EOPL in F# Wiki

OCaml with Eclipse

2007-06-01T13:28:00.000-07:00

The primary editor on which to write OCaml code has always been Emacs. This tends to be a problem for users on Windows, that mostly aren't familiar with the editor. And of course there are many people that use unix platforms and don't like Emacs.

A good alternative is Eclipse, which has very good plugins for Java programming, and can be extended to handle other languages. ODT, a plugin for OCaml development in Eclipse, is being actively developed by Emmanuel Dieul. Actually there's another plugin in development by someone under the Google Summer of Code, and we hope they can integrate both efforts to get a better plugin in the end.

Anyway, ODT looks interesting right now, and it's been evolving quite fast. Eclipse is quite a memory hog, but if you already use it or are willing to pay the requirements, it can provide a modern IDE for OCaml under Windows or unix, and a good alternative for Emacs. Let's hope ODT keeps improving.

Great news in the Haskell Books front

2007-05-26T14:36:00.000-07:00

This was recently announced and everyone must already know about it (I was away at a conference), but just in case: O'Reilly will publish a book about Haskell called Real-World Haskell, written by people very active in the Haskell community. Such a book from O'Reilly has the potential to seriously increase Haskell's popularity, and familiarize more people with functional programming.

Considering that a book about F# is already out and another one is on the way, and that APress recently published a book on OCaml (it doesn't seem to be very good, unfortunately), I guess functional programming is really getting more popular.

Maybe there's hope that Haskell will take over the world and everyone will use monads and pure lazy functional programming :)

The EOPL in F# thing

2007-05-16T16:59:00.000-07:00

I have translated more of the EOPL book into F#, but the examples keep growing and proving how unfit the whole enterprise is to the blog format. I knew this from the beginning, and would prefer a wiki, but then I couldn't find a decent wiki server. I may have found one now, and if all goes well I'll link to it here after moving there some of the contents posted here. After this, I don't know if this blog will still be useful, but I'll wait and see.

Functional programming in Wall Street

2007-04-30T14:39:00.000-07:00

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

2007-04-03T15:42:00.000-07:00

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

2007-04-03T15:23:00.000-07:00

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

2007-03-23T17:48:00.000-07:00

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

2007-03-18T18:04:00.000-07:00

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

2007-03-11T22:01:00.000-07:00

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

2007-03-09T15:16:00.000-08:00

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.

EOPL - 2.3.4 - Exercise 2.25

2007-03-07T15:40:00.000-08:00

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.


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

2007-03-07T15:32:00.000-08:00

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:


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.

EOPL - 2.3.4 - Alternative Representation

2007-03-06T16:24:00.000-08:00

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

2007-03-06T16:02:00.000-08:00

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

2007-03-06T16:01:00.000-08:00

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

2007-03-06T15:58:00.000-08:00

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

EOPL - 2.3.2 - Exercise 2.16

2007-03-05T13:40:00.000-08:00

Easy one, in two versions.

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

2007-03-05T13:18:00.000-08:00

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.


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

2007-03-05T13:03:00.000-08:00

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:


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'

EOPL - 2.2.2 - Exercise 2.12

2007-02-21T10:35:00.000-08:00

This one asks you to implement alpha, beta and eta conversion on lambda-calculus expressions based on the substitution function of the previous exercise. For this we need a function to see if an identifier occurs free in an expression, similar to the one presented on section 1.3 and easy enough. The conversion functions can then be implemented quite simply:


let rec occurs_free v exp =
   match exp with
     Identifier i when v = i -> true
   | Lambda (x, e) when v <> x -> occurs_free v e
   | App (e1, e2) -> (occurs_free v e1) || (occurs_free v e2)
   | Prim (p, e1, e2) -> (occurs_free v e1) || (occurs_free v e2)
   | _ -> false

let alpha_conversion exp new_id =
   match exp with
     Lambda (id, body) when not (occurs_free new_id body) ->
         Lambda (new_id, lambda_calculus_subst body (Identifier new_id) id)
   | _ -> exp
  
let beta_conversion exp =
   match exp with
     App (Lambda (id, body), e) -> lambda_calculus_subst body e id
   | _ -> exp
  
let eta_conversion exp =
   match exp with
     Lambda (id, App (e, Identifier id'))
     when (id=id') && (not (occurs_free id e)) -> e
   | _ -> exp

These conversion functions simply return the same expression if they aren't of the right form. They could signal an error, depending on the application.

EOPL - 2.2.2 - Exercise 2.11

2007-02-21T10:08:00.000-08:00

Exercise 2.11 asks you to correct the definition of a substitution function on the lambda-calculus, to avoid variable capture. To do that, we need function fresh-id from the previous exercise, but alas, we can't use it as is, because it is also asked to extend the definition of a lambda-calculus expression to includes literals and primitives. Nevertheless, it's an easy exercise.

To define the new lambda-calculus expression type, we first define a type to specify primitives:


type Primitive = Sum | Mult

type LPExp = Identifier of string | Lambda of string * LPExp
          | App of LPExp * LPExp | Literal of int
          | Prim of Primitive * LPExp * LPExp

And here is the code for auxiliary functions and the substitution function:


let rec all_ids exp =
   match exp with
     Identifier i -> [i]
   | Lambda (x, e) -> x :: (all_ids e)
   | App (e1, e2) -> (all_ids e1) @ (all_ids e2)
   | _ -> []
  
let fresh_id exp s =
   let syms = all_ids' exp in
   let rec loop n =
       let sym = s + (string_of_int n) in
       if List.mem sym syms then loop (n + 1) else sym in
   loop 0
         
let rec lambda_calculus_subst exp subst_exp subst_id =
   let rec subst exp =
       match exp with
         Identifier id when id = subst_id -> subst_exp
       | Identifier id -> exp
       | Lambda (id, body) when id = subst_id -> exp
       | Lambda (id, body) ->
           let id'=fresh_id body id in
           let body'=lambda_calculus_subst body (Identifier id') id in
           Lambda (id', subst body')
       | App (e1, e2) -> App (subst e1, subst e2)
       | Literal l -> exp
       | Prim (p, e1, e2) -> Prim (p, subst e1, subst e2) in
   subst exp

The substitution function always does an alpha conversion (substitution of the identifier bound by the lambda) unless the bound identifier is the same as the one being substituted for. This surely works, as alpha conversion doesn't change the meaning of a lambda expression. An alternative would be to alpha convert only when a capture would occur, but this would require a further check like


if List.mem id (all_ids body) then
 // do alpha conversion
else
 // just simple substitution

It would make the code bigger, but not better. Both versions require linear scans of the body, so the efficiency shouldn't differ much between them.

EOPL - 2.2.2 - Exercise 2.10

2007-02-20T18:20:00.001-08:00

Chapter 2 includes examples and exercises for parsing and unparsing textual representations (e.g. parse-expression on page 51). The parsing functions assume a Scheme reader, and just convert from a list representation to an abstract syntax-tree representation based on define-datatype. The unparsing functions do the converse, from the syntax-tree representation to a list representation. As we don't have a list reader in F#, I skipped the examples and exercises related to parsing and unparsing. I also skipped other exercises that I felt wouldn't add much.

So here is Exercise 2.10 about generating fresh identifiers for renaming of variables that might be captured. I first defined a type for lambda-calculus expressions.


type Exp = Identifier of string | Lambda of string * Exp
        | App of Exp * Exp

Then there's all-ids and a converted version of fresh-id:


let rec all_ids exp =
   match exp with
     Identifier i -> [i]
   | Lambda (x, e) -> x :: (all_ids e)
   | App (e1, e2) -> (all_ids e1) @ (all_ids e2)
  
let fresh_id exp s =
   let syms = all_ids exp in
   let rec loop n =
       let sym = s + (string_of_int n) in
       if List.mem sym syms then loop (n + 1)
       else Identifier sym in
   loop 0

EOPL - Chapter 2, Exercise 2.5

2007-02-19T21:07:00.000-08:00

Chapter 2 is about data abstraction. Section 2.1 describes the concepts of interface, representation and implementation, and how a single interface may be implemented by different representations. Not much code there. Section 2.2 presents the constructions define-datatype and cases, to define and pattern-match over variant data types (or disjoint unions, or sum types, choose your preferred terminology). That is roughly equivalent to facilities already present in F#, so there's not much new here.

Exercise 2.5 is a simple pattern-matching exercise to work with the definition of a binary tree data type, expressed in F# as


type BinTree = Leaf of int | Interior of string * BinTree * BinTree

Then we can define max-interior using pattern guards, which aren't available in the Scheme cases construct:


let max_interior bt = 
    let rec maxint t = 
        match t with
          Leaf _ -> failwith "Shouldn't get here"
        | Interior (tag, Leaf l1, Leaf l2) -> (tag, l1 + l2)
        | Interior (tag, Leaf l1, t2) -> 
            let tg, s = maxint t2 in 
            if s > s + l1 then (tg, s) else (tag, s+l1)
        | Interior (tag, t1, Leaf l2) -> 
            let tg, s = maxint t1 in 
            if s > s + l2 then (tg, s) else (tag, s+l2)
        | Interior (tag, t1, t2) -> 
            let tg1, s1 = maxint t1 in
            let tg2, s2 = maxint t2 in
            if s1 > s2 then 
                if s1 > s1 + s2 then (tg1, s1) else (tag, s1+s2)
            else
                if s2 > s1 + s2 then (tg2, s2) else (tag, s1+s2) in
    fst (maxint bt)

But this is a case where it's actually shorter to just use a single pattern match and a conditional, instead of pattern guards:


let max_interior bt = 
    let rec maxint t = 
        match t with
          Leaf i -> (None, i)
        | Interior (tag, t1, t2) -> 
            let tg1, s1 = maxint t1 in
            let tg2, s2 = maxint t2 in
            if tg1 = None && tg2 = None then
                (Some tag, s1 + s2)
            elif s1 > s2 || tg2 = None then
                if s1 > s1+s2 then (tg1, s1) 
                else (Some tag, s1+s2)
            else
                if s2 > s1+s2 then (tg2, s2) 
                else (Some tag, s1+s2) in
    match bt with
      Leaf _ -> failwith "Shouldn't happen"
    | t -> maxint t |> fst |> Option.get

Even so, the function is somewhat big, and could be broken in two, but we'll let it as it is.

Scala

2007-02-12T10:37:00.000-08:00

My choice for a functional programming language that integrates with .NET is F#. By the same token, when I think about writing software for the Java platform and wish to use a language better suited to my tastes, my choice is Scala. It's a pretty cool language that mixes OO and functional programming quite neatly, and with interesting theoretical studies to support it. The syntax was chosen to be similar to Java, which I don't like, but it's a minor problem. It's actively supported and developed, and is gaining momentum right now, which can be a good thing.

I need to write a simple program to talk to a Java program in the next few days, so I'll probably be using Scala for it. This means I may write posts about it in the near future.

EOPL - 1.2.4 - Exercise 1.18

2007-01-25T15:37:00.000-08:00

Exercise 1.18 takes advantage of Scheme's uniform treatment of code and data, so the functions proposed should return lists that can be evaluated to get some effect. Furthermore, there are typing issues, so adaptations are needed. The first function, compose, is easy enough:


let compose p1 p2 = fun x -> p1 (p2 x)

Next, I defined a data type to represent list operations:


type ListOp = Car | Cdr | Compose of ListOp * ListOp | Error

So it's easy to define car_cdr, but it doesn't return a list to evaluate, rather a ListOp object. Also, because of typing it was easier to include a variant Error of type ListOp and eliminate parameter errval.


let rec car_cdr s slist =
    match slist with 
      [] -> Error 
    | s1 :: rslist when s1 = s -> Car
    | _ :: rslist -> Compose (car_cdr s rslist, Cdr)

Thus we get


> car_cdr "c" ["a"; "b"; "c"];;
val it : ListOp = Compose (Compose (Car,Cdr),Cdr)

So we have a description of the necessary list operations, but it's not directly executable as in Scheme. So we need a function to execute the list operations returned on a list, and this is run_listop


let rec run_listop op lst = 
    match op with
      Car -> List.hd lst
    | Compose (c1, Cdr) -> run_listop c1 (List.tl lst)
    | _ -> failwith "can't do"

The case that leads to an exception is to find a single Cdr without a previous Car. This is a good indication that the type was not designed properly, but we will not bother with this here. Function car_cdr2 doesn't need explicit Compose operations, and returns a list of list operations that must be applied in succession.


let car_cdr2 s slist errval =
    let rec loop lst =
        match lst with
          [] -> []
        | l :: rlst when s = l -> [Car]
        | _ :: rlst -> Cdr :: (loop rlst) in
    List.rev (loop slist)

It's quite easy to define a function to execute these ListOp lists, but not that interesting at this point.

EOPL - 1.2.4 - Exercise 1.17, sorting

2007-01-15T13:04:00.000-08:00

Another exercise. This one involves binary trees and sorting. For the bintrees and finding a path through them to an element, we define two types:


type BinTree = Empty | Node of int * BinTree * BinTree
type direction = Left | Right

Then we can define function path, returning a list of directions:


let rec path n bst = 
    match bst with
      Empty -> failwith ("number " + (string_of_int n) + " not found in tree")
    | (Node (x, left, right)) when n = x -> []
    | (Node (x, left, right)) when n < x -> Left :: path n left
    | (Node (_, left, right)) -> Right :: path n right

For sorting, I chose to implement a rudimentary quicksort (with the first element as pivot). As with previous functions, beware of the value restriction.


let rec sort lst = 
    let left_part x (lp, rp) = (x :: lp, rp) in
    let right_part x (lp, rp) = (lp, x :: rp) in
    let rec partition p lst = 
        match lst with 
          [] -> ([], [])
        | (x :: rlst) when x < p -> left_part x (partition p rlst)
        | (x :: rlst) when x > p -> right_part x (partition p rlst)
        | (x :: rlst) -> partition p rlst in
    match lst with
      [] -> []
    | (x :: rlst) -> let lp, rp = partition x lst in 
                     (sort lp) @ [x] @ (sort rp)

I wrote the internal function partition because it was part of the exercise, but it is already there in the standard library. Using this fact, we can get a much shorter version of quicksort:


let rec sort lst = 
    match lst with
      [] -> []
    | (x :: rlst) -> let lp, rp = List.partition (fun n -> n < x) rlst in 
                     (sort lp) @ [x] @ (sort rp)

To sort with a different predicate is a straightforward change in either version. Here is the longer version working with a predicate:


let rec sort pred lst = 
    let left_part x (lp, rp) = (x :: lp, rp) in
    let right_part x (lp, rp) = (lp, x :: rp) in
    let rec partition p lst = 
        match lst with 
          [] -> ([], [])
        | (x :: rlst) when x = p -> partition p rlst
        | (x :: rlst) when (pred x p) -> left_part x (partition p rlst)
        | (x :: rlst) -> right_part x (partition p rlst) in
    match lst with
      [] -> []
    | (x :: rlst) -> let lp, rp = partition x lst in 
                     (sort pred lp) @ [x] @ (sort pred rp)

Finally, just for fun, I wrote a merge sort function too.


let rec merge_sort (lst:'a list) =  
    let merge_pairs (ll1, rl1) (ll2, rl2) = 
        (ll1 @ ll2, rl1 @ rl2) in
    let split_pairs i x = 
        if i < (lst.Length / 2) then ([x], []) else ([], [x]) in
    let split l = 
        List.fold_right merge_pairs (List.mapi split_pairs l) ([], []) in
    let rec merge lon1 lon2 = 
        match (lon1, lon2) with
          ([], _) -> lon2
        | (_, []) -> lon1
        | (x :: rlon1, y :: rlon2) when x <= y -> x :: (merge rlon1 lon2)
        | (x :: rlon1, y :: rlon2) -> y :: (merge lon1 rlon2) in
    match lst with
      [] -> []
    | [x] -> [x]
    | _ -> let l, r = split lst in merge (merge_sort l) (merge_sort r)

It's quite long, but I didn't bother trying to get a shorter version.

EOPL - 1.2.4 - Exercise 1.16

2007-01-14T18:47:00.000-08:00

And now back to business, nothing really exciting yet: the next batch of exercises. The first is function up that in F# ends up being the same as concat, unless we define some new type.


// if not defining a new type that may be a list or a single element, 
// up will work like concat, on lists of lists
let rec up lst = 
    match lst with
      [] -> []
    | (l :: rlst) -> l @ (up rlst)

This is the Scheme version of up, for comparison:


(define up
  (lambda (lst)
    (if (null? lst)
      '()
      (if (list? (car lst)
        (append (car lst) (up (cdr lst)))
        (cons (car lst) (up (cdr lst)))))))

The next functions work on lists of symbols, so we repeat here the necessary type definition for symbol expressions.


type SymbolExp = Symbol of string | SList of SymbolExp list

And the functions can thus be written:


let rec swapper s1 s2 slist = 
    match slist with
      [] -> []
    | (s :: rslist) -> swapper_in_symbol_exp s1 s2 s :: 
                      (swapper s1 s2 rslist)
and swapper_in_symbol_exp s1 s2 sexp = 
    match sexp with
      (Symbol s) when s = s1 -> Symbol s2
    | (Symbol s) when s = s2 -> Symbol s1
    | (SList sl) -> SList (swapper s1 s2 sl)
    | _ -> sexp

let rec count_occurrences sym slist = 
    match slist with
      [] -> 0
    | (s :: rsl) -> (count_occurrences_sexp sym s) + 
                    (count_occurrences sym rsl)
and count_occurrences_sexp sym sexp = 
    match sexp with
      (Symbol s) when s = sym -> 1
    | (SList sl) -> count_occurrences sym sl
    | _ -> 0
    
let rec flatten slist = 
    match slist with
      [] -> []
    | ((Symbol s) :: rsl) -> (Symbol s) :: (flatten rsl)
    | ((SList sl) :: rsl) -> (flatten sl) @ (flatten rsl)
    
// lon1 and lon2 are sorted lists of numbers
let rec merge lon1 lon2 = 
    match (lon1, lon2) with
      ([], _) -> lon2
    | (_, []) -> lon1
    | (x :: rlon1, y :: rlon2) when x <= y -> x :: (merge rlon1 lon2)
    | (x :: rlon1, y :: rlon2) -> y :: (merge lon1 rlon2)

EOPL - 1.2.3 - Other Patterns of Recursion

2007-01-02T18:11:00.000-08:00

Forgot to post the code for this section. Simple stuff, and only three functions.


let rec list_sum l = 
    match l with
      [] -> 0
    | (x :: rl) -> x + list_sum rl
    
let rec partial_vector_sum von n =
    if n = 0 then 0 
    else von.(n - 1) + partial_vector_sum von (n - 1)
     
let vector_sum von = 
    partial_vector_sum von von.Length

EOPL - 1.2.4 - Some Exercises - 1.15

2007-01-02T17:34:00.000-08:00

These are F# solutions to Exercise 1.15. In some places the functions proposed in the exercise are not completely suited to a ML language, so I made notes in the comments, but otherwise there is little that is exciting about these functions. I did alternative versions in some cases, even though the whole point of this exercise (and the rest from Section 1.2) is to write recursive functions to get a feel for them.

The function product once again runs into troubles with the value restriction. If one of the parameters is an empty list, the F# system won't recognize the result as a simple data value, so it will complain. The only way around it is to use type annotations, as noted in the comments after both versions of the function.


let rec duple n x = 
    if n = 0 then [] else x :: (duple (n - 1) x)

// invert would probably accept a list of real pairs in F#
let invert lp = 
    let invpair p = 
        match p with 
          [] -> [] 
        | (a :: b :: []) -> [b; a] 
        | _ -> failwith "invalid list" in
    List.map invpair lp

let rec filter_in p lst = 
    match lst with 
      [] -> []
    | (x :: rl) when p x -> x :: (filter_in p rl)
    | (_ :: rl) -> filter_in p rl

let rec every p lst = 
    match lst with 
      [] -> true
    | (x :: rl) when p x -> every p rl
    | _ -> false

let every2 p lst = 
   List.fold_left (fun b x -> b && p x) true lst

let rec exists p lst = 
    match lst with 
      [] -> false
    | (x :: rl) when p x -> true
    | (_ :: rl) -> exists p rl

// It's not possible to return numbers and booleans, so we could 
// use an algebraic data type, or int option, which seems better
let vector_index p (v:'a array) = 
    let rec search i = 
        if i = v.Length then None
        elif p v.(i) then Some i
        else search (i + 1) in
    search 0
    
// the test given can't be easily expressed in F#
// also: fragile for negative n
let rec list_set lst n x = 
    match (lst, n) with
      ([], _) -> []
    | (elt :: rl, 0) -> x :: rl
    | (elt :: rl, i) -> elt :: (list_set rl (n - 1) x)

// value restriction troubles: any empty list gives an error    
let rec product l1 l2 = 
    match (l1, l2) with
      (_, []) -> []
    | ([], _) -> []
    | (x :: rl1, _) -> (List.map (fun e -> (x, e)) l2) @ (product rl1 l2)

// value restriction troubles: any empty list gives an error    
let product2 l1 l2 = 
    List.concat (List.map (fun x -> List.map (fun e -> (x, e)) l2) l1)

(* 
To call product with an empty list as argument, you must annotate its type:
> product [1; 2; 3] ([] : int list);;
val it : (int * int) list = []
*)

// once again, this function makes less sense in F# than in Scheme
let down lst = 
    List.map (fun x -> [x]) lst 

// explicitly recursive version:
let rec down2 lst =  
    match lst with [] -> [] | (x::rl) -> [x] :: (down2 rl)

// scheme version    
(* 
(define down
  (lambda (lst)
    (if (null? lst)
      '()
      (cons (list (car lst))
            (down (cdr lst))))))
*)
    
// more type inference nuances: these types must be written down
let vector_append_list (v:'a array) (lst:'a list) = 
    let rec copy src dst i = 
        if i = 0 then () 
        else (dst.(i-1) <- src.(i-1); copy src dst (i-1)) in
    let rec copy_list_to_vector ls vc i = 
        match ls with 
          [] -> () 
        | (x :: rls) -> (vc.(i) <- x; 
                         copy_list_to_vector rls vc (i + 1)) in
    let newv = Array.create (v.Length + lst.Length) 0 in
    (copy v newv v.Length; 
     copy_list_to_vector lst newv v.Length; 
     newv)

EOPL - 1.2.2 - Some Important Examples

2006-12-31T13:57:00.000-08:00

The first 2 chapters of the book are quite basic, but in this section we get some interesting tidbits regarding static versus dynamic typing.

Beginning with two easy functions, remove and remove-first. The type definition for a list of symbols is


<list-of-symbols> ::= [] | <symbol> :: <list_of_symbols>

And the implementation of the functions are:


let rec remove_first s los =
   match los with
     [] -> []
   | (smb :: los') when smb = s -> los'
   | (smb :: los') -> smb :: (remove_first s los')
  
let rec remove s los =
   match los with
     [] -> []
   | (smb :: los') when smb = s -> remove s los'
   | (smb :: los') -> smb :: (remove s los')

Of course, the structural equality operator (=) here implies that these functions work not only with lists of symbols, but lists of any type. The type checker correctly infers the type 'a -> 'a list -> 'a list for both lists. In Scheme too it's possible to get generic functions using the structural equality function equal? -- and as it is the function is guaranteed to work with symbols, numbers and characters because it uses eqv? -- but the authors probably didn't want to talk about parametric polymorphism at this point in the discussion.

Now to two more functions, subst and notate-depth, that work on symbol expressions. A symbol expression is either a symbol or a list of symbol expressions, called an slist:


<s-list>            ::= [] | <symbol-expression> :: <s-list>
<symbol-expression> ::= <symbol> | <s-list>

So now we can't directly define in F# functions that work either on a symbol or a list of similar data. We must define a new type that is a disjoint union of symbols and lists of symbol expressions:


type SymbolExp = Symbol of string | SList of SymbolExp list

And now define the function subst as in the book:


let rec subst n old slist =
   match slist with
     [] -> []
   | (s :: sls) -> (subst_in_symbol_expression n old s) ::
                   (subst n old sls)
and subst_in_symbol_expression n old sexp =
   match sexp with
     Symbol s when s = old -> Symbol n
   | Symbol s -> Symbol s
   | SList sl -> SList (subst n old sl)

Note that subst receives plain strings as the new and old parameters, not a Symbol str where str is a string. Also, the list that subst receives is a SymbolExp list and not a SymbolExp that is a SList. The former fact is a difference in relation to the Scheme version (but could easily be changed) and the latter is consistent with the Scheme version; both may seem a bit confusing.

For notate-depth there's still another problem: the values returned by it are not really slists. While in Scheme this causes no problem, in F# we have to define a new type that includes the depth information with every symbol. So we get


type NotatedSymbolExp = NSymbol of string * int 
                      | NSList of NotatedSymbolExp list

And finally, the function:


let rec notate_depth_in_slist slist n =
   match slist with
     [] -> []
   | (s :: sls) -> (notate_depth_in_symbol_expression s n) ::
                   (notate_depth_in_slist sls n)
and notate_depth_in_symbol_expression sexp n =
   match sexp with
     Symbol s -> NSymbol (s, n)
   | SList sl -> NSList (notate_depth_in_slist sl (n + 1))
  
let notate_depth slist = notate_depth_in_slist slist 0

The rest of the code are solutions to the exercises that require coding.

Exercise 1.11


let rec subst n o slist =
   match slist with
     [] -> []
   | ((Symbol s)::sls) when s=old -> ((Symbol n)::subst n o sls)
   | ((SList sl)::sls) -> ((SList (subst n o sl))::subst n o sls)
   | (s::sls) -> s :: subst n o sls

Exercise 1.12


let rec subst_in_symbol_expression n old sexp =
   match sexp with
     Symbol s when s = old -> Symbol n
   | Symbol s -> Symbol s
   | SList sl -> SList (subst3 n old sl)
and subst n old slist =
   List.map (subst_in_symbol_expression n old) slist

Exercise 1.13


let rec notate_depth_in_slist slist n =
   List.map (notate_depth_in_symbol_expression n) slist
and notate_depth_in_symbol_expression n sexp =
   match sexp with
     Symbol s -> NSymbol (s, n)
   | SList sl -> NSList (notate_depth_in_slist sl (n + 1))

EOPL - 1.2.1 - Deriving Programs from BNF Data Specifications

2006-12-31T11:59:00.000-08:00

It's not necessary to have functions like list-of-numbers? in F#, because types are checked statically. An int list will always be a list of integers if the code compiles. The type checker takes care of that. So here are versions of nth-elt and list-length:


let rec nth_elt l n = 
    match (l, n) with 
      ([], _) -> failwith ("List too short by " + 
                           string_of_int (n + 1) + " elements")
    | (x :: rl, 0) -> x
    | (_ :: rl, _) -> nth_elt rl (n - 1)
    
let rec list_length l = 
    match l with
      [] -> 0
    | (_ :: rl) -> 1 + list_length rl

Just for fun, here is a non-recursive version of list-length, using a fold:


let list_length l = List.fold_left (fun n _ -> n + 1) 0 l

Unfortunately the F# compiler doesn't let us write this version in point-free style because of some trouble with the value restriction.

Exercises 1.5 and 1.6 make no sense in F#, once again because of the static type checker. Exercise 1.7 is quite easy, thanks to any_to_string:


let nth_elt l n = 
    let rec loop l' n' =
        match (l', n') with
          ([], _) -> failwith ((any_to_string l) + 
                               " does not have an element " + 
                               string_of_int n)
        | (x :: rl, 0) -> x
        | (_ :: rl, _) -> loop rl (n' - 1) in
    loop l n

IRC messages and 2 more Haskell functions

2006-12-31T08:38:00.000-08:00

An IRC (Internet Relay Chat) message is composed of fields delimited by a space, up to an optional last argument which may include spaces. This last argument is delimited by a field whose first character is a colon; in this case, from the colon to the terminating CR-LF pair, every character is part of the same argument. This is done to send chat messages that may include spaces, of course. A message to the person with nickname lovecraft is sent (from the client to the server) like this:
"PRIVMSG lovecraft :hi there, man!\r\n"

Also, the message may include a sender field as its first field. This is indicated by the very first character of the message being a colon. When the above PRIVMSG is sent by a user cthulhu to the server, it redirects the message to the recipient, but now indicating who sent it; like this:
":cthulhu PRIVMSG lovecraft :hi there, man!\r\n"

So the task is to break an incoming IRC message into its constituent fields. There are two complications: 1) it's not possible to just split using spaces as separators, because of the last argument and 2) the first and last argument both may begin with a colon, and so it's not sufficient to just stop splitting at the first sight of a colon in the first character of a field.

I first defined a recursive function that did most of the work after a call to String.split, but then thought about using higher-order functions. Two Haskell functions could be used, called takeWhile and dropWhile. They are like take and drop, but instead of using a numeric index to decide where to stop taking (or dropping) elements to (or from) the list, it uses a predicate testing over the elements. So, takeWhile p l will return a list taking elements x from l while p x is true. Here is the code for these functions:


let rec takeWhile p l = 
    match l with
      [] -> []
    | (x :: rl) when p x -> x :: (takeWhile p rl)
    | _ -> []
    
let rec dropWhile p l = 
    match l with 
      [] -> []
    | (x :: rl) when p x -> dropWhile p rl
    | _ -> l

Now it's easy to define the function splitLine that splits an incoming IRC message into fields, keeping the last field intact. It assumes that the trailing CR-LF characters where already stripped from the message.


let splitLine line = 
    let noColon s = s.[0] <> ':' in
    let concat l = match l with [] -> [] | _ -> [String.concat " " l] in
    let words = line |> String.split [' '] in
    match words with
      [] -> []
    | (w :: wds) -> w :: ((takeWhile noColon wds) @ 
                          (concat (dropWhile noColon wds)))

So, to show an example:


> splitLine 
   ":cthulhu PRIVMSG lovecraft :hi there, man!\r\n";;
val it : string list = [":cthulhu"; 
                        "PRIVMSG"; 
                        "lovecraft"; 
                        ":hi there, man!"]

It's necessary, at this stage, to keep the colon in the sender field (to signal that the message has a sender field), but it could be removed from the last field. Anyway, splitLine will be used by another function that builds a Message record, removing all the colons that are added by the protocol.

Good news

2006-12-27T09:26:00.000-08:00

It seems String.map will be added to the F# library in its next release. Also, there were quite good responses to the points I raised about library functions in the F# mailing list. Don Syme noted that zip is already there, and it's called List.combine. I hadn't noticed this.

Also, Robert Pickering, author of the upcoming APress book Foundations of F#, responded on his blog with a short version of the ROT13 algorithm, using only functions already present in the current library:
http://strangelights.com/blog/archive/2006/12/27/1580.aspx

It basically uses List.mapi instead of my combo of zip, drop and take. List.mapi maps a function over a list, but this function gets as arguments the list element and its index. And mapping over a string is implemented by converting the string to a char array, using Array.map over it and then creating a new string based on the result.

Still more ROT13

2006-12-25T09:15:00.000-08:00

This is the last post on ROT13, I promise. The shortest version in F# is a low-level one, working with character codes. This is the most obvious solution to C programmers, and I considered it from the start, but I feel it loses something from the other versions. We have to "break" the abstraction of characters and think about their representation, and this lowers the level we are working. Here it is:


#light

let strmap f (s : string) = 
    let sb = new System.Text.StringBuilder(s) 
    let rec aux i = 
        if i = sb.Length then () else
        (sb.Chars(i) <- f (sb.Chars(i)) ; aux (i + 1))
    ( aux 0; sb.ToString() )

// still another one
let rot13 s = 
    strmap 
     (fun c -> Char.chr ((((Char.code c) - 97 + 13) mod 26) + 97)) 
     s

I should probably substitute Char.code 'a' for 97 there, and this would work as long as the encoding guaranteed that letters a to z were assigned contiguous codes, which I believe is valid in most or all current text encodings. Still, we have to think about text encodings and character representations. And we still need a function to map over strings.

ROT13 in F#, revisited

2006-12-24T22:31:00.000-08:00

So after seeing the Haskell version I thought, lookup is actually assoc, in F# included in the module List. So how about trying a F# version similar to the Haskell one? Well, the problem is, as I mentioned, that F# doesn't have zip, take and drop, and there is no way to map over a string. So we have to define all these functions, and then define rot13 as in the Haskell version. I defined zipWith from the Haskell prelude as well, and then used it to define zip (as it is in Haskell).


#light

let strmap f (s : string) = 
    let sb = new System.Text.StringBuilder(s) 
    let rec aux i = 
        if i = sb.Length then () else
        (sb.Chars(i) <- f (sb.Chars(i)) ; aux (i + 1))
    ( aux 0; sb.ToString() )

let rec drop n l = 
    match (l, n) with
      ([], _) -> []
    | (l, 0) -> l
    | (_ :: rl, n) -> drop (n - 1) rl
    
let rec take n l = 
    match (l, n) with
      ([], _) -> []
    | (l, 0) -> []
    | (x :: rl, n) -> x :: (take (n - 1) rl)

let rec zipWith f l1 l2 = 
    match (l1, l2) with
      ([], _) -> []
    | (_, []) -> []
    | (x1 :: rl1, x2 :: rl2) -> (f x1 x2) :: (zipWith f rl1 rl2)

let zip l1 l2 = 
    zipWith (fun a b -> (a, b)) l1 l2

// and now for something completely different
let rot13 s = 
    let letters = ['a' .. 'z']
    let transp = zip letters ((drop 13 letters) @ (take 13 letters))
    let rotchar c = List.assoc c transp
    strmap rotchar s

Works as expected, but we ended with code that is still longer than the first version, only because it was necessary to define some general-use functions. I guess I will create a Prelude module to use with F#, containing the Haskell functions I use most.

EOPL - 1.2 - Recursively Specified Programs

2006-12-24T21:32:00.000-08:00

The first program is easy enough:


let rec e n x = 
    if n = 0 then 1 else x * (e (n-1) x)

But the second one uses the definition of bintrees from section 1.1. I should have noted there that some differences are caused because of static vs. dynamic typing. Scheme is "dynamically typed" (that's the usual term, anyway -- maybe it should be called "dynamically checked"), so it can define a bintree data type that may be a number or a list. Parts of the program that use this type must check if it received a number or a list, and act accordingly. But F# is statically typed, so we can't do it like this, because a number is a member of a type and a list is from another one. The way to solve this in F# is by creating a disjoint union data type that includes numbers and lists; well, as we know the second possibility has only 3 components, we'll do this as a tuple. So we get


type Bintree = Leaf of int | Node of string * Bintree * Bintree

With this definition, and some pattern matching, it's easy to write count-nodes:


let rec count_nodes s = 
    match s with
      Leaf _ -> 1
    | Node (_, bt1, bt2) -> (count_nodes bt1) + (count_nodes bt2)

The program still follows the same structure as the proof given earlier for the property.

It's interesting to note that we have to define a type, where in Scheme it wouldn't need any definition. Of course, the Scheme program is harder to understand because of the use of implicit list structure (cadr and caddr are used to decompose the list). But in F# we have to define a representation in terms of a tagged union type, and to hide the representation we would have to define an interface with an opaque type. A bit more of work but we get static checking and better runtime performance.

ROT13 in Haskell

2006-12-24T19:53:00.000-08:00

To drive home the point of F#/OCaml lacking some predefined functions that make life easier, here is a version of the same ROT13 encoding algorithm, now in Haskell. Of course the whole thing is easier not only because of functions like zip, take and drop, but also because strings in Haskell are actually lists of characters. Anyway, here it is. Compare with the F# version.


rot13 s = map rotchar s 
    where rotchar c = maybe '#' id (lookup c transp)
          transp = zip letters ((drop 13 letters) ++ (take 13 letters))
          letters = ['a' .. 'z']

And now for the use case:


*Rot13> rot13 "feijoada"
"srvwbnqn"

ROT13 in F#

2006-12-24T16:42:00.000-08:00

So, this is nothing really exciting, I wrote a simple program to do ROT13 text encoding, and in the way bumped into some minor quirks of the standard library. One of the problems with OCaml is its idiosyncratic standard library which is missing a lot of simple and useful functions. Granted, most of them you can write in less than five minutes, but it would be better if they were already done and standardized. I guess I became spoiled by Haskell. Anyway, F# seems to have inherited this as well. Below you can see the code, and a sample use case.


#light

let letters = Array.of_list(['a' .. 'z'] @ ['a' .. 'z'])

let index a c =
  let rec aux i = if a.(i) = c then i else aux (i + 1) in
  aux 0

let strmap f (s : string) =
  let sb = new System.Text.StringBuilder(s) in
  let rec aux i =
      if i = sb.Length then () else
      (sb.Chars(i) <- f (sb.Chars(i)) ; aux (i + 1)) in     
      ( aux 0; sb.ToString() )     

let rotchar c =     
    let i = index letters c in     
    letters.(i + 13)  

let rot13 s =     
    strmap rotchar s

And now for the use case:


> rot13 "feijoada";;
val it : string = "srvwbnqn"

EOPL - 1.1 - Recursive Sets of Data

2006-12-23T16:48:00.000-08:00

The ML languages, unlike Scheme, don't have a "cons pair" type. For pairs one can use tuples, and for proper lists there are lists. This means it is not possible to build an improper list in ML. So it is with F#, and this implies a simple change to the definition of lists of numbers (Definition 1.1.2, page 2).

Definition 1.1.2 The set list-of-numbers is the smallest set of values satisfying the two properties:

The empty list is a list-of-numbers, and
If l is a list-of-numbers and n is a number, then the cons expression (n :: l) is a list-of-numbers

Another point of difference is that F# lacks a native symbol type. Regarding the examples in the book, it seems we can safely use strings in place of symbols, although I don't know if later chapters make use of the fact that the symbols may have associated values. Regarding types, we can use a simple type synonym:


type Symbol = string

Or a tagged type:


type Symbol = Symbol of string

The latter will be more useful when defining other types of expressions, like the examples for the lambda-calculus. In this case there will be symbols, applications and abstractions, and not only a single variant.

With this in mind, it's easy to define a list-of-symbols type. At this point in the book, though, there's not much attention to representation of the data types, as the goal is to become familiar with recursive definitions. It uses the lisp pair notation, however, and lisp symbols, and these dependencies would be thus represented in F#. The same would hold for Standard ML or OCaml, of course.

ML type systems and Hindley-Milner type inference

2006-12-22T17:58:00.000-08:00

Two texts I've come across in the last few days dealing with type systems for ML-like languages and Hindley-Milner type inference.

First, from a rather simple question about principal typings and principal types in the Caml list came a link to the paper ML Has Principal Typings by Carlos Camarão and Lucília Figueiredo; it shows a type system for ML that has principal typings, whereas the usual Damas-Milner type system found in ML languages has not.

Then, LtU links today to A modern eye on ML type inference, some seemingly interesting lecture notes that explain Hindley-Milner type inference in current terms, including extensions. I didn't read it yet, but will do.

Just beginning

2006-12-22T17:26:00.000-08:00

This will be used to collect some code, mostly snippets I'm writing from time to time, often as exercices in books. One of the ideas is to translate code in some interesting books to other languages, like the SICP in other languages stuff. The language I'll be tackling will be, mostly, F#, but I guess some Haskell will appear too. Initially the idea is to work through the book Essentials of Programming Languages, but there are other candidates.

And maybe something else beyond book translations, I don't know. I'll try to comment on the code where I think it's necessary.