3 years of FriCAS
Waldek Hebisch
I think it is desirable to write a bit about what was done in
that time and how this correlates with expectations.
First, compared to Axiom September 2005, FriCAS contains
51 new constructors having 13651 lines in total. Given that
the whole algebra has 142992 lines, this means that about 10%
of algebra is in new constructors. There were several mass edits
which changed of order of 10000 lines of code. There are
additions to existing constructors (of order of 3000 lines).
There are tens of fixed bugs. Speed of many core operations
(polynomial operations, kernel manipulations, coercions)
improved significantly (testsuite runs about 2.5 times
faster than before, some coercions are hundred time faster).
Main new additions are:
- output routines (MathML and HTML format, new graphic framework)
- guessing package
- new special functions
- improvements to integrator and normalization
- tensoring framework
I think the main observation is that we achieved normal speed of
algebra developement (we are close to 30 years average).
Spad compiler is significantly faster than it used to be in the
past, several bugs are fixed and few new constructs (nested
functions, closures via '+->', type-valued arguments and return
values) added. There is new parser written in Boot and new
pass which expands most macros before compilation.
In general FriCAS code undergone a significant cleanup.
Compared to expectations:
- in general, changes go much slower than hoped for
- in particular Spad compiler needs a rewrite and this goes on
slowely
Still, for me balance looks quite positive. I think that
compared to other systems and taking into account small number
of developers that we have we are doing quite well.
--
Waldek Hebisch
heb...@math.uni.wroc.pl
Bill Page
> ...
> Still, for me balance looks quite positive. I think that
> compared to other systems and taking into account
> small number of developers that we have we are doing
> quite well.
>
Waldek,
I agree whole heartedly that FriCAS is doing very well. Thank you for
all your efforts and thanks also to the other developers who have
contributed to this project.
Congratulations on turning 3!
Regards,
Bill Page.
Martin Baker
> - in general, changes go much slower than hoped for
> - in particular Spad compiler needs a rewrite and this goes on
> slowely
I've been thinking about this over the last week or so. I wouldn't
presume to understand the issues but I was wondering if it would be
possible to implement a two stage compiler? I was thinking that the
first stage would do the pattern matching, so it would take a line
like:
myVector * myMatrix
and convert it to an intermediate form like:
_*(myVector:Vector DF,myMatrix:Martix DF)$Martix DF
This intermediate form would be very hard for humans to read but the
idea is that it could be defined in BNF so that standard tools like
ANTLR could be used for Lex, Parse, Semantic Analysis and so on.
Sorry to take up your time with what is probably a crackpot idea, when
you are busy with the next release, its just that I like to think
about possible options.
Thanks for all the good work you are doing on this,
Martin Baker
Waldek Hebisch
>
> On Thursday 04 Nov 2010 18:25:13 Waldek Hebisch wrote:
> > - in general, changes go much slower than hoped for
> > - in particular Spad compiler needs a rewrite and this goes on
> > slowely
>
> Waldek,
>
> I've been thinking about this over the last week or so. I wouldn't
> presume to understand the issues but I was wondering if it would be
> possible to implement a two stage compiler? I was thinking that the
> first stage would do the pattern matching, so it would take a line
> like:
>
> myVector * myMatrix
>
> and convert it to an intermediate form like:
>
> _*(myVector:Vector DF,myMatrix:Martix DF)$Martix DF
>
> This intermediate form would be very hard for humans to read but the
> idea is that it could be defined in BNF so that standard tools like
> ANTLR could be used for Lex, Parse, Semantic Analysis and so on.
>
Spad compiler is divided into stages. Lexical analysis and parsing
are not a serious problem. Standard tools could help a bit but
actually part that tools can handle is very simple while some
other aspects (like whitespace sensitivity) must be done in
ad-hoc way because tools do not support them.
When one comes to semantic analysis things get more tricky. First,
when trying to write simple specification of what compiler should
do one quickly sees that desired behaviour is not computable.
So one has to introduce restrictions to turn problem into
computable one (but retain as much as possible from nice
features). Second difficulty is that currently at some places
the compiler is doing rather strange things, but if one tries
to disable such behaviour the algebra no longer compiles.
Also, there is a saying that real men can do simultanously
several things. But my experiece is that trying to multitask
slows me down. When I concentate on one thing, I can do it,
then I can move to another thing. In the last two years
I spent most of time working on algebra and only a little
on the compiler.
--
Waldek Hebisch
heb...@math.uni.wroc.pl
Martin Baker
> Spad compiler is divided into stages. Lexical analysis and parsing
> are not a serious problem. Standard tools could help a bit but
> actually part that tools can handle is very simple while some
> other aspects (like whitespace sensitivity) must be done in
> ad-hoc way because tools do not support them.
point of view! (the error message on the first pass seem worst of all,
I can't even work out what line is causing the problem).
Regarding whitespace, I seem to remember a message, from you, saying
you were planning to delimit blocks using braces instead of
indentation? So if you made a clean break to such a syntax would that
make things easier? Also, when working on graphics stuff aldor-like OO
capability would be very nice.
> When one comes to semantic analysis things get more tricky. First,
> when trying to write simple specification of what compiler should
> do one quickly sees that desired behaviour is not computable.
> So one has to introduce restrictions to turn problem into
> computable one (but retain as much as possible from nice
> features). Second difficulty is that currently at some places
> the compiler is doing rather strange things, but if one tries
> to disable such behaviour the algebra no longer compiles.
matching (not sure if that's semantic analysis?) which is why I
thought of factoring it out, but I guess there are lots of other
issues.
> Also, there is a saying that real men can do simultanously
> several things. But my experiece is that trying to multitask
> slows me down. When I concentate on one thing, I can do it,
> then I can move to another thing. In the last two years
> I spent most of time working on algebra and only a little
> on the compiler.
either, however if you did decide to use standard tools and if you
could think of some way that I could help, I would be happy to try to
do so.
Martin Baker
Waldek Hebisch
>
> On Saturday 13 Nov 2010 16:34:40 Waldek Hebisch wrote:
> > Spad compiler is divided into stages. Lexical analysis and parsing
> > are not a serious problem. Standard tools could help a bit but
> > actually part that tools can handle is very simple while some
> > other aspects (like whitespace sensitivity) must be done in
> > ad-hoc way because tools do not support them.
>
> Better error messages and build environment would be very nice from my
> point of view! (the error message on the first pass seem worst of all,
> I can't even work out what line is causing the problem).
> Regarding whitespace, I seem to remember a message, from you, saying
> you were planning to delimit blocks using braces instead of
> indentation? So if you made a clean break to such a syntax would that
> make things easier? Also, when working on graphics stuff aldor-like OO
> capability would be very nice.
I do not want to make a "clean break": we have about 140_000 lines
of Spad code and this code must compile correctly. If compiler
stops supporting some construct, then we need to modify algebra.
This is practical only for rarely used constucts. In particular
we need to support indentation based syntax for long time. The
plans are to support alternative "nopile" mode and have better
support for multiline constructs in pile mode.
Let me add that I do not expect really good error messages
from Spad parser or lexer: basically Spad syntax contains so
little redundancy that parser has no chance to guess what
malformed code is intended to say. But messages could be
better than now: currently indentaion and parentheses get
mixed in lexer and parser so indentation errors give quite
strange error messages and similarely unbalanced parentheses.
I have experimental code which uses Spad parser with lexer
from the interpreter. When ready this code should give
much clearer messages about indentation errors and
unbalanced parenthesis. But ATM it interprets indentation
differently that old Spad, so I need to fix this.
> > When one comes to semantic analysis things get more tricky. First,
> > when trying to write simple specification of what compiler should
> > do one quickly sees that desired behaviour is not computable.
> > So one has to introduce restrictions to turn problem into
> > computable one (but retain as much as possible from nice
> > features). Second difficulty is that currently at some places
> > the compiler is doing rather strange things, but if one tries
> > to disable such behaviour the algebra no longer compiles.
>
> I was assuming that a big part of the difficulty is the pattern
> matching (not sure if that's semantic analysis?) which is why I
> thought of factoring it out, but I guess there are lots of other
> issues.
>
> > Also, there is a saying that real men can do simultanously
> > several things. But my experiece is that trying to multitask
> > slows me down. When I concentate on one thing, I can do it,
> > then I can move to another thing. In the last two years
> > I spent most of time working on algebra and only a little
> > on the compiler.
>
> Yes I can't multitask and I would not claim your level of expertise on
> either, however if you did decide to use standard tools and if you
> could think of some way that I could help, I would be happy to try to
> do so.
>
Concerning tools: of existing tools in my experience parser and lexer
generators are useful, other I have found of little use. I particular
I have met generators of data structures and tree-walker generators.
I would say that I feel that language should have apropriate support
for data structures and tools doe not change much here. Similarely
for tree walkers: we use tree walkers to perform some operation and
typically tree walker code is small compared to operations. Actually,
IME pattern ML-style matching helps more for creating tree walkers
than external tools.
As I wrote, for FriCAS lexer generator would help. But we have
working lexer, it has few hunderd lines so not using lexer
generator is not a big deal. I have doubts if parser generator
would help: Spad syntax is very well suited to existing parser
and not so well typical parser generators. More precisely, bulk
of syntax is in operator priorities. Because we use _four_
priorites per operator Spad priorities are awkward to describe
in a parser generator. OTOH part of FriCAS parser handling
priorites is quite small and the other parts of Spad syntax are
rather simple, so it is easy to handle them in hand written
parser. For some comparison, current parser has 543 lines,
_including_ priority tables. Previous version using a
home-grown parser generator (META) has slightly more than
200 lines. Grammar rules of PL/1 parser have more than 600 lines.
Grammar plus actions for GNU Pascal have more than 2000 lines.
So, potential gain form using parser generator is quite
limited.
As I wrote, for tree walker I find ML-style pattern matching
quite useful. Now, Boot has special support for pattern
matching -- not such good as ML, but better than many
"standard" languages.
Now, if you want to use ML (or Haskell, ...) and associated tools
and develop alternative compiler, than go on.
However:
- Both compiler and Spad runtime have to deal with types. It
is preferable to share type machinery
- We have "interpter", I feel that "interpter" and Spad compiler
could share a lot (currently there is only limited sharing)
So code of Spad compiler should communicate with algebra code,
which is easy if Spad compiler is in Spad, Boot or Lisp but
gets tricky otherwise. Let me say that I considered using
lexer generator and communicate with lexer via FFI -- my
conclusion was that gain from lexer generator was not worth
the trouble with FFI.
Concering difficulty of compiling Spad: the main work is
in "type checking". Parametric types, overloading and
conditionals involving types make it more difficult than
in other languages -- doing it really well is a research topic.
After type checking it is possible to releatively easy generate
code. Spad compiler could do more optimizations after
type checking and probably code generation could be more
efficient. But currently most of compile type is spent in
type checking, type checking generates error messages so
clearly improvement in type checking will be visible to
users. Also, currently type checking resolves overloading
and after that essentially forgets types (it keeps only type
of result). Which means that to do more after type checking
one probably needs to re-work typechecking to keep types
(and other information) longer.
--
Waldek Hebisch
heb...@math.uni.wroc.pl
Martin Baker
Thanks very much for a very full reply, I find it interesting and
useful to know about these things. I'm tempted to ask follow-up
questions but I think I had better let you get on with it rather than
take up more of your time answering my questions.
> Now, if you want to use ML (or Haskell, ...) and associated tools
> and develop alternative compiler, than go on.
have a mathematical basis. Like you said in an earlier message: I also
am not very good at multitasking (especially two computer languages at
the same time) but perhaps if I spend some time learning Haskell then
I may come back to SPAD later with a better perspective and perhaps
some ideas for an alternative compiler.
Martin Baker
Ralf Hemmecke
to understand SPAD, you should maybe also take a look at the Aldor User
Guide. It's not exactly the same as SPAD, but you probably get a better
feeling for SPAD, once you have read the Language specification of Aldor.
http://www.aldor.org/docs/aldorug.pdf
I think that Haskell is quite a bit different from SPAD. Haskell is
functional, SPAD is not. Haskell has pattern matching SPAD has not. You
should maybe also look at DoCon http://www.haskell.org/docon/
and look why (to my knowledge) it was/is not very much in use.
Ralf
Bertfried Fauser
I do not actually understand the efforts to improve the spad compiler,
as I do not understand compilers at all. However, aldor seems to provide
quite a bit of what you want (better error messages etc) and much more,
as Ralf will advocate ;-)).
> I think that Haskell is quite a bit different from SPAD. Haskell is
> functional, SPAD is not. Haskell has pattern matching SPAD has not. You
> should maybe also look at DoCon http://www.haskell.org/docon/
> and look why (to my knowledge) it was/is not very much in use.
Indeed Haskell is an entirely different world. However, I have to object that
functional programming languages are not used. There are industrial applications
(even own programming languages like `erlang' (Erikson language)).
Here in my department and person seems to have haskell running and they use it
(for nearly everything you can (and cannot) imagine) <grin>
But I agree with Ralf, Haskell and spad are far too different. Perhaps all this
`we-need-a-better-compiler-in-axiom' mails should be cc-ed to Steven Watt's,
maybe just the desire to get his inbox free again may help to free aldor?
If not the apparent need for aldor in axiom convinces him.
Cheers
BF.
--
% PD Dr Bertfried Fauser
% Research Fellow, School of Computer Science, Univ. of Birmingham
% Honorary Associate, University of Tasmania
% Privat Docent: University of Konstanz, Physics Dept
<http://www.uni-konstanz.de>
% contact |-> URL : http://www.cs.bham.ac.uk/~fauserb/
% Phone : +44-121-41-42795
Ralf Hemmecke
> as I do not understand compilers at all. However, aldor seems to provide
> quite a bit of what you want (better error messages etc) and much more,
> as Ralf will advocate ;-)).
I only advocate reading the manual and maybe asking Stephen Watt to free
the Aldor compiler. ;-)
>> I think that Haskell is quite a bit different from SPAD. Haskell is
>> functional, SPAD is not. Haskell has pattern matching SPAD has not. You
>> should maybe also look at DoCon http://www.haskell.org/docon/
>> and look why (to my knowledge) it was/is not very much in use.
> Indeed Haskell is an entirely different world. However, I have to object that
> functional programming languages are not used. There are industrial applications
> (even own programming languages like `erlang' (Erikson language)).
> Here in my department and person seems to have haskell running and they use it
> (for nearly everything you can (and cannot) imagine)<grin>
Oh, you misinterpreted my paragraph. That "is not very much in use"
referred only to DoCon. To my understanding that was (is?) an attempt to
build something like a mathematical hierarchy in Haskell.
Functional programming in general should actually be well suited for
mathematics, since mathematics speaks about functions and functors and
what not. But there it's hard to incorporate side effects, like changing
the entry of a huge matrix. As a mathematician one doesn't care, but
bringing mathematics into the field of computation is not just using a
functional programming language. There are things like changing an entry
in a matrix that can become cumbersome or impossible in a functional
language except that one copies the whole matrix or uses other
constructs like monads in Haskell.
Pondering a bit about it... Changing a matrix entry can be done quickly
even in a functional language, if one somehow gives the additional
information "I will never ever use my input again (so you can re-use
that storage)". But it's questionable that this will fit into a purely
functional style.
> But I agree with Ralf, Haskell and spad are far too different. Perhaps all this
> `we-need-a-better-compiler-in-axiom' mails should be cc-ed to Steven Watt's,
> maybe just the desire to get his inbox free again may help to free aldor?
> If not the apparent need for aldor in axiom convinces him.
;-)
Ralf