[Caml-list] How to read three integers from a text-file... ?

[Caml-list] How to read three integers from a text-file... ?

[Jacek Chrzaszcz]

Hello list,

Is there a clean way (a one-liner) to read a constant number of
integers separated by whitespace from a text-file (or stdin) ?

I mean something like 
scanf("%d%d%d",&a,&b,&c) in C, or
readln(a,b,c) in Pascal

I know I can use String.index, Str.split or read char by char (this
sucks), but you have to admit the Pascal or even C versions are more
appealing.


I am asking this question, because our students want to use Ocaml for
competing in various programming contests, where the comfort and speed
(of programming) are essential.

Moreover in such contests the use of external libraries (Str) if often
forbiden.


If the easy way of doing this is missing, may I suggest adding it to
the standard library?


Jacek Chrzaszcz
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

RE: [Caml-list] How to read three integers from a text-file... ?

[Stefano Lanzavecchia]

> Moreover in such contests the use of external libraries (Str) if often
> forbidden.

Well, in that case the use of scanf should be prohibited too. Str is
part of the standard OCaml distributed library and it's in no way
different from scanf. While it's certainly easy to rewrite parts of Str
in OCaml (and the source code is available), your students would
probably find a bit harder to recode scanf in pure C...
-- 
WildHeart'2k2 - mailto:stf@apl.it
Homepage: currently offline

<<<Ne aishitara daremo ga Konna kodoku ni naru no? ---
   Hey If you fall in love Does everyone become this lonely?>>>

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] How to read three integers from a text-file... ?

[Tomasz Zielonka]

On Wed, Apr 24, 2002 at 12:44:37PM +0200, Stefano Lanzavecchia wrote:
> > Moreover in such contests the use of external libraries (Str) if often
> > forbidden.
> 
> Well, in that case the use of scanf should be prohibited too. Str is
> part of the standard OCaml distributed library and it's in no way
> different from scanf.

They are different with regard to typical contest rules, which are
simple (maybe too simple).

Those rules describe commands, which will be used to compile programs,
typically:

C        - gcc source.c
OCaml    - ocamlopt source.ml

The C program can use scanf, which is in libc. The OCaml program can't
use Str.

> While it's certainly easy to rewrite parts of Str in OCaml (and the
> source code is available),

Str source code is mainly C, not OCaml.

> your students would probably find a bit harder to recode scanf in pure
> C...

scanf source is available too and it is probably C.

And I wouldn't say that implementing regular expression matching library
is easier than implementing scanf.

regards,
tom

-- 
sig outdated
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] How to read three integers from a text-file... ?

[Jacques Garrigue]

From: Jacek Chrzaszcz <chrzaszcz@mimuw.edu.pl>

> Is there a clean way (a one-liner) to read a constant number of
> integers separated by whitespace from a text-file (or stdin) ?
> 
> I mean something like 
> scanf("%d%d%d",&a,&b,&c) in C, or
> readln(a,b,c) in Pascal

A clean way to do this is to use then Genlex module.

# #load"camlp4o.cma";;
# open Genlex;;
# let s = Genlex.make_lexer [] (Stream.of_channel stdin);;
val s : Genlex.token Stream.t = <abstr>
# match s with parser [< 'Int x; 'Int y; 'Int z >] -> (x, y, z);;
3 5 7
- : int * int * int = 3, 5, 7

If you don't want to use camlp4o.cma, it is possible with Stream.next,
but a bit more painful.

Cheers,

Jacques Garrigue
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] How to read three integers from a text-file... ?

[Tomasz Zielonka]

On Wed, Apr 24, 2002 at 08:16:16PM +0900, Jacques Garrigue wrote:
> From: Jacek Chrzaszcz <chrzaszcz@mimuw.edu.pl>
> 
> > Is there a clean way (a one-liner) to read a constant number of
> > integers separated by whitespace from a text-file (or stdin) ?
> > 
> > I mean something like 
> > scanf("%d%d%d",&a,&b,&c) in C, or
> > readln(a,b,c) in Pascal
> 
> A clean way to do this is to use then Genlex module.

You can also use ocamllex and that's what I did recently to read strings
of digits (up to 170 digits). The contest won't probably accept the .mll
file, but you can send the ocamllex output itself. Such lexer is much
faster than Genlex generated one.  Bad thing is that the code will be
cluttered with lexer arrays, etc.

tom

-- 
no sig
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

pervasives (was: Re: [Caml-list] How to read three integers from a text-file... ?)

[Chris Hecker]

I was about to answer, "why not just use read_int in a loop from the 
in_channel?", but then I looked and it's only defined on stdin (as is 
read_float).  read_line has input_line, but the others aren't 
symmetric.  Can we fix this and add input_int and input_float to 
Pervasives?  Relatively minor, but annoying to emulate.

Chris

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: pervasives (was: Re: [Caml-list] How to read three integers from a text-file... ?)

[Tomasz Zielonka]

On Wed, Apr 24, 2002 at 10:30:48PM -0700, Chris Hecker wrote:
> 
> I was about to answer, "why not just use read_int in a loop from the 
> in_channel?", but then I looked and it's only defined on stdin (as is 
> read_float).

val read_int : unit -> int
(** Flush standard output, then read one line from standard input
   and convert it to an integer. Raise [Failure "int_of_string"]
   if the line read is not a valid representation of an integer. *)

This function assumes that every integer is on a separate line. This is
rarely true in programming contests.

> Chris

tom

-- 
Tomek Zielonka <t.zielonka@students.mimuw.edu.pl>
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: pervasives (was: Re: [Caml-list] How to read three integers from a text-file... ?)

[Chris Hecker]

>This function assumes that every integer is on a separate line. This is
>rarely true in programming contests.

Ah, I missed the "read one line" part.  Interesting that print_int doesn't 
insert a newline but read_int eats one...another assymetry.  int_of_string 
also seems to require that the string be only the integer, so int_of_string 
"123 some more" excepts.

It seems like it might be useful to have the core simple types (string, 
int, float) have orthogonal reading and writing functions in 
Pervasives.  Maybe it's not worth the effort, though...

Chris


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: pervasives (was: Re: [Caml-list] How to read three integers from a text-file... ?)

[John Max Skaller]

Chris Hecker wrote:

>
>> This function assumes that every integer is on a separate line. This is
>> rarely true in programming contests.
>
>
> Ah, I missed the "read one line" part.  Interesting that print_int 
> doesn't insert a newline but read_int eats one...another assymetry.  
> int_of_string also seems to require that the string be only the 
> integer, so int_of_string "123 some more" excepts.
>
> It seems like it might be useful to have the core simple types 
> (string, int, float) have orthogonal reading and writing functions in 
> Pervasives.  Maybe it's not worth the effort, though... 

I have a philosophy .. a bit extreme perhaps .. I NEVER read anything
other than lines (or whole files). Always parse in-core. So the 'asymmetry'
doesn't worry me .. the existence of useless functions does though.
I'd get rid of all input other than read line/read file. Similarly,
though I'm slightly less pedantic here .. output should be formatted 
in-core.
So you only need one output function (print string).
I'd get rid of all the others .. and also get rid of printf ..

I can only site an example .. an academic compiler that printed
terms out  .. I had to rewrite reams of code
to generate strings when I needed to reroute the output ..
there was also a need to generate 'potential' output ..
diagnostic information that needed to be gleaned
to print an error message .. before it was known
if there was actually an error.

In-core formatting/parsing is sometimes slower
than doing the same job on output/input,
and may use more memory .. but the contexts where this is important are
fairly rare.

-- 
John Max Skaller, mailto:skaller@ozemail.com.au
snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia.
voice:61-2-9660-0850




-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

[Caml-list] input_line (Re: pervasives)

[Lauri Alanko]

On Sat, Apr 27, 2002 at 02:43:26PM +1000, John Max Skaller wrote:
> I have a philosophy .. a bit extreme perhaps .. I NEVER read anything
> other than lines (or whole files).

Vaguely related to this, I have some minor gripes about input_line.
Here's the implementation in 3.04:


let rec input_line chan =
  let n = input_scan_line chan in
  if n = 0 then                         (* n = 0: we are at EOF *)
    raise End_of_file
  else if n > 0 then begin              (* n > 0: newline found in buffer *)
    let res = string_create (n-1) in
    ignore (unsafe_input chan res 0 (n-1));
    ignore (input_char chan);           (* skip the newline *)
    res
  end else begin                        (* n < 0: newline not found *)
    let beg = string_create (-n) in
    ignore(unsafe_input chan beg 0 (-n));
    try
      beg ^ input_line chan
    with End_of_file ->
      beg
  end


It's obvious that this doesn't handle obnoxiously large newlineless
inputs very gracefully. Its complexity is quadratic and it's not tail
recursive. And worst of all, there are no limits on the size of string
to be created. So a maliciously designed huge input could blow either
the stack or the heap. I wouldn't want to use input_line in a network
application.

(All right, on 32-bit architectures input_line will terminate at ~16M
when string_create fails, but I wouldn't call that a solution.)

So here's an alternative implementation. It's tail recursive, its
amortized cpu usage is linear, and the space usage can be bounded:


exception Buffer_overflow of string

let expand_buf buf old_size expand =
  if old_size == 0 then
    string_create expand
  else
    let new_buf = string_create (old_size + expand) in
      string_blit buf 0 new_buf 0 old_size;
      new_buf

let rec input_bounded_line_to_buf chan buf offset maxlen =
  let n = input_scan_line chan in
    if n > maxlen + 1 || n < (-maxlen) then
      let err_buf = expand_buf buf offset maxlen in
	ignore (unsafe_input chan err_buf offset maxlen);
	raise (Buffer_overflow err_buf)
    else if n > 0 then
      let ret_buf = expand_buf buf offset (n - 1) in
	ignore (unsafe_input chan ret_buf offset (n - 1));
	ignore (input_char chan);
	ret_buf
    else if n < 0 then
      let m = (-n) in
      let new_offset = offset + m in
      let old_len = string_length buf in
      let new_buf = 
	if new_offset > old_len then
	  expand_buf buf offset (new_offset + old_len * 2)
	else
	  buf
      in
	ignore (unsafe_input chan new_buf offset m);
	input_bounded_line_to_buf chan new_buf new_offset (maxlen - m)
    else if offset = 0 then
      raise End_of_file
    else 
      expand_buf buf offset 0

let input_bounded_line chan maxlen = 
  input_bounded_line_to_buf chan "" 0 maxlen

let input_line chan = input_bounded_line chan max_int


I hope that something similar to this could be included in Pervasives in
the future.


Lauri Alanko
la@iki.fi
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] input_line

[Xavier Leroy]

> Vaguely related to this, I have some minor gripes about input_line.
> Here's the implementation in 3.04:
> It's obvious that this doesn't handle obnoxiously large newlineless
> inputs very gracefully. Its complexity is quadratic and it's not tail
> recursive.

input_line was reimplemented in the working sources to avoid the
quadratic behavior you mention.

> And worst of all, there are no limits on the size of string
> to be created. So a maliciously designed huge input could blow either
> the stack or the heap. I wouldn't want to use input_line in a network
> application.

I see your point, but there are other (most?) applications where you
really do not want to have any hard limits beyond available memory.

- Xavier Leroy
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] input_line

[Lauri Alanko]

On Tue, Apr 30, 2002 at 02:07:20PM +0200, Xavier Leroy wrote:
> > And worst of all, there are no limits on the size of string
> > to be created. So a maliciously designed huge input could blow either
> > the stack or the heap. I wouldn't want to use input_line in a network
> > application.
> 
> I see your point, but there are other (most?) applications where you
> really do not want to have any hard limits beyond available memory.

Well, strings already _have_ a hard limit on their size...

But on second thought, yes, it seems that networking applications do
need features that are beyond what can reasonably be expected from a
Pervasives function. For example, in addition to limiting memory usage,
I also need to implement timeouts. Since there is no way to
asynchronously interrupt threads[1], the only way to make sure a
thread never blocks indefinitely is to use nonblocking IO, which
complicates things a bit.

So I ended up writing my own IO interface on top of the Unix module.
What bothers me about this is that now I cannot use any library
functions that operate on (in|out)_channels. Moreover, I had to
implement basic buffering, although the channel implementations do that
already.

Why, therefore, is it not possible to create standard channels that are
backed by user-defined functions? This is pretty much a standard feature
in many languages, and it would make life easier in many ways.


Lauri Alanko
la@iki.fi

[1] Or so I gather. The Haskell folks have studied asynchronous
exceptions in PLDI '01 and implemented them in GHC. Perhaps their work
could be adapted for ocaml as well?
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] input_line

[Florian Hars]

Lauri Alanko wrote:
> So I ended up writing my own IO interface on top of the Unix module.

Have you had a lookt at the netchannels code from then ocamlnet project?
http://sourceforge.net/projects/ocamlnet the actual code is in the
CVS repository:
http://cvs.sourceforge.net/cgi-bin/viewcvs.cgi/ocamlnet/ocamlnet/src/netstring/

Yours, Florian Hars.
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] How to read three integers from a text-file... ?

[Tomasz Zielonka]

On Tue, Apr 23, 2002 at 12:41:49PM +0200, Jacek Chrzaszcz wrote:
> Hello list,

[Hello]    ;)

