Tag Archives: o’reilly

Threading with Ocaml

Building, Check writing notes

Tagged , , , , ,

Lexical Tree – The redo Exercises

Ok, so the first code I made for this exercise was bad, and I couldn’t get to the solution, so this is a redo!

 

The exercise is from the O’Reilly book on Ocaml, “Developping Application with Ocaml”.

Its the Second exercise of the second chapter, Lexical Trees.

 

The exercise is simple. A structure for the Lexical Tree is given, and also its nodes, and what is asked is to build the methods to access and modify the tree.

Its functional programming so the point is not to reuse variables but to make copies, I want to keep that in mind this time.

 

As opposed to before, I will first use a pen and papers and then code it in Ocaml.

 

1. Write the function exists which testes wether a word belongs to a dictionary or not, of type lex_tree

Its impossible not to be biased after viewing the solution, so:

1. Pattern match dictionary with 3 cases:

Empty Dictionary

Filled and Letter = word.[i]

Filled and Letter != word [i]

2. Make it recursive, after all its the point of the xercise

Create an auxiliary function that you can call and increment i

3. Everytime you call the function, it only happens in the second case, call it with the substring of word

4. Return the value as boolean

(5. End case of recursion is n = 1!, when the word reaches the last word, return the node boolean)

 

From O’Reilly

# let rec exists w d = 
let aux sw i n = match d with
[] -> false
| (Letter (c,b,l))::t when c=sw.[i] ->
if n = 1 then b else exists (String.sub sw (i+1) (n-1)) l
| (Letter (c,b,l))::t -> exists sw t
in aux w 0 (String.length w) ;;
val exists : string -> lex_tree -> bool = <fun>

 

2. Write function insert element, which should only insert if it doesn’t exist already


Here we use almost the same algorithm as above.

Keeping in mind we have to return the modified dictionary 

 

From O’Reilly

# let rec insert w d = 
let aux sw i n =
if n = 0 then d
else match d with
[] -> [Letter (sw.[i], n = 1, insert (String.sub sw (i+1) (n-1)) [])]
| (Letter(c,b,l))::t when c=sw.[i]->
if n = 1 then (Letter(c,true,l))::t
else Letter(c,b,insert (String.sub sw (i+1) (n-1)) l)::t
| (Letter(c,b,l))::t -> (Letter(c,b,l))::(insert sw t)
in aux w 0 (String.length w) ;;
val insert : string -> lex_tree -> lex_tree = <fun>

 

3. Write a function construct which takes a list of words and constructs the dictionary

Simple as it sounds. With what I learned before, I will create a simple recursive function.

I did a solution of mine, almost similar, but the one in the solutions is far simpler.

 

1. Receives a list of strings and returns a dictionary

2. Create récursive aux fonction, just as done above. 

3. If empty list, its the end so, return dictionary

4. If not empty, call aux recursion with rest of list and new dictionary (returned from insert head dictionary)

5. Done

From O’Reilly

# let construct l = 
let rec aux l d = match l with
[] -> d
| h::t -> aux t (insert h d)
in aux l [] ;;
val construct : string list -> lex_tree = <fun>

 

To continue…


Tagged , ,

Compiling and Executing

Well I have been studying Ocaml for some days now but I have been using the Ocaml top-level to test my code until now. 

Therefore, I decided to grab a book and start understanding how to build a small project.

 

ByteCode vs NativeCode

For starters, there are two compilers, one generates portable code and the other one  specific architecture performance programs.

They byteCode compiler, from what I could understand, works like Java Virtual Machine. It is, in fact, a Virtual Machine, its name is Zinc (Zinc is not Caml). The byteCode compiler generates Zinc instructions. 

This way code can be run in any system where a byteCode compiler as been developed for, just like JVM.

The native compiler is optimized for the architecture of the system it was designed for.

ocamlc (ByteCode compiler)

ocamlopt (NativeCode compiler)

 

Compiling

Compiling a single file is as simples as doing it with a C compiler:

ocamlc -o executalbe_file source_file.ml

Its analogous to the native compile. Its quite simple, nothing to add here.

 

Running Toplevel

If you are using, or just started working with, Ocaml, the first thing you notice is that you have a nice little thing called Toplevel execution. If you used MATLAB, like I did, the first thing you will think is: “This is just like MATLAB console”

Basically yes, it runs Ocaml code right on the fly, which is very useful, for debugging or testing.

But, I haven’t studied much about it in particular. I will try to do it later, because it has some interesting directives like #trace.

 

Modules

Now, the reason why I made this little summary, Modules. I need modules, I think everyone needs. 

So, I decided to go a bit back and try to understand how it works, from compiling a simple file to testing it.

I want to make a small project that simulates an Anti-Missil (check project here), and for that I want to use modules.

Modules in Ocaml, so far look like they are the same as in Java or C, you make them in different files (usually) and compile each one individually and compile the interfaces with the main file in the end. 

I will test a small example to see if I am able to do a simple module compile and execution:

I created a small program a.ml that defined a record and a method for this record, and another program b.ml that would create a value of type record A and call the method on it. Therefore b.ml depends on a.ml

Compiling the files according to dependency, first a.ml then b.ml, worked fine.

I guess makefiles will be useful in the future.

For now I will stop my experiments with modules and try to start solving my project: Anti Missile.

 

 

 

This post will be reviewed as soon as I can so it has the correct information. Right now it was written as a form of a work log.

 

Thank you,

João Bastos

  

Tagged , ,

Lexical Trees and the quest for redefining a variable

I have been doing some exercises from the O’reilly book, which by the way is very good, and I always end up failing or missing the point of the exercises.

I discovered that the solutions are available in the online version of the text-book ( who would have guessed?), and since then have been confirming my solutions.

This post is about the Lexical Tree exercise.

My struggle has been to understand reset my mind to think recursively and not imperatively. Its hard. I have been a C, C# and Java programmer as long as I remember. I like recursive functions, but its hard for me to think of them as a first approach.

Anyway, after slowing down and think about all the possible cases and criteria’s I was able to find a suitable solution, however, not as good as the one provided by the authors.

The elegance in Ocaml keep amazing me, its so simple.

The functions are all the same after you know how to go though the tree. That’s the elegance.

I will redo the assignment and post here a good solutions and scheme.

For now I just want to record these thoughts and discoveries:

– Recursive always!
– Use pattern matching when possible, to attend the several constraints and cases
– Use the libraries, String in this specific case
– Practice in paper first!

Doubts:

I still can’t think of a good way of redefining values. The functions return a new data structure, a modified data structure but if I don’t use it again, or recursively I loose the information.

Right now, I am using let for re-assigining the values. for ex:

– let d = insert w d;;
– let d = insert w2 d;;

And so on.

Edit 3/12/12

After sleeping on this, I realized how stupid I was being by trying to force imperative thinking on this language again.

There is no need for mutable variables, here I have to start thinking about returning a new instance.

Its really hard to think like this, I have been completely formatted for imperative programming.

I just got a small new book to take a look, its called “Thinking Ocaml”. I post later a follow-up on this.

 

 

Tagged , , ,