We work towards solving the Simultaneous Localization and Mapping (SLAM) problem using a Probabilistic Programming System (PPS). After surveying existing SLAM methods, we choose FastSLAM as the most promising candidate. FastSLAM uses ad-hoc methods for data association, and does not enforce mutual exclusion between observations arriving at the same timestep. This leads to poor accuracy on an example dataset. We propose a new probabilistic model for SLAM that handles association uncertainty and mutual exclusion. We then propose an algorithm for doing inference in this model: FastSLAM-DA (FastSLAM with Data Association), which uses a particle filter with a custom data-driven proposal. We show that FastSLAM-DA performs well on the example where FastSLAM previously failed. However, the new algorithm produces inaccurate maps when there is a high rate of false detections. To remedy this, we propose FastSLAM-DA-RM (FastSLAM with Data Association and Resample-Move), which adds MCMC moves on the recent association variables. We show that FastSLAM-DA-RM performs well where FastSLAM-DA previously failed. Our two new algorithms use no heuristics other than custom proposals, so they are suitable for implementation in a PPS. As a step in this direction, we implement a general-purpose resample-move particle filter in the BLOG PPS, and demonstrate it on a simplified SLAM problem.