summaryrefslogtreecommitdiffstats
path: root/final_project/paper
diff options
context:
space:
mode:
authorbnewbold <bnewbold@eta.mit.edu>2009-05-11 13:45:12 -0400
committerbnewbold <bnewbold@eta.mit.edu>2009-05-11 13:45:12 -0400
commit38e10dc81d5f8f1a2bbededb790e775c0c637d6c (patch)
treec1c97634df0c0ff31f70d87462ad1f1390fd301f /final_project/paper
parentca6558941cf604b2e5ddb8fe38261091a99f6d09 (diff)
download6.945-38e10dc81d5f8f1a2bbededb790e775c0c637d6c.tar.gz
6.945-38e10dc81d5f8f1a2bbededb790e775c0c637d6c.zip
files from laura
Diffstat (limited to 'final_project/paper')
-rw-r--r--final_project/paper/bnewbold_lch_report_draft.lyx2159
-rw-r--r--final_project/paper/outline25
2 files changed, 1659 insertions, 525 deletions
diff --git a/final_project/paper/bnewbold_lch_report_draft.lyx b/final_project/paper/bnewbold_lch_report_draft.lyx
index d141996..c7f39b4 100644
--- a/final_project/paper/bnewbold_lch_report_draft.lyx
+++ b/final_project/paper/bnewbold_lch_report_draft.lyx
@@ -31,7 +31,11 @@
\begin_body
\begin_layout Title
-Generic Operator Discovery
+Generic Operator Discovery:
+\newline
+
+\emph on
+10,000 Monkeys with 10,000 Lambdas
\end_layout
\begin_layout Date
@@ -48,13 +52,14 @@ Laura Harris and Bryan Newbold for 6.945
\end_layout
\begin_layout Abstract
-We present a hardware design to convert captured images to an audio stream.
- There are a wealth of real time
-\emph on
-software
-\emph default
- implementations of the Fast Fourier Transform (FFT), but we use a Field
- Programable Gate Array
+We have implemented a simple system which enables the discovery and exploration
+ of generic operators and brute force predicate satisfaction.
+ Our procedures build on top of existing predicate-based operator dispatch
+ databases; this allows existing code to be reused in useful and unexpected
+ ways.
+ In this write up we describe our code, give a few simple demonstrations
+ (including one with a native graphic user interface), and mention some
+ potential applications.
\end_layout
\begin_layout Standard
@@ -66,663 +71,556 @@ software
\end_layout
\begin_layout Section
-Overview
+Generic Operator Discovery System
\end_layout
\begin_layout Standard
-The Real-Time Audio Composition system allows for the conversion of visually
- encoded information into audio.
- A typical visual encoding program, such as Baudline, takes audio input
- and produces a scrolling visualization of the fast-Fourier transform (FFT).
- Our system could take one of these visualizations and produce ch serve
- as the visual spectrograph to interpreted and played back through headphones
- or speakers.
- A PS/2 mouse allows for control of the GUI system.
- Using the mouse, the user can interact with the buttons, the image itself,
- and a number of other features.
- An image of the GUI is shown in Figure
-\begin_inset LatexCommand \ref{fig:gui_photo}
+The normal purpose of a generic operator dispatch system is to allow the
+ programmer or user to use a single operator with many different object
+ types or combinations of object types.
+ Mature libraries and codebases may have dozens of generic operators defined
+ for domain-specific data structures; these generic operations often represent
+ the core functionality offered by the system.
+ For large systems, those with which the user is unfamiliar, or those with
+ poor documentation, it can be daunting to find the operation desired.
+ By using
+\begin_inset Quotes eld
+\end_inset
+operator discovery
+\begin_inset Quotes erd
\end_inset
-.
-\begin_inset Float figure
-wide false
-sideways false
-status collapsed
+ techniques, the operator dispatch system can be reverse engineered to find
+ all of the generic operations which can be applied to given arguments.
+ In addition to facilitating user exploration, these techniques can be used
+ to improve the robustness of computing systems, as part of automated problem
+ solving, as a testing tool, and for the automated generation of higher
+ level programs.
+\end_layout
\begin_layout Standard
-\begin_inset Graphics
- filename gui_photo.jpg
- display none
- width 5in
- keepAspectRatio
+The generic operator system we have built upon uses predicate dispatch;
+ for an overview of this strategy see [TODO: cite].
+ The version we used for MIT/GNU Scheme was distributed by the 6.945 staff
+ and is included in the appendix as
+\family typewriter
+ghelper.scm
+\family default
+.
+ The exact same dispatch system is used in the scmutils classical mechanics
+ software package, which allowed us to experiment with an existing software
+ system.
+\end_layout
-\end_inset
+\begin_layout Section
+Implementation
+\end_layout
+\begin_layout Standard
+For examples and demonstrations of the system, see the applications section
+ and the file
+\family typewriter
+discovery-examples.scm
+\family default
+ in the appendix.
+\end_layout
+\begin_layout Subsection
+Review of Predicate Dispatch
\end_layout
-\begin_layout Caption
-A photograph of the GUI implemented in the Real Time Audio Composition system.
- Each area of the screen will be explained in detail.
+\begin_layout Standard
+Predicate dispatch works by choosing the first
\emph on
-
-\newline
-(Source: Team Member)
+handler
\emph default
+ whose associated
+\emph on
+predicates
+\emph default
+ all return true for a given set of arguments; a list of predicate/handler
+ pairs is stored in a tree structure for each generic operator.
+\end_layout
-\begin_inset LatexCommand \label{fig:gui_photo}
-
-\end_inset
-
+\begin_layout Standard
+A few crucial procedures, globals, and data structures are defined in
+\family typewriter
+ghelper.scm:
+\end_layout
+\begin_layout Paragraph*
+*generic-operator-table*
\end_layout
+\begin_layout Standard
+This is the global table of generic operators.
+ It is an
+\family typewriter
+eq-hash
+\family default
+ table which associates operator record
+\emph on
+keys
+\emph default
+ (which define the arity) with predicate/handler tree
+\emph on
+values
+\emph default
+.
+ In addition, for
+\begin_inset Quotes eld
\end_inset
+named
+\begin_inset Quotes erd
+\end_inset
+ operators, the symbol representing an operator is added as a second
+\emph on
+key
+\emph default
+ pointing at the same predicate/handler tree
+\emph on
+value
+\emph default
+.
+
\end_layout
-\begin_layout Standard
-The GUI allows for a number of functions.
- An edit function, regrettably never fully implemented due to time constraints,
- would allow for the direct editing of captured images by manually selecting
- an eight bit binary lved with the time domain audio data to produce the
- audio signal.
- The AC97 audio chip in the FPGA runs at a clock speed of 48kHz so the audio
- samples must also be up-sampled to produce the final signal.
+\begin_layout Paragraph*
+(make-generic-operator arity default-operation #!optional name)
\end_layout
\begin_layout Standard
-t vector with at least 1024 bins is required.
- Aliever, a full wrapper module was necessary to load samples in and out
- of the module, enable and disable processing, ensure sample index synchronizati
-on, etc.
- The ifft_wrapper module ensures that only the 12-bit real components are
- written and that both the 8-bit phase and 12-bit complex components are
- tied to 0 at input and ignored at output.
-\end_layout
-
-\begin_layout Standard
-\align center
-\begin_inset Float table
-placement h
-wide false
-sideways false
-status collapsed
-
-\begin_layout Standard
-\align center
-\begin_inset Tabular
-<lyxtabular version="3" rows="8" columns="2">
-<features>
-<column alignment="center" valignment="top" width="0">
-<column alignment="center" valignment="top" width="0">
-<row bottomline="true">
-<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
-\begin_inset Text
-
-\begin_layout Standard
+This procedure creates a new record in the
+\family typewriter
+*generic-operator-table*
+\family default
+ for the given arity; it returns an operator procedure which is usually
+ bound in the user's environment and when applied initiates the procedure
+ dispatch process.
+ If not null, the default-operation is bound (using assign-operation) as
+ an any-argument-accepting default handler.
+ If passed, the name (which should be a symbol) is bound as a redundant
+ key in the
+\family typewriter
+*generic-operator-table*
+\family default
+.
-\family roman
\series bold
-\shape up
-\size normal
-\emph off
-\bar no
-\noun off
-\color none
-Setting
+ defhandler
+\series default
+ is an alias for make-generic-operator.
\end_layout
-\end_inset
-</cell>
-<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
-\begin_inset Text
+\begin_layout Paragraph*
+(assign-operation operator handler .
+ argument-predicates)
+\end_layout
\begin_layout Standard
-
-\family roman
-\series bold
-\shape up
-\size normal
-\emph off
-\bar no
-\noun off
-\color none
-Value
+This procedure adds a new predicate/handler pair to an operator's tree in
+ the *generic-operator-table*.
+ The binding is done with
+\family typewriter
+bind-in-tree
+\family default
+ (see below).
\end_layout
-\end_inset
-</cell>
-</row>
-<row topline="true">
-<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
-\begin_inset Text
+\begin_layout Paragraph*
+(bind-in-tree keys handler tree)
+\end_layout
\begin_layout Standard
-
-\family roman
-\series medium
-\shape up
-\size normal
-\emph off
-\bar no
-\noun off
-\color none
-Generator Version
+This procedure simply adds a new handler (with the argument predicates
+\emph on
+keys
+\emph default
+) in a given generic operator's dispatch
+\emph on
+tree
+\emph default
+.
+
\end_layout
-\end_inset
-</cell>
-<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
-\begin_inset Text
+\begin_layout Subsection
+Procedures
+\end_layout
\begin_layout Standard
-
-\family roman
-\series medium
-\shape up
-\size normal
-\emph off
-\bar no
-\noun off
-\color none
- Fast Fourier Transform 3.2
+The actual implementations of these procedures can be found in the appendix.
\end_layout
-\end_inset
-</cell>
-</row>
-<row topline="true">
-<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
-\begin_inset Text
+\begin_layout Subsubsection*
+(discover:opers-for .
+ args)
+\end_layout
\begin_layout Standard
-
-\family roman
-\series medium
-\shape up
-\size normal
-\emph off
-\bar no
-\noun off
-\color none
-Input Length
+This procedure returns all of the operators which can be applied to the
+ arguments.
+ The return value is a list of the keys from *generic-operator-table* which
+ are associated with predicate/handler trees matching the arguments.
+ This is the core of the discovery system.
\end_layout
-\end_inset
-</cell>
-<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
-\begin_inset Text
+\begin_layout Subsubsection*
+(discover:named-opers-for .
+ args)
+\end_layout
\begin_layout Standard
+This procedure is the same as discover:opers-for except that it only returns
+ lookup keys which are symbols (thus the original operator record was defined
+ with a name symbol).
+
+\end_layout
-\family roman
-\series medium
-\shape up
-\size normal
-\emph off
-\bar no
-\noun off
-\color none
-2048 samples
+\begin_layout Paragraph*
+(discover:named-opers)
\end_layout
+\begin_layout Standard
+This procedure returns a list of
+\emph on
+all
+\emph default
+ the
+\begin_inset Quotes eld
\end_inset
-</cell>
-</row>
-<row topline="true">
-<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
-\begin_inset Text
-\begin_layout Standard
+named
+\begin_inset Quotes erd
+\end_inset
-\family roman
-\series medium
-\shape up
-\size normal
-\emph off
-\bar no
-\noun off
-\color none
-Processing Mode
+ generic operators in the
+\family typewriter
+*generic-operator-table*
+\family default
+ ; it is useful to determine the size of scope of an unknown software system.
\end_layout
-\end_inset
-</cell>
-<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
-\begin_inset Text
+\begin_layout Paragraph*
+(discover:apply-name name .
+ args)
+\end_layout
\begin_layout Standard
+This procedure allows
+\begin_inset Quotes eld
+\end_inset
-\family roman
-\series medium
-\shape up
-\size normal
-\emph off
-\bar no
-\noun off
-\color none
-Pipelined
+named
+\begin_inset Quotes erd
+\end_inset
+
+ operator symbols to be treated like actual operator procedures: it initiates
+ the dispatch process for the predicate/handler tree associated with
+\emph on
+name
+\emph default
+ for the given
+\emph on
+args
+\emph default
+.
+
\end_layout
-\end_inset
-</cell>
-</row>
-<row topline="true">
-<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
-\begin_inset Text
+\begin_layout Paragraph*
+(discover:apply-all .
+ args)
+\end_layout
\begin_layout Standard
+This procedure finds all of the operators which can act on the given args,
+ then returns a list with the results of applying each of these operators.
+\end_layout
-\family roman
-\series medium
-\shape up
-\size normal
-\emph off
-\bar no
-\noun off
-\color none
-Sample bitwidth
+\begin_layout Paragraph*
+(discover:apply-all-name .
+ args)
\end_layout
+\begin_layout Standard
+This is identical to
+\family typewriter
+discover:apply-all
+\family default
+ except that it only applies
+\begin_inset Quotes eld
\end_inset
-</cell>
-<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
-\begin_inset Text
-\begin_layout Standard
+named
+\begin_inset Quotes erd
+\end_inset
-\family roman
-\series medium
-\shape up
-\size normal
-\emph off
-\bar no
-\noun off
-\color none
-12-bit signed
+ operators.
+
\end_layout
-\end_inset
-</cell>
-</row>
-<row topline="true">
-<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
-\begin_inset Text
+\begin_layout Paragraph*
+(discover:satisfy pred? .
+ args)
+\end_layout
\begin_layout Standard
-
-\family roman
-\series medium
-\shape up
-\size normal
-\emph off
-\bar no
-\noun off
-\color none
-Output ordering
+This procedure attempts to satisfy the given predicate by repeatedly applying
+ all possible operators the arguments (and the return values of these applicatio
+ns recursively).
+ It operates as a breadth first search and returns the first matching return
+ value.
\end_layout
-\end_inset
-</cell>
-<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
-\begin_inset Text
+\begin_layout Paragraph*
+(discover:satisfy-sequence pred? .
+ args)
+\end_layout
\begin_layout Standard
+This procedure is similar to
+\family typewriter
+discover:satisfy
+\family default
+ except that it only applies
+\begin_inset Quotes eld
+\end_inset
-\family roman
-\series medium
-\shape up
-\size normal
-\emph off
-\bar no
-\noun off
-\color none
-Natural
-\end_layout
+named
+\begin_inset Quotes erd
+\end_inset
+ operators and it maintains a record of which operators were applied to
+ obtain a given return value; it will also return all of the matching return
+ values for a given
+\begin_inset Quotes eld
\end_inset
-</cell>
-</row>
-<row topline="true">
-<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
-\begin_inset Text
-\begin_layout Standard
+depth
+\begin_inset Quotes erd
+\end_inset
-\family roman
-\series medium
-\shape up
-\size normal
-\emph off
-\bar no
-\noun off
-\color none
-Clock enable pin
+ of search.
\end_layout
-\end_inset
-</cell>
-<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
-\begin_inset Text
+\begin_layout Subsection
+Room for improvement
+\end_layout
\begin_layout Standard
-
-\family roman
-\series medium
-\shape up
-\size normal
-\emph off
-\bar no
-\noun off
-\color none
-Enabled
+The code for all of these procedures is rather ugly and complicated due
+ to the crude data structures used: for example discover:satisfy-sequence
+ has an internal variable to store potential solutions as a list with the
+ first argument being a list of arguments (always a single element after
+ the first application of operators) and all subsequent operators being
+ a record of the operators applied to obtain those arguments.
+ This could almost certainly be reimplemented in a more elegant functional
+ style.
\end_layout
-\end_inset
-</cell>
-</row>
-<row topline="true">
-<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
-\begin_inset Text
+\begin_layout Standard
+The predicate/handler tree format does not currently include a name symbol
+ for the given operator.
+ Perhaps the name symbol could also be determined by searching the environment
+ bindings, but this does not seem like a great idea (search would be slow?).
+\end_layout
\begin_layout Standard
+Almost all of the implementations are ripe for trivial optimization: for
+ example
+\family typewriter
+discover:named-opers-for
+\family default
+ just filters the results of
+\family typewriter
+discover:opers-for
+\family default
+; it could be much more efficient if it filtered out non-symbol operators
+ earlier in the search process.
+\end_layout
-\family roman
-\series medium
-\shape up
-\size normal
-\emph off
-\bar no
-\noun off
-\color none
-Processing Stages
+\begin_layout Section
+Applications
\end_layout
-\end_inset
-</cell>
-<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
-\begin_inset Text
+\begin_layout Subsection
+scmutils Package
+\end_layout
\begin_layout Standard
-
-\family roman
-\series medium
-\shape up
-\size normal
-\emph off
-\bar no
-\noun off
-\color none
-3 using BRAM
+hold
\end_layout
-\end_inset
-</cell>
-</row>
-</lyxtabular>
+\begin_layout Quotation
-\end_inset
+\family typewriter
+(discover:named-opers)
+\end_layout
+\begin_layout Quotation
+\family typewriter
+;Value: (+ one-like cos dot-product expt one? * gcd
\end_layout
-\begin_layout Caption
-IFFT Auto-generation Settings
-\begin_inset LatexCommand \label{tab:ifft_settings}
+\begin_layout Quotation
-\end_inset
+\family typewriter
+partial-derivative acos exp atan2 cosh imag-part one = conjugate
+\end_layout
+\begin_layout Quotation
+\family typewriter
+zero? / zero-like abs sinh identity? sin asin derivative angle
\end_layout
-\end_inset
+\begin_layout Quotation
+\family typewriter
+magnitude inexact? type apply identity make-polar arity real-part -
+\end_layout
+
+\begin_layout Quotation
+\family typewriter
+invert negate identity-like trace determinant sqrt zero log square
\end_layout
-\begin_layout Standard
-onversion is implemented by using each time-domain sample twice, then low
- pass filtering the output to remove the high frequency artifacts introduced.
- This low pass filter also conveniently filters out any noise or aliasing
- occurring in the frequencies above the 720 or so lowest frequencies actually
- specified by image data.
- Note that the up-sampling process also effectively halves the frequency
- corresponding to each bin in our frequency-domain spectral vectors, giving
- better frequency resolution in the lower, more human discernible regime.
+\begin_layout Quotation
+
+\family typewriter
+make-rectangular type-predicate atan1)
\end_layout
\begin_layout Standard
-The low pass filter is implemented almost exactly like in Lab 3, using 31
- tap filters generated in matlab using the command:
+hold
\end_layout
-\begin_layout Verse
+\begin_layout Quotation
\family typewriter
-round(fir1(30,.5)*(2^13))
+(discover:named-opers-for
\end_layout
-\begin_layout Standard
-Each tap is 14-bits signed, thus the scaling by
-\begin_inset Formula $2^{13}$
-\end_inset
+\begin_layout Quotation
-.
- The parameter
-\begin_inset Formula $W_{n}=0.5$
-\end_inset
+\family typewriter
+\InsetSpace ~
+\InsetSpace ~
+\InsetSpace ~
+(matrix-by-rows '(1 0 0) '(0 1 0) '(0 0 1)))
+\end_layout
+
+\begin_layout Quotation
- specifies a cutoff frequency
+\family typewriter
+;Value: (one-like cos exp conjugate zero? zero-like identity? sin
\end_layout
-\begin_layout Standard
-entire packet length is filled (128 values in our case), the IFFT is computed.
- Natural order refers to the ordering of bits on the output.
- Reverse ordering of bits is the natural mode of the IFFT, and since timing
- is not a huge concern at this stage, producing natural order bits is worth
- the time.
- The different stages of the IFFT input and output are controlled by an
- FSM as shown in Figure
+\begin_layout Quotation
+
+\family typewriter
+inexact? type arity invert negate identity-like trace determinant
\end_layout
-\begin_layout Standard
-Unless just reset, at which the FSM is immediately clock enabled and put
- in the setup state so the time domain taps can be initialized, the FSM
- naturally idles in the wait state.
- With the edge detection of a button press release within the bode plot,
- the FSM enters the setup state since it can be assumed that a value within
- the bode plot has changed.
- As soon as the ready for data flag is set high, the FSM enters the write
- state.
- The values from the bode array are fed into the IFFT, lagging behind three
- cycles as designated by the datasheet.
- After all data has been entered, the FSM enters the read state.
- The resulting tap indices and values are completely synchronous at this
- point and can be fed directly into the tap manager which will hold the
- resultant values.
+\begin_layout Quotation
+
+\family typewriter
+type-predicate)
\end_layout
\begin_layout Standard
-Memory Management
+hold
\end_layout
-\begin_layout Address
+\begin_layout Quotation
-\emph on
-Author: Dimitri Turbiner
+\family typewriter
+(discover:named-opers-for 'a)
\end_layout
-\begin_layout Standard
-The memory control module uses four interface modules to communicate with
- the Camera, GUI, and IFFT subsystems and two interface modules to control
- the physical SRAM chips on the LabKit.
- The camera_to_zbt interface module, keeps track of the sync signals coming
- from the Camera subsystem in order to compute the memory destination address.
- Incomming pixels are buffered and packed together into groups of four.
- When such a group of four is ready, the memory controller is signalled
- by camera_we.
- The input signals are all synchronized to the clock in the Camera subsystem
- -- 27mHz, while the output signals have to be synchronized at the memory
- clock -- 65mHz.
- Thus, the camera_to_zbt module has to perform clock resynchronization between
- the two subsystems it connects.
- The zbt_to_display, zbt_to_ifft, edit_to_zbt, modules all compute the memory
- destination address based on the requested pixel horizontal and vertical
- index (hcount and vcount), and when signalled by the memory controller
- that data is valid, pack or unpack four 8bit pixels to/from the 36 bit
- data bus.
-
+\begin_layout Quotation
+
+\family typewriter
+;Value: (one-like cos acos exp cosh imag-part conjugate zero-like
\end_layout
-\begin_layout Standard
-The memory controller controls the two zbt ram access modules depending
- on which memory IO operations have been requested by the subsystems.
- The controller supports latching the various subsystem's data and address
- busses in order to guarantee minimum hold delays and to resolve simultaneous
- memory access requests.
- The latches control logic is built around a memory access priority hierarchy:
-
+\begin_layout Quotation
+
+\family typewriter
+sinh sin asin angle magnitude inexact? type arity real-part invert
\end_layout
\begin_layout Quotation
\family typewriter
-assign main_addr = camera_capture_request ? camera_addr :
+negate identity-like sqrt log type-predicate atan1)
+\end_layout
+
+\begin_layout Standard
+hold
\end_layout
\begin_layout Quotation
\family typewriter
-\InsetSpace ~
-\InsetSpace ~
-\InsetSpace ~
-\InsetSpace ~
-\InsetSpace ~
-\InsetSpace ~
-\InsetSpace ~
-\InsetSpace ~
-\InsetSpace ~
-\InsetSpace ~
-\InsetSpace ~
-\InsetSpace ~
-\InsetSpace ~
-\InsetSpace ~
-\InsetSpace ~
-\InsetSpace ~
-\InsetSpace ~
-\InsetSpace ~
-\InsetSpace ~
-(display_read_request ? display_addr :
+(discover:named-opers-for (compose sin cos))
\end_layout
\begin_layout Quotation
\family typewriter
-\InsetSpace ~
-\InsetSpace ~
-\InsetSpace ~
-\InsetSpace ~
-\InsetSpace ~
-\InsetSpace ~
-\InsetSpace ~
-\InsetSpace ~
-\InsetSpace ~
-\InsetSpace ~
-\InsetSpace ~
-\InsetSpace ~
-\InsetSpace ~
-\InsetSpace ~
-\InsetSpace ~
-\InsetSpace ~
-\InsetSpace ~
-\InsetSpace ~
-\InsetSpace ~
-(ifft_read_request ? ifft_addr :
+;Value: (one-like cos acos exp cosh imag-part zero-like abs sinh
\end_layout
\begin_layout Quotation
\family typewriter
-\InsetSpace ~
-\InsetSpace ~
-\InsetSpace ~
-\InsetSpace ~
-\InsetSpace ~
-\InsetSpace ~
-\InsetSpace ~
-\InsetSpace ~
-\InsetSpace ~
-\InsetSpace ~
-\InsetSpace ~
-\InsetSpace ~
-\InsetSpace ~
-\InsetSpace ~
-\InsetSpace ~
-\InsetSpace ~
-\InsetSpace ~
-\InsetSpace ~
-\InsetSpace ~
-(edit_write_request ? edit_addr :0)));
+sin asin angle magnitude inexact? type arity real-part invert
\end_layout
-\begin_layout Standard
-problem was also noticed after this implementation.
- When the pixel itself was updated by multiplying the stored bode value
- by the incoming pixel data, a great deal of scattering across the boundaries
- of the image was noticed.
- By pipelining the data within the clocked region, this problem was removed
- and smooth fading occurred.
- (Note: the unimplemented edit mode code uses only slightly different math
- than the bode plot draw function, and should theoretically work, but was
- never tested).
+\begin_layout Quotation
+
+\family typewriter
+negate identity-like sqrt log square type-predicate atan1)
\end_layout
\begin_layout Subsection
-Audio Pipeline
+Other Applications
\end_layout
-\begin_layout Standard
-A number of external tools were crucial for the development and debugging
- of the audio processing pipeline.
- An entire separate labkit module with a parameterized dummy sample generator
- replacing the camera and memory management and no GUI output.
- This allowed for debugging with consistent, simple, noise free spectral
- input.
- This labkit module was also wired to make full use of the hex display (to
- show bode tap index and both horizontal and vertical memory indexes) and
- the logic analyzer connections (all 4 16-bit connectors were used!).
- For instance, Figure shows the IFFT module output of a simple sine wave;
- the clock-like ticks of channels above and below the sine waveform show
- the request and ready signals of the various other stages of the audio
- pipeline.
- Note that this section of the spectral waveform shows the all zero padding
- from the windowing module; the single non-zero sample_value is off screen
- to the left, and the dummy ram module request/ready pins are not toggled.
+\begin_layout Section
+A GUI Interface
\end_layout
-\begin_layout Standard
-A few other buttons and switches came in useful for debugging: Switch #7
- disables the regular audio output
+\begin_layout Subsection
+FFI
\end_layout
-\begin_layout Standard
-Conclusion
+\begin_layout Subsection
+Gtk Bindings
\end_layout
-\begin_layout Address
+\begin_layout Subsection
+Procedures
+\end_layout
-\emph on
-Author: Tyler Hutchison
+\begin_layout Paragraph*
+(discover:thunklist-for .
+ args)
\end_layout
\begin_layout Standard
-The implementation of a real time audio composition system has been described.
- Using the GUI interface, coupled with complex memory interactions, and
- robust audio output, one can use visual information to encode
+This is a special purpose function
+\end_layout
+
+\begin_layout Subsection
+Screenshots
\end_layout
\begin_layout Section
@@ -740,32 +638,31 @@ ghelper.scm
\end_layout
\begin_layout LyX-Code
-////////////////////////////////////////////////////////////////////////////////
-/
+;;; From 6.945 Staff, with minor edit by bnewbold (May 2009):
\end_layout
\begin_layout LyX-Code
-//
+;;; the optional name argument is handled in the style of
\end_layout
\begin_layout LyX-Code
-// 6.111 FPGA Labkit -- Template Toplevel Module
+;;; the scmutils implementation
\end_layout
\begin_layout LyX-Code
-//
+
\end_layout
\begin_layout LyX-Code
-// Author: Nathan Ickes
+;;;; Most General Generic-Operator Dispatch
\end_layout
\begin_layout LyX-Code
-//
+
\end_layout
\begin_layout LyX-Code
-// Edited: Nov 4, 2008, FTW
+(declare (usual-integrations))
\end_layout
\begin_layout LyX-Code
@@ -773,6 +670,394 @@ ghelper.scm
\end_layout
\begin_layout LyX-Code
+;;; Generic-operator dispatch is implemented here by a discrimination
+\end_layout
+
+\begin_layout LyX-Code
+;;; list, where the arguments passed to the operator are examined by
+\end_layout
+
+\begin_layout LyX-Code
+;;; predicates that are supplied at the point of attachment of a
+\end_layout
+
+\begin_layout LyX-Code
+;;; handler (by ASSIGN-OPERATION).
+\end_layout
+
+\begin_layout LyX-Code
+;;; To be the correct branch all arguments must be accepted by
+\end_layout
+
+\begin_layout LyX-Code
+;;; the branch predicates, so this makes it necessary to
+\end_layout
+
+\begin_layout LyX-Code
+;;; backtrack to find another branch where the first argument
+\end_layout
+
+\begin_layout LyX-Code
+;;; is accepted if the second argument is rejected.
+ Here
+\end_layout
+
+\begin_layout LyX-Code
+;;; backtracking is implemented by OR.
+\end_layout
+
+\begin_layout LyX-Code
+
+\end_layout
+
+\begin_layout LyX-Code
+(define (make-generic-operator arity default-operation #!optional name)
+\end_layout
+
+\begin_layout LyX-Code
+ (let ((record (make-operator-record arity)))
+\end_layout
+
+\begin_layout LyX-Code
+ (define (operator .
+ arguments)
+\end_layout
+
+\begin_layout LyX-Code
+ (if (not (= (length arguments) arity))
+\end_layout
+
+\begin_layout LyX-Code
+ (error:wrong-number-of-arguments operator arity arguments))
+\end_layout
+
+\begin_layout LyX-Code
+ (let ((succeed
+\end_layout
+
+\begin_layout LyX-Code
+ (lambda (handler)
+\end_layout
+
+\begin_layout LyX-Code
+ (apply handler arguments))))
+\end_layout
+
+\begin_layout LyX-Code
+ (let per-arg
+\end_layout
+
+\begin_layout LyX-Code
+ ((tree (operator-record-tree record))
+\end_layout
+
+\begin_layout LyX-Code
+ (args arguments)
+\end_layout
+
+\begin_layout LyX-Code
+ (fail
+\end_layout
+
+\begin_layout LyX-Code
+ (lambda ()
+\end_layout
+
+\begin_layout LyX-Code
+ (error:no-applicable-methods operator arguments))))
+\end_layout
+
+\begin_layout LyX-Code
+ (let per-pred ((tree tree) (fail fail))
+\end_layout
+
+\begin_layout LyX-Code
+ (cond ((pair? tree)
+\end_layout
+
+\begin_layout LyX-Code
+ (if ((caar tree) (car args))
+\end_layout
+
+\begin_layout LyX-Code
+ (if (pair? (cdr args))
+\end_layout
+
+\begin_layout LyX-Code
+ (per-arg (cdar tree)
+\end_layout
+
+\begin_layout LyX-Code
+ (cdr args)
+\end_layout
+
+\begin_layout LyX-Code
+ (lambda ()
+\end_layout
+
+\begin_layout LyX-Code
+ (per-pred (cdr tree) fail)))
+\end_layout
+
+\begin_layout LyX-Code
+ (succeed (cdar tree)))
+\end_layout
+
+\begin_layout LyX-Code
+ (per-pred (cdr tree) fail)))
+\end_layout
+
+\begin_layout LyX-Code
+ ((null? tree)
+\end_layout
+
+\begin_layout LyX-Code
+ (fail))
+\end_layout
+
+\begin_layout LyX-Code
+ (else
+\end_layout
+
+\begin_layout LyX-Code
+ (succeed tree)))))))
+\end_layout
+
+\begin_layout LyX-Code
+ (hash-table/put! *generic-operator-table* operator record)
+\end_layout
+
+\begin_layout LyX-Code
+ (if default-operation
+\end_layout
+
+\begin_layout LyX-Code
+ (assign-operation operator default-operation))
+\end_layout
+
+\begin_layout LyX-Code
+ (if (not (default-object? name))
+\end_layout
+
+\begin_layout LyX-Code
+ (hash-table/put! *generic-operator-table* name record))
+\end_layout
+
+\begin_layout LyX-Code
+ operator))
+\end_layout
+
+\begin_layout LyX-Code
+
+\end_layout
+
+\begin_layout LyX-Code
+(define *generic-operator-table*
+\end_layout
+
+\begin_layout LyX-Code
+ (make-eq-hash-table))
+\end_layout
+
+\begin_layout LyX-Code
+(define (make-operator-record arity) (cons arity '()))
+\end_layout
+
+\begin_layout LyX-Code
+(define (operator-record-arity record) (car record))
+\end_layout
+
+\begin_layout LyX-Code
+(define (operator-record-tree record) (cdr record))
+\end_layout
+
+\begin_layout LyX-Code
+(define (set-operator-record-tree! record tree) (set-cdr! record tree))
+\end_layout
+
+\begin_layout LyX-Code
+
+\end_layout
+
+\begin_layout LyX-Code
+(define (assign-operation operator handler .
+ argument-predicates)
+\end_layout
+
+\begin_layout LyX-Code
+ (let ((record
+\end_layout
+
+\begin_layout LyX-Code
+ (let ((record (hash-table/get *generic-operator-table* operator
+ #f))
+\end_layout
+
+\begin_layout LyX-Code
+ (arity (length argument-predicates)))
+\end_layout
+
+\begin_layout LyX-Code
+ (if record
+\end_layout
+
+\begin_layout LyX-Code
+ (begin
+\end_layout
+
+\begin_layout LyX-Code
+ (if (not (<= arity (operator-record-arity record)))
+\end_layout
+
+\begin_layout LyX-Code
+ (error "Incorrect operator arity:" operator))
+\end_layout
+
+\begin_layout LyX-Code
+ record)
+\end_layout
+
+\begin_layout LyX-Code
+ (let ((record (make-operator-record arity)))
+\end_layout
+
+\begin_layout LyX-Code
+ (hash-table/put! *generic-operator-table* operator record)
+\end_layout
+
+\begin_layout LyX-Code
+ record)))))
+\end_layout
+
+\begin_layout LyX-Code
+ (set-operator-record-tree! record
+\end_layout
+
+\begin_layout LyX-Code
+ (bind-in-tree argument-predicates
+\end_layout
+
+\begin_layout LyX-Code
+ handler
+\end_layout
+
+\begin_layout LyX-Code
+ (operator-record-tree record))))
+\end_layout
+
+\begin_layout LyX-Code
+ operator)
+\end_layout
+
+\begin_layout LyX-Code
+
+\end_layout
+
+\begin_layout LyX-Code
+(define defhandler assign-operation)
+\end_layout
+
+\begin_layout LyX-Code
+
+\end_layout
+
+\begin_layout LyX-Code
+(define (bind-in-tree keys handler tree)
+\end_layout
+
+\begin_layout LyX-Code
+ (let loop ((keys keys) (tree tree))
+\end_layout
+
+\begin_layout LyX-Code
+ (if (pair? keys)
+\end_layout
+
+\begin_layout LyX-Code
+ (let find-key ((tree* tree))
+\end_layout
+
+\begin_layout LyX-Code
+ (if (pair? tree*)
+\end_layout
+
+\begin_layout LyX-Code
+ (if (eq? (caar tree*) (car keys))
+\end_layout
+
+\begin_layout LyX-Code
+ (begin
+\end_layout
+
+\begin_layout LyX-Code
+ (set-cdr! (car tree*)
+\end_layout
+
+\begin_layout LyX-Code
+ (loop (cdr keys) (cdar tree*)))
+\end_layout
+
+\begin_layout LyX-Code
+ tree)
+\end_layout
+
+\begin_layout LyX-Code
+ (find-key (cdr tree*)))
+\end_layout
+
+\begin_layout LyX-Code
+ (cons (cons (car keys)
+\end_layout
+
+\begin_layout LyX-Code
+ (loop (cdr keys) '()))
+\end_layout
+
+\begin_layout LyX-Code
+ tree)))
+\end_layout
+
+\begin_layout LyX-Code
+ (if (pair? tree)
+\end_layout
+
+\begin_layout LyX-Code
+ (let ((p (last-pair tree)))
+\end_layout
+
+\begin_layout LyX-Code
+ (if (not (null? (cdr p)))
+\end_layout
+
+\begin_layout LyX-Code
+ (warn "Replacing a handler:" (cdr p) handler))
+\end_layout
+
+\begin_layout LyX-Code
+ (set-cdr! p handler)
+\end_layout
+
+\begin_layout LyX-Code
+ tree)
+\end_layout
+
+\begin_layout LyX-Code
+ (begin
+\end_layout
+
+\begin_layout LyX-Code
+ (if (not (null? tree))
+\end_layout
+
+\begin_layout LyX-Code
+ (warn "Replacing top-level handler:" tree handler))
+\end_layout
+
+\begin_layout LyX-Code
+ handler)))))
+\end_layout
+
+\begin_layout LyX-Code
\end_layout
@@ -781,38 +1066,892 @@ discovery.scm
\end_layout
\begin_layout LyX-Code
-//Dima Turbiner
+; discovery.scm
\end_layout
\begin_layout LyX-Code
-module zbt_to_ifft(input clk, reset, input [9:0]hcount, input [8:0]vcount,
-
+; author: bnewbold @ mit (with lch @ mit)
+\end_layout
+
+\begin_layout LyX-Code
+; for 6.945
+\end_layout
+
+\begin_layout LyX-Code
+; circa 04/2009
+\end_layout
+
+\begin_layout LyX-Code
+
+\end_layout
+
+\begin_layout LyX-Code
+; For speed?
+\end_layout
+
+\begin_layout LyX-Code
+;(declare (usual-integrations))
+\end_layout
+
+\begin_layout LyX-Code
+
+\end_layout
+
+\begin_layout LyX-Code
+; If it isn't already....
+\end_layout
+
+\begin_layout LyX-Code
+;(load "ghelper")
+\end_layout
+
+\begin_layout LyX-Code
+
+\end_layout
+
+\begin_layout LyX-Code
+; takes two lists: the first is a set of predicates and the second a set
+\end_layout
+
+\begin_layout LyX-Code
+; of arguments; if any of the predicates are #t for the args, win, else
+ fail
+\end_layout
+
+\begin_layout LyX-Code
+(define (for-any? preds args)
+\end_layout
+
+\begin_layout LyX-Code
+ (cond ((null? preds) #f)
+\end_layout
+
+\begin_layout LyX-Code
+ ((null? (car preds)) #f)
+\end_layout
+
+\begin_layout LyX-Code
+ ((apply (car preds) args) #t)
+\end_layout
+
+\begin_layout LyX-Code
+ (else (for-any? (cdr preds) args))))
+\end_layout
+
+\begin_layout LyX-Code
+
+\end_layout
+
+\begin_layout LyX-Code
+; Test
+\end_layout
+
+\begin_layout LyX-Code
+(for-any? (list list? null? vector?) '(5))
+\end_layout
+
+\begin_layout LyX-Code
+; #f
+\end_layout
+
+\begin_layout LyX-Code
+(for-any? (list list? null? vector?) '('(1 2 3)))
+\end_layout
+
+\begin_layout LyX-Code
+; #t
+\end_layout
+
+\begin_layout LyX-Code
+
+\end_layout
+
+\begin_layout LyX-Code
+; finds all the operators which can be applied to the args; returns a list
+\end_layout
+
+\begin_layout LyX-Code
+; of operators (not the actual procedures; will include duplicate symbols
+ and
+\end_layout
+
+\begin_layout LyX-Code
+; operator stubs for named operators)
+\end_layout
+
+\begin_layout LyX-Code
+(define (discover:opers-for .
+ args)
+\end_layout
+
+\begin_layout LyX-Code
+ (let* ((arity (length args))
+\end_layout
+
+\begin_layout LyX-Code
+ (opers (hash-table->alist *generic-operator-table*))
+\end_layout
+
+\begin_layout LyX-Code
+ (check
+\end_layout
+
+\begin_layout LyX-Code
+ (lambda (op)
+\end_layout
+
+\begin_layout LyX-Code
+ (if (not (eq? arity (cadr op)))
+\end_layout
+
+\begin_layout LyX-Code
+ #f
+\end_layout
+
+\begin_layout LyX-Code
+ (let per-arg ((tree (operator-record-tree (cdr op)))
+\end_layout
+
+\begin_layout LyX-Code
+ (args args)
+\end_layout
+
+\begin_layout LyX-Code
+ (fail (lambda () #f)))
+\end_layout
+
+\begin_layout LyX-Code
+ (let per-pred ((tree tree) (fail fail))
+\end_layout
+
+\begin_layout LyX-Code
+ (cond ((pair? tree)
+\end_layout
+
+\begin_layout LyX-Code
+ (if ((caar tree) (car args))
+\end_layout
+
+\begin_layout LyX-Code
+ (if (pair? (cdr args))
+\end_layout
+
+\begin_layout LyX-Code
+ (per-arg (cdar tree)
+\end_layout
+
+\begin_layout LyX-Code
+ (cdr args)
+\end_layout
+
+\begin_layout LyX-Code
+ (lambda ()
+\end_layout
+
+\begin_layout LyX-Code
+ (per-pred (cdr tree) fail)))
+\end_layout
+
+\begin_layout LyX-Code
+ #t)
+\end_layout
+
+\begin_layout LyX-Code
+ (per-pred (cdr tree) fail)))
+\end_layout
+
+\begin_layout LyX-Code
+ ((null? tree) (fail))
+\end_layout
+
+\begin_layout LyX-Code
+ (else #t))))))))
+\end_layout
+
+\begin_layout LyX-Code
+ (map car (filter check opers))))
+\end_layout
+
+\begin_layout LyX-Code
+
+\end_layout
+
+\begin_layout LyX-Code
+; same as the above but only grabs the symboled ones
+\end_layout
+
+\begin_layout LyX-Code
+(define (discover:named-opers-for .
+ args)
+\end_layout
+
+\begin_layout LyX-Code
+ (filter symbol? (apply discover:opers-for args)))
+\end_layout
+
+\begin_layout LyX-Code
+
+\end_layout
+
+\begin_layout LyX-Code
+; returns a list of
+\end_layout
+
+\begin_layout LyX-Code
+(define (discover:named-opers)
+\end_layout
+
+\begin_layout LyX-Code
+ (let ((check (lambda (x) (cond ((null? x) '())
+\end_layout
+
+\begin_layout LyX-Code
+ ((symbol? x) x)
+\end_layout
+
+\begin_layout LyX-Code
+ (else '())))))
+\end_layout
+
+\begin_layout LyX-Code
+ (filter (lambda (x) (not (null? x)))
+\end_layout
+
+\begin_layout LyX-Code
+ (map check (hash-table-keys *generic-operator-table*)))))
+\end_layout
+
+\begin_layout LyX-Code
+
+\end_layout
+
+\begin_layout LyX-Code
+; this is just what operators do
+\end_layout
+
+\begin_layout LyX-Code
+(define (discover:apply-name name .
+ args)
+\end_layout
+
+\begin_layout LyX-Code
+ (let ((record (hash-table/get *generic-operator-table* name #f)))
+\end_layout
+
+\begin_layout LyX-Code
+ (let ((succeed
+\end_layout
+
+\begin_layout LyX-Code
+ (lambda (handler)
+\end_layout
+
+\begin_layout LyX-Code
+ (apply handler args))))
+\end_layout
+
+\begin_layout LyX-Code
+ (let per-arg
+\end_layout
+
+\begin_layout LyX-Code
+ ((tree (operator-record-tree record))
+\end_layout
+
+\begin_layout LyX-Code
+ (args args)
+\end_layout
+
+\begin_layout LyX-Code
+ (fail
+\end_layout
+
+\begin_layout LyX-Code
+ (lambda ()
+\end_layout
+
+\begin_layout LyX-Code
+ (error:no-applicable-methods operator args))))
+\end_layout
+
+\begin_layout LyX-Code
+ (let per-pred ((tree tree) (fail fail))
+\end_layout
+
+\begin_layout LyX-Code
+ (cond ((pair? tree)
+\end_layout
+
+\begin_layout LyX-Code
+ (if ((caar tree) (car args))
+\end_layout
+
+\begin_layout LyX-Code
+ (if (pair? (cdr args))
+\end_layout
+
+\begin_layout LyX-Code
+ (per-arg (cdar tree)
+\end_layout
+
+\begin_layout LyX-Code
+ (cdr args)
+\end_layout
+
+\begin_layout LyX-Code
+ (lambda ()
+\end_layout
+
+\begin_layout LyX-Code
+ (per-pred (cdr tree) fail)))
+\end_layout
+
+\begin_layout LyX-Code
+ (succeed (cdar tree)))
+\end_layout
+
+\begin_layout LyX-Code
+ (per-pred (cdr tree) fail)))
+\end_layout
+
+\begin_layout LyX-Code
+ ((null? tree)
+\end_layout
+
+\begin_layout LyX-Code
+ (fail))
+\end_layout
+
+\begin_layout LyX-Code
+ (else
+\end_layout
+
+\begin_layout LyX-Code
+ (succeed tree))))))))
+\end_layout
+
+\begin_layout LyX-Code
+(define (discover:thunklist-for .
+ args)
+\end_layout
+
+\begin_layout LyX-Code
+ (let ((names (apply discover:named-opers-for args)))
+\end_layout
+
+\begin_layout LyX-Code
+ (cons args
+\end_layout
+
+\begin_layout LyX-Code
+ (map (lambda (x)
+\end_layout
+
+\begin_layout LyX-Code
+ (list x
+\end_layout
+
+\begin_layout LyX-Code
+ (lambda ()
+\end_layout
+
+\begin_layout LyX-Code
+ (apply discover:apply-name (cons x args)))))
+\end_layout
+
+\begin_layout LyX-Code
+ names))))
+\end_layout
+
+\begin_layout LyX-Code
+(define (discover:apply-all .
+ args)
+\end_layout
+
+\begin_layout LyX-Code
+ (let ((names (apply discover:named-opers-for args)))
+\end_layout
+
+\begin_layout LyX-Code
+ (map (lambda (x)
+\end_layout
+
+\begin_layout LyX-Code
+ (apply discover:apply-name (cons x args)))
+\end_layout
+
+\begin_layout LyX-Code
+ names)))
+\end_layout
+
+\begin_layout LyX-Code
+(define (discover:apply-all-name .
+ args)
+\end_layout
+
+\begin_layout LyX-Code
+ (let ((names (apply discover:named-opers-for args)))
+\end_layout
+
+\begin_layout LyX-Code
+ (map (lambda (x)
+\end_layout
+
+\begin_layout LyX-Code
+ (list (apply discover:apply-name (cons x args)) x))
+\end_layout
+
+\begin_layout LyX-Code
+ names)))
+\end_layout
+
+\begin_layout LyX-Code
+(define (discover:satisfy pred? .
+ args)
+\end_layout
+
+\begin_layout LyX-Code
+ (let try ((objs (list args)))
+\end_layout
+
+\begin_layout LyX-Code
+ (let ((goodies (filter (lambda (x) (apply pred? x)) objs)))
+\end_layout
+
+\begin_layout LyX-Code
+ (if (not (null? goodies))
+\end_layout
+
+\begin_layout LyX-Code
+ (car goodies)
+\end_layout
+
+\begin_layout LyX-Code
+ (try (fold-right append
+\end_layout
+
+\begin_layout LyX-Code
+ '()
+\end_layout
+
+\begin_layout LyX-Code
+ (map (lambda (x)
+\end_layout
+
+\begin_layout LyX-Code
+ (map list
+\end_layout
+
+\begin_layout LyX-Code
+ (apply discover:apply-all x)))
+\end_layout
+
+\begin_layout LyX-Code
+ objs)))))))
+\end_layout
+
+\begin_layout LyX-Code
+(define (discover:satisfy-sequence pred? .
+ args)
+\end_layout
+
+\begin_layout LyX-Code
+ (let try ((objs (list (list args))))
+\end_layout
+
+\begin_layout LyX-Code
+ (let ((goodies (filter (lambda (x) (apply pred? (car x))) objs)))
+\end_layout
+
+\begin_layout LyX-Code
+ (if (not (null? goodies))
+\end_layout
+
+\begin_layout LyX-Code
+ goodies
+\end_layout
+
+\begin_layout LyX-Code
+ (try (fold-right append
+\end_layout
+
+\begin_layout LyX-Code
+ '()
+\end_layout
+
+\begin_layout LyX-Code
+ (map (lambda (x)
+\end_layout
+
+\begin_layout LyX-Code
+ (map (lambda (y)
+\end_layout
+
+\begin_layout LyX-Code
+ (cons (list (car y)) (cons (cadr
+ y)
+\end_layout
+
+\begin_layout LyX-Code
+ (cdr
+ x))))
+\end_layout
+
+\begin_layout LyX-Code
+ (apply discover:apply-all-name (car
+ x))))
+\end_layout
+
+\begin_layout LyX-Code
+ objs)))))))
+\end_layout
+
+\begin_layout LyX-Code
+
+\end_layout
+
+\begin_layout LyX-Code
+; see discovery-examples.scm for testing and examples
+\end_layout
+
+\begin_layout Subsection
+discovery-examples.scm
+\end_layout
+
+\begin_layout LyX-Code
+(load "ghelper")
+\end_layout
+
+\begin_layout LyX-Code
+(load "discovery")
+\end_layout
+
+\begin_layout LyX-Code
+(define inverse
+\end_layout
+
+\begin_layout LyX-Code
+ (make-generic-operator 1 #f 'inverse))
+\end_layout
+
+\begin_layout LyX-Code
+(define plus
+\end_layout
+
+\begin_layout LyX-Code
+ (make-generic-operator 2 #f 'plus))
+\end_layout
+
+\begin_layout LyX-Code
+(define minus
+\end_layout
+
+\begin_layout LyX-Code
+ (make-generic-operator 2 #f 'minus))
+\end_layout
+
+\begin_layout LyX-Code
+
+\end_layout
+
+\begin_layout LyX-Code
+(assign-operation inverse
+\end_layout
+
+\begin_layout LyX-Code
+ (lambda (x) (/ 1 x))
+\end_layout
+
+\begin_layout LyX-Code
+ (lambda (x) (and (number? x)
+\end_layout
+
+\begin_layout LyX-Code
+ (not (integer? x)))))
+\end_layout
+
+\begin_layout LyX-Code
+; actually a transpose, but meh
+\end_layout
+
+\begin_layout LyX-Code
+(assign-operation inverse
+\end_layout
+
+\begin_layout LyX-Code
+ (lambda (x) (apply zip x))
+\end_layout
+
+\begin_layout LyX-Code
+ (lambda (x)
+\end_layout
+
+\begin_layout LyX-Code
+ (and (list? x)
+\end_layout
+
+\begin_layout LyX-Code
+ (for-all? x list?))))
+\end_layout
+
+\begin_layout LyX-Code
+(define any? (lambda (x) #t))
+\end_layout
+
+\begin_layout LyX-Code
+(assign-operation minus - any? any?)
+\end_layout
+
+\begin_layout LyX-Code
+(assign-operation plus + any? any?)
+\end_layout
+
+\begin_layout LyX-Code
+(plus 1 2)
+\end_layout
+
+\begin_layout LyX-Code
+; 3
+\end_layout
+
+\begin_layout LyX-Code
+;(minus 3)
+\end_layout
+
+\begin_layout LyX-Code
+; ERROR
+\end_layout
+
+\begin_layout LyX-Code
+(inverse 6.5)
+\end_layout
+
+\begin_layout LyX-Code
+;Value: .15384615384615385
+\end_layout
+
+\begin_layout LyX-Code
+(discover:opers-for 6.5)
+\end_layout
+
+\begin_layout LyX-Code
+;Value 52: (inverse #[compound-procedure 49 operator])
+\end_layout
+
+\begin_layout LyX-Code
+(discover:named-opers-for 6.5)
+\end_layout
+
+\begin_layout LyX-Code
+;Value 53: (inverse)
+\end_layout
+
+\begin_layout LyX-Code
+(discover:named-opers-for 1 2)
+\end_layout
+
+\begin_layout LyX-Code
+;Value 54: (plus minus)
+\end_layout
+
+\begin_layout LyX-Code
+(environment-lookup (the-environment) 'inverse)
+\end_layout
+
+\begin_layout LyX-Code
+;Value 49: #[compound-procedure 49 operator]
+\end_layout
+
+\begin_layout LyX-Code
+(hash-table/get *generic-operator-table* inverse #f)
+\end_layout
+
+\begin_layout LyX-Code
+;Value 59: (1 (#[compound-procedure 57] .
+ #[compound-procedure 60]) (#[compound-procedure 61] .
+ #[compound-procedure 62]))
+\end_layout
+
+\begin_layout LyX-Code
+(hash-table/get *generic-operator-table* minus #f)
+\end_layout
+
+\begin_layout LyX-Code
+;Value 63: (2 (#[compound-procedure 56 any?] (#[compound-procedure 56 any?]
+ .
+ #[arity-dispatched-procedure 28])))
+\end_layout
+
+\begin_layout LyX-Code
+(hash-table-size *generic-operator-table*)
+\end_layout
+
+\begin_layout LyX-Code
+;Value: 6 ; for this file
+\end_layout
+
+\begin_layout LyX-Code
+;Value: 92 ; for scmutils
+\end_layout
+
+\begin_layout LyX-Code
+;this prints all keys line by line
+\end_layout
+
+\begin_layout LyX-Code
+(for-each
+\end_layout
+
+\begin_layout LyX-Code
+ (lambda (x) (newline)
+\end_layout
+
+\begin_layout LyX-Code
+ (display x))
+\end_layout
+
+\begin_layout LyX-Code
+ (hash-table/key-list *generic-operator-table*))
+\end_layout
+
+\begin_layout LyX-Code
+(define add1 (make-generic-operator 1 #f 'add1))
+\end_layout
+
+\begin_layout LyX-Code
+(define sub1 (make-generic-operator 1 #f 'sub1))
+\end_layout
+
+\begin_layout LyX-Code
+(define double (make-generic-operator 1 #f 'double))
+\end_layout
+
+\begin_layout LyX-Code
+(define square (make-generic-operator 1 #f 'square))
+\end_layout
+
+\begin_layout LyX-Code
+(define inverse (make-generic-operator 1 #f 'inverse))
+\end_layout
+
+\begin_layout LyX-Code
+(defhandler add1 (lambda (x) (+ x 1)) number?)
+\end_layout
+
+\begin_layout LyX-Code
+(defhandler sub1 (lambda (x) (- x 1)) number?)
+\end_layout
+
+\begin_layout LyX-Code
+(defhandler double (lambda (x) (* 2 x)) number?)
+\end_layout
+
+\begin_layout LyX-Code
+(defhandler square (lambda (x) (* x x)) number?)
+\end_layout
+
+\begin_layout LyX-Code
+(defhandler inverse (lambda (x) (/ 1 x)) (lambda (n)
+\end_layout
+
+\begin_layout LyX-Code
+ (and (number? n)
+\end_layout
+
+\begin_layout LyX-Code
+ (not (zero? n)))))
+\end_layout
+
+\begin_layout LyX-Code
+(discover:apply-all 3)
+\end_layout
+
+\begin_layout LyX-Code
+;Value 89: (1/3 4 9 2 6)
+\end_layout
+
+\begin_layout LyX-Code
+(discover:satisfy (lambda (x) (eq? x 9)) (/ 1 2))
+\end_layout
+
+\begin_layout LyX-Code
+;Value 35: (9)
+\end_layout
+
+\begin_layout LyX-Code
+(discover:satisfy-sequence (lambda (x) (eq? x 9)) (/ 1 2))
+\end_layout
+
+\begin_layout LyX-Code
+;Value 36: (((9) square double add1) ((9) square add1 inverse))
+\end_layout
+
+\begin_layout LyX-Code
+(discover:satisfy-sequence (lambda (x) (eq? x 49)) (/ 5 6))
+\end_layout
+
+\begin_layout LyX-Code
+;Value 37: (((49) square sub1 inverse sub1))
+\end_layout
+
+\begin_layout LyX-Code
+(define (prime? n)
+\end_layout
+
+\begin_layout LyX-Code
+ (cond ((null? n) #f)
+\end_layout
+
+\begin_layout LyX-Code
+ ((not (integer? n)) #f)
+\end_layout
+
+\begin_layout LyX-Code
+ ((> 0 n) #f)
+\end_layout
+
+\begin_layout LyX-Code
+ (else (let lp ((m 2))
+\end_layout
+
+\begin_layout LyX-Code
+ (cond ((> m (sqrt n)) #t)
+\end_layout
+
+\begin_layout LyX-Code
+ ((integer? (/ n m)) #f)
+\end_layout
+
+\begin_layout LyX-Code
+ (else (lp (+ m 1))))))))
+\end_layout
+
+\begin_layout LyX-Code
+(prime? 47)
\end_layout
\begin_layout LyX-Code
- input [35:0]data_main, input
- [35:0]data_overlay,
+; #t
\end_layout
\begin_layout LyX-Code
- output reg [7:0]main_pixel,
- output reg [7:0]overlay_pixel, output [18:0]addr);
+(discover:satisfy-sequence prime? (/ 5 6))
\end_layout
\begin_layout LyX-Code
- //**** CHECK THIS ADDRESSING
+;Value 39: (((5) inverse sub1 inverse))
\end_layout
\begin_layout LyX-Code
- assign addr = {2'b0, vcount, hcount[9:2]};
+(discover:satisfy-sequence prime? 923)
\end_layout
\begin_layout LyX-Code
-
+;Value 44: (((1847) add1 double))
\end_layout
\begin_layout LyX-Code
- wire [1:0] hc4 = hcount[1:0];
+(discover:named-opers)
\end_layout
\begin_layout LyX-Code
diff --git a/final_project/paper/outline b/final_project/paper/outline
index 84443d2..ca04e74 100644
--- a/final_project/paper/outline
+++ b/final_project/paper/outline
@@ -4,8 +4,8 @@ Title: Generic Operator Discovery
Abstract: Predicate dispatch for generic operators [blah blah]
-Generic Discovery System
-------------------------
+Generic Operator Discovery System
+---------------------------------
Conceptual Description
- review of predicate dispatch
@@ -13,27 +13,22 @@ Generic Discovery System
Implementation
- list of procedures
+ - areas for improvement
Applications
- examples from mechanics
- examples of searching
- Areas for improvement
-GTK and Foreign Function Interface
-----------------------------------
-
- Description of FFI
- - cite what's his name
- - how it works (briefly?)
-
- GTK Bindings
- - brief
-
- Description of Object Discovery Implementation
- - procedures?
+ GUI Interface
+ - description of FFI (cite what's his name)
+ - how it works
+ - gtk bindings
+ - procedures? description of our interface
- screenshots!
+
+
Code Appendix
-------------
discovery.scm