[<<][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][>>][..]