[<<][meta][>>][..]
Code generation for C-based applications

TL;DR

The core project is RAI (Racket Abstract Interpretation), currently
used in the generation of C code for digital music instruments and
effects.

http://zwizwa.be/rai


For DSPM, the Haskell experiments that predate RAI, have a look at the
entries in this log, and the files in the meta archive:

http://zwizwa.be/darcs/meta/dspm



-----------------------------------------------------------------------


These notes concentrate on techniques for manageable code generation
(multi-stage programming, macros, domain-specific languages, ...) to
be integrated with C-based applications in the domains of embedded
systems and digital signal processing.

The focus is on approaches using Functional Programming languages and
techniques.  For more info see entry://20111119-093057

The source code archive for this project is at:

    http://zwizwa.be/darcs/meta


Current - Jan 2012

  The problem I'm trying to solve is to separate these 2 engineering
  tasks that pop up when creating (audio) DSP applications:

    * Mathematical models, expressed as (possibly nonlinear)
      state-space update equations[1].

    * Implementation: management of interconnect, persistent state and
      code sequencing.

   Traditionally, one would verify correctness of models in some
   simulation package, and then manually incorporate the second step
   by translating the abstract structure into a specialized
   implementation.

   The problem is that not recognizing the structure of this last step
   leads to ad-hoc implementation decisions and hard to manage code.

   Put differently: the information difference between the abstract
   model and the implementation is quite substantial, i.e. there are
   many decisions to be made about where to put data and in what order
   to perform computations.

   However, the inherent structure/symmetry of the design choices to
   be made do lend themselves to abstraction, by employing the
   technique of (C) code generation.

   The approach I'm using is the construction of a typed, embedded DSL
   in Haskell, with extensive use of generic programming (type
   classes).  Code generation in itself is not a new thing.  Typed
   code generation however is.  I'm mostly following the ideas
   described here[2].

  

[1] http://en.wikipedia.org/wiki/State_space_(controls)
[2] http://okmij.org/ftp/tagless-final/index.html


