Yet another sudoku solver (838 bytes)

Yet another sudoku solver (838 bytes)

[Marco Maggesi]

While we are there, this is my soduku solver.  It is not as efficient
as the other solver proposed in this list, but it takes a fraction of
seconds to compute a solution on a P4 anyway.

Perhaps, the distinguishing feature of this implementation is that it
uses higher order functions in an essential way (that is, the
accumulator argument of the "fold" in the body of "search" is a
function).  And it is only 838 of code of clear (?) and concise code.

BTW, now that we have so many sudoku solvers, wouldn't be be nice to
have one with a computer certified implementation?

Marco

------------------------------------------------------------

Instructions:

  $ ocamlopt -o sudoku sudoku.ml
  
  $ cat schema
  0 6 0 1 0 0 0 5 0
  0 0 8 3 0 5 6 0 0
  2 0 0 0 0 0 0 0 1
  8 0 0 4 0 7 0 0 6
  0 0 6 0 0 0 3 0 0
  7 0 0 9 0 1 0 0 4
  5 0 0 0 0 0 0 0 2
  0 0 7 0 0 6 9 0 0
  0 4 0 0 0 8 0 7 0

  $ ./sudoku < schema
  9 6 3 1 7 4 2 5 8
  1 7 8 3 2 5 6 4 9
  2 5 4 6 8 9 7 3 1
  8 2 1 4 3 7 5 9 6
  4 9 6 8 5 2 3 1 7
  7 3 5 9 6 1 8 2 4
  5 8 9 7 1 3 4 6 2
  3 1 7 2 4 6 9 8 5
  6 4 2 5 9 8 1 7 3



------------------- 8< ----------------------------------- 8<  -------
include Set.Make(struct type t = (int * int) * int let compare = compare end)
 
let (@) g f x = g (f x) and id x = x and sw f x y = f y x and zip x y = (x, y)
 
let fold9 f = let rec loop i = if i>8 then id else loop (i+1) @ f i in loop 0
 
let fold81 f = fold9 (fold9 @ (@) f @ zip)
 
let mark ((i,j),x as e) : t -> t =
  add e @ fold9 (fun k -> remove ((i/3*3 + k/3, j/3*3 + k mod 3), x) @
    remove ((i,j),k) @ remove ((i,k),x) @ remove ((k,j),x))
 
let search =
  let g p f s = fold (f @ sw mark s) (filter ((=) p @ fst) s) in
  fold81 g
 
let read () =
  let f p = Scanf.scanf "%d " (fun x -> if x>0 then mark (p,x-1) else
  id) in
  fold81 f (fold81 (fold9 @ ((@) add @ zip)) empty)
 
let print s () =
  let pr ((i,j),x) = Printf.printf "%d%c" (x+1) (if j=8 then '\n' else ' ') in
  iter pr s; print_newline ();;
 
search print (read ()) ();;

Yet another OCaml Webserver?! (was: Re: [Caml-list] Yet another sudoku solver (838 bytes))

[Oliver Bandel]

On Sat, Nov 19, 2005 at 12:41:32PM +0000, Marco Maggesi wrote:
> While we are there, this is my soduku solver.  It is not as efficient
> as the other solver proposed in this list, but it takes a fraction of
> seconds to compute a solution on a P4 anyway.
[...]


Well, this nice game is able to trigger the OCaml-programmers
very well. It's fun and it's kind of academic programming
experience, because it's about solving theoretical problems.


But where is the "yet another" or even "first" Ocaml webserver?

Where are other interesting applications, which can show people
the power of this language - especially safety/security of an application?

When looking at many progra,s and libs, written in C, or Web-Languages
like PHP and such stupid stuff, I always remind me the very often
readable security warnings - buffer overflows and so on.

But where's the OCaml programmers community (is there something like that?),
showing that it also goes in other ways?

When asking here for databases and other stuff, often comes the
answer: try to use <xyz> library and write a C-binding.

Nice idea, but too often most of the libraries are buggy and
many of them struggle with Buffer Overflow (and similar) problems.

For example pcre-lib, curl-lib, a lot of the graphic-format libs, ...
...even cryptographic libs... where you send your credit card
informations through the network... well....


So, it looks like OCaml is mainly used to write code that lives
on the base of C-libraries.
Not thatr it is a nice feature to have the possibility to have
C-libs included relatively easy.
But to rely completely on that feature (and relying on potentially
insecure libraries) instead of reimplementing save versions of these
libraries, this is IMHO not the best idea.

