index.scm0000644000175000017500000000517210756615637012200 0ustar athenaathena(load "support/genhtml.scm") (load "support/athena-defs.scm") (define page-contents ($SEQUENTIALLY (H1 (TEXT "Matteo Frigo's Home Page")) (section "Software") (UL (LI (TEXT (simple-link cilk-web-page "Cilk") " is a multithreaded parallel language with a provably good " "scheduler.")) (LI (TEXT (simple-link fftw-web-page "FFTW") " (Fastest Fourier Transform in the West) is a library that " "computes Fourier transforms in a nonstandard manner.")) (LI (TEXT (simple-link gmeteor-web-page "gmeteor") " is a flexible program for FIR filter design.")) ) (section "Papers") (TEXT "See " (simple-link "papers.html" "this web page") ".") (section "Quick hacks") (UL (LI (TEXT (simple-link "hacks/source.tar" "Source code for this web page") " (in Scheme).")) (LI (TEXT (simple-link "hacks/pipe.scm" "Functional pipelines in Scheme") ". (I learned the trick from Olin Shivers.) " "See also the " (simple-link "hacks/pipe.ml" "OCaml version") ".")) (LI (TEXT (simple-link "hacks/schinken.tar" "Schinken") " is a personal-finance system written in Scheme. " "Basic idea: the evaluation of" (P (CODE (TEXT "((may 1 2002) (USD 100.00) \"payment\" checking credit-card)"))) " does the right thing.")) (LI (TEXT "Unpublished memo: " (simple-link "hacks/density-product-real-gaussians.dvi" "Density of the product of two real Gaussian random variables") ". This result is mentioned in the paper " (EM (TEXT "On the Frequency Function of$xy$,")) " by Cecil C. Craig, Ann. Math. Statist. Volume 7, " "Number 1 (1936), 1-15, where it is said to be well-known''" " and attributed to a 1932 paper by J. Wishart and M. S. Bartlett.")) (LI (TEXT "Unpublished memo: " (simple-link "hacks/density-product-complex-gaussians.dvi" "Density of the product of two complex Gaussian random variables") ". This result must be known, but I am not aware of any reference.")) (LI (TEXT "Unpublished memo: " (simple-link "hacks/ternary.dvi" "Radix-3 computation of twiddle factors") ".")) (LI (TEXT (simple-link "hacks/nvsetvol.c" "nvsetvol.c") " is a simple program that sets the volume of the Power Macintosh " "startup chime from linux. Setting the volume to 0 disables " "the startup sound altogether.")) ) (section "Public key") (TEXT (simple-link "pubkey.asc" "Here ") " is my GPG public key.") )) (define page (athena-page "Matteo Frigo's Home Page" "./" page-contents)) (print-html page)papers.scm0000644000175000017500000006366211217427303012353 0ustar athenaathena(load "support/genhtml.scm") (load "support/athena-defs.scm") (define (phd-thesis when) (TEXT "Ph. D. Thesis, MIT Department of Electrical Engineering and Computer Science." (BR) when ".")) (define (masters-thesis when) (TEXT "Master's Thesis, MIT Department of Electrical Engineering and Computer Science." (BR) when ".")) (define (by authors) (case (length authors) ((1) (car authors)) ((2) (TEXT (car authors) " and " (cadr authors))) (else (let ((butlast (reverse (cdr (reverse authors)))) (last-guy (car (reverse authors)))) (TEXT (apply$SEQUENTIALLY (map (lambda (guy) (TEXT guy ", ")) butlast)) " and " (TEXT last-guy)))))) (define some-html (lambda (url remarks) ($SEQUENTIALLY (if (not (null? remarks)) ($SEQUENTIALLY (apply $SEQUENTIALLY (map TEXT remarks)) (BR)) NIL) (if url (simple-link url "[Full text]") NIL)))) (define abstract-link (lambda (title authors abstract abstract-text url remarks) (with-output-to-file (string-append "abstracts/" abstract ".html") (lambda () (print-html (athena-page "Abstract" "../../" ($SEQUENTIALLY (A:NAME "afterheading" (TEXT "")) (HR) (CENTER (H3 (TEXT title))) (CENTER (TEXT "by " (by authors) ".")) (P (CENTER (some-html url remarks))) (HR) (P (CENTER (H3 (TEXT "Abstract")))) abstract-text))))) ($SEQUENTIALLY (TEXT " ") (simple-link (string-append "abstracts/" abstract ".html#afterheading") "Abstract") (BR)))) (define paper (let ((count 0)) (lambda (title authors abstract-text url . remarks) (set! count (+ count 1)) (let ((abstract (string-append "abstract" (number->string count)))) (LI ($SEQUENTIALLY (STRONG (TEXT title)) (BR) (TEXT "by " (by authors) ".") (BR) (some-html url remarks) (if abstract-text (abstract-link title authors abstract abstract-text url remarks) NIL) (P NIL) )))))) (define papers-list (UL (paper "Reducers and Other Cilk++ Hyperobjects" (list Matteo-Frigo "Pablo Halpern" cel "Stephen Lewin-Berlin") (P (TEXT "This paper introduces hyperobjects, a linguistic mechanism that allows different branches of a multithreaded program to maintain coordinated local views of the same nonlocal variable. We have identified three kinds of hyperobjects that seem to be useful --- reducers, holders, and splitters --- and we have implemented reducers and holders in Cilk++, a set of extensions to the C++ programming language that enables multicore programming in the style of MIT Cilk. We analyze a randomized locking methodology for reducers and show that a work-stealing scheduler can support reducers without incurring significant overhead.")) (on-paperdir "hyper.pdf") (CITE (TEXT "To appear in SPAA 2009.")) (BR) (TEXT " SPAA 2009 Best Paper Award.")) (paper "Parallel Sparse Matrix-Vector and Matrix-Transpose-Vector Multiplication Using Compressed Sparse Blocks" (list Aydin-Buluc Jeremy-Fineman Matteo-Frigo John-Gilbert cel) #f (on-paperdir "csb.pdf") (CITE (TEXT "To appear in SPAA 2009."))) (paper "The Cache Complexity of Multithreaded Cache Oblivious Algorithms" (list Matteo-Frigo Volker-Strumpen) (P (TEXT "We present a technique for analyzing the number of cache misses incurred by multithreaded cache oblivious algorithms on an idealized parallel machine in which each processor has a private cache. We specialize this technique to computations executed by the Cilk work-stealing scheduler on a machine with dag-consistent shared memory. We show that a multithreaded cache oblivious matrix multiplication incurs $O(n^3/\\sqrt{Z} + (P n)^{1/3} n^2)$ cache misses when executed by the Cilk scheduler on a machine with~$P$ processors, each with a cache of size~$Z$, with high probability. This bound is tighter than previously published bounds. We also present a new multithreaded cache oblivious algorithm for 1D stencil computations incurring $O(n^2/Z + n + \\sqrt{P n^{3+\\epsilon}})$ cache misses with high probability, one for Gaussian elimination and back substitution, and one for the length computation part of the longest common subsequence problem incurring $O(n^2/Z + \\sqrt{P n^{3.58}})$ cache misses with high probability.")) (on-paperdir "tocs08.pdf") (CITE (TEXT "To appear in Theory of Computing Systems.")) (BR) (TEXT " An earlier version of this paper appears in the Proceedings of the 18th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'06).")) (paper "A modified split-radix FFT with fewer arithmetic operations" (list Steven-Johnson Matteo-Frigo) (P (TEXT "Recent results by Van Buskirk et al. have broken the record set by Yavne in 1968 for the lowest exact count of real additions and multiplications to compute a power-of-two discrete Fourier transform (DFT). Here, we present a simple recursive modification of the split-radix algorithm that computes the DFT with asymptotically about 6% fewer operations than Yavne, matching the count achieved by Van Buskirk's program generation framework. We also discuss the application of our algorithm to real-data and real-symmetric (discrete cosine) transforms, where we are again able to achieve lower arithmetic counts than previously published algorithms.")) (on-paperdir "newsplit-pub.pdf") (CITE (TEXT "IEEE Transactions on Signal Processing, volume 55, number 1, Jan 2007, pages 111-119"))) (paper "Software Engineering Aspects of Cache Oblivious Stencil Computations" (list Volker-Strumpen Matteo-Frigo) (P (TEXT "We discuss the design of cache oblivious stencil computations for finite-difference methods in 1-dimensional space and time. We employ our cache oblivious spacetime traversal [ICS'05] to obtain several fully cache oblivious algorithms. We focus on the practical aspects of the software engineering chores that today's superscalar architectures impose on high performance programming.")) (on-paperdir "rc24035.pdf") (CITE (TEXT "IBM Research Report RC24035 (W0608-077)"))) (paper "Cache Oblivious Stencil Computations" (list Matteo-Frigo Volker-Strumpen) (P (TEXT "We present a cache oblivious algorithm for stencil computations, which arise for example in finite-difference methods. Our algorithm applies to arbitrary stencils in $n$-dimensional spaces. On an ideal cache'' of size $Z$, our algorithm saves a factor of $\Theta(Z^{1/n})$ cache misses compared to a naive algorithm, and it exploits temporal locality optimally throughout the entire memory hierarchy.")) (on-paperdir "ics05.pdf") (CITE (TEXT "Proceedings of the 19th ACM International Conference on Supercomputing (ICS05)."))) (paper "The Design and Implementation of FFTW3" (list Matteo-Frigo Steven-Johnson) (P (TEXT "FFTW is an implementation of the discrete Fourier transform (DFT) that adapts to the hardware in order to maximize performance. This paper shows that such an approach can yield an implementation that is competitive with hand-optimized libraries, and describes the software structure that makes our current FFTW3 version flexible and adaptive. We further discuss a new algorithm for real-data DFTs of prime size, a new way of implementing DFTs by means of machine-specific SIMD'' instructions, and how a special-purpose compiler can derive optimized implementations of the discrete cosine and sine transforms automatically from a DFT algorithm.")) (on-paperdir "fftw-paper-ieee.ps.gz") (CITE (TEXT "Proceedings of the IEEE, vol. 93, no. 2, pp. 216--231 (2005)"))) (paper "A Noise-Adaptive Strategy for First-Order Reed-Muller Decoding" (list Jon-Feldman Ibrahim-Abou-Faycal Matteo-Frigo) (P (TEXT "We consider the problem of decoding First-Order Reed-Muller codes efficiently. We give an algorithm that implicitly adapts to the noise conditions, runs significantly faster than known maximum-likelihood algorithms, and yields an error rate that is very close to optimal. When applied to CCK demodulation (used in the 802.11b standard for Wireless Local Area Networks), the algorithm runs up to 4 times faster than a decoder based on the Fast Hadamard Transform, with a loss of at most 0.2dB in error rate. We show analytically that the error rate of our adaptive algorithm is 2^-\Omega(n), where n is the length of a codeword.")) (on-paperdir "reed-muller.ps.gz") (CITE (TEXT "IEEE Semiannual Vehicular Technology Conference, Fall 2002"))) (paper "A Fast Maximum-Likelihood Decoder for Convolutional Codes" (list Jon-Feldman Ibrahim-Abou-Faycal Matteo-Frigo) (P (TEXT "The " (STRONG (TEXT "lazy Viterbi decoder")) " is a maximum-likelihood decoder for block and stream convolutional codes. For many codes of practical interest, under reasonable noise conditions, the lazy decoder is much faster than the original Viterbi decoder. For a code of constraint length 6, the lazy algorithm is about 50% faster than an optimized implementation of the Viterbi decoder whenever SNR > 6dB. Moreover, while the running time of the Viterbi decoder grows exponentially with the constraint length, under reasonable noise conditions, the running time of the lazy algorithm is essentially independent of the constraint length. This paper introduces the lazy Viterbi decoder and shows how to make it efficient in practice.")) (on-paperdir "viterbi.ps.gz") (CITE (TEXT "IEEE Semiannual Vehicular Technology Conference, Fall 2002"))) (paper "Portable High-Performance Programs" (list Matteo-Frigo) ($SEQUENTIALLY (P (TEXT "This dissertation discusses how to write computer programs that attain both high performance and portability, despite the fact that current computer systems have different degrees of parallelism, deep memory hierarchies, and diverse processor architectures.")) (P (TEXT "To cope with parallelism portably in high-performance programs, we present the" (STRONG (TEXT " Cilk ")) "multithreaded programming system. In the Cilk-5 system, parallel programs scale up to run efficiently on multiple processors, but unlike existing parallel-programming environments, such as MPI and HPF, Cilk programs scale down'' to run on one processor as efficiently as a comparable C program. The typical cost of spawning a parallel thread in Cilk-5 is only between 2 and 6 times the cost of a C function call. This efficient implementation was guided by the" (STRONG (TEXT " work-first principle ")) ", which dictates that scheduling overheads should be borne by the critical path of the computation and not by the work. We show how the work-first principle inspired Cilk's novel two-clone'' compilation strategy and its Dijkstra-like mutual-exclusion protocol for implementing the ready deque in the work-stealing scheduler.")) (P (TEXT "To cope portably with the memory hierarchy, we present asymptotically optimal algorithms for rectangular matrix transpose, FFT, and sorting on computers with multiple levels of caching. Unlike previous optimal algorithms, these algorithms are" (STRONG (TEXT " cache oblivious")) ": no variables dependent on hardware parameters, such as cache size and cache-line length, need to be tuned to achieve optimality. Nevertheless, these algorithms use an optimal amount of work and move data optimally among multiple levels of cache. For a cache with size$Z$and cache-line length$L$where$Z=\\Omega(L" (SUP (TEXT "2")) ")$the number of cache misses for an$m\\times n$matrix transpose is$\\Theta(1+mn/L)$. The number of cache misses for either an$n$-point FFT or the sorting of$n$numbers is$\\Theta(1+(n/L)(1+\\log_Z n))$. We also give a$\\Theta(mnp)$-work algorithm to multiply an$m\\times n$matrix by an$n\\times p$matrix that incurs$\\Theta(1 + (mn+np+mp)/L + mnp/L\\sqrt{Z})$cache faults.")) (P (TEXT "To attain portability in the face of both parallelism and the memory hierarchy at the same time, we examine the" (STRONG (TEXT " location consistency ")) "memory model and the" (STRONG (TEXT " Backer ")) "coherence algorithm for maintaining it. We prove good asymptotic bounds on the execution time of Cilk programs that use location-consistent shared memory.")) (P (TEXT "To cope with the diversity of processor architectures, we develop the FFTW self-optimizing program, a portable C library that computes Fourier transforms. FFTW is unique in that it can automatically tune itself to the underlying hardware in order to achieve high performance. Through extensive benchmarking, FFTW has been shown to be typically faster than all other publicly available FFT software, including codes such as Sun's Performance Library and IBM's ESSL that are tuned to a specific machine. Most of the performance-critical code of FFTW was generated automatically by a special-purpose compiler written in Objective Caml, which uses symbolic evaluation and other compiler techniques to produce codelets''---optimized sequences of C code that can be assembled into plans'' to compute a Fourier transform. At runtime, FFTW measures the execution time of many plans and uses dynamic programming to select the fastest. Finally, the plan drives a special interpreter that computes the actual transforms."))) (on-paperdir "frigo-phd-thesis.ps.gz") (phd-thesis "June 1999")) (paper "Cache-Oblivious Algorithms" (list Matteo-Frigo cel Harald-Prokop Sridhar-Ramachandran) ($SEQUENTIALLY (P (TEXT "This paper presents asymptotically optimal algorithms for rectangular matrix transpose, FFT, and sorting on computers with multiple levels of caching. Unlike previous optimal algorithms, these algorithms are cache oblivious: no variables dependent on hardware parameters, such as cache size and cache-line length, need to be tuned to achieve optimality. Nevertheless, these algorithms use an optimal amount of work and move data optimally among multiple levels of cache. For a cache with size Z and cache-line length L where Z=\\Omega(L^2) the number of cache misses for an m\\times n matrix transpose is \\Theta(1+mn/L). The number of cache misses for either an n-point FFT or the sorting of n numbers is \\Theta(1+(n/L)(1+\\logZ n)). We also give an \\Theta(mnp)-work algorithm to multiply an m\\times n matrix by an n\\times p matrix that incurs \\Theta(1 + (mn+np+mp)/L + mnp/L\\sqrt{Z}) cache faults.")) (P (TEXT "We introduce an ideal-cache'' model to analyze our algorithms, and we prove that an optimal cache-oblivious algorithm designed for two levels of memory is also optimal for multiple levels. We also prove that any optimal cache-oblivious algorithm is also optimal in the previously studied HMM and SUMH models. Algorithms developed for these earlier models are perforce cache-aware: their behavior varies as a function of hardware-dependent parameters which must be tuned to attain optimality. Our cache-oblivious algorithms achieve the same asymptotic optimality, but without any tuning."))) (on-paperdir "FrigoLePr99.ps.gz") (CITE (TEXT "In the 40th Annual Symposium on Foundations of Computer Science, FOCS '99, 17-18 October, 1999, New York, NY, USA."))) (paper "A Fast Fourier Transform Compiler" (list Matteo-Frigo) ($SEQUENTIALLY (P (TEXT "The FFTW library for computing the discrete Fourier transform (DFT) has gained a wide acceptance in both academia and industry, because it provides excellent performance on a variety of machines (even competitive with or faster than equivalent libraries supplied by vendors). In FFTW, most of the performance-critical code was generated automatically by a special-purpose compiler, called genfft, that outputs C code. Written in Objective Caml, genfft can produce DFT programs for any input length, and it can specialize the DFT program for the common case where the input data are real instead of complex. Unexpectedly, genfft discovered'' algorithms that were previously unknown, and it was able to reduce the arithmetic complexity of some other existing algorithms. This paper describes the internals of this special-purpose compiler in some detail, and it argues that a specialized compiler is a valuable tool."))) (on-paperdir "pldi99.ps.gz") (CITE (TEXT "In the ACM SIGPLAN'99 Conference on Programming " "Language Design and Implementation (PLDI), Atlanta, GA, USA")) (BR) (TEXT "2009 Most Influential PLDI Paper Award (for 1999)")) (paper "Computation-Centric Memory Models" (list Matteo-Frigo "Victor Luchangco") ($SEQUENTIALLY (P (TEXT "We present a computation-centric theory of memory models. Unlike traditional processor-centric models, computation-centric models focus on the logical dependencies among instructions rather than the processor that happens to execute them. This theory allows us to define what a memory model is, and to investigate abstract properties of memory models. In particular, we focus on constructibility, which is a necessary property of those models that can be implemented exactly by an online algorithm. For a nonconstructible model, we show that there is a natural way to define the constructible version of that model. We explore the implications of constructibility in the context of dag-consistent memory models, which do not require that memory locations be serialized. The strongest dag-consistent model, called NN-dag consistency, is not constructible. However, its constructible version is equivalent to a model that we call location consistency, in which each location is serialized independently."))) (on-paperdir "spaa98-memory.ps.gz") (CITE (TEXT "In the 10th ACM Symposium on Parallel Algorithms and Architectures, June 28-July 2, 1998."))) (paper "FFTW: An Adaptive Software Architecture for the FFT" (list Matteo-Frigo Steven-Johnson) (P (TEXT "FFT literature has been mostly concerned with minimizing the number of floating-point operations performed by an algorithm. Unfortunately, on present-day microprocessors this measure is far less important than it used to be, and interactions with the processor pipeline and the memory hierarchy have a larger impact on performance. Consequently, one must know the details of a computer architecture in order to design a fast algorithm. In this paper, we propose an adaptive FFT program that tunes the computation automatically for any particular hardware. We compared our program, called FFTW, with over 40 implementations of the FFT on 7 machines. Our tests show that FFTW's self-optimizing approach usually yields significantly better performance than all other publicly available software. FFTW also compares favorably with machine-specific, vendor-optimized libraries.")) (on-paperdir "fftw-paper-icassp.ps.gz") (CITE (TEXT "In the Proceedings of the 1998 ICASSP conference (vol. 3, pp. 1381-1384)"))) (paper "The Weakest Reasonable Memory Model" (list Matteo-Frigo) ($SEQUENTIALLY (P (TEXT "A memory model is some description of how memory behaves in a parallel computer system. While there is consensus that sequential consistency [Lamport 79] is the strongest memory model, nobody seems to have tried to identify the weakest memory model. This thesis concerns itself with precisely this problem.")) (P (TEXT "We cannot hope to identify the weakest memory model unless we specify a minimal set of properties we want it to obey. In this thesis, we identify five such properties: completeness, monotonicity, constructibility, nondeterminism confinement, and classicality. Constructibility is especially interesting, because a nonconstructible model cannot be implemented exactly, and hence every implementation necessarily supports a stronger model. One nonconstructible model is, for example, dag consistency [Blumofe et al. 96].")) (P (TEXT "We argue (with some caveats) that if one wants the five properties, then location consistency is the weakest reasonable memory model. In location consistency, every memory location is serialized, but different locations may be serialized independently. (Location consistency is sometimes called coherence [Hennessy and Patterson 96], and our location consistency is" (STRONG (TEXT " not ")) " the model with the same name proposed by [Gao and Sarkar 93].)")) (P (TEXT "We obtain these results within a computation-centric theory of memory models, where memory models are defined independently of scheduling issues and language semantics."))) (on-paperdir "frigo-ms-thesis.ps.gz") (masters-thesis "January 1998")) (paper "The Implementation of the Cilk-5 Multithreaded Language" (list Matteo-Frigo cel Keith-Randall) ($SEQUENTIALLY (P (TEXT "The fifth release of the multithreaded language Cilk uses a provably good work-stealing'' scheduling algorithm similar to the first system, but the runtime system has been completely reengineered. The efficiency of the new implementation was aided by a clear strategy that arose from a theoretical analysis of the scheduling algorithm: concentrate on minimizing overheads that contribute to the work, even at the expense of overheads that contribute to the critical path. Although it may seem counterintuitive to move overheads from the work of a computation to its critical path, this work-first'' principle has led to a portable Cilk-5 implementation in which the typical cost of spawning a parallel thread is only between 2 and 6 times the cost of a C function call on a variety of contemporary machines. Many Cilk programs run on one processor with virtually no degradation compared to equivalent C programs. This paper describes how the work-first principle was exploited in the design of Cilk-5's compiler and its runtime system. In particular, we present Cilk-5's novel two-clone'' compilation strategy and its Dijkstra-like mutual-exclusion protocol for implementing the ready deque in the work-stealing scheduler."))) (on-paperdir "cilk5.ps.gz") (CITE (TEXT "1998 ACM SIGPLAN Conference on Programming Language")) (BR) (TEXT "2008 Most Influential PLDI Paper Award (for 1998)")) (paper "The Fastest Fourier Transform in the West" (list Matteo-Frigo Steven-Johnson) #f (on-paperdir "fftw-paper.ps.gz") "Technical Report MIT-LCS-TR-728, September 1997.") (paper "An Analysis of Dag-Consistent Distributed Shared-Memory Algorithms" (list Bobby-Blumofe Matteo-Frigo Chris-Joerg cel Keith-Randall) ($SEQUENTIALLY (P (TEXT "In this paper, we analyze the performance of parallel multithreaded algorithms that use dag-consistent distributed shared memory. Specifically, we analyze execution time, page faults, and space requirements for multithreaded algorithms executed by a work-stealing thread scheduler and the Backer coherence algorithm for maintaining dag consistency. We prove that if the accesses to the backing store are random and independent (the Backer algorithm actually uses hashing), then the expected execution time of a fully strict'' multithreaded computation on " (EM (TEXT " P ")) " processors, each with an LRU cache of " (EM (TEXT " C ")) " pages, is " (EM (TEXT " O(T1(C)/P + m C Tinf) ")) ", where " (EM (TEXT " T1(C) ")) " is the total work of the computation including page faults," (EM (TEXT " Tinf ")) " is its critical-path length excluding page faults, and " (EM (TEXT " m ")) " is the minimum page transfer time. As a corollary to this theorem, we show that the expected number of page faults incurred by a computation executed on " (EM (TEXT " P ")) " processors, each with an LRU cache of " (EM (TEXT " C ")) " pages, is " (EM (TEXT " F1(C) + O(C P Tinf) ")) ", where " (EM (TEXT " F1(C) ")) " is the number of serial page faults. Finally, we give simple bounds on the number of page faults and the space requirements for regular'' divide-and-conquer algorithms. We use these bounds to analyze parallel multithreaded algorithms for matrix multiplication and LU-decomposition."))) (on-paperdir "spaa96.ps.gz") "In " (CITE (TEXT "8th Annual ACM Symposium on Parallel Algorithms and Architectures")) (BR) (simple-link "http://www.cs.jhu.edu/Conferences/SPAA96/" "SPAA'96") ", June 24-26, 1996, Padua, Italy, pp.297-308.") (paper "Dag-Consistent Distributed Shared Memory" (list Bobby-Blumofe Matteo-Frigo Chris-Joerg cel Keith-Randall) ($SEQUENTIALLY (P (TEXT "We introduce dag consistency, a relaxed consistency model for distributed shared memory which is suitable for multithreaded programming. We have implemented dag consistency in software for the Cilk multithreaded runtime system running on a Connection Machine CM5. Our implementation includes a dag-consistent distributed cactus stack for storage allocation. We provide empirical evidence of the flexibility and efficiency of dag consistency for applications that include blocked matrix multiplication, Strassen's matrix multiplication algorithm, and a Barnes-Hut code. Although Cilk schedules the executions of these programs dynamically, their performances are competitive with statically scheduled implementations in the literature. We also prove that the number" (EM (TEXT " FP ")) " of page faults incurred by a user program running on " (EM (TEXT " P ")) " processors can be related to the number " (EM (TEXT " F1 ")) " of page faults running serially by the formula" (EM (TEXT " FP <= F1 + 2Cs ")) ", where " (EM (TEXT " C ")) " is the cache size and " (EM (TEXT " s ")) " is the number of thread migrations executed by Cilk's scheduler."))) (on-paperdir "ipps96.ps.gz") "In " (CITE (TEXT "10th International Parallel Processing Symposium")) " (IPPS '96), April 15-19, 1996, Honolulu, Hawaii, pp. 132-141.") )) (define page-contents ($SEQUENTIALLY (section "Papers (co-)authored by Matteo Frigo") papers-list)) (define page (athena-page "Papers (co-)authored by Matteo Frigo" "./" page-contents)) (print-html page) support/athena-defs.scm0000644000175000017500000001141111217430546014740 0ustar athenaathena(require 'posix-time) (define supertech-web-page "http://supertech.lcs.mit.edu/") (define cilk-web-page (string-append supertech-web-page "cilk/")) (define fftw-web-page "http://fftw.org/") (define gmeteor-web-page "http://gmeteor.sourceforge.net/") (define (on-theory filename) (string-append "ftp://theory.lcs.mit.edu/pub/cilk/" filename)) (define (on-fftw filename) (string-append "ftp://ftp.fftw.org/pub/fftw/" filename)) (define (on-paperdir filename) (string-append "http://www.fftw.org/~athena/papers/" filename)) (define (simple-link link name) (A:HREF link (TEXT name))) (define cilk-maintainer (simple-link "mailto:athena@fftw.org" "Matteo Frigo")) (define (athena-head titl topdir) (define (href name) (list 'HREF (string-append topdir name))) (HEAD ($SEQUENTIALLY (A:NAME "top-of-logo" (TEXT "")) (META '(http-equiv "name") '(content "Matteo Frigo Home Page")) (META '(http-equiv "distribution") '(content "global")) (META '(name "alias") '(content "http://theory.lcs.mit.edu/~athena/")) (TITLE (VERBATIM titl)) (LINK '(rel "BOOKMARK") (list 'title titl) (href "index.html")) (LINK '(rel "Contents") (href "index.html")) (LINK '(rel "STYLESHEET") (href "cilk.css") '(type "text/css"))))) (define horizontal-rule (P (HR '(noshade) '(width "90%") '(size "1")) '(align "center"))) (define (athena-tail topdir) (SEQUENTIALLY horizontal-rule (TEXT "This page maintained by: " cilk-maintainer ". Last updated: " (asctime (localtime (current-time))) ))) (define (athena-body titl topdir contents) (BODY ($SEQUENTIALLY contents (athena-tail topdir)) '(text "#000000") '(bgcolor "#FFFFFF"))) (define (athena-page titl topdir contents) ($SEQUENTIALLY (DOCTYPE) ($NEWLINE) (comment "This file was automatically generated. DO NOT EDIT!") ($NEWLINE) (HTML ($SEQUENTIALLY (athena-head titl topdir) (athena-body titl topdir contents) )))) (define (section name) ($SEQUENTIALLY (H2 (TEXT name)))) (define Matteo-Frigo (simple-link "http://www.fftw.org/~athena" "Matteo Frigo")) (define Harald-Prokop (simple-link "http://supertech.lcs.mit.edu/~prokop" "Harald Prokop")) (define Keith-Randall (simple-link "http://theory.lcs.mit.edu/~randall" "Keith H. Randall")) (define cel (simple-link "http://supertech.lcs.mit.edu/~cel" "Charles E. Leiserson")) (define Sridhar-Ramachandran "Sridhar Ramachandran") (define Andy-Stark (simple-link "http://www-swiss.ai.mit.edu/~astark" "Andrew F. Stark")) (define Steven-Johnson (A:HREF "http://math.mit.edu/~stevenj/" (TEXT "Steven G. Johnson"))) (define Feng-Mingdong (simple-link "http://theory.lcs.mit.edu/~fengmd" "Mingdong Feng")) (define Bin-Song (simple-link "http://theory.lcs.mit.edu/~bsong" "Bin Song")) (define Volker-Strumpen (simple-link "http://strumpen.net/" "Volker Strumpen")) (define Balkrishna-Ramkumar (simple-link "http://www.eng.uiowa.edu/~ramkumar" "Balkrishna Ramkumar")) (define Phil-Lisiecki (simple-link "http://web.mit.edu/lisiecki/www/home.html" "Philip A. Lisiecki")) (define Bobby-Blumofe "Robert D. Blumofe") (define Chris-Joerg "Christopher F. Joerg") (define Bradley-Kuszmaul (simple-link "http://arch.cs.yale.edu:8080/~bradley/" "Bradley C. Kuszmaul")) (define Yuli-Zhou "Yuli Zhou") (define Don-Dailey "Don Dailey") (define Howard-Lu "Howard J. Lu") (define Robert-Miller "Robert C. Miller") (define David-Park "David S. Park") (define Michael-Halbherr "Michael Halbherr") (define Eric-Brewer (simple-link "http://jukebox.lcs.mit.edu:80/~brewer/" "Eric A. Brewer")) (define Supercomputing-Group "Supercomputing Technologies Group") (define Igor-Lyubashevskiy "Igor B. Lyubashevskiy") (define Nathaniel-Kushman "Nathaniel A. Kushman") (define Guang-Ien-Cheng "Guang-Ien Cheng") (define Yaron-Shoham (simple-link "http://www.math.tau.ac.il/~ysh/" "Yaron Shoham")) (define Cilkchess (simple-link "/chess" "Cilkchess")) (define *Socrates (simple-link "/chess" "*Socrates")) (define LCS (simple-link "http://www.lcs.mit.edu/" "Laboratory for Computer Science")) (define Bruce-Maggs (simple-link "http://www.cs.cmu.edu/~bmm/" "Bruce M. Maggs")) (define Aske-Plaat (simple-link "http://www.cs.vu.nl/~aske/" "Aske Plaat")) (define Ibrahim-Abou-Faycal "Ibrahim Abou-Faycal") (define Jon-Feldman (simple-link "http://www.columbia.edu/~jf2189/index.html" "Jon Feldman")) (define Aydin-Buluc (simple-link "http://gauss.cs.ucsb.edu/~aydin/" "Aydin Buluc")) (define Jeremy-Fineman (simple-link "http://people.csail.mit.edu/jfineman/" "Jeremy T. Fineman")) (define John-Gilbert (simple-link "http://www.cs.ucsb.edu/~gilbert/" "John R. Gilbert")) (define (create-abstract text) text) support/genhtml.scm0000644000175000017500000001174010707257156014233 0ustar athenaathena (require 'macro) (define-syntax define-datatype (syntax-rules () ((define-datatype ; is ignored, documentation only ( ...) ...) (begin (%match-define-constructor ...) ...)))) (define-syntax %match-define-constructor (syntax-rules () ((%match-define-constructor ( ) ...) (begin (%match-define-constructor ...) (define (let (( )) (lambda (thing) (thing (lambda _ #t) (lambda () #f))))))) ((%match-define-constructor ...) (define (letrec (( (lambda ( ...) (lambda (token win lose) (if (eq? token ) (win ...) (lose)))))) ))))) (define-syntax match (syntax-rules () ((match ( ) ...) (let ((E )) (%match-aux E ( ) ...))))) (define-syntax %match-aux (syntax-rules (else) ((%match-aux E) (%match-no-match)) ((%match-aux E (else )) ) ((%match-aux E (( ...) ) ...) (let ((fail (lambda () (%match-aux E ...)))) (E (%match-bind ( ...) () fail) fail))))) (define-syntax %match-bind (syntax-rules (_) ((%match-bind (( ...) ...) ( ...) ) (%match-bind ( ...) ( ... temp) (match temp (( ...) ) (else ())) )) ((%match-bind (_ ...) ( ...) ) (%match-bind ( ...) ( ... temp) )) ((%match-bind ( ...) ( ...) ) (%match-bind ( ...) ( ... ) )) ((%match-bind () ( ...) ) (lambda ( ...) )))) (define (%match-no-match) (error "match: no matching pattern")) (define-datatype html ($VERBATIM item) ($STRING item) ($NEWLINE) ($SEQUENTIALLY:l l)) (define ($SEQUENTIALLY . l) ($SEQUENTIALLY:l l)) (define (print-html l) (match l (($VERBATIM item) (display item)) (($STRING item) (begin (display "\"") (display item) (display "\""))) (($NEWLINE) (newline)) (($SEQUENTIALLY:l l) (for-each print-html l)))) (define NIL ($SEQUENTIALLY)) (define (comment what) ($SEQUENTIALLY ($VERBATIM ""))) (define (DTD what) ($SEQUENTIALLY ($VERBATIM ""))) (define (space) ($VERBATIM " ")) (define (DOCTYPE) (DTD "DOCTYPE HTML PUBLIC \"-//W3C//DTD HTML 4.0 Transitional//EN\"")) (define (attributes a) ($SEQUENTIALLY:l (map (lambda (item) ($SEQUENTIALLY ($VERBATIM (symbol->string (car item))) (if (null? (cdr item)) NIL ($SEQUENTIALLY ($VERBATIM "=") ($STRING (cadr item)))) (space))) a))) (define (tag t) (lambda (body . attr) ($SEQUENTIALLY ($SEQUENTIALLY ($VERBATIM "<") ($VERBATIM t) ($VERBATIM " ") (attributes attr) ($VERBATIM ">")) body ($SEQUENTIALLY ($VERBATIM ""))))) (define (unbalanced-tag t) (lambda (body . attr) ($SEQUENTIALLY ($SEQUENTIALLY ($VERBATIM "<") ($VERBATIM t) ($VERBATIM " ") (attributes attr) ($VERBATIM ">")) body))) (define HEAD (tag "HEAD")) (define HTML (tag "HTML")) (define TITLE (tag "TITLE")) (define BODY (tag "BODY")) (define FONT (tag "FONT")) (define TABLE (tag "TABLE")) (define TR:l (tag "TR")) (define (TR . l) (TR:l ($SEQUENTIALLY:l l))) (define TD (tag "TD")) (define DIV (tag "DIV")) (define CENTER (tag "CENTER")) (define STRONG (tag "STRONG")) (define SUP (tag "SUP")) (define CITE (tag "CITE")) (define CODE (tag "CODE")) (define A (tag "A")) (define B (tag "B")) (define P (tag "P")) (define EM (tag "EM")) (define H1 (tag "H1")) (define H2 (tag "H2")) (define H3 (tag "H3")) (define H4 (tag "H4")) (define H5 (tag "H5")) (define H6 (tag "H6")) (define UL:l (tag "UL")) (define (UL . l) (UL:l ($SEQUENTIALLY:l l))) (define LI (unbalanced-tag "LI")) (define PRE:t (tag "PRE")) (define (PRE x) (PRE:t ($VERBATIM x))) ; shortcut for common case (define (A:HREF link body) (A body (list 'href link))) (define (A:NAME link body) (A body (list 'name link))) (define (unbalanced-tag-no-body name) (lambda attr ($SEQUENTIALLY ($VERBATIM "<") ($VERBATIM name) ($VERBATIM " ") (attributes attr) ($VERBATIM ">") ($NEWLINE)))) (define META (unbalanced-tag-no-body "META")) (define LINK (unbalanced-tag-no-body "LINK")) (define IMG (unbalanced-tag-no-body "IMG")) (define HR (unbalanced-tag-no-body "HR")) (define BR (unbalanced-tag-no-body "BR")) ; shortcut for text (define (TEXT . l) ($SEQUENTIALLY:l (map (lambda (thing) (if (string? thing) ($VERBATIM thing) thing)) l))) support/match.scm0000644000175000017500000000563710707257156013701 0ustar athenaathena;;; Copyright (c) 2000 Matteo Frigo ;;; ;;; This program is free software; you can redistribute it and/or modify ;;; it under the terms of the GNU General Public License as published by ;;; the Free Software Foundation; either version 2 of the License, or ;;; (at your option) any later version. ;;; ;;; This program is distributed in the hope that it will be useful, ;;; but WITHOUT ANY WARRANTY; without even the implied warranty of ;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the ;;; GNU General Public License for more details. ;;; ;;; You should have received a copy of the GNU General Public License ;;; along with this program; if not, write to the Free Software ;;; Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA ;;; (require 'macro) (define-syntax define-datatype (syntax-rules () ((define-datatype ; is ignored, documentation only ( ...) ...) (begin (%match-define-constructor ...) ...)))) (define-syntax %match-define-constructor (syntax-rules () ((%match-define-constructor ( ) ...) (begin (%match-define-constructor ...) (define (let (( )) (lambda (thing) (thing (lambda _ #t) (lambda () #f))))))) ((%match-define-constructor ...) (define (letrec (( (lambda ( ...) (lambda (token win lose) (if (eq? token ) (win ...) (lose)))))) ))))) (define-syntax match (syntax-rules () ((match ( ) ...) (let ((E )) (%match-aux E ( ) ...))))) (define-syntax %match-aux (syntax-rules (else) ((%match-aux E) (%match-no-match)) ((%match-aux E (else )) ) ((%match-aux E (( ...) ) ...) (let ((fail (lambda () (%match-aux E ...)))) (E (%match-bind ( ...) () fail) fail))))) (define-syntax %match-bind (syntax-rules (_) ((%match-bind (( ...) ...) ( ...) ) (%match-bind ( ...) ( ... temp) (match temp (( ...) ) (else ())) )) ((%match-bind (_ ...) ( ...) ) (%match-bind ( ...) ( ... temp) )) ((%match-bind ( ...) ( ...) ) (%match-bind ( ...) ( ... ) )) ((%match-bind () ( ...) ) (lambda ( ...) )))) (define (%match-no-match) (error "match: no matching pattern")) ;;; Local Variables: *** ;;; eval: (put 'match 'scheme-indent-function 1) *** ;;; eval: (put '%letrec 'scheme-indent-function 2) *** ;;; eval: (put '%lambda 'scheme-indent-function 2) *** ;;; End: *** Makefile0000644000175000017500000000077510707257156012023 0ustar athenaathena# scheme interpreter SCHEME=scm -l # list of pages to generate PAGES=index.html papers.html .SUFFIXES: .scm .html .scm.html:$(SCHEME) $< >$@ all: $(PAGES) hacks/source.tar clean: rm -f$(PAGES) core nohup.out a.out *~ */*~ abstracts/*.html rm -f hacks/source.tar $(PAGES): support/genhtml.scm support/athena-defs.scm hacks/source.tar index.html: index.scm hacks/source.tar: rm -f hacks/source.tar make clean tar cf source.tar *.scm support/*.scm Makefile abstracts hacks mv source.tar hacks abstracts/0000755000175000017500000000000011217432463012331 5ustar athenaathenahacks/0000755000175000017500000000000011217432463011434 5ustar athenaathenahacks/density-product-real-gaussians.dvi0000644000175000017500000000752410707257156020230 0ustar athenaathena���� ;� TeX output 2002.02.09:0907������x�������=��������6�0�D��t�qG�cmr17�Densit��uNy�B�of�the�pro���duct�of�t�w�o�real�gaussian�������random�B�v���ariables��#�􍍍����°�X�Q ff cmr12�Matteo��/F���4rigo������ &a���F���4ebruary��/9,�2002��,.����'���N� cmbx12�Lemma��1���cuQ� ���@ cmti12�L��ffet�d5� ��g� cmmi12�a��and��b��b�e�indep�endent�r�e�al�normal�r�andom�variables�with�����'me��ffan�!0�and�varianc�e�1.�/�The�pr�ob�ability�density�function�of��"!",� cmsy10�j�ab�j��is��f�G��X�Q cmr12�(�c�)� �=����'�K����� |{Ycmr8�0����(�j�c�j�)�=�n9�,��=wher��ffe����K�����0�� ���is�the�mo�di e�d�Bessel�function�of�se�c�ond�kind�and�in-����'dex�350.��� ��'�Pro�of:� i(�In��the�follo��rwing,���assume�for�simplicit�y�that��c�UR���0.�6(Because���f�G��(�c�)�is����'an��ev��ren�function,�the�case��c�UR<��0��follo�ws�b�y�symmetry��V.)�8�W�e��ha�v�e��� �ʍ����@k�Pr����N��[��R?^�c�UR���ab����c����+��dc��]��������lR=����������ō��OQ1���� �[��z���� S�������p��� ��ǉz� ��� �9��2�������������甆�%��u cmex10�Z�����M������#�K� cmsy8�1�����m1����5��e��� ��� �2cmmi8�a���-:� �Aa�cmr6�2��*��=�2���J��Pr����&�G��q��������ō�2G�c��.cџ[��z� խ� �΍�j�a�j�����?��UR�b�<������ō���c����+��dc�����[��z� ��� �΍����j�a�j������$l���q������s�da���� G1�����lR�=����������ō�ê��dc���� �[��z� ��� �΍�2��������甆�Z�����M������1����ٙk1����5��e��������������33�1��33�s^�\)�����2������� ��(��&a6cmex8��� $��a���-:�2��*��+�����������!;�cmmi6�c���{q�2���33�s^�\)7F����a���G �2������� ����(�����������ō�4�K�da��4pv�[��z� խ� �΍�j�a�j�������������lR�=����������ō��� �dc���� �[��z� )�� �΍��������� ϟ甆�Z�����M��� ��1������{�0���� ��e���� ����������33�1��33�s^�\)�����2������� ��(����$��a���-:�2��*��+�����������c���{q�2���33�s^�\)7F����a���G�2������� ����(�����������ō�4pv�2�a���da��4pv�[��z�P�� �΍� ��2�a���a��������X�������ڹ[let���a����2�2��V�=�UR�u�,�2�a���da��=��du�]������z�����lR=����������ō��� �dc���� �[��z� )�� �΍���������ϟ甆�Z�����M�����1������{�0������e����V����������[�c��33�s^�\)������2������� ��(���������� ��u�� ��s^�\)lq������c�����u��+�����������c��33�s^�\)lq���u�������ן�)���������ō�-�d�du��-�d�[��z� ��� �΍���2�u���������_�������ڹ[let���u�UR�=��ce����2�z��ʮ�,��du=u��=��dz���]����������lR=����������ō��� �dc���� �[��z� )�� �΍���������ϟ甆�Z�����M�����1������{1����f��e��� ���c��j��cosh����z�������ō�%8��dz��%8��[��z� 7� �΍���2�������� G1�����lR=����������ō��� �dc���� �[��z� )�� �΍���������ϟ甆�Z�����M�����1������{�0������e��� ���c��j��cosh����z��$T�dz���� 󚍍���lR�=����������ō��� �K�����0����(�c�)����dc���� �[��z�* �΍�� ��������:����� ����1����*�x�������=�������'�(F��Vor��the�latter�iden��rtit�y�,��see�[�1����,�9.6.24].)��(V��'�/��N�G� cmbx12�References��b#����'����9GM.�<Abramo��rwitz�and�I.�A.�Stegun.�'��Handb��ffo�ok�}�of�Mathematic��ffal�F���unctions�����9Gwith�[F���ormulas,��NGr��ffaphs�and�Mathematic�al�T���ables�.��@Do��rv�er,�.�New���Y��Vork,�1965.��� ���2���� A��� ;�x�� �/��N�G� cmbx12�&a6cmex8�%��u cmex10�#�K� cmsy8�"!",� cmsy10�!;�cmmi6� �2cmmi8� ��g� cmmi12� �Aa�cmr6� |{Ycmr8� ���@ cmti12���N� cmbx12�X�Q ff cmr12�D��t�qG�cmr17�X�Q cmr12� ��������hacks/nvsetvol.c0000644000175000017500000000334210707257156013471 0ustar athenaathena/* set volume of the startup chime in the PowerMac nvram. Written by Matteo Frigo .$Id: nvsetvol.c,v 1.1 2003/01/11 11:26:30 athena Exp $This program is in the public domain. */ /* The volume is stored as a byte at address 8 in the parameter ram. */ #include #include #include #include #include #include #include typedef struct { unsigned char sig; unsigned char cksum; unsigned short len; char name; } header; void die(const char *s) { perror(s); exit(1); } void seek_pram(int fd, int offset) { if (lseek(fd, offset, SEEK_SET) < 0) die("lseek"); } int find_pram(int fd, int *size) { header buf; int offset = 0; while(read(fd, &buf, sizeof(header)) == sizeof(header)) { int sz = buf.len * 16; if (!strncmp(buf.name, "APL,MacOS75", 11)) { *size = sz - sizeof(header); return offset + sizeof(header); } offset += sz; seek_pram(fd, offset); } die("no PRAM found"); } #define VOLADDR 8 int main(int argc, char *argv[]) { int fd, offset, size; char *buf; fd = open("/dev/nvram", O_RDWR); if (fd < 0) die("can't open /dev/nvram"); offset = find_pram(fd, &size); buf = malloc(size); if (!buf) die("can't malloc()"); seek_pram(fd, offset); if (read(fd, buf, size) != size) die("error reading /dev/nvram"); printf("current volume is %d\n", buf[VOLADDR]); if (argc > 1) { buf[VOLADDR] = atoi(argv); seek_pram(fd, offset); if (write(fd, buf, size) != size) die("error writing /dev/nvram"); printf("new volume is %d\n", buf[VOLADDR]); } close(fd); } hacks/pipe.ml0000644000175000017500000000072410707257156012735 0ustar athenaathenatype void = Void type ('a) ucont = U of (('a) dcont -> void) and ('a) dcont = D of ('a -> ('a) ucont -> void) and ('a, 'b) pipeline = 'a ucont -> 'b dcont -> void let get k (U u) (D d) = u (D (fun v u' -> k v u' (D d))) let put v k (U u) (D d) = d v (U (fun d' -> k () (U u) d')) let pipe a b u d = a u (D (fun v u' -> b (U (fun (D d') -> d' v u')) d)) let run pipeline = pipeline (U (fun d' -> Void)) (D (fun v u' -> Void)) let stop (U u) (D d) = Void hacks/schinken.tar0000644000175000017500000005000010707257156013750 0ustar athenaathenaschinken.scm0100644000076400007640000001575607471535622012710 0ustar athenaathena(require 'macro) (require 'sort) (require 'printf) ;;; dates (define (make-date yyyy mm dd) (let ((t (make-vector 3))) (begin (vector-set! t 0 yyyy) (vector-set! t 1 mm) (vector-set! t 2 dd) t ))) (define (date->yyyy t) (vector-ref t 0)) (define (date->mm t) (vector-ref t 1)) (define (date->dd t) (vector-ref t 2)) (define (date-less? a b) (or (< (date->yyyy a) (date->yyyy b)) (and (= (date->yyyy a) (date->yyyy b)) (or (< (date->mm a) (date->mm b)) (and (= (date->mm a) (date->mm b)) (< (date->dd a) (date->dd b))))))) ;; list functions from Olin's library (define (filter pred lis) (let recur ((lis lis)) (if (pair? lis) (let ((head (car lis)) (tail (cdr lis))) (if (pred head) (let ((new-tail (recur tail))) (if (eq? tail new-tail) lis (cons head new-tail))) (recur tail))) '()))) (define (filter* preds lis) (if (null? preds) lis (filter* (cdr preds) (filter (car preds) lis)))) ;;; values ;; Values are lists of pairs (currency . amount), as in ;; '((USD . 10) (Eur . 20)) . Algebraically, values are ;; first-degree polynomials in the currencies. ; merge terms with the same currency (define (value/canonicalize val) (define (sum l x) (if (null? l) x (sum (cdr l) (+ x (car l))))) (if (null? val) val (let* ((currency (caar val)) (same (filter (lambda (v) (eq? currency (car v))) val)) (other (filter (lambda (v) (not (eq? currency (car v)))) val))) (cons (cons currency (sum (map cdr same) 0)) (value/canonicalize other))))) ; add list of values (define (value/sum l) (value/canonicalize (apply append l))) (define (make-currency c) (let ((in-currency (cons 'in c)) (out-currency (cons 'out c))) (lambda (amount) (lambda (return) (return (cons in-currency amount) (cons out-currency amount)))))) ;;; transactions (define (make-transaction amount date description other-account reconciled?) (let ((t (make-vector 5))) (begin (vector-set! t 0 amount) (vector-set! t 1 date) (vector-set! t 2 description) (vector-set! t 3 other-account) (vector-set! t 4 reconciled?) t ))) (define (transaction->amount t) (vector-ref t 0)) (define (transaction->date t) (vector-ref t 1)) (define (transaction->description t) (vector-ref t 2)) (define (transaction->other-account t) (vector-ref t 3)) (define (transaction->reconciled? t) (vector-ref t 4)) (define (sort-by-date l) (sort:sort l (lambda (a b) (date-less? (transaction->date a) (transaction->date b))))) ; unique check mark token (define ^ '^) (define (make-account name description) (let ((transactions '())) (define (add! reconciled?) (lambda (howmuch when why other) (let ((t (make-transaction howmuch when why other reconciled?))) (set! transactions (cons t transactions))))) (define (self reconciled?) (lambda (msg) (case msg ((name) name) ((description) description) ((transactions) transactions) ((^) (self #t)) ((add!) (add! reconciled?))))) (self #f))) (define (make-combined-account name description . accounts) (define (acc->name acc) (acc 'name)) (let ((acc-names (map acc->name accounts))) (define (transactions) (filter (lambda (t) (not (memq (acc->name (transaction->other-account t)) acc-names))) (apply append (map (lambda (acc) (acc 'transactions)) accounts)))) (define self (lambda (msg) (case msg ((name) name) ((description) description) ((transactions) (transactions))))) self)) (define (account->trasactions preds account) (filter* preds (account 'transactions))) ;; list of accounts (define *accounts* '()) (define (register-account! a) (set! *accounts* (cons a *accounts*))) (define (destroy-accounts!) (set! *accounts* '())) (define-syntax define-account (syntax-rules () ((define-account ) (begin (define (make-account (quote ) )) (register-account! ))))) (define-syntax define-combined-account (syntax-rules () ((define-combined-account ...) (define (make-combined-account (quote ) ...))))) ;; user interface: (define (move! when howmuch why from to) (howmuch (lambda (in out) (begin ((from 'add!) (list out) when why to) ((to 'add!) (list in) when why from))))) (define (move*! when howmuch why accounts) (if (and (pair? accounts) (pair? (cdr accounts))) (begin (move! when howmuch why (car accounts) (cadr accounts)) (move*! when howmuch why (cdr accounts))))) (define (month mm) (lambda (dd yyyy) (let ((when (make-date yyyy mm dd))) (lambda (howmuch why acc0 acc1 . accn) (move*! when howmuch why (cons acc0 (cons acc1 accn))))))) ; user-visible date constructors. Usage: (apr 1 2001) (define jan (month 0)) (define feb (month 1)) (define mar (month 2)) (define apr (month 3)) (define may (month 4)) (define jun (month 5)) (define jul (month 6)) (define aug (month 7)) (define sep (month 8)) (define oct (month 9)) (define nov (month 10)) (define dec (month 11)) ; user-visible value constructors. Usage: (USD 10) (define USD (make-currency 'USD)) (define Eur (make-currency 'Eur)) (define (money->string v) (let ((currency (car v)) (amount (cdr v))) (case (car currency) ((in) (sprintf #f "in %-4a %9.2f" (cdr currency) amount)) ((out) (sprintf #f "out %-4a %9.2f" (cdr currency) amount))))) (define (money->algebraic v) (let ((currency (car v)) (amount (cdr v))) (case (car currency) ((in) (cons (cdr currency) amount)) ((out) (cons (cdr currency) (- amount)))))) (define report-transaction (lambda (transaction) (let ((date (transaction->date transaction)) (amount (transaction->amount transaction)) (desc (transaction->description transaction)) (reconciled? (transaction->reconciled? transaction)) (other (transaction->other-account transaction))) (printf "%1s %04d/%02d/%02d %a %-18a %s\n" (if reconciled? "^" " ") (date->yyyy date) (+ 1 (date->mm date)) ; month human format (date->dd date) (apply string-append (map money->string amount)) (other 'name) desc)))) (define (report account . interesting?) (for-each report-transaction (sort-by-date (account->trasactions interesting? account)))) (define (balance account . interesting?) (map money->string (value/sum (map transaction->amount (account->trasactions interesting? account))))) (define (algebraic-balance account . interesting?) (value/sum (map (lambda (v) (map money->algebraic v)) (map transaction->amount (account->trasactions interesting? account))))) (define (compose f g) (lambda (x) (f (g x)))) ;; commonly used predicates (define reconciled? transaction->reconciled?) (define not-reconciled? (compose not reconciled?)) (define (before yyyy mm dd) (lambda (t) (date-less? (transaction->date t) (make-date yyyy (- mm 1) dd))))schinken-example.scm0100644000076400007640000000221307473014161014311 0ustar athenaathena(load "schinken.scm") (define-account checking "Checking Account") (define-account rent "monthly rent") (define-account income "income") (define-account utilities "gas, electric, phone and cable") (define-account other-expenses "") ((may 1 2002) (USD 1234.56) "salary" income checking) ((may 2 2002) (USD 100.00) "May rent" checking rent) ((may 2 2002) (USD 10.00) "phone bill" checking utilities) ((may 3 2002) (Eur 13.00) "check #101" checking other-expenses) ;; example interactive use: ;; ; > (balance checking) ; ;Evaluation took 0 mSec (0 in gc) 948 cells work, 4024 env, 695 bytes other ; ("out eur 13.00" "out usd 110.00" "in usd 1234.56") ; > (algebraic-balance checking) ; ;Evaluation took 10 mSec (0 in gc) 94 cells work, 317 env, 39 bytes other ; ((eur . -13.0) (usd . 1124.56)) ; > (report checking) ; 2002/05/01 in usd 1234.56 income salary ; 2002/05/02 out usd 10.00 utilities phone bill ; 2002/05/02 out usd 100.00 rent May rent ; 2002/05/03 out eur 13.00 other-expenses check #101 ; ;Evaluation took 10 mSec (0 in gc) 3015 cells work, 11996 env, 1114 bytes other hacks/pipe.scm0000644000175000017500000000150110707257156013101 0ustar athenaathena(define (get k) (lambda (u d) (u (lambda (v u*) ((k v) u* d))))) (define (put v k) (lambda (u d) (d v (lambda (d*) ((k) u d*))))) (define (pipe a b) (lambda (u d) (a u (lambda (v u*) (b (lambda (d*) (d* v u*)) d))))) (define (run pipeline) (pipeline 'bogus-source 'bogus-sink)) (define (produce n) (put n (lambda () (produce (+ n 1))))) (define (consume) (get (lambda (n) (begin (display n) (newline) (consume))))) (define pipeline (pipe (produce 1) (consume))) ;(run pipeline) ;;;------------------------------------------------------------ ;; Safe-for-space version (define (get1 k d) (lambda (v u*) ((k v) u* d))) (define (get k) (lambda (u d) (u (get1 k d)))) (define (put1 k u) (lambda (d*) ((k) u d*))) (define (put v k) (lambda (u d) (d v (put1 k u)))) hacks/density-product-complex-gaussians.dvi0000644000175000017500000001030410707257156020742 0ustar athenaathena���� ;� TeX output 2002.02.09:0833������x�������=��������I���D��t�qG�cmr17�Densit��uNy�B�of�the�pro���duct�of�t�w�o�complex����|��gaussian�B�random�v���ariables��#�􍍍����°�X�Q ff cmr12�Matteo��/F���4rigo������ &a���F���4ebruary��/9,�2002��%�܍���'���N� cmbx12�Lemma��1���cuQ� ���@ cmti12�L��ffet�/�� ��g� cmmi12�a��and��b��b�e�indep�endent�c�omplex�normal�r�andom�variables�with�����'me��ffan�!0�and�varianc�e�2.�/�The�pr�ob�ability�density�function�of��"!",� cmsy10�j�ab�j��is��f�G��X�Q cmr12�(�c�)� �=����'�cK����� |{Ycmr8�0����(�c�)�,��wher��ffe���K�����0����is�the�mo�di e�d�Bessel�function�of�se�c�ond�kind�and�index�0.��7荑'�Pro�`of:� ���Let�6x�F��ƹ(�c�)��\=��Pr��f�[�j�ab�j��<�c�]�b�S�e�the�probabilit��ry�distribution�function�of����'�j�ab�j�,��so�that��f�G��(�c�)�UR=�����Fu��_�� �2cmmi8�d��������z�!���dc����� ���F��ƹ(�c�).�8�W��Ve�ha��rv�e:�� 덍��fȶ1������F��ƹ(�c�)�������f=���������Pr���vA[�j�ab�j�UR��c�]����U^������f=����������ō���*1���!�[��z�� � �΍(2��n9�)������2��������(_�甆�%��u cmex10�Z����� � �_�,p�p�msbm8�C���$�da�����甆�Z������ �_�#�K� cmsy8�j�b�j��c=�j�a�j���+N�e��� ���(�j�a�j���-:��Aa�cmr6�2��*��+�j�b�j���-:�2���)�=�2��8�7�db����#'卍����f�=����������ō���d1���!�[��z� ��� �΍2��������Dӟ甆�Z������ �_�C���6��e��� ��j�a�j���-:�2��*��=�2����da�����甆�Z�����M���2��������0��������ō��V�d��?�[��z� ��� �΍�2�������+I�甆�Z�����M��7I��1����1���c=�j�a�j���=���r�S�e��� ���r�� �c�����b�+���������qS�c��33�s^�\)����r��1Ɵ�G�2������� =}��(������2l�dr�>6:�����덑'�The��substitution��e����2�z�� �=�UR�r��S����2�2����=c��yields��=e�����C�1������F��ƹ(�c�)������=�=�������a�甆�Z�����M���a�1����� �1��������ō��D0�c����y�[��z���� �΍�2��������e��� ��z��ʬ�e��� ���c��j��cosh����z��$T�dz��������'�The��Bessel�function��K�����1�����ob�S�eys�the�follo��rwing�iden�tit�y�[�1����,�9.6.24]:����������K�����1����(�c�)������~-=������С��甆�Z�����M��ܡ��1�����La�0���硽�e��� ���c��j��cosh����z���$T�cosh���all�required�v��X�alues�are����'readily��a��rv��X�ailable�from�the�table.����8��Compared�d*to�its�w��rell-kno�wn�d*base-2�analog,���this�sc��rheme�requires�a�table����'of��size��log���Ο�T�3�����n��instead�of��log���Ο�T�2���n�,��Wand�its�maxim��rum�relativ�e�error�also�gro�ws�as�����'log���6-K��T�3��<�M�n�꨹instead�of��log�����T�2�����n�.������1����*���;�x����K� cmsy8�!",� cmsy10�;�cmmi6��2cmmi8���g� cmmi12�|{Ycmr8�X�Q ff cmr12�D��t�qG�cmr17���� msbm10�X�Q cmr12���u cmex10���������
{"ft_lang_label":"__label__en","ft_lang_prob":0.62129766,"math_prob":0.82477665,"size":54873,"snap":"2019-13-2019-22","text_gpt3_token_len":16324,"char_repetition_ratio":0.14055295,"word_repetition_ratio":0.12448133,"special_character_ratio":0.333388,"punctuation_ratio":0.12593846,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9516143,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2019-03-20T00:51:58Z\",\"WARC-Record-ID\":\"<urn:uuid:2d0c956d-dd3c-42e6-a054-792246155753>\",\"Content-Length\":\"92416\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:5cc06355-1349-49e6-a37f-676e1deee1be>\",\"WARC-Concurrent-To\":\"<urn:uuid:92f8dab6-a95c-40f3-a457-eb8753b5a046>\",\"WARC-IP-Address\":\"75.98.172.202\",\"WARC-Target-URI\":\"http://www.fftw.org/~athena/hacks/source.tar\",\"WARC-Payload-Digest\":\"sha1:CZS2UI7HYEJ2QDNK2IXQWWPWBNP3I2G2\",\"WARC-Block-Digest\":\"sha1:RKWO46BWXSQ2C6D24M6TZI4WS2VNAGQ2\",\"WARC-Identified-Payload-Type\":\"application/x-gtar\",\"warc_filename\":\"/cc_download/warc_2019/CC-MAIN-2019-13/CC-MAIN-2019-13_segments_1552912202188.9_warc_CC-MAIN-20190320004046-20190320030046-00299.warc.gz\"}"}