20161009 P Language: event-driven state machines
20140328 Real time and stacks
20140127 Ragel state machine compiler
The Disciplined Disciple Compiler (DDC)
20140114 Conclusions from RAI
20140113 Haskell Embedded
20130928 State machine compiler
20130706 State machines
20130610 Moved
20130529 Delay lines already are SISO systems
Delay: cut out dl-bind.. what happens?
Take a break
RAI doc merge
Time feedback
Stream vs. param
20130528 Delays and loops don't mix
Cleanup
20130527 Trouble
Array sizes
auto-lifting
for/n
20130526 Intermediate vectors
20130524 Now, what is the point?
A proper map?
Catchy name: Kauzal
Roadmap
Grid
FeldSpar
What is a stream?
20130523 Extra pass?
Albert Graef - Pure
Faster code gen
Common subexpression elimination
Faust
Circular deps between typing and evaluation
20130522 Compile-time vectors
FDN: pipelining
unpack-function
Delay inside loop?
To inline or not?
Implicit sharing in Haskell
20130521 C-like Surface syntax
ai-array.rkt
20130520 Tension between compile time and run time aggregate datastructures
Delay #f
Abstracting recursion
Is it too crufty?
Type analysis stuff
Macro stepper
Type Checking
20130517 Compile time vectors
20130515 Delay lines
20130514 KVR / music-dsp / pd-list post
Type system trouble: delay lines
20130511 Differentiated integral interpolation
20130510 Delay lines
20130509 Array references.
Getting rid of all syntax stuff in ai-array
Outer product
Abstract array references
const
Scrap the whole thing?
Refactoring
Automatic lifting
#lang vs. macro
20130508 Speeding up the dev cycle
20130507 Bret Victor / Live coding
Higher order functions?
BUG: problem with time / space commutation
Fixed point DSPs
20130506 Feldspar
20130504 How to make something difficult?
Events
Annotating approximations
20130503 Scales
20130501 Tagging nodes
20130430 Parameter meta info
20130428 Parameter ranges
20130427 Input types
20130426 Encoding "float types"
20130419 Transfer function computation
20130413 Structured vs. random access arrays
20130411 Delay memory
Type system thoughts + array language
20130410 type cleanup day
20130408 copy-nodes
Delay lines
20130406 Racket plotting
Better plotting
20130405 Ai-stream state stuff
Changing the hold / setup stuff
20130404 hold and setup
ai-stream.rkt : implementation of reduce/n is wrong
Fold or map-reduce?
20130403 Explicit time loop
Cleanups
Trouble
20130402 State machine setup
Lazy nodes
Ill-defined?
Control rate ops
Setup code : duplicate input network
Cleanup
TODO
Type composition
20130401 ai-type
Implementing dual/multiple-rate programs and dead code elimination
20130329 BUG: dependency problem
20130327 BCR2000
20130326 Missing ordinary data-dependent loops for initialization
Fast floating point modulo
Solving polynomial constraints
20130325 BCR2000
20130324 Small signal analysis
20130323 Environment extension
Problem in ai-freq.rkt
20130321 Autodiff full
Autodif pow(x,y)
20130319 Filter math
Lowpass filter
TODO
Graphs
20130317 ai-stream.rkt
Rough edge: setup depends on streams?
20130316 Testing the control-rate functionality.
State names
Naming parameters
20130315 Control rate combinators
Control rate
20130314 Series expansion vs. differentiation
FLUNK presentation
20130313 Autodiff vs taylor
Tailor series
Control rate
20130310 Tension between functional (e.g. Haskell) and function-level (FP) programming
Support for truncated power series
Support for piecewize time processing
Cleanup
Explicit time loop?
Linear exponentials, conclusions up to now
20130309 Linear exponentials, without reset?
Approach for linear exponentials
20130308 VCF / VCO
20130307 Controls
20130301 Plugin format: sp: just data?
20130228 Focus
Lifting semantics : adding type information
Transfer functions
Rings and multiplicative inverses
Composing semantics
20130226 Matrix operations
20130225 Linear function test functions
20130224 Guessing types of linear functions : linear variable vs. multiplicative parameter
20130223 Prolog
Testing linear functions
20130222 Compile time data structures.
Conclusions: transfer functions
Transfer function
Gaussian elimination
Z transform
Output feedback
feedback/n trouble
Compiling to C and Scheme is difficult
Fold vs accumulate
20130220 State buffer swapping
C arrays
20130219 Single assigment
Auto-lifting
control is only necessary for memoization
Tension between SSA and "named output" Oz dataflow style.
for/fold to accumulator assigments
Named let
20130218 Distributing indices
Lifting primitives
Fixing typing
20130216 Next
20130212 Possible bug
Loop inference. Automatic map?
20130210 Types
20130205 Delay lines
Generalizing fold
20130204 BUG: Voice alloc
Const is not well-defined
20130202 Enhancements
20130130 Language factory
20130129 Grid index computation
Nested structure for dictionary?
Why not simply OO then? - part II
Generalize loop
Next
It works!
20130128 Fixed const
Occurs check
Accumulators
The `bus' form
Lazy syntax
Bus: practically
20130127 Think streams
Building an audio synth DSL: Space and Time
Dimensions: TIME vs. SPACE
Loop context
Composition of structure: commutation of space and time combinators
Duplicate circuit
Why not simply OO then?
Loops in DSP: `feedback' is contextual
State threading context needs to be explicit.
Practically: lazy encoding?
Macros, combinators, circuits.
Loops: combinators or straight recursion?
Mainloop over in/out/param blocks
20130126 Loops
Trouble
Type inference (unification)
bound-identifier=?
Map and AI
20130125 Plugin extension: SP
Parameter structure
Propagate parameter names
C loop generation: split inputs in streams and parameters
Loadable modules in Pd
20130124 Testability / partial evaluation
20130123 AI and single (concrete) intepretation
Autodifferentiation
20130122 Haskell vs. Scheme : DSL embedding with higher order abstract syntax
20130121 Can #%app be overridden locally?
Next
20130120 ai-eval.rkt
What are feedback stream operations?
ai-eval.rkt
This is going to be fun!
Stream fold
Onepole
Time delay primitive
Phasors
Multiple return values
20130119 Modifying %app syntax?
Multi out
C code generation from scheme syntax?
AI stream spec to state-threaded update function
20130118 Doing it wrong?
Practical application
siso.rkt
20130117 Racket compile-time bindings
SISO in scheme
siso abstraction in Scheme
20130116 Simple AI tests
Abstract interpretation in Racket
Time for the difficult questions
20121223 More use of GCC
Data structures
Too complex?
Trying out test cases
Status
Language parameterized by monad with pure semantics
GreenArrays GA144
20121222 Monads and arrows
Monads too serial?
Is multiple interpretation necessary?
Poly^2
20121126 ORC
20121119 GCC AVR ABI
20121113 restrict
Does GCC inline function pointers?
20120128 DSL concrete syntax
20120118 Prettyprinting
20120116 Language.C.Analysis
20120115 A closer look at Language.C
Analyzing C
20120114 CAnalyze
20120112 Meta-currying
20120111 Type Level Programming
20120110 Upsampler: config
Next
Evaluation of recent work
Upsampling : Constant Array / Discrete Events?
Next
20120109 replace stx by r s ?
20120108 SM updates
Still fundep problems
Renaming
20120107 Pack
20120104 Next
ArrowLoop
SysCompile
Getting Sys.hs to work
20120102 Another Atom bug?
Sys.hs and monadic initial values
From let -> do
Bug
Done?
Fix named fields
Some missing Unatom
_lambda type
Fundeps
20111231 Debugging functional dependencies
Cleanup
I'm sick of misunderstood morphisms..
Generalizing array instead
Inference check
Next: failing test cases
What is a a virtual struct?
20111230 It's a mess
Replace argument lists by Var / VarPair / VarCar / VarCdr
Binary trees all the way down
Horrible hack
Simpler tests for SArray
Supporting multi-arity references in Term?
SArray has no 'a' param
20111229 SArray and inference
20111228 Full stack?
Monadic anyway..
compilation without annotation
Atom -> L for Leaf ?
20111227 Multi-dim arrays
20111225 Struct declarations
Binder for _unpack
20111224 APair
Why binary trees as primitive structure?
Flat structures
20111222 Struct / Tuple
20111218 Structure get/set and _lambda / _app
PrettC : monadic generator necessary?
C struct
Typed CPP
20111215 C Struct's "." and "->" dereference.
20111213 C structs
Toplevel definitions
20111212 Compiling toplevel functions
Indexing
Deleted patch
I'm done with these stupid type indexing tricks
20111209 Toplevel definitions
20111208 So is it ready?
20111207 Sys.hs existentials
Just structuring of representation (<-> representation of structuring)
20111206 Next: fix Sys.hs
Building Atom into TML?
Sys.hs
Review
Missing _letrec for Value
Mile stone
20111205 Signatures..
Ambiguities..
Occurs check
Types are too complex
runSTUArray
Haskell type classes and optimization
20111204 Next
Array types
Representing arrays in Term
Problem: first argument of _let monadic?
Arrays or ports?
20111120 Mutable arrays
Term Write
Streams - Named outputs
20111119 Next
PrettyC.hs
Meta Introduction
20111107 Next
Language.C Functor
20111104 Pretty-printed C AST
Parsing with Language.C
20111102 Reusing haskell parser
20111030 Language.C
Delimiting Let
20111029 Next
Cleanup
Lambda problem
Next
Infer multi-arg functions
Next
Inserting Lambda binding
20111028 Pure functions vs. embedded syntax
Strategy
Primitive data
CompileVar
Close, no sigar
Simply typed functional language?
Term = (type-annotated) Scheme?
Pfff...
LoopArgs
Fixing type infrerence
20111027 Representing functions
20111026 Fixing some of the overlapping instances cruft
20111025 (->) (Code Tint) as monad
TML Code in terms of Expr
Smart Generators
Zipper for Exp?
2 levels: dataflow and control flow
20111024 Zipper for Expr?
20111023 _if
Primtiive type stuff
Handling tuples
Encoding of loop
One return type?
Overlapping Instances
20111022 Compiling to expression form
Expression form
20111021 Fold or Map
20111020 Summary
Assignments suck
Representing I/O as consumer functions.
Nested let syntax
Summary
Stackless recursion
Compiling letrec
Tail recursion
Fold is good
20111019 Reflection / summary.
Abstracting foldable code
SigFold
Stuck - control flow / nested scopes.
Nesting
20111018 Applicative vs. dataflow
Memory read is just another binding
Lifting SMs
lifting over streams
20111017 SSA
Adding load/store
Combinators
20111016 Generating C code
Full circle?
TML + SysM
20111015 Uncurried input
Bug: computations run twice
Getting unstuck with recursive type class definitions.
20111014 TermApp
Remove existential type
Type annotations in Asm interpretation of ExprM
DSPM : interpretation
Pure Monad?
DSPM
Giving up on Haskell's LLVM bindings
20110922 Commutation with staging
Interfacing Pd with LLVM objects
20110910 Combinatory Logic and State Machines
Status
20110906 NEXT
Primitive data
Commuting monad & state observe
20110831 Ha!
20110830 Disentangling the Arrow and Monad
20110828 2 x existentials
20110827 Functional dependencies
Connecting sharing monad to SigOp
Sharing monad
Sharing revisited
20110826 Tuples to lists
State access
I want code not just behaviour
Next: make abstract interpretation work.
20110825 Recent HC stuff
The problem with hardware is state
20110824 C/C++ is good enough
20110823 Code gen & let/if
20110821 AudioProc
Next
Towards 1 / 1 - z
Moving on
20110820 Answer to Oleg's post
20110818 Writing down the Kleisli isomorphism with existential types.
20110817 Arrows to Monads: different SSM representation.
20110816 The existential unpacking problem
Arrow to Monad
StateSpace as Arrow
TODO
Arrow class
Kleisli arrows
HC question: Hiding "growing" state using existentials.
20110815 Join
Conclusion
Is this SSM threading a Monad?
Tying the knot with Applicative
Applicative approach
Applicative?
Num SSA ?
20110814 The State Monad and State Space Models
Monad transformers
Audio DSP is not Image DSP
State machines and applicative.
Sawtooth
full circle
LLVM command line tools
Re-focus
Struggling with LLVM type classes
20110808 do and binding
Interface question: a -> b -> M c or M a -> M b -> M c
All this fuss over liftA2 ?
Type classes as constraints
LLVM Haskell bindings
Numeric Prelude
synthesizer-llvm
LLVM's SSA
20110806 Next
20110803 Control flow graphs, is it really a problem?
20110802 Closure Conversion / Lambda Lifting
Next: representing basic blocks
Predicates and Control flow
Type magic
SymExpr: compiling to type-stripped recursive data structure
Phantom types
Atom
Conclusion: Num can be sequential
20110801 Better syntax
Sharing
Next?
So... instead of strings, what about different data types?
Struggling with SC monad
Data vs. Code
Joining dictionaries
Intuition
20110724 Let : summary
Representing "let" in the final language
Merging HOAS & Sharing monad
Higher-order abstract syntax
Next
20110723 Textual representation: no intermediate data type
GADTs for typed assembly language
Type conversions
Symantics => Num, or the other way around?
Tagless..
Very simple type system -> inference is trivial. Can we ignore?
Typed syntax
Types for DSP language
General -> concrete type?
Term type
Keeping types
Next
20110719 Sharing
Can I have let?
20110717 Mixing expressions (trees) and sharing (directed, acyclic graphs)
20110716 Code gen and eval?
Separate memo function
Allocating nodes
CPS + memoization
Lifting to CPS computations
Learning Haskell: exploring abstractions
Type of bind
Using the CPS monad
Continuation monad : two return types?
Monad intuition
20110712 comonads
Monad data flow analysis
20110702 OCaml perform notation
20110627 Getting over do-notation
20110619 Partial Evaluation
20110612 Tethered development
20110615 Macros vs. functions
20110608 Separate meaning from mapping
20110523 HiTech C compiler
20110521 Doing something wrong
20110520 BER MetaOCaml
Opaque code in Scheme?
20110416 The real problem is not C.
20110126 Composition at run time
Problems
2 x n stages
Compile time vs. Run time
Automatic state patching
20110124 Composite Models
Runtime or compile-time?
Abstract vector
State space composition
Syntax parameters
20110123 Simpler state space syntax
State space DSL: next
Context: absint and state-space
State space models: representation?
State space form: draft logic
20110122 Different state space form
Stacking units
Sawtooth generator
Natural rise of partial continuations
First class signatures
Signatures and syntax
20110121 Using a single model ouput? I.e. a "main" function?
Racket-based DSP eDSL specs: simple abstract interpretation.
Racket units and the type class trick
Racket (PLT) units
20110120 Back to Scheme?
Adding context to values in Haskell: not possible implicitly.
20110119 Monads, CPS: too serial?
TODO
Onward: sharing + type classes
Simpler monad
Is Haskell just too difficult?
20110118 Using the SC monad
20110117 State Continuation Monad
Folding Code : Giving Up Random Access
Monadic multi-stage programming
Monadic let (a failed attempt at State continuation monad in Haskell)
20110116 Reasoning About Staged Programs
20110114 DSP code gen
Combining code generation with memoization: Not without monads?
20110113 Update equations
20110111 Representing difference equations
20110110 Sawtooth generator
Virtual analog
20110102 Multiple interpretations in Scheme
20110101 Copilot
20101118 Again: concatenative languages
20101117 Generalizing Staapl
20101023 Yegge Grok
20101008 Writing languages in the C preprocessor
20100930 Backronym: ENUFC
20100827 Hash Consing with Names
20100826 A Theory of Typed Hygienic Macros (Dave Herman's PhD dissertation)
Hash consing for static data structures: mixing Flash and RAM
20100819 Data Structures in Flash
20100703 Practically: an application + Current code structure reminders
Simple IIR compilation: slow + fast state memory
Linear versus Tree updates
The DSP problem
Implementing Z
20100629 Modeling: interpretation and compilation
20100624 Picking up again
20100623 Next
20100511 Defining Z
20100510 Lifting and combinators
Next
20100509 Memo again
Stacks
I -> O -> C
Summary
20100508 Multiple outputs
Summary
Just State
Combining monads
Just flattening + node allocation + input collection.
Flattening Term graphs (SSA)
Main problem
Goals
20100507 Finalizing (-> Procedure)
Removing Function.hs
20100506 Memoization of (==), the right way
Living without intrinsic object identity : Shared.hs
20100505 Composition in the low-level rep
20100504 Summary
Assignments + applications are primitive procedures
Much ado
Unification
The Pure Data patch format
Connect consumes inputs, while outputs can observe internal nodes
Comment dumps
Implementing DFN as a State monad.
The essence of dataflow
Representing (single) assignment
More DAG interface
20100502 DAG Interface
SSA IN/OUT parameterization
DAG Representations
Pure Data & Abstract Interpretation
Compositional dataflow notation
20100501 Abstract Interpretation & Polymorphism
20100430 Unified Embedded^2 DSL
20100428 Dataflow notation: input and output?
20100426 Fender Tone Stack
Dataflow notation
20100424 Z -> loop
20100423 Term.hs and Function.hs -> generate C code
Haskell in Emacs: getting rid of :cd ~/.cabal on C-x C-l
Jack simple-client.c
20100421 Re-loadable C modules
Generating an audio synth
20100419 Simulating Mechanical Systems in Haskell
20100418 Loop Fusion: Parametrization of Equivalence Classes
DSP language - combinators
20100417 Classical Mechanics in Scheme and Abstract Interpretation
20100411 Image processing
20100407 Total functional programming
Embedding C in Haskell
20100403 Dataflow and loops
20100327 Register allocation for image processing
20100316 When is a stage a stage?
Feldspar
20100314 Haskell vs. Scheme
Squinting at machine code
Compiler
Dirty machine language
Is this useful for testing optimization rules?
Encoding `find' in types?
The Simulator
20100313 Manipulating binding structure in Haskell
Haskell and unicode
What are macros?
Logic simulation and SSA form
Functions vs Macros
Logic simulation : the problem is state.
20100311 Assembler snarfing
20100310 Closing the Stage
Improving the Static Analysis of Embedded Programs via Partial Evaluation.
Type checking is a stage
Analyzing PowerPC programs
20100302 MetaOCaml -> BER MetaOCaml
20100227 Filters
Next
Adaptive filtering
Memoization and filter banks
RatFunc and Applicative
Functional analysis
Next?
AwesomePrelude
20100226 Converting rational functions to difference equations
Lucid and Streams in Haskell
20100225 Simulink S-functions
20100224 Applicative functors
Practical issues for DSP language
20100221 The DSL for DSP
Using tagless representations
Tagless interpreters
Input / State / Output
Scheme vs. Serious Static Types
20100220 Type-level vector size specifications
Operations on polynomials
Embedding Faust in Haskell
A project
Replaced check with mplus from Control.Monad
Shared -> properly factorized memoization
Next
20100219 State / Continuation monad
20100218 Control Structures or Network Combinators?
20100215 Conclusions
Combining Cas.hs and Ai.hs
Nesting the Term type
Template Haskell
Commutative manipulations cont..
20100214 Commutative manipulations
Ai and nesting types
Cleanup: sparate Ai.hs and Term.hs
Environment is only necessary during threading
Merging lists: recovering tail sharing
Merging environments
Term -> Closure Term Env
20100213 Pointer equality in Haskell
Memoizing original "merge" approach
Flattening expressions into SSA
code.hs (nodes.hs)
Staged programming vs. partial evaluation
Let's start again
20100212 Continuation monad
20100210 Monads and the incredible uselessness of intuition
Memoization and Control
Typeclasses vs. multiple dispatch
Nesting number types
Affine values
Knuth - Bendix
Typed functional programming (Haskell vs. Scheme)
Commutation rewrite rule in CPS
One-pass generation
Normal forms
Structure of datatypes
Terms do not know of environments
Expected kind `* -> *', but `Code a' has kind `*'
20100208 Haskell and memoization
Threading environment
20100207 Cleanup
Vectors and Matrices
Type classes are nice
Reconstructing environment
Problem with evaluation order
Commutativity and associativity
ai.hs: base code works
20100206 Expression equality
Explicit memoization
Backtracking and lazy association
20100205 Haskell: generating unique tags
Combining environments
20100204 Simple numeric abstract interpretation: implementation
20100203 MetaOCaml and functors, or Haskell and typeclasses
20100130 OCaml monads: perform (do) notation
20091226 Defunctionalization
20091021 UML
Process vs. Tools
20091020 XML and XSLT
20091010 MetaOCaml -> Fortran90
20091009 Code Gen @ Sioux (dutch)
Address Generation
C preprocessor functional programming
20091007 NASA Survey on Automatic Code Generation (ACG)
HPC & CFD
20090927 DSP: the problem
20090925 Marc Leeman's thesis
20090924 DSL'09 conference
MARTE & UML modeling
20090923 code generation from UML
20090922 NXP & SCATE/MPC/C3PO
FMTC & Model Based Design
Local MetaOCaml
MARTES
Hardware Mapping
20090921 Monads in OCaml
20090920 Selling Lisp in a Bag
20090919 SML as a DSL for writing compilers
Extensions to C syntax
20090918 Formal Verification of Timed Systems: A Survey and Perspective
20090913 Staging vs. Partial Evaluation
20090910 Algebra of Programs
20090909 IP - staged image processing
20090904 Matlab parser
Synthesis of implicit models (optimization problems)
20090903 DSLs
20090904 A Methodology for Generating Verified Combinatorial Circuits
20090903 C pretty printing
DSL: syntax and semantics
Prototyping and DSLs
Staged CSP/Pi ?
20090902 Staging Control Flow of Data Driven Languages
20090901 Your generator is my macro
Abstract Interpretation and Scheme -> C mapping
Dynamically Typed Metaprogramming
20090829 CamlP4 and concatenative languages
20090824 MetaOcaml
20090823 Progress in ideas: how to sell Lisp anyway.
20090817 Bison's getting extinct?
20090814 Real men program in C
20090724 How to use C
20090721 ocaml + llvm
future of performance (LtU)
20090720 Writing an LLVM frontend
20090719 Clang - LLVM's C parser
Installing Ocaml + FrontC
First concrete goal
GCC's parser
Survey of existing C parsers
Scheme and Electrical Engineering / Two kinds of programmers
C is not a programming language
Standard way for Metaprogramming C?
Two forms of broken base systems
20090715 The importance of platform
20090714 Staapl's ideas in a broader context
20090628 int f(int *);
Getting Started with c.plt
20090227 Generating/Processing C code
[Reply][About]
[<<][meta][>>][..]