Recent Content

The Derivation of Cosine

posted on 2015-02-08 15:10:00

Trigonometry introduces us to a class of new functions which allow us to, among other things, work with angles and solve triangles. We learn about sine and cosine, starting off by defining them as ratios of side lengths of a triangle, and then seeing their relationship to the unit circle. However, one thing is typically left missing: how does one derive the sine and cosine functions? I don't mean "derive" as in "differentiate", I mean "create".

It turns out that calculus is a huge aid here.

Suppose we draw a point \((x,y)\) on the unit circle. For simplicity's sake, let's assume the first quadrant only. Both drawing the radius to this point, and dropping a perpendicular from this point allows us to visualize each Cartesian coordinate as sides of a right triangle. We see that \[x^2 + y^2 = 1.\] If we choose, we can solve for the \(y\)-coordinate to get a closed-form expression for the circle in this quadrant: \[y = \sqrt{1 - x^2}.\]

Finding what the sine and cosine functions are is equivalent to finding a parameterization of \((x,y)\), parameterized by angle. For a circle, angle is defined as the distance along the circumference divided by the radius. Hence, for a unit circle, this is just a unitless measure equal to the arclength of an arc of the circle.

If the unit circle is parameterized by \(\vec r = (x(\theta), y(\theta))\), then we know the unit tangent vector \(\vec T\) is just the derivative of the components: \[\vec T = \left(\frac{dx}{d\theta},\frac{dy}{d\theta}\right).\] From a geometric point of view, a vector can only have two distinct (unit) perpendicular vectors; the vector \((x,y)\) is perpendicular to both \((-y,x)\) and its negation \(-(-y,x)=(y,-x)\). Let's verify thos holds true around the entire unit circle.

Unit circle

Observe that the slope of the vector \(\vec r\) is just \(y/x\). Given we know that \(y=\sqrt{1-x^2}\), we can differentiate this with respect to \(x\) to get \[\frac{dy}{dx} = -\frac{x}{\sqrt{1-x^2}}.\] But this itself is just \(-x/y\), which is the slope of the tangent vector \((-y,x)\). (We choose this tangent vector because we want it to be pointing in the positive \(y\) direction at \((1,0)\).)

Since \[\vec T = (-y,x) = \left(\frac{dx}{d\theta},\frac{dy}{d\theta}\right),\] we arrive at the set of equations

\begin{align} \frac{dx}{d\theta} &= -y\\ \frac{dy}{d\theta} &= x. \end{align}

Taking the first equation and differentiating both sides gives

\begin{equation} \frac{d^2x}{d\theta^2} = -\frac{dy}{d\theta} \end{equation}

which of course, back-substituting, gives

\begin{equation} \frac{d^2x}{d\theta^2} = -x. \end{equation}

This is the familiar differential equation that we know the sine function satisfies. It also turns out to be the differential equation that will allow us to compute the Taylor series, which gives us a constructive definition of sine.

Suppose that \(x = x(\theta)\) has the Maclaurin expansion

\begin{align} x(\theta) = \sum_{k=0}^{\infty} a_k\theta^k. \end{align}

Differentiating twice gives

\begin{align} x''(\theta) = \sum_{k=2}^{\infty} k(k-1)a_k\theta^{k-2}. \end{align}

Note the change in the lower index, where two constant terms got dropped off. But this series is equal to the negation of the original, so

\begin{align} \sum_{k=2}^{\infty} k(k-1)a_k\theta^{k-2} &= -\sum_{k=0}^{\infty} a_k \theta^k\\ &= -\sum_{k=2}^{\infty} a_{k-2} \theta^{k-2}. \end{align}

Matching coefficients, we have \(k(k-1)a_k = -a_{k-2}\). Rearranging gives \[a_k = -\frac{a_{k-2}}{k(k-1)}.\] This is a recurrence relation which we can solve, once we find some boundary conditions.

The coefficients of a Maclaurin series are determined by the derivatives of the function being approximated. Namely, \[a_k = \frac{x^{(k)}(0)}{k!}.\] We will use this to compute two boundary conditions.

Since \((x(0),y(0)) = (1,0)\), then from our basic vector and tangent relations, we know that \((x'(0),y'(0)) = (0,1)\). Hence, \(x'(0) = 0\), which means \(x'(0) \propto a_1 = 0\). Since our recurrence relation is purely multiplicative, every odd-indexed term must be zero. This just leaves the even terms.

