Search

Many language implementations, like C++ and Java, check the types of values and operations to be sure each operation is supported for the types of its operands. An important feature of Standard ML is the type inference system which is somewhat like the type checkers of C++ and Java, but a bit more powerful. A type checker checks the types written by the programmer to be sure each type declaration is consistent with the operations being performed, values being passed to functions, and the values being returned. Compilers for Java and C++ even infer the types of some expressions when polymorphic operators are used. For instance, the addition operator has multiple result types depending on the types of its operands.

The ML in the name Standard ML stands for meta-language. SML was designed as a language for describing languages when it was used as part of the Logic for Computable Functions (LCF) system [9]. Two tools were designed to work with Standard ML for language implementation, ML-lex and ML-yacc. The pattern matching, ease of defining recursive datatypes, the functional nature of the language along with these two tools make Standard ML an excellent language choice for implementing interpreters and compilers.

This paper provides a description of a framework for programming language implementation that is accessible to students in a one semester course focused on programming languages. Rather than concentrating solely on language features, this paper describes a framework where imperative, functional, and logic programming languages are all used to develop a compiler for a non-trivial subset of a functional programming language. Provided by the framework are a virtual machine, a disassember of Python programs, a partial implementation of a Standard ML compiler with suggested tests, and a partial implementation of a type inference system implemented using Prolog, again with suggested tests. Classroom experience gained while using this framework is also shared. A suggested fourteen week sequence is provided. Real reactions from students and reflections on coverage of the ACM 2013 Curricula guildelines conclude the paper.

This is the sample drawing application from the first chapter. It illustrates the use of the tkinter library including many widgets and mouse handling. This program can be downloaded from the text’s website.

This documentation was generated from the Python documentation available by typing from turtle import * help (TurtleScreen) in the Python shell.

In the last chapter we studied sequences which are used to keep track of lists of things where duplicate values are allowed. For instance, there can be two sixes in a sequence or list of integers. In this chapter we look at sets where duplicate values are not allowed. After examining sets we’ll move on to talk about maps. Maps may also be called dictionaries or hash tables.The term hash table actually suggests an implementation of a set or map. The primary focus of this chapter is in understanding hashing. Hashing is a very important concept in Computer Science because it is a very efficient method of searching for a value. To begin the chapter we’ll motivate our interest in hashing, then we’ll develop a hashing algorithm for finding values in a set. We’ll also apply hashing to the building of sets and maps. Then we’ll look at an important technique that uses hashing called memoization and we’ll apply that technique to a couple of problems.

This documentation was generated from the Python documentation available by typing from turtle import * help (Turtle) in the Python shell.

This first chapter introduces Python to readers that have never programmed in Python before. It also provides instructions for installing Python on your computer. The Wing Integrated Development Environment (IDE) is recommended for students learning to program. Wing IDE 101 is the free version of the IDE for educational use. The chapter goes on to introduce classes, objects, and object-oriented programming by developing a drawing application using the Tkinter graphical user interface library. An understanding of object-oriented programming concepts presented in this chapter is necessary before reading the rest of the text. The PyList datatype presented in this chapter is also used in subsequent chapters including Chap. 2. Even if the reader has worked through an introductory text or has a basic understanding of Python, there are concepts from this first chapter that are used throughout the text.

This documentation was generated from the Python documentation available by typing help(list) in the Python shell.

In Chap. 6 binary search trees were defined along with a recursive insert algorithm. The discussion of binary search trees pointed out they have problems in some cases. Binary search trees can become unbalanced, actually quite often. When a tree is unbalanced the complexity of insert, delete, and lookup operations can get as bad as \(\Theta (n)\). This problem with unbalanced binary search trees was the motivation for the development of height-balanced AVL trees by G.M. Adelson-Velskii and E.M. Landis, two Soviet computer scientists, in 1962. AVL trees were named for these two inventors. Their paper on AVL trees [AVL62] described the first algorithm for maintaining balanced binary search trees. The chapter goes on to discuss Splay Trees as another example of balanced binary search trees.

This documentation was generated from the Python documentation available by typing help(int) in the Python shell.

This documentation was generated from the Python documentation available by typing help(float) in the Python shell.

This documentation was generated from the Python documentation available by typing help(str) in the Python shell.

Introduction Syntax Assembly Language C++ Standard ML Compiling Standard ML Prolog Type Inference The CoCo Virtual Machine Specification The Standard ML Basis Library

JCoCo is a virtual machine which includes a built-in assembler. JCoCo executes assembly language programs by first processing the assembly language program and then executing it. The processing of the assembly language program is called assembling.

Chapter six introduces event-driven programming. In an event-driven program, the program goes to an event queue to find the next event and then calls some code to process that event. Graphical User Interface (GUI) programs operate like this. Chapter six introduces event-driven programming using Tkinter, a graphical user interface library for Python programmers.