Index: doc/theses/andrew_beach_MMath/Makefile =================================================================== --- doc/theses/andrew_beach_MMath/Makefile (revision 1f9a4d0ea5207988f1865f786e53bb8849f607b8) +++ doc/theses/andrew_beach_MMath/Makefile (revision 4432b52ff17e976caa39d57935a4bca5281718a7) @@ -31,5 +31,4 @@ ${GLOSSARY} ${BUILD}/${BASE} ${LATEX} ${BASE} - ${LATEX} ${BASE} ${DOC}: ${BUILD}/${DOC} Index: doc/theses/andrew_beach_MMath/cfalab.sty =================================================================== --- doc/theses/andrew_beach_MMath/cfalab.sty (revision 1f9a4d0ea5207988f1865f786e53bb8849f607b8) +++ doc/theses/andrew_beach_MMath/cfalab.sty (revision 4432b52ff17e976caa39d57935a4bca5281718a7) @@ -27,4 +27,17 @@ % Cforall with the forall symbol. \newsymbolcmd\CFA{\textsf{C}\raisebox{\depth}{\rotatebox{180}{\textsf{A}}}} +% C++ with kerning. (No standard number support.) +\newsymbolcmd\CPP{\textrm{C}\kern-.1em\hbox{+\kern-.25em+}} + +% This is executed very early in the \begin{document} code. +\AtEndPreamble{ + \@ifpackageloaded{hyperref}{ + % Convert symbols to pdf compatable forms when required. + \pdfstringdefDisableCommands{ + \def\CFA{CFA} + \def\CPP{C++} + } + }{} +} % The CFA listings language. Based off of ANCI C and including GCC extensions. @@ -72,13 +85,3 @@ \renewcommand\textunderscore{\csuse{cfalab@textunderscore@#1}}} -% This is executed very early in the \begin{document} code. -\AtEndPreamble{ - \@ifpackageloaded{hyperref}{ - % Convert symbols to pdf compatable forms when required. - \pdfstringdefDisableCommands{ - \def\CFA{CFA} - } - }{} -} - \endinput Index: doc/theses/andrew_beach_MMath/existing.tex =================================================================== --- doc/theses/andrew_beach_MMath/existing.tex (revision 4432b52ff17e976caa39d57935a4bca5281718a7) +++ doc/theses/andrew_beach_MMath/existing.tex (revision 4432b52ff17e976caa39d57935a4bca5281718a7) @@ -0,0 +1,237 @@ +\chapter{\CFA{} Existing Features} + +\section{Overloading and extern} +Cforall has overloading, allowing multiple definitions of the same name to +be defined. + +This also adds name mangling so that the assembly symbols are unique for +different overloads. For compatability with names in C there is also a +syntax to diable the name mangling. These unmangled names cannot be overloaded +but act as the interface between C and \CFA code. + +The syntax for disabling mangling is: +\begin{lstlisting} +extern "C" { + ... +} +\end{lstlisting} + +To re-enable mangling once it is disabled the syntax is: +\begin{lstlisting} +extern "Cforall" { + ... +} +\end{lstlisting} + +Both should occur at the declaration level and effect all the declarations +in \texttt{...}. Neither care about the state of mangling when they begin +and will return to that state after the group is finished. So re-enabling +is only used to nest areas of mangled and unmangled declarations. + +\section{References} +\CFA adds references to C. These are auto-dereferencing pointers and use the +same syntax as pointers except they use ampersand (\codeCFA{\&}) instead of +the asterisk (\codeCFA{*}). They can also be constaint or mutable, if they +are mutable they may be assigned to by using the address-of operator +(\codeCFA\&) which converts them into a pointer. + +\section{Constructors and Destructors} + +Both constructors and destructors are operators, which means they are just +functions with special names. The special names are used to define them and +may be used to call the functions expicately. The \CFA special names are +constructed by taking the tokens in the operators and putting \texttt{?} where +the arguments would go. So multiplication is \texttt{?*?} while dereference +is \texttt{*?}. This also make it easy to tell the difference between +pre-fix operations (such as \texttt{++?}) and post-fix operations +(\texttt{?++}). + +The special name for contructors is \texttt{?\{\}}, which comes from the +initialization syntax in C. The special name for destructors is +\texttt{\^{}?\{\}}. % I don't like the \^{} symbol but $^\wedge$ isn't better. + +Any time a type T goes out of scope the destructor matching +\codeCFA{void ^?\{\}(T \&);} is called. In theory this is also true of +primitive types such as \codeCFA{int}, but in practice those are no-ops and +are usually omitted for optimization. + +\section{Polymorphism} +\CFA uses polymorphism to create functions and types that are defined over +different types. \CFA polymorphic declarations serve the same role as \CPP +templates or Java generics. + +Polymorphic declaractions start with a forall clause that goes before the +standard (monomorphic) declaration. These declarations have the same syntax +except that you may use the names introduced by the forall clause in them. + +Forall clauses are written \codeCFA{forall( ... )} where \codeCFA{...} becomes +the list of polymorphic variables (local type names) and assertions, which +repersent required operations on those types. + +\begin{lstlisting} +forall(dtype T | { void do_once(T &); }) +void do_twice(T & value) { + do_once(value); + do_once(value); +} +\end{lstlisting} + +A polymorphic function can be used in the same way normal functions are. +The polymorphics variables are filled in with concrete types and the +assertions are checked. An assertion checked by seeing if that name of that +type (with all the variables replaced with the concrete types) is defined at +the the call site. + +As an example, even if no function named \codeCFA{do\_once} is not defined +near the definition of \codeCFA{do\_twice} the following code will work. +\begin{lstlisting} +int quadruple(int x) { + void do_once(int & y) { + y = y * 2; + } + do_twice(x); + return x; +} +\end{lstlisting} +This is not the recommended way to implement a quadruple function but it +does work. The complier will deduce that \codeCFA{do\_twice}'s T is an +integer from the argument. It will then look for a definition matching the +assertion which is the \codeCFA{do\_once} defined within the function. That +function will be passed in as a function pointer to \codeCFA{do\_twice} and +called within it. + +To avoid typing out long lists of assertions again and again there are also +traits which collect assertions into convenent packages that can then be used +in assertion lists instead of all of their components. +\begin{lstlisting} +trait done_once(dtype T) { + void do_once(T &); +} +\end{lstlisting} + +After this the forall list in the previous example could instead be written +with the trait instead of the assertion itself. +\begin{lstlisting} +forall(dtype T | done_once(T)) +\end{lstlisting} + +Traits can have arbitrary number of assertions in them and are usually used to +create short hands for, and give descriptive names to, commond groupings of +assertions. + +Polymorphic structures and unions may also be defined by putting a forall +clause before the declaration. The type variables work the same way except +are now used in field declaractions instead of parameters and local variables. + +\begin{lstlisting} +forall(dtype T) +struct node { + node(T) * next; + T * data; +} +\end{lstlisting} + +The \codeCFA{node(T)} is a use of a polymorphic structure. Polymorphic types +must be provided their polymorphic parameters. + +There are many other features of polymorphism that have not given here but +these are the ones used by the exception system. + +\section{Concurrency} + +\CFA has a number of concurrency features, \codeCFA{thread}s, +\codeCFA{monitor}s and \codeCFA{mutex} parameters, \codeCFA{coroutine}s and +\codeCFA{generator}s. The two features that interact with the exception system +are \codeCFA{thread}s and \codeCFA{coroutine}s; they and their supporting +constructs will be described here. + +\subsection{Coroutines} +Coroutines are routines that do not have to finish execution to hand control +back to their caller, instead they may suspend their execution at any time +and resume it later. +Coroutines are not true concurrency but share some similarities and many of +the same underpinnings and so are included as part of the \CFA threading +library. + +In \CFA coroutines are created using the \codeCFA{coroutine} keyword which +works just like \codeCFA{struct} except that the created structure will be +modified by the compiler to satify the \codeCFA{is\_coroutine} trait. + +These structures act as the interface between callers and the coroutine, +the fields are used to pass information in and out. Here is a simple example +where the single field is used to pass the next number in a sequence out. +\begin{lstlisting} +coroutine CountUp { + unsigned int next; +} +\end{lstlisting} + +The routine part of the coroutine is a main function for the coroutine. It +takes a reference to a coroutine object and returns nothing. In this function, +and any functions called by this function, the suspend statement may be used +to return execution to the coroutine's caller. When control returns to the +function it continue from that same suspend statement instead of at the top +of the function. +\begin{lstlisting} +void main(CountUp & this) { + unsigned int next = 0; + while (true) { + this.next = next; + suspend; + next = next + 1; + } +} +\end{lstlisting} + +Control is passed to the coroutine with the resume function. This includes the +first time when the coroutine is starting up. The resume function takes a +reference to the coroutine structure and returns the same reference. The +return value is for easy access to communication variables. For example the +next value from a count-up can be generated and collected in a single +expression: \codeCFA{resume(count).next}. + +\subsection{Monitors and Mutex} + +True concurrency does not garrenty ordering. To get some of that ordering back +\CFA uses monitors and mutex (mutual exclution) parameters. A monitor is +another special declaration that contains a lock and is compatable with mutex +parameters. + +Function parameters can have the \codeCFA{mutex} qualifiers on reference +arguments, for example \codeCFA{void example(a_monitor & mutex arg);}. When the +function is called it will acquire the lock on all of the mutex parameters. + +This means that all functions that mutex on a type are part of a critical +section and only one will ever run at a time. + +\subsection{Threads} +While coroutines allow new things to be done with a single execution path +threads actually introduce new paths of execution that continue independently. +Now for threads to work together their must be some communication between them +and that means the timing of certain operations does have to be known. There +or various means of syncronization and mutual exclution provided by \CFA but +for exceptions only the basic two -- fork and join -- are needed. + +Threads are created like coroutines except the keyword is changed: +\begin{lstlisting} +thread StringWorker { + const char * input; + int result; +}; + +void main(StringWorker & this) { + const char * localCopy = this.input; + // ... do some work, perhaps hashing the string ... + this.result = result; +} +\end{lstlisting} +The main function will start executing after the fork operation and continue +executing until it is finished. If another thread joins with this one it will +wait until main has completed execution. In other words everything the thread +does is between fork and join. + +From the outside this is the creation and destruction of the thread object. +Fork happens after the constructor is run and join happens before the +destructor runs. Join also happens during the \codeCFA{join} function which +can be used to join a thread earlier. If it is used the destructor does not +join as that has already been completed. Index: doc/theses/andrew_beach_MMath/thesis.tex =================================================================== --- doc/theses/andrew_beach_MMath/thesis.tex (revision 1f9a4d0ea5207988f1865f786e53bb8849f607b8) +++ doc/theses/andrew_beach_MMath/thesis.tex (revision 4432b52ff17e976caa39d57935a4bca5281718a7) @@ -50,5 +50,8 @@ % MAIN BODY %---------------------------------------------------------------------- +\input{existing} +\input{features} \input{unwinding} +\input{future} %====================================================================== Index: src/ResolvExpr/AlternativeFinder.cc =================================================================== --- src/ResolvExpr/AlternativeFinder.cc (revision 1f9a4d0ea5207988f1865f786e53bb8849f607b8) +++ src/ResolvExpr/AlternativeFinder.cc (revision 4432b52ff17e976caa39d57935a4bca5281718a7) @@ -251,5 +251,5 @@ SemanticError( expr, "No reasonable alternatives for expression " ); } - if ( mode.satisfyAssns || mode.prune ) { + if ( mode.prune ) { // trim candidates just to those where the assertions resolve // - necessary pre-requisite to pruning Index: src/ResolvExpr/CandidateFinder.cpp =================================================================== --- src/ResolvExpr/CandidateFinder.cpp (revision 1f9a4d0ea5207988f1865f786e53bb8849f607b8) +++ src/ResolvExpr/CandidateFinder.cpp (revision 4432b52ff17e976caa39d57935a4bca5281718a7) @@ -1645,76 +1645,115 @@ /// Prunes a list of candidates down to those that have the minimum conversion cost for a given /// return type. Skips ambiguous candidates. - CandidateList pruneCandidates( CandidateList & candidates ) { - struct PruneStruct { - CandidateRef candidate; - bool ambiguous; - - PruneStruct() = default; - PruneStruct( const CandidateRef & c ) : candidate( c ), ambiguous( false ) {} - }; - - // find lowest-cost candidate for each type - std::unordered_map< std::string, PruneStruct > selected; - for ( CandidateRef & candidate : candidates ) { - std::string mangleName; + +} // anonymous namespace + +bool CandidateFinder::pruneCandidates( CandidateList & candidates, CandidateList & out, std::vector & errors ) { + struct PruneStruct { + CandidateRef candidate; + bool ambiguous; + + PruneStruct() = default; + PruneStruct( const CandidateRef & c ) : candidate( c ), ambiguous( false ) {} + }; + + // find lowest-cost candidate for each type + std::unordered_map< std::string, PruneStruct > selected; + // attempt to skip satisfyAssertions on more expensive alternatives if better options have been found + std::sort(candidates.begin(), candidates.end(), [](const CandidateRef & x, const CandidateRef & y){return x->cost < y->cost;}); + for ( CandidateRef & candidate : candidates ) { + std::string mangleName; + { + ast::ptr< ast::Type > newType = candidate->expr->result; + assertf(candidate->expr->result, "Result of expression %p for candidate is null", candidate->expr.get()); + candidate->env.apply( newType ); + mangleName = Mangle::mangle( newType ); + } + + auto found = selected.find( mangleName ); + if (found != selected.end() && found->second.candidate->cost < candidate->cost) { + PRINT( + std::cerr << "cost " << candidate->cost << " loses to " + << found->second.candidate->cost << std::endl; + ) + continue; + } + + // xxx - when do satisfyAssertions produce more than 1 result? + // this should only happen when initial result type contains + // unbound type parameters, then it should never be pruned by + // the previous step, since renameTyVars guarantees the mangled name + // is unique. + CandidateList satisfied; + bool needRecomputeKey = false; + if (candidate->need.empty()) { + satisfied.emplace_back(candidate); + } + else { + satisfyAssertions(candidate, localSyms, satisfied, errors); + needRecomputeKey = true; + } + + for (auto & newCand : satisfied) { + // recomputes type key, if satisfyAssertions changed it + if (needRecomputeKey) { - ast::ptr< ast::Type > newType = candidate->expr->result; - assertf(candidate->expr->result, "Result of expression %p for candidate is null", candidate->expr.get()); - candidate->env.apply( newType ); + ast::ptr< ast::Type > newType = newCand->expr->result; + assertf(newCand->expr->result, "Result of expression %p for candidate is null", newCand->expr.get()); + newCand->env.apply( newType ); mangleName = Mangle::mangle( newType ); } - auto found = selected.find( mangleName ); if ( found != selected.end() ) { - if ( candidate->cost < found->second.candidate->cost ) { + if ( newCand->cost < found->second.candidate->cost ) { PRINT( - std::cerr << "cost " << candidate->cost << " beats " + std::cerr << "cost " << newCand->cost << " beats " << found->second.candidate->cost << std::endl; ) - found->second = PruneStruct{ candidate }; - } else if ( candidate->cost == found->second.candidate->cost ) { + found->second = PruneStruct{ newCand }; + } else if ( newCand->cost == found->second.candidate->cost ) { // if one of the candidates contains a deleted identifier, can pick the other, // since deleted expressions should not be ambiguous if there is another option // that is at least as good - if ( findDeletedExpr( candidate->expr ) ) { + if ( findDeletedExpr( newCand->expr ) ) { // do nothing PRINT( std::cerr << "candidate is deleted" << std::endl; ) } else if ( findDeletedExpr( found->second.candidate->expr ) ) { PRINT( std::cerr << "current is deleted" << std::endl; ) - found->second = PruneStruct{ candidate }; + found->second = PruneStruct{ newCand }; } else { PRINT( std::cerr << "marking ambiguous" << std::endl; ) found->second.ambiguous = true; } - } else { + } else { + // xxx - can satisfyAssertions increase the cost? PRINT( - std::cerr << "cost " << candidate->cost << " loses to " + std::cerr << "cost " << newCand->cost << " loses to " << found->second.candidate->cost << std::endl; - ) + ) } } else { - selected.emplace_hint( found, mangleName, candidate ); - } - } - - // report unambiguous min-cost candidates - CandidateList out; - for ( auto & target : selected ) { - if ( target.second.ambiguous ) continue; - - CandidateRef cand = target.second.candidate; - - ast::ptr< ast::Type > newResult = cand->expr->result; - cand->env.applyFree( newResult ); - cand->expr = ast::mutate_field( - cand->expr.get(), &ast::Expr::result, move( newResult ) ); - - out.emplace_back( cand ); - } - return out; + selected.emplace_hint( found, mangleName, newCand ); + } + } } -} // anonymous namespace + // report unambiguous min-cost candidates + // CandidateList out; + for ( auto & target : selected ) { + if ( target.second.ambiguous ) continue; + + CandidateRef cand = target.second.candidate; + + ast::ptr< ast::Type > newResult = cand->expr->result; + cand->env.applyFree( newResult ); + cand->expr = ast::mutate_field( + cand->expr.get(), &ast::Expr::result, move( newResult ) ); + + out.emplace_back( cand ); + } + // if everything is lost in satisfyAssertions, report the error + return !selected.empty(); +} void CandidateFinder::find( const ast::Expr * expr, ResolvMode mode ) { @@ -1739,4 +1778,5 @@ } + /* if ( mode.satisfyAssns || mode.prune ) { // trim candidates to just those where the assertions are satisfiable @@ -1761,4 +1801,5 @@ candidates = move( satisfied ); } + */ if ( mode.prune ) { @@ -1769,15 +1810,26 @@ ) - CandidateList pruned = pruneCandidates( candidates ); + CandidateList pruned; + std::vector errors; + bool found = pruneCandidates( candidates, pruned, errors ); if ( mode.failFast && pruned.empty() ) { std::ostringstream stream; - CandidateList winners = findMinCost( candidates ); - stream << "Cannot choose between " << winners.size() << " alternatives for " - "expression\n"; - ast::print( stream, expr ); - stream << " Alternatives are:\n"; - print( stream, winners, 1 ); - SemanticError( expr->location, stream.str() ); + if (found) { + CandidateList winners = findMinCost( candidates ); + stream << "Cannot choose between " << winners.size() << " alternatives for " + "expression\n"; + ast::print( stream, expr ); + stream << " Alternatives are:\n"; + print( stream, winners, 1 ); + SemanticError( expr->location, stream.str() ); + } + else { + stream << "No alternatives with satisfiable assertions for " << expr << "\n"; + for ( const auto& err : errors ) { + stream << err; + } + SemanticError( expr->location, stream.str() ); + } } Index: src/ResolvExpr/CandidateFinder.hpp =================================================================== --- src/ResolvExpr/CandidateFinder.hpp (revision 1f9a4d0ea5207988f1865f786e53bb8849f607b8) +++ src/ResolvExpr/CandidateFinder.hpp (revision 4432b52ff17e976caa39d57935a4bca5281718a7) @@ -40,4 +40,5 @@ /// Fill candidates with feasible resolutions for `expr` void find( const ast::Expr * expr, ResolvMode mode = {} ); + bool pruneCandidates( CandidateList & candidates, CandidateList & out, std::vector & errors ); /// Runs new candidate finder on each element in xs, returning the list of finders Index: src/ResolvExpr/ResolvMode.h =================================================================== --- src/ResolvExpr/ResolvMode.h (revision 1f9a4d0ea5207988f1865f786e53bb8849f607b8) +++ src/ResolvExpr/ResolvMode.h (revision 4432b52ff17e976caa39d57935a4bca5281718a7) @@ -22,27 +22,26 @@ const bool prune; ///< Prune alternatives to min-cost per return type? [true] const bool failFast; ///< Fail on no resulting alternatives? [true] - const bool satisfyAssns; ///< Satisfy assertions? [false] private: - constexpr ResolvMode(bool a, bool p, bool ff, bool sa) - : adjust(a), prune(p), failFast(ff), satisfyAssns(sa) {} + constexpr ResolvMode(bool a, bool p, bool ff) + : adjust(a), prune(p), failFast(ff) {} public: /// Default settings - constexpr ResolvMode() : adjust(false), prune(true), failFast(true), satisfyAssns(false) {} + constexpr ResolvMode() : adjust(false), prune(true), failFast(true) {} /// With adjust flag set; turns array and function types into equivalent pointers - static constexpr ResolvMode withAdjustment() { return { true, true, true, false }; } + static constexpr ResolvMode withAdjustment() { return { true, true, true }; } /// With adjust flag set but prune unset; pruning ensures there is at least one alternative /// per result type - static constexpr ResolvMode withoutPrune() { return { true, false, true, false }; } + static constexpr ResolvMode withoutPrune() { return { true, false, true }; } /// With adjust and prune flags set but failFast unset; failFast ensures there is at least /// one resulting alternative - static constexpr ResolvMode withoutFailFast() { return { true, true, false, false }; } + static constexpr ResolvMode withoutFailFast() { return { true, true, false }; } /// The same mode, but with satisfyAssns turned on; for top-level calls - ResolvMode atTopLevel() const { return { adjust, prune, failFast, true }; } + ResolvMode atTopLevel() const { return { adjust, true, failFast }; } }; } // namespace ResolvExpr Index: src/ResolvExpr/SatisfyAssertions.hpp =================================================================== --- src/ResolvExpr/SatisfyAssertions.hpp (revision 1f9a4d0ea5207988f1865f786e53bb8849f607b8) +++ src/ResolvExpr/SatisfyAssertions.hpp (revision 4432b52ff17e976caa39d57935a4bca5281718a7) @@ -27,5 +27,6 @@ namespace ResolvExpr { -/// Recursively satisfies all assertions provided in a candidate; returns true if succeeds +/// Recursively satisfies all assertions provided in a candidate +/// returns true if it has been run (candidate has any assertions) void satisfyAssertions( CandidateRef & cand, const ast::SymbolTable & symtab, CandidateList & out,