Well, I really hate slow applications, and so, if a C-application
is much faster than one written in OCaml, this would be not so fine,
but when a fast application works unsecure/unsafe, then it is much
worse.
Speed of OCaml-programs maybe could be enhanced, when the compiler
will be more optimized. But as long as OCaml is only used for
such toy-applications (not that this is bad, it's fine, but
what's about the "real world"?!), then there will be no need for
further optimizing.
And no interest in that language on a broader population...


So, where are the projects like a webserver in OCaml (the first one,
and another one, and yet another one...) as there are several
implementations of other programs written in C?!


What's about starting such a project?

Here are a lot of fine programmers on the list, but
all are doing some small academic toy-programming,
but when it comes to bigger stuff, no one will start
the first line of code...

...big projects are done in C or Java or C++ or maybe
Perl/Python.

OCaml?

No one knows, no one uses...


Just... just only some thoughts about it...


Ciao,
   Oliver

Re: Yet another OCaml Webserver?! (was: Re: [Caml-list] Yet another sudoku solver (838 bytes))

[Thomas Fischbacher]

On Sat, 19 Nov 2005, Oliver Bandel wrote:

> But where is the "yet another" or even "first" Ocaml webserver?

A much more interesting project (in my opinion) would be a DNS server in 
OCaml.

Rationale:

(1) To my knowledge, there are only two-and-a-half DNS server 
implementations that work reasonably well to be used for that job: 
BIND and djbdns. BIND was considered a major security catastrophe for a 
long time, and still is considered at least a design catastrophe by many.
djbdns is far slicker, but suffers from the problem that the major 
difference between djb and God seems to be that God knows he isn't djb.

It may be just me, but I think it's excessively rude to address this 
"every unix has its own place to install stuff" issue with "I am a big 
enough authority to decide upon the the introduction of new toplevel 
directories that resolve that point". Furthermore, djbdns is just another 
C application doing potentially dangerous stuff. Sure, djb is an excellent 
C hacker, but what if it eventually turned out that this "it's safe even 
though doing hairy stuff in an unsafe language because I know I am the 
best hacker in the world" hubris were unfounded?

At least, many people could sleep better if they could rely on their 
DNS server giving them better safety guarantees than that. I would 
especially *love* to see a well designed, properly implemented, 
peer-reviewed DNS server written in Haskell, but OCaml may also be a nice 
alternative. (Nevertheless, one should take a close look at many of those 
points which djb addresses with djbdns that the BIND folks did not care 
about.)

Erlang may be another interesting choice, which brings me to the last 
working DNS implementation I know: Eddie. This is the DNS half of a (now 
dead, I suppose) combined DNS/Webserver Erlang load balancing project. 
I managed to make it work, but it did not appear to be mature enough for 
real world use.

Aside from this, there is a CPAN Perl module named something 
like DNS::Server which sucks badly at dealing with recursive queries, as 
well as a Python DNS named "Oak", for which I can only find broken 
sources on the web. Anything else I missed?

-- 
regards,               tf@cip.physik.uni-muenchen.de              (o_
 Thomas Fischbacher -  http://www.cip.physik.uni-muenchen.de/~tf  //\
(lambda (n) ((lambda (p q r) (p p q r)) (lambda (g x y)           V_/_
(if (= x 0) y (g g (- x 1) (* x y)))) n 1))                  (Debian GNU)

Re: Yet another OCaml Webserver?! (was: Re: [Caml-list] Yet another sudoku solver (838 bytes))

[William Neumann]

On Nov 19, 2005, at 8:09 AM, Oliver Bandel wrote:

> But where's the OCaml programmers community (is there something  
> like that?),
> showing that it also goes in other ways?
>
> When asking here for databases and other stuff, often comes the
> answer: try to use <xyz> library and write a C-binding.
>
> Nice idea, but too often most of the libraries are buggy and
> many of them struggle with Buffer Overflow (and similar) problems.
>
> For example pcre-lib, curl-lib, a lot of the graphic-format libs, ...
> ...even cryptographic libs... where you send your credit card
> informations through the network... well....

Well, there are a number of reasons for this.  The biggest, I would  
guess is time.  Seriously, why would I want to re-implement, say,  
libcurl when one already exists and works well?  I don't have enough  
hours in the day to do that kind of evangelism *and* my day job.   
Number two on the list is that OCaml just isn't well suited to some  
of those domains.  I do crypto for a living (though more at the  
research level than the implementation level), and I know why things  
like cryptokit rely on C routines... Crypto and pure OCaml don't work  
well together because you don't get direct access to 32 and/or 64 bit  
words for manipulation.  It's less of a hassle when you just need  
simple operations like XORs which you can do on strings without too  
much overhead, but when you need something like addition mod 2^32,  
well... Int32 is a bit of a pain in the ass.

OCaml's great for the higher level stuff.  I just wrote a few Merkle- 
Damgard type constructions using stream parsers, and it's all very  
compact, pretty and elegant.  But if I want a final hash with a  
decent throughput, chances are I'll have to implement my compression  
function in C.  And you know what... that's OK.  Best tool for the  
job is usually a good motto.

William D. Neumann

"I eat T-bone steaks, I lift barbell plates, I'm sweeter than a
German chocolate cake. I'm the reflection of perfection, the number
one selection. I'm the man of the hour, the man with the power, too
sweet to be sour. The ladies' pet, the men's regret, where what you
see is what you get, and what you don't see, is better yet."

          --Superstar Billy Graham

Re: Yet another OCaml Webserver?! (was: Re: [Caml-list] Yet another sudoku solver (838 bytes))

[Oliver Bandel]

On Sat, Nov 19, 2005 at 08:55:57AM -0700, William Neumann wrote:
> On Nov 19, 2005, at 8:09 AM, Oliver Bandel wrote:
> 
> >But where's the OCaml programmers community (is there something  
> >like that?),
> >showing that it also goes in other ways?
> >
> >When asking here for databases and other stuff, often comes the
> >answer: try to use <xyz> library and write a C-binding.
> >
> >Nice idea, but too often most of the libraries are buggy and
> >many of them struggle with Buffer Overflow (and similar) problems.
> >
> >For example pcre-lib, curl-lib, a lot of the graphic-format libs, ...
> >...even cryptographic libs... where you send your credit card
> >informations through the network... well....
> 
> Well, there are a number of reasons for this.  The biggest, I would  
> guess is time.  Seriously, why would I want to re-implement, say,  
> libcurl when one already exists and works well?
[...]

