[<<][meta][>>][..]
Code generation for C-based applications
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
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][>>][..]