Using \(x(0) = 1\), we can tabulate a few terms, and see a general pattern immediately.

\begin{align} a_0 &= 1\\ a_2 &= -\frac{1}{2(2-1)} = -\frac{1}{2\cdot 1}\\ a_4 &= -\frac{-\frac{1}{2\cdot 1}}{4(4-1)} = \frac{1}{4\cdot 3\cdot 2\cdot 1}\\ a_6 &= -\frac{\frac{1}{4\cdot 3\cdot 2\cdot 1}}{6(6-1)} = -\frac{1}{6!}\\ \vdots &= \vdots\\ a_k &= (-1)^{k/2}\frac{1}{k!}. \end{align}

Substituting this into our original Maclaurin series gives us

\begin{align} x(\theta) &= \sum_{k=0,\ k\text{ even}}^{\infty} (-1)^{k/2}\frac{1}{k!}\theta^k, \end{align}

which can be written with \(k\mapsto 2k\) as

\begin{align} x(\theta) &= \sum_{k=0}^{\infty} (-1)^{k}\frac{1}{(2k)!}\theta^{2k}. \end{align}

As desired, this is the definition of cosine. Tidying up, we have

\begin{align} \cos \theta &= \sum_{k=0}^{\infty} (-1)^{k}\frac{\theta^{2k}}{(2k)!}. \end{align}

Graphics in Chicken Scheme on OS X

posted on 2015-01-29 11:14:00

CHICKEN Scheme is a fantastic Scheme system. It is pretty portable, and lets one interact with C relatively painlessly.

Getting graphics, specifically SDL, to work on OS X is rather painful. It's not really CHICKEN's fault though; SDL has requirements on which thread owns what.

Here's the quick way to get started using graphics in CHICKEN Scheme using the doodle library.

First, as a one-time thing, install all of the system dependencies.

# Install Cairo
brew install cairo
# Install SDL requirements
brew install sdl sdl_ttf sdl_image sdl_gfx sdl_net

Next, install some CHICKEN dependency libraries ("eggs"):

chicken-install sdl matchable

The library matchable isn't a strict requirement, just a requirement for the example below.

You should have XQuartz installed. If you don't, go do that.

We need to install doodle separately as follows. We need to tell it where pkgconfig is from X11 so doodle can be built properly.

PKG_CONFIG_PATH=/opt/X11/lib/pkgconfig chicken-install doodle

We should be done with all of the one-time bits. Now we can write graphics code. Unfortunately, there are a few hitches. As mentioned previously, SDL has certain requirements on what thread main is in, and so on. This means that interactive graphics development on OS X is a bit of a pain, if not currently impossible.

In your Scheme file, say graphics.scm, you must have the following at the top:

(use matchable doodle)

;; Required on OS X.
(declare (foreign-declare "#include<SDL/SDL.h>\n"))
(foreign-code "SDL_Init(SDL_INIT_EVERYTHING);")

;; graphics code follows...

Now we can write graphics code. See the doodle API for the functions you can use, and see the end of this post for an example application.

Once we've written our application, we can compile it. We need to link it with SDL and provide the necessary SDL compilation configuration parameters, which can be injected using the sdl-config utility program. The compilation line looks like this:

csc graphics.scm -lSDLmain `sdl-config --cflags --libs`

Now we should have an executable which we can run: ./graphics.

An example application, taken from the example on the doodle API page:

(use matchable doodle)

;; Required on OS X.
(declare (foreign-declare "#include<SDL/SDL.h>\n"))
(foreign-code "SDL_Init(SDL_INIT_EVERYTHING);")

(define *paint* #f)

(define red '(1 0 0 0.3))

(world-inits
 (lambda ()
   (clear-screen)
   (set-font! "Vollkorn" 18 red)
   (text (/ doodle-width 2)
         (/ doodle-height 2) '("Welcome to doodle!"
                               "Click the left mouse button to draw circles"
                               "Press ESC to leave")
         align: #:center)))

(world-changes
 (lambda (events dt exit)
   (for-each
    (lambda (e)
      (match e
       (('mouse 'pressed x y 1)
        (set! *paint* #t)
        (filled-circle x y 10 red))
       (('mouse 'released x y 1)
        (set! *paint* #f))
       (('mouse 'moved x y)
        (when *paint*
          (filled-circle x y 10 red)))
       (('key 'pressed #\esc)
        (exit #t))
       (else (void))))
    events)))

(new-doodle title: "Doodle paint" background: solid-white)
(run-event-loop)

Burning CDs for Macintosh System 7 from OS X

posted on 2015-01-29 10:57:00

I have a Macintosh Quadra 650 with System 7.6.1 on it. I wanted to get software onto it, namely web browsers and other things. How does one do that on OS X?

It's actually relatively simple. Get the software you want into a folder on your machine. Let's say ~/software. It seems to work best if this software has been compressed with StuffIt Expander. If you decompress it on your OS X ("host") machine, things don't seem to work as well and things get lost.

We will need cdrtools, so install that.

brew install cdrtools

Now that we have that, we can make an image we can burn. The image needs to have HFS as its file system, as this is what is used my System 7. Making images with this file system became unsupported in versions of OS X after 10.5 "Leopard", but mkisofs from cdrtools still has this capability.

mkisofs -hfs -o software.iso ~/software

Once the image is made, software.iso, you can open it with Disk Utility and burn it. I recommend burning at the slowest speed and verifying it.

When you pop the disk into your old Mac, you should be able to explore the contents of the CD.

Inauguration of Style Warning

posted on 2015-01-22 20:40:00

So, my last blog basically died. Some of you may notice that it has redirected to the Wayback Machine.

There was a catastrophic mishap, of course accidental, where the database of the website was deleted. I, assuming all system administrative duties were taken care of, did not ensure there was a complete backup. So, a lot of new material, and all partial drafts, are gone.

It's too bad, but not the end of the world. Slowly I will be manually migrating old content from Symbo1ics to Style Warning.

Style Warning is this new shiny website. It isn't as fancy as Symbo1ics in terms of features, because I decided I will go with nearly the bare minimum. This time, instead of Wordpress for dynamic content, I am going with Coleslaw, a Jekyll-like static blog generator written in Common Lisp.

Wordpress was a behemoth of PHP. Go check one of the sources on Symbo1ics. Your eyes will bleed. It is huge, bloated, and whenever something popped up on the front page of Hacker News, the entire site would come to a screeching halt. Also, the constant updates to the website were annoying. Eventually, it just began to bit rot, which in turn, made it insecure.

Why change domains? One might say this is a re-branding. There will be mostly the same kind of content, but just under a different name. Symbo1ics was originally supposed to be a website about my Lisp machines, but I never got to documenting them. I still hope to one day. Of course, "Symbo1ics" is a play on the name "Symbolics", which was the name of the at the time successful company that produced Lisp machines and a plethora of software.

Using the name "Symbo1ics" had its own problems though. Here is a typical exchange over the phone.

Them: So, Robert, what is your email address?

Me: It is Q U A D at S Y M B O the number one I C S dot C O M. Quad at symbolics dot com, but with the L replaced with the number one.

Them: So let me repeat. It is quad at S Y M B O the number one I C S dot com?

Me: Yes.

Can you see the problem? Also, whenever I write the email address, I have to always explicitly follow up saying to pay particular attention to the number 1 in the name. Many have told me eventually that they sent emails to symbolics.com, which is a domain currently being wasted by an investor for advertising.

Hopefully such issues will be partially mitigated by the new domain.

This website isn't complete. There are some things that I need to add or fix, like permalinking or maybe even comments. It also needs a better look. But for now, it's an improvement over the previous system.

Stay tuned!

Things I Want in Common Lisp

posted on 2014-06-23

This post contains some things I want in Common Lisp, in no particular order. I'll try to keep things short and to the point.

Shared Libraries

Right now, the concept of a "library" in idiomatic Lisp is a .asd file along with some Lisp source code. I don't always want to distribute the source code. (Though most of the time I do.)

It would be nice if we had both statically and dynamically linkable/loadable libraries like those from C. Of course Lisp's model of how things work doesn't quite match up to this, but I think it could be done if implementations standardized on some loading (and unloading?) strategy.

As far as I know, the closest thing we can do to this is something like concatenating FASL files. But I would like something more robust and semi-standard across implementations.

Standard Calling Interface

Lisp isn't too friendly with the outside world. It is difficult to call Lisp code from another application, unless you're using a special implementation. Right now, message passing seems to be the only way to go.

It would be nice if there was some standard interface to call into Lisp with. Maybe even with just other Lisp applications. Something like a calling convention.

A Graphics/GUI Library

I honestly can't recommend Lisp to anyone personally who wants to do graphical programming. There's the commercial LispWorks CAPI which works relatively well, but it comes at a cost.

Right now, all of the existing open source "solutions" are junk. Qt is junk. SDL is marginally better but still junk. Garnet is old and junk. McCLIM is broken and junk (though it's interesting!). Tcl/Tk is antiquated and junk.

This has been the largest pain point for me for writing open source scientific simulation code.

Better Type Abstractions

I want to be able to have, for example, a hash table that can specialize efficiently on different types. In Lisp, you essentially either support every type (perhaps with a few restrictions) inefficiently, or you support a single type efficiently.

I don't think there exists a good way to have generic and efficient code reuse right now. All of the polymorphic stuff built in to Lisp is efficient only because the compiler knows about it.

I ranted about this a little bit here.

TYPECASE is not a solution. Inlining is not a solution.

Polymorphic/algebraic/recursive types that the compiler knows about is probably the most difficult thing on this list, since it gets into language semantics.

An Interface/API Mechanism

It would be nice to programmatically specify interfaces/APIs. C has header files. C++ has class declarations. SML has signatures/structures/functors. I would love to in my source code to specify programmatically what is provided.

Packages do not solve this problem. Packages just let us group symbols together. Packages cannot tell the difference between a function, type, class, or variable. Many people still use packages as the way to write an "interface" though. I do, usually with an annotation of what each symbol is. But that isn't very good.

I've tried my hand at some sort of DEFINE-API and DEFINE-INTERFACE mechanism.

As an extension, although it doesn't quite fit with the philosophy of generic functions, it would be nice to specify which methods a subclass should implement to really be a subclass of that class. And it would be nice if this was checked statically.

I started working on something at least dynamic many years ago but never finished it. You can find it here.

Better Static Analyzers

It would be nice if we could have better static analysis tools for Lisp that aren't baked into a single Lisp compiler. Lisp should be amenable to this, even if the analyzer has to make some bold assumptions about the code.

Better Executable Support

Whole program optimization, tree shaking, all that would be nice. There's LispWorks' deliver mechanism, which has some sophisticated features, but that's about it. Everyone else just dumps out an image with a little bit of start up code, and maybe some compression.

Fast start-up times would also be very useful for small, oft-called utilities.

Seamless Arbitrary Precision Floats

Arbitrary precision floats (including complex floats) would be nice if they were seamlessly integrated into the language compiler/runtime without any performance penalty on other types.

CLISP has this, but that's it. An MPFR interface is in development. (SB-MPFR, Fateman's MPFR interface.) Something portable would be nice. I myself started working on an MPFR interface with CFFI but have little to show. And of course it's not integrated with the rest of Lisp like all of the other numeric functions are.

A standard way of controlling precision would need to be developed. I think this is a non-trivial problem; simply setting some global *long-float-precision* might not be good enough.

Damage Control Mechanisms

Lisp has some built-in things to ensure that standard symbols and definitions are not screwed around with. It would be nice if implementations had some options to protect the current state of the Lisp image from being destructively modified in certain ways. It would also be nice if some operations were reversible, such as unloading a library or cleanly removing the existence of a package (and ensuring it gets cleaned up from memory).

Efficient Finalizers on Classes

It would be nice if there existed efficient class-wide finalizers, so there could be smoother integration with C stuff. If a Lisp object gets deallocated, then the corresponding C stuff gets free'd as well. (Of course, this should be programmed by the programmer, not some special construct.)

Right now, trivial-garbage allows one to set finalizers on individual Lisp objects, and of course we can set a finalizer for every object allocated by a class easily.

Predictable Tail Call Elimination

I don't know if it would be right to bake TCE into the standard itself, but it would be nice if I could turn it on and off via some DECLARE or DECLAIM syntax.

Some implementations of course do some TCE with the right compiler policy, but more granularity and less "you get TCE and the kitchen sink of optimizations" would be nice.

This blog covers tutorial, scheme, retro, programming, math, lisp

View content from 2014-06, 2015-01, 2015-02


Unless otherwise credited all material copyright © 2015 by Robert Smith