... works well:

   "CAN-2005-0490 - Buffer Overflows in cURL bei Kerberos und NTLM
    Authentizizierung"



Ciao,
   Oliver

Re: Yet another OCaml Webserver?! (was: Re: [Caml-list] Yet another sudoku solver (838 bytes))

[William Neumann]

On Nov 19, 2005, at 9:05 AM, Oliver Bandel wrote:

> ... works well:
>
>    "CAN-2005-0490 - Buffer Overflows in cURL bei Kerberos und NTLM
>     Authentizizierung"

Fine.  So recompile it with something like this <http://www.acsa- 
admin.org/2004/abstracts/98.html>.  Buffer overflows are just one  
aspect of secure code, and there's no guarantee that a re- 
implementation of something like libcurl wouldn't be peppered with  
security flaws of a different color.

That's not to say it shouldn't be done.  And if it's a tool that you  
use a lot and that you think could be mode even better, then go for  
it, that's great.  Hell, I might even help out if the project  
interests me somehow.  But for now, if I need a one-off tool for  
doing something curl-esque, it's a much better use of my time to wrap  
an existing library.

William D. Neumann

"I eat T-bone steaks, I lift barbell plates, I'm sweeter than a
German chocolate cake. I'm the reflection of perfection, the number
one selection. I'm the man of the hour, the man with the power, too
sweet to be sour. The ladies' pet, the men's regret, where what you
see is what you get, and what you don't see, is better yet."

          --Superstar Billy Graham

Re: Yet another OCaml Webserver?! (was: Re: [Caml-list] Yet another sudoku solver (838 bytes))

[Jonathan Bryant]

Although this may sound like a shameless plug, it is not... :)

I wholeheartedly agree with your sentiments.  Although still within
academia, at least ATM, I am part of a group writing a full blown AI/web
crawler/search engine in OCaml.  I'm implementing a lot of the necessary
libraries (Client/Server, Clustering, Protocols, Persistance, etc.) by
hand in pure OCaml.  Now, maybe I'm just a masochist, but I'm
thouroughly enjoying myself while doing it.  Also, any of these
libraries should make it into the OpenSource world, and are being
designed, not as libraries specific to this task, but as general use
libraries with clean, clear interfaces and lots of documentation.

On the other hand, I will have to admit that there are some times that
you need C libraries.  Many times, in our project, we are using bindings
to an existing library to speed things up until we can go back and hand
roll our own.  Right now, we're using Curl, BerkeleyDB, and a few
others.  Also, things like BDB are fast because of C specific features. 
For example, the B tree is of a certain arity so that reading a "node"
involves only 1 disk read.  This is possible in OCaml, but extremely
difficult, not because of the read size, but because it is difficult to
find out the necessary filesystem information.  Eventually, we will
hand-roll our own, but, since it is already there, we are using it in
the interim.

Of course, for our web server we're using Apache, but we are writing our
CGI scripts in OCaml :).  I guess we're considering making a web
server.  With the aforementioned libraries at our disposal (once they
are complete ...  :), writing an Apache-killer web server would
definitely be very plausable.