> Is there a clean way (a one-liner) to read a constant number of
> integers separated by whitespace from a text-file (or stdin) ?

For 'constant numbers' greater than 1 there are at least five
solutions:

1) Write function which will read 'n' ints from input and return a list
   of them. But that would be unsafe, inefficient and would cause 'this
   pattern-matching is not exhaustive' warnings in destructuring 'let'
   bindings.

2) Write several functions: read_1_int, read_2_ints, ..., read_5_ints,
   which will return tuples with appropriate number of ints. Safer but
   still inefficient (tuple allocation, copying) and a bit clumsy.

3) Create CamlP4 macro/(syntax extension) which will expand to
   'let's binding subsequent ints to given names. Something like:

   READINTS(a, b, c, d)

   (sorry, I know it looks like a CPP macro)

   expanded to:

   let a = get_int () in
   let b = get_int () in
   let c = get_int () in
   let d = get_int () in

4) Create mechanism dual to printf, but as far as I understand
   OCaml's printf, this would require extending typechecker.

5) Just 'n' times use a function which reads 1 integer from input.

Personally I prefer option 5.

I write

  let read_int = ()

at top of my program, to avoid using this standard OCaml function.
Then I define get_int function, which just reads characters one by one.

  get_int: unit -> int

When using such imperative function, one should be careful. OCaml's
evaluation order is not left to right, so following constructs may have
effects other than desired:

  let pair = (get_int (), get_int ())

  f (get_int ()) (get_int ())

> I know I can use String.index, Str.split or read char by char (this
> sucks), but you have to admit the Pascal or even C versions are more
> appealing.

Reading char by char sucks? Why? 

Scanf probably does it, and it isn't exactly _reading_ char by char
when you have buffered I/O.

I participated in online contest recently and I made some "research" in
integer reading :) 

I've even made benchmarks - the task was to read first integer from input
as 'n', sum following 'n' unsigned integers and print the result.  Here
are the times for n=200000 on PIII 850 (gcc ocamlopt 3.04).

program         time    description
-----------------------------------------------------------------------
c_scanf        0.201s - C scanf ("%d", ...
c_scanf4       0.173s - C scanf ("%d%d%d%d", ...
c_macro        0.095s - my C macro (using getchar())
c_macro2       0.037s - my C macro with input pre-loaded into array

ml_genlex      5.032s - Genlex, Genlex.npeek, List.map & List.fold_left
ml_genlex2     3.583s - Genlex with other sum function
ml_ocamllex    0.517s - ocamllex + int_of_string
ml_simple      0.100s - char by char tail-recursive reading function
ml_string2     0.061s - similar function, but with input pre-loading

Note that C programs were compiled without optimisation. With -O3
c_macro2 peforms even faster - 0m0.028s.

I think that ml_simple solution is satisfactory for such contests. It's
fast, simple and quite safe to use. I can send the source if someone's
interested.

> I am asking this question, because our students want to use Ocaml for
> competing in various programming contests, where the comfort and speed
> (of programming) are essential.

My simple solution is comfortable enough for me. 

Speed of execution is also important in contests - you rather don't
want to spend 5 seconds to just read the data.

> Jacek Chrzaszcz

tomek

-- 
Tomek Zielonka <t.zielonka@students.mimuw.edu.pl>
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] How to read three integers from a text-file... ?

[John Max Skaller]

>
>
>
>3) Create CamlP4 macro/(syntax extension) which will expand to
>
Oh, may I ask please that

1) the camlp4 manual should be part of the distribution now that camlp4 is
2) camlp4 should be described in the "tools" section of the manual,
   even if the description is only a reference to the camlp4 manual

-- 
John Max Skaller, mailto:skaller@ozemail.com.au
snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia.
voice:61-2-9660-0850




-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] How to read three integers from a text-file... ?

[Daniel de Rauglaudre]

Hi,

On Wed, Apr 24, 2002 at 11:23:16PM +0200, Tomasz Zielonka wrote:

> 3) Create CamlP4 macro/(syntax extension) which will expand to
>    'let's binding subsequent ints to given names. Something like:
> 
>    READINTS(a, b, c, d)

I think that it should be possible to have a Camlp4 syntax extension
to have the equivalent of the C function scanf. I can try to implement
that, if people are interested.

BTW, it is perfectly possible to write printf as a Camlp4 syntax
extension not using the special type "format". In such an implementation,
"printf" is a keyword always followed by a string. Camlp4 analyses the
string and generates calls to print_string, print_int, and so on. The
result is normally typed by OCaml.

-- 
Daniel de RAUGLAUDRE
daniel.de_rauglaudre@inria.fr
http://cristal.inria.fr/~ddr/
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] How to read three integers from a text-file... ?

[Markus Mottl]

On Thu, 25 Apr 2002, Daniel de Rauglaudre wrote:
> I think that it should be possible to have a Camlp4 syntax extension
> to have the equivalent of the C function scanf. I can try to implement
> that, if people are interested.
> 
> BTW, it is perfectly possible to write printf as a Camlp4 syntax
> extension not using the special type "format". In such an implementation,
> "printf" is a keyword always followed by a string. Camlp4 analyses the
> string and generates calls to print_string, print_int, and so on. The
> result is normally typed by OCaml.

These are interesting proposals! I am sure that others would appreciate
this very much, too...

Regards,
Markus Mottl

-- 
Markus Mottl                                             markus@oefai.at
Austrian Research Institute
for Artificial Intelligence                  http://www.oefai.at/~markus
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] How to read three integers from a text-file... ?

[Jérôme Marant]

On Thu, Apr 25, 2002 at 01:19:05PM +0200, Markus Mottl wrote:
> On Thu, 25 Apr 2002, Daniel de Rauglaudre wrote:
> > BTW, it is perfectly possible to write printf as a Camlp4 syntax
> > extension not using the special type "format". In such an implementation,
> > "printf" is a keyword always followed by a string. Camlp4 analyses the
> > string and generates calls to print_string, print_int, and so on. The
> > result is normally typed by OCaml.
> 
> These are interesting proposals! I am sure that others would appreciate
> this very much, too...

  Well, this would make a static printf rather that the well known printf
  from C, since the format string may be known only at runtime in some
  cases.

-- 
Jérôme Marant
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] How to read three integers from a text-file... ?

[Markus Mottl]

On Thu, 25 Apr 2002, Jérôme Marant wrote:
>   Well, this would make a static printf rather that the well known printf
>   from C, since the format string may be known only at runtime in some
>   cases.

Sure, but the current solution isn't very convenient in this respect
anyway. It's usually easiest to pass higher-order functions that handle
specific parts in a pattern (%t or %a) at runtime.

Regards,
Markus Mottl

-- 
Markus Mottl                                             markus@oefai.at
Austrian Research Institute
for Artificial Intelligence                  http://www.oefai.at/~markus
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] How to read three integers from a text-file... ?

[Chris Hecker]

>   Well, this would make a static printf rather that the well known printf
>   from C, since the format string may be known only at runtime in some
>   cases.

As Markus says, the Printf.printf doesn't work in this case anyway right 
now, since it happens completely at compile time, I believe.

Chris


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] How to read three integers from a text-file... ?

[John Prevost]

>>>>> "ch" == Chris Hecker <checker@d6.com> writes:

    ch> As Markus says, the Printf.printf doesn't work in this case
    ch> anyway right now, since it happens completely at compile time,
    ch> I believe.

Actually, this is not the case, though printf formats are limited in
what you can do with them.  (i.e. you may substitute, but not
combine.)

As an example:

# let fmt x = (x : ('a,'b,'c) format)

  let a = fmt "First: %d, Second: %d\n"
  let b = fmt "[1, %d; 2, %d]\n"
  let f fmt = Printf.printf fmt 10 10
  let _ = f a
  let _ = f b
  ;;

First: 10, Second: 10
[1, 10; 2, 10]
val fmt : ('a, 'b, 'c) format -> ('a, 'b, 'c) format = <fun>
val a : (int -> int -> unit, out_channel, unit) format = <abstr>
val b : (int -> int -> unit, out_channel, unit) format = <abstr>
val f : (int -> int -> 'a, out_channel, unit) format -> 'a = <fun>

The definition of fmt is just to provide a quick way to force a string
into the context of a format type--otherwise, the cimpiler would
assign the type string to that value.

So it is possible to do some small things with these formats.  A more
interesting strategy is to use formatting combinators:

let id x = x
let ( ** ) f g x = f (g x)

let str     k s x = k (s ^ x)
let int     k s x = k (s ^ string_of_int x)
let lit p x k s   = p k s x

let lis p   k s x = match x with
  | [] -> k (s ^ "[]")
  | _  ->
    let rec loop xs k s = match xs with
      | [x]   -> p (fun s -> k (s ^ "]")) s x
      | x::xs -> p (fun s -> loop xs k (s ^ ";")) s x
    in loop x k (s ^ "[")

let format p = p id ""

Which lets you do things like:

# format (int ** lit int 3) 5;;
- : string = "53"
# format (int ** lit str " -> " ** lis int) 5 [1;2;3;4;5];;
- : string = "5 -> [1;2;3;4;5]"

Of course, these combinators can be extended for other ways of
producing results, and you can add new formats later.  So, it's more
extensible than the current printf is.  Quite nice, really.

John.
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] How to read three integers from a text-file... ?

[Jacques Garrigue]

From: Chris Hecker <checker@d6.com>
> 
> >   Well, this would make a static printf rather that the well known printf
> >   from C, since the format string may be known only at runtime in some
> >   cases.
> 
> As Markus says, the Printf.printf doesn't work in this case anyway right 
> now, since it happens completely at compile time, I believe.

Type-checking is completely at compile time, but you can define your
format independently if you want:

# let fmt : (_,_,_) format = "Hello %s, it's %d:%d.\n";;
val fmt : (string -> int -> int -> 'a, 'b, 'a) format = <abstr>
# Printf.printf fmt "Chris" 9 30;;
Hello Chris, it's 9:30.

Of course this could be done in camlp4 also. The only advantage of the
current approach is that the internal representation of the format is
still a string, which is kind of memory-efficient.

Exercise to the interested reader:
Define a function which, given a string and a concrete representation
of its format type, checks whether the string conforms to the type.
To make it more useful, the concrete representation used should
include the format type in its type, using phantom types.

val check_format : ('a, 'b) format_type -> string -> bool
val make_format : ('a, 'b) format_type -> string -> ('a, 'c, 'b) format

# make_format (arr string (arr int (arr int null))) "Hello %s, it's %d:%d.\n";;
val fmt : (string -> int -> int -> 'a, 'b, 'a) format = <abstr>

Cheers,

Jacques Garrigue
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] How to read three integers from a text-file... ?

[Jérôme Marant]

On Fri, Apr 26, 2002 at 08:32:44AM +0900, Jacques Garrigue wrote:
> From: Chris Hecker <checker@d6.com>
> > 
> > >   Well, this would make a static printf rather that the well known printf
> > >   from C, since the format string may be known only at runtime in some
> > >   cases.
> > 
> > As Markus says, the Printf.printf doesn't work in this case anyway right 
> > now, since it happens completely at compile time, I believe.
> 
> Type-checking is completely at compile time, but you can define your
> format independently if you want:
> 
> # let fmt : (_,_,_) format = "Hello %s, it's %d:%d.\n";;
> val fmt : (string -> int -> int -> 'a, 'b, 'a) format = <abstr>
> # Printf.printf fmt "Chris" 9 30;;
> Hello Chris, it's 9:30.

  Jacques,

  Would it be difficult to add arguments reordering to printf like:
  (we already talked about this in previous messages)
 
    printf " %2$d %1$s " 1 "hello";;

  Which gives:

    hello 1


  Thanks.

-- 
Jérôme Marant
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] How to read three integers from a text-file... ?

[Jacques Garrigue]

From: Chris Hecker <checker@d6.com>
> 
> >   Well, this would make a static printf rather that the well known printf
> >   from C, since the format string may be known only at runtime in some
> >   cases.
> 
> As Markus says, the Printf.printf doesn't work in this case anyway right 
> now, since it happens completely at compile time, I believe.

Type-checking is completely at compile time, but you can define your
format independently if you want:

# let fmt : (_,_,_) format = "Hello %s, it's %d:%d.\n";;
val fmt : (string -> int -> int -> 'a, 'b, 'a) format = <abstr>
# Printf.printf fmt "Chris" 9 30;;
Hello Chris, it's 9:30.

Of course this could be done in camlp4 also. The only advantage of the
current approach is that the internal representation of the format is
still a string, which is kind of memory-efficient.

Exercise to the interested reader:
Define a function which, given a string and a concrete representation
of its format type, checks whether the string conforms to the type.
To make it more useful, the concrete representation used should
include the format type in its type, using phantom types.

val check_format : ('a, 'b) format_type -> string -> bool
val make_format : ('a, 'b) format_type -> string -> ('a, 'c, 'b) format

# make_format (arr string (arr int (arr int null))) "Hello %s, it's %d:%d.\n";;
val fmt : (string -> int -> int -> 'a, 'b, 'a) format = <abstr>

Cheers,

Jacques Garrigue
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] How to read three integers from a text-file... ?

[Jacques Garrigue]

> Exercise to the interested reader:
> Define a function which, given a string and a concrete representation
> of its format type, checks whether the string conforms to the type.
> To make it more useful, the concrete representation used should
> include the format type in its type, using phantom types.
> 
> val check_format : ('a, 'b) format_type -> string -> bool
> val make_format : ('a, 'b) format_type -> string -> ('a, 'c, 'b) format
> 
> # make_format (arr string (arr int (arr int null))) "Hello %s, it's %d:%d.\n";;
> val fmt : (string -> int -> int -> 'a, 'b, 'a) format = <abstr>

Since nobody answered to the challenge, here is a solution (only
partial, qualifiers are not supported).

Syntax slightly differs.

# open Checkfmt;;
# check_printf (apply (int null)) "Price is %a or %i.\n"
    (fun c -> Printf.fprintf c "%f") 1.2 3;;
Price is 1.200000 or 3.
- : unit = ()

Here is the code. Note that I use Obj.magic only once.

module Checkfmt : sig
  type ('a, 'b, 'c) format_type
  val null : ('a, 'b, 'a) format_type
  val int : ('a, 'b, 'c) format_type -> (int -> 'a, 'b, 'c) format_type
  val string :
      ('a, 'b, 'c) format_type -> (string -> 'a, 'b, 'c) format_type
  val char : ('a, 'b, 'c) format_type -> (char -> 'a, 'b, 'c) format_type
  val float : ('a, 'b, 'c) format_type -> (float -> 'a, 'b, 'c) format_type
  val bool : ('a, 'b, 'c) format_type -> (bool -> 'a, 'b, 'c) format_type
  val apply :
      ('a, 'b, 'c) format_type ->
      (('b -> 'd -> 'c) -> 'd -> 'a, 'b, 'c) format_type
  val output :
      ('a, 'b, 'c) format_type -> (('b -> 'c) -> 'a, 'b, 'c) format_type
  val check_format : ('a, 'b, 'c) format_type -> string -> bool
  val make_format : ('a, 'b, 'c) format_type -> string -> ('a, 'b, 'c) format
  val check_printf : ('a, out_channel, unit) format_type -> string -> 'a
end = struct
type ('a,'b, 'c) format_type =
    Null
  | Int of ('a, 'b, 'c) format_type
  | String of ('a, 'b, 'c) format_type
  | Char of ('a, 'b, 'c) format_type
  | Float of ('a, 'b, 'c) format_type
  | Bool of ('a, 'b, 'c) format_type
  | Apply of ('a, 'b, 'c) format_type
  | Output of ('a, 'b, 'c) format_type

let null : ('a, 'b, 'a) format_type = Null
let int (x : ('a, 'b, 'c) format_type) =
  (Int x :> (int -> 'a, 'b, 'c) format_type)
let string (x : ('a, 'b, 'c) format_type) =
  (String x :> (string -> 'a, 'b, 'c) format_type)
let char (x : ('a, 'b, 'c) format_type) =
  (Char x :> (char -> 'a, 'b, 'c) format_type)
let float (x : ('a, 'b, 'c) format_type) =
  (Float x :> (float -> 'a, 'b, 'c) format_type)
let bool (x : ('a, 'b, 'c) format_type) =
  (Bool x :> (bool -> 'a, 'b, 'c) format_type)
let apply (x : ('a, 'b, 'c) format_type) =
  (Apply x :> (('b -> 'd -> 'c) -> 'd -> 'a, 'b, 'c) format_type)
let output (x : ('a, 'b, 'c) format_type) =
  (Apply x :> (('b -> 'c) -> 'a, 'b, 'c) format_type)

let check_format fmtype fmt =
  let rec check pos fmtype =
    if pos >= String.length fmt then fmtype = Null else
    try
      let pos = String.index_from fmt pos '%' + 1 in
      if pos >= String.length fmt then invalid_arg "check_format";
      let c = fmt.[pos] in
      match c, fmtype with
        '%', _ -> check (pos+1) fmtype
      | ('d'|'i'|'u'|'x'|'X'|'o'), Int fmtype -> check (pos+1) fmtype
      | 's', String fmtype -> check (pos+1) fmtype
      | 'c', Char fmtype -> check (pos+1) fmtype
      | ('f'|'e'|'E'|'g'|'G'), Float fmtype -> check (pos+1) fmtype
      | 'b', Bool fmtype -> check (pos+1) fmtype
      | 'a', Apply fmtype -> check (pos+1) fmtype
      | 't', Output fmtype -> check (pos+1) fmtype
      | _ -> false
    with Not_found ->
      fmtype = Null
  in
  check 0 fmtype

let make_format (fmtype : ('a,'b,'c) format_type) fmt =
  if check_format fmtype fmt then (Obj.magic fmt : ('a,'b,'c) format)
  else failwith "make_format"

let check_printf fmtype fmt =
  Printf.printf (make_format fmtype fmt)
end
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] How to read three integers from a text-file... ?

[Daniel de Rauglaudre]

Hi,

On Thu, Apr 25, 2002 at 01:33:44PM +0200, Jérôme Marant wrote:

>   Well, this would make a static printf rather that the well known printf
>   from C, since the format string may be known only at runtime in some
>   cases.

I did not mean that we are going to change the current printf into
a syntax extension. I just said that it is possible. The current
implementation is very practical, since you can manipulate format
variables, and though it supposes a strange typing. With a syntax
extension, you would not have this strange typing and that ability
to use format variables: it is just an interesting exercise. I
did it one day, but I did not terminated it.

About scanf as a Camlp4 syntax extension, I just looked at it: not
a so interesting exercice, actually. We need library functions reading
integers or strings (but not systematically reading a line), skipping
spaces and so on. With a good module with these functions, we are
very close to the result, and Camlp4 brings very few more.

-- 
Daniel de RAUGLAUDRE
daniel.de_rauglaudre@inria.fr
http://cristal.inria.fr/~ddr/
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] How to read three integers from a text-file... ?

[Francois Pottier]

On Wed, Apr 24, 2002 at 11:23:16PM +0200, Tomasz Zielonka wrote:
> 
> 4) Create mechanism dual to printf, but as far as I understand
>    OCaml's printf, this would require extending typechecker.
> 

No, it does not. Check out Olivier Danvy's paper `Functional Unparsing':

  http://www.brics.dk/RS/98/12/

It describes a very nice way of programming `printf' within ML's type
system. `scanf' could be handled in a similar way. Furthermore, this approach
yields code that is claimed to be more efficient than O'Caml's current
`printf' implementation (because the overhead of interpreting format strings
is lower). Lastly, it scales up to more expressive format directives, such as
a directive for printing a list.

It might be worth adding a module that implements Danvy-style `printf' and
`scanf' to the standard library. Has anyone written such a module already?
Otherwise, I might consider doing it.

-- 
François Pottier
Francois.Pottier@inria.fr
http://pauillac.inria.fr/~fpottier/
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] How to read three integers from a text-file... ?

[Dave Berry]

At 08:44 29/04/2002, Francois Pottier wrote:
>Check out Olivier Danvy's paper `Functional Unparsing':
>
>  http://www.brics.dk/RS/98/12/
>
>It describes a very nice way of programming `printf' within ML's type
>system. `scanf' could be handled in a similar way. 

Scanf would be a little harder.  For printf (actually Danvy describes
sprintf), each combinator extends a string with either the next string
literal or the string representation of the next argument, using string
catenation.  For scanf, the result type has to be a tuple.  Therefore you
need a function that takes an arbitrary n-tuple (the values read so far)
and returns an (n+1)-tuple of those values plus the value read by the
current combinator.  Most implementations of ML do not provide such a function.

There are extensions of ML type systems that do include this operation.  I
don't know whether it is included in the record calculus that underlies
Objective ML (the object part of OCaml).  Or how easy it would be to add.

Such an operation would be useful for scanning functions in general.  E.g.
it could be used in a regexp library for handling \(...\) pairs.

>Furthermore, this approach
>yields code that is claimed to be more efficient than O'Caml's current
>`printf' implementation (because the overhead of interpreting format strings
>is lower). Lastly, it scales up to more expressive format directives, such as
>a directive for printing a list.

On the other hand, once you've converted:
	sprintf("%d is %s\n", i, s)
into:
	format(int oo lit " is " oo str oo eol) i s
you might just as well write:
	concat [int i; " is "; s; "\n"]
which is shorter, and arguably easier to read, than Danvy's version.  This
is the approach taken in the SML Basis Library.  It would be interesting to
know how the performance of this approach compares with Danvy's approach.

Dave.
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] How to read three integers from a text-file... ?

[Francois Pottier]

Hi Dave,

On Tue, Apr 30, 2002 at 12:07:38PM +0100, Dave Berry wrote:
>
> Scanf would be a little harder. [...] For scanf, the result type has to be a
> tuple.

No, it doesn't, if you program in CPS style. Instead of returning a tuple,
return a function that expects a continuation, and applies it successively to
several values. You obtain the same effect, except in that case, ``tuple
concatenation'' becomes typable. A similar trick was used by Didier Rémy in
``Typing record concatenation for free'' back in 1993.

The function that concatenates CPS-encoded tuples is as follows:

  let (++) tuple1 tuple2 k =
    tuple2 (tuple1 k)

A simple ``tuple'' that contains one integer (read from standard input
when the tuple is queried) is

  let int k =
    k (int_of_string (input_line stdin))

You can then read, say, three integers from standard input and compute
something out of them in the following way:

  (int ++ int ++ int) (fun x y z -> x + y * z)

As far as I can tell, this approach scales up to format specifiers
other than `int'.

> Such an operation would be useful for scanning functions in general.  E.g.
> it could be used in a regexp library for handling \(...\) pairs.

Yes, it would be very nice to use this approach for regexps. Unfortunately,
Danvy's encoding relies on the fact that the format specification is *not*
a string. So, it would be possible to devise something along these lines,
but the good old regexp syntax would probably have to be dropped.

-- 
François Pottier
Francois.Pottier@inria.fr
http://pauillac.inria.fr/~fpottier/
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] How to read three integers from a text-file... ?

[T. Kurt Bond]

Francois Pottier, speaking of using a "Functional Unparsing" like 
approach (cps) to regexps writes:

> Yes, it would be very nice to use this approach for regexps. Unfortunately,
> Danvy's encoding relies on the fact that the format specification is *not*
> a string. So, it would be possible to devise something along these lines,
> but the good old regexp syntax would probably have to be dropped.

That is not necessarily a bad thing.  The classic string-based regexp
syntax has often been criticized for unreadability.  Scsh's SRE
sexp-based regexp syntax may be an improvement.  I imagine that
something using this a cps approach could be an improvement, since the
"Functional Unparsing" approach to printing seems to provide a
reasonable notation.
-- 
T. Kurt Bond, tkb@tkb.mpl.com

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] How to read three integers from a text-file... ?

[Dave Berry]

At 14:20 30/04/2002, Francois Pottier wrote:
>The function that concatenates CPS-encoded tuples is as follows:
>
>  let (++) tuple1 tuple2 k =
>    tuple2 (tuple1 k)
>
>A simple ``tuple'' that contains one integer (read from standard input
>when the tuple is queried) is
>
>  let int k =
>    k (int_of_string (input_line stdin))

Neat.  In practice you'd want to thread the input stream (or possibly the
input operation) through the combinators.

>You can then read, say, three integers from standard input and compute
>something out of them in the following way:
>
>  (int ++ int ++ int) (fun x y z -> x + y * z)

Perhaps it would be neat to have some syntactic sugar for this, e.g.:

	bind <pat> = <exp1>  in <exp2> end

as sugar for

	<exp1> (fun <pat> -> <exp2>)

(This is simply the opposite application order from the expansion of "let"
bindings:
	let <pat> = <exp1> in <exp2> end
 is sugar for
	(fun <pat> -> <exp2>) (<exp1>).
Of course, the types are different, and "let" bindings also generalise type
variables).

Dave.]


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] How to read three integers from a text-file... ?

[Jocelyn Sérot]

Le mardi 30 avril 2002, à 01:07 PM, Dave Berry a écrit :

> At 08:44 29/04/2002, Francois Pottier wrote:
>> Check out Olivier Danvy's paper `Functional Unparsing':
>>
>>  http://www.brics.dk/RS/98/12/
>>
>> It describes a very nice way of programming `printf' within ML's type
>> system. `scanf' could be handled in a similar way.
>
> Scanf would be a little harder.  For printf (actually Danvy describes
> sprintf), each combinator extends a string with either the next string
> literal or the string representation of the next argument, using string
> catenation.  For scanf, the result type has to be a tuple.  Therefore 
> you
> need a function that takes an arbitrary n-tuple (the values read so far)
> and returns an (n+1)-tuple of those values plus the value read by the
> current combinator.  Most implementations of ML do not provide such a 
> function.
>
> There are extensions of ML type systems that do include this 
> operation.  I
> don't know whether it is included in the record calculus that underlies
> Objective ML (the object part of OCaml).  Or how easy it would be to 
> add.
>

Sorry to jump in the middle of this discussion, but your last remark on 
"extensible
n-tuples" drew my attention (i use to need this kind of thing in a 
completely different
context). Can you provide references on these extensions of ML type 
systems ?
Also, if s/o knows the answer to your last question (whether this has 
been implemented in
OCaml or how hard it would be to add), i'd very happy to know !

Thanks,

J. Sérot

--
E-mail: Jocelyn.Serot@l_a_s_m_e_a.u_n_i_v-bpclermont.fr
S-mail: LASMEA - UMR 6602 CNRS, Universite Blaise Pascal, 63177 Aubiere 
cedex
Tel: +33.(0)4.73.40.73.30 - Fax: +33.(0)4.73.40.72.62
http://wwwlasmea.univ-bpclermont.fr/Personnel/Jocelyn.Serot/Welcome.html
Valid e-mail: remove underscores (sorry, this is prevention against junk 
mail)
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Extensible tuple types

[Francois Pottier]

On Tue, Apr 30, 2002 at 04:42:01PM +0200, Jocelyn Sérot wrote:
> 
> Sorry to jump in the middle of this discussion, but your last remark on 
> "extensible
> n-tuples" drew my attention (i use to need this kind of thing in a 
> completely different
> context). Can you provide references on these extensions of ML type 
> systems ?

Tuples can be viewed as records whose field labels are integers, rather than
names. (In particular, this means that tuple fields do not commute, contrary
to record fields.) Records can be typed in a flexible way using rows; see
Didier Rémy's papers, for instance ``Type Inference for Records in a Natural
Extension of ML''. In the case of tuples, it's possible to use a variant of
rows -- I'll call them ``sequences'' -- to describe an infinite sequence of
types. Their syntax is given by

  s ::= 's | t; s | all(t)

where t stands for a type. 's is a ``sequence variable''. t; s is a sequence
whose first component is t and whose other components are listed by s. all(t)
is the sequence where every component is t.

As in the case of records, we introduce type constructors Absent (0-ary) and
Present (unary) to tell which components are present/absent in a tuple. We
also introduce a ``tuple'' type constructor, whose argument is a sequence;
that is, (s) is the type of tuples whose contents is described by the sequence
s.

Then, you can give types to the basic operations on tuples, as follows.

The empty tuple has type (all(Absent)), for it has no components.

The operation which accepts any tuple, of length at least k, and returns
its k-th component, has type

  forall 'a_1, ..., 'a_k, 's.
    ('a_1; ...; 'a_{k-1}; Present('a_k); 's) -> 'a_k

The operation which accepts any tuple and adds a new component in front
of it has type

  forall 'a, 's.
    'a -> ('s) -> (Present('a); 's)

Now, for the whole thing to work out in an extension of ML, you need to make
sure that unification of sequences is decidable. This seems straightforward;
the cases of interest are decomposition:

  t1;s1 = t2; s2 reduces to t1 = t2 and s1 = s2

and expansion of uniform sequences:

  all(t1) = t2; s2 reduces to t1 = t2 and all(t1) = s2

One slightly inelegant aspect of this approach is the fact that there
are empty types, such as (Absent;Present(int);all(Absent)). It's
impossible, given the operations above, to build a value of this
type. However, I can imagine situations where such types could
actually be of some use, e.g. if you add coercions of type

  forall 'a_1, ..., 'a_k, 's.
    ('a_1; ...; 'a_{k-1}; 'a_k; 's) -> ('a_1; ...; 'a_{k-1}; Absent; 's)

then you gain the ability to forbid access to certain fields
within a tuple.

After writing this far, I realize that it's possible to simplify further
by considering *finite* sequences and replacing the form all(t) with a
simple ``nil'' sequence constructor, representing an empty sequence. Then,
you can suppress Absent and Present, and you no longer have ``tuples with
holes'' as above. My original presentation was biased because I started
from rows, which represent infinite collections.

These ``sequences'' haven't been widely used in the literature; the only
instance I know of is the use of finite sequences to describe the structure of
stacks in Morrisett et al's STAL (stack-based assembly language). In their
setting, the key point is the ability to universally quantify over sequence
variables, making all but a portion of the stack abstract.

I hope this helps,

-- 
François Pottier
Francois.Pottier@inria.fr
http://pauillac.inria.fr/~fpottier/
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Extensible tuple types

[Alain Frisch]

On Thu, 2 May 2002, Francois Pottier wrote:

> On Tue, Apr 30, 2002 at 04:42:01PM +0200, Jocelyn Sérot wrote:
> >
> > Sorry to jump in the middle of this discussion, but your last remark on
> > "extensible
> > n-tuples" drew my attention (i use to need this kind of thing in a
> > completely different
> > context). Can you provide references on these extensions of ML type
> > systems ?
>
> Tuples can be viewed as records whose field labels are integers, rather than
> names. (In particular, this means that tuple fields do not commute, contrary
> to record fields.) Records can be typed in a flexible way using rows; see
> Didier Rémy's papers, for instance ``Type Inference for Records in a Natural
> Extension of ML''. In the case of tuples, it's possible to use a variant of
> rows -- I'll call them ``sequences'' -- to describe an infinite sequence of
> types.

I don't understand what this encoding of extensible tuples allows,
compared to the simple minded solution [the type of an n-typle is
(t1,(t2,...(tn,unit)...)) ]


> The operation which accepts any tuple, of length at least k, and returns
> its k-th component, has type
>
>   forall 'a_1, ..., 'a_k, 's.
>     ('a_1; ...; 'a_{k-1}; Present('a_k); 's) -> 'a_k

fun (x1,(x2,...(xk,_)...)) -> xk

> The operation which accepts any tuple and adds a new component in front
> of it has type
>
>   forall 'a, 's.
>     'a -> ('s) -> (Present('a); 's)


fun x c -> (x,c)


-- Alain

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Extensible tuple types

[Francois Pottier]

On Thu, May 02, 2002 at 11:42:35AM +0200, Alain Frisch wrote:
> 
> I don't understand what this encoding of extensible tuples allows,
> compared to the simple minded solution [the type of an n-typle is
> (t1,(t2,...(tn,unit)...)) ]

You're right -- and I should think more before I write -- it's
essentially the same solution. You do need to distinguish the
kind of sequences from the kind of types, though (that is, to
distinguish sequence extension ; from the product * and the
empty sequence nil from the unit type), otherwise you can't
distinguish a tuple from a cascade of pairs. But, apart from
that, you're right, it's the same thing.

-- 
François Pottier
Francois.Pottier@inria.fr
http://pauillac.inria.fr/~fpottier/
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] How to read three integers from a text-file... ?

[Dave Berry]

At 16:42 30/04/2002, Jocelyn Sérot wrote:
>Sorry to jump in the middle of this discussion, but your last remark on 
>"extensible n-tuples" drew my attention (i use to need this kind of thing
in a 
>completely different context). Can you provide references on these
>extensions of ML type systems ?

Hi Jocelyn,

I give some references below, but I have to add several caveats to my
remarks.  I don't have all these papers, so I can't check exactly what they
cover.  I believe they include similar operations on labelled records, and
these can be mapped to tuples by the SML technique of defining tuples as
records with numeric labels.  Whether that's the best approach is another
question; possibly it would be simpler to represent them as nested pairs,
as Alain Frisch suggested.  Finally, I'm not sure whether all these papers
gave type systems that were extensions of ML.

Anyway, here are the papers I had in mind.  Didier's work went on to become
Objective ML (which is why I wondered whether this operation was already
available in the system underlying OCaml).  Some of the other authors are
active on this list, and might be able to tell you more accurately whether
their work is relevant.

Dave.

Luca Cardelli and John C. Mitchell, "Operations on records", DEC SRC,
August 1989.

Mitchell Wand, "Type inference for record concatenation and multiple
inheritance", LICS 1989.

Didier Remy, "Typechecking records in a natural extension of ML", POPL 1989.

Robert Harper and Benjamin Pierce, "A record calculus based on symmetric
concatenation", POPL 1991.  [N.b. Symmetric concatenation is more complex
then simple record extension]

Atsushi Ohori, "A compilation method for ML-style polymorphic record
calculi", POPL 1992.

Didier Remy, "Typing record concatenation for free", POPL 1992.







-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] How to read three integers from a text-file... ?

[Eray Ozkural]

On Saturday 04 May 2002 00:58, Dave Berry wrote:
>
> Luca Cardelli and John C. Mitchell, "Operations on records", DEC SRC,
> August 1989.

Cardelli had a book on Object Calculus. Do you think that is a good book?

Thanks,

-- 
Eray Ozkural (exa) <erayo@cs.bilkent.edu.tr>
Comp. Sci. Dept., Bilkent University, Ankara
www: http://www.cs.bilkent.edu.tr/~erayo  Malfunction: http://mp3.com/ariza
GPG public key fingerprint: 360C 852F 88B0 A745 F31B  EA0F 7C07 AE16 874D 539C

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] How to read three integers from a text-file... ?

[Florian Hars]

Dave Berry wrote:
> I give some references below, but I have to add several caveats to my
> remarks.  I don't have all these papers, so I can't check exactly what they
> cover.

Just in case someone has not yet found this extremely useful site:
You can always find literature related to some topic if you look at
citeseer. Say, you start with one item from Dave's list like
http://citeseer.nj.nec.com/remy91type.html
and then surf around along the links to related, cited or similar
documents. But don't waste you whole day there :-).

Yours, Florian.
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

[Caml-list] Danvy "Functional Unparsing" style output in OCaml [was: How to read three integers from a text-file... ?]

[T. Kurt Bond]

Francois Pottier writes:
> Check out Olivier Danvy's paper `Functional Unparsing':
> 
>   http://www.brics.dk/RS/98/12/
> 
> It describes a very nice way of programming `printf' within ML's type
> system. `scanf' could be handled in a similar way. Furthermore, this approach
> yields code that is claimed to be more efficient than O'Caml's current
> `printf' implementation (because the overhead of interpreting format strings
> is lower). Lastly, it scales up to more expressive format directives, such as
> a directive for printing a list.
> 
> It might be worth adding a module that implements Danvy-style `printf' and
> `scanf' to the standard library. Has anyone written such a module already?
> Otherwise, I might consider doing it.

Back during an earlier discussion of Danvy-style output (probably on
this) I implemented a simple module for this (possibly starting from
some code that flew by on the list).

This round of discussion prompted me to go back and finish it up and
knock of a few of the rough edges and package it up.  Here's the README:

Cpsio is an Objective Caml implementation of the
continuation-passing-style output from Olivier Danvy's paper
Functional Unparsing.  It is available from:

   http://tkb.mpl.com/~tkb/software.html

The distribution is a gzipped tar file. It includes two modules:

   + Cpsio, which has a format function comparable to sprintf; and

   + Cpsio_exp, which has format_string, format_out, and
     format_err functions comparable to sprintf, printf, and
     eprintf, and a format function that allows the user to
     specify an accumulator/output function and an initial value
     (the later function is used to build the three previous
     functions and is available to clients for use with
     client-defined accumualtor/output functions).

Both modules have (rough) Ocamldoc documentation. The distribution
also includes test/example/benchmark programs for both Cpsio and Cpsio_exp,
and benchmark programs for comparing against OCaml and C
printf-style output. Perfomance with the bytecode compiler mostly
seems slightly faster than the OCaml printf, while performance with
the native code compiler seems to range from slower than the OCaml
printf to barely faster than the OCaml printf.

Deficiencies
   + Despite the "io" in the name, it unfortunately does not
     include input at this time, just output.
   + The Makefile is weak and does not have an install target.

I do not claim that this code is most elegant or most efficent
implementation of this idea.  

I would welcome comments on the code.

This software is in the public domain.

-- 
T. Kurt Bond, tkb@tkb.mpl.com

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

[Caml-list] RE: Danvy "Functional Unparsing" style output in OCaml

[T. Kurt Bond]

Back on April 30th, 2002, I wrote:

> Back during an earlier discussion of Danvy-style output (probably on
> this [mailing list]) I implemented a simple module for this
> (possibly starting from some code that flew by on the list).
[...]
> Cpsio is an Objective Caml implementation of the
> continuation-passing-style output from Olivier Danvy's paper
> Functional Unparsing.  It is available from:
> 
>    http://tkb.mpl.com/~tkb/software.html

I've updated the software slightly and included the results and a
short explanation (in postscript and PDF) on that page of some
benchmarking I did that shows that the Cpsio functions are faster than
the equivalent OCaml printf functions in byte-code, and often faster
in native-code, despite doing more garbage collecting.  Results are
also compared to the equivalent C printf functions.

The web page again is:

    http://tkb.mpl.com/~tkb/software.html
-- 
T. Kurt Bond, tkb@tkb.mpl.com

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

[Caml-list] "Functional Unparsing" benchmark results links fixed [Was: Danvy "Functional Unparsing" style output in OCaml]

[T. Kurt Bond]

I've fixed the broken links to postscript and PDF versions of the
results of benchmarking "Functional Unparsing" style output functions
against the equivalent O'Caml and C printf functions.

I apologize for the inconvenience, and thank those who pointed out the
problem.

Earlier today I wrote:
> I've updated the software slightly and included the results and a
> short explanation (in postscript and PDF) on that page of some
> benchmarking I did that shows that the Cpsio functions are faster than
> the equivalent OCaml printf functions in byte-code, and often faster
> in native-code, despite doing more garbage collecting.  Results are
> also compared to the equivalent C printf functions.
> 
> The web page again is:
> 
>     http://tkb.mpl.com/~tkb/software.html
-- 
T. Kurt Bond, tkb@tkb.mpl.com

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners