bug in "developing applications with objective caml" (english translation)

bug in "developing applications with objective caml" (english translation)

[Jack Andrews]

hi,


i think there's a problem in the oreilly book (probably the english
translation?)

Chapter 11, section 'Basic Revisited' (p307) in the third paragraph, talks
about "the declaration of the type |sentences|"

i don't see this type used or declared anywhere in the book, and i can't
see if |sentences| is a convention of some sort in ocamlyacc/lex

i'm a newbie biting off quite a bit in starting with ocaml{lex,yacc} but
it's the job i need to do, so that's where i am.

any pointers muchly appreciated.


jack

Re: [Caml-list] bug in "developing applications with objective caml" (english translation)

[Ken Rose]

Jack Andrews wrote:
> hi,
> 
> 
> i think there's a problem in the oreilly book (probably the english
> translation?)
> 
> Chapter 11, section 'Basic Revisited' (p307) in the third paragraph, talks
> about "the declaration of the type |sentences|"
> 
> i don't see this type used or declared anywhere in the book, and i can't
> see if |sentences| is a convention of some sort in ocamlyacc/lex

This seems to be a communication failure between the translators & 
proofreaders of chapter 11 and their counterparts on chapter 6.  I was a 
proofreader on chapter 6, so I'm a guilty party.

I'm not certain, but I think the type in question is called "phrase" in 
chapter 6.

Is the translation effort still active at all?  I got dropped from the 
translators mailing list when I changed ISPs about 2 years ago.  Could 
one of our French-speakers check in the original text to see if I've 
figured this out correctly?

> i'm a newbie biting off quite a bit in starting with ocaml{lex,yacc} but
> it's the job i need to do, so that's where i am.

I'd recommend Levine et al., "Lex & Yacc", from O'Reilly.  It doesn't 
address ocaml at all, but it's a good grounding on how this family of 
tools work.

  - ken

some comments on ocaml{lex,yacc} from a novice's POV

[Jack Andrews]

hi,

this is a little long.  i'm new to ocaml, but like most, have been
educated in FLs and experimented with and applied functional languages and
techniques.  python has been the first language i turn to for a few years
now.

i need to parse text as a sequence of records (with odd variations). i
have used ply (python lex-yacc) most recently for parsing and believe it
to be one of the more elegant mechanisms i've seen. 
http://systems.cs.uchicago.edu/ply/ply.html

elegant because there are no lex and yacc input files, but rather the
tokens and grammar rules are defined in python code -- succinctly!  eg:

# calclex.py
import lex
tokens = ( 'NUMBER', 'PLUS', 'MINUS', 'TIMES', 'DIVIDE', 'LPAREN', 'RPAREN',)
t_PLUS    = r'\+'  # in python, the r prefix to a string literal
t_MINUS   = r'-'   #  means as-is.  r'\' in python is "\\" in c
[snip]
def t_NUMBER(t):
    r'\d+'
    try: t.value = int(t.value)
    except ValueError:
         print "Line %d: Number %s is too large!" % (t.lineno,t.value)
         t.value = 0
    return t

by reflection/introspection ply finds all the token definitions in
calclex.py.  the only trick here is the first line of the t_NUMBER
function.  in python, any string literal as the first expression in a
function is the doc_string (accessible by t_NUMBER.__doc__ in this case)

#!/usr/local/bin/python
import yacc
from calclex import tokens  # this is where python builds the lexer

def p_expression_plus(p):
    'expression : expression PLUS term'
    p[0] = p[1] + p[3]
[snip]
def p_factor_expr(p):
    'factor : LPAREN expression RPAREN'
    p[0] = p[2]
# this is where python builds the parser
yacc.yacc()   # or yacc.yacc(method="LALR") for alternate parsing methods
while 1:
   try: s = raw_input('calc > ')
   except EOFError: break
   if not s: continue
   result = yacc.parse(s)
   print result

once again, using the names of functions and their docstrings, ply can
build a parser.

but i want to use ocaml, not python because i know i need (more) speed. 
after using ply, the ocaml{yacc,lex} implementation looks like it's just
glued on GNU tools.  not that there's anything wrong with that, but
integration with the language is nothing like that of ply.

don't get me wrong, i don't think ply is perfect, and i don't know enough
about parsing to be any kind of authority, but it seems to me a bit odd
that a comment in a caml parser is either (**) or /**/ depending on
context and in lexical analysis, a character set is expressed as ['A'-'Z'
'a'-'z' '_'] rather than usual (succinct) regexp syntax: [A-Za-z_]  (less
than half the characters)   really, the .mll and .mly look nothing like
caml

take what i say with a grain of salt, i'm no authority on anything i've said.


jack

Re: [Caml-list] some comments on ocaml{lex,yacc} from a novice's POV

[Erik de Castro Lopo]

On Sat, 2 Apr 2005 15:10:04 +1000 (EST)
"Jack Andrews" <effbiae@ivorykite.com> wrote:

> but i want to use ocaml, not python because i know i need (more) speed. 
> after using ply, the ocaml{yacc,lex} implementation looks like it's just
> glued on GNU tools.

Lex and yacc are amazilingly powerful tools that are let down by the
fact the code they produce is C code.

Ocaml(lex|yacc) extend on the very powerful lex/yacc concepts but produce
Ocaml code whick hoos in very nicely with a powerful functional/imperative
OO language.

The thing that amazes me about the original lex and yacc is that all
the tutorials I've seen for using them only deal with trivially simple
parsing problems when they are capable of som much more.

Erik
-- 
+-----------------------------------------------------------+
  Erik de Castro Lopo  nospam@mega-nerd.com (Yes it's valid)
+-----------------------------------------------------------+
"The day Microsoft makes something that doesn't suck is probably the
day they start making vacuum cleaners." -- Ernst Jan Plugge

Re: [Caml-list] some comments on ocaml{lex,yacc} from a novice's POV

[Jacques Garrigue]

From: "Jack Andrews" <effbiae@ivorykite.com>

> this is a little long.  i'm new to ocaml, but like most, have been
> educated in FLs and experimented with and applied functional languages and
> techniques.  python has been the first language i turn to for a few years
> now.
> 
> i need to parse text as a sequence of records (with odd variations). i
> have used ply (python lex-yacc) most recently for parsing and believe it
> to be one of the more elegant mechanisms i've seen. 
> http://systems.cs.uchicago.edu/ply/ply.html
> 
> elegant because there are no lex and yacc input files, but rather the
> tokens and grammar rules are defined in python code -- succinctly!  eg:
> 
> # calclex.py
> import lex
> tokens = ( 'NUMBER', 'PLUS', 'MINUS', 'TIMES', 'DIVIDE', 'LPAREN', 'RPAREN',)
> t_PLUS    = r'\+'  # in python, the r prefix to a string literal
> t_MINUS   = r'-'   #  means as-is.  r'\' in python is "\\" in c
> [snip]

Interestingly, your example corresponds exactly to the one in the
ocaml tutorial, where it is solved using stream parsers.
Stream parsers are a bit more involved than just writing yacc rules,
but they give you more control on how to combine rules (you can write
parser combinators.) And they are completely integrated in the
language using camlp4.

Alternatively, you can also use ocamllex/ocamlyacc (a little bit more
overhead, but really easy once you're set up), or use the Scanf module
(if you don't need a real parser.)

By the way, Caml 3.1 had complete yacc integration (15 years ago).
I suppose this was considered too monolithic, but it was very nice to
use in practice.

Jacques Garrigue

Parser combinators [was: some comments on ocaml{lex,yacc} from a novice's POV]

[Alex Baretta]

Jacques Garrigue wrote:

> 
> Interestingly, your example corresponds exactly to the one in the
> ocaml tutorial, where it is solved using stream parsers.
> Stream parsers are a bit more involved than just writing yacc rules,
> but they give you more control on how to combine rules (you can write
> parser combinators.) And they are completely integrated in the
> language using camlp4.
> 

Er.. Excuse me for sticking my nose into this, but I think I read 
something interesting. Parser combinators? What do you mean? I'm quite 
sure I have not seen any operators acting on stream parsers, at least if 
by stream parsers you mean the LL1 based on pa_op.cmo camlp4 module.

Alex


-- 
*********************************************************************
http://www.barettadeit.com/
Baretta DE&IT
A division of Baretta SRL

tel. +39 02 370 111 55
fax. +39 02 370 111 54

Our technology:

The Application System/Xcaml (AS/Xcaml)
<http://www.asxcaml.org/>

The FreerP Project
<http://www.freerp.org/>

Re: [Caml-list] Parser combinators

[Jacques Garrigue]

From: Alex Baretta <alex@barettadeit.com>
> > Interestingly, your example corresponds exactly to the one in the
> > ocaml tutorial, where it is solved using stream parsers.
> > Stream parsers are a bit more involved than just writing yacc rules,
> > but they give you more control on how to combine rules (you can write
> > parser combinators.) And they are completely integrated in the
> > language using camlp4.
> 
> Er.. Excuse me for sticking my nose into this, but I think I read 
> something interesting. Parser combinators? What do you mean? I'm quite 
> sure I have not seen any operators acting on stream parsers, at least if 
> by stream parsers you mean the LL1 based on pa_op.cmo camlp4 module.

The point is that you can define them yourself.
For instance here is the star operator.

let rec star ?(acc=[]) p = parser
    [< x = p ; s >] -> star ~acc:(x::acc) p s
  | [< >] -> List.rev acc

More concretely, here is another version of expression parsing, using
functionals. 

type expr =
    Num of int
  | Var of string
  | Plus of expr * expr
  | Mult of expr * expr

open Genlex

let rec accumulate parse accu = parser
  | [< e = parse accu; s >] -> accumulate parse e s
  | [< >] -> accu
(* val accumulate : ('a -> Genlex.token Stream.t -> 'a) ->
                    'a -> Genlex.token Stream.t -> 'a *)
let left_assoc parse op wrap =
  let parse' accu =
    parser [< 'Kwd k when k = op; s >] -> wrap accu (parse s) in
  parser [< e1 = parse; e2 = accumulate parse' e1 >] -> e2
(* val left_assoc : (Genlex.token Stream.t -> 'a) ->
       string -> ('a -> 'a -> 'a) -> Genlex.token Stream.t -> 'a *)
let rec parse_simple = parser
  | [< 'Int n >] -> Num n
  | [< 'Ident x >] -> Var x
  | [< 'Kwd"("; e = parse_expr; 'Kwd")" >] -> e
and parse_mult s =
  left_assoc parse_simple "*" (fun e1 e2 -> Mult(e1,e2)) s
and parse_expr s =
  left_assoc parse_mult "+" (fun e1 e2 -> Plus(e1,e2)) s
(* val parse_simple : Genlex.token Stream.t -> expr
   val parse_mult : Genlex.token Stream.t -> expr
   val parse_expr : Genlex.token Stream.t -> expr *)

let lexer = Genlex.make_lexer ["+";"*";"(";")"]
let parse_string s =
  match lexer (Stream.of_string s) with parser
    [< e = parse_expr; _ = Stream.empty >] -> e
(* val parse_string : string -> expr *)

I leave as exercise how to extend it to handle "-" and "/" in a
generic way.

Jacques Garrigue

Re: [Caml-list] some comments on ocaml{lex,yacc} from a novice's POV

[Oliver Bandel]

On Sat, Apr 02, 2005 at 04:38:51PM +0900, Jacques Garrigue wrote:
> From: "Jack Andrews" <effbiae@ivorykite.com>
[...]
> > # calclex.py
> > import lex
> > tokens = ( 'NUMBER', 'PLUS', 'MINUS', 'TIMES', 'DIVIDE', 'LPAREN', 'RPAREN',)
> > t_PLUS    = r'\+'  # in python, the r prefix to a string literal
> > t_MINUS   = r'-'   #  means as-is.  r'\' in python is "\\" in c
> > [snip]
> 
> Interestingly, your example corresponds exactly to the one in the
> ocaml tutorial, where it is solved using stream parsers.
> Stream parsers are a bit more involved than just writing yacc rules,
> but they give you more control on how to combine rules (you can write
> parser combinators.) And they are completely integrated in the
> language using camlp4.

...which lacks adequate documentation... :(

Btw: Is the campl4-tutorial-project growing?

Ciao,
   Oliver

Re: some comments on ocaml{lex,yacc} from a novice's POV

[Jack Andrews]

Jack Andrews said:
> have used ply (python lex-yacc) most recently for parsing and believe it
> to be one of the more elegant mechanisms i've seen.
> http://systems.cs.uchicago.edu/ply/ply.html
>
> elegant because there are no lex and yacc input files, but rather the
> tokens and grammar rules are defined in python code -- succinctly!

i've now found the most elegant parser generator i have seen (scheme):
 http://www.iro.umontreal.ca/~boucherd/Lalr/documentation/lalr.html

here's the usual calc example that generates a parser:

 (define expr-parser
  (lalr-parser
   ; Terminal symbols
   (ID + - * /)
   ; Productions
   (e (e + t)    : (+ $1 $3)
      (e - t)    : (- $1 $3)
      (t)        : $1)
   (t (t * f)    : (* $1 $3)
      (t / f)    : (/ $1 $3)
      (f)        : $1)
   (f (ID)       : $1)))

isn't that nice?!?  this is an example of the power of lisp macros that
paul graham talks about.

compare with caml solutions? compare with any other solution?

i'm genuinely trying to choose my next language.  i was drawn to ocaml
because it's a fast, functional language: i want that power without having
to optimize to C.  i'm told there are good scheme compilers.  i was drawn
to ocaml because of it's score in the "language shootout"(s) and because
of it's high placing in the programming contest.

so this post is a troll, i guess, but i want to make an informed choice.

tia,   jack

Re: [Caml-list] Re: some comments on ocaml{lex,yacc} from a novice's POV

[Erik de Castro Lopo]

On Mon, 4 Apr 2005 13:42:03 +1000 (EST)
"Jack Andrews" <effbiae@ivorykite.com> wrote:

> here's the usual calc example that generates a parser:
> 
>  (define expr-parser
>   (lalr-parser
>    ; Terminal symbols
>    (ID + - * /)
>    ; Productions
>    (e (e + t)    : (+ $1 $3)
>       (e - t)    : (- $1 $3)
>       (t)        : $1)
>    (t (t * f)    : (* $1 $3)
>       (t / f)    : (/ $1 $3)
>       (f)        : $1)
>    (f (ID)       : $1)))
> 
> isn't that nice?!?

Yes.

> compare with caml solutions? compare with any other solution?

There are parsers for Haskell which would compare very favourably 
with your lisp parser. I haven't used them myself but I've seen 
example code somewhere.

> i'm told there are good scheme compilers.

Since scheme is a dynamically typed language, scheme compilers are
unlikely to ever produce code as fast as a compiler for a statically 
typed langugae like ocaml.

Erik
-- 
+-----------------------------------------------------------+
  Erik de Castro Lopo  nospam@mega-nerd.com (Yes it's valid)
+-----------------------------------------------------------+
" ... new TV ad for Microsoft's Internet Explorer e-mail program which
uses the musical theme of the "Confutatis Maledictis" from Mozart's
Requiem. "Where do you want to go today?" is the cheery line on the
screen, while the chorus sings "Confutatis maledictis, flammis acribus
addictis,". This translates to "The damned and accursed are convicted
to the flames of hell."

Re: [Caml-list] Re: some comments on ocaml{lex,yacc} from a novice's POV

[Jon Harrop]

On Monday 04 April 2005 06:44, Erik de Castro Lopo wrote:
> On Mon, 4 Apr 2005 13:42:03 +1000 (EST)
> > isn't that nice?!?
>
> Yes.

Not if it isn't statically checked.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists

Re: [Caml-list] Re: some comments on ocaml{lex,yacc} from a novice's POV

[Geoff Wozniak]

[-- Attachment #1: Type: text/plain, Size: 981 bytes --]

Jon Harrop <jon@ffconsultancy.com> writes:

> On Monday 04 April 2005 06:44, Erik de Castro Lopo wrote:
>> On Mon, 4 Apr 2005 13:42:03 +1000 (EST)
>> > isn't that nice?!?
>>
>> Yes.
>
> Not if it isn't statically checked.
>

I take issue with this statement, not because of some personal vendetta,
but because it dismisses some very useful tools.

When I am developing software, I often find that at the beginning, static
typing is a burden that I would rather not be bothered with for the simple
reason that I don't know what types are to be used.  Later in development,
once I know more about my problem space, I will migrate to using some
language that uses a static (preferably strong) type system.

Saying some programming tool isn't nice because it isn't "statically
checked" is short-sighted and I'd rather not see a novice come away with
the impression that if a language/tool is not statically checked, it's
somehow inferior.

-- 
Geoff Wozniak

[-- Attachment #2: Type: application/pgp-signature, Size: 188 bytes --]

Re: [Caml-list] Re: some comments on ocaml{lex,yacc} from a novice's POV

[Jon Harrop]

On Tuesday 05 April 2005 13:00, Geoff Wozniak wrote:
> When I am developing software, I often find that at the beginning, static
> typing is a burden

Note that, in this case, I was referring to the detection of grammar conflicts 
and not static type checking.

> that I would rather not be bothered with for the simple 
> reason that I don't know what types are to be used.  Later in development,
> once I know more about my problem space, I will migrate to using some
> language that uses a static (preferably strong) type system.

I think this is very interesting. Someone else recently expressed this view to 
me. Personally, I'm undecided. I must say that I do occasionally resort to 
Mathematica (which is "kind of" dynamically typed) instead of OCaml for 
simple programs. However, I think this is not because of the typing but, 
rather, because Mathematica provides many more features in some areas (e.g. 
pattern matching). Also, in most cases I end up regretting my decision and 
resort to OCaml.

For example, I recently tried to write programs to compute the number of 
unique posters per month on the two caml lists. I initially tried this in 
Mathematica because it is more lax and I thought it would let me knock up 
such a program more quickly. However, having written several versions which 
didn't work (mostly bailing with the equivalent of run-time type errors) I 
ended up using a lexer written in OCaml.

> Saying some programming tool isn't nice because it isn't "statically
> checked" is short-sighted and I'd rather not see a novice come away with
> the impression that if a language/tool is not statically checked, it's
> somehow inferior.

Can you give an example where dynamic typing has helped you to prototype a 
program more quickly than you could have done with static type checking?

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists

Re: [Caml-list] Re: some comments on ocaml{lex,yacc} from a novice's POV

[Richard Jones]

On Tue, Apr 05, 2005 at 02:49:38PM +0100, Jon Harrop wrote:
> For example, I recently tried to write programs to compute the number of 
> unique posters per month on the two caml lists.

Perhaps a case for a specialised language?  Once you've split up the
mail into monthly archives, something like:

< mail/caml-list.YYYY.MM formail -s formail -x 'From:' | sort -u | wc -l

(This is, I suppose, an argument for not just dynamic typing, but
tolerating a complete lack of checks altogether ...)

Rich.

-- 
Richard Jones, CTO Merjis Ltd.
Merjis - web marketing and technology - http://merjis.com
Team Notepad - intranets and extranets for business - http://team-notepad.com

Re: [Caml-list] Re: some comments on ocaml{lex,yacc} from a novice's POV

[Oliver Bandel]

On Tue, Apr 05, 2005 at 03:26:16PM +0100, Richard Jones wrote:
> On Tue, Apr 05, 2005 at 02:49:38PM +0100, Jon Harrop wrote:
> > For example, I recently tried to write programs to compute the number of 
> > unique posters per month on the two caml lists.
> 
> Perhaps a case for a specialised language?  Once you've split up the
> mail into monthly archives, something like:
> 
> < mail/caml-list.YYYY.MM formail -s formail -x 'From:' | sort -u | wc -l
[...]

Well, even formail is overhead. :)

Why not using grep for this?! ;-)

Ciao,
   Oliver

Re: [Caml-list] Re: some comments on ocaml{lex,yacc} from a novice's POV

[Geoff Wozniak]

[-- Attachment #1: Type: text/plain, Size: 2100 bytes --]

Jon Harrop <jon@ffconsultancy.com> writes:

> Note that, in this case, I was referring to the detection of grammar
> conflicts and not static type checking.
>

Sorry -- that notion didn't come across very well in your message.  The
criticism was misplaced.  (And I hope that my response didn't come off as
an "ad hominem" fallacy.)

> Can you give an example where dynamic typing has helped you to prototype a 
> program more quickly than you could have done with static type checking?
>

It happens quite often when I write code for a specification that is
incomplete and I have to go back and change something.  For example, I was
recently working on a recursive decent parser for some grammar.  I was
interested to see what sentences in the grammar would look like, how they
would parse, and other things of this nature.  Basically, I was coding to
flush out the inadequacies of the design.

I was doing this in OCaml, but I found that I had to constantly create new
types to represent the different forms that could be found in the parse
tree.  Often, it would involve moving some element from one type to
another.  This resulted in me making minor changes to a few different
functions in order for the program to type check.  It would have been
considerably simpler to just throw the element into a cons cell with the
first element being a symbol/string/whatever that just described the
element.  Then I would just write code that checked if the car/head of the
cons cell was X and if so, do something with it.

I am not advocating that this code would be suitable for release.  In fact,
I would have little faith in it and would probably be embarassed to release
it.  However, incrementally developing some program that does not have much
of a specification seems to be much simpler if I don't burden myself with
the act of conjuring up types for everything.  Once I've gone through a
couple iterations of the program, then I'm very interested in some form of
strong type checking to make sure that I'm not missing the little things.

-- 
Geoff Wozniak

[-- Attachment #2: Type: application/pgp-signature, Size: 188 bytes --]

Re: [Caml-list] Re: some comments on ocaml{lex,yacc} from a novice's POV

[Kenneth Knowles]

On Wed, Apr 06, 2005 at 12:52:58AM -0400, Geoff Wozniak wrote:
> I was doing this in OCaml, but I found that I had to constantly create new
> types to represent the different forms that could be found in the parse
> tree.  

This sounds quite familiar.  One idea is to use polymorphic variants and
immediate objects instead of conventional variants and record types (though this
can create some scary error messages).  I've only ever done this for very rapid
prototyping, though.

- Kenn

Re: some comments on ocaml{lex,yacc} from anovice's POV

[Jack Andrews]

Jon Harrop <jon@ffconsultancy.com> writes:
> Can you give an example where dynamic typing has helped you to prototype
> a program more quickly than you could have done with static type
> checking?

if a type checking scheme can infer all the types from
my python scripts, then i'd be happy for my code to be
passed through such a checker.

static type checking is fine, but why would you want to
write more code for the same prototype for the sake of
some type checking.  maybe after the prototype stage,
it could be argued that static type checking is essential,
but i don't think so.

but there are many factors that go towards bulletproof
code.  who's to say that the time spent writing statically
checked code isn't better spent making more runtime checks
(invariants/contracts)?  after all, we all have a time budget.

having all possible static checks with all possible
code succinctness is ideal.  this only implies that compromise
is needed, and the compromise, more often than not, will be
directed by taste.


jack

Re: [Caml-list] Re: some comments on ocaml{lex,yacc} from a novice's POV

[Daan Leijen]

[-- Attachment #1: Type: text/plain, Size: 763 bytes --]

Erik de Castro Lopo wrote:

>>compare with caml solutions? compare with any other solution?
>>    
>>
>
>There are parsers for Haskell which would compare very favourably 
>with your lisp parser. I haven't used them myself but I've seen 
>example code somewhere.
>  
>
The Parsec manual contains a few nice examples and pointers to further 
literature
on parser combinators if you are interested.

<http://www.cs.uu.nl/~daan/parsec.html>

Everything is statically checked of course ;-)

All the best,
-- Daan Leijen.


>  
>
>>i'm told there are good scheme compilers.
>>    
>>
>
>Since scheme is a dynamically typed language, scheme compilers are
>unlikely to ever produce code as fast as a compiler for a statically 
>typed langugae like ocaml.
>
>Erik
>  
>


[-- Attachment #2: Type: text/html, Size: 1508 bytes --]

Re: [Caml-list] Re: some comments on ocaml{lex,yacc} from a novice's POV

[Paul Snively]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1


On Apr 3, 2005, at 10:44 PM, Erik de Castro Lopo wrote:

> On Mon, 4 Apr 2005 13:42:03 +1000 (EST)
> "Jack Andrews" <effbiae@ivorykite.com> wrote:
>
>> here's the usual calc example that generates a parser:
>>
>>  (define expr-parser
>>   (lalr-parser
>>    ; Terminal symbols
>>    (ID + - * /)
>>    ; Productions
>>    (e (e + t)    : (+ $1 $3)
>>       (e - t)    : (- $1 $3)
>>       (t)        : $1)
>>    (t (t * f)    : (* $1 $3)
>>       (t / f)    : (/ $1 $3)
>>       (f)        : $1)
>>    (f (ID)       : $1)))
>>
>> isn't that nice?!?
>
> Yes.
>
>> compare with caml solutions? compare with any other solution?
>
> There are parsers for Haskell which would compare very favourably
> with your lisp parser. I haven't used them myself but I've seen
> example code somewhere.
>
ONAE's cf's parser combinators, perhaps, if the point is to have an 
"in-native-code" solution. See also the Spirit parser generator 
framework in the Boost libraries for C++, at <http://www.boost.org> or 
<http://spirit.sourceforge.net>.

>> i'm told there are good scheme compilers.
>
> Since scheme is a dynamically typed language, scheme compilers are
> unlikely to ever produce code as fast as a compiler for a statically
> typed langugae like ocaml.
>
It's hard, but by making the closed-world assumption and doing some 
careful type inference, it's possible to be competitive: see the 
Stalin, Bigloo, and Gambit compilers.

> Erik
> -- 
> +-----------------------------------------------------------+
>   Erik de Castro Lopo  nospam@mega-nerd.com (Yes it's valid)
> +-----------------------------------------------------------+
> " ... new TV ad for Microsoft's Internet Explorer e-mail program which
> uses the musical theme of the "Confutatis Maledictis" from Mozart's
> Requiem. "Where do you want to go today?" is the cheery line on the
> screen, while the chorus sings "Confutatis maledictis, flammis acribus
> addictis,". This translates to "The damned and accursed are convicted
> to the flames of hell."
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>
Best regards,
Paul

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.0 (Darwin)

iEYEARECAAYFAkJRe9gACgkQO3fYpochAqKNyQCg8wks+wUbD9phOo2/7p9s+uDc
u+sAn1bc3LOKJJyVDMrIsKqtiIFOFrv8
=KmnK
-----END PGP SIGNATURE-----

Re: [Caml-list] Re: some comments on ocaml{lex,yacc} from a novice's POV

[skaller]

On Tue, 2005-04-05 at 03:39, Paul Snively wrote:

> ONAE's cf's parser combinators, perhaps, if the point is to have an 
> "in-native-code" solution. See also the Spirit parser generator 
> framework in the Boost libraries for C++, at <http://www.boost.org> or 
> <http://spirit.sourceforge.net>.

And if you're throwing parsers around, Felix provides
an inbuilt GLR parser (based on Scott McPeaks Elkhound).


-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net

Re: [Caml-list] Re: some comments on ocaml{lex,yacc} from a novice's POV

[Paul Snively]

Hi John,

On Apr 4, 2005, at 11:16 AM, skaller wrote:

> And if you're throwing parsers around, Felix provides
> an inbuilt GLR parser (based on Scott McPeaks Elkhound).
>
Thanks for the reminder: a recent post on ll-discuss about overcoming 
C++ "brainwashing" reminded me that I need to look at Felix.

Having said that, I certainly would like to see a GLR parser generator 
written in O'Caml, preferably in-code. Yes, I know that Elkhound 
generates O'Caml parsers despite being written in C++, and in fact I 
may yet take advantage of that.

>
> -- 
> John Skaller, mailto:skaller@users.sf.net
> voice: 061-2-9660-0850,
> snail: PO BOX 401 Glebe NSW 2037 Australia
> Checkout the Felix programming language http://felix.sf.net
>
Best regards,
Paul

Re: [Caml-list] recursive modules redux, & interface files

[Xavier Leroy]

> 1.  So, I understand that doing recursive types across modules is
> hard (but I'd say very important for decoupling large software), but
> is it true that I can't even call across modules recursively?  Even
> with mli files to resolve the types?  I find that incredibly hard to
> believe, but I can't get it to work and it seems the docs say it's
> impossible as well (so why am I posting about it, you ask?
> Disbelief that it's not possible, I guess. :).

You're right that cross-module recursion even between functions is not
supported, and you're right that this is not because of typing
difficulties -- the type-checking of such recursions is easy.

This is because value components of modules can be the result of
arbitrary computations, and the only way to ensure that these
computations succeed is by making sure they occur sequentially.
Consider for instance:

    A.mli    val x : int                B.mli    val y : int
    A.ml     let x = B.y + 1            B.ml     let y = A.x * 3

We don't know how to evaluate these definitions correctly -- indeed,
there is no integer solution to this recursive definition.

Other languages avoid this problem in one of two ways.  C and C-like
languages only allow global identifiers to be defined as functions or
compile-time constants, but not results of arbitrary computations.
Haskell and other lazy languages rely on lazy evaluation to perform
on-demand initialization (i.e. compute the definition the first time
it's needed), and aborting computation if a dynamic dependency cycle
is detected (as in the example above).

Java goes pretty much the Haskell way, relying on dynamic class
loading to lazily evaluate static field definitions; originally, it
raised an exception on discovering a dynamic dependency cycle;
nowadays, I think it just pre-initializes static fields to 0 or null,
then compute the initial values based on this (so that in the example
above you'd get x = 1 and y = 3 if the program refers to B.y first,
and y = 0 and x = 1 if the program refers to A.x first :-).

The Haskell solution is semantically cleanest, but lazy evaluation
of module components entails a performance penalty and some increase
in code size (the compiler must emit "am I initialized already?" tests
on every module value access).  (The semantics of Java class
initialization entail similar penalties, although they partially hide
them by relying on JIT compilation -- blech.)

A possible approach for Caml would be to have a link-time analysis
that detects cross-module value recursions that involve only function
definitions, and allow these (because they are safe -- like in C!).
Fabrice Le Fessant posted a patch to OCaml a while ago that does
pretty much this.  I'm still hoping more general, principled solutions
exist, but they sure are hard to design!

> 2. Also, on a related note, why do the interface file and the
> implementation file (or equivalently, I believe, the signature and
> structure) both have to have all the concrete types duplicated?  I can
> see the value of having interfaces that hide some implementation stuff
> and abstract types, but if I've got a big fully-specified variant type
> in a .mli file, it's annoying and error prone (yes, I know the
> compiler will catch it) to have to retype the whole thing into the ml
> file (which I have to do if I want to hide anything else in the ml
> file, meaning I can't just have an ml without an mli).

Yes, it's annoying, and it's more or less a consequence of the
ideology behind the ML module system: that structures define things,
and that signatures can later be ascribed to these structures to hide
or abstract some of these things.  With this ideology, every type that
is declared in a signature -- even if it's a concrete declaration that
includes as much information as a type definition! -- must be matched
by a type definition in the corresponding structure. It's just very
principled and logical -- just a bit inconvenient at times :-)

Another way to think about it is that every structure (or
implementation file) must "stand on its own" and make sense without
the signature (or interface file) that will be ascribed to it later
on.  It makes sense when the signature is not known when the structure
is defined, e.g.

        module M = struct type t = A | B ... end
        (* 5000 lines later: *)
        module M' = (M : sig type t = A | B ... end)

It becomes practically inconvenient when the signature is known at the
time of the structure definition:

        module M : sig type t = A | B ... end =
          struct type t = A | B ... end

Which is the case with interface and implementation files.

In this case, one could envision an automatic completion of the
structure / implementation file so that concrete type specifications
from the signature do not need to be implemented in the structure.
Doing this right is not obvious, though.  First, it's not enough to
say that a concrete type spec does not need to be matched in the
structure.  This would type-check

        module M : sig type t = A | B end = struct end

but not

    module M : sig type t = A | B  val v : t end = struct let v = A end

In other terms, the unmatched concrete type specs in the signature
need to be somehow reintroduced in the structure definition, so that
other parts of the structure may refer to them.  While I think it can
be done in most practical cases, it's a bit of a kludge and I'm not
sure how to do this in all cases.

Is the practical value of this kludge enough to forget that it's a
kludge?  Can't we live with the current duplication of concrete type
definitions in the name of systematic, principled module systems?  
I really don't know.

Best,

- Xavier Leroy
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

[Caml-list] parser combinators

[Kevin Backhouse]

Is there a parser combinator library for OCaml? I would like to write a
parser for Java and I gather that Java's grammar is LL(1). That might mean
that parser combinators are better suited than yacc.

thanks,

Kevin Backhouse

-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] parser combinators

[Daniel de Rauglaudre]

Hello,

On Fri, Mar 30, 2001 at 11:27:55AM +0100, Kevin Backhouse wrote:

> Is there a parser combinator library for OCaml? I would like to write a
> parser for Java and I gather that Java's grammar is LL(1). That might mean
> that parser combinators are better suited than yacc.

No, there is not, but you may consider using Camlp4 and its grammars.

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