There's some real-world code, for you.  A large scale project in OCaml
with minimal use of C libraries that takes advantage of the advanced
language features of OCaml.

Hope that helps,

-- Jonathan

On Sat, 2005-11-19 at 10:09, Oliver Bandel wrote:

[snip]


--Jonathan Bryant
  jtbryant@valdosta.edu
  Student Intern
  Unix System Operations
  VSU Information Technology

"Das Leben ohne Music ist einfach ein Irrtum, eine Strapaze, ein" Exil."
("Life without music is simply an error, a pain, an exile.")
--Frederich Nietzsche

"The three cardinal values of a programmer are laziness, impatience, and
hubris."
--Perl Man Page

Re: Yet another OCaml Webserver?! (was: Re: [Caml-list] Yet another sudoku solver (838 bytes))

[Jonathan Roewen]

> Where are other interesting applications, which can show people
> the power of this language - especially safety/security of an application?

This is a major goal of Desert Spring-Time. Whilst using bytecode, it
will probably not be very performant (ocamljit will help a small
amount here I think) compared to say a native code version.

However, the goals are: reliability, safety, and not so important:
portability. I think processors are more than fast enough these days
to accomodate a slower running kernel environment .. in fact, the
mpeg2 decoder project should help prove/disprove this theory.

Jonathan

Re: Yet another OCaml Webserver?! (was: Re: [Caml-list] Yet another sudoku solver (838 bytes))

[Oliver Bandel]

Hello Jonathan,


On Sun, Nov 20, 2005 at 09:09:29AM +1300, Jonathan Roewen wrote:
> > Where are other interesting applications, which can show people
> > the power of this language - especially safety/security of an application?
> 
> This is a major goal of Desert Spring-Time.

Well, this is one single project, but it's a good attempt. :)


> Whilst using bytecode, it

Why using bytecode?


> will probably not be very performant (ocamljit will help a small
> amount here I think) compared to say a native code version.
> 
> However, the goals are: reliability, safety, and not so important:
> portability.

If portability is not so important (for now?!),
why not using native code?


> I think processors are more than fast enough these days
> to accomodate a slower running kernel environment

Well, the kernel is very important... if it is slow,
so the whole system is slower... this is different
to a fast kernel/operating system, where only one
application is a littlebis slower.

But: if the kernel is less used and the main time the
program is in usermode (not kernel mode), then the
speed of the kernel is not sooooo much a big problem.
But the kernel is the part of the system, which is
central... so IMHO it should be very fast!

> .. in fact, the
> mpeg2 decoder project should help prove/disprove this theory.


well... IMHO graphic card drivers is not ideally done
in OCaml, and not in C... at least certain parts would
necessaryly be coded in Assembler...

...but if you can show the opposite, that's fine. ;-)

Ciao,
   Oliver

Re: Yet another OCaml Webserver?! (was: Re: [Caml-list] Yet another sudoku solver (838 bytes))

[skaller]

On Sat, 2005-11-19 at 21:19 +0100, Oliver Bandel wrote:
> Hello Jonathan,
> 
> 
> On Sun, Nov 20, 2005 at 09:09:29AM +1300, Jonathan Roewen wrote:
> > > Where are other interesting applications, which can show people
> > > the power of this language - especially safety/security of an application?
> > 
> > This is a major goal of Desert Spring-Time.
> 
> Well, this is one single project, but it's a good attempt. :)
> 
> 
> > Whilst using bytecode, it
> 
> Why using bytecode?

Because it's an OS .. dynamic loading is mandatory.

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net

Re: Yet another OCaml Webserver?! (was: Re: [Caml-list] Yet another sudoku solver (838 bytes))

[Jonathan Roewen]

> > Why using bytecode?
>
> Because it's an OS .. dynamic loading is mandatory.

This is indeed the reason =) Asmdynlink I read was slower than the
bytecode interpreter itself; another reason not to use ocamlopt.

>> But: if the kernel is less used and the main time the
>> program is in usermode (not kernel mode), then the
>> speed of the kernel is not sooooo much a big problem.

Apps are dynlink'd into the kernel. There is no user-space. No
syscalls -- use direct function calls. Dynlink will ensure
apps/drivers only access necessary modules.

>> well... IMHO graphic card drivers is not ideally done
>> in OCaml, and not in C... at least certain parts would
>> necessaryly be coded in Assembler...

Generally, drivers only need port IO and/or memory IO. Port IO is easy
(and is already done ... though resource allocation isn't), and Memory
IO could probably be done with the Bigarray module (PCI bus knows what
the range is).

